CAS 原理新讲 | 月光中的污点

一、什么是 CAS

CAS 全程 Compare-And-Swap，它的功能是判断内存中某个位置的值是否为预期值，如果是则更改为新值，这个过程是原子性的。

二、CAS 作用

CAS 是另一个无锁解决方案，更准确的是采用乐观锁技术，实现线程安全的问题。

三、CAS 实现原理

在设计思想上，CAS 的执行有三个操作数，V-内存值，A-期望值，B-修改成的目标值。当且仅当 V 的值等于 A 时， CAS 通过原子方式用新值 B 来更新 V 的值，否则不会执行任何操作。

CAS 是一条CPU 并发原语。即属于操作系统用语范畴，是由若干条指令组成，用于完成某种功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断。

JAVA 中的 CAS 操作通过调用 sun.misc.Unsafe 类中各个方法来实现。当调用 UnSafe 类中的 CAS 方法，JVM 会帮我们实现出 CAS 汇编指令。这是一种完全依赖与硬件的功能，通过它实现了原子操作。

四、实战演练

在 java.util.concurrent.atomic 包下提供了很多 AtomicXXX 原子性操作的类，它们底层封装了 UnSafe 类来提供 CAS 操作相关的方法，我们以 AtomicInteger 为例，执行 1000 的数字累加操作：

public class CASTest {

    private static int number = 0;

    private static AtomicInteger atomicNumber = new AtomicInteger(0);

    public static void main(String[] args) throws Exception {
        ExecutorService service = Executors.newCachedThreadPool();
        test1(service);
        test2(service);
        service.shutdown();
    }

    private static void test1(ExecutorService service) throws Exception {
        for (int i = 0; i < 1000; i++) {
            service.submit(() -> {
                number++;
            });
        }

        TimeUnit.SECONDS.sleep(2);
        System.out.println("number: " + number);
    }
    
    private static void test2(ExecutorService service) throws Exception {
        for (int i = 0; i < 1000; i++) {
            service.submit(() -> {
                atomicNumber.incrementAndGet();
            });
        }

        TimeUnit.SECONDS.sleep(2);
        System.out.println("atomicNumber: " + atomicNumber.get());
    }
}

执行结果：

1 2	number: 972 atomicNumber: 1000

案例中，我们声明了普通的静态变量 number 和原子类型的 atomicNumber，让它们在多线程下各执行 1000 次的数值累加。

由于 number ++ 编译成字节码是多行指令，并非原子操作，当多线程访问修改时，大概率有旧值覆盖新值的问题，因此出现累加 1000 次的操作后结果却小于 1000 的情况。

而 atomicNumber.incrementAndGet() 底层使用了 CAS，确保数值修改的原子性，因此能正常返回结果。

五、源码解析

AtomicInteger 源码：

public class AtomicInteger extends Number implements Serializable {
    private static final long serialVersionUID = 6214790243416807050L;
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    // value 值的内存偏移量
    private static final long valueOffset;
    // 内存值
    private volatile int value;
    
    static {
        try {
            valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception var1) {
            throw new Error(var1);
        }
    }
    
    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }
    
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }
    
    ... 
}

AtomicInteger 中的原子性操作都是通过 Unsafe 来完成，后者为我们提供了硬件级别的原子操作。

在加载 AtomicInteger 类时就将 valueOffset (即 value 值相对 AtomicInteger 实例内存地址的偏移位置)获取到，在实例化对象调用方法时就该参数传入底层调用的 Unsafe 的方法中。

Q1: 为什么需要保存 valueOffset 值？ 我们来到 Unsafe 源码中找寻答案：

Unsafe 源码：

public final class Unsafe {
    
    ...
    
    /**
     * Int 类型的 CAS 操作  
     * @param obj     AtomicXXX 实例
     * @param offset  value 的偏移量
     * @param expect  期望值
     * @param update  新值
     */
    public final native boolean compareAndSwapInt(Object obj, long offset, int expect, int update);

    public final int getAndAddInt(Object obj, long offset, int incr) {
        int val;
        do {
            // (1)
            val = this.getIntVolatile(obj, offset);
            // (2)
        } while(!this.compareAndSwapInt(obj, offset, val, val + incr));

        return val;
    }
}

在 Unsafe 源码中定义了许多 native 方法。native 方法底层由 C/C++ 实现，很多方法都依赖内存偏移量(valueOffset)。由于 Java 无法直接操作系统底层资源，因此需要借助 native 方法，通过 C/C++ 去实现对系统底层的 CAS 操作。

我们来看 getAndAddInt 方法，它是 getAndIncrement 方法的底层实现。该方法的实现很简单，先通过 AtomicInteger 的实例和 value 值的偏移量获取到 value 值。然后在 while 循环中调用 compareAndSwapInt 进行 CAS 操作，如果判断成功设置新值跳出循环返回数据。如果判断不成功，重新获取 value 值继续进行 CAS 操作。

六、CAS 的缺点

循环时间长，开销大

在上文 Unsafe 源码中可以看到，getAndAddInt 方法中的 compareAndSwapInt 方法的调用是在 do while 循环中完成的。遇到极端情况，判断一直失败，while 就会不断循环导致 CPU 资源的浪费。这种操作也成为自旋。

注意：getAndIncrement 底层之所以需要自旋是因为需要返回 value 的最终值。而 compareAndSet 只返回判断结果，如果在某个业务场景中修改某个值(对象)并返回，那么 compareAndSet 也需要在 while 循环中进行。

只能保证一个共享变量的原子性操作

在上文中 AtomicInteger 类中只声明了一个实例变量 value，所有的 CAS 操作都是围绕着它进行，没有其他多余的共享变量可用。

解决方案: JDK1.5 开始提供 AtomicReference 类用于对对象的 CAS 操作，我们可以将多个需要共享的变量声明到对象中，通过操作对象进行 CAS 操作。

会出现 ABA 问题

我们拿 getAndAddInt 方法来描述，该方法未加锁，因此在 (1) 和 (2) 操作过程中可能会被线程切换。假设 t1 线程对 value 进行获取并累加操作，在执行完成 (1) 后，获取到的 value 是为 1，这时被 CPU 切换。t2 线程拿到 CPU 资源顺利将 value 改成 3。之后 t2 线程又拿到 CPU 资源将 value 值改成 1。最后轮到 t1 线程拿到 CPU 资源继续进行 (2) 操作，判断成功将 value 值改成新值。

虽然 t1 线程能一次过的判断成功，将 value 值进行累计，但是 value 在修改过程中被其他线程修改过，这就是 ABA 问题。

将例子延伸到实际案例中理解：某公司有 100 万公款，某员工非法挪用了 50 万，之后又将之前挪用的公款还了回去。虽说公款还是 100 万元，但公款被挪用过，先不论非员工最终是否被惩罚，在法律层面上讲，他已经犯法了。

解决方案: 给修改的数据添加版本号-AtomicStampedReference

public class AtomicTest {

    // 入参1：初始值  入参2：初始版本号
    private static AtomicStampedReference<Integer> numVersion = new AtomicStampedReference<>(0, 1);

    public static void main(String[] args) {

        int stamp = numVersion.getStamp();
        System.out.println("当前 num 的版本: " + stamp);

        System.out.println(numVersion.compareAndSet(0, 100, stamp, stamp + 1));

        stamp = numVersion.getStamp();
        System.out.println("进行一次修改，当前 num 的版本: " + stamp);
    }
}

执行结果：

1
2
3

初始状态，当前 num 的版本: 1
true
进行一次修改，当前 num 的版本: 2

七、参考资料

悲观锁和乐观锁的区别