大話CAS

語言: CN / TW / HK

theme: cyanosis

1. 無鎖的概念

在談論無鎖概念時,總會關聯起樂觀派與悲觀派,對於樂觀派而言,他們認為事情總會往好的方向發展,總是認為壞的情況發生的概率特別小

可以無所顧忌地做事,但對於悲觀派而言,他們總會認為發展事態如果不及時控制,以後就無法挽回了,即使無法挽回的局面幾乎不可能發生。

這兩種派系對映到併發程式設計中就如同加鎖與無鎖的策略,即加鎖是一種悲觀策略,無鎖是一種樂觀策略,因為對於加鎖的併發程式來說,它們總是認為每次訪問共享資源時總會發生衝突,因此必須對每一次資料操作實施加鎖策略。

而無鎖則總是假設對共享資源的訪問沒有衝突,執行緒可以不停執行,無需加鎖,無需等待,一旦發現衝突,無鎖策略則採用一種稱為CAS的技術來保證執行緒執行的安全性,

這項CAS技術就是無鎖策略實現的關鍵,下面我們進一步瞭解CAS技術的奇妙之處。

2. 什麼是CAS

CAS(Compare and Swap),即比較並替換,是用於實現多執行緒同步的原子指令。

執行函式:CAS(V,E,N)

其包含3個引數

  • V表示要更新的變數
  • E表示預期值
  • N表示新值

假定有兩個操作A和B,如果從執行A的執行緒來看,當另一個執行緒執行B時,要麼將B全部執行完,要麼完全不執行B,那麼A和B對彼此來說是原子的。

實現原子操作可以使用鎖,鎖機制,滿足基本的需求是沒有問題的了,但是有的時候我們的需求並非這麼簡單,我們需要更有效,更加靈活的機制,synchronized關鍵字是基於阻塞的鎖機制,也就是說當一個執行緒擁有鎖的時候,訪問同一資源的其它執行緒需要等待,直到該執行緒釋放鎖,

這裡會有些問題:首先,如果被阻塞的執行緒優先順序很高很重要怎麼辦?其次,如果獲得鎖的執行緒一直不釋放鎖怎麼辦?(這種情況是非常糟糕的)。還有一種情況,如果有大量的執行緒來競爭資源,那CPU將會花費大量的時間和資源來處理這些競爭,同時,還有可能出現一些例如死鎖之類的情況,最後,其實鎖機制是一種比較粗糙,粒度比較大的機制,相對於像計數器這樣的需求有點兒過於笨重。

實現原子操作還可以使用當前的處理器基本都支援CAS的指令,只不過每個廠家所實現的演算法並不一樣,每一個CAS操作過程都包含三個運算子:一個記憶體地址V,一個期望的值A和一個新值B,操作的時候如果這個地址上存放的值等於這個期望的值A,則將地址上的值賦為新值B,否則不做任何操作。

CAS的基本思路就是,如果這個地址上的值和期望的值相等,則給其賦予新值,否則不做任何事兒,但是要返回原值是多少。迴圈CAS就是在一個迴圈裡不斷的做cas操作,直到成功為止。

CAS是怎麼實現執行緒的安全呢?語言層面不做處理,我們將其交給硬體—CPU和記憶體,利用CPU的多處理能力,實現硬體層面的阻塞,再加上volatile變數的特性即可實現基於原子操作的執行緒安全。

3. CPU指令對CAS的支援

或許我們可能會有這樣的疑問,假設存在多個執行緒執行CAS操作並且CAS的步驟很多,有沒有可能在判斷V和E相同後,正要賦值時,切換了執行緒,更改了值。造成了資料不一致呢?答案是否定的,因為CAS是一種系統原語,原語屬於作業系統用語範疇,是由若干條指令組成的,用於完成某個功能的一個過程,並且原語的執行必須是連續的,在執行過程中不允許被中斷,也就是說CAS是一條CPU的原子指令,不會造成所謂的資料不一致問題。

4. 悲觀鎖,樂觀鎖

說到CAS,不得不提到兩個專業詞語:悲觀鎖,樂觀鎖。我們先來看看什麼是悲觀鎖,什麼是樂觀鎖。

4.1 悲觀鎖

顧名思義,就是比較悲觀的鎖,總是假設最壞的情況,每次去拿資料的時候都認為別人會修改,所以每次在拿資料的時候都會上鎖,這樣別人想拿這個資料就會阻塞直到它拿到鎖(共享資源每次只給一個執行緒使用,其它執行緒阻塞,用完後再把資源轉讓給其它執行緒)。傳統的關係型資料庫裡邊就用到了很多這種鎖機制,比如行鎖,表鎖等,讀鎖,寫鎖等,都是在做操作之前先上鎖。Java中synchronizedReentrantLock等獨佔鎖就是悲觀鎖思想的實現。

