【Java 并发编程】CAS 原理解析
CAS 原理解析
1. 什么是 CAS？
1.1 悲观锁与乐观锁
悲观锁的原理是每次实现数据库的增删改的时候都进⾏阻塞，防⽌数据发⽣脏读。
乐观锁的原理是在数据库更新的时候，⽤⼀个 version 字段来记录版本号，然后通过⽐较是不是⾃⼰要修改的版本号再进⾏修改。这其中就引出了⼀种⽐较交换的思路来实现数据的⼀致性，事实上，CAS 也是基于这样的原理。
1.2 CAS 是什么？
CAS 是指 Compare And Swap，比较并交换，是一种无锁原子算法，在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步。
JAVA 底层是 C++ 实现，映射到操作系统就是一条 cmpxchg 硬件汇编指令（保证原子性），其作用就是让 CPU 将内存值更新为新值，但是有个条件，内存值必须与期望值相同。并且 CAS 操作无需用户态与内核态切换，直接在用户态对内存进行读写操作（意味着不会阻塞/线程上下文切换）。
java.util.concurrent.atomic 包中的原子类就是通过 CAS 来实现了乐观锁。
CAS 算法涉及到三个操作数：
-
需要更新的内存变量值 V（volatile）；
-
上一次从内存中读取，进行比较的预期原值 E（except）；
-
要写入的新值 N（new）。
当且仅当 V 的值等于 E 时，CAS 通过原子方式用新值 N 来更新 V 的值（“比较 + 更新” 整体是一个原子操作），否则不会执行任何操作，这就是一次 CAS 的操作。一般情况下，“更新” 是一个不断重试的操作。
简单说，CAS 需要你额外给出一个期望值，也就是你认为这个变量现在应该是什么样子的，如果变量不是你想象的那样，说明它已经被别人修改过了，你只需要重新读取，设置新期望值，再次尝试修改就好了。
2. CAS 核心源码
java.util.concurrent.atomic 包中的原子类就是通过 CAS 思想来实现，CAS 思想实现靠的是 Unsafe 类。以 AtomicInteger 为例：
Unsafe 类是 CAS 的核心类，由于 Java 方法无法直接访问底层系统，需要通过本地（native）方法来访问，Unsafe 相当于一个后门，基于该类可以直接操作特定内存的数据。Unsafe 类存在于 sun.misc 包中，其内部方法操作可以像C的指针一样直接操作内存。
valueOffset 表示当前类对象中使用变量的偏移量，Unsafe 就是根据内存偏移地址获取数据的。
value 要修改的值，用 volatile 修饰，保证了多线程之间的内存可见性。
一起看一下 AtomicInteger.getAndIncrement() 方法是怎么替换内容的：
public final int getAndIncrement() {
// 拿到当前对象和当前对象的地址，然后加一。
return unsafe.getAndAddInt(this, valueOffset, 1);
}
// var1 就是当前对象，var2 就是当前对象的内存地址，var4 就是要加的数
public final int getAndAddInt(Object var1, long var2, int var4) {
// 旧的预期值
int var5;
do {
// 获得当前 var2 地址中的值，可以理解为从当前主物理内存中拷贝一份到自己的本地内存
var5 = this.getIntVolatile(var1, var2);
}
// 如果var1 = var5，执行var5 + var4，执行成功返回 true，跳出 while 循环，执行失败返回false，自旋
while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
oop p = JNIHandles::resolve(obj);
jint* addr = (jint *)index_oop_from_field_offset_long(p, offset);
return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
} UNSAFE_END
首先获取 var5 旧的预期值，然后调用底层代码 Unsafe_CompareAndSetInt。下面看 Unsafe_CompareAndSetInt 怎么做的：
第一步通过 JNIHandles::resolve() 获取 obj 在内存中 OOP 实例；
第二步根据成员变量 value 反射后计算出的内存偏移值 offset 去内存中取指针 addr；
最后通过 Atomic::cmpxchg(x, addr, e) 实现 CAS。
3. CAS 实现原子操作的三大问题
3.1 ABA 问题
并发环境下，假设初始条件是 A，去修改数据时，发现是 A 就会执行修改。但是看到的虽然是 A，中间可能发生了 A 变 B，B 又变回 A 的情况。此 A 已经非彼 A，数据即使成功修改，也可能有问题。
怎么解决 ABA 问题？
加版本号。
每次修改变量，都在这个变量的版本号上加1，这样发生 A->B->A 时，虽然 A 的值没变，但是它的版本号已经变了，再判断版本号就会发现此时的 A 已经被改过了。参考乐观锁的版本号，这种做法可以给数据带上了一种时效性的检验。
Java 提供了 AtomicStampReference 类，它的 compareAndSet 方法首先检查当前的对象引用值是否等于预期引用，并且当前版本号（Stamp）标志是否等于预期标志，如果全部相等，则以原子方式将引用值和版本号标志的值更新为给定的更新值。
3.2 循环性能开销
自旋 CAS，如果一直循环执行，一直不成功，会给 CPU 带来非常大的执行开销。
怎么解决循环性能开销问题？
在 Java 中，很多使用自旋 CAS 的地方，会有一个自旋次数的限制，超过一定次数，就停止自旋。
3.3 只能保证一个变量的原子操作
CAS 保证的是对一个变量执行操作的原子性，如果对多个变量操作时，CAS 目前无法直接保证操作的原子性的。
怎么解决只能保证一个变量的原子操作问题？
- 可以考虑改用锁来保证操作的原子性
- 可以考虑合并多个变量，将多个变量封装成一个对象，从 Java 1.5 开始，JDK 提供了 AtomicReference 类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行 CAS 操作。
4. synchronized、volatile、CAS 比较
（1）synchronized 是悲观锁，属于抢占式，会引起其他线程阻塞。
（2）volatile 提供多线程共享变量可见性和禁止指令重排序优化。
（3）CAS 是基于冲突检测的乐观锁（非阻塞）。