多线程——CAS

什么是CAS

CAS的全称：Compare and swap，字面意思就是：“比较并交换”，一个CAS涉及到以下操作：
假设内存中的原数据V，旧的预期值A，需要修改的新值B
1.比较A与V是否相等（比较）
2.如果相等，将B写入V（交换）
3.返回操作是否成功
CAS伪代码：
下面写的不是原子的，真正的CAS是一个原子的硬件指令完成的，这个伪代码只是用来辅助理解CAS的工作流程

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

CAS 有哪些应用

1) 实现原子类

标准库中提供了 java.util.concurrent.atomic 包, ??的类都是基于这种?式来实现的.
典型的就是 AtomicInteger 类. 其中的 getAndIncrement 相当于 i++ 操作.

AtomicInteger atomicInteger = new AtomicInteger(0);
// 相当于 i++
atomicInteger.getAndIncrement();

伪代码表示：

class AtomicInteger {
 private int value;
 public int getAndIncrement() {
 int oldValue = value;
 while ( CAS(value, oldValue, oldValue+1) != true) {
 oldValue = value;
 }
 return 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;
 }
}

CAS 的 ABA 问题

什么是 ABA 问题
ABA 的问题:
假设存在两个线程 t1 和 t2. 有?个共享变量 num, 初始值为 A.
接下来, 线程 t1 想使? CAS 把 num 值改成 Z, 那么就需要

? 先读取 num 的值, 记录到 oldNum 变量中.
? 使? CAS 判定当前 num 的值是否为 A, 如果为 A, 就修改成 Z.

但是, 在 t1 执?这两个操作之间, t2 线程可能把 num 的值从 A 改成了 B, ?从 B 改成了 A

线程 t1 的 CAS 是期望 num 不变就修改. 但是 num 的值已经被 t2 给改了. 只不过?改成 A 了. 这个时候 t1 究竟是否要更新 num 的值为 Z 呢?

到这一步，t1线程无法区分当前这个变量始终是A，还是经过了一个变化过程

ABA 问题引来的 BUG

?部分的情况下, t2 线程这样的?个反复横跳改动, 对于 t1 是否修改 num 是没有影响的. 但是不排除?些特殊情况.

假设 滑稽?哥 有 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.
? 如果当前版本号?于读到的版本号. 就操作失败(认为数据已经被修改过了).
这就好?, 判定这个?机是否是翻新机, 那么就需要收集每个?机的数据, 第?次挂在电商?站上的?机记为版本1, 以后每次这个?机出现在电商?站上, 就把版本号进?递增. 这样如果买家不在意这是翻新机, 就买. 如果买家在意, 就可以直接略过.

对?理解上?的转账例?

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

我们期望?个线程执? -50 成功, 另?个线程 -50 失败.
为了解决 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, 版本?于当前版本, 认为操作失败.

在 Java 标准库中提供了 AtomicStampedReference 类. 这个类可以对某个类进?包装, 在内部就提供了上?描述的版本管理功能.

相关面试题

1. 讲解下你??理解的 CAS 机制

全称 Compare and swap, 即 “?较并交换”. 相当于通过?个原?的操作, 同时完成 “读取内存, ?较是否相等,修改内存” 这三个步骤. 本质上需要 CPU 指令的?撑.

1. ABA问题怎么解决？

给要修改的数据引?版本号. 在 CAS ?较数据当前值和旧值的同时, 也要?较版本号是否符合预期. 如果发现当前版本号和之前读到的版本号?致, 就真正执?修改操作, 并让版本号?增; 如果发现当前版本号?之前读到的版本号?, 就认为操作失败