CAS無鎖實作原理以及ABA問題

       CAS（比較與交換，Compare and swap） 是一種有名的無鎖算法。無鎖程式設計，即不使用鎖的情況下實作多線程之間的變量同步，也就是在沒有線程被阻塞的情況下實作變量的同步，是以也叫非阻塞同步（Non-blocking Synchronization）。實作非阻塞同步的方案稱為“無鎖程式設計算法”（ Non-blocking algorithm）。

為什麼要用CAS

       在多線程高并發程式設計的時候，最關鍵的問題就是保證臨界區的對象的安全通路。通常是用加鎖來處理，其實加鎖本質上是将并發轉變為串行來實作的，勢必會影響吞吐量。而且線程的數量是有限的，依賴于作業系統，而且線程的建立和銷毀帶來的性能損耗是不可以忽略掉的。雖然現在基本都是用線程池來盡可能的降低不斷建立線程帶來的性能損耗。對于并發控制而言，鎖是一種悲觀政策，會阻塞線程執行。而無鎖是一種樂觀政策，它會假設對資源的通路時沒有沖突的，既然沒有沖突就不需要等待，線程不需要阻塞。那多個線程共同通路臨界區的資源怎麼辦呢，無鎖的政策采用一種比較交換技術CAS（compare and swap）來鑒别線程沖突，一旦檢測到沖突，就重試目前操作直到沒有沖突為止。

       與鎖相比，CAS會使得程式設計比較複雜，但是由于其優越的性能優勢，以及天生免疫死鎖（根本就沒有鎖，當然就不會有線程一直阻塞了），更為重要的是，使用無鎖的方式沒有所競争帶來的開銷，也沒有線程間頻繁排程帶來的開銷大，他比基于鎖的方式有更優越的性能，是以在目前被廣泛應用，我們在程式設計時也可以适當的使用。不過由于CAS編碼确實稍微複雜，而且jdk作者本身也不希望你直接使用unsafe（後面會講到）來進行代碼的編寫，是以如果不能深刻了解CAS以及unsafe還是要慎用，使用一些别人已經實作好的無鎖類或者架構就好了。

CAS原理分析

       一個CAS方法包含三個參數CAS(V,E,N)。V表示要更新的變量，E表示預期的值，N表示新值。隻有當V的值等于E時，才會将V的值修改為N。如果V的值不等于E，說明已經被其他線程修改了，目前線程可以放棄此操作，也可以再次嘗試次操作直至修改成功。基于這樣的算法，CAS操作即使沒有鎖，也可以發現其他線程對目前線程的幹擾（臨界區值的修改），并進行恰當的處理。

      額外引申技術點：上面說到目前線程可以發現其他線程對臨界區資料的修改，這點可以使用volatile進行保證。volatile實作了JMM中的可見性。使得對臨界區資源的修改可以馬上被其他線程看到，它是通過添加記憶體屏障實作的。具體實作原理請自行搜尋volatile

ABA 問題

       由于 CAS 設計機制就是擷取某兩個時刻(初始預期值和目前記憶體值)變量值，并進行比較更新，是以說如果在擷取初始預期值和目前記憶體值這段時間間隔内，變量值由 A 變為 B 再變為 A，那麼對于 CAS 來說是不可感覺的，但實際上變量已經發生了變化；解決辦法是在每次擷取時加版本号，并且每次更新對版本号 +1，這樣當發生 ABA 問題時通過版本号可以得知變量被改動過。JDK 1.5 以後的 AtomicStampedReference 類就提供了此種能力，其中的 compareAndSet 方法就是首先檢查目前引用是否等于預期引用，并且目前标志是否等于預期标志，如果全部相等，則以原子方式将該引用和該标志的值設定為給定的更新值。

循環時間長開銷大

       所謂循環時間長開銷大問題就是當 CAS 判定變量被修改了以後則放棄本次修改，但往往為了保證資料正确性該計算會以循環的方式再次發起 CAS，如果多次 CAS 判定失敗，則會産生大量的時間消耗和性能浪費；如果JVM能支援處理器提供的pause指令那麼效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執行指令（de-pipeline）,使CPU不會消耗過多的執行資源，延遲的時間取決于具體實作的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環的時候因記憶體順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），進而提高CPU的執行效率。

隻能保證一個共享變量的原子操作

CAS 隻對單個共享變量有效，當操作涉及跨多個共享變量時 CAS 無效；從 JDK 1.5開始提供了 AtomicReference 類來保證引用對象之間的原子性，你可以把多個變量放在一個對象裡來進行 CAS 操作

Unsafe是CAS的核心類，Java無法直接通路底層作業系統，而是通過本地（native）方法來通路。不過盡管如此，JVM還是開了一個後門，JDK中有一個類Unsafe，它提供了硬體級别的原子操作。

valueOffset表示的是變量值在記憶體中的偏移位址，因為Unsafe就是根據記憶體偏移位址擷取資料的原值的。

value是用volatile修飾的，保證了多線程之間看到的value值是同一份。

在java領域的廣泛應用

jdk中的CAS實作java.util.concurrent.atomic包，該包下的類都是采用CAS來實作的無鎖。