小白也能與BAT面試官對線：CAS

前言

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

C A S作為並發程式設計必不可少的基礎知識，面試時C A S也是個高頻考點，所以說C A S是必知必會，本文將帶讀者們深入理解C A S。

大綱

#C A S基本概念

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

它包含3個參數C A S（V，E，N），V表示待更新的記憶體值，E表示預期值，N表示新值，當V值等於E值時，才會將V值更新成N 值，如果V值和E值不等，不做更新，這就是一次C A S的運算。

簡單地說，C A S需要你額外給出一個期望值，也就是你認為這個變數現在應該是什麼樣子的，如果變數不是你想像的那樣，說明它已經被別人修改過了，你只需要重新讀取，設定新期望值，再次嘗試修改就好了。

C A S如何保證原子性

原子性是指一個或多個運算在C P U執行的過程中不被中斷的特性，要麼執行，要不執行，不能執行到一半（不可被中斷的一個或一系列操作）。

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

• 匯流排鎖定
• 快取鎖定

#總線鎖定

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

總線鎖定是指C P U使用了匯流排鎖，所謂匯流排鎖定就是使用C P U提供的LOCK#訊號，當C P U在總線上輸出LOCK#訊號時，其他C P U的匯流排請求將會被阻塞。

快取鎖定

總線鎖定方式雖然保證了原子性，但是在鎖定期間，會導致大量阻塞，增加系統的性能開銷，所以現代C P U為了提升性能，通過鎖定範圍縮小的思想設計出了快取行鎖定（快取行是C P U快取儲存的最小單位）。

所謂快取鎖定是指C P U對快取行進行鎖定，當快取行中的共享變數回寫到記憶體時，其他 C P U會透過匯流排嗅探機制感知該共享變數是否發生變化，如果發生變化，讓自己對應的共享變數快取行失效，重新從記憶體讀取最新的數據，快取鎖定是基於快取一致性機制來實現的，因為快取一致性機制會阻止兩個以上C P U同時修改同一個共享變數（現代C P U基本上都支援和使用快取鎖定機制） 。

C A S的問題

C A S和鎖定都解決了原子性問題，和鎖相比沒有阻塞、線程上下文你切換、死鎖，所以C A S要比鎖擁有更優越的性能，但是C A S同樣有缺點。

C A S的問題如下

• 只能保證一個共享變數的原子操作
• #自旋時間太長（建立在自旋鎖的基礎上）
• ABA問題

##只能保證一個共享變數原子運算

C A S只能針對一個共享變數使用，如果多個共享變數就只能使用鎖了，當然如果你有辦法把多個變數整成一個變量，利用C A S也不錯，例如讀寫鎖中state 的高低位。

自旋時間太長

#當一個執行緒取得鎖定時失敗，不進行阻塞掛起，而是間隔一段時間再次嘗試獲取，直到成功為止，這種循環獲取的機制被稱為自旋鎖(spinlock)。

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

自旋鎖壞處顯而易見，執行緒在長時間內持有鎖，等待競爭鎖的執行緒一直自旋，即CPU一直空轉，資源浪費在毫無意義的地方，所以一般會限制自旋次數。

最後來說自旋鎖的實現，實現自旋鎖定可以基於C A S實現，先定義lockValue物件預設值1#， 1代表鎖定資源空閒，0代表鎖定資源被佔用，程式碼如下

public class SpinLock {
    
    //lockValue 默认值1
    private AtomicInteger lockValue = new AtomicInteger(1);
    
    //自旋获取锁
    public void lock(){

        // 循环检测尝试获取锁
        while (!tryLock()){
            // 空转
        }

    }
    
    //获取锁
    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實現的Integer原子操作類，也定義了3個函數lock、tryLock、unLock

tryLock函數-取得鎖定

#

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

unLock函數-釋放鎖定

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

lock函數-自旋取得鎖定

#

• 執行tryLock函數，傳回true#停止，否則一直循環

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

ABA問題

C A S需要檢查待更新的記憶體值有沒有被修改，如果沒有則更新，但是存在這樣一種情況，如果一個值原來是A，變成了B，然後又變成了A，在C A S檢查的時候會發現沒有被修改。

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

只是簡單的資料結構，確實不會有什麼問題，如果是複雜的資料結構可能就會有問題了（使用AtomicReference可以把C A S使用在物件上），以鍊錶資料結構為例，兩個執行緒透過C A S去刪除頭節點，假設現在鍊錶有A->B節點

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

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

#

以上是小白也能與BAT面試官對線：CAS的詳細內容。更多資訊請關注PHP中文網其他相關文章！