歡迎光臨
每天分享高質量文章

面試必問的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的正確性。

赞(0)

分享創造快樂