一、CAS是什么？

CAS的全称：Compare and swap，字面意思:”比较并交换“，一个 CAS 涉及到以下操作：

我们假设内存中的原数据V，旧的预期值A，需要修改的新值B。

1. 比较 A 与 V 是否相等。（比较）

2. 如果比较相等，将 B 写入 V。（交换）

3. 返回操作是否成功。

CAS 伪代码：

boolean CAS(address, expectValue, swapValue) {
   if (&address == expectedValue) {
       &address = swapValue;
       return true;
   }
   return false;
}

当多个线程同时对某个资源进行CAS操作，只能有一个线程操作成功，但是并不会阻塞其他线程,其他线

程只会收到操作失败的信号。CAS 可以视为是一种乐观锁(或者可以理解成 CAS 是乐观锁的一种实现方式)。

整个CAS的过程，它并不是通过一段代码来实现的，而是通过一条CPU指令来完成的。而CAS操作是原子的，这样就可以在一定程度上规避线程安全问题。所以，解决线程安全问题除了加锁之外，CAS操作也是一个方向。

小结：CAS可以理解成是CPU给咱们提供的一个特殊指令,通过这个指令，就可以一定程度的处理线程安全问题。

二、CAS的应用场景

- 实现原子类

标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的。

典型的就是 AtomicInteger 类，其中的 getAndIncrement 相当于 i++ 操作。

 public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger(0);

        Thread t1 = new Thread(()->{
            for (int i = 0; i < 5_0000; i++) {
                atomicInteger.getAndIncrement();//相当于count++
//                atomicInteger.incrementAndGet();//相当于++count
//                atomicInteger.getAndDecrement();//相当于count--
//                atomicInteger.decrementAndGet();//相当于--count
            }
        });

        Thread t2 = new Thread(()->{
            for (int i = 0; i < 5_0000; i++) {
                atomicInteger.getAndIncrement();//相当于count++
            }
        });

        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println(atomicInteger);//  运行结果为10_0000
    }

AtomicInteger的伪代码（AtomicInteger 的实现原理是什么？）：

class AtomicInteger {
   private int value;
   public int getAndIncrement() {
       int oldValue = value;
       while ( CAS(value, oldValue, oldValue+1) != true) {
           oldValue = value;
       }
       return oldValue;
    }
}

假设两个线程同时调用 getAndIncrement：

1) 两个线程都读取 value 的值到 oldValue 中 (oldValue 是一个局部变量, 在栈上，每个线程有自己的栈)

2) 线程1 先执行 CAS 操作，由于 oldValue 和 value 的值相同, 直接进行对 value 赋值

3) 线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环，在循环里重新读取 value 的值赋给 oldValue

4) 线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作

5) 线程1 和线程2 返回各自的 oldValue 的值即可

通过形如上述代码就可以实现一个原子类。不需要使用重量级锁, 就可以高效的完成多线程的自增操作。

本来 check and set 这样的操作在代码角度不是原子的。但是在硬件层面上可以让一条指令完成这个操作, 也就变成原子的了。

- 实现自旋锁

通过CAS实现自旋锁伪代码：

public class SpinLock {
    private Thread owner = null;
    public void lock(){
       // 通过 CAS 看当前锁是否被某个线程持有
       // 如果这个锁已经被别的线程持有, 那么就自旋等待
       // 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程
       while(!CAS(this.owner, null, Thread.currentThread())){
       }
    }
    public void unlock (){
       this.owner = null;
    }
}

三、CAS的典型问题：ABA问题

ABA 的问题:

假设存在两个线程 t1 和 t2，有一个共享变量 num, 初始值为 A。接下来, 线程 t1 想使用 CAS 把 num 值改成 Z, 那么就需要先读取 num 的值, 记录到 oldNum 变量中。使用 CAS 判定当前 num 的值是否为 A, 如果为 A, 就修改成 Z。但是, 在 t1 执行这两个操作之间, t2 线程可能把 num 的值从 A 改成了 B, 又从 B 改成了 A。线程 t1 的 CAS 是期望 num 不变就修改。但是 num 的值已经被 t2 给改了，只不过又改成 A 了。这个时候 t1 究竟是否要更新 num 的值为 Z 呢?

到这一步, t1 线程无法区分当前这个变量始终是 A, 还是经历了一个变化过程后的A。

ABA 问题引来的 BUG：举个例子

假设 A有 100 存款，A想从 ATM 取 50 块钱。但是取钱的过程中机子卡顿了一下，一下子按了两次取款操作，取款机创建了两个线程, 并发的来执行 -50操作。

期望的是一个线程执行 -50 成功, 另一个线程 -50 失败。但是如果使用 CAS 的方式来完成这个扣款过程，在一些极端情况下就可能出现问题。

正常的过程

1) 存款 100，线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期

望更新为 50。

2) 线程1 执行扣款成功, 存款被改成 50，线程2 阻塞等待中。

3) 轮到线程2 执行了, 发现当前存款为 50, 和之前读到的 100 不相同, 执行失败。

异常的过程

1) 存款 100，线程1 获取到当前存款值为 100, 期望更新为 50; 线程2 获取到当前存款值为 100, 期

望更新为 50。