什么是 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，有几个关键的值：
- 要修改的变量内存中的值V
- 更新变量前事先记录的期望值E，取值来自V
- 将要更新的值A
一个典型的CAS更新操作如下：
- 读取内存中的值V，赋值给E
- 更新变量前，比较内存值V与E
- 如果V==E,将V更新成A
- 如果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要将数据从A变成B时（此时线程1的期待值E=='A'）
- 其他线程已经抢先更新了变量，把变量从A变成其他值，再变回A（如A->C->A）。
- 当线程1用CAS机制准备更新变量时，发现E==A，所以继续更新变量。
这样有什么问题？
虽然变量最终结果是对的，但是线程1更新变量前，变量已经经历了一系列变化才回到原值。对于某些场景，忽略变化会继续进行更新操作，会带来错误的结果。
比如：
比如：
银行账户扣费问题
某个银行账户扣款操作，由于系统故障，产生了2个线程（T1,T2）对同一账户进行扣款，正常防重逻辑应该是一个执行成功，另一个失败，但是如果使用上面的CAS操作，就是：
- 账户里有100元，需要扣款50元
- T1先完成操作，扣款50元，将账户值V改为50
- T2准备扣款，当时期待值E==100
- 此时有其他转账操作先于T2对V进行累加，比如转入50元，此时V又变成100
- T2进行CAS的更新操作，发现E==V==100,执行更新操作，又扣款50
堆栈操作问题
如果CAS中的操作，变量值V是栈顶指针，也会有同样的问题：
- 某个堆栈内容是：A-B-C,栈顶为A
- 线程1更新前，得到期望值E==A
- 其他线程对栈进行进行pop,push操作，pop A B,push D A,此时栈的内容为 A-D-C
- 此时栈顶还是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 } }
总结
- CAS 是一种自旋锁，由一个死循环+compareAndSet 实现。
- CAS 存在ABA隐患，对于需要关注竞争变量变化过程（不仅仅是变量的值）的场景，ABA问题必须关注。
- 解决ABA问题，需要在CAS的compare过程中，增加对期望值E和当前值V版本号的判断。
