@TOC
CAS ( Compare and swap)
1、解析CAS
CAS：全称 Compare and swap，字面意思：”比较并交换“，一个 CAS 涉及到以下操作：
我们假设内存中的原数据V，旧的预期值A，需要修改的新值B。
CAS 伪代码：
下面写的代码不是原子的, 真实的 CAS 是一个原子的硬件指令完成的. 这个伪代码只是辅助理解CAS 的工作流程.
boolean CAS(address, expectValue, swapValue) { if (&address == expectedValue) { &address = swapValue; return true; } return false; }
此处所谓的 CAS ，指的是 CPU 提供了一个单独的 CAS 指令，通过这一条CPU指令，就可以完成上述伪代码要做的所有事情。
我们此处讨论的CAS，其实讨论的就是这一条CPU的指令。 这个代码很明显是线程不安全的
但是如果上述是“一条指令”，（CPU上指令是一条一条执行的）此时线程安全
CAS最大的意义，就是让我们写这种多线程安全的代码，提供了一个新的思路和方向 (就和锁不一样了)
很多功能，既可以是硬件实现，也可以是软件实现
就像刚才这段比较交换逻辑，这就相当于硬件直接实现出来了，通过这一条指令，封装好，直接让咱们用了
2、CAS 应用
1. 基于CAS 能够实现“原子类”
Java 标准库中提供了一组原子类，针对所常用多一些 int, long, int array… 进行了封装，可以基于 CAS 的方式进行修改，并且线程安全
java.util.concurrent.atomic 包，里面的类都是基于这种方式来实现的
典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作.
import java.util.concurrent.atomic.AtomicInteger; public class Demo27 { public static void main(String[] args) throws InterruptedException { AtomicInteger num = new AtomicInteger(0); Thread t1 = new Thread(() -> { for (int i = 0; i < 50000; i++) { // 这个方法就相当于 num++ num.getAndIncrement(); } }); Thread t2 = new Thread(() -> { for (int i = 0; i < 50000; i++) { // 这个方法就相当于 num++ num.getAndIncrement(); } }); // // ++num // num.incrementAndGet(); // // --num // num.decrementAndGet(); // // num-- // num.getAndDecrement(); // // += 10 // num.getAndAdd(10); t1.start(); t2.start(); t1.join(); t2.join(); // 通过 get 方法得到 原子类 内部的数值. System.out.println(num.get()); } }运行结果：
100000这个代码里面不存在线程安全问题，基于 CAS 实现的 ++ 操作
这里面就可以保证既能够线程安全，又能够比 synchronized 高效，`synchronized会涉及到锁的
竞争，两个线程要相互等待CAS不涉及到线程阻塞等待
方法：
num.incrementAndGet(); // ++num num.decrementAndGet(); // --num num.getAndIncrement(); // num++; num.getAndDecrement(); // num--; num.getAndAdd(10); // += 10原子类背后具体是怎么实现的
原子类背后具体是怎么实现的？
伪代码实现:
class AtomicInteger { private int value; public int getAndIncrement() { int oldValue = value; while ( CAS(value, oldValue, oldValue+1) != true) { oldValue = value; } return oldValue; } }图解：
图上的意思就是：假设两个线程同时调用 getAndIncrement
2. 基于CAS能够实现自旋锁
基于 CAS 实现更灵活的锁，获取到更多的控制权
自旋锁伪代码 ：
public class SpinLock { private Thread owner = null; // 记录下当前锁被哪个线程持有了，为 null 表示当前未加锁 public void lock(){ // 通过 CAS 看当前锁是否被某个线程持有. // 如果这个锁已经被别的线程持有, 那么就自旋等待. // 如果这个锁没有被别的线程持有, 那么就把 owner 设为当前尝试加锁的线程. while(!CAS(this.owner, null, Thread.currentThread())){ } } public void unlock (){ this.owner = null; } }图解：
CAS中的ABA问题
ABA问题：就是CAS中的关键【先比较，在交换】
而这里的比较，其实是在比较 当前值 和 旧值 是不是相同的。
把这两个值相同的情况，就视为中间没有发生过改变。
但是这里的结论存在这漏洞。
当前值 和 旧值 相同，可能是中间确实没改变过。也有可能是改变了，但是变回来了。
【最终的值虽然和旧值相同，但是它确实改变了】
而当前就很草率的决定，只要值相同就没有发生改变。这样的漏洞，在大多数情况下，其实没有影响。但是，在极端情况也会引起bug。这种问题，就被称为 ABA 问题。
所谓的ABA 指的是：
本来旧的值A，当前值也是A。
结果你不知道当前的A，它是一直都是A，还是从A变成了B，再从B又变回了A。
举—个典型的例子，ABA问题产生的bug：
假设 有 100 存款. 滑稽想从 ATM 取 50 块钱. 取款机创建了两个线程, 并发的来执行 -50 操作我们期望一个线程执行 -50 成功, 另一个线程 -50 失败.如果使用 CAS 的方式来完成这个扣款过程就可能出现问题.
正常的过程：
异常的过程：
这个时候, 扣款操作被执行了两次 ! ! ! 都是 ABA 问题搞的鬼
int oldValue = value; //读取旧值 CAS(&value, oldValue, oldValue - 50)当按下取款的操作的时候,机器卡了一下，滑稽多按了—下取款~
这就相当于，一次取钱操作,执行了两遍，(两个线程，并发的去执行这个取钱操作)，咱们的预期效果应该是只能取成功一次！(希望取走50，账户还剩50)
假设在取款的一瞬间,滑稽的朋友给他转了50此时就会触发ABA问题
卡了和转了50，这两次巧合导致了一个存在 BUG 的 ABA 问题 (极端场景的问题)
哪怕这样的 bug 出现概率是 0.01%，咱们也需要处理!!!
如何解决ABA问题
给要修改的值, 引入版本号。在 CAS 比较数据当前值和旧值的同时，也要比较版本号是否符合预期
这个版本号只能变大，不能变小，修改变量的时候，比较就不是比较变量本身了，而是比较版本号了
这里不一定非得用“版本号"，也可以用“时间戳"
- CAS 操作在读取旧值的同时，也要读取版本号
- 真正修改的时候
- 如果当前版本号和读到的版本号相同，则修改数据，并把版本号 + 1.
- 如果当前版本号高于读到的版本号，就操作失败 (认为数据已经被修改过了
另外，这里不一定非得“版本号”，也可以使用“时间戳”，日期时间肯定是一直往前走的。
所以使用 时间戳也是没有问题的。
拓展：
这种基于 版本号 的方式 来进行多线程数据的控制，也是一种乐观锁的典型实现。
1、数据库里
在数据库里面，并发的去通过事务来访问表的时候，这也会涉及到类似加锁的一些多线程操作 2、版本管理工具（SVN）
它就是通过版本号来进行多人开发的协同。
如果别人改过了，就需要先去进行一个拉去数据，再重新提交。
相关面试题
① 讲解下你自己理解的 CAS 机制
CAS全称 Compare and swap, 即 “比较并交换”.
相当于通过一个原子的操作, 同时完成 “读取内存, 比较是否相等, 修改内存” 这三个步骤.
本质上需要 CPU 指令的支撑.
② ABA问题怎么解决？
给要修改的数据引入版本号。
在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.
如果发现当前版本号和之前读到的版本号一致, 就真正执行修改操作, 并让版本号自增;
如果发现当前版本号比之前读到的版本号大, 就认为操作失败