【多线程】CAS

来源：五一七教育网

🐍一. 什么是 CAS

CAS 是操作系统/硬件，给 JVM 提供的另外一种更轻量的原子操作的机制

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

比较内存和寄存器的值，如果相等，则把寄存器和另一个内存中的值进行交换，如果不相等，不进行操作。

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

CAS 伪代码

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

expectValue 用来比较的值(寄存器)

swapValue 用来交换的值(另一个寄存器)

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

CAS 可以视为是一种乐观锁. (或者可以理解成 CAS 是乐观锁的一种实现方式)

🦎二. CAS 是怎么实现的

针对不同的操作系统，JVM 用到了不同的 CAS 实现原理，简单来讲：

java 的 CAS 利用的的是 unsafe 这个类提供的 CAS 操作；
unsafe 的 CAS 依赖了的是 jvm 针对不同的操作系统实现的 Atomic::cmpxchg；
Atomic::cmpxchg 的实现使用了汇编的 CAS 操作，并使用 cpu 硬件提供的 lock 机制保证其原子性。

简而言之，是因为硬件予以了支持，软件层面才能做到。

🦖三. CAS 典型应用场景

🐶1. 实现原子类

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

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

例如我们之前 count 在两个线程中都自增 5000，结果却不是 10000，在这里就可以解决这个问题

public class Demo27 {
    //public static int count = 0;
    public static AtomicInteger count = new AtomicInteger(0);

    public static void main(String[] args) throws InterruptedException {
        Thread t1 = new Thread(()->{
           for (int i = 0; i < 50000; i++){
               //count++;
               //这个方法就相当于 count++;
               count.getAndIncrement();
           }
        });
        Thread t2 = new Thread(()->{
            for (int i = 0; i < 50000; i++) {
                //count++;
                count.getAndIncrement();
            }
        });
        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println("count = " + count);
    }
}

伪代码实现：

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

内部实现过程：两个线程同时调用 getAndIncrement

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

线程1的 oldvalue = 0，线程2的 oldvalue = 0，Value = 0 。

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

注意:

CAS 是直接读写内存的, 而不是操作寄存器.

CAS 的读内存, 比较, 写内存操作是一条硬件指令, 是原子的.

线程1的 oldvalue = 0，线程2的 oldvalue = 0，Value = 1 。

线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要

进入循环.

在循环里重新读取 value 的值赋给 oldValue

线程1的 oldvalue = 0，线程2的 oldvalue = 1，Value = 1 。

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

线程1的 oldvalue = 0，线程2的 oldvalue = 1，Value = 2 。

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

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

🐱2. 实现自旋锁

基于 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;
   }
}

当 owner 为 null 的时候 CAS 才能成功，循环才能结束；当 owner 为非 null 的时候，说明当前的锁已经被其他的线程占用了，因此就需要继续循环。

🦕四. CAS 的 ABA 问题

🐭1. 什么是 ABA 问题

在 CAS 中无法区分，数据始终是 A ，还是从 A -> B -> A 。

🐹2. ABA 问题引来的 BUG

假设滑稽老哥有 100 存款. 滑稽想从 ATM 取 50 块钱. 取款机创建了两个线程, 并发的来执行 -50

操作.

我们期望一个线程执行 -50 成功, 另一个线程 -50 失败.

如果使用 CAS 的方式来完成这个扣款过程就可能出现问题.

正常的过程：

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

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

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

异常的过程：

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

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

在线程2 执行之前, 滑稽的朋友正好给滑稽转账 50, 账户余额变成 100 !!

轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 再次执行扣款操作

这个时候, 扣款操作被执行了两次!!! 都是 ABA 问题搞的鬼!!

🐰3. 解决方案

正确的解决 ABA 问题的办法，是想办法获取到中间过程，于是引入了一个 “版本号” 来解决

给要修改的值, 引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.

CAS 操作在读取旧值的同时, 也要读取版本号.
真正修改的时候,

如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1.

如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).

这就好比, 判定这个手机是否是翻新机, 那么就需要收集每个手机的数据, 第一次挂在电商网站上的

手机记为版本1, 以后每次这个手机出现在电商网站上, 就把版本号进行递增. 这样如果买家不在意

这是翻新机, 就买. 如果买家在意, 就可以直接略过.

对比理解上面的转账例子

假设滑稽老哥有 100 存款. 滑稽想从 ATM 取 50 块钱. 取款机创建了两个线程, 并发的来执行 -50

操作.

我们期望一个线程执行 -50 成功, 另一个线程 -50 失败.

为了解决 ABA 问题, 给余额搭配一个版本号, 初始设为 1.

存款 100. 线程1 获取到存款值为 100, 版本号为 1, 期望更新为 50; 线程2 获取到存款值为 100, 版本号为 1, 期望更新为 50.

线程1 执行扣款成功, 存款被改成 50, 版本号改为2. 线程2 阻塞等待中.

在线程2 执行之前, 滑稽的朋友正好给滑稽转账 50, 账户余额变成 100, 版本号变成3.

轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 但是当前版本号为 3, 之前读

到的版本号为 1, 版本小于当前版本, 认为操作失败.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文