【原創】Java並發編程系列12 | 揭秘CAS

2020 年 3 月 13 日
筆記

並發編程，為了保證數據的安全，需要滿足三個特性：原子性、可見性、有序性。Java 中可以通過鎖和 CAS 的方式來實現原子操作。

前面 synchronized 的文章中介紹過，synchronized 是一個重量級操作，性能較差，CAS 在保證原子性中有較好的性能。此外，synchronized 的優化中，偏向鎖、輕量級鎖也都用的到了 CAS。

那麼，CAS 到底是什麼？今天就來揭秘一下：

CAS 是什麼？為什麼要用到 CAS？
如何使用 CAS 解決原子性問題？
CAS 原子操作的原理？
CAS 有哪些問題？
Java 中利用 CAS 的原子操作有哪些，如何使用？

1. CAS 介紹

CAS，Compare And Swap，即比較並交換。Doug lea 大神在同步組件中大量使用 CAS 技術鬼斧神工地實現了 Java 多執行緒的並發操作。整個 AQS 同步組件、Atomic 原子類操作等等都是以 CAS 實現的。可以說 CAS 是整個 J.U.C 的基石。

CAS 比較交換的過程 CAS(V,A,B)： V-一個記憶體地址存放的實際值、A-舊的預期值、B-即將更新的值，當且僅當預期值 A 和記憶體值 V 相同時，將記憶體值修改為 B 並返回 true，否則什麼都不做，並返回 false。

CAS VS synchronized

synchronized 是執行緒獲取鎖是一種悲觀鎖策略，即假設每一次執行臨界區程式碼都會產生衝突，所以當前執行緒獲取到鎖的之後會阻塞其他執行緒獲取該鎖。

CAS（無鎖操作）是一種樂觀鎖策略，它假設所有執行緒訪問共享資源的時候不會出現衝突，所以出現衝突時就不會阻塞其他執行緒的操作，而是重試當前操作直到沒有衝突為止。

2. 如何用 CAS 解決原子性問題

如下程式碼，目的是啟動 10 個執行緒，每個執行緒將 a 累加 1000 次，最終得到 a=10000。

