CAS簡歷
CAS（Compare and swap）比較和替換是設(shè)計并發(fā)算法時用到的一種技術(shù) 嗤朴。Compare and Swap, 翻譯成比較并交換娱仔。 簡單來說沐飘，比較和替換是使用一個期望值和一個變量的當(dāng)前值進(jìn)行比較，如果當(dāng)前變量的值與我們期望的值相等拟枚，就使用一個新值替換當(dāng)前變量的值薪铜。
java.util.concurrent包完全建立在CAS之上的，沒有CAS就不會有此包恩溅「艄浚可見CAS
的重要性。java.util.concurrent包中借助CAS實(shí)現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂觀鎖脚乡。
這聽起來可能有一點(diǎn)復(fù)雜但是實(shí)際上你理解之后發(fā)現(xiàn)很簡單蜒滩，接下來滨达，讓我們跟深入的了解一下這項(xiàng)技術(shù)。
CAS操作
我們常常做這樣的操作
if(a==b) {
a++;
}
試想一下如果在做a++之前a的值被改變了怎么辦俯艰？a++還執(zhí)行嗎捡遍？出現(xiàn)該問題的原因是在多線程環(huán)境下，a的值處于一種不定的狀態(tài)竹握。采用鎖可以解決此類問題画株，但CAS也可以解決，而且可以不加鎖啦辐。
int expect = a;
if(a.compareAndSet(expect,a+1)) {
doSomeThing1();
} else {
doSomeThing2();
}
這樣如果a的值被改變了a++就不會被執(zhí)行谓传。按照上面的寫法，a!=expect之后,a++就不會被執(zhí)行芹关，如果我們還是想執(zhí)行a++操作怎么辦续挟，沒關(guān)系，可以采用while循環(huán)
while(true) {
int expect = a;
if (a.compareAndSet(expect, a + 1)) {
doSomeThing1();
return;
} else {
doSomeThing2();
}
}
采用上面的寫法侥衬，在沒有鎖的情況下實(shí)現(xiàn)了a++操作诗祸，這實(shí)際上是一種非阻塞算法。
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，否則什么都不做漂佩。
非阻塞算法 （nonblocking algorithms）
一個線程的失敗或者掛起不應(yīng)該影響其他線程的失敗或掛起的算法脖含。
現(xiàn)代的CPU提供了特殊的指令，可以自動更新共享數(shù)據(jù)投蝉，而且能夠檢測到其他線程的干擾养葵，而 compareAndSet() 就用這些代替了鎖定。
拿出AtomicInteger來研究在沒有鎖的情況下是如何做到數(shù)據(jù)正確性的瘩缆。
private volatile int value;
首先毫無以為关拒，在沒有鎖的機(jī)制下可能需要借助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é)果進(jìn)行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如何這兩個步驟的原子性呢？ 參考CAS的原理
Concurrent包的實(shí)現(xiàn)
由于java的CAS同時具有 volatile 讀和volatile寫的內(nèi)存語義掉缺，因此Java線程之間的通信現(xiàn)在有了下面四種方式：
- A線程寫volatile變量福也，隨后B線程讀這個volatile變量。
- A線程寫volatile變量攀圈，隨后B線程用CAS更新這個volatile變量。
- A線程用CAS更新一個volatile變量峦甩，隨后B線程用CAS更新這個volatile變量赘来。
- A線程用CAS更新一個volatile變量，隨后B線程讀這個volatile變量凯傲。
Java的CAS會使用現(xiàn)代處理器上提供的高效機(jī)器級別原子指令犬辰，這些原子指令以原子方式對內(nèi)存執(zhí)行讀-改-寫操作，這是在多處理器中實(shí)現(xiàn)同步的關(guān)鍵（從本質(zhì)上來說冰单，能夠支持原子性讀-改-寫指令的計算機(jī)器幌缝，是順序計算圖靈機(jī)的異步等價機(jī)器，因此任何現(xiàn)代的多處理器都會去支持某種能對內(nèi)存執(zhí)行原子性讀-改-寫操作的原子指令）诫欠。同時涵卵，volatile變量的讀/寫和CAS可以實(shí)現(xiàn)線程之間的通信。把這些特性整合在一起荒叼，就形成了整個concurrent包得以實(shí)現(xiàn)的基石轿偎。如果我們仔細(xì)分析concurrent包的源代碼實(shí)現(xiàn)，會發(fā)現(xiàn)一個通用化的實(shí)現(xiàn)模式：
首先被廓，聲明共享變量為volatile坏晦；
然后，使用CAS的原子條件更新來實(shí)現(xiàn)線程之間的同步嫁乘；
同時昆婿，配合以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)示意圖如下：
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);
可以看到這是個本地方法調(diào)用相味。這個本地方法在openjdk中依次調(diào)用的c++代碼為：unsafe.cpp拾积、atomic.cpp、atomic*windows*x86.inline.hpp丰涉。
這個本地方法的最終實(shí)現(xiàn)在openjdk的如下位置：
openjdk-7-fcs-src-b147-27*jun*2011\openjdk\hotspot\src\os*cpu\windows*x86\vm\ atomic*windows*x86.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前綴的說明如下：
- 確保對內(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)前處于獨(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)存中。
備注知識
關(guān)于CPU的鎖有如下3種：
- 處理器自動保證基本內(nèi)存操作的原子性
首先處理器會自動保證基本的內(nèi)存操作的原子性浦夷。處理器保證從系統(tǒng)內(nèi)存當(dāng)中讀取或者寫入一個字節(jié)是原子的辖试，意思是當(dāng)一個處理器讀取一個字節(jié)時辜王，其他處理器不能訪問這個字節(jié)的內(nèi)存地址。奔騰6和最新的處理器能自動保證單處理器對同一個緩存行里進(jìn)行16/32/64位的操作是原子的罐孝，但是復(fù)雜的內(nèi)存操作處理器不能自動保證其原子性呐馆，比如跨總線寬度，跨多個緩存行莲兢，跨頁表的訪問汹来。但是處理器提供總線鎖定和緩存鎖定兩個機(jī)制來保證復(fù)雜內(nèi)存操作的原子性。
- 使用總線鎖保證原子性
第一個機(jī)制是通過總線鎖保證原子性改艇。如果多個處理器同時對共享變量進(jìn)行讀改寫（i++就是經(jīng)典的讀改寫操作）操作收班，那么共享變量就會被多個處理器同時進(jìn)行操作，這樣讀改寫操作就不是原子的谒兄，操作完之后共享變量的值會和期望的不一致摔桦，舉個例子：如果i=1,我們進(jìn)行兩次i++操作，我們期望的結(jié)果是3承疲，但是有可能結(jié)果是2邻耕。如下圖
原因是有可能多個處理器同時從各自的緩存中讀取變量i，分別進(jìn)行加一操作纪隙，然后分別寫入系統(tǒng)內(nèi)存當(dāng)中。那么想要保證讀改寫共享變量的操作是原子的扛或，就必須保證CPU1讀改寫共享變量的時候绵咱，CPU2不能操作緩存了該共享變量內(nèi)存地址的緩存。
處理器使用總線鎖就是來解決這個問題的熙兔。所謂總線鎖就是使用處理器提供的一個LOCK＃信號悲伶，當(dāng)一個處理器在總線上輸出此信號時，其他處理器的請求將被阻塞住,那么該處理器可以獨(dú)占使用共享內(nèi)存住涉。
- 使用緩存鎖保證原子性
第二個機(jī)制是通過緩存鎖定保證原子性麸锉。在同一時刻我們只需保證對某個內(nèi)存地址的操作是原子性即可，但總線鎖定把CPU和內(nèi)存之間通信鎖住了舆声，這使得鎖定期間花沉，其他處理器不能操作其他內(nèi)存地址的數(shù)據(jù)，所以總線鎖定的開銷比較大媳握，最近的處理器在某些場合下使用緩存鎖定代替總線鎖定來進(jìn)行優(yōu)化碱屁。
頻繁使用的內(nèi)存會緩存在處理器的L1，L2和L3高速緩存里蛾找，那么原子操作就可以直接在處理器內(nèi)部緩存中進(jìn)行娩脾，并不需要聲明總線鎖，在奔騰6和最近的處理器中可以使用“緩存鎖定”的方式來實(shí)現(xiàn)復(fù)雜的原子性打毛。所謂“緩存鎖定”就是如果緩存在處理器緩存行中內(nèi)存區(qū)域在LOCK操作期間被鎖定柿赊，當(dāng)它執(zhí)行鎖操作回寫內(nèi)存時俩功，處理器不在總線上聲言LOCK＃信號，而是修改內(nèi)部的內(nèi)存地址碰声，并允許它的緩存一致性機(jī)制來保證操作的原子性诡蜓，因?yàn)榫彺嬉恢滦詸C(jī)制會阻止同時修改被兩個以上處理器緩存的內(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)用總線鎖定藕坯。
以上兩個機(jī)制我們可以通過Inter處理器提供了很多LOCK前綴的指令來實(shí)現(xiàn)团南。比如位測試和修改指令BTS，BTR炼彪，BTC吐根，交換指令XADD，CMPXCHG和其他一些操作數(shù)和邏輯指令辐马，比如ADD（加）拷橘，OR（或）等，被這些指令操作的內(nèi)存區(qū)域就會加鎖喜爷，導(dǎo)致其他處理器不能同時訪問它冗疮。
CAS缺點(diǎn)
CAS雖然很高效的解決原子操作，但是CAS仍然存在三大問題檩帐。ABA問題术幔，循環(huán)時間長開銷大和只能保證一個共享變量的原子操作
-
ABA問題
因?yàn)镃AS需要在操作值的時候檢查下值有沒有發(fā)生變化，如果沒有發(fā)生變化則更新湃密，但是如果一個值原來是A诅挑，變成了B，又變成了A泛源，那么使用CAS進(jìn)行檢查時會發(fā)現(xiàn)它的值沒有發(fā)生變化揍障，但是實(shí)際上卻變化了。ABA問題的解決思路就是使用版本號俩由。在變量前面追加上版本號毒嫡，每次變量更新的時候把版本號加一，那么A－B－A 就會變成1A-2B－3A。
從Java1.5開始JDK的atomic包里提供了一個類AtomicStampedReference來解決ABA問題兜畸。這個類的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
- ** 循環(huán)時間長開銷大**
自旋CAS如果長時間不成功，會給CPU帶來非常大的執(zhí)行開銷肛鹏。如果JVM能支持處理器提供的pause指令那么效率會有一定的提升逸邦，pause指令有兩個作用，第一它可以延遲流水線執(zhí)行指令（de-pipeline）,使CPU不會消耗過多的執(zhí)行資源在扰，延遲的時間取決于具體實(shí)現(xiàn)的版本缕减，在一些處理器上延遲時間是零。第二它可以避免在退出循環(huán)的時候因內(nèi)存順序沖突（memory order violation）而引起CPU流水線被清空（CPU pipeline flush）芒珠，從而提高CPU的執(zhí)行效率桥狡。
比較花費(fèi)CPU資源，即使沒有任何爭用也會做一些無用功皱卓。
只能保證一個共享變量的原子操作
當(dāng)對一個共享變量執(zhí)行操作時裹芝，我們可以使用循環(huán)CAS的方式來保證原子操作，但是對多個共享變量操作時娜汁，循環(huán)CAS就無法保證操作的原子性嫂易，這個時候就可以用鎖，或者有一個取巧的辦法掐禁，就是把多個共享變量合并成一個共享變量來操作怜械。比如有兩個共享變量i＝2,j=a，合并一下ij=2a穆桂，然后用CAS來操作ij宫盔。從Java1.5開始JDK提供了AtomicReference類來保證引用對象之間的原子性融虽，你可以把多個變量放在一個對象里來進(jìn)行CAS操作享完。會增加程序測試的復(fù)雜度，稍不注意就會出現(xiàn)問題
總結(jié)
可以用CAS在無鎖的情況下實(shí)現(xiàn)原子操作有额，但要明確應(yīng)用場合般又，非常簡單的操作且又不想引入鎖可以考慮使用CAS操作，當(dāng)想要非阻塞地完成某一操作也可以考慮CAS巍佑。不推薦在復(fù)雜操作中引入CAS茴迁，會使程序可讀性變差，且難以測試萤衰，同時會出現(xiàn)ABA問題堕义。
參考文檔
http://www.blogjava.net/xylz/archive/2010/07/04/325206.html
http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html
http://www.searchsoa.com.cn/showcontent_69238.htm
http://ifeve.com/atomic-operation/
http://www.infoq.com/cn/articles/java-memory-model-5
http://blog.csdn.net/aesop_wubo/article/details/7537960
http://ifeve.com/compare-and-swap/
