【多线程】CAS 详解

一. 什么是 CAS

CAS: 全称Compare and swap，字面意思:”比较并交换“
1

一个 CAS 涉及到以下操作：
我们假设内存中的原数据 V，旧的预期值 A，需要修改的新值 B。

1. 比较 A 与 V 是否相等。（比较）
2. 如果比较相等，将 B 写入 V。（交换）
3. 返回操作是否成功。

CAS 伪代码:
下面写的代码不是原子的, 真实的 CAS 是一个原子的硬件指令完成的.
因为本身就是原子操作, 就没有线程安全问题,

    boolean CAS(address, expectValue, swapValue) {
    	// 取出 address 的值
        if (&address == expectedValue) {
            &address = swapValue;
            return true;
        }
        return false;
    }
1
2
3
4
5
6
7
8

当多个线程同时对某个资源进行CAS操作，只能有一个线程操作成功，但是并不会阻塞其他线程, 其他线程只会收到操作失败的信号。

可以理解为: CAS 是乐观锁的一种实现方式

二. CAS 的应用

CAS 最大的意义: 为我们写多线程安全的代码提供新的方向和思路

1. 实现原子类

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

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

伪代码实现:

class AtomicInteger {
    private int value;
    public int getAndIncrement() {
        int oldValue = value;
        while ( CAS(value, oldValue, oldValue+1) != true) {
            // 没有成功就将期待值换为最新值
            oldValue = value;
        }
        return oldValue;
    }
}
1
2
3
4
5
6
7
8
9
10
11

通过形如上述代码就可以实现一个原子类. 不需要使用重量级锁, 就可以高效的完成多线程的自增操作, 技能保证线程安全又高效, 因为 加锁就涉及到锁竞争, 而 CAS 不涉及线程阻塞.

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

2. 实现自旋锁

自旋锁伪代码

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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三. CAS 的 ABA 问题

ABA 问题:
CAS 关键是先比较再交换, 比较实质是比较当前值和旧值是否相同, 若相同, 则视为中间没有发生改变, 就进行修改. 但是这存在漏洞, 可能中间值变化了又变回来了, CAS 就无法判断到底是否发生过改变.

假设存在两个线程 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, 还是经历了一个变化过程又变为 A

这就好比, 我们买一个手机, 无法判定这个手机是刚出厂的新手机, 还是别人用旧了, 又翻新过的手
机.

ABA 问题引来的 BUG:

• 假设 A 有 100 存款. 想转账给 B 50 块钱. 但是点击转账按钮时没反应, 于是 A 又点击了一次
• 但是取款机实际创建了两个线程, 并发的来执行 -50 操作.
• 我们期望一个线程执行 -50 成功, 另一个线程 -50 失败.

如果使用 CAS 的方式来完成这个扣款过程就可能出现问题:

• 正常情况,第二个 线程 CAS 期望值是 100, 但实际是 50, 所以扣款失败.
• 但是如果转账过程中 C 又 给 A 转帐 50, 所以第二个线程 CAS 去判断余额还是 100, 所以就会扣款成功.

解决方案: 引入版本号

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

• CAS 操作在读取旧值的同时, 也要读取版本号.

真正修改的时候,

• 如果当前版本号和读到的版本号相同, 则修改数据, 并把版本号 + 1.
• 如果当前版本号高于读到的版本号. 就操作失败(认为数据已经被修改过了)

四. 相关面试题

1. 讲解下你自己理解的 CAS 机制
   全称 Compare and swap, 即 “比较并交换”. 相当于通过一个原子的操作, 同时完成 “读取内存, 比
   较是否相等, 修改内存” 这三个步骤. 本质上需要 CPU 指令的支撑.

2. ABA问题怎么解决？
   给要修改的数据引入版本号. 在 CAS 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.
   如果发现当前版本号和之前读到的版本号一致, 就真正执行修改操作, 并让版本号自增; 如果发现当前版本号比之前读到的版本号大, 就操作失败.

3. 相对于 锁机制, 为什么 CAS 效率更高?
   因为 CAS 本身就是一组原子指令, 不涉及线程安全问题, 所以不需要加锁、解锁等开销，减少了线程在互斥同步时所产生的性能消耗，当多个线程同时进行 CAS 操作时，只有一个能成功，其余则需重试，不涉及线程阻塞.

好啦！ 以上就是对 CAS 的讲解，希望能帮到你 ！
评论区欢迎指正 !