- title: Java中CAS（Compare And Swap，比较和交换）算法的技术原理简述
- date: 2021/8/14
文章目录
CAS全称 Compare And Swap，是一种无锁算法。在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步。java.util.concurrent包中的原子类就是通过CAS来实现了乐观锁。
这里简要提一下乐观并发策略。
实现线程安全的方法主要有三大手段：阻塞同步（也叫互斥同步），非阻塞同步（基于冲突检测的乐观并发策略）以及无同步方案；
从解决问题的方式上，互斥同步属于一种悲观的并发策略，无论共享的数据是否会出现竞争，它都会进行加锁（这里讨论的是概念模型，实际上虚拟机会优化掉很大一部分不必要的加锁（锁消除）），这会导致用户态到核心态转换、维护锁计数器和检查是否有被阻塞的线程需要被唤醒等开销。
随着硬件指令集的发展，我们有了另一个选择：基于冲突检测的乐观并发策略，通俗地说就是不管风险，先进行操作，如果没有其它线程争用共享数据，那么操作就直接成功了；如果共享的数据的确被争用，产生了冲突，再进行其它的补偿措施，最常用的补偿措施是不断地重试，直到出现没有竞争的共享数据为止。这种乐观并发策略的实现不再需要将线程阻塞挂起，因此这种同步操作被称为非阻塞同步，使用这种措施的代码也常被称为无锁（Lock-Free）编程。
这里提到硬件指令集，是因为我们必须要求操作和冲突检测两个步骤具有原子性。那么靠什么实现原子性呢？这里如果使用互斥同步来保证就完全失去了意义了，所以我们只能靠硬件来实现这件事情，硬件保证某些从语义上看起来需要多次操作的行为可以只通过一条处理器指令还完成，这类指令常用的有：
- 测试并设置（Test-and-Set）;
- 获取并增加（Fetch-and-Increment）;
- 交换（Swap）;
- 比较并交换（Compare-and-Swap，即CAS）；
- 加载连接/条件储存（Load-Linked/Stored-Conditional，即LL/SC）；
其中后两条指令是现代处理器新增的，其中在Java中最终暴露的是CAS操作。
CAS指令需要三个操作数：
- 需要读写的变量的内存位置 V；
- 旧的预期值 A；
- 准备设置的新值 B；
当且仅当 V 的值等于 A 的值时，CAS通过原子操作用新值 B 来更新V的值（“比较+更新”是一个原子操作，执行期间不会被其它线程打断），否则不会执行更新。一般情况下，“更新”是一个不断重试的操作。不管是否更新了V的值，都会返回V的旧值。
下面通过查看AtomicInteger的自增函数incrementAndGet()的源码，发现自增函数底层调用的是Unsafe.getAndAddInt()。但是JDK本身只有Unsafe.class，因此可以通过OpenJDK 8 来查看Unsafe的源码；
//AtomicInteger.java
private static final long valueOffset;
static {
try {
//获取value变量的偏移量, 赋值给valueOffset
valueOffset = unsafe.objectFieldOffset
(AtomicInteger.class.getDeclaredField("value"));
} catch (Exception ex) { throw new Error(ex); }
}
/**
* Atomically increments by one the current value.
*
* @return the updated value
*/
//执行value++操作
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
private volatile int value;
/**
* Creates a new AtomicInteger with the given initial value.
*
* @param initialValue the initial value
*/
public AtomicInteger(int initialValue) {
value = initialValue;
}
//Unsafe.class decompiled
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
//------------ OpenJDK 8 -----------------
//Unsafe.java
//获取内存地址为obj+offset的变量值, 并将该变量值加上delta
public final int getAndAddInt(Object o, long offset, int delta) {
int v;
do {
//通过对象和偏移量获取变量的值
//由于volatile的修饰, 所有线程看到的v都是一样的
v = getIntVolatile(o, offset);
/*while中的compareAndSwapInt()方法尝试修改v的值,
具体地, 该方法也会通过obj和offset获取变量的值，如果这个值和v不一样, 说明其他线程修改了obj+offset地址处的值,
此时compareAndSwapInt()返回false, 继续循环；
如果这个值和v一样, 说明没有其他线程修改obj+offset地址处的值,
此时可以将obj+offset地址处的值改为v+delta, compareAndSwapInt()返回true, 退出循环。
Unsafe类中的compareAndSwapInt()方法是原子操作,
所以compareAndSwapInt()修改obj+offset地址处的值的时候不会被其他线程中断
*/
} while (!compareAndSwapInt(o, offset, v, v + delta));
return v;
}
CAS实现原子操作的三大问题：
ABA问题。因为CAS 在操作值时，会检查值有没有变化，如果没有变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生，但实际却变化了。
解决思路：使用版本号，在变量前面追加版本号，每次变量更新的时候把版本号加1.从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志设置为给定的新值。
循环时间开销大：自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。
解决思路：指定自旋次数或者自适应自旋。并且如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：1. 延迟流水线执行指令，使CPU不会消耗过多的执行资源；2. 避免在退出循环的时候因内存顺序冲突而引起CPU流水线被清空。
只能保证一个共享变量的原子操作：锁机制保证了只有获得锁的线程才能操作锁定的内存区域。JVM内部实现了很多种锁机制，除了偏向锁，JVM实现锁的机制都用了循环CAS，即当一个线程向进入同步块的时候使用循环CAS的方式来获取锁，当它退出同步时，使用循环CAS释放锁。但是，对一个共享变量执行操作时，CAS能够保证原子操作，但是对多个共享变量操作时，CAS是无法保证操作的原子性的。
解决思路：Java从1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个对象里进行CAS操作。
参考资料：
- 《Java并发编程艺术》
- 《深入理解Java虚拟机》
- 不可不说的Java“锁”事 - 美团技术团队 (meituan.com)
- Java Unsafe类中的getAndAddInt方法解释_