(目录)

---

CAS ( Compare and swap)

1、解析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 ，指的是 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

1. 两个线程都读取 value 的值到 oldValue 中. (oldValue 是一个局部变量, 在栈上. 每个线程有自己的栈)
2. 线程1 先执行 CAS 操作. 由于 oldValue 和 value 的值相同, 直接进行对 value 赋值
3. 线程2 再执行 CAS 操作, 第一次 CAS 的时候发现 oldValue 和 value 不相等, 不能进行赋值. 因此需要进入循环. 在循环里重新读取 value 的值赋给 oldValue
4. 线程2 接下来第二次执行 CAS, 此时 oldValue 和 value 相同, 于是直接执行赋值操作
5. 线程1 和 线程2 返回各自的 oldValue 的值即可

---

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 的方式来完成这个扣款过程就可能出现问题.

正常的过程：

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 相同, 再次执行扣款操作

这个时候, 扣款操作被执行了两次 ! ! ! 都是 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 比较数据当前值和旧值的同时, 也要比较版本号是否符合预期.

如果发现当前版本号和之前读到的版本号一致, 就真正执行修改操作, 并让版本号自增;

如果发现当前版本号比之前读到的版本号大, 就认为操作失败

---