前言

Java並發(fā)程式設(shè)計(jì)系列番外篇C A S（Compare and swap），文章風(fēng)格依然是圖文並茂，通俗易懂，讓讀者也能與面試官瘋狂對(duì)線。

C A S作為並發(fā)程式設(shè)計(jì)必不可少的基礎(chǔ)知識(shí)，面試時(shí)C A S也是個(gè)高頻考點(diǎn)，所以說(shuō)C A S是必知必會(huì)，本文將帶讀者們深入理解C A S。

大綱

#C A S基本概念

C A S（compareAndSwap）也叫比較交換，是一種無(wú)鎖原子演算法，映射到作業(yè)系統(tǒng)就是一條cmpxchg硬體彙編指令（保證原子性），其作用是讓C P U將記憶體值更新為新值，但是有個(gè)條件，記憶體值必須與期望值相同，且C A S操作無(wú)需用戶態(tài)與內(nèi)核態(tài)切換，直接在用戶態(tài)對(duì)記憶體進(jìn)行讀寫操作（ 意味著不會(huì)阻塞/線程上下文切換）。

它包含3個(gè)參數(shù)C A S（V，E，N），V表示待更新的記憶體值，E表示預(yù)期值，N表示新值，當(dāng)V值等於E值時(shí)，才會(huì)將V值更新成N 值，如果V值和E值不等，不做更新，這就是一次C A S的運(yùn)算。

簡(jiǎn)單地說(shuō)，C A S需要你額外給出一個(gè)期望值，也就是你認(rèn)為這個(gè)變數(shù)現(xiàn)在應(yīng)該是什麼樣子的，如果變數(shù)不是你想像的那樣，說(shuō)明它已經(jīng)被別人修改過(guò)了，你只需要重新讀取，設(shè)定新期望值，再次嘗試修改就好了。

C A S如何保證原子性

原子性是指一個(gè)或多個(gè)運(yùn)算在C P U執(zhí)行的過(guò)程中不被中斷的特性，要麼執(zhí)行，要不執(zhí)行，不能執(zhí)行到一半（不可被中斷的一個(gè)或一系列操作）。

為了保證C A S的原子性，C P U提供了下面兩種方式

• 匯流排鎖定
• 快取鎖定

#總線鎖定

匯流排（B U S）是電腦元件間的傳輸資料方式，也就是說(shuō)C P U與其他元件連接傳輸數(shù)據(jù)，就是靠總線完成的，例如C P U對(duì)記憶體的讀寫。

總線鎖定是指C P U使用了匯流排鎖，所謂匯流排鎖定就是使用C P U提供的LOCK#訊號(hào)，當(dāng)C P U在總線上輸出LOCK#訊號(hào)時(shí)，其他C P U的匯流排請(qǐng)求將會(huì)被阻塞。

快取鎖定

總線鎖定方式雖然保證了原子性，但是在鎖定期間，會(huì)導(dǎo)致大量阻塞，增加系統(tǒng)的性能開(kāi)銷，所以現(xiàn)代C P U為了提升性能，通過(guò)鎖定範(fàn)圍縮小的思想設(shè)計(jì)出了快取行鎖定（快取行是C P U快取儲(chǔ)存的最小單位）。

所謂快取鎖定是指C P U對(duì)快取行進(jìn)行鎖定，當(dāng)快取行中的共享變數(shù)回寫到記憶體時(shí)，其他 C P U會(huì)透過(guò)匯流排嗅探機(jī)制感知該共享變數(shù)是否發(fā)生變化，如果發(fā)生變化，讓自己對(duì)應(yīng)的共享變數(shù)快取行失效，重新從記憶體讀取最新的數(shù)據(jù)，快取鎖定是基於快取一致性機(jī)制來(lái)實(shí)現(xiàn)的，因?yàn)榭烊∫恢滦詸C(jī)制會(huì)阻止兩個(gè)以上C P U同時(shí)修改同一個(gè)共享變數(shù)（現(xiàn)代C P U基本上都支援和使用快取鎖定機(jī)制） 。

C A S的問(wèn)題

C A S和鎖定都解決了原子性問(wèn)題，和鎖相比沒(méi)有阻塞、線程上下文你切換、死鎖，所以C A S要比鎖擁有更優(yōu)越的性能，但是C A S同樣有缺點(diǎn)。

C A S的問(wèn)題如下

• 只能保證一個(gè)共享變數(shù)的原子操作
• #自旋時(shí)間太長(zhǎng)（建立在自旋鎖的基礎(chǔ)上）
• ABA問(wèn)題

##只能保證一個(gè)共享變數(shù)原子運(yùn)算

C A S只能針對(duì)一個(gè)共享變數(shù)使用，如果多個(gè)共享變數(shù)就只能使用鎖了，當(dāng)然如果你有辦法把多個(gè)變數(shù)整成一個(gè)變量，利用C A S也不錯(cuò)，例如讀寫鎖中state 的高低位。

自旋時(shí)間太長(zhǎng)

#當(dāng)一個(gè)執(zhí)行緒取得鎖定時(shí)失敗，不進(jìn)行阻塞掛起，而是間隔一段時(shí)間再次嘗試獲取，直到成功為止，這種循環(huán)獲取的機(jī)制被稱為自旋鎖(spinlock)。

