漫畫：什麼是CAS機制？（進階篇）

來自：程式員小灰（微訊號：chengxuyuanxiaohui）

上一期為大家講解的CAS機制的基本概念，沒看過的小夥伴們可以點選下麵的連結：

漫畫：什麼是 CAS 機制？

這一期我們來深入介紹之前遺留的兩個問題：

1. Java當中CAS的底層實現

2. CAS的ABA問題和解決方法

首先看一看AtomicInteger當中常用的自增方法 incrementAndGet：

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;
}

這段程式碼是一個無限迴圈，也就是CAS的自旋。迴圈體當中做了三件事：
1.獲取當前值。
2.當前值+1，計算出標的值。
3.進行CAS操作，如果成功則跳出迴圈，如果失敗則重覆上述步驟。

這裡需要註意的重點是 get 方法，這個方法的作用是獲取變數的當前值。

如何保證獲得的當前值是記憶體中的最新值呢？很簡單，用volatile關鍵字來保證。有關volatile關鍵字的知識，我們之前有介紹過，這裡就不詳細闡述了。

接下來看一看compareAndSet方法的實現，以及方法所依賴物件的來歷：

compareAndSet方法的實現很簡單，只有一行程式碼。這裡涉及到兩個重要的物件，一個是unsafe，一個是valueOffset。

什麼是unsafe呢？Java語言不像C，C++那樣可以直接訪問底層作業系統，但是JVM為我們提供了一個後門，這個後門就是unsafe。unsafe為我們提供了硬體級別的原子操作。

至於valueOffset物件，是透過unsafe.objectFieldOffset方法得到，所代表的是AtomicInteger物件value成員變數在記憶體中的偏移量。我們可以簡單地把valueOffset理解為value變數的記憶體地址。

我們在上一期說過，CAS機制當中使用了3個基本運算元：記憶體地址V，舊的預期值A，要修改的新值B。

而unsafe的compareAndSwapInt方法引數包括了這三個基本元素：valueOffset引數代表了V，expect引數代表了A，update引數代表了B。

正是unsafe的compareAndSwapInt方法保證了Compare和Swap操作之間的原子性操作。

什麼是ABA呢？假設記憶體中有一個值為A的變數，儲存在地址V當中。

此時有三個執行緒想使用CAS的方式更新這個變數值，每個執行緒的執行時間有略微的偏差。執行緒1和執行緒2已經獲得當前值，執行緒3還未獲得當前值。

接下來，執行緒1先一步執行成功，把當前值成功從A更新為B；同時執行緒2因為某種原因被阻塞住，沒有做更新操作；執行緒3在執行緒1更新之後，獲得了當前值B。

再之後，執行緒2仍然處於阻塞狀態，執行緒3繼續執行，成功把當前值從B更新成了A。

最後，執行緒2終於恢復了執行狀態，由於阻塞之前已經獲得了“當前值”A，並且經過compare檢測，記憶體地址V中的實際值也是A，所以成功把變數值A更新成了B。

這個過程中，執行緒2獲取到的變數值A是一個舊值，儘管和當前的實際值相同，但記憶體地址V中的變數已經經歷了A->B->A的改變。

當我們舉一個提款機的例子。假設有一個遵循CAS原理的提款機，小灰有100元存款，要用這個提款機來提款50元。

由於提款機硬體出了點小問題，小灰的提款操作被同時提交兩次，開啟了兩個執行緒，兩個執行緒都是獲取當前值100元，要更新成50元。

理想情況下，應該一個執行緒更新成功，另一個執行緒更新失敗，小灰的存款只被扣一次。

執行緒1首先執行成功，把餘額從100改成50。執行緒2因為某種原因阻塞了。這時候，小灰的媽媽剛好給小灰匯款50元。

執行緒2仍然是阻塞狀態，執行緒3執行成功，把餘額從50改成100。

執行緒2恢復執行，由於阻塞之前已經獲得了“當前值”100，並且經過compare檢測，此時存款實際值也是100，所以成功把變數值100更新成了50。

這個舉例改編自《java特種兵》當中的一段例子。原本執行緒2應當提交失敗，小灰的正確餘額應該保持為100元，結果由於ABA問題提交成功了。

什麼意思呢？真正要做到嚴謹的CAS機制，我們在Compare階段不僅要比較期望值A和地址V中的實際值，還要比較變數的版本號是否一致。

我們仍然以最初的例子來說明一下，假設地址V中儲存著變數值A，當前版本號是01。執行緒1獲得了當前值A和版本號01，想要更新為B，但是被阻塞了。

這時候，記憶體地址V中的變數發生了多次改變，版本號提升為03，但是變數值仍然是A。

隨後執行緒1恢復執行，進行Compare操作。經過比較，執行緒1所獲得的值和地址V的實際值都是A，但是版本號不相等，所以這一次更新失敗。

在Java當中，AtomicStampedReference類就實現了用版本號做比較的CAS機制。

1. Java語言CAS底層如何實現？

利用unsafe提供了原子性操作方法。

2. 什麼是ABA問題？怎麼解決？

當一個值從A更新成B，又更新會A，普通CAS機制會誤判透過檢測。

利用版本號比較可以有效解決ABA問題。

---

●本文編號583，以後想閱讀這篇文章直接輸入583即可

●輸入m獲取文章目錄

推薦↓↓↓

 

演演算法與資料結構

更多推薦《18個技術類微信公眾號》

涵蓋：程式人生、演演算法與資料結構、駭客技術與網路安全、大資料技術、前端開發、Java、Python、Web開發、安卓開發、iOS開發、C/C++、.NET、Linux、資料庫、運維等。