什么是 CAS

• CAS,compare and swap的縮寫，中文翻譯成比較并交換。CAS指令在Intel CPU上稱為CMPXCHG指令获询，它的作用是將指定內(nèi)存地址的內(nèi)容與所給的某個(gè)值相比，如果相等，則將其內(nèi)容替換為指令中提供的新值拯钻，如果不相等，則更新失敗撰豺。
• 從內(nèi)存領(lǐng)域來(lái)說(shuō)這是樂觀鎖粪般，因?yàn)樗趯?duì)共享變量更新之前會(huì)先比較當(dāng)前值是否與更新前的值一致，如果是污桦，則更新亩歹，如果不是，則無(wú)限循環(huán)執(zhí)行(稱為自旋)凡橱，直到當(dāng)前值與更新前的值一致為止弓千，才執(zhí)行更新。
• CAS 有 3 個(gè)操作數(shù)啦撮，內(nèi)存值 V苟呐，舊的預(yù)期值 A，要修改的新值 B变抽。當(dāng)且僅當(dāng)預(yù)期值 A 和內(nèi)存值 V 相同時(shí)础拨，將內(nèi)存值 V 修改為 B，否則什么都不做绍载。

那些地方采用了 CAS 機(jī)制诡宗？

• 在 java.util.concurrent.atomic 包下，一系列以 Atomic 開頭的包裝類击儡。例如AtomicBoolean塔沃，AtomicInteger，AtomicLong 等阳谍，它們就是典型的利用 CAS 機(jī)制實(shí)現(xiàn)的原子操作類蛀柴。
• 此外，Lock 系列類的底層實(shí)現(xiàn)以及 Java 1.6 在 synchronized 轉(zhuǎn)換為重量級(jí)鎖之前矫夯，也會(huì)采用到 CAS 機(jī)制鸽疾。

CAS底層實(shí)現(xiàn)

簡(jiǎn)單分析一下AtomicInteger的incrementAndGet的實(shí)現(xiàn)。

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

這段代碼是一個(gè)無(wú)限循環(huán)训貌，也就是CAS的自旋制肮。循環(huán)體當(dāng)中做了三件事：

• 獲取當(dāng)前值冒窍。
• 當(dāng)前值+1，計(jì)算出目標(biāo)值豺鼻。
• 進(jìn)行CAS操作综液，如果成功則跳出循環(huán)（當(dāng)前值和目標(biāo)值相等），如果失敗則重復(fù)上述步驟儒飒。

注意：

• 這里需要注意的重點(diǎn)是 get 方法谬莹，這個(gè)方法的作用是獲取變量的當(dāng)前值。
• 如何保證獲得的當(dāng)前值是內(nèi)存中的最新值呢桩了？很簡(jiǎn)單附帽，用volatile關(guān)鍵字來(lái)保證。

拓展一下：while(1) 和 for(;;)兩種死循環(huán)：

while(1) ：

  編譯前              編譯后 
while (1)圣猎；         mov eax,1  
                    test eax,eax 
                    je foo+23h
                    jmp foo+18h
 for(;;)：

    編譯前              編譯后 
for (士葫；；)送悔；          jmp foo+23h 

總結(jié)：宏觀功能相同的慢显，但是底層編譯后代碼簡(jiǎn)潔很多。

那么compareAndSet方法如何保證原子性操作呢欠啤？

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

compareAndSet方法的實(shí)現(xiàn)很簡(jiǎn)單荚藻，只有一行代碼。這里涉及到兩個(gè)重要的對(duì)象洁段，一個(gè)是unsafe应狱，一個(gè)是valueOffset。

• 什么是unsafe呢祠丝？Java語(yǔ)言不像C疾呻，C++那樣可以直接訪問底層操作系統(tǒng)，但是JVM為我們提供了一個(gè)后門写半，這個(gè)后門就是unsafe岸蜗。unsafe為我們提供了硬件級(jí)別的原子操作。
• 至于valueOffset對(duì)象叠蝇，是通過(guò)unsafe.objectFieldOffset方法得到璃岳，所代表的是AtomicInteger對(duì)象value成員變量在內(nèi)存中的偏移量。我們可以簡(jiǎn)單地把valueOffset理解為value變量的內(nèi)存地址悔捶。

總結(jié)：關(guān)鍵在于unsafe提供硬件級(jí)別的原子操作铃慷。

CAS機(jī)制當(dāng)中使用了3個(gè)基本操作數(shù)：內(nèi)存地址V，舊的預(yù)期值A(chǔ)蜕该，要修改的新值B犁柜。而unsafe的compareAndSwapInt方法參數(shù)包括了這三個(gè)基本元素：valueOffset參數(shù)代表了V，expect參數(shù)代表了A堂淡，update參數(shù)代表了B馋缅。正是unsafe的compareAndSwapInt方法保證了Compare和Swap操作之間的原子性操作坛怪。

CAS 的缺點(diǎn)及解決方式

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

