CAS中的ABA问题解决方案

CAS

CAS:Compare and Swap, 翻译成比较并交换。
java.util.concurrent包中借助CAS实现了区别于synchronized同步锁的一种乐观锁。
其原理是CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。

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

ABA问题

    private static AtomicInteger atomicInt = new AtomicInteger(100);
    public static void main(String[] args) throws InterruptedException {
        Thread intT1 = new Thread(new Runnable() {
            @Override
            public void run() {
                atomicInt.compareAndSet(100, 101);
                log("thread intT1:" + atomicInt.get());
                atomicInt.compareAndSet(101, 100);
                log("thread intT1:" + atomicInt.get());
            }
        });

        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);
                log("thread intT2:" + atomicInt.get() + ",c3 is:" + c3);        //true
            }
        });

        intT1.start();
        intT2.start();

上面程序的打印结果如下：

thread intT1:101
thread intT1:100
thread intT2:101,c3 is:true

线程intT2获取到的变量值A，尽管和当前的实际值相同，但内存地址V中的变量已经经历了A->B->A的改变。实际应用中有可能会导致漫画：什么是CAS机制？（进阶篇）中所提到的提款问题。

解决方案

JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。如果当前引用 == 预期引用，并且当前标志等于预期标志，则以原子方式将该引用和该标志的值设置为给定的更新值。源码如下：

/**
 *expectedReference - 该引用的预期值
 *newReference - 该引用的新值
 *expectedStamp - 该标志的预期值
 *newStamp - 该标志的新值
 */
public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
            expectedReference == current.reference &&
            expectedStamp == current.stamp &&
            ((newReference == current.reference &&
              newStamp == current.stamp) ||
             casPair(current, Pair.of(newReference, newStamp)));
    }

最佳实践

    private static AtomicStampedReference<Integer> atomicStampedRef =
            new AtomicStampedReference<Integer>(100, 0);

        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);
                log("thread refT1:" + atomicStampedRef.getReference());
                atomicStampedRef.compareAndSet(101, 100,
                        atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                log("thread refT1:" + atomicStampedRef.getReference());
            }
        });

        Thread refT2 = new Thread(new Runnable() {
            @Override
            public void run() {
                int stamp = atomicStampedRef.getStamp();
                log("before sleep : stamp = " + stamp);    // stamp = 0
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                log("after sleep : stamp = " + atomicStampedRef.getStamp());//stamp = 1
                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                log("thread refT2:" + atomicStampedRef.getReference() + ",c3 is " + c3);        //true
            }
        });

        refT1.start();
        refT2.start();
    }

    private static void log(String logString) {
        System.out.println(logString);
    }

输出结果如下：

before sleep : stamp = 0
thread refT1:101
thread refT1:100
after sleep : stamp = 2
thread refT2:100,c3 is false

可以看到refT2的值和expect是相同的，但是由于版本号发生了变化，所以更新失败。

漫画：什么是 CAS 机制？
漫画：什么是CAS机制？（进阶篇）
Java CAS 和ABA问题