723
汽車大全
原子變量與非阻塞同步機製（第十五章）
原子變量與非阻塞同步機製
與基於鎖的方案相比，非阻塞算法在設計和實現上都要負責得多，但它們在可伸縮性和活躍性上擁有巨大的優勢。
原子變量提供了與volatile類型變量相同的內存語義，此外還支持原子的更新操作，從而使它們更加適用於實現計數器、序列發生器和統計數據收集等，同時還能比基於鎖的方法提供更高的可伸縮性。
獨占鎖是一種悲觀技術----它假設最壞的情況。
現在，幾乎所有的現代處理器中都包含了某種形式的原子讀-改-寫指令，例如比較並交換（Compare-and-Swap）或者關聯加載/條件存儲（Load-Linked/Store-Condition）。
1. 比較並交換（CAS）
CAS包含了3個操作數----需要讀寫的值V、進行比較的值A和擬寫入的新值B。當且僅當V的值等於A時，CAS才會通過原子方式用新值B來更新V的值，否則不會執行任何操作，無論V的值是否等於A，都將返回V的原值。
當多個線程嚐試使用CAS同時更新同一個變量時，隻有其中一個線程能更新變量的值，而其他線程都將失敗，然而，失敗的線程並不會掛起，而是被告知在這次競爭中失敗，並可以再次嚐試。
2. JVM對CAS的支持
在Java5.0中引入了地城的支持，在int、long和對象的引用等類型上都公開了CAS操作，並且JVM把它們編譯為底層提供的最有效方法。
3. 原子變量類
共有12個原子變量類，可分為4組：標量類（Scalar）、更新器類、數組類以及複合變量類。最常用的原子變量就是標量類：AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。所有這些類都支持CAS，此外，AtomicInteger和AtominLong還支持算術運算。
- 原子變量是一種“更好的volatile”
- 原子變量的效率更高，可伸縮性更好
4. 非阻塞算法
如果在某種算法中，一個線程的失敗或掛起不會導致其他線程也失敗或掛起，那麼這種算法就被稱為非阻塞算法。如果在算法的每個步驟中都存在某個線程能夠執行下去，那麼這種算法也被稱為無鎖（Lock-Free）算法。
5. ABA問題
ABA問題是一種異常現象：如果在算法中的節點可以被循環使用，那麼在使用“比較並交換”指令時就可能出現這種問題。在CAS操作中將判斷“V的值是否仍然為A？”，並且如果是的話就繼續執行更新操作，在大多數情況下，包括本章給出的示例，這種判斷是完全足夠的。然而，有時候還需要知道“自從上次看到V的值為A以來，這個值是否發生了變化？”，在某些算法中，如果V的值首先由A變成B，再由B變成A，那麼仍然被認為是發生了變化，並需要重新執行算法中的某些步驟。
解決ABA問題的一個簡單方法是：不是更新某個引用的值，而是更新兩個值，包括一個引用和一個版本號。即使這個值由A變為B，然後又變為A，版本號也將是不同的。
AtomicStampedReference、AtomicMarkableReference支持在兩個變量上執行原子的條件更新。AtomicStampedReference將更新一個“對象-引用”二元組，通過在引用上加上“版本號”，從而避免ABA問題。AtomicMarkableReference將更新一個“對象引用-布爾值”二元組，在某些算法中將通過這種二元組使節點保存在鏈表中同時又將其標記為“已刪除的節點”。
最後更新：2017-11-04 18:33:53