Java并发技术总结之四——CAS
四. CAS 原理
CAS (Compare And Swap)，即比较并交换，是解决多线程并行情况下使用锁造成性能损耗的一种机制。在 JAVA 中，sun.misc.Unsafe 类提供了硬件级别的原子操作来实现 CAS。 java.util.concurrent 包下的大量类 (AtomicInteger, AtomicBoolean, AtomicLong, … )都使用了这个 Unsafe.java 类的 CAS 操作。至于 Unsafe.java 的具体实现这里就不讨论了。
CAS 本身是一种乐观锁的实现方式，在 Java 中的运用很多：
- AQS：作为 ReentrantLock, CountDownLatch 等锁的底层基础；
- 它的乐观锁实现方式，体现在入队时反复执行 CAS 操作，直到 CAS 操作成功，即入队成功；
- CAS 与 AQS 的关系与区别：
- CAS 是一种解决并发问题的思想，也就是先比较后替换，JUC 通过自旋执行 CAS 操作实现线程安全的状态更新。
- AQS 是 Java 并发包的一个底层框架，是可重入锁 (ReentrantLock) 与共享锁（比如 CountDownLatch, CyclicBarrier 等）的基础。关于 Lock 与 AQS，Lock 面向用户，AQS 面向 Lock，也就是说 AQS 为各种 Lock 提供了底层的支持，AQS 的最核心原理之一就是利用 CAS 更新同步状态。
- Atomit 类：一系列原子类，底层都是使用 CAS 操作；
- ConcurrentHashMap：1.7 -> 1.8 的优化，使用 CAS 替代了 1.7 版本的 ReentrantLock；
- 见 《数据结构与算法》篇第一章
下面以 AtomicInteger.java 的部分实现来大致讲解下这些原子类的实现。
注：CAS 与 AQS 的关系与区别： CAS 是一种解决并发问题的思想，也就是先比较后替换，JUC 通过自旋执行 CAS 操作实现线程安全的状态更新。 AQS 是 Java 并发包的一个底层框架，是可重入锁 (ReentrantLock) 与共享锁（比如 CountDownLatch, CyclicBarrier 等）的基础。关于 Lock 与 AQS，Lock 面向用户，AQS 面向 Lock，也就是说 AQS 为各种 Lock 提供了底层的支持，AQS 的最核心原理之一就是利用 CAS 更新同步状态。
public class AtomicInteger extends Number implements java.io.Serializable {
private static final long serialVersionUID = 6214790243416807050L;
// setup to use Unsafe.compareAndSwapInt for updates
private static final Unsafe unsafe = Unsafe.getUnsafe();
// 初始 int 大小
private volatile int value;
// 省略了部分代码...
// 返回旧值，并设置新值为 newValue
public final int getAndSet(int newValue) {
/**
* 这里使用 for 循环不断通过 CAS 操作来设置新值
* CAS 实现和加锁实现的关系有点类似乐观锁和悲观锁的关系
*/
for (;;) {
int current = get();
if (compareAndSet(current, newValue))
return current;
}
}
// 原子的设置新值为 update, expect 为期望的当前的值
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
// 获取当前值 current，并设置新值为 current+1
public final int getAndIncrement() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return current;
}
}
// 此处省略部分代码，余下的代码大致实现原理都是类似的
}核心系列方法 compareAndSet 包含三个操作数——内存位置 (V)、预期原值 (A) 和新值 (B)。CAS 有效地说明了“我认为位置 V 应该包含值 A；如果包含该值，则将 B 放到这个位置；否则不做任何更改，只告诉我这个位置现在的值即可。无论哪种情况，它都会在 CAS 指令之前返回该位置的值。
在竞争不是特别激烈的时候，使用该包下的原子操作性能比使用 synchronized 关键字的方式高效的多（查看 getAndSet(int newValue) 源码，可知如果资源竞争十分激烈的话，这个 for 循环可能换持续很久都不能成功跳出。不过这种情况更应该考虑降低资源竞争)。
注：通常使用 AtomicInteger，会用到它的
getAndIncrement()方法作计数器。
CAS 最主要的运用，就是在 JUC 中的 AbstractQueuedSynchronizer，即 AQS，它是 Java 中多种锁实现的父类。该类核心同步队列的入队操作是一种乐观锁实现，多线程情况下对头节点、尾节点操作都有可能失效，失效后 CAS 会再次尝试，直到尝试成功。比如 AbstractQueuedSynchronizer # enq(Node node) 方法：
private Node enq(final Node node) {
for (;;) {
Node t = tail;
if (t == null) { // Must initialize
if (compareAndSetHead(new Node()))
tail = head;
} else {
node.prev = t;
if (compareAndSetTail(t, node)) {
t.next = node;
return t;
}
}
}
}此外，CAS 仍然有三个缺点：
- 循环时间开销大
- 从
getAndAddInt()源码中可以看到，如果 CAS 执行返回 false，那么会一直执行尝试，如果 CAS 长时间不成功，可能会有比较大的 CPU 资源开销；
- 从
- 只保证一个共享变量原子操作
- 对于多个共享变量，无法使用 CAS 方式保证操作原子性，此时应该使用锁 (synchronized, Lock) 保证原子性；
- ABA 问题
- ABA 问题：如果内存地址 V 上的值在读取时为 A，准备赋值的时候检查它的值也为 A，但也不能保证在这期间没有被其他线程改变过；
- 在使用 CAS 之前要考虑好一致性的效果，是需要达到最终一致性，还是完全一致性。如果需要解决 ABA 问题，Java 中提供了
AtomicStampedReference/AtomicMarkableReference来处理会发生 ABA 问题的场景，它们的主要思想是在对象中额外再增加一个版本号的标记，标识对象是否有过变更；此外也可以改用传统互斥同步。
- 不适用于高并发场景