深入學習CAS

語言: CN / TW / HK

highlight: atom-one-dark theme: vuepress


小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動 本文基於Java 11

什麼是CAS

CAS是Compare-And-Swap的縮寫,意思為比較並交換。以AtomicInteger為例,其提供了compareAndSet(int expect, int update)方法,expect為期望值(被修改的值在主記憶體中的期望值),update為修改後的值。compareAndSet方法返回值型別為布林型別,修改成功則返回true,修改失敗返回false。

舉個compareAndSet方法的例子:

```java public class AtomticIntegerTest { public static void main(String[] args) { AtomicInteger atomicInteger = new AtomicInteger(0);

    boolean result = atomicInteger.compareAndSet(0, 1);
    System.out.println(result);
    System.out.println(atomicInteger.get());
}

} ```

上面例子中,通過AtomicInteger(int initialValue)構造方法指定了AtomicInteger類成員變數value的初始值為0:

```java public class AtomicInteger extends Number implements java.io.Serializable { ......

private volatile int value;

/**
 * Creates a new AtomicInteger with the given initial value.
 *
 * @param initialValue the initial value
 */
public AtomicInteger(int initialValue) {
    value = initialValue;
}
......

} ```

接著執行compareAndSet方法,main執行緒從主記憶體中拷貝了value的副本到工作執行緒,值為0,並將這個值修改為1。如果此時主記憶體中value的值還是為0的話(言外之意就是沒有被其他執行緒修改過),則將修改後的副本值刷回主記憶體更新value的值。所以上面的例子執行結果應該是true和1:

image-20211007133530980.png

將上面的例子修改為:

```java public class AtomticIntegerTest { public static void main(String[] args) { AtomicInteger atomicInteger = new AtomicInteger(0);

    boolean firstResult = atomicInteger.compareAndSet(0, 1);
    boolean secondResult = atomicInteger.compareAndSet(0, 1);
    System.out.println(firstResult);
    System.out.println(secondResult);
    System.out.println(atomicInteger.get());
}

} ```

上面例子中,main執行緒第二次呼叫compareAndSet方法的時候,value的值已經被修改為1了,不符合其expect的值,所以修改將失敗。上面例子輸出如下:

image-20211007133634261.png

CAS底層原理

檢視compareAndSet方法原始碼:

java /** * Atomically sets the value to {@code newValue} * if the current value {@code == expectedValue}, * with memory effects as specified by {@link VarHandle#compareAndSet}. * * @param expectedValue the expected value * @param newValue the new value * @return {@code true} if successful. False return indicates that * the actual value was not equal to the expected value. */ public final boolean compareAndSet(int expectedValue, int newValue) { return U.compareAndSetInt(this, VALUE, expectedValue, newValue); }

該方法通過呼叫unsafe類的compareAndSwapInt方法實現相關功能。compareAndSwapInt方法包含四個引數:

  1. this,當前物件;

  2. valueOffsetvalue成員變數的記憶體偏移量(也就是記憶體地址):

    ```java private static final long valueOffset;

    static { try { valueOffset = unsafe.objectFieldOffset (AtomicInteger.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } ```

  3. expect,期待值;

  4. update,更新值。

所以這個方法的含義為:獲取當前物件value成員變數在主記憶體中的值,和傳入的期待值相比,如果相等則說明這個值沒有被別的執行緒修改過,然後將其修改為更新值。

那麼unsafe又是什麼?它的compareAndSwapInt方法是原子性的麼?檢視該方法的原始碼:

java /** * Atomically updates Java variable to {@code x} if it is currently * holding {@code expected}. * * <p>This operation has memory semantics of a {@code volatile} read * and write. Corresponds to C11 atomic_compare_exchange_strong. * * @return {@code true} if successful */ @HotSpotIntrinsicCandidate public final native boolean compareAndSetInt(Object o, long offset, int expected, int x);

該方法並沒有具體Java程式碼實現,方法通過native關鍵字修飾。由於Java方法無法直接訪問底層系統,Unsafe類相當於一個後門,可以通過該類的方法直接操作特定記憶體的資料。Unsafe類存在於sun.msic包中,JVM會幫我們實現出相應的彙編指令Unsafe類中的CAS方法是一條CPU併發原語,由若干條指令組成,用於完成某個功能的一個過程。原語的執行必須是連續的,在執行過程中不允許被中斷,不會存在資料不一致的問題

getAndIncrement方法剖析

瞭解了CAS原理後,我們回頭看下AtomicIntegergetAndIncrement方法原始碼:

java /** * Atomically increments the current value, * with memory effects as specified by {@link VarHandle#getAndAdd}. * * <p>Equivalent to {@code getAndAdd(1)}. * * @return the previous value */ public final int getAndIncrement() { return U.getAndAddInt(this, VALUE, 1); }

該方法通過呼叫unsafe類的getAndAddInt方法實現相關功能。繼續檢視getAndAddInt方法的原始碼:

