CAS.md

简述 CAS 原理，什么是 ABA 问题，怎么解决？

1. 什么是CAS

• CAS即Compare And Swap的缩写，翻译成中文就是比较并交换.
• 作用：让CPU比较内存中某个值是否和预期的值相同，如果相同则将这个值更新为新值，不相同则不做更新，
• 原子性：CAS是原子性的操作(读和写两者同时具有原子性)，其实现方式是通过借助C/C++调用CPU指令完成的，所以效率很高。

2. CAS的缺点 - ABA问题

1. 在多线程的环境中，线程1从共享的地址X中读取到了对象A。
2. 在线程1准备对地址X进行更新之前，线程2将地址X中的值修改为了B。
3. 接着线程2将地址X中的值又修改回了A。
4. 最新线程1对地址X执行CAS，发现X中存储的还是对象A，对象匹配，CAS成功。

上面的例子中CAS成功了，但是实际上这个CAS并不是原子操作。

隐藏的问题：

1. 现有一个用单向链表实现的FIFO堆栈，栈顶为A
2. 线程1已经知道A.next为B，然后希望用CAS将栈顶替换为B，
3. 在线程1执行上面这条指令之前，线程2 介入，将A、B出栈，再push D、C、A,
4. 此时A位于栈顶，B已经不在栈中；

• 此时线程1执行CAS，发现栈顶仍为A，所以CAS成功，即将栈顶变成B，
• 但实际上此时B与 当前栈中元素D、C没有关系，B.next为null，这样一来就直接把C、D丢掉了

解决方案 - 加版本号

在每个变量都加上一个版本号，每次改变时加1，即A —> B —> A，变成A(1) —> B(2) —> A(3)。

解决方案的应用 - AtomicStampedReference

它通过包装[E,Integer]的元组来对对象标记版本戳stamp，从而避免ABA问题。

3. CAS的缺点 - 循环时间长开销大

• 自旋： 如果CAS操作失败，就需要循环（自旋）进行CAS操作(循环同时将期望值更新为最新的)，如果长时间都不成功的话，那么会造成CPU极大的开销。
• 解决方法： 限制自旋次数，防止进入死循环。

4. CAS的缺点 - 只能保证一个共享变量的原子操作

• CAS的原子操作只能针对一个共享变量。
• 解决方法： 如果需要对多个共享变量进行操作，可以使用加锁方式(悲观锁)保证原子性，或者可以把多个共享变量合并成一个共享变量进行CAS操作。

5. CAS的应用

Java利用CAS的乐观锁、原子性的特性高效解决了多线程的安全性问题，例如JDK1.8中的集合类ConcurrentHashMap、关键字volatile、ReentrantLock等。