Jakob Jenkov 2021-06-16
比较并交换（Compare and Swap，简称 CAS）是一种在设计并发算法时常用的技术。其基本原理是：将一个变量的当前值与期望值进行比较，如果两者相等，则用一个新值替换该变量的值。
虽然“比较并交换”听起来可能有点复杂，但一旦理解了它的机制，其实相当简单。本文将进一步详细阐述这一主题。
顺便提一下，CAS 是 “Compare and Swap” 的缩写。如果你在某些关于并发的文章或视频中看到 CAS，很可能指的就是比较并交换操作。
用于“检查后执行”场景的比较并交换
在并发算法中，一种常见的模式是“检查后执行”（Check Then Act）。这种模式指的是代码首先检查某个变量的值，然后根据该值采取相应操作。
下面是一个简单的例子：
public class ProblematicLock {
private volatile boolean locked = false;
public void lock() {
while(this.locked) {
// 忙等待 - 直到 this.locked == false
}
this.locked = true;
}
public void unlock() {
this.locked = false;
}
}
这个代码并不是一个多线程锁的完全正确实现，因此我将其命名为 ProblematicLock（有问题的锁）。我特意创建这个有缺陷的实现，是为了说明如何通过比较并交换功能来修复其问题。
lock() 方法首先检查成员变量 locked 是否等于 false，这一步是在 while 循环中完成的。如果 locked 为 false，lock() 方法就会退出 while 循环，并将 locked 设置为 true。换句话说，lock() 方法先检查 locked 变量的值，然后基于这个检查结果执行操作 —— 先检查，再执行。
如果多个线程同时访问同一个 ProblematicLock 实例，上述 lock() 方法就无法保证正常工作。例如：
- 线程 A 检查
locked的值，发现它是false（期望值），于是退出while循环准备执行后续操作。 - 如果在线程 A 将
locked设置为true之前，线程 B 也检查了locked的值，同样会看到false，也会退出while循环。
这就形成了典型的竞态条件（Race Condition）。
“检查后执行”必须是原子的
为了在多线程应用中正常工作（避免竞态条件），“检查后执行”操作必须是原子的。所谓原子，是指检查和执行这两个动作必须作为一个不可分割的代码块来执行。任何开始执行该代码块的线程都必须在没有其他线程干扰的情况下完成整个操作。同一时间，不能有多个线程同时执行这个原子块。
在 Java 中，使一段代码变为原子的一种简单方法是使用 synchronized 关键字。更多细节请参阅我的 Java synchronized 教程。下面是前面的 ProblematicLock 类，其 lock() 方法通过 synchronized 关键字变成了原子操作：
public class ProblematicLock {
private volatile boolean locked = false;
public synchronized void lock() {
while(this.locked) {
// 忙等待 - 直到 this.locked == false
}
this.locked = true;
}
public void unlock() {
this.locked = false;
}
}
现在，lock() 方法被同步了，因此在同一 MyLock 实例上，同一时间只能有一个线程执行它。这样，lock() 方法就有效地变成了原子操作。
阻塞线程代价高昂
当两个线程同时尝试进入 Java 中的同步块时，其中一个线程会被阻塞，而另一个线程则被允许进入同步块。当进入同步块的线程退出后，等待的线程才会被允许进入。
如果线程被允许进入同步块，那么进入的开销并不大。但如果因为另一个线程已经在同步块中执行而导致当前线程被阻塞，那么这种阻塞操作的代价就比较高。
此外，当同步块释放后，你无法确切知道被阻塞的线程何时会被唤醒。这通常由操作系统或执行平台来协调。当然，不会花几秒甚至几分钟才唤醒线程，但被阻塞的线程仍会浪费一些本可用于访问共享数据结构的时间。如下图所示：
硬件提供的原子比较并交换操作
现代 CPU 内置了对原子比较并交换操作的支持。在某些情况下，比较并交换操作可以替代同步块或其他阻塞型数据结构。CPU 保证同一时间只有一个线程（即使跨多个 CPU 核心）可以执行比较并交换操作。本教程后面会给出代码示例。
使用硬件/CPU 提供的比较并交换功能，而不是依赖操作系统或执行平台提供的同步、锁、互斥体等机制，可以避免 OS 层面对线程阻塞和唤醒的管理。这减少了线程等待执行比较并交换操作的时间，从而降低了拥塞，提高了吞吐量。如下图所示：
如图所示，尝试进入共享数据结构的线程永远不会被完全阻塞。它会不断尝试执行比较并交换操作，直到成功并获得对共享数据结构的访问权限。这种方式最小化了线程进入共享数据结构前的延迟。
当然，如果线程长时间重复执行比较并交换操作而未能成功，可能会浪费大量 CPU 周期，这些周期本可用于其他任务（其他线程）。但在很多情况下并非如此，这取决于共享数据结构被其他线程占用的时间长短。实践中，共享数据结构通常不会被长时间占用，因此上述情况并不常见。但具体情况仍取决于代码、数据结构、线程数量、系统负载等因素。相比之下，被阻塞的线程完全不占用 CPU。
Java 中的比较并交换
从 Java 5 开始，你可以通过 java.util.concurrent.atomic 包中的一些新原子类，访问 CPU 级别的比较并交换功能。这些类包括：
- AtomicBoolean
- AtomicInteger
- AtomicLong
- AtomicReference
- AtomicStampedReference
- AtomicIntegerArray
- AtomicLongArray
- AtomicReferenceArray
使用 Java 5+ 内置的比较并交换功能，而不是自己实现，其优势在于可以利用应用程序运行所在 CPU 的底层比较并交换指令，从而使你的比较并交换代码运行得更快。
比较并交换作为守卫（Guard）
比较并交换功能可用于保护临界区（critical section），从而防止多个线程同时执行该临界区。
下面是一个使用 AtomicBoolean 类实现前述 lock() 方法的例子，它利用比较并交换功能作为守卫（确保每次只有一个线程能退出 lock() 方法）：
public class CompareAndSwapLock {
private AtomicBoolean locked = new AtomicBoolean(false);
public void unlock() {
this.locked.set(false);
}
public void lock() {
while(!this.locked.compareAndSet(false, true)) {
// 忙等待 - 直到 compareAndSet() 成功
}
}
}
注意，这里的 locked 变量不再是 boolean 类型，而是 AtomicBoolean 类型。该类提供了一个 compareAndSet() 方法，它会将 AtomicBoolean 实例的当前值与期望值进行比较，如果相等，则用新值替换它。compareAndSet() 方法在成功交换值时返回 true，否则返回 false。
在上面的例子中，compareAndSet() 方法将 locked 的值与 false 比较，如果确实是 false，就将其设置为 true。
由于同一时间只有一个线程能执行 compareAndSet() 方法，因此只有一个线程能看到 AtomicBoolean 的值为 false，并成功将其改为 true。因此，每次调用 unlock() 方法（通过 locked.set(false) 解锁）后，只有一个线程能退出 while 循环。
比较并交换作为乐观锁机制
比较并交换也可以用作**乐观锁（Optimistic Locking）**机制。乐观锁允许多个线程同时进入临界区，但在临界区结束时，只允许其中一个线程提交其修改。
下面是一个使用乐观锁策略的并发计数器类示例：
public class OptimisticLockCounter {
private AtomicLong count = new AtomicLong();
public void inc() {
boolean incSuccessful = false;
while(!incSuccessful) {
long value = this.count.get();
long newValue = value + 1;
incSuccessful = this.count.compareAndSet(value, newValue);
}
}
public long getCount() {
return this.count.get();
}
}
注意，inc() 方法首先从 count 变量（一个 AtomicLong 实例）中获取当前计数值，然后基于旧值计算出新值。最后，通过调用 compareAndSet() 尝试将新值写回 AtomicLong 实例。
如果 AtomicLong 的值自上次读取以来未被其他线程修改，compareAndSet() 就会成功。但如果在此期间另一个线程已经递增了该值，compareAndSet() 就会失败，因为期望值（value）已不再等于 AtomicLong 中存储的当前值。此时，inc() 方法会再次进入 while 循环，重新尝试递增操作。