CAS原理深度分析

java.util.concurrent包完全建立在CAS之上的蚕断，沒有CAS就不會有此包。可見CAS的重要性曲聂。

CAS

CAS：Compare and Swap，翻譯成比較并交換佑惠。

java.util.concurrent包中借助CAS實現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂觀鎖朋腋。

本文先從CAS的應(yīng)用說起，再深入原理解析膜楷。

CAS應(yīng)用

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

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

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

private volatile int value;

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

這樣獲取變量的值的時候才能直接讀取匈勋。

public final int get() {
    return value;
}

然后來看看 ++i 是怎么做到的。

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é)果進行CAS操作，如果成功就返回結(jié)果菲嘴，否則重試直到成功為止饿自。

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

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

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

其中

unsafe.compareAndSwapInt(this, valueOffset, expect, update);

類似：

if (this == expect) {

   this = update

   return true;

} else {

   return false;
}

那么問題就來了烛卧，成功過程中需要2個步驟：比較this == expect，替換this = update妓局，compareAndSwapInt如何實現(xiàn)這兩個步驟的原子性呢总放？ 參考CAS的原理呈宇。

CAS原理

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

而compareAndSwapInt就是借助C來調(diào)用CPU底層指令實現(xiàn)的。

下面從分析比較常用的CPU（intel x86）來解釋CAS的實現(xiàn)原理炬搭。

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

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

可以看到這是個本地方法調(diào)用蜈漓。這個本地方法在openjdk中依次調(diào)用的c++代碼為：unsafe.cpp，atomic.cpp和atomicwindowsx86.inline.hpp宫盔。這個本地方法的最終實現(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前綴衣形。如果程序是在多處理器上運行，就為cmpxchg指令加上lock前綴（lock cmpxchg）姿鸿。反之谆吴，如果程序是在單處理器上運行，就省略lock前綴（單處理器自身會維護單處理器內(nèi)的順序一致性苛预，不需要lock前綴提供的內(nèi)存屏障效果）句狼。

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

1. 確保對內(nèi)存的讀-改-寫操作原子執(zhí)行。在Pentium及Pentium之前的處理器中热某，帶有l(wèi)ock前綴的指令在執(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)前處于獨占或以修改狀態(tài)）丘薛，并且該內(nèi)存區(qū)域被完全包含在單個緩存行（cache line）中，那么處理器將直接執(zhí)行該指令邦危。由于在指令執(zhí)行期間該緩存行會一直被鎖定洋侨，其它處理器無法讀/寫該指令要訪問的內(nèi)存區(qū)域，因此能保證指令執(zhí)行的原子性倦蚪。這個操作過程叫做緩存鎖定（cache locking）希坚，緩存鎖定將大大降低lock前綴指令的執(zhí)行開銷，但是當(dāng)多處理器之間的競爭程度很高或者指令訪問的內(nèi)存地址未對齊時陵且，仍然會鎖住總線裁僧。
2. 禁止該指令與之前和之后的讀和寫指令重排序。
3. 把寫緩沖區(qū)中的所有數(shù)據(jù)刷新到內(nèi)存中。

關(guān)于CPU的鎖有如下3種：

• 處理器自動保證基本內(nèi)存操作的原子性

首先處理器會自動保證基本的內(nèi)存操作的原子性锅知。處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個字節(jié)是原子的播急，意思是當(dāng)一個處理器讀取一個字節(jié)時脓钾，其他處理器不能訪問這個字節(jié)的內(nèi)存地址售睹。奔騰6和最新的處理器能自動保證單處理器對同一個緩存行里進行16/32/64位的操作是原子的，但是復(fù)雜的內(nèi)存操作處理器不能自動保證其原子性可训，比如跨總線寬度昌妹，跨多個緩存行，跨頁表的訪問握截。但是處理器提供總線鎖定和緩存鎖定兩個機制來保證復(fù)雜內(nèi)存操作的原子性飞崖。

• 使用總線鎖保證原子性

第一個機制是通過總線鎖保證原子性。如果多個處理器同時對共享變量進行讀改寫（i++就是經(jīng)典的讀改寫操作）操作谨胞，那么共享變量就會被多個處理器同時進行操作固歪，這樣讀改寫操作就不是原子的，操作完之后共享變量的值會和期望的不一致胯努，舉個例子：如果i=1,我們進行兩次i++操作牢裳，我們期望的結(jié)果是3，但是有可能結(jié)果是2叶沛。如下圖

image.png

原因是有可能多個處理器同時從各自的緩存中讀取變量i蒲讯，分別進行加一操作，然后分別寫入系統(tǒng)內(nèi)存當(dāng)中灰署。那么想要保證讀改寫共享變量的操作是原子的判帮，就必須保證CPU1讀改寫共享變量的時候，CPU2不能操作緩存了該共享變量內(nèi)存地址的緩存溉箕。

處理器使用總線鎖就是來解決這個問題的晦墙。所謂總線鎖就是使用處理器提供的一個LOCK＃信號，當(dāng)一個處理器在總線上輸出此信號時肴茄，其他處理器的請求將被阻塞住偎痛，那么該處理器可以獨占使用共享內(nèi)存。

• 使用緩存鎖保證原子性

第二個機制是通過緩存鎖定保證原子性独郎。在同一時刻我們只需保證對某個內(nèi)存地址的操作是原子性即可踩麦，但總線鎖定把CPU和內(nèi)存之間通信鎖住了，這使得鎖定期間氓癌，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)谓谦，所以總線鎖定的開銷比較大，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進行優(yōu)化贪婉。

