面試必問的CAS，瞭解多少？

前言

CAS（Compare and Swap），即比較並替換，實現併發演演算法時常用到的一種技術，Doug lea大神在java同步器中大量使用了CAS技術，鬼斧神工的實現了多執行緒執行的安全性。

CAS的思想很簡單：三個引數，一個當前記憶體值V、舊的預期值A、即將更新的值B，當且僅當預期值A和記憶體值V相同時，將記憶體值修改為B並傳回true，否則什麼都不做，並傳回false。

問題

一個n++的問題。

1. public class Case {
2.  
3.    public volatile int n;
4.  
5.    public void add() {
6.        n++;
7.    }
8. }

透過javap -verbose Case看看add方法的位元組碼指令

1. public void add();
2.    flags: ACC_PUBLIC
3.    Code:
4.      stack=3, locals=1, args_size=1
5.         0: aload_0      
6.         1: dup          
7.         2: getfield      #2                  // Field n:I
8.         5: iconst_1      
9.         6: iadd          
10.         7: putfield      #2                  // Field n:I
11.        10: return

n++被拆分成了幾個指令：

• 執行getfield拿到原始n；
• 執行iadd進行加1操作；
• 執行putfield寫把累加後的值寫回n；

透過volatile修飾的變數可以保證執行緒之間的可見性，但並不能保證這3個指令的原子執行，在多執行緒併發執行下，無法做到執行緒安全，得到正確的結果，那麼應該如何解決呢？

如何解決

在add方法加上synchronized修飾解決。

1. public class Case {
2.  
3.    public volatile int n;
4.  
5.    public synchronized void add() {
6.        n++;
7.    }
8. }

這個方案當然可行，但是效能上差了點，還有其它方案麼？

再來看一段程式碼

1. public int a = 1;
2. public boolean compareAndSwapInt(int b) {
3.    if (a == 1) {
4.        a = b;
5.        return true;
6.    }
7.    return f

如果這段程式碼在併發下執行，會發生什麼？

假設執行緒1和執行緒2都過了a==1的檢測，都準備執行對a進行賦值，結果就是兩個執行緒同時修改了變數a，顯然這種結果是無法符合預期的，無法確定a的最終值。

解決方法也同樣暴力，在compareAndSwapInt方法加鎖同步，變成一個原子操作，同一時刻只有一個執行緒才能修改變數a。

除了低效能的加鎖方案，我們還可以使用JDK自帶的CAS方案，在CAS中，比較和替換是一組原子操作，不會被外部打斷，且在效能上更佔有優勢。

下麵以AtomicInteger的實現為例，分析一下CAS是如何實現的。

1. public class AtomicInteger extends Number implements java.io.Serializable {
2.    // setup to use Unsafe.compareAndSwapInt for updates
3.    private static final Unsafe unsafe = Unsafe.getUnsafe();
4.    private static final long valueOffset;
5.  
6.    static {
7.        try {
8.            valueOffset = unsafe.objectFieldOffset
9.                (AtomicInteger.class.getDeclaredField("value"));
10.        } catch (Exception ex) { throw new Error(ex); }
11.    }
12.  
13.    private volatile int value;
14.    public final int get() {return value;}
15. }

1. Unsafe，是CAS的核心類，由於Java方法無法直接訪問底層系統，需要透過本地（native）方法來訪問，Unsafe相當於一個後門，基於該類可以直接操作特定記憶體的資料。
2. 變數valueOffset，表示該變數值在記憶體中的偏移地址，因為Unsafe就是根據記憶體偏移地址獲取資料的。
3. 變數value用volatile修飾，保證了多執行緒之間的記憶體可見性。 看看AtomicInteger如何實現併發下的累加操作：

1. public final int getAndAdd(int delta) {    
2.    return unsafe.getAndAddInt(this, valueOffset, delta);
3. }
4.  
5. //unsafe.getAndAddInt
6. public final int getAndAddInt(Object var1, long var2, int var4) {
7.    int var5;
8.    do {
9.        var5 = this.getIntVolatile(var1, var2);
10.    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
11.    return var5;
12. }

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

1. AtomicInteger裡面的value原始值為3，即主記憶體中AtomicInteger的value為3，根據Java記憶體模型，執行緒A和執行緒B各自持有一份value的副本，值為3。
2. 執行緒A透過getIntVolatile(var1, var2)拿到value值3，這時執行緒A被掛起。
3. 執行緒B也透過getIntVolatile(var1, var2)方法獲取到value值3，運氣好，執行緒B沒有被掛起，並執行compareAndSwapInt方法比較記憶體值也為3，成功修改記憶體值為2。
4. 這時執行緒A恢復，執行compareAndSwapInt方法比較，發現自己手裡的值(3)和記憶體的值(2)不一致，說明該值已經被其它執行緒提前修改過了，那隻能重新來一遍了。
5. 重新獲取value值，因為變數value被volatile修飾，所以其它執行緒對它的修改，執行緒A總是能夠看到，執行緒A繼續執行compareAndSwapInt進行比較替換，直到成功。

整個過程中，利用CAS保證了對於value的修改的併發安全，繼續深入看看Unsafe類中的compareAndSwapInt方法實現。

1. public final native boolean compareAndSwapInt(Object paramObject, long paramLong, int paramInt1, int paramInt2);

Unsafe類中的compareAndSwapInt，是一個本地方法，該方法的實現位於unsafe.cpp中

1. UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
2.  UnsafeWrapper("Unsafe_CompareAndSwapInt");
3.  oop p = JNIHandles::resolve(obj);
4.  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
5.  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
6. UNSAFE_END

1. 先想辦法拿到變數value在記憶體中的地址。
2. 透過Atomic::cmpxchg實現比較替換，其中引數x是即將更新的值，引數e是原記憶體的值。

如果是Linux的x86，Atomic::cmpxchg方法的實現如下：

1. inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
2.  int mp = os::is_MP();
3.  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
4.                    : "=a" (exchange_value)
5.                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
6.                    : "cc", "memory");
7.  return exchange_value;
8. }

