技術文章 » 淺談CAS底層原理和ABA問題

淺談CAS底層原理和ABA問題

2020-10-02 12:00:29

文章目錄

概述

CAS的全稱是Compare-And-Swap，它是CPU並行原語

它的功能是判斷記憶體某個位置的值是否為預期值，如果是則更改為新的值，這個過程是原子的

CAS並行原語體現在Java語言中就是sun.misc.Unsafe類的各個方法。呼叫UnSafe類中的CAS方法，JVM會幫我們實現出CAS組合指令，這是一種完全依賴於硬體的功能，通過它實現了原子操作，再次強調，由於CAS是一種系統原語，原語屬於作業系統用於範疇，是由若干條指令組成，用於完成某個功能的一個過程，並且原語的執行必須是連續的，在執行過程中不允許被中斷，也就是說CAS是一條CPU的原子指令，不會造成所謂的資料不一致的問題，也就是說CAS是執行緒安全的。

CAS底層原理

在Volatile中談到有JUC下的原子類，用來執行緒安全的實現number++，那就是atomicInteger.getAndIncrement()方法，檢視該方法原始碼
在這裡插入圖片描述
從這裡能夠看到，底層又呼叫了一個unsafe類的getAndAddInt方法

1.unsafe類
在這裡插入圖片描述
Unsafe是CAS的核心類，由於Java方法無法直接存取底層系統，需要通過本地（Native）方法來存取，Unsafe相當於一個後門，基於該類可以直接操作特定的記憶體資料。Unsafe類存在sun.misc包中，其內部方法操作可以像C的指標一樣直接操作記憶體，因為Java中的CAS操作的執行依賴於Unsafe類的方法。

注意Unsafe類的所有方法都是native修飾的，也就是說unsafe類中的方法都直接呼叫作業系統底層資源執行相應的任務

Atomic修飾的包裝類能夠保證原子性，依靠的就是底層的unsafe類

2.變數valueOffset

表示該變數值在記憶體中的偏移地址，因為Unsafe就是根據記憶體偏移地址獲取資料的。

在這裡插入圖片描述
通過valueOffset，直接通過記憶體地址，獲取到值，然後進行加1的操作

3.變數value用volatile修飾

保證了多執行緒之間的記憶體可見性
在這裡插入圖片描述
var5：就是我們從主記憶體中拷貝到工作記憶體中的值

那麼操作的時候，需要比較工作記憶體中的值，和主記憶體中的值進行比較

假設執行 compareAndSwapInt返回false，那麼就一直執行 while方法，直到期望的值和真實值一樣

  • val1：AtomicInteger物件本身
  • var2：該物件值得參照地址
  • var4：需要變動的數量
  • var5：用var1和var2找到的記憶體中的真實值
    • 用該物件當前的值與var5比較
    • 如果相同，更新var5 + var4 並返回true
    • 如果不同，繼續取值然後再比較，直到更新完成

這裡沒有用synchronized，而用CAS，這樣提高了並行性，也能夠實現一致性，是因為每個執行緒進來後，進入的do while迴圈，然後不斷的獲取記憶體中的值，判斷是否為最新，然後在進行更新操作。

假設執行緒A和執行緒B同時執行getAndInt操作（分別跑在不同的CPU上）

  1. AtomicInteger裡面的value原始值為3，即主記憶體中AtomicInteger的 value 為3，根據JMM模型，執行緒A和執行緒B各自持有一份價值為3的副本，分別儲存在各自的工作記憶體
  2. 執行緒A通過getIntVolatile(var1 , var2) 拿到value值3，這時執行緒A被掛起（該執行緒失去CPU執行權）
  3. 執行緒B也通過getIntVolatile(var1, var2)方法獲取到value值也是3，此時剛好執行緒B沒有被掛起，並執行了compareAndSwapInt方法，比較記憶體的值也是3，成功修改記憶體值為4，執行緒B打完收工，一切OK
  4. 這時候執行緒A恢復，執行CAS方法，比較發現自己手裡的數位3和主記憶體中的數位4不一致，說明該值已經被其它執行緒搶先一步修改過了，那麼A執行緒本次修改失敗，只能夠重新讀取後在來一遍了，也就是在執行do while
  5. 執行緒A重新獲取value值，因為變數value被volatile修飾，所以其它執行緒對它的修改，執行緒A總能夠看到，執行緒A繼續執行compareAndSwapInt進行比較替換，直到成功。

Unsafe類 + CAS思想： 也就是自旋，自我旋轉

CAS缺點

