一、術(shù)語定義

二、CAS應(yīng)用

CAS有3個(gè)操作數(shù)，內(nèi)存值V，舊的預(yù)期值A(chǔ)，要修改的新值B。當(dāng)且僅當(dāng)預(yù)期值A(chǔ)和內(nèi)存值V相同時(shí)，將內(nèi)存值V修改為B，否則什么都不做。

非阻塞算法 （nonblocking algorithms）

一個(gè)線程的失敗或者掛起不應(yīng)該影響其他線程的失敗或掛起的算法。

現(xiàn)代的CPU提供了特殊的指令，可以自動更新共享數(shù)據(jù)，而且能夠檢測到其他線程的干擾，而 compareAndSet() 就用這些代替了鎖定。

以AtomicInteger來研究在沒有鎖的情況下是如何做到數(shù)據(jù)正確性的。

private volatile int value;

首先毫無疑問，在沒有鎖的機(jī)制下可能需要借助volatile原語，保證線程間的數(shù)據(jù)是可見的（共享的）。

這樣才獲取變量的值的時(shí)候才能直接讀取。

public final int get() {return value; }

然后來看看++1(自增)是怎么做到的:

 public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
}

在這里采用了CAS操作，每次從內(nèi)存中讀取數(shù)據(jù)然后將此數(shù)據(jù)和+1后的結(jié)果進(jìn)行CAS操作，如果成功就返回結(jié)果，否則重試直到成功為止。

而compareAndSet利用JNI來完成CPU指令的操作。

public final boolean compareAndSet(int expect, int update) {   
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

整體的過程就是這樣子的，利用CPU的CAS指令，同時(shí)借助JNI來完成Java的非阻塞算法。其它原子操作都是利用類似的特性完成的。

三、CAS原理

CAS通過調(diào)用JNI的代碼實(shí)現(xiàn)的。JNI:Java Native Interface為JAVA本地調(diào)用，允許java調(diào)用其他語言。

而compareAndSwapInt就是借助C來調(diào)用CPU底層指令實(shí)現(xiàn)的。下面從分析比較常用的CPU（intel x86）來解釋CAS的實(shí)現(xiàn)原理。

下面是sun.misc.Unsafe類的compareAndSwapInt()方法的源代碼：

public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

可以看到這是個(gè)本地方法調(diào)用。這個(gè)本地方法在openjdk中依次調(diào)用的c++代碼為：unsafe.cpp，atomic.cpp和atomicwindowsx86.inline.hpp。這個(gè)本地方法的最終實(shí)現(xiàn)在openjdk的如下位置：openjdk-7-fcs-src-b147-27jun2011\openjdk\hotspot\src\oscpu\windowsx86\vm\ atomicwindowsx86.inline.hpp（對應(yīng)于windows操作系統(tǒng)，X86處理器）。下面是對應(yīng)于intel x86處理器的源代碼的片段:

// Adding a lock prefix to an instruction on MP machine 
// VC++ doesn't like the lock prefix to be on a single line 
// so we can't insert a label after the lock prefix. 
// By emitting a lock prefix, we can define a label after it. 
#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
    } 
}

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

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

1. 確保對內(nèi)存的讀-改-寫操作原子執(zhí)行。在 Pentium 及 Pentium 之前的處理器中，帶有l(wèi)ock 前綴的指令在執(zhí)行期間會鎖住總線，使得其他處理器暫時(shí)無法通過總線訪問內(nèi)存。很顯然，這會帶來昂貴的開銷。從 Pentium 4，Intel Xeon 及 P6 處理器開始，intel 在原有總線鎖的基礎(chǔ)上做了一個(gè)很有意義的優(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ū)域被完全包含在單個(gè)緩存行（cache line）中，那么處理器將直接執(zhí)行該指令。由于在指令執(zhí)行期間該緩存行會一直被鎖定，其它處理器無法讀/寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性。這個(gè)操作過程叫做緩存鎖定（cache locking），緩存鎖定將大大降低 lock 前綴指令的執(zhí)行開銷，但是當(dāng)多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時(shí)，仍然會鎖住總線。

2. 禁止該指令與之前和之后的讀和寫指令重排序。

3. 把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

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

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

四、CAS缺點(diǎn)

CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題。ABA問題，循環(huán)時(shí)間長開銷大和只能保證一個(gè)共享變量的原子操作

1. ABA問題。因?yàn)镃AS需要在操作值的時(shí)候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新，但是如果一個(gè)值原來是A，變成了B，又變成了A，那么使用CAS進(jìn)行檢查時(shí)會發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實(shí)際上卻變化了。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號，每次變量更新的時(shí)候把版本號加一，那么A－B－A 就會變成1A-2B－3A。

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

關(guān)于ABA問題參考文檔: http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html

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

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

五、concurrent包的實(shí)現(xiàn)

由于java的CAS同時(shí)具有 volatile 讀和volatile寫的內(nèi)存語義，因此Java線程之間的通信現(xiàn)在有了下面四種方式：

1. A線程寫volatile變量，隨后B線程讀這個(gè)volatile變量。
2. A線程寫volatile變量，隨后B線程用CAS更新這個(gè)volatile變量。
3. A線程用CAS更新一個(gè)volatile變量，隨后B線程用CAS更新這個(gè)volatile變量。
4. A線程用CAS更新一個(gè)volatile變量，隨后B線程讀這個(gè)volatile變量。

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

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

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

img