java /** * Atomically adds the given value to the current value of a field * or array element within the given object {@code o} * at the given {@code offset}. * * @param o object/array to update the field/element in * @param offset field/element offset * @param delta the value to add * @return the previous value * @since 1.8 */ @HotSpotIntrinsicCandidate public final int getAndAddInt(Object o, long offset, int delta) { int v; do { v = getIntVolatile(o, offset); } while (!weakCompareAndSetInt(o, offset, v, v + delta)); return v; }

結合原始碼,我們便可以很直觀地看出為什麼AtomicIntegergetAndIncrement方法是執行緒安全的了:

oAtomicInteger物件本身;offsetAtomicInteger物件的成員變數value的記憶體地址;delta是需要變更的數量;v是通過unsafegetIntVolatile方法獲得AtomicInteger物件的成員變數value在主記憶體中的值。do while迴圈中的邏輯為:用當前物件的值和var5比較,如果相同,說明該值沒有被別的執行緒修改過,更新為v + delta,並返回true(CAS);否則繼續獲取值並比較,直到更新完成。

CAS的缺點

CAS並不是完美的,其存在以下這些缺點:

  1. 如果剛好while裡的CAS操作一直不成功,那麼對CPU的開銷大;
  2. 只能確保一個共享變數的原子操作;
  3. 存在ABA問題。

CAS實現的一個重要前提是需要取出某一時刻的資料並在當下時刻比較交換,這之間的時間差會導致資料的變化。比如:thread1執行緒從主記憶體中取出了變數a的值為A,thread2頁從主記憶體中取出了變數a的值為A。由於執行緒排程的不確定性,這時候thread1可能被短暫掛起了,thread2進行了一些操作將值修改為了B,然後又進行了一些操作將值修改回了A,這時候當thread1重新獲取CPU時間片重新執行CAS操作時,會發現變數a在主記憶體中的值仍然是A,所以CAS操作成功。

解決ABA問題

那麼如何解決CAS的ABA問題呢?由上面的闡述課件,光通過判斷值是否相等並不能確保在一定時間差內值沒有變更過,所以我們需要一個額外的指標來輔助判斷,類似於時間戳,版本號等。

JUC為我們提供了一個AtomicStampedReference類,通過檢視它的構造方法就可以看出,除了指定初始值外,還需指定一個版本號(戳):

java /** * Creates a new {@code AtomicStampedReference} with the given * initial values. * * @param initialRef the initial reference * @param initialStamp the initial stamp */ public AtomicStampedReference(V initialRef, int initialStamp) { pair = Pair.of(initialRef, initialStamp); }

我們就用這個類來解決ABA問題,首先模擬一個ABA問題場景:

```java public class AtomticIntegerTest { public static void main(String[] args) { AtomicReference atomicReference = new AtomicReference<>("A");

    new Thread(() -> {
        // 模擬一次ABA操作
        atomicReference.compareAndSet("A", "B");
        atomicReference.compareAndSet("B", "A");
        System.out.println(Thread.currentThread().getName() + "執行緒完成了一次ABA操作");
    }, "thread1").start();

    new Thread(() -> {
        // 讓thread2先睡眠2秒鐘,確保thread1的ABA操作完成
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        boolean result = atomicReference.compareAndSet("A", "B");
        if (result) {
            System.out.println(Thread.currentThread().getName() + "執行緒修改值成功,當前值為:" + atomicReference.get());
        }
    }, "thread2").start();
}

} ```

執行程式,輸出如下:

image-20211007134923854.png

使用AtomicStampedReference解決ABA問題:

```java public class AtomticIntegerTest { public static void main(String[] args) { // 初始值為A,版本號為1 AtomicStampedReference reference = new AtomicStampedReference<>("A", 1);

    new Thread(() -> {
        int stamp = reference.getStamp();
        System.out.println(Thread.currentThread().getName() + "當前版本號為:" + stamp);
        // 休眠1秒,讓thread2也拿到初始的版本號
        try {
            TimeUnit.SECONDS.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        // 模擬一次ABA操作
        reference.compareAndSet("A", "B", reference.getStamp(), reference.getStamp() + 1);
        reference.compareAndSet("B", "A", reference.getStamp(), reference.getStamp() + 1);
        System.out.println(Thread.currentThread().getName() + "執行緒完成了一次ABA操作");
    }, "thread1").start();

    new Thread(() -> {
        int stamp = reference.getStamp();
        System.out.println(Thread.currentThread().getName() + "當前版本號為:" + stamp);
        // 讓thread2先睡眠2秒鐘,確保thread1的ABA操作完成
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        boolean result = reference.compareAndSet("A", "B", stamp, stamp + 1);
        if (result) {
            System.out.println(Thread.currentThread().getName() + "執行緒修改值成功,當前值為:" + reference.getReference());
        } else {
            System.out.println(Thread.currentThread().getName() + "執行緒修改值失敗,當前值為:" + reference.getReference() + ",版本號為:" + reference.getStamp());
        }
    }, "thread2").start();
}

} ``` 程式輸出如下:

image-20211007135008069.png