本文來源于微信公眾號【胖滾豬學編程】、轉載請注明出處

在漫畫并發編程系統博文中，我們講了N篇關于鎖的知識，確實，鎖是解決并發問題的萬能鑰匙，可是并發問題只有鎖能解決嗎？今天要出場一個大BOSS：CAS無鎖演算法，可謂是并發編程核心中的核心！

溫故

首先我們再回顧一下原子性問題的原因，參考【漫畫】JAVA并發編程如何解決原子性問題，

兩個執行緒同時把count=0加載到自己的作業記憶體，執行緒B先執行count++操作，此時主記憶體已經變化成了1，但是執行緒A依舊以為count=0，這是導致問題的根源，

所以解決方案就是：不能讓執行緒A以為count=0，而是要和主記憶體進行一次compare(比較)，如果記憶體中的值是0，說明沒有其他執行緒更新過count值，那么就swap(交換)，把新值寫回主記憶體，如果記憶體中的值不是0，比如本案例中，記憶體中count就已經被執行緒B更新成了1，比較0!=1，因此compare失敗，不把新值寫回主記憶體，

本文來源于微信公眾號【胖滾豬學編程】，一個集顏值與才華于一身的女程式媛、以漫畫形式讓編程so easy and interesting！轉載請注明出處

CAS概念

CAS （compareAndSwap），中文叫比較交換，一種無鎖原子演算法，

CAS演算法包含 3 個引數 CAS（V，E，N），V表示要更新變數在記憶體中的值，E表示舊的預期值，N表示新值，
僅當 V值等于E值時，才會將V的值設為N，
如果V值和E值不同，則說明已經有其他執行緒做兩個更新，那么當前執行緒不做更新，而是自旋，

模擬CAS實作

既然我們了解了CAS的思想，那可以手寫一個簡單的CAS模型：

    // count必須用volatile修飾 保證不同執行緒之間的可見性
    private volatile static int count;
    
    public void addOne() {
        int newValue;
        do {
            newValue = https://www.cnblogs.com/liuyanling/p/count++;
        } while (!compareAndSwapInt(expectCount, newValue)); //自旋 回圈
    }

    public final boolean compareAndSwapInt(int expectCount, int newValue) {
        // 讀目前 count 的值
        int curValue = count;
        // 比較目前 count 值是否 == 期望值
        if (curValue == expectCount) {
            // 如果是，則更新 count 的值
            count = newValue;
            return true;

        }
        //否則回傳false 然后回圈
        return false;
    }

這個簡單的模擬代碼，其實基本上把CAS的思想體現出來了，但實際上CAS原理可要復雜很多哦，我們還是看看JAVA是怎么實作CAS的吧！

原子類

要了解JAVA中CAS的實作，那不得不提到大名鼎鼎的原子類，原子類的使用非常簡單，而其中深奧的原理就是CAS無鎖演算法，

Java 并發包里提供的原子類內容很豐富，我們可以將它們分為五個類別：原子化的基本資料型別、原子化的物件參考型別、原子化陣列、原子化物件屬性更新器和原子化的累加器，

原子類的使用可謂非常簡單，相信只要看一下api就知道如何使用，因此不過多解釋，如有需要可以參考本人github代碼，
此處只以AtomicInteger為例子，測驗一下原子類是否名副其實可以保證原子性：

    private static AtomicInteger count = new AtomicInteger(0);
    private static int count1 = 0;
    //省略代碼 同時啟動10個執行緒 分別測驗AtomicInteger和普通int的輸出結果
    private static void add10K() {
        int idx = 0;
        while (idx++ < 10000) {
            //使用incrementAndGet實作i++功能
            count.incrementAndGet();
        }
        countDownLatch.countDown();
    }
    private static void add10K1() {
        int idx = 0;
        while (idx++ < 10000) {
            count1++;
        }
        countDownLatch.countDown();
    }

通過測驗可以發現，使用AtomicInteger可以保證輸出結果為100000，而普通int則不能保證，

本文來源于微信公眾號【胖滾豬學編程】，一個集顏值與才華于一身的女程式媛、以漫畫形式讓編程so easy and interesting！轉載請注明出處

CAS原始碼分析

