CAS 算法與 Java 原子類

2020 年 10 月 23 日
筆記
Java 並發編程

樂觀鎖

一般而言，在並發情況下我們必須通過一定的手段來保證數據的準確性，如果沒有做好並發控制，就可能導致臟讀、幻讀和不可重複度等一系列問題。樂觀鎖是人們為了應付並發問題而提出的一種思想，具體的實現則有多種方式。

樂觀鎖假設數據一般情況下不會造成衝突，只在數據進行提交更新時，才會正式對數據的衝突與否進行檢測，如果發現衝突了，則返回給用戶錯誤的信息，讓用戶決定如何去做。樂觀鎖適用於讀操作多的場景，可以提高程序的吞吐量。

CAS

CAS（Compare And Swap）比較並交換，是一種實現了樂觀鎖思想的並發控制技術。CAS 算法的過程是：它包含 3 個參數 CAS（V，E，N），V 表示要更新的變量（內存值），E 表示舊的預期值，N 表示即將更新的預期值。當且僅當 V 值等於 E 值時，才會將 V 的值設為 N，如果 V 值和 E 值不同，說明已經有其他線程做了更新，則當前線程什麼也不做，並返回當前 V 的真實值。整個操作是原子性的。

當多個線程同時使用 CAS 操作一個變量時，只有一個會勝出，並成功更新，其餘均會失敗。失敗的線程不會被掛起，僅是被告知失敗，並允許再次嘗試，當然也可以放棄本次操作，所以 CAS 算法是非阻塞的。基於上述原理，CAS 操作可以在不藉助鎖的情況下實現合適的並發處理。

ABA 問題

ABA 問題是 CAS 算法的一個漏洞。CAS 算法實現的一個重要前提是：取出內存中某時刻的數據，並在下一時刻比較並替換，在這個時間差內可能會導致數據的變化。

假設有兩個線程，分別要對內存中某一變量做 CAS 操作，線程一先從內存中取出值 A，線程二也從內存中取出值 A，並把值從 A 變為 B 寫回，然後又把值從 B 變為 A 寫回，這時候線程一進行 CAS 操作，發現內存中的值還是 A，於是認為和預期值一致，操作成功。儘管線程一的 CAS 操作成功，但並不代表這個過程就沒有問題。

ABA 問題會帶來什麼隱患呢？維基百科給出了詳細的示例：假設現有一個用單鏈表實現的堆棧，棧頂為 A，A.next = B，現有線程一希望用 CAS 把棧頂替換為 B，但在此之前，線程二介入，將 A、B 出棧，再壓入 D、C、A，整個過程如下

此時 B 處於遊離轉態，輪到線程一執行 CAS 操作，發現棧頂仍為 A，CAS 成功，棧頂變為 B，但實際上 B.next = null，即堆棧中只有 B 一個元素，C 和 D 並不在堆棧中，平白無故就丟了。簡單來說，ABA 問題使我們漏掉某一段時間的數據監控，誰知道在這段時間內會發生什麼有趣（可怕）的事呢？

可以通過版本號的方式來解決 ABA 問題，每次執行數據修改操作時，都會帶上一個版本號，如果版本號和數據的版本一致，對數據進行修改操作並對版本號 +1，否則執行失敗。因為每次操作的版本號都會隨之增加，所以不用擔心出現 ABA 問題。

使用 Java 模擬 CAS 算法

這僅僅是基於 Java 層面上的模擬，真正的實現要涉及到底層（我學不會）

public class TestCompareAndSwap {

    private static CompareAndSwap cas = new CompareAndSwap();

    public static void main(String[] args) {

        for (int i = 0; i < 10; i++) {
            new Thread(new Runnable() {
                public void run() {
                    // 獲取預估值
                    int expectedValue = cas.get();
                    boolean b = cas.compareAndSet(expectedValue, (int) (Math.random() * 101));
                    System.out.println(b);
                }
            });
        }
    }
}

class CompareAndSwap {

    private int value;

    // 獲取內存值
    public synchronized int get() {
        return value;
    }

    // 比較
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        // 讀取內存值
        int oldValue = value;
        // 比較
        if (oldValue == expectedValue) {
            this.value = newValue;
        }
        return oldValue;
    }

    // 設置
    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return expectedValue == compareAndSwap(expectedValue, newValue);
    }
}

原子類

原子包 java.util.concurrent.atomic 提供了一組原子類，原子類的操作具有原子性，一旦開始，就一直運行直到結束，中間不會有任何線程上下文切換。原子類的底層正是基於 CAS 算法實現線程安全。

Java 為我們提供了十六個原子類，可以大致分為以下四種：

1. 基本類型

AtomicBoolean

原子更新布爾類型，內部使用 int 類型的 value 存儲 1 和 0 表示 true 和 false，底層也是對 int 類型的原子操作
AtomicInteger

原子更新 int 類型
AtomicLong

原子更新 long 類型

2. 引用類型

AtomicReference

原子更新引用類型，通過泛型指定要操作的類

AtomicMarkableReference

原子更新引用類型，內部維護一個 Pair 類型（靜態內部類）的成員屬性，其中有一個 boolean 類型的標誌位，避免 ABA 問題

private static class Pair<T> {
    final T reference;
    final boolean mark;
    private Pair(T reference, boolean mark) {
        this.reference = reference;
        this.mark = mark;
    }
    static <T> Pair<T> of(T reference, boolean mark) {
        return new Pair<T>(reference, mark);
    }
}

private volatile Pair<V> pair;

AtomicStampedReference

原子更新引用類型，內部維護一個 Pair 類型（靜態內部類）的成員屬性，其中有一個 int 類型的郵戳（版本號），避免 ABA 問題

private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
    static <T> Pair<T> of(T reference, int stamp) {
        return new Pair<T>(reference, stamp);
    }
}

private volatile Pair<V> pair;

3. 數組類型

AtomicIntegerArray

原子更新 int 數組中的元素
AtomicLongArray

原子更新 long 數組中的元素
AtomicReferenceArray

原子更新 Object 數組中的元素

4. 對象屬性類型

用於解決對象的屬性的原子操作

AtomicIntegerFieldUpdater

原子更新對象中的 int 類型字段
AtomicLongFieldUpdater

原子更新對象中的 long 類型字段
AtomicReferenceFieldUpdater

原子更新對象中的引用類型字段

之前提到的三種類型的使用都比較簡單，查閱對應 API 即可，而對象屬性類型則有一些限制：

字段必須是 volatile 類型的，在線程之間共享變量時保證立即可見
只能是實例變量，不能是類變量，也就是說不能加 static 關鍵字
只能是可修改變量，不能使用 final 變量
該對象字段能夠被直接操作，因為它是基於反射實現的

5. 高性能原子類

Java8 新增的原子類，使用分段的思想，把不同的線程 hash 到不同的段上去更新，最後再把這些段的值相加得到最終的值。以下四個類都繼承自 Striped64，對並發的優化在 Striped64 中實現

LongAccumulator

long 類型的聚合器，需要傳入一個 long 類型的二元操作，可以用來計算各種聚合操作，包括加乘等
LongAdder

long 類型的累加器，LongAccumulator 的特例，只能用來計算加法，且從 0 開始計算
DoubleAccumulator

double 類型的聚合器，需要傳入一個 double 類型的二元操作，可以用來計算各種聚合操作，包括加乘等
DoubleAdder

double 類型的累加器，DoubleAccumulator 的特例，只能用來計算加法，且從 0 開始計算

Tags: Java 並發編程