CAS不加鎖，保證一次性，但是需要多次比較

  • 迴圈時間長，開銷大（因為執行的是do while，如果比較不成功一直在迴圈，最差的情況，就是某個執行緒一直取到的值和預期值都不一樣，這樣就會無限迴圈）
  • 只能保證一個共用變數的原子操作
    • 當對一個共用變數執行操作時，我們可以通過迴圈CAS的方式來保證原子操作
    • 但是對於多個共用變數操作時，迴圈CAS就無法保證操作的原子性，這個時候只能用鎖來保證原子性
  • 引出來ABA問題

ABA問題

俗話來說就是「狸貓換太子」，比如十年前的小明同學跟十年後的小明同學，雖然是表明上同一個人，但十年間他發生了什麼事你並不清楚。

在這裡插入圖片描述
假設現在有兩個執行緒，分別是T1 和 T2，然後T1執行某個操作的時間為10秒，T2執行某個時間的操作是2秒，最開始AB兩個執行緒，分別從主記憶體中獲取A值，但是因為B的執行速度更快，他先把A的值改成B，然後在修改成A，然後執行完畢，T1執行緒在10秒後，執行完畢，判斷記憶體中的值為A，並且和自己預期的值一樣，它就認為沒有人更改了主記憶體中的值，就快樂的修改成B，但是實際上 可能中間經歷了 ABCDEFA 這個變換，也就是中間的值經歷了狸貓換太子。

所以ABA問題就是，在進行獲取主記憶體值的時候，該記憶體值在我們寫入主記憶體的時候，已經被修改了N次，但是最終又改成原來的值了

CAS只管開頭和結尾，也就是頭和尾是一樣，那就修改成功，中間的這個過程，可能會被人修改過

解決ABA問題

新增一種機制，也就是修改版本號，類似於時間戳的概念

如原來的A，版本號為2，落後於現在的版本號3，所以要重新獲取最新值，這裡就提出了一個使用時間戳版本號，來解決ABA問題的思路

這裡引出原子應用的概念

原子參照其實和原子包裝類是差不多的概念，就是將一個java類，用原子參照類進行包裝起來，那麼這個類就具備了原子性

AtomicStampedReference

時間戳原子參照，來這裡應用於版本號的更新，也就是每次更新的時候，需要比較期望值和當前值，以及期望版本號和當前版本號

public class ABADemo {

    /**
     * 普通的原子參照包裝類
     */
    static AtomicReference<Integer> atomicReference = new AtomicReference<>(100);

    // 傳遞兩個值，一個是初始值，一個是初始版本號
    static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(100, 1);

    public static void main(String[] args) {

        System.out.println("============以下是ABA問題的產生==========");

        new Thread(() -> {
            // 把100 改成 101 然後在改成100，也就是ABA
            atomicReference.compareAndSet(100, 101);
            atomicReference.compareAndSet(101, 100);
        }, "t1").start();

        new Thread(() -> {
            try {
                // 睡眠一秒，保證t1執行緒，完成了ABA操作
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            // 把100 改成 101 然後在改成100，也就是ABA
            System.out.println(atomicReference.compareAndSet(100, 2019) + "\t" + atomicReference.get());

        }, "t2").start();

        System.out.println("============以下是ABA問題的解決==========");

        new Thread(() -> {

            // 獲取版本號
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t 第一次版本號" + stamp);

            // 暫停t3一秒鐘
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            // 傳入4個值，期望值，更新值，期望版本號，更新版本號
            atomicStampedReference.compareAndSet(100, 101, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);

            System.out.println(Thread.currentThread().getName() + "\t 第二次版本號" + atomicStampedReference.getStamp());

            atomicStampedReference.compareAndSet(101, 100, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);

            System.out.println(Thread.currentThread().getName() + "\t 第三次版本號" + atomicStampedReference.getStamp());

        }, "t3").start();

        new Thread(() -> {

            // 獲取版本號
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t 第一次版本號" + stamp);

            // 暫停t4 3秒鐘，保證t3執行緒也進行一次ABA問題
            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            boolean result = atomicStampedReference.compareAndSet(100, 2019, stamp, stamp+1);

            System.out.println(Thread.currentThread().getName() + "\t 修改成功否：" + result + "\t 當前最新實際版本號：" + atomicStampedReference.getStamp());

            System.out.println(Thread.currentThread().getName() + "\t 當前實際最新值" + atomicStampedReference.getReference());


        }, "t4").start();

    }
}

在這裡插入圖片描述
執行緒t3，在進行ABA操作後，版本號變更成了3，而執行緒t4在進行操作的時候，就出現操作失敗了，因為版本號和當初拿到的不一樣

總結

CAS
CAS是compareAndSwap，比較當前工作記憶體中的值和主實體記憶體中的值，如果相同則執行規定操作，否者繼續比較直到主記憶體和工作記憶體的值一致為止

CAS應用
CAS有3個運算元，記憶體值V，舊的預期值A，要修改的更新值B。當且僅當預期值A和記憶體值V相同時，將記憶體值V修改為B，否者什麼都不做