【JavaEE】CAS -- 多线程篇(7)

CAS

1. 什么是 CAS
2. CAS 伪代码
3. CAS 是怎么实现的
4. CAS的应用
- 4.1 实现原子类
- 4.2 实现自旋锁
5. CAS 的 ABA 问题

1. 什么是 CAS

CAS: 全称Compare and swap，字面意思:”比较并交换“
能够比较和交换某个寄存器中的值和内存中的值, 看是否相等, 如果相等, 则把另一个寄存器中的值和内存进行交换

2. CAS 伪代码

下面写的代码不是原子的, 真实的 CAS 是一个原子的硬件指令完成的. 这个伪代码只是辅助理解CAS 的工作流程

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

伪代码解释

address 是内存地址, 剩下的两个都是寄存器中的值 – 一个表示旧的数据的值, 一个表示要更新的数据的值
这一段逻辑, 是通过一条 CPU 指令完成的 – 所以这个操作是原子的
解释交换语句只有一条赋值语句的原因: 把 address 内存的值和 swapValue 寄存器的值进行交换, 但是我们一般重点关注是内内存中的值, 寄存器往往作为保存临时数据的方法, 这里的值是干啥的, 很多时候就忽略了

3. CAS 是怎么实现的

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

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

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

4. CAS的应用

4.1 实现原子类

标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的.
在这里插入图片描述
典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作.

原子类的使用

public static AtomicInteger count = new AtomicInteger(0);
public static void main(String[] args) throws InterruptedException {Thread t1 = new Thread(() -> {for (int i = 0; i < 5000; i++) {// count++count.getAndIncrement();// ++count// count.incrementAndGet();// count--// count.getAndDecrement();// --count// count.decrementAndGet();}});Thread t2 = new Thread(() -> {for (int i = 0; i < 5000; i++) {// count++count.getAndIncrement();}});t1.start();t2.start();t1.join();t2.join();System.out.println(count.get());
}

伪代码实现

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 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值.

注意:
- CAS 是直接读写内存的, 而不是操作寄存器.
- CAS 的读内存, 比较, 写内存操作是一条硬件指令, 是原子的.

在这里插入图片描述

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

在这里插入图片描述

线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作.
线程1 和线程2 返回各自的 oldValue 的值即可.

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

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

4.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;}
}

伪代码分析

在这里插入图片描述

5. CAS 的 ABA 问题

CAS 关键要点, 是比较寄存器1 和内存的值, 通过这里的是否相等来判定内存的值是否发生了该变;
- 如果内存的值变量, 存在其他线程进行了修改;
- 如果内存的值没有改变, 没有别的线程修改, 接下来的修改就是安全的
问题提出: 这里的值没有变, 就一定没有别的线程修改吗?
- 答案是否定的!
- 内存的值变化过程可能是 A -> B -> A
- 这就是是所谓的ABA问题
大部分情况下, 就算是出现 ABA 问题, 也没啥太大影响, 但是如果与发哦一些极端的场景, 就不一定了

ABA 问题引出的 bug

在这里插入图片描述

解决方案

给要修改的值, 引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.
- CAS 操作在读取旧值的同时, 也要读取版本号.
- 真正修改的时候,
  - 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1
  - 如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).

在这里插入图片描述