【多线程】CAS详解
目录
一、什么是CAS
二、CAS 是怎么实现的
三、CAS 应用
实现原子类
实现自旋锁
四、CAS 的 ABA 问题
什么是 ABA 问题
ABA问题引来的BUG
解决方案
一、什么是CAS
CAS: 全称Compare and swap，字面意思:”比较并交换“，一个 CAS 涉及到以下操作：
我们假设内存中的原数据V，旧的预期值A，需要修改的新值B。
1. 比较 A 与 V 是否相等。（比较）
2. 如果比较相等，将 B 写入 V。（交换）
3. 返回操作是否成功。
int i = 0;i++;线程不安全，如果需要多线程并发的i++，就需要加锁，加锁操作比较低效，因此可以使用CAS就可以完成自增，同时保证线程安全
二、CAS 是怎么实现的
针对不同的操作系统，JVM 用到了不同的 CAS 实现原理，简单来讲：
java 的 CAS 利用的的是 unsafe 这个类提供的 CAS 操作；
unsafe 的 CAS 依赖了的是 jvm 针对不同的操作系统实现的 Atomic::cmpxchg；
Atomic::cmpxchg 的实现使用了汇编的 CAS 操作，并使用 cpu 硬件提供的 lock 机制保证其原子 性。
简而言之，是因为硬件予以了支持，软件层面才能做到。
三、CAS 应用
实现原子类
标准库中提供了 java.util.concurrent.atomic 包, 里面的类都是基于这种方式来实现的. 典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作.
1) 两个线程都读取 value 的值到 oldValue 中. (oldValue 是一个局部变量, 在栈上. 每个线程有自己的栈)
2) 线程1 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值.
CAS 是直接读写内存的, 而不是操作寄存器.
CAS 的读内存, 比较, 写内存操作是一条硬件指令, 是原子的
3) 线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环.
4) 线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作.
实现自旋锁
CPU指令，来一次完成比较和交换这样的过程，尤其是可以不加锁也能保证线程安全
队列中有一种特殊的队列，无锁队列，通过CAS，直接在用户态实现了一个轻量级的自旋锁，通过这个自旋锁保证线程安全
四、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
ABA问题引来的BUG
假设小明有 100 存款. 滑稽想从 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.
2) 线程1 执行扣款成功, 存款被改成 50. 线程2 阻塞等待中.
3) 在线程2 执行之前, 小明的朋友正好给滑稽转账 50, 账户余额变成 100
4) 轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 再次执行扣款操作
解决方案
给要修改的值, 引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.
CAS 操作在读取旧值的同时, 也要读取版本号.
真正修改的时候,如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1. 如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了).
为了解决 ABA 问题, 给余额搭配一个版本号, 初始设为 1.
1) 存款 100. 线程1 获取到 存款值为 100, 版本号为 1, 期望更新为 50; 线程2 获取到存款值为 100, 版本号为 1, 期望更新为 50.
2) 线程1 执行扣款成功, 存款被改成 50, 版本号改为2. 线程2 阻塞等待中.
3) 在线程2 执行之前, 小明的朋友正好给滑稽转账 50, 账户余额变成 100, 版本号变成3.
4) 轮到线程2 执行了, 发现当前存款为 100, 和之前读到的 100 相同, 但是当前版本号为 3, 之前读 到的版本号为 1, 版本小于当前版本, 认为操作失败.
给要修改的数据引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期. 如果发现当前版本号和之前读到的版本号一致, 就真正执行修改操作, 并让版本号自增; 如果发现当 前版本号比之前读到的版本号大, 就认为操作失败