荐 Java并发技术总结之四——CAS

接上篇《Java并发技术总结之三——线程状态》

四. CAS 原理

参考地址：
《JAVA并发编程: CAS和AQS》
《面试必问的CAS，你懂了吗？》

CAS (Compare And Swap)，即比较并交换，是解决多线程并行情况下使用锁造成性能损耗的一种机制。在 JAVA 中，sun.misc.Unsafe 类提供了硬件级别的原子操作来实现 CAS。 java.util.concurrent 包下的大量类 (AtomicInteger, AtomicBoolean, AtomicLong, … )都使用了这个 Unsafe.java 类的 CAS 操作。至于 Unsafe.java 的具体实现这里就不讨论了。
CAS 本身是一种乐观锁的实现方式，在 Java 中的运用很多：

1. AQS：作为 ReentrantLock, CountDownLatch 等锁的底层基础；
   • 它的乐观锁实现方式，体现在入队时反复执行 CAS 操作，直到 CAS 操作成功，即入队成功；
   • CAS 与 AQS 的关系与区别：
     • CAS 是一种解决并发问题的思想，也就是先比较后替换，JUC 通过自旋执行 CAS 操作实现线程安全的状态更新。
     • AQS 是 Java 并发包的一个底层框架，是可重入锁 (ReentrantLock) 与共享锁（比如 CountDownLatch, CyclicBarrier 等）的基础。关于 Lock 与 AQS，Lock 面向用户，AQS 面向 Lock，也就是说 AQS 为各种 Lock 提供了底层的支持，AQS 的最核心原理之一就是利用 CAS 更新同步状态。
2. Atomit 类：一系列原子类，底层都是使用 CAS 操作；
3. 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 仍然有三个缺点：

1. 循环时间开销大
   • 从 getAndAddInt() 源码中可以看到，如果 CAS 执行返回 false，那么会一直执行尝试，如果 CAS 长时间不成功，可能会有比较大的 CPU 资源开销；
2. 只保证一个共享变量原子操作
   • 对于多个共享变量，无法使用 CAS 方式保证操作原子性，此时应该使用锁 (synchronized, Lock) 保证原子性；
3. ABA 问题
   • ABA 问题：如果内存地址 V 上的值在读取时为 A，准备赋值的时候检查它的值也为 A，但也不能保证在这期间没有被其他线程改变过；
   • 在使用 CAS 之前要考虑好一致性的效果，是需要达到最终一致性，还是完全一致性。如果需要解决 ABA 问题，Java 中提供了 AtomicStampedReference / AtomicMarkableReference 来处理会发生 ABA 问题的场景，它们的主要思想是在对象中额外再增加一个版本号的标记，标识对象是否有过变更；此外也可以改用传统互斥同步。
4. 不适用于高并发场景

本文地址：https://blog.csdn.net/ajianyingxiaoqinghan/article/details/107327755