• ABA問題：因?yàn)镃AS需要在操作值的時(shí)候檢查下值有沒有發(fā)生變化更啄，如果沒有發(fā)生變化則更新稚疹，但是如果一個(gè)值原來(lái)是A，變成了B祭务，又變成了A内狗， 那么使用CAS進(jìn)行檢查時(shí)會(huì)發(fā)現(xiàn)它的值沒有發(fā)生變化，但是實(shí)際上卻變化了义锥。

  • ABA問題的解決思路就是使用版本號(hào)柳沙。在變量前面追加上版本號(hào)，每次變量更新的時(shí)候把版本號(hào)加一拌倍，那么A－B－A 就會(huì)變成1A-2B-3A赂鲤。
  • 從Java1.5開始JDK的atomic包里提供了一個(gè)類 AtomicStampedReference 來(lái)解決ABA問題。這個(gè)類的compareAndSet方法作用是首先檢查當(dāng)前引用是否等于預(yù)期引用柱恤，并且當(dāng)前標(biāo)志是否等于預(yù)期標(biāo)志数初，如果全部相等，則以原子方式將該引用和該標(biāo)志的值設(shè)置為給定的更新值梗顺。

• 循環(huán)時(shí)間長(zhǎng)開銷大：在并發(fā)量比較高的情況下泡孩，如果許多線程反復(fù)嘗試更新某一個(gè)變量，即自旋CAS如果長(zhǎng)時(shí)間不成功寺谤，會(huì)給CPU帶來(lái)非常大的執(zhí)行開銷仑鸥。

  • 如果JVM能支持處理器提供的pause指令，那么效率會(huì)有一定的提升变屁。pause指令有兩個(gè)作用眼俊，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會(huì)消耗過(guò)多的執(zhí)行資源，延遲的時(shí)間取決于具體實(shí)現(xiàn)的版本敞贡，在一些處理器上延遲時(shí)間是零泵琳。第二它可以避免在退出循環(huán)的時(shí)候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush），從而提高CPU的執(zhí)行效率誊役。
  • 代碼層面获列，破壞掉for死循環(huán)，當(dāng)自旋超過(guò)一定時(shí)間或者一定次數(shù)時(shí)蛔垢，return退出击孩。
  • 使用類似ConcurrentHashMap的方法。當(dāng)多個(gè)線程競(jìng)爭(zhēng)時(shí)鹏漆，將粒度變小巩梢，將一個(gè)變量拆分為多個(gè)變量创泄，達(dá)到多個(gè)線程訪問多個(gè)資源的效果，最后再調(diào)用sum把它合起來(lái)括蝠，能降低CPU消耗鞠抑，但是治標(biāo)不治本。

• 只能保證一個(gè)共享變量的原子操作：當(dāng)對(duì)一個(gè)共享變量執(zhí)行操作時(shí)忌警，我們可以使用循環(huán)CAS的方式來(lái)保證原子操作搁拙，但是對(duì)多個(gè)共享變量操作時(shí)，循環(huán)CAS就無(wú)法保證操作的原子性法绵。

  • 這個(gè)時(shí)候就可以用鎖箕速，或者有一個(gè)取巧的辦法，就是把多個(gè)共享變量合并成一個(gè)共享變量來(lái)操作朋譬。比如有兩個(gè)共享變量i＝2,j=a盐茎，合并一下ij=2a，然后用CAS來(lái)操作ij徙赢。
  • 從Java1.5開始JDK提供了AtomicReference類來(lái)保證引用對(duì)象之間的原子性字柠，你可以把多個(gè)變量放在一個(gè)對(duì)象里來(lái)進(jìn)行CAS操作。

synchronized 和 CAS 的區(qū)別

• synchronized 采用的是 CPU 悲觀鎖機(jī)制犀忱，即線程獲得的是獨(dú)占鎖募谎。獨(dú)占鎖就意味著 其他線程只能依靠阻塞來(lái)等待線程釋放鎖。而在 CPU 轉(zhuǎn)換線程阻塞時(shí)會(huì)引起線程上下文切換阴汇，當(dāng)有很多線程競(jìng)爭(zhēng)鎖的時(shí)候数冬，會(huì)引起 CPU 頻繁的上下文切換導(dǎo)致效率很低。盡管 Java1.6 為 synchronized 做了優(yōu)化搀庶，增加了從偏向鎖到輕量級(jí)鎖再到重量級(jí)鎖的過(guò)度拐纱，但是在最終轉(zhuǎn)變?yōu)橹亓考?jí)鎖之后，性能仍然較低哥倔。
• CAS 是英文單詞 Compare And Swap 的縮寫秸架，翻譯過(guò)來(lái)就是比較并替換。它當(dāng)中使用了3個(gè)基本操作數(shù)：內(nèi)存地址 V咆蒿，舊的預(yù)期值 A东抹，要修改的新值 B。采用的是一種樂觀鎖的機(jī)制沃测，它不會(huì)阻塞任何線程缭黔，所以在效率上，它會(huì)比 synchronized 要高蒂破。所謂樂觀鎖就是：每次不加鎖而是假設(shè)沒有沖突而去完成某項(xiàng)操作馏谨，如果因?yàn)闆_突失敗就重試，直到成功為止附迷。

所以惧互，在并發(fā)量非常高的情況下哎媚，我們盡量的用同步鎖，而在其他情況下喊儡，我們可以靈活的采用 CAS 機(jī)制拨与。

巨人的肩膀：

http://www.reibang.com/p/335b0c273345
https://mp.weixin.qq.com/s/nRnQKhiSUrDKu3mz3vItWg
http://www.reibang.com/p/12192b13990f