自旋鎖好處是，持有鎖的線程在短時(shí)間內(nèi)釋放鎖，那些等待競(jìng)爭(zhēng)鎖的線程就不需進(jìn)入阻塞狀態(tài)（無(wú)需線程上下文切換/無(wú)需用戶態(tài)與內(nèi)核態(tài)切換），它們只需要等一等（自旋），等到持有鎖的線程釋放鎖之後即可獲取，這樣就避免了用戶態(tài)和內(nèi)核態(tài)的切換消耗。

自旋鎖壞處顯而易見(jiàn)，執(zhí)行緒在長(zhǎng)時(shí)間內(nèi)持有鎖，等待競(jìng)爭(zhēng)鎖的執(zhí)行緒一直自旋，即CPU一直空轉(zhuǎn)，資源浪費(fèi)在毫無(wú)意義的地方，所以一般會(huì)限制自旋次數(shù)。

最後來(lái)說(shuō)自旋鎖的實(shí)現(xiàn)，實(shí)現(xiàn)自旋鎖定可以基於C A S實(shí)現(xiàn)，先定義lockValue物件預(yù)設(shè)值1#， 1代表鎖定資源空閒，0代表鎖定資源被佔(zhàn)用，程式碼如下

public?class?SpinLock?{
????
????//lockValue?默認(rèn)值1
????private?AtomicInteger?lockValue?=?new?AtomicInteger(1);
????
????//自旋獲取鎖
????public?void?lock(){

????????//?循環(huán)檢測(cè)嘗試獲取鎖
????????while?(!tryLock()){
????????????//?空轉(zhuǎn)
????????}

????}
????
????//獲取鎖
????public?boolean?tryLock(){
????????//?期望值1，更新值0，更新成功返回true，更新失敗返回false
????????return?lockValue.compareAndSet(1,0);
????}
????
????//釋放鎖
????public?void?unLock(){
????????if(!lockValue.compareAndSet(1,0)){
????????????throw?new?RuntimeException("釋放鎖失敗");
????????}
????}

}

上面定義了AtomicInteger類型的lockValue變量，AtomicInteger是Java基於C A S實(shí)現(xiàn)的Integer原子操作類，也定義了3個(gè)函數(shù)lock、tryLock、unLock

tryLock函數(shù)-取得鎖定

• 期望值1，更新值0
• #C A S更新
• 如果期望值與lockValue值相等，則lockValue值更新為0，傳回true，否則執(zhí)行下面邏輯
• 如果期望值與lockValue值不相等，不做任何更新，回傳false

unLock函數(shù)-釋放鎖定

• 期望值0，更新值1
• C A S更新
• 如果期望值與lockValue值相等，則lockValue值更新為1，傳回true，否則執(zhí)行下面邏輯
• #如果期望值與lockValue#值不相等，不做任何更新，返回false

lock函數(shù)-自旋取得鎖定

• 執(zhí)行tryLock函數(shù)，傳回true#停止，否則一直循環(huán)

從上圖可以看出，只有tryLock成功的執(zhí)行緒（把lockValue更新為0），才會(huì)執(zhí)行程式碼區(qū)塊，其他執(zhí)行緒個(gè)tryLock自旋等待lockValue被更新成1，tryLock成功的線程執(zhí)行unLock（把lockValue#更新為1），自旋的執(zhí)行緒才會(huì)tryLock成功。

ABA問(wèn)題

C A S需要檢查待更新的記憶體值有沒(méi)有被修改，如果沒(méi)有則更新，但是存在這樣一種情況，如果一個(gè)值原來(lái)是A，變成了B，然後又變成了A，在C A S檢查的時(shí)候會(huì)發(fā)現(xiàn)沒(méi)有被修改。

假設(shè)有兩個(gè)線程，線程1讀取到記憶體值A，線程1時(shí)間片用完，切換到線程2，線程2也讀取到了記憶體值A，並且把它修改為B值，然後再把B值還原到A值，簡(jiǎn)單說(shuō)，修改次序是A->B->A，接著執(zhí)行緒1恢復(fù)運(yùn)行，它發(fā)現(xiàn)記憶體值還是A，然後執(zhí)行C A S操作，這就是著名的ABA問(wèn)題，但好像又看不出什麼問(wèn)題。

只是簡(jiǎn)單的資料結(jié)構(gòu)，確實(shí)不會(huì)有什麼問(wèn)題，如果是複雜的資料結(jié)構(gòu)可能就會(huì)有問(wèn)題了（使用AtomicReference可以把C A S使用在物件上），以鍊錶資料結(jié)構(gòu)為例，兩個(gè)執(zhí)行緒透過(guò)C A S去刪除頭節(jié)點(diǎn)，假設(shè)現(xiàn)在鍊錶有A->B節(jié)點(diǎn)

• 線程1刪除A節(jié)點(diǎn)，B節(jié)點(diǎn)成為頭節(jié)點(diǎn)，正要執(zhí)行C A S(A,A,B)時(shí)，時(shí)間片用完，切換到執(zhí)行緒2
• 執(zhí)行緒2刪除A、B節(jié)點(diǎn)
• 線程2加入C、A節(jié)點(diǎn)，鍊錶節(jié)點(diǎn)變成A- >C
• 線程1重新取得時(shí)間片，執(zhí)行C A S(A,A,B)
• 遺失C節(jié)點(diǎn)
#

要解決A B A問(wèn)題也非常簡(jiǎn)單，只要追加版本號(hào)即可，每次改變時(shí)加1，即A —> B — > A，變成1A —> 2B —> 3A，在Java#中提供了AtomicStampedRdference可以實(shí)作這個(gè)方案（面試只要問(wèn)了C A S，就一定會(huì)問(wèn)ABA，這塊一定要搞清楚）。