CAS的英文為Compare and Swap 翻譯為比較并交換。

CAS加volatile關(guān)鍵字是實現(xiàn)并發(fā)包的基石。沒有CAS就不會有并發(fā)包，synchronized是一種獨(dú)占鎖、悲觀鎖，java.util.concurrent中借助了CAS指令實現(xiàn)了一種區(qū)別于synchronized的一種樂觀鎖。

一、什么是樂觀鎖與悲觀鎖？

樂觀鎖和悲觀鎖是一種概念和思想：

悲觀鎖：總是假設(shè)最壞的情況，每次去拿數(shù)據(jù)的時候都認(rèn)為別人會修改，所以每次在拿數(shù)據(jù)的時候都會上鎖，這樣當(dāng)?shù)诙€線程想拿這個數(shù)據(jù)的時候，第二個線程會一直堵塞，直到第一個釋放鎖，他拿到鎖后才可以訪問。傳統(tǒng)的數(shù)據(jù)庫里面就用到了這種鎖機(jī)制，例如：行鎖，表鎖，讀鎖，寫鎖，都是在操作前先上鎖。java中的synchronized的實現(xiàn)也是一種悲觀鎖。

樂觀鎖：樂觀鎖概念為，每次拿數(shù)據(jù)的時候都認(rèn)為別的線程不會修改這個數(shù)據(jù)，所以不會上鎖，但是在更新的時候會判斷一下在此期間別的線程有沒有修改過數(shù)據(jù)，樂觀鎖適用于讀操作多的場景，這樣可以提高程序的吞吐量。在Java中
java.util.concurrent.atomic包下面的原子變量就是使用了樂觀鎖的一種實現(xiàn)方式CAS實現(xiàn)。

二、背景：

在JDK 5之前Java語言是靠 synchronized 關(guān)鍵字保證同步的，這會導(dǎo)致有鎖。鎖機(jī)制存在以下問題：

• 在多線程競爭下，加鎖、釋放鎖會導(dǎo)致比較多的上下文切換和調(diào)度延時，引起性能問題。
• 一個線程持有鎖會導(dǎo)致其它所有需要此鎖的線程掛起。
• 如果一個優(yōu)先級高的線程等待一個優(yōu)先級低的線程釋放鎖會導(dǎo)致優(yōu)先級倒置，引起性能風(fēng)險。

Volatile關(guān)鍵字能夠在并發(fā)條件下，強(qiáng)制將修改后的值刷新到主內(nèi)存中來保持內(nèi)存的可見性。通過 CPU內(nèi)存屏障禁止編譯器指令性重排來保證并發(fā)操作的有序性

如果多個線程同時操作 Volatile 修飾的變量，也會造成數(shù)據(jù)的不一致。

public class Test {
    public volatile int inc = 0;
     
    public void increase() {
        inc++;
    }     
    public static void main(String[] args) {
        final Test test = new Test();
        for(int i=0;i<10;i++){
            new Thread(){
                public void run() {
                    for(int j=0;j<1000;j++)
                        test.increase();
                };
            }.start();
        }    
        while(Thread.activeCount()>1)
            Thread.yield();
        System.out.println(test.inc);
    }
}

事實上運(yùn)行它會發(fā)現(xiàn)每次運(yùn)行結(jié)果都不一致，都是一個小于10000的數(shù)字。

假如某個時刻變量 inc 的值為10：

• 線程1對變量進(jìn)行自增操作，線程1先讀取了變量inc的原始值，然后線程1被阻塞了；
• 然后線程2對變量進(jìn)行自增操作，線程2也去讀取變量inc的原始值，由于線程1只是對變量inc進(jìn)行讀取操作，而沒有對變量進(jìn)行修改操作，所以不會導(dǎo)致線程2的工作內(nèi)存中緩存變量inc的緩存行無效，所以線程2會直接去主存讀取inc的值，發(fā)現(xiàn)inc的值時10，然后進(jìn)行加1操作，并把11寫入工作內(nèi)存，最后寫入主存。
• 然后線程1接著進(jìn)行加1操作，由于已經(jīng)讀取了inc的值，注意此時在線程1的工作內(nèi)存中inc的值仍然為10，所以線程1對inc進(jìn)行加1操作后inc的值為11，然后將11寫入工作內(nèi)存，最后寫入主存。
• 那么兩個線程分別進(jìn)行了一次自增操作后，inc只增加了1。