public class CASTest {  	public int a = 0;    	public void increase() {  		a++;  	}    	public static void main(String[] args) {  		final CASTest test = new CASTest();  		for (int i = 0; i < 10; i++) {  			new Thread() {  				public void run() {  					for (int j = 0; j < 1000; j++)  						test.increase();  				};  			}.start();  		}    		while (Thread.activeCount() > 1) {  			// 保證前面的執行緒都執行完  			Thread.yield();  		}  		System.out.println(test.a);  	}  }

結果：每次運行結果都小於 10000。

原因分析：

當執行緒 1 將 a 加到 2 時，a=2 刷新到主記憶體；執行緒 2 執行增加運算時，到主記憶體讀取 a=2，此時執行緒 3 也要執行增加運算，也到主記憶體中讀取到 a=2；執行緒 2 和執行緒 3 執行的都是 a=2+1，將 a=3 刷新到主記憶體。相當於兩次加 1 運算只將 a 增加了 1，也就是說存在執行了多次加 1 運算卻只是將 a 增加 1 的情況，所以 10000 次加 1 運算，得到的結果會小於 10000。

原子性問題，解決方案 synchronized 和 CAS。

解決方案一：synchronized 加鎖

public synchronized void increase() {      a++;  }

通過 synchronized 加鎖之後，每次只能有一個執行緒訪問 increase()方法，能夠保證最終得到 10000。但是 synchronized 加鎖是個重量級操作，程式執行效率很低。

解決方案二：CAS

public AtomicInteger a = new AtomicInteger();  public void increase() {      a.getAndIncrement();  }

利用 CAS，保證 a=a+1 是原子性操作，最終得到結果 10000。

3. CAS 原理

探究 CAS 原理，其實就是探究上個例子中 a.getAndIncrement()如何保證 a=a+1 是原子性操作，先通過源碼看下。

AtomicInteger 類結構

public class AtomicInteger extends Number implements java.io.Serializable {      // setup to use Unsafe.compareAndSwapInt for updates      private static final Unsafe unsafe = Unsafe.getUnsafe();      private static final long valueOffset;        static {          try {              valueOffset = unsafe.objectFieldOffset                  (AtomicInteger.class.getDeclaredField("value"));          } catch (Exception ex) { throw new Error(ex); }      }        private volatile int value;  }

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

a.getAndIncrement()的實現如下

public final int getAndIncrement() {      return unsafe.getAndAddInt(this, valueOffset, 1);  }    public final int getAndAddInt(Object var1, long var2, int var4) {      int var5;      do {          var5 = this.getIntVolatile(var1, var2);      } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));      return var5;  }

getIntVolatile(var1, var2)：根據對象 var1 和對象中該變數地址 var2，獲取變數的值 var5。

this.compareAndSwapInt(var1, var2, var5, var5 + var4);：

根據對象 var1 和對象中該變數地址 var2 獲取變數當前的值 value
比較 value 跟 var5，如果 value==var5，則 value=var5+var4 並返回 true。這步操作就是比較和替換操作，是原子性的。
如果 value!=var5，則返回 false，再去自旋循環到下一次調用 compareAndSwapInt 方法。

可見，getAndIncrement()的原子性是通過 compareAndSwapInt()中的第二步比較和替換保證的，那麼 compareAndSwapInt()又是怎麼保證原子性的呢？

compareAndSwapInt 方法是 JNI（Java Native InterfaceJAVA 本地調用），java 通過 C 來調用 CPU 底層指令實現的。

compareAndSwapInt 方法中的比較替換操作之前插入一個 lock 前綴指令，這個指令能過確保後續操作的原子性。

lock 前綴指令確保後續指令執行的原子性：

在Pentium及之前的處理器中，帶有lock前綴的指令在執行期間會鎖住匯流排，使得其它處理器暫時無法通過匯流排訪問記憶體，很顯然，這個開銷很大。  在新的處理器中，Intel使用快取鎖定來保證指令執行的原子性，快取鎖定將大大降低lock前綴指令的執行開銷。

CPU 提供了兩種方法來實現多處理器的原子操作：匯流排加鎖和快取加鎖。

匯流排加鎖：匯流排加鎖就是就是使用處理器提供的一個 LOCK#訊號，當一個處理器在匯流排上輸出此訊號時，其他處理器的請求將被阻塞住，那麼該處理器可以獨佔使用共享記憶體。但是這種處理方式顯得有點兒霸道，不厚道，他把 CPU 和記憶體之間的通訊鎖住了，在鎖定期間，其他處理器都不能其他記憶體地址的數據，其開銷有點兒大。所以就有了快取加鎖。
快取加鎖：其實針對於上面那種情況我們只需要保證在同一時刻對某個記憶體地址的操作是原子性的即可。快取加鎖就是快取在記憶體區域的數據如果在加鎖期間，當它執行鎖操作寫回記憶體時，處理器不在輸出 LOCK#訊號，而是修改內部的記憶體地址，利用快取一致性協議來保證原子性。快取一致性機制可以保證同一個記憶體區域的數據僅能被一個處理器修改，也就是說當 CPU1 修改快取行中的 i 時使用快取鎖定，那麼 CPU2 就不能同時快取了 i 的快取行。

比較替換操作過程分析

假設執行緒 A 和執行緒 B 同時調用 a.getAndIncrement()–>getAndIncrement()–>getAndAddInt()，AtomicInteger 裡面的 value 原始值為 3，即主記憶體中 AtomicInteger 的 value 為 3，且執行緒 A 和執行緒 B 各自持有一份 value 的副本，值為 3。
執行緒 A 通過 getIntVolatile(var1, var2)拿到 value 值 3，執行緒 B 也通過 getIntVolatile(var1, var2)拿到 value 值 3，執行緒 A 和執行緒 B 同時調用 compareAndSwapInt()。
執行緒 A 執行 compareAndSwapInt()方法比較和替換時，其他 CPU 無法訪問該變數的記憶體，所以執行緒 B 不能進行比較替換。執行緒 A 成功修改記憶體值為 4，返回 true，執行結束。
執行緒 B 恢復，執行 compareAndSwapInt()方法比較和替換，發現記憶體的實際值 4 跟自己期望值 3 不一致，說明該值已經被其它執行緒提前修改過了，返回 false，自旋進入 while 循環，再通過 getIntVolatile(var1, var2)方法獲取 value 值 4，執行 compareAndSwapInt()比較替換，直到成功。

4. CAS 的問題

ABA 問題

CAS 需要檢查操作值有沒有發生改變，如果沒有發生改變則更新。但是存在這樣一種情況：如果一個值原來是 A，變成了 B，然後又變成了 A，那麼在 CAS 檢查的時候會認為沒有改變，但是實質上它已經發生了改變，這就是 ABA 問題。

解決方案可以沿襲資料庫中常用的樂觀鎖方式，添加一個版本號可以解決。原來的變化路徑 A->B->A 就變成了 1A->2B->3A。

在 java 1.5 後的 atomic 包中提供了 AtomicStampedReference 來解決 ABA 問題，解決思路就是這樣的。

自旋時間過長

使用 CAS 時非阻塞同步，也就是說不會將執行緒掛起，會自旋（無非就是一個死循環）進行下一次嘗試，如果自旋 CAS 長時間地不成功，則會給 CPU 帶來非常大的開銷。

優化：限制 CAS 自旋的次數，例如 BlockingQueue 的 SynchronousQueue。

只能保證一個共享變數的原子操作

當對一個共享變數執行操作時 CAS 能保證其原子性，如果對多個共享變數進行操作，CAS 就不能保證其原子性。

解決方案：把多個變數整成一個變數

利用對象整合多個共享變數，即一個類中的成員變數就是這幾個共享變數，然後將這個對象做 CAS 操作就可以保證其原子性。atomic 中提供了 AtomicReference 來保證引用對象之間的原子性。
利用變數的高低位，如 JDK 讀寫鎖 ReentrantReadWriteLock 的 state，高 16 位用於共享模式 ReadLock，低 16 位用於獨佔模式 WriteLock。

5. Java 中的原子操作類

在 J.U.C 下的 atomic 包提供了一系列原子操作類。

1）基本數據類型的原子操作類

AtomicInteger、AtomicLong、AtomicBoolean

以 AtomicInteger 為例總結一下常用的方法：

addAndGet(int delta) ：以原子方式將輸入的數值delta與實例中原本的值相加，並返回最後的結果；  incrementAndGet() ：以原子的方式將實例中的原值進行加1操作，並返回最終相加後的結果；  getAndSet(int newValue)：將實例中的值更新為新值newValue，並返回舊值；  getAndIncrement()：以原子的方式將實例中的原值加1，返回的是自增前的舊值；

用法：

public class AtomicDemo {      private static AtomicInteger atomicInteger = new AtomicInteger(1);        public static void main(String[] args) {          System.out.println(atomicInteger.getAndIncrement());          System.out.println(atomicInteger.get());      }  }

輸出結果：

1  2

2）數組類型的原子操作類

AtomicIntegerArray、AtomicLongArray、AtomicReferenceArray（引用類型數組）。

以 AtomicIntegerArray 來總結下常用的方法：

addAndGet(int i, int delta)：以原子更新的方式將數組中索引為i的元素與輸入值delta相加；  getAndIncrement(int i)：以原子更新的方式將數組中索引為i的元素自增加1；  compareAndSet(int i, int expect, int update)：將數組中索引為i的位置的元素進行更新；

用法：

AtomicIntegerArray 與 AtomicInteger 的方法基本一致，只不過在 AtomicIntegerArray 的方法中會多一個指定數組索引位 i。

通過 getAndAdd 方法將位置為 1 的元素加 5，從結果可以看出索引為 1 的元素變成了 7，該方法返回的也是相加之前的數為 2。

public class AtomicDemo {      private static int[] value = new int[]{1, 2, 3};      private static AtomicIntegerArray integerArray = new AtomicIntegerArray(value);        public static void main(String[] args) {          //對數組中索引為1的位置的元素加5          int result = integerArray.getAndAdd(1, 5);          System.out.println(integerArray.get(1));          System.out.println(result);      }  }

輸出結果：

7  2

3）引用類型的原子操作類

AtomicReference

用法：

public class AtomicDemo {        private static AtomicReference<User> reference = new AtomicReference<>();        public static void main(String[] args) {          User user1 = new User("a", 1);          reference.set(user1);          User user2 = new User("b",2);          User user = reference.getAndSet(user2);          System.out.println(user);          System.out.println(reference.get());      }        static class User {          private String userName;          private int age;            public User(String userName, int age) {              this.userName = userName;              this.age = age;          }            @Override          public String toString() {              return "User{" +                      "userName='" + userName + ''' +                      ", age=" + age +                      '}';          }      }  }

輸出結果：

User{userName='a', age=1}  User{userName='b', age=2}

4）欄位類型的原子操作類

如果需要更新對象的某個欄位，並在多執行緒的情況下，能夠保證執行緒安全，atomic 同樣也提供了相應的原子操作類：

AtomicIntegeFieldUpdater：原子更新整型欄位類；  AtomicLongFieldUpdater：原子更新長整型欄位類；  AtomicStampedReference：原子更新引用類型，這種更新方式會帶有版本號。解決CAS的ABA問題。

用法：

通過 AtomicIntegerFieldUpdater 的靜態方法 newUpdater 來創建一個更新器，並且需要設置想要更新的類和屬性；
更新類的屬性必須使用 public volatile 進行修飾；

public class AtomicDemo {        private static AtomicIntegerFieldUpdater updater = AtomicIntegerFieldUpdater.newUpdater(User.class,"age");      public static void main(String[] args) {          User user = new User("a", 1);          int oldValue = updater.getAndAdd(user, 5);          System.out.println(oldValue);          System.out.println(updater.get(user));      }        static class User {          private String userName;          public volatile int age;            public User(String userName, int age) {              this.userName = userName;              this.age = age;          }            @Override          public String toString() {              return "User{" +                      "userName='" + userName + ''' +                      ", age=" + age +                      '}';          }      }  }

輸出結果：

1  6

總結

CAS 即比較和替換，可以高效的解決原子性問題。

CAS 原子操作原理：使用一個期望值和一個變數的當前值進行比較，如果當前變數的值與我們期望的值相等，就使用一個新值替換當前變數的值。

Java 中的 CAS：atomic 包下原子操作類，如 AtomicInteger 常用於修飾共享變數來保證原子性。

參考資料

《Java 並發編程之美》
《Java 並發編程實戰》
《Java 並發編程的藝術》
技術和媒體實驗室-Java 並發和多執行緒教程: http://tutorials.jenkov.com/java-concurrency/index.html
The Java® Virtual Machine Specification: https://docs.oracle.com/javase/specs/jvms/se8/html