據此，我們又可以回歸正題，JAVA是怎么實作CAS的呢？跟蹤一下AtomicInteger中的incrementAndGet()方法，相信就會有答案了，
首先關注一下AtomicInteger.java中這么幾個東西：

    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;//資料在記憶體中的地址偏移量，通過偏移地址可以獲取資料原值

    static {
        try {
            //計算變數 value 在類物件中的偏移量
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;//要修改的值 volatile保證可見性

    public final int incrementAndGet() {
        return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
    }

Unsafe，是CAS的核心類，由于Java方法無法直接訪問底層系統，需要通過本地（native）方法來訪問，Unsafe相當于一個后門，基于該類可以直接操作特定記憶體的資料，
變數valueOffset，表示該變數值在記憶體中的偏移地址，因為Unsafe就是根據記憶體偏移地址獲取資料的，
變數value必須用volatile修飾，保證了多執行緒之間的記憶體可見性，

當然具體實作我們還是得瞧瞧getAndAddInt方法：

    //內部使用自旋的方式進行CAS更新（while回圈進行CAS更新，如果更新失敗，則回圈再次重試）
    public final int getAndAddInt(Object var1, long var2, int var4) {
         //var1為當前這個物件，如count.getAndIncrement()，則var1為count這個物件
        //第二個引數為AtomicInteger物件value成員變數在記憶體中的偏移量
        //第三個引數為要增加的值
        int var5;
        do {
            //var5 獲取物件記憶體地址偏移量上的數值v 即預期舊值
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));//回圈判斷記憶體位置的值與預期原值是否相匹配

        return var5;
    }

此時我們還想繼續了解compareAndSwapInt的實作，點進去看，首先映入眼簾的是四個引數：1、當前的實體 2、實體變數的記憶體地址偏移量 3、預期的舊值 4、要更新的值

    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

還想繼續刨根問底，會發現點不動了，因為用native修飾的方法代表是底層方法，當然如果你非得一探究竟你也可以找找對應的unsafe.cpp 檔案進行深度決議C代碼：

個人認為沒必要深究，畢竟術業有專攻，你只需要知道其實核心代碼就是一條 cmpxchg 指令，
cmpxchg: 即“比較并交換”指令，與我們上面說的思想是一樣的：將 eax 暫存器中的值（compare_value）與 [edx] 雙字記憶體單元中的值進行對比，如果相同，則將 ecx 暫存器中的值（exchange_value）存入 [edx] 記憶體單元中，

總之：你只需要記住：CAS是靠硬體實作的，從而在硬體層面提升效率，實作方式是基于硬體平臺的匯編指令，在intel的CPU中，使用的是cmpxchg指令， 核心思想就是：比較要更新變數的值V和預期值E（compare），相等才會將V的值設為新值N（swap），

CAS真有這么好嗎？

CAS和鎖都解決了原子性問題，和鎖相比，由于其非阻塞的，它對死鎖問題天生免疫，并且，執行緒間的相互影響也非常小，更為重要的是，使用無鎖的方式完全沒有鎖競爭帶來的系統開銷，也沒有執行緒間頻繁調度帶來的開銷，因此，他要比基于鎖的方式擁有更優越的性能，

但是，CAS真的有那么好嗎？又到挑刺時間了！

要讓我們失望了，CAS并沒有那么好，主要表現在三個方面：

1、回圈時間太長
2、只能保證一個共享變數原子操作
3、ABA問題，

回圈時間太長
如果CAS長時間地不成功，我們知道會持續回圈、自旋，必然會給CPU帶來非常大的開銷，在JUC中有些地方就限制了CAS自旋的次數，例如BlockingQueue的SynchronousQueue，

只能保證一個共享變數原子操作
看了CAS的實作就知道這只能針對一個共享變數，如果是多個共享變數就只能使用鎖了，當然如果你有辦法把多個變數整成一個變數，利用CAS也不錯，例如讀寫鎖中state的高低位，

ABA問題
這可是個面試重點問題哦！認真聽好！

CAS需要檢查操作值有沒有發生改變，如果沒有發生改變則更新，但是存在這樣一種情況：如果一個值原來是A，變成了B，然后又變成了A，那么在CAS檢查的時候會發現沒有改變，但是實質上它已經發生了改變，這就是所謂的ABA問題，
某些情況我們并不關心 ABA 問題，例如數值的原子遞增，但也不能所有情況下都不關心，例如原子化的更新物件很可能就需要關心 ABA 問題，因為兩個 A 雖然相等，但是第二個 A 的屬性可能已經發生變化了，

對于ABA問題其解決方案是加上版本號，即在每個變數都加上一個版本號，每次改變時加1，即A —> B —> A，變成1A —> 2B —> 3A，

原子類之AtomicStampedReference可以解決ABA問題，它內部不僅維護了物件值，還維護了一個Stamp（可把它理解為版本號，它使用整數來表示狀態值），當AtomicStampedReference對應的數值被修改時，除了更新資料本身外，還必須要更新版本號，當AtomicStampedReference設定物件值時，物件值以及版本號都必須滿足期望值，寫入才會成功，因此，即使物件值被反復讀寫，寫回原值，只要版本號發生變化，就能防止不恰當的寫入，

    // 引數依次為：期望值 寫入新值 期望版本號 新版本號
    public boolean compareAndSet(V expectedReference, V
            newReference, int expectedStamp, int newStamp);

    //獲得當前物件參考
    public V getReference();

    //獲得當前版本號
    public int getStamp();

    //設定當前物件參考和版本號
    public void set(V newReference, int newStamp);

說理論太多也沒用，還是親自實驗它是否能解決ABA問題吧：

    private static AtomicStampedReference<Integer> count = new AtomicStampedReference<>(10, 0);

    public static void main(String[] args) {
        Thread main = new Thread(() -> {
            int stamp = count.getStamp(); //獲取當前版本

            log.info("執行緒{} 當前版本{}",Thread.currentThread(),stamp);
            try {
                Thread.sleep(1000); //等待1秒 ，以便讓干擾執行緒執行
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            boolean isCASSuccess = count.compareAndSet(10, 12, stamp, stamp + 1);  //此時expectedReference未發生改變，但是stamp已經被修改了,所以CAS失敗
            log.info("CAS是否成功={}",isCASSuccess);
        }, "主操作執行緒");

        Thread other = new Thread(() -> {
            int stamp = count.getStamp(); //獲取當前版本
            log.info("執行緒{} 當前版本{}",Thread.currentThread(),stamp);
            count.compareAndSet(10, 12, stamp, stamp + 1);
            log.info("執行緒{} 增加后版本{}",Thread.currentThread(),count.getStamp());

            // 模擬ABA問題 先更新成12 又更新回10
            int stamp1 = count.getStamp(); //獲取當前版本
            count.compareAndSet(12, 10, stamp1, stamp1 + 1);
            log.info("執行緒{} 減少后版本{}",Thread.currentThread(),count.getStamp());
        }, "干擾執行緒");

        main.start();
        other.start();
    }

輸出結果如下：

執行緒Thread[主操作執行緒,5,main] 當前版本0
[干擾執行緒] INFO - 執行緒Thread[干擾執行緒,5,main] 當前版本0
[干擾執行緒] INFO  - 執行緒Thread[干擾執行緒,5,main] 增加后版本1
[干擾執行緒] INFO - 執行緒Thread[干擾執行緒,5,main] 減少后版本2
[主操作執行緒] INFO  - CAS是否成功=false

總結

JAVA博大精深，解決并發問題可不僅僅是鎖才能擔此大任，CAS無鎖演算法對于解決原子性問題同樣是勢在必得，而原子類，則是無鎖工具類的典范，原子類包括五大型別(原子化的基本資料型別、原子化的物件參考型別、原子化陣列、原子化物件屬性更新器和原子化的累加器)，

CAS 是一種樂觀鎖，樂觀鎖會以一種更加樂觀的態度對待事情，認為自己可以操作成功，而悲觀鎖會讓執行緒一直阻塞，因此CAS具有很多優勢，比如性能佳、可以避免死鎖，但是它沒有那么好，你應該考慮到ABA問題、回圈時間長的問題，因此需要綜合選擇，適合自己的才是最好的，

附錄：并發編程全系列代碼github

本文來源于微信公眾號【胖滾豬學編程】，一個集顏值與才華于一身的女程式媛、以漫畫形式讓編程so easy and interesting！歡迎關注與我一起交流！

本文轉載自公眾號【胖滾豬學編程】用漫畫讓編程so easy and interesting！歡迎關注！形象來源于微信表情包【胖滾家族】喜歡可以下載哦~

轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/8650.html

標籤：大數據

上一篇：一站式Kafka平臺解決方案——KafkaCenter

下一篇：選方向？大資料的職位你了解多少

【漫畫】CAS原理分析！無鎖原子類也能解決并發問題！

溫故

CAS概念

模擬CAS實作

原子類

CAS原始碼分析

CAS真有這么好嗎？

總結