之所以出現(xiàn)還是 volatile 只是保證讀寫具有原子性，但是對于 ++ 操作的復(fù)合操作是不存在原子操作的。只能在有限的一些情形下使用 volatile 變量替代鎖。要使 volatile 變量提供理想的線程安全，比如：對變量的寫操作不依賴于當(dāng)前值。

volatile 是不錯的機(jī)制，但是 volatile 不能保證原子性。因此對于同步最終還是要回到鎖機(jī)制上來。

獨(dú)占鎖是一種悲觀鎖，synchronized 就是一種獨(dú)占鎖，會導(dǎo)致其它所有需要鎖的線程掛起，等待持有鎖的線程釋放鎖。而另一個更加有效的鎖就是樂觀鎖。所謂樂觀鎖就是，每次不加鎖而是假設(shè)沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。樂觀鎖用到的機(jī)制就是 CAS。

三、CAS原理：

CAS 操作包含三個操作數(shù) -- 內(nèi)存位置、預(yù)期數(shù)值和新值。CAS 的實現(xiàn)邏輯是將內(nèi)存位置處的數(shù)值與預(yù)期數(shù)值想比較，若相等，則將內(nèi)存位置處的值替換為新值。若不相等，則不做任何操作。

在 Java 中，Java 并沒有直接實現(xiàn) CAS，CAS 相關(guān)的實現(xiàn)是通過 C++ 內(nèi)聯(lián)匯編的形式實現(xiàn)的。Java 代碼需通過 JNI 才能調(diào)用。

在JVM中的CAS操作就是基于處理器的CMPXCHG匯編指令實現(xiàn)的，因此，JVM中的CAS的原子性是處理器保障的

CAS 是一條 CPU 的原子指令（cmpxchg指令），不會造成所謂的數(shù)據(jù)不一致問題，Unsafe 提供的 CAS 方法（如compareAndSwapXXX）底層實現(xiàn)即為 CPU 指令 cmpxchg

對
java.util.concurrent.atomic 包下的原子類 AtomicInteger 中的 compareAndSet 方法進(jìn)行分析，相關(guān)分析如下：

