CAS 演算法與 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 = https://www.cnblogs.com/Yee-Q/archive/2020/10/23/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 開始計算

標籤：其他

上一篇：pytest-pyppeteer：在pytest中運行pyppeteer

下一篇：【C/C++】虛擬機實作：用C語言來寫Java虛擬機