4.2 樂觀鎖

反之,總是假設最好的情況,每次去拿資料的時候都認為別人不會修改,所以不會上鎖,但是在更新的時候會判斷一下在此期間別人有沒有去更新這個資料,可以使用版本號機制和CAS演算法實現。樂觀鎖適用於多讀的應用型別,這樣可以提高吞吐量,像資料庫提供的類似於write_condition機制,其實都是提供的樂觀鎖。我們今天講的CAS就是樂觀鎖。

由於CAS操作屬於樂觀派,它總認為自己可以成功完成操作,當多個執行緒同時使用CAS操作一個變數時,只有一個會勝出,併成功更新,其餘均會失敗,但失敗的執行緒並不會被掛起,僅是被告知失敗,並且允許再次嘗試,當然也允許失敗的執行緒放棄操作。基於這樣的原理,CAS操作即使沒有鎖,同樣知道其他執行緒對共享資源操作影響,並執行相應的處理措施。同時從這點也可以看出,由於無鎖操作中沒有鎖的存在,因此不可能出現死鎖的情況,也就是說無鎖操作天生免疫死鎖。

5. CAS 的優點

非阻塞的輕量級樂觀鎖, 通過CPU指令實現, 在資源競爭不激烈的情況下效能高, 相比synchronize重量級悲觀鎖, synchronize有複雜的加鎖, 解鎖和喚醒執行緒操作.。

6. 三大問題

6.1 ABA問題

假設這樣一種場景,當第一個執行緒執行CAS(V,E,U)操作,在獲取到當前變數V,準備修改為新值U前,另外兩個執行緒已連續修改了兩次變數V的值,使得該值又恢復為舊值,這樣的話,我們就無法正確判斷這個變數是否已被修改過,如下圖

image.png

因為CAS需要在操作值的時候,檢查值有沒有發生變化,如果沒有發生變化則更新,但是如果一個值原來是A,變成了B,又變成了A,那麼使用CAS進行檢查時會發現它的值沒有發生變化,但是實際上卻變化了。

就像上圖描述的一樣,執行緒A原來的值是10,執行緒B修改為了20,但是執行緒C又將值修改為了10,這個時候執行緒A來讀取了,與舊值做判斷,發現還是10,沒有修改過,就做了更新操作,但是我們知道,值有過變更。

這就是典型的CAS的ABA問題,一般情況這種情況發生的概率比較小,可能發生了也不會造成什麼問題,比如說我們對某個做加減法,不關心數字的過程,那麼發生ABA問題也沒啥關係。但是在某些情況下還是需要防止的,那麼該如何解決呢?在Java中解決ABA問題,我們可以使用以下兩個原子類。

6.1.1 AtomicStampedReference

AtomicStampedReference原子類是一個帶有時間戳的物件引用,在每次修改後,AtomicStampedReference不僅會設定新值而且還會記錄更改的時間。當AtomicStampedReference設定物件值時,物件值以及時間戳都必須滿足期望值才能寫入成功,這也就解決了反覆讀寫時,無法預知值是否已被修改的窘境,測試demo如下

```java public class ABADemo {

static AtomicInteger atIn = new AtomicInteger(100);

//初始化時需要傳入一個初始值和初始時間
static AtomicStampedReference<Integer> atomicStampedR =
        new AtomicStampedReference<Integer>(200,0);


static Thread t1 = new Thread(new Runnable() {
    @Override
    public void run() {
        //更新為200
        atIn.compareAndSet(100, 200);
        //更新為100
        atIn.compareAndSet(200, 100);
    }
});


static Thread t2 = new Thread(new Runnable() {
    @Override
    public void run() {
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        boolean flag=atIn.compareAndSet(100,500);
        System.out.println("flag:"+flag+",newValue:"+atIn);
    }
});


static Thread t3 = new Thread(new Runnable() {
    @Override
    public void run() {
        int time=atomicStampedR.getStamp();
        //更新為200
        atomicStampedR.compareAndSet(100, 200,time,time+1);
        //更新為100
        int time2=atomicStampedR.getStamp();
        atomicStampedR.compareAndSet(200, 100,time2,time2+1);
    }
});


static Thread t4 = new Thread(new Runnable() {
    @Override
    public void run() {
        int time = atomicStampedR.getStamp();
        System.out.println("sleep 前 t4 time:"+time);
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        boolean flag=atomicStampedR.compareAndSet(100,500,time,time+1);
        System.out.println("flag:"+flag+",newValue:"+atomicStampedR.getReference());
    }
});

public static  void  main(String[] args) throws InterruptedException {
    t1.start();
    t2.start();
    t1.join();
    t2.join();

    t3.start();
    t4.start();
    /**
     * 輸出結果:
     flag:true,newValue:500
     sleep 前 t4 time:0
     flag:false,newValue:200
     */
}

} ```