看到這彙編，內心崩潰

__asm__ 表示彙編的開始 volatile 表示禁止編譯器最佳化 LOCKIFMP 是個行內函式

1. #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

Window的x86實現如下：

1. inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
2.    int mp = os::isMP(); //判斷是否是多處理器
3.    _asm {
4.        mov edx, dest
5.        mov ecx, exchange_value
6.        mov eax, compare_value
7.        LOCK_IF_MP(mp)
8.        cmpxchg dword ptr [edx], ecx
9.    }
10. }
11.  
12. // Adding a lock prefix to an instruction on MP machine
13. // VC++ doesn't like the lock prefix to be on a single line
14. // so we can't insert a label after the lock prefix.
15. // By emitting a lock prefix, we can define a label after it.
16. #define LOCK_IF_MP(mp) __asm cmp mp, 0  \
17.                       __asm je L0      \
18.                       __asm _emit 0xF0 \
19.                       __asm L0:

LOCKIFMP根據當前系統是否為多核處理器決定是否為cmpxchg指令新增lock字首。

• 如果是多處理器，為cmpxchg指令新增lock字首。
• 反之，就省略lock字首。（單處理器會不需要lock字首提供的記憶體屏障效果）

intel手冊對lock字首的說明如下：

• 確保後續指令執行的原子性。
• 在Pentium及之前的處理器中，帶有lock字首的指令在執行期間會鎖住匯流排，使得其它處理器暫時無法透過匯流排訪問記憶體，很顯然，這個開銷很大。在新的處理器中，Intel使用快取鎖定來保證指令執行的原子性，快取鎖定將大大降低lock字首指令的執行開銷。
• 禁止該指令與前面和後面的讀寫指令重排序。
• 把寫緩衝區的所有資料掃清到記憶體中。

上面的第2點和第3點所具有的記憶體屏障效果，保證了CAS同時具有volatile讀和volatile寫的記憶體語意。

CAS缺點

CAS存在一個很明顯的問題，即ABA問題。

問題：如果變數V初次讀取的時候是A，並且在準備賦值的時候檢查到它仍然是A，那能說明它的值沒有被其他執行緒修改過了嗎？

如果在這段期間曾經被改成B，然後又改回A，那CAS操作就會誤認為它從來沒有被修改過。針對這種情況，java併發包中提供了一個帶有標記的原子取用類AtomicStampedReference，它可以透過控制變數值的版本來保證CAS的正確性。