CAS和ABA問題

2019-11-08 03:08:28

字體：大中小

來源：轉載

供稿：網友

CAS

CAS全稱是CompareAndSwap，是一條CPU的原子指令，其作用是讓CPU經過比較后原子地更新某個位置的值，CAS是靠硬件實現的，JVM只是封裝了匯編調用，那些AtomicInteger類便是使用了封裝匯編的接口。

我們知道synchronized是一種悲觀鎖，它使得其它需要鎖的線程掛起，等待持有鎖的線程釋放鎖。而樂觀鎖卻不加鎖，它假設沒有沖突去完成某項操作，如果沖突失敗就重試，直到成功為止。樂觀鎖用到的機制就是CAS，Compare and Swap。

以java.util.concurrent.atomic.AtomicInteger為例，我們看一下在沒有鎖的情況下是如何做到數據一致的。

PRivate volatile int value; public final int get() { return value; } public final int incrementAndGet() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return next; } } public final boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); }

incrementAndGet方法每次從內存中獲取value和+1后的結果next，再進行CAS操作，即將value值和最新內存值進行比較。如果一致就更新next，否則重試直到成功為止。

ABA問題

運用CAS做Lock-Free操作存在著一個經典的ABA問題：

這里寫圖片描述 (1) 現有一個用單向鏈表實現的堆棧，棧頂為A。這時線程T1已經知道A.next為B，然后希望用CAS將棧頂替換為B：

head.compareAndSet(A,B);

(2) 在T1執行上面這條指令之前，線程T2介入，將A、B出棧，再依次入棧D、C、A，而對象B此時處于游離狀態。

(3) 此時輪到線程T1執行CAS操作，檢測發現棧頂仍為A，所以CAS成功，棧頂變為B。但實際上B.next為null，此時堆棧中只有B一個元素，C和D組成的鏈表不再存在于堆棧中，C、D被丟掉了。

以上就是由于ABA問題帶來的隱患，各種樂觀鎖的實現中通常都會用版本戳version來對記錄或對象標記，避免并發操作帶來的問題。在Java中，AtomicStampedReference也實現了這個作用，它通過包裝[E,Integer]的元組來對對象標記版本戳stamp，從而避免ABA問題。例如下面的代碼分別用AtomicInteger和AtomicStampedReference來對初始值為100的原子整型變量進行更新，AtomicInteger會成功執行CAS操作，而加上版本戳的AtomicStampedReference對于ABA問題會執行CAS失敗：

public class ABA { private static AtomicInteger atomicInt = new AtomicInteger(100); private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<Integer>(100, 0); public static void main(String[] args) throws InterruptedException { Thread intT1 = new Thread(new Runnable() { @Override public void run() { atomicInt.compareAndSet(100, 101); atomicInt.compareAndSet(101, 100); } }); Thread intT2 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } boolean c3 = atomicInt.compareAndSet(100, 101); System.out.println(c3); //true } }); intT1.start(); intT2.start(); intT1.join(); intT2.join(); Thread refT1 = new Thread(new Runnable() { @Override public void run() { try { TimeUnit.SECONDS.sleep(1); } catch (InterruptedException e) { e.printStackTrace(); } atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1); atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1); } }); Thread refT2 = new Thread(new Runnable() { @Override public void run() { int stamp = atomicStampedRef.getStamp(); System.out.println("before sleep : stamp = " + stamp); // stamp = 0 try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("after sleep : stamp = " + atomicStampedRef.getStamp());//stamp = 1 boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1); System.out.println(c3); //false } }); refT1.start(); refT2.start(); }}

運行結果：這里寫圖片描述