Java中的CAS与ABA问题

今天面试别人的时候，提到了CAS，本来想要引导他说出CAS潜在的ABA问题，发现自己也没发简单的向他解释清楚,需要好好梳理下。

什么是 CAS

维基百科的解释是：

In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of that memory location to a new given value. This is done as a single atomic operation. The atomicity guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write would fail. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).

CAS(compare and swap)，简单地说就是一种在多线程的情况下，让每个线程修改某个数据是一种原子操作。要实现CAS，有几个关键的值：

1. 要修改的变量内存中的值V
2. 更新变量前事先记录的期望值E，取值来自V
3. 将要更新的值A

一个典型的CAS更新操作如下：

1. 读取内存中的值V，赋值给E
2. 更新变量前，比较内存值V与E
3. 如果V==E,将V更新成A
4. 如果V!=E，重复步骤1

如此循环，直到步骤3更新操作完成，写成伪代码就是：

do{
    int e=v.getVal();
    synchronized(this){
        if(e==getVal()){
            v.setVal(a);
            break;
        }
    }

}while(true)

CAS在JDK中被广泛应用，比如java.util.concurrent包下面的Lock、AtomicInteger相关的类都有用到。
例如a++;这种操作在Java里面并不是原子操作（包含了值的累加和赋值两个动作），所以并发情况下竞争操作某一个变量，需要用AtomicXXX几个类。

举个例子

AtomicInteger 实现类似a++操作，使用的是它的incrementAndGet 方法，源码很简单：

    /**
     * Atomically increments by one the current value.
     *
     * @return the updated value
     */
    public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            // 此处的 compareAndSet 由usafe对象提供硬件级别的原子操作
            if (compareAndSet(current, next))
                return next;
        }
    }

Lock中对于竞争变量的CAS，也是类似的操作。

什么是ABA问题

简单地说就是，多个线程同时使用CAS更新数据时：

1. 线程1要将数据从A变成B时（此时线程1的期待值E=='A'）
2. 其他线程已经抢先更新了变量，把变量从A变成其他值，再变回A（如A->C->A）。
3. 当线程1用CAS机制准备更新变量时，发现E==A，所以继续更新变量。

这样有什么问题？

虽然变量最终结果是对的，但是线程1更新变量前，变量已经经历了一系列变化才回到原值。对于某些场景，忽略变化会继续进行更新操作，会带来错误的结果。
比如：

银行账户扣费问题

某个银行账户扣款操作，由于系统故障，产生了2个线程（T1,T2）对同一账户进行扣款，正常防重逻辑应该是一个执行成功，另一个失败，但是如果使用上面的CAS操作，就是：

1. 账户里有100元，需要扣款50元
2. T1先完成操作，扣款50元，将账户值V改为50
3. T2准备扣款，当时期待值E==100
4. 此时有其他转账操作先于T2对V进行累加，比如转入50元，此时V又变成100
5. T2进行CAS的更新操作，发现E==V==100,执行更新操作，又扣款50

堆栈操作问题

如果CAS中的操作，变量值V是栈顶指针，也会有同样的问题：

1. 某个堆栈内容是：A-B-C,栈顶为A
2. 线程1更新前，得到期望值E==A
3. 其他线程对栈进行进行pop,push操作，pop A B,push D A,此时栈的内容为 A-D-C
4. 此时栈顶还是A，但是内容已经改变，线程1要更新的堆栈，已经不是第2步拿到期望值E时，自己要操作的那个堆栈了

如何规避

思路也很简单，就是对得到的期望值E和变量值V，增加一个版本号（比如时间戳），对于不同时期操作产生的同一个值的V，版本号是不同的，比较E与V时，需要同时比较版本号。比如juc包的AtomicStampedReference实现：

public class AtomicStampedReference<V> {
    private static class Pair<T> {
        final T reference;  //维护对象引用
        final int stamp;  //用于标志版本
        private Pair(T reference, int stamp) {
            this.reference = reference;
            this.stamp = stamp;
        }
        static <T> Pair<T> of(T reference, int stamp) {
            return new Pair<T>(reference, stamp);
        }
    }
    private volatile Pair<V> pair;
    ....
    /**
      * expectedReference ：更新之前的原始值
      * newReference : 将要更新的新值
      * expectedStamp : 期待更新的标志版本
      * newStamp : 将要更新的标志版本
      */
    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair; //获取当前pair
        return
            expectedReference == current.reference && //原始值等于当前pair的值引用，说明值未变化
            expectedStamp == current.stamp && // 原始标记版本等于当前pair的标记版本，说明标记未变化
            ((newReference == current.reference &&
              newStamp == current.stamp) || // 将要更新的值和标记都没有变化
             casPair(current, Pair.of(newReference, newStamp))); // cas 更新pair
    }
}    

总结

1. CAS 是一种自旋锁，由一个死循环+compareAndSet 实现。
2. CAS 存在ABA隐患，对于需要关注竞争变量变化过程（不仅仅是变量的值）的场景，ABA问题必须关注。
3. 解决ABA问题，需要在CAS的compare过程中，增加对期望值E和当前值V版本号的判断。