頻繁使用的內(nèi)存會緩存在處理器的L1反粥，L2和L3高速緩存里，那么原子操作就可以直接在處理器內(nèi)部緩存中進行，并不需要聲明總線鎖才顿，在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實現(xiàn)復(fù)雜的原子性莫湘。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內(nèi)存區(qū)域在LOCK操作期間被鎖定，當(dāng)它執(zhí)行鎖操作回寫內(nèi)存時郑气，處理器不在總線上聲言LOCK＃信號幅垮，而是修改內(nèi)部的內(nèi)存地址，并允許它的緩存一致性機制來保證操作的原子性尾组，因為緩存一致性機制會阻止同時修改被兩個以上處理器緩存的內(nèi)存區(qū)域數(shù)據(jù)忙芒，當(dāng)其他處理器回寫已被鎖定的緩存行的數(shù)據(jù)時會起緩存行無效，在例1中讳侨，當(dāng)CPU1修改緩存行中的i時使用緩存鎖定呵萨，那么CPU2就不能同時緩存了i的緩存行。

但是有兩種情況下處理器不會使用緩存鎖定跨跨。第一種情況是：當(dāng)操作的數(shù)據(jù)不能被緩存在處理器內(nèi)部潮峦，或操作的數(shù)據(jù)跨多個緩存行（cache line），則處理器會調(diào)用總線鎖定勇婴。第二種情況是：有些處理器不支持緩存鎖定忱嘹。對于Inter486和奔騰處理器,就算鎖定的內(nèi)存區(qū)域在處理器的緩存行中也會調(diào)用總線鎖定。

以上兩個機制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實現(xiàn)咆耿。比如位測試和修改指令BTS德谅，BTR，BTC萨螺，交換指令XADD窄做，CMPXCHG和其他一些操作數(shù)和邏輯指令，比如ADD（加）慰技，OR（或）等椭盏，被這些指令操作的內(nèi)存區(qū)域就會加鎖，導(dǎo)致其他處理器不能同時訪問它吻商。

CAS缺點

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

1. ABA問題乌叶。因為CAS需要在操作值的時候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新柒爸，但是如果一個值原來是A准浴，變成了B，又變成了A捎稚，那么使用CAS進行檢查時會發(fā)現(xiàn)它的值沒有發(fā)生變化乐横，但是實際上卻變化了求橄。ABA問題的解決思路就是使用版本號。在變量前面追加上版本號葡公，每次變量更新的時候把版本號加一罐农，那么A－B－A 就會變成1A-2B－3A。

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

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

2. 循環(huán)時間長開銷大夹厌。自旋CAS如果長時間不成功豹爹，會給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í)行效率产艾。

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

concurrent包的實現(xiàn)

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

1. A線程寫volatile變量封豪，隨后B線程讀這個volatile變量谴轮。
2. A線程寫volatile變量，隨后B線程用CAS更新這個volatile變量撑毛。
3. A線程用CAS更新一個volatile變量书聚，隨后B線程用CAS更新這個volatile變量唧领。
4. A線程用CAS更新一個volatile變量，隨后B線程讀這個volatile變量雌续。

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

1. 首先糯景，聲明共享變量為volatile嘁圈；
2. 然后，使用CAS的原子條件更新來實現(xiàn)線程之間的同步蟀淮；
3. 同時最住，配合以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)示意圖如下：

image.png