面试官：什么是CAS？存在什么问题？

大家好，我是大明哥，一个专注「死磕 Java」系列创作的硬核程序员。

回答

CAS，Compare And Swap，即比较并交换，它一种无锁编程技术的核心机制。其工作方式分为两步：

1. 比较：它首先会比较内存中的某个值（V）与预期的值（A）是否相等。
2. **交换：**如果相等，那么会自动将该值（V）更新为新值（B）。如果不相等，不做任何操作。

这个过程是原子操作，保证在并发环境中的数据一致性和线程安全。

CAS 主要存在如下三个问题：

1. ABA 问题：如果变量 V 的值原先是 A，然后被其他线程改为 B，然后又改回 A，这时CAS操作会误认为自从上次读取以来 V 没有被修改过，从而可能产生错误的操作结果。
2. 循环时间过长问题：CAS操作如果长时间不成功，会不断进行重试，这可能会导致线程长时间处于忙等（Busy-Wait）状态，从而导致 CPU 长时间做无效操作。
3. 多变量原子问题：CAS 只能保证一个变量的原子操作。

详解

CAS 详解

CAS，Compare And Swap，即比较并交换。Doug lea大神在同步组件中大量使用 CAS 技术鬼斧神工地实现了Java多线程的并发操作。整个 AQS 同步组件、Atomic 原子类操作等等都是基于 CAS 实现的，可以说CAS 是整个 JUC 的基石。

在CAS中有三个参数：内存值 V、旧的预期值 A以及要更新的值 B。它涉及两个操作：

1. 比较：首先比较内存位置的当前值 V 和预期原值 A 是否相等，即 V == A ？
2. 交换：如果相等则将该位置值更新为新值，即 set B → V

用伪代码表示：

if(this.value == A){
    this.value = B
    return true;
}else{
     return false;
}

流程图如下：

CAS 存在的问题

CAS 主要存在如下三个问题：

1. ABA 问题：如果变量 V 的值原先是 A，然后被其他线程改为 B，然后又改回 A，这时CAS操作会误认为自从上次读取以来 V 没有被修改过，从而可能产生错误的操作结果。
2. 循环时间过长问题：CAS操作如果长时间不成功，会不断进行重试，这可能会导致线程长时间处于忙等（Busy-Wait）状态，从而导致 CPU 长时间做无效操作。
3. 多变量原子问题：CAS 只能保证一个变量的原子操作。

ABA 问题

CAS 需要检查操作值有没有发生改变，如果没有发生改变则更新。但是存在这样一种情况：一个变量原来的值为 A，后来被某个线程改为 B，再后来又被改回 A。在这种情况下，使用 CAS 进行比较时，会发现变量的值仍然为 A，从而认为这个变量没有被修改过，导致CAS 操作会成功。然而，实际上这个变量经历了 A->B->A的变化，其状态已经发生了变化，可能会导致一些逻辑上的错误。

为了解决 ABA 问题，一种常用的方法是使用版本号，即每次更新变量时，除了改变变量的值，还会更新一个附加的版本号，这样，即使一个变量的值被改回原来的值，它的版本号也会不同。

Java 提供了AtomicStampedReference 来解决 ABA 问题。AtomicStampedReference通过包装[E,Integer] 的元组来对对象标记版本戳stamp，从而避免ABA问题。

AtomicStampedReference 内部有一个 Pair 内部类，它主要用于记录引用和版本戳信息（标识）：

    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);
        }
    }

Pair 是一个不可变对象，其所有属性全部定义为final：

• reference：即变量当前的值。
• stamp：版本号，每次变量更新时，版本号也会更新。

同时，Pair 对外提供一个of方法，该方法返回一个新建的Pari对象。

AtomicStampedReference 中对 Pair对象定义为volatile，保证多线程环境下的可见性。

AtomicStampedReference的compareAndSet()方法源码如下：

    public boolean compareAndSet(V   expectedReference,
                                 V   newReference,
                                 int expectedStamp,
                                 int newStamp) {
        Pair<V> current = pair;
        return
                expectedReference == current.reference &&
                        expectedStamp == current.stamp &&
                        ((newReference == current.reference &&
                                newStamp == current.stamp) ||
                                casPair(current, Pair.of(newReference, newStamp)));
    }

