CAS (Compare And Swap)

比较并交换, 可以理解成是 CPU 提供一种特殊指令, 该指令是原子的, 可以用其一定程度解决线程安全问题, 具体过程如下

假设内存中有原数据 V, 寄存器中有旧的预期值 A 和修改值 B

1. 比较 V 与 B 的值是否相等
2. 如果相等, 则将 B 写入 V
3. 返回操作是否成功

上述三步操作就是 CAS 的具体描述, 并且这三步操作是通过一条 CPU 指令完成 (原子操作)

简单理解
CAS 即 Compare And Swap , “比较和交换”. 相当于通过一个原子操作, 同时完成 “读取内存, 比较是否相等, 修改内存” 这三个步骤, 本质上需要 CPU 指令的支撑 .

---

CAS 的应用场景

1. 实现原子类

Java 标准库提供了一些原子类 java.util.concurrent.atomic

而这些原子类基于 CAS 实现, 使用原子类进行多线程的操作, 可保证线程安全

2. 实现自旋锁

基于 CAS 实现的锁, 具有更强的锁竞争能力

下述是一段CAS 实现自旋锁的伪代码(基本逻辑是这样, 但是实现要复杂的多)

伪代码分析

可以看到, 如果把解锁操作认为是给锁对象赋值 null 的话,加锁操作就是在一个死循环内不断的去对锁资源进行判定, 看其是否已被释放, 当其被释放的时候, 就可以被当前线程获取.
伪代码是在 while() 循环内进行, 代表此时 CPU 一直在使用

---

ABA问题

什么是ABA问题

假设存在两个线程 t1 和 t2, 存在共享变量为 num, 初始值为 A.

接下来, 线程 t1 想使用 CAS 把 num 值改成 Z, 那么就需要

• 先读取 num 的值, 记录到 oldNum 变量中
• 使用 CAS 判定 num 的值是否等于 oldNum, 如果相等, 那么将Z写入num

那么如果在这两个步骤之间, t2线程对 num 进行了操作, 把 num 的值从 A 改成了 B, 又从 B 改成了 A.
对于 线程 t1来说, A->B->A 的变换不可见, 但是仍会进行第二步操作, 即 num : A -> Z, 这就是 ABA问题: CAS 的误判

---

解决方案

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

• CAS 操作在读取旧值的同时, 也读取版本号
• 真正修改的时候
  • 如果当前读到的版本号和之前读到的版本号相同, 则修改数据, 并把版本号+1
  • 如果当前读到的版本号和之前读到的版本号不同,则操作失败(认为数据已经被修改过了)

---