CAS和ABA问题

CAS

概念

CAS 的全称是 Compare-And-Swap，它是 CPU 并发原语，功能是判断内存某个位置的值是否为预期值，如果是则更改为新的值

CAS 并发原语体现在 Java 语言中就是 sun.misc.Unsafe 类的各个方法。调用 UnSafe 类中的 CAS 方法，JVM 会帮我们实现出 CAS 汇编指令，这是一种完全依赖于硬件的功能，通过它实现了原子操作。由于 CAS 是一种系统原语，原语属于操作系统使用范畴，是由若干条指令组成，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说 CAS 是一条 CPU 的原子指令，不会造成所谓的数据不一致的问题，是线程安全的。

CAS代码及底层原理

这里我们需要创建一个 AtomicInteger 示例并初始化，然后调用 compareAndSet() 方法来体验 CAS 操作，具体代码如下：

AtomicInteger atomicInteger = new AtomicInteger(5);
// 这行代码可以执行成功，因为主内存存的数据为5
System.out.println(atomicInteger.compareAndSet(5, 1024) + "\t current data: " + atomicInteger.get());
// 这行代码执行不成功，因为上一步操作将主内存存的数据改为1024
System.out.println(atomicInteger.compareAndSet(5, 2023) + "\t current data: " + atomicInteger.get());

这里我们查看 AtomicInteger 源码（如下图所示）可以发现其实现中定义了一个 Unsafe 变量，Unsafe 是 CAS 的核心类，Unsafe 类的所有方法都是 native 修饰的，也就是说 Unsafe 类中的方法都直接调用操作系统底层资源执行相应的任务，保证了操作的原子性。此外源码中 value 变量用 volatile 进行修饰，保证了该变量的可见性

接下来我们通过讲解 AtomicInteger 中 getAndIncrement() 方法来细说 CAS 具体实现原理，首先我们看该方法的定义：

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

上述代码中 this 指的是当前对象，valueOffset 表示该变量值在内存中的偏移地址，Unsafe 是根据内存偏移地址获取数据的。上述代码的意思是先通过 valueOffset 获取内存偏移地址，再通过内存偏移地址获取到值，然后进行加1的操作

现在我们看看 getAndAddInt() 该方法的实现:

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

    return var5;
}

var5：就是我们从主内存中拷贝到工作内存中的值

该代码的意思是每次都要从主内存拿到最新的值到自己的本地内存，然后执行 compareAndSwapInt() 方法和主内存的值进行比较，不同则返回 false，取非就是 true，就一直执行 while 方法，直到期望的值和真实值一样，然后执行加1操作。

CAS缺点

CAS 不加锁，保证原子性，但是需要多次比较，具有以下缺点：

• 循环时间长，开销大

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

  • 当对一个共享变量执行操作时，我们可以通过循环 CAS 的方式（自旋）来保证原子操作
  • 但是对于多个共享变量操作时，循环 CAS 就无法保证操作的原子性，这个时候只能用锁来保证原子性

• 引出来 ABA 问题

ABA问题

概念

所谓 ABA（见维基百科的ABA词条），问题基本是这个样子：

• 进程 P1 在共享变量中读到值为 A
• P1 被抢占了，进程 P2 执行
• P2 把共享变量里的值从A改成了 B，再改回到 A，此时被 P1 抢占
• P1 回来看到共享变量里的值没有被改变，于是继续执行

ABA 问题说的直白点就是在进行获取主内存值的时候，该内存值在我们写入主内存的时候，已经被修改了 N 次，但是最终又改成原来的值了

CAS 出现 ABA 问题的根本是在修改变量的时候，无法记录变量的状态，比如修改的次数，CAS 只管开头和结尾，也就是头和尾一样，就修改成功，但中间的这个过程可能会被人修改过

解决方法

利用AtomicStampedReference （时间戳原子引用）来解决 ABA 问题，它解决 ABA 问题的原理是引入版本号，每次修改都会改相应的版本号（类似于乐观锁），同时每次更新的时候，不但比较期望值和当前值，还比较期望版本号和当前版本号

下面代码是 ABA 问题的产生以及用AtomicStampedReference 来解决 ABA 问题：

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABADemo {

    /**
     * 普通的原子引用包装类
     */
    static AtomicReference<Integer> atomicReference = new AtomicReference<>(100);

    // 传递两个值，一个是初始值，一个是初始版本号
    static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<>(100, 1);

    public static void main(String[] args) {

        System.out.println("============以下是ABA问题的产生==========");

        new Thread(() -> {
            // 把100 改成 101 然后在改成100，也就是ABA
            atomicReference.compareAndSet(100, 101);
            atomicReference.compareAndSet(101, 100);
        }, "t1").start();

        new Thread(() -> {
            try {
                // 睡眠一秒，保证t1线程，完成了ABA操作
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            // 把100 改成 101 然后在改成100，也就是ABA
            System.out.println(atomicReference.compareAndSet(100, 2023) + "\t" + atomicReference.get());

        }, "t2").start();

        try {
            // 睡眠一秒，保证t1线程，完成了ABA操作
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        System.out.println("============以下是ABA问题的解决==========");

        new Thread(() -> {

            // 获取版本号
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t 第一次版本号" + stamp);

            // 暂停t3一秒钟
            try {
                TimeUnit.SECONDS.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            // 传入4个值，期望值，更新值，期望版本号，更新版本号
            atomicStampedReference.compareAndSet(100, 101, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);

            System.out.println(Thread.currentThread().getName() + "\t 第二次版本号" + atomicStampedReference.getStamp());

            atomicStampedReference.compareAndSet(101, 100, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);

            System.out.println(Thread.currentThread().getName() + "\t 第三次版本号" + atomicStampedReference.getStamp());

        }, "t3").start();

        new Thread(() -> {

            // 获取版本号
            int stamp = atomicStampedReference.getStamp();
            System.out.println(Thread.currentThread().getName() + "\t 第一次版本号" + stamp);

            // 暂停t4 3秒钟，保证t3线程也进行一次ABA问题
            try {
                TimeUnit.SECONDS.sleep(3);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

            boolean result = atomicStampedReference.compareAndSet(100, 2023, stamp, stamp+1);

            System.out.println(Thread.currentThread().getName() + "\t 修改成功否：" + result + "\t 当前最新实际版本号：" + atomicStampedReference.getStamp());

            System.out.println(Thread.currentThread().getName() + "\t 当前实际最新值" + atomicStampedReference.getReference());


        }, "t4").start();

    }
}

运行结果为：

我们能够发现，线程 t3，在进行 ABA 操作后，版本号变更成了 3，而线程 t4 在进行操作的时候，就出现操作失败了，因为版本号和当初拿到的不一样

参考

• 尚硅谷Java大厂面试题第2季