Java CAS操作的ABA問(wèn)題

本文轉(zhuǎn)載至?ksfzhaohui?的?Java CAS操作的ABA問(wèn)題

1. CAS介紹

比較并交換(compare and swap, CAS)，是原子操作的一種，可用于在多線程編程中實(shí)現(xiàn)不被打斷的數(shù)據(jù)交換操作，從而避免多線程同時(shí)改寫(xiě)某一數(shù)據(jù)時(shí)由于執(zhí)行順序不確定性以及中斷的不可預(yù)知性產(chǎn)生的數(shù)據(jù)不一致問(wèn)題。

CAS操作基于CPU提供的原子操作指令實(shí)現(xiàn)，各個(gè)編譯器根據(jù)這個(gè)特點(diǎn)實(shí)現(xiàn)了各自的原子操作函數(shù)。來(lái)源維基百科：

C語(yǔ)言：由GNU提供了對(duì)應(yīng)的__sync系列函數(shù)完成原子操作。
Windows：通過(guò)WindowsAPI實(shí)現(xiàn)了InterLocked Functions。
C++ 11：STL提供了atomic系列函數(shù)。
JAVA：sun.misc.Unsafe提供了compareAndSwap系列函數(shù)。
C#：通過(guò)Interlocked方法實(shí)現(xiàn)。
Go：通過(guò)import "sync/atomic"包實(shí)現(xiàn)。

java.util.concurrent包完全建立在CAS之上的，借助CAS實(shí)現(xiàn)了區(qū)別于synchronouse同步鎖的一種樂(lè)觀鎖。
可以看一下AtomicInteger：

public final int getAndIncrement() {
     for (;;) {
         int current = get();
         int next = current + 1;
         if (compareAndSet(current, next))
             return current;
     }
}

public final boolean compareAndSet(int expect, int update) {
     return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

其中牽扯到3個(gè)值：current，next以及當(dāng)前內(nèi)存中的最新值，當(dāng)且僅當(dāng)current和內(nèi)存中的最新值相同時(shí)，才會(huì)改變內(nèi)存值為next。

2. CAS的ABA問(wèn)題

ABA問(wèn)題描述：

1. 進(jìn)程P1在共享變量中讀到值為A
2. P1被搶占了，進(jìn)程P2執(zhí)行
3. P2把共享變量里的值從A改成了B，再改回到A，此時(shí)被P1搶占。
4. P1回來(lái)看到共享變量里的值沒(méi)有被改變，于是繼續(xù)執(zhí)行。

雖然P1以為變量值沒(méi)有改變，繼續(xù)執(zhí)行了，但是這個(gè)會(huì)引發(fā)一些潛在的問(wèn)題。ABA問(wèn)題最容易發(fā)生在lock free的算法中的，CAS首當(dāng)其沖，因?yàn)镃AS判斷的是指針的地址。如果這個(gè)地址被重用了呢，問(wèn)題就很大了。（地址被重用是很經(jīng)常發(fā)生的，一個(gè)內(nèi)存分配后釋放了，再分配，很有可能還是原來(lái)的地址）。

ABA問(wèn)題解決方案
各種樂(lè)觀鎖的實(shí)現(xiàn)中通常都會(huì)用版本戳version?來(lái)對(duì)記錄或?qū)ο髽?biāo)記，避免并發(fā)操作帶來(lái)的問(wèn)題，在Java中，?AtomicStampedReference?也實(shí)現(xiàn)了這個(gè)作用，它通過(guò)包裝類?Pair[E,Integer]的元組來(lái)對(duì)對(duì)象標(biāo)記版本戳stamp，從而避免ABA問(wèn)題。

下面看一下AtomicInteger和AtomicStampedReference分別執(zhí)行CAS操作：

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABASingle {

    public static void main(String[] args) {
        AtomicInteger atomicInt = new AtomicInteger(100);
        atomicInt.compareAndSet(100, 101);
        atomicInt.compareAndSet(101, 100);
        System.out.println("new value = " + atomicInt.get());
        boolean result1 = atomicInt.compareAndSet(100, 101);
        System.out.println(result1); // result:true

        AtomicInteger v1 = new AtomicInteger(100);
        AtomicInteger v2 = new AtomicInteger(101);
        AtomicStampedReference<AtomicInteger> stampedRef = new AtomicStampedReference<AtomicInteger>(
                v1, 0);

        int stamp = stampedRef.getStamp();
        stampedRef.compareAndSet(v1, v2, stampedRef.getStamp(),
                stampedRef.getStamp() + 1);
        stampedRef.compareAndSet(v2, v1, stampedRef.getStamp(),
                stampedRef.getStamp() + 1);
        System.out.println("new value = " + stampedRef.getReference());
        boolean result2 = stampedRef.compareAndSet(v1, v2, stamp, stamp + 1);
        System.out.println(result2); // result:false
    }
}

AtomicInteger 執(zhí)行cas操作成功，AtomicStampedReference執(zhí)行cas操作失敗。

這樣是不是就是說(shuō)AtomicInteger存在ABA問(wèn)題，根本就不能用了；肯定是可以用的，AtomicInteger處理的一個(gè)數(shù)值，所有就算出現(xiàn)ABA問(wèn)題問(wèn)題，也不會(huì)有什么影響；但是如果這里是一個(gè)地址 （地址被重用是很經(jīng)常發(fā)生的，一個(gè)內(nèi)存分配后釋放了，再分配，很有可能還是原來(lái)的地址） ，比較地址發(fā)現(xiàn)沒(méi)有問(wèn)題，但其實(shí)這個(gè)對(duì)象早就變了，這時(shí)候就可以使用AtomicStampedReference來(lái)解決ABA問(wèn)題。