CAS算法

前言

CAS，即 Compare And Swap(比较与交换)，是一种无锁算法，基于硬件原语实现，能够在不使用锁的情况下实现多线程之间的变量同步。jdk 中的 java.util.concurrent.atomic 包中的原子类就是通过 CAS 来实现了乐观锁。

CAS 算法过程

算法涉及到三个操作数：

• 需要读写的内存位置 V
• 需要进行比较的预期值 A
• 需要写入的新值 U

CAS 算法解析：

CAS 具体执行时，当且仅当预期值 A 符合内存地址 V 中存储的值时，就用新值 U 替换掉旧值，并写入到内存地址 V 中。否则不做更新。

CAS 算法的运行原理如下如所示：

CAS 会有如下三个方面的问题：

1.ABA 问题，一个线程将内存值从 A 改为 B，另一个线程又从 B 改回到 A。

2. 循环时间长开销大：CAS 算法需要不断地自旋来读取最新的内存值，长时间读取不到就会造成不必要的 CPU 开销。

1. 只能保证一个共享变量的原子操作（jdk 的 AtomicReference 来保证应用对象之间的原子性，可以把多个变量放在一个对象里来进行 CAS 操作，解决了这一问题）。

ABA 问题图解：

ABA 问题解决方案：在变量前面添加版本号，每次变量更新的时候都将版本号加 1，比如 juc 的原子包中的 AtomicStampedReference 类。