對比輸出結果可知,AtomicStampedReference類確實解決了ABA的問題,下面我們簡單看看其內部實現原理

```java public class AtomicStampedReference { //通過Pair內部類儲存資料和時間戳 private static class Pair { final T reference; final int stamp; private Pair(T reference, int stamp) { this.reference = reference; this.stamp = stamp; } static Pair of(T reference, int stamp) { return new Pair(reference, stamp); } } //儲存數值和時間的內部類 private volatile Pair pair;

//構造器,建立時需傳入初始值和時間初始值
public AtomicStampedReference(V initialRef, int initialStamp) {
    pair = Pair.of(initialRef, initialStamp);
}

} ```

接著看看其compareAndSet方法的實現:

java public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp) { Pair<V> current = pair; return expectedReference == current.reference && expectedStamp == current.stamp && ((newReference == current.reference && newStamp == current.stamp) || casPair(current, Pair.of(newReference, newStamp))); }

同時對當前資料和當前時間進行比較,只有兩者都相等是才會執行casPair()方法,單從該方法的名稱就可知是一個CAS方法,最終呼叫的還是Unsafe類中的compareAndSwapObject方法

java private boolean casPair(Pair<V> cmp, Pair<V> val) { return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val); }

到這我們就很清晰AtomicStampedReference的內部實現思想了,通過一個鍵值對Pair儲存資料和時間戳,在更新時對資料和時間戳進行比較,只有兩者都符合預期才會呼叫Unsafe的compareAndSwapObject方法執行數值和時間戳替換,也就避免了ABA的問題。

6.1.2 AtomicMarkableReference

AtomicMarkableReference與AtomicStampedReference不同的是,AtomicMarkableReference維護的是一個boolean值的標識,也就是說至於true和false兩種切換狀態,經過測試,這種方式並不能完全防止ABA問題的發生,只能減少ABA問題發生的概率。

```java public class ABADemo { static AtomicMarkableReference atMarkRef = new AtomicMarkableReference(100,false);

static Thread t5 = new Thread(new Runnable() { @Override public void run() { boolean mark=atMarkRef.isMarked(); System.out.println("mark:"+mark); //更新為200 System.out.println("t5 result:"+atMarkRef.compareAndSet(atMarkRef.getReference(), 200,mark,!mark)); } });

static Thread t6 = new Thread(new Runnable() {
    @Override
    public void run() {
        boolean mark2=atMarkRef.isMarked();
        System.out.println("mark2:"+mark2);
        System.out.println("t6 result:"+atMarkRef.compareAndSet(atMarkRef.getReference(), 100,mark2,!mark2));
    }
});

static Thread t7 = new Thread(new Runnable() {
    @Override
    public void run() {
        boolean mark=atMarkRef.isMarked();
        System.out.println("sleep 前 t7 mark:"+mark);
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        boolean flag=atMarkRef.compareAndSet(100,500,mark,!mark);
        System.out.println("flag:"+flag+",newValue:"+atMarkRef.getReference());
    }
});

public static  void  main(String[] args) throws InterruptedException {        
    t5.start();t5.join();
    t6.start();t6.join();
    t7.start();

    /**
     * 輸出結果:
     mark:false
     t5 result:true
     mark2:true
     t6 result:true
     sleep 前 t5 mark:false
     flag:true,newValue:500 ---->成功了.....說明還是發生ABA問題
     */
}

} ```

AtomicMarkableReference的實現原理與AtomicStampedReference類似。到此,我們也明白瞭如果要完全杜絕ABA問題的發生,我們應該使用AtomicStampedReference原子類更新物件,而對於AtomicMarkableReference來說只能減少ABA問題的發生概率,並不能杜絕。

6.2 迴圈時間長開銷大

自旋CAS如果長時間不成功,會給CPU帶來非常大的執行開銷。

6.3 只能保證一個共享變數的原子操作

當對一個共享變數執行操作時,我們可以使用迴圈CAS的方式來保證原子操作,但是對多個共享變數操作時,迴圈CAS就無法保證操作的原子性,這個時候就可以用鎖。

還有一個取巧的辦法,就是把多個共享變數合併成一個共享變數來操作。比如,有兩個共享變數i=2,j=a,合併一下ij=2a,然後用CAS來操作ij。從Java 1.5開始,

JDK提供了AtomicReference類來保證引用物件之間的原子性,就可以把多個變數放在一個物件裡來進行CAS操作。

往期乾貨:

本文由傳智教育博學谷教研團隊釋出。

如果本文對您有幫助,歡迎關注點贊;如果您有任何建議也可留言評論私信,您的支援是我堅持創作的動力。

轉載請註明出處!