CAS

CAS, 全称是 Compare-and-swap, 是多线程同步的一种原子操作.
它把预期值 E(expected memory value) 和内存中的 M(memory value) 进行比较,
如果没其他线程修改 M, 那么 E 和 M 将是相同的 (Compare), 然后可将 M 修改为 N (new value),
这是一个原子操作. 如果更改的同时, M 被其他线程修改了, M 和 E 一般来说不相同, 那么修改就会失败.

CAS 操作基于 CPU提供的原子操作 指令实现(现在几乎所有的CPU指令都支持 CAS 的原子操作，
X86下对应的是 CMPXCHG 汇编指令), 这是保证数据一致的根本,
也是 Java concurrent 包并发机制的基础之一, 使用上 CAS 常被用于实现无锁队列.

从CAS的机制可以发现, 这和乐观锁很相似, 它假设在它修改之前，没有其它线程修改它,
直到提交的时候才进行检查；而synchronized是一种悲观的策略, 它假设会有线程同时修改它,
因此一开始就锁定, 无论是否真的有线程修改它, 因此性能比较低.

以 AtomicInteger 为例 :

这里使用的是 Jdk 8:

// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();

public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}


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

这两个方法的实现要看 openjdk8 中的sun.misc.Unsafe.java :

public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!compareAndSwapInt(o, offset, v, v + delta));
    return v;
}


public final native boolean compareAndSwapInt(java.lang.Object o, long l, int i, int i1);

可知, 底层还是依赖 native 方法 compareAndSwapInt(), 进行 CAS 的操作,
因此这个方法在 concurrent 和 locks 包中被大量使用.

ABA 问题

CAS很好, 不过也存在一个 ABA问题, 简单来说就是:

一个进程P1读取值的时候是 A
然后因为一些原因被挂起(时间片耗尽、中断等)
另一个进程 P2 把 A 改成了 B, 然后又改回了 A
P1被唤醒, 发现值仍然是A, 没有变化, 于是继续执行

这个在某些场景下, 可能不会影响正确结果. 但是, 比如在设计一个队列时,
地址重用机制 将可能导致top指针异常错乱和误修改next元素. 这里有个案例

wikipedia给出的一种解决方法是增加引用计数或者 timeStamp (如Java的AtomicStampedReference).

参考

https://en.wikipedia.org/wiki/Compare-and-swap
http://coolshell.cn/articles/8239.html
http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/sun/misc/Unsafe.java
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.53.8674&rep=rep1&type=pdf
http://www.ibm.com/developerworks/cn/aix/library/au-multithreaded_structures2/index.html
http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html