原子變量與非阻塞同步機制（第十五章）

與基于鎖的方案相比，非阻塞算法在設計和實作上都要負責得多，但它們在可伸縮性和活躍性上擁有巨大的優勢。

原子變量提供了與volatile類型變量相同的記憶體語義，此外還支援原子的更新操作，進而使它們更加适用于實作計數器、序列發生器和統計資料收集等，同時還能比基于鎖的方法提供更高的可伸縮性。

獨占鎖是一種悲觀技術----它假設最壞的情況。

現在，幾乎所有的現代處理器中都包含了某種形式的原子讀-改-寫指令，例如比較并交換（Compare-and-Swap）或者關聯加載/條件存儲（Load-Linked/Store-Condition）。

CAS包含了3個操作數----需要讀寫的值V、進行比較的值A和拟寫入的新值B。當且僅當V的值等于A時，CAS才會通過原子方式用新值B來更新V的值，否則不會執行任何操作，無論V的值是否等于A，都将傳回V的原值。

當多個線程嘗試使用CAS同時更新同一個變量時，隻有其中一個線程能更新變量的值，而其他線程都将失敗，然而，失敗的線程并不會挂起，而是被告知在這次競争中失敗，并可以再次嘗試。

在Java5.0中引入了地城的支援，在int、long和對象的引用等類型上都公開了CAS操作，并且JVM把它們編譯為底層提供的最有效方法。

共有12個原子變量類，可分為4組：标量類（Scalar）、更新器類、數組類以及複合變量類。最常用的原子變量就是标量類：AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。所有這些類都支援CAS，此外，AtomicInteger和AtominLong還支援算術運算。

原子變量是一種“更好的volatile”

原子變量的效率更高，可伸縮性更好

如果在某種算法中，一個線程的失敗或挂起不會導緻其他線程也失敗或挂起，那麼這種算法就被稱為非阻塞算法。如果在算法的每個步驟中都存在某個線程能夠執行下去，那麼這種算法也被稱為無鎖（Lock-Free）算法。

ABA問題是一種異常現象：如果在算法中的節點可以被循環使用，那麼在使用“比較并交換”指令時就可能出現這種問題。在CAS操作中将判斷“V的值是否仍然為A？”，并且如果是的話就繼續執行更新操作，在大多數情況下，包括本章給出的示例，這種判斷是完全足夠的。然而，有時候還需要知道“自從上次看到V的值為A以來，這個值是否發生了變化？”，在某些算法中，如果V的值首先由A變成B，再由B變成A，那麼仍然被認為是發生了變化，并需要重新執行算法中的某些步驟。

解決ABA問題的一個簡單方法是：不是更新某個引用的值，而是更新兩個值，包括一個引用和一個版本号。即使這個值由A變為B，然後又變為A，版本号也将是不同的。

AtomicStampedReference、AtomicMarkableReference支援在兩個變量上執行原子的條件更新。AtomicStampedReference将更新一個“對象-引用”二進制組，通過在引用上加上“版本号”，進而避免ABA問題。AtomicMarkableReference将更新一個“對象引用-布爾值”二進制組，在某些算法中将通過這種二進制組使節點儲存在連結清單中同時又将其标記為“已删除的節點”。