public class AtomicInteger extends Number implements java.io.Serializable {    
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();    
    private static final long valueOffset;   
    static {       
        try {            
            // 計算變量 value 在類對象中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }        private volatile int value;    
    public final boolean compareAndSet(int expect, int update) {                /**
         * compareAndSet 實際上只是一個殼子，主要的邏輯封裝在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }    
    // ......
}
　　public final class Unsafe {    
      // compareAndSwapInt 是 native 類型的方法，繼續(xù)往下看
      public final native boolean compareAndSwapInt(Object o, long offset,  int expected,  int x);    
      // ......
  }

public class AtomicInteger extends Number implements java.io.Serializable {    
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();    
    private static final long valueOffset;   
    static {       
        try {            
            // 計算變量 value 在類對象中的偏移
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }        private volatile int value;    
    public final boolean compareAndSet(int expect, int update) {                /**
         * compareAndSet 實際上只是一個殼子，主要的邏輯封裝在 Unsafe 的 
         * compareAndSwapInt 方法中
         */
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }    
    // ......
}
　　public final class Unsafe {    
      // compareAndSwapInt 是 native 類型的方法，繼續(xù)往下看
      public final native boolean compareAndSwapInt(Object o, long offset,  int expected,  int x);    
      // ......
  }

上面的分析看起來比較多，不過主流程并不復(fù)雜。如果不糾結(jié)于代碼細(xì)節(jié)，還是比較容易看懂的。接下來，我會分析 Windows 平臺下的 Atomic::cmpxchg 函數(shù)。繼續(xù)往下看吧。

// atomic_windows_x86.inline.hpp
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:
              inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

上面的代碼由 LOCK_IF_MP 預(yù)編譯標(biāo)識符和 cmpxchg 函數(shù)組成。為了看到更清楚一些，我們將 cmpxchg 函數(shù)中的 LOCK_IF_MP 替換為實際內(nèi)容。如下：

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {  
  // 判斷是否是多核 CPU
  int mp = os::is_MP();
  __asm {    // 將參數(shù)值放入寄存器中
    mov edx, dest    // 注意: dest 是指針類型，這里是把內(nèi)存地址存入 edx 寄存器中
    mov ecx, exchange_value
    mov eax, compare_value    
    // LOCK_IF_MP
    cmp mp, 0
    /*
     * 如果 mp = 0，表明是線程運(yùn)行在單核 CPU 環(huán)境下。此時 je 會跳轉(zhuǎn)到 L0 標(biāo)記處，
     * 也就是越過 _emit 0xF0 指令，直接執(zhí)行 cmpxchg 指令。也就是不在下面的 cmpxchg 指令
     * 前加 lock 前綴。
     */
    je L0    /*
     * 0xF0 是 lock 前綴的機(jī)器碼，這里沒有使用 lock，而是直接使用了機(jī)器碼的形式。至于這樣做的
     * 原因可以參考知乎的一個回答：
     *     https://www.zhihu.com/question/50878124/answer/123099923
     */ 
    _emit 0xF0L0:    /*
     * 比較并交換。簡單解釋一下下面這條指令，熟悉匯編的朋友可以略過下面的解釋:
     *   cmpxchg: 即“比較并交換”指令
     *   dword: 全稱是 double word，在 x86/x64 體系中，一個 
     *          word = 2 byte，dword = 4 byte = 32 bit
     *   ptr: 全稱是 pointer，與前面的 dword 連起來使用，表明訪問的內(nèi)存單元是一個雙字單元
     *   [edx]: [...] 表示一個內(nèi)存單元，edx 是寄存器，dest 指針值存放在 edx 中。
     *          那么 [edx] 表示內(nèi)存地址為 dest 的內(nèi)存單元
     *          
     * 這一條指令的意思就是，將 eax 寄存器中的值（compare_value）與 [edx] 雙字內(nèi)存單元中的值
     * 進(jìn)行對比，如果相同，則將 ecx 寄存器中的值（exchange_value）存入 [edx] 內(nèi)存單元中。
     */
    cmpxchg dword ptr [edx], ecx
  }
}

到這里 CAS 的實現(xiàn)過程就講完了，CAS 的實現(xiàn)離不開處理器的支持。如上面源代碼所示，程序會根據(jù)當(dāng)前處理器的類型來決定是否為 cmpxchg 指令添加 lock 前綴。如果程序是在多處理器上運(yùn)行，就為 cmpxchg 指令加上 lock 前綴（lock cmpxchg）。反之，如果程序是在單處理器上運(yùn)行，就省略 lock 前綴（單處理器自身會維護(hù)單處理器內(nèi)的順序一致性，不需要 lock 前綴提供的內(nèi)存屏障效果）。

intel 的手冊對 lock 前綴的說明如下：

• 確保對內(nèi)存的讀 - 改 - 寫操作原子執(zhí)行。在 Pentium 及 Pentium 之前的處理器中，帶有 lock 前綴的指令在執(zhí)行期間會鎖住總線，使得其他處理器暫時無法通過總線訪問內(nèi)存。很顯然，這會帶來昂貴的開銷。從 Pentium 4，Intel Xeon 及 P6 處理器開始，intel 在原有總線鎖的基礎(chǔ)上做了一個很有意義的優(yōu)化：如果要訪問的內(nèi)存區(qū)域（area of memory）在 lock 前綴指令執(zhí)行期間已經(jīng)在處理器內(nèi)部的緩存中被鎖定（即包含該內(nèi)存區(qū)域的緩存行當(dāng)前處于獨(dú)占或以修改狀態(tài)），并且該內(nèi)存區(qū)域被完全包含在單個緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會一直被鎖定，其它處理器無法讀 / 寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低 lock 前綴指令的執(zhí)行開銷，但是當(dāng)多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時，仍然會鎖住總線。
• 禁止該指令與之前和之后的讀和寫指令重排序。
• 把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

上面的第 2 點和第 3 點所具有的內(nèi)存屏障效果，足以同時實現(xiàn) volatile 讀和 volatile 寫的內(nèi)存語義。

經(jīng)過上面的這些分析，現(xiàn)在我們終于能明白為什么 JDK 文檔說 CAS 同時具有 volatile 讀和 volatile 寫的內(nèi)存語義了。

Java 的 CAS 會使用現(xiàn)代處理器上提供的高效機(jī)器級別原子指令，這些原子指令以原子方式對內(nèi)存執(zhí)行讀 - 改 - 寫操作，這是在多處理器中實現(xiàn)同步的關(guān)鍵（從本質(zhì)上來說，能夠支持原子性讀 - 改 - 寫指令的計算機(jī)器，是順序計算圖靈機(jī)的異步等價機(jī)器，因此任何現(xiàn)代的多處理器都會去支持某種能對內(nèi)存執(zhí)行原子性讀 - 改 - 寫操作的原子指令）。同時，volatile 變量的讀 / 寫和 CAS 可以實現(xiàn)線程之間的通信。把這些特性整合在一起，就形成了整個 concurrent 包得以實現(xiàn)的基石。如果我們仔細(xì)分析 concurrent 包的源代碼實現(xiàn)，會發(fā)現(xiàn)一個通用化的實現(xiàn)模式：

• 首先，聲明共享變量為 volatile；
• 然后，使用 CAS 的原子條件更新來實現(xiàn)線程之間的同步；
• 同時，配合以 volatile 的讀 / 寫和 CAS 所具有的 volatile 讀和寫的內(nèi)存語義來實現(xiàn)線程之間的通信。

AQS，非阻塞數(shù)據(jù)結(jié)構(gòu)和原子變量類（
java.util.concurrent.atomic 包中的類），這些 concurrent 包中的基礎(chǔ)類都是使用這種模式來實現(xiàn)的，而 concurrent 包中的高層類又是依賴于這些基礎(chǔ)類來實現(xiàn)的。從整體來看，concurrent 包的實現(xiàn)示意圖如下：

JVM中的CAS（堆中對象的分配）：　

Java 調(diào)用 new object() 會創(chuàng)建一個對象，這個對象會被分配到 JVM 的堆中。那么這個對象到底是怎么在堆中保存的呢？

首先，new object() 執(zhí)行的時候，這個對象需要多大的空間，其實是已經(jīng)確定的，因為 java 中的各種數(shù)據(jù)類型，占用多大的空間都是固定的（對其原理不清楚的請自行Google）。那么接下來的工作就是在堆中找出那么一塊空間用于存放這個對象。

在單線程的情況下，一般有兩種分配策略：

1. 指針碰撞：這種一般適用于內(nèi)存是絕對規(guī)整的（內(nèi)存是否規(guī)整取決于內(nèi)存回收策略），分配空間的工作只是將指針像空閑內(nèi)存一側(cè)移動對象大小的距離即可。
2. 空閑列表：這種適用于內(nèi)存非規(guī)整的情況，這種情況下JVM會維護(hù)一個內(nèi)存列表，記錄哪些內(nèi)存區(qū)域是空閑的，大小是多少。給對象分配空間的時候去空閑列表里查詢到合適的區(qū)域然后進(jìn)行分配即可。

但是JVM不可能一直在單線程狀態(tài)下運(yùn)行，那樣效率太差了。由于再給一個對象分配內(nèi)存的時候不是原子性的操作，至少需要以下幾步：查找空閑列表、分配內(nèi)存、修改空閑列表等等，這是不安全的。解決并發(fā)時的安全問題也有兩種策略：

1. CAS：實際上虛擬機(jī)采用CAS配合上失敗重試的方式保證更新操作的原子性，原理和上面講的一樣。
2. TLAB：如果使用CAS其實對性能還是會有影響的，所以 JVM 又提出了一種更高級的優(yōu)化策略：每個線程在 Java 堆中預(yù)先分配一小塊內(nèi)存，稱為本地線程分配緩沖區(qū)（TLAB），線程內(nèi)部需要分配內(nèi)存時直接在 TLAB 上分配就行，避免了線程沖突。只有當(dāng)緩沖區(qū)的內(nèi)存用光需要重新分配內(nèi)存的時候才會進(jìn)行CAS操作分配更大的內(nèi)存空間。

虛擬機(jī)是否使用TLAB，可以通過-XX:+/-UseTLAB參數(shù)來進(jìn)行配置（jdk5及以后的版本默認(rèn)是啟用TLAB的）。

四、CAS存在的問題：

4.1 ABA 問題

談到 CAS，基本上都要談一下 CAS 的 ABA 問題。CAS 由三個步驟組成，分別是“讀取-比較-寫回”。考慮這樣一種情況，線程1和線程2同時執(zhí)行 CAS 邏輯，兩個線程的執(zhí)行順序如下：

• 時刻1：線程1執(zhí)行讀取操作，獲取原值 A，然后線程被切換走
• 時刻2：線程2執(zhí)行完成 CAS 操作將原值由 A 修改為 B
• 時刻3：線程2再次執(zhí)行 CAS 操作，并將原值由 B 修改為 A
• 時刻4：線程1恢復(fù)運(yùn)行，將比較值(compareValue)與原值(oldValue)進(jìn)行比較，發(fā)現(xiàn)兩個值相等。

然后用新值(newValue)寫入內(nèi)存中，完成 CAS 操作

如上流程，線程1并不知道原值已經(jīng)被修改過了，在它看來并沒什么變化，所以它會繼續(xù)往下執(zhí)行流程。對于 ABA 問題，通常的處理措施是對每一次 CAS 操作設(shè)置版本號。

ABA問題的解決思路其實也很簡單，就是使用版本號。在變量前面追加上版本號，每次變量更新的時候把版本號加1，那么A→B→A就會變成1A→2B→3A了。

java.util.concurrent.atomic 包下提供了一個可處理 ABA 問題的原子類 AtomicStampedReference，

從Java1.5開始JDK的atomic包里提供了一個類AtomicStampedReference來解決ABA問題。這個類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值。

4.2 循環(huán)時間長開銷大

自旋CAS（不成功，就一直循環(huán)執(zhí)行，直到成功） 如果長時間不成功，會給 CPU 帶來非常大的執(zhí)行開銷。如果JVM能支持處理器提供的 pause 指令那么效率會有一定的提升，pause指令有兩個作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline），使 CPU 不會消耗過多的執(zhí)行資源，延遲的時間取決于具體實現(xiàn)的版本，在一些處理器上延遲時間是零。第二它可以避免在退出循環(huán)的時候因內(nèi)存順序沖突（memory order violation）而引起 CPU 流水線被清空（CPU pipeline flush），從而提高 CPU 的執(zhí)行效率。

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

當(dāng)對一個共享變量執(zhí)行操作時，我們可以使用循環(huán) CAS 的方式來保證原子操作，但是對多個共享變量操作時，循環(huán) CAS 就無法保證操作的原子性，這個時候就可以用鎖，或者有一個取巧的辦法，就是把多個共享變量合并成一個共享變量來操作。比如有兩個共享變量 i＝2，j=a，合并一下 ij=2a，然后用CAS來操作ij。從Java1.5開始JDK提供了 AtomicReference 類來保證引用對象之間的原子性，你可以把多個變量放在一個對象里來進(jìn)行 CAS 操作。

CAS 與 Synchronized 的使用情景：　　　

1. 對于資源競爭較少（線程沖突較輕）的情況，使用synchronized同步鎖進(jìn)行線程阻塞和喚醒切換以及用戶態(tài)內(nèi)核態(tài)間的切換操作額外浪費(fèi)消耗cpu資源；而CAS基于硬件實現(xiàn)，不需要進(jìn)入內(nèi)核，不需要切換線程，操作自旋幾率較少，因此可以獲得更高的性能。
2. 對于資源競爭嚴(yán)重（線程沖突嚴(yán)重）的情況，CAS自旋的概率會比較大，從而浪費(fèi)更多的CPU資源，效率低于synchronized。

補(bǔ)充： synchronized 在 jdk1.6 之后，已經(jīng)改進(jìn)優(yōu)化。synchronized 的底層實現(xiàn)主要依靠 Lock-Free 的隊列，基本思路是自旋后阻塞，競爭切換后繼續(xù)競爭鎖，稍微犧牲了公平性，但獲得了高吞吐量。在線程沖突較少的情況下，可以獲得和 CAS 類似的性能；而線程沖突嚴(yán)重的情況下，性能遠(yuǎn)高于 CAS。