下面我们将通过一个例子可以可以看到AtomicStampedReference和AtomicInteger的区别。我们定义两个线程，线程1负责将100 —> 110 —> 100，线程2执行 100 —>120，看两者之间的区别。

public class CASTest {
    public static void main(String[] args) throws InterruptedException {

        //AtomicInteger
        AtomicInteger atomicInteger = new AtomicInteger(100);
        new Thread(() -> {
            System.out.println("线程 atomicInteger_01 开始执行...");
            atomicInteger.compareAndSet(100,110);
            atomicInteger.compareAndSet(110,100);
            System.out.println("线程 atomicInteger_01 已执行完成...");
        }).start();
        // 确保线程1先执行完成
        TimeUnit.SECONDS.sleep(2);

        new Thread(() -> {
            System.out.println("线程 atomicInteger_02 开始执行...");
            System.out.println("AtomicInteger:" + atomicInteger.compareAndSet(100,120));
        }).start();
        TimeUnit.SECONDS.sleep(2);
        System.out.println("========================");

        //AtomicStampedReference
        AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100,1);

        new Thread(() -> {
            System.out.println("线程 atomicStampedReference_01 开始执行...");
            int stamp = atomicStampedReference.getStamp();
            atomicStampedReference.compareAndSet(100, 110, stamp, stamp + 1);
            stamp = atomicStampedReference.getStamp();
            atomicStampedReference.compareAndSet(110, 100, stamp, stamp + 1);
            System.out.println("线程 atomicStampedReference_01 已执行完成...");
        }).start();

        TimeUnit.SECONDS.sleep(2);
        new Thread(() -> {
            int tempstamp = atomicStampedReference.getStamp();
            System.out.println("线程 atomicStampedReference_02 开始执行...");
            System.out.println("AtomicStampedReference:" +atomicStampedReference.compareAndSet(100,120,tempstamp,tempstamp + 1));
        }).start();
    }
}

执行结果：

这是一种正常的写法，我们将 int tempstamp = atomicStampedReference.getStamp(); 移到外面去：

public class CASTest {
    public static void main(String[] args) throws InterruptedException {
         //....

        //AtomicStampedReference
        AtomicStampedReference atomicStampedReference = new AtomicStampedReference(100,1);
        int tempstamp = atomicStampedReference.getStamp();
        //...

        TimeUnit.SECONDS.sleep(2);
        new Thread(() -> {
            System.out.println("线程 atomicStampedReference_02 开始执行...");
            System.out.println("AtomicStampedReference:" +atomicStampedReference.compareAndSet(100,120,tempstamp,tempstamp + 1));
        }).start();
    }
}

执行结果：

循环时间过长问题

CAS 如果长时间操作不成功，则会让 CPU 在那里空转，会增加 CPU 的消耗。针对这个问题我们一般通过减少失败次数和优化重试机制来实现。

1. 退避策略：在高并发情况下，如果 CAS 操作失败，我们不用立刻就重试，而是让线程暂时“退避”，比如休眠一段时间，这样可以减少竞争线程的数量。如果失败次数增加了，我们可以逐渐增加休眠时间，比如失败小于 10 次，休眠 500毫秒，10~20次休眠 1000 毫秒这样逐步递增。
2. 限制重试次数：不能让线程一直都在那里重试，我们可以设置一个阈值，超过这个阈值，线程可能需要放弃竞争这个资源，比如报个错之类的。
3. 自适应：为了应对更加复杂的场景，我们可以采用自适应的策略来动态调整退避时间或重试策略。比如，根据当前系统的负载、CAS 操作的成功率和失败次数等因素，动态调整策略参数。这种方式实现难度比较大，容易采坑。

最后，在一般情况下如果在高并发场景下，其实不是很建议使用 CAS，还不如直接使用锁来的直接，有可能效率会更高。

多变量原子问题

CAS 只能保证一个变量的原子操作。对于多个变量是无法做到原则操作的。我们一般有如下几种方案：

1. 使用锁：这是最直接的方案，直接放弃 CAS，采用锁机制来解决多变量原则问题。
2. 使用 AtomicReference：将多个变量封装成一个 Java 对象，然后使用 AtomicReference 对这个对象进行原子操作。