并发算法 #01：CAS 与 ABA 问题

CAS（Compare-And-Swap）是无锁并发编程的基石，是一条原子指令：仅当内存值等于预期值时，才将其更新为新值。Java 的 AtomicInteger、ConcurrentHashMap、无锁队列均以 CAS 构建。本文深入 CAS 的硬件实现、ABA 问题及修复方案，以及无锁算法的三个层次。

相关文章：AQS（AbstractQueuedSynchronizer） · MVCC（多版本并发控制） · 无锁队列（Michael-Scott Queue）

目录

CAS 原理

CAS(addr, expected, new_value) -> bool

语义（原子执行，不可被中断）：
  if *addr == expected:
      *addr = new_value
      return true    // 成功
  else:
      return false   // 失败（*addr 被别人改了）

x86 硬件实现

; LOCK CMPXCHG：x86 的原子 CAS 指令
; 比较 rax（期望值）与 [rdi]（内存地址中的值）
; 相等则将 [rdi] 更新为 rsi（新值），否则将 [rdi] 加载到 rax

LOCK CMPXCHG [rdi], rsi

; LOCK 前缀：锁住内存总线（或利用缓存一致性协议 MESI），
; 确保其他核心在本指令执行期间无法读写 [rdi]

ARM 的 LL/SC（Load-Link / Store-Conditional）

; ARM 没有 CMPXCHG，用 LL/SC 实现：
LDXR  x0, [x1]       ; Load-Exclusive: 读内存并标记"监视"
CMP   x0, x2         ; 比较期望值
B.NE  fail
STXR  w3, x4, [x1]   ; Store-Conditional: 若监视未中断则写入
CBNZ  w3, retry      ; w3 != 0 表示被中断（伪失败），重试

伪失败（Spurious Failure）：

ARM 的 STXR 可能因无关原因失败（如中断、上下文切换），
即使内存值未被其他线程修改
→ 软件必须处理重试，不能把失败当作"值已被修改"
→ Java 等语言的 CAS 封装内部处理了 ARM 的重试

Java 中的 CAS

JDK 8 及以前：Unsafe

// sun.misc.Unsafe（非公开 API，JDK 内部使用）
boolean compareAndSwapInt(Object obj, long offset, int expected, int update)

// AtomicInteger 内部：
private volatile int value;
private static final long valueOffset;

static {
    valueOffset = unsafe.objectFieldOffset(AtomicInteger.class.getDeclaredField("value"));
}

public final boolean compareAndSet(int expect, int update) {
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

JDK 9+：VarHandle（推荐）

// VarHandle：更安全、更灵活的低层内存访问
VarHandle vh = MethodHandles.lookup()
    .findVarHandle(MyClass.class, "value", int.class);

// CAS：compareAndSet(obj, expected, newValue)
boolean success = vh.compareAndSet(obj, 0, 1);

// 也支持 getAndAdd、getAndSet 等原子操作
int old = (int) vh.getAndAdd(obj, 1);

用 CAS 实现计数器

// 无锁计数器（等价于 AtomicInteger.incrementAndGet）
public int increment(AtomicInteger counter) {
    while (true) {
        int current = counter.get();       // 读当前值（volatile 读）
        int next    = current + 1;
        if (counter.compareAndSet(current, next)) {
            return next;                   // CAS 成功，返回新值
        }
        // CAS 失败：有其他线程并发修改了 counter
        // 循环重试（spin）
    }
}

执行追踪（两线程并发 increment）：

线程1读 current=5，线程2读 current=5
线程1 CAS(5→6)：成功，counter=6
线程2 CAS(5→6)：失败（counter已是6，不等于5）
  → 线程2 重新读 current=6，CAS(6→7)：成功
最终 counter=7 ✅（等效于两次串行 increment）

ABA 问题

场景：无锁栈的 Pop

初始栈（链表）：head → A → B → C

线程1（慢）：
  读 head=A，记录 expected=A
  准备 CAS(head, A, B)（把 head 从 A 改为 B）
  被 OS 调度出去...

线程2（快）：
  Pop A：CAS(head, A, B) 成功，head=B
  Pop B：CAS(head, B, C) 成功，head=C
  Push A：CAS(head, C, A) 成功，head=A（注意：A.next 已被改为 C，不再指向 B！）

线程1恢复：
  执行 CAS(head, A, B)
  检查 head==A？ 是！（A 回来了）
  CAS 成功：head=B

但此时 B 已经被线程2 释放/重用了！
head 指向 B，而 B.next 已经是 ??? 的野指针
→ 栈结构损坏 ← 这就是 ABA 问题

根本原因：

CAS 只能检测"值是否相同"，不能检测"中间是否发生过变化"
A → B → A 的过程中，最终值虽与初始相同，但语义已经改变

修复 ABA：AtomicStampedReference

// AtomicStampedReference：将值和版本号（stamp）一起原子更新
AtomicStampedReference<Node> head = new AtomicStampedReference<>(nodeA, 0);

// 读取时同时获取 stamp
int[] stampHolder = new int[1];
Node current = head.get(stampHolder);   // current=A, stamp=0
int   stamp   = stampHolder[0];

// CAS：要求值和 stamp 都匹配才成功
boolean success = head.compareAndSet(
    current,      // expected reference
    newHead,      // new reference
    stamp,        // expected stamp
    stamp + 1     // new stamp
);

// 即使 A 被 B 替换又换回 A，stamp 也从 0 → 1 → 2，CAS 会失败 ✅

执行追踪（修复后）：

线程1读 head=A, stamp=0
线程2: 弹 A(stamp 0→1)，弹 B(stamp 1→2)，推 A(stamp 2→3)
线程1: CAS(A,B, stamp=0, stamp=1)
  检查 head==A：是
  检查 stamp==0：否！（stamp 已是 3）
  CAS 失败 ✅ → 线程1重新读，发现 A 回来了但 stamp 不对

无锁算法的三个层次

从强到弱（越强越难实现）：

Wait-Free（无等待，最强）：
  每个线程无论其他线程如何运行，都能在有限步内完成操作
  实现极难，实际系统中很少见
  例：简单的原子读写（AtomicInteger.get/set）

Lock-Free（无锁，中等）：
  整体系统（所有线程合起来）始终在进展
  但单个线程可能被饥饿（理论上无限 CAS 失败）
  实践中最常用，Java AtomicInteger.incrementAndGet 是 Lock-Free
  
  证明方法：
    若 Thread A 的 CAS 失败，说明有 Thread B 成功 → 整体有进展
    系统不会"整体卡住"

Obstruction-Free（无阻塞，最弱）：
  只有在"单独运行"时（无竞争）才能保证完成
  存在竞争时允许活锁（所有线程都在重试，没有一个完成）
  需要额外的"竞争管理"机制（如随机退避）配合使用

异常场景

CAS 自旋浪费 CPU

场景：高并发下，大量线程竞争同一 CAS，大多数失败重试
  线程数=100，每次只有 1 个成功 → 其余 99 个白转
  CPU 利用率高（全在转），但有效吞吐低

解法：
  1. 退避（Backoff）：失败后等待随机时间再重试
     Thread.sleep(random(1, maxWait))
  
  2. 分段（Striping）：将一个计数器拆成多个，各线程操作不同分段
     Java LongAdder：内部维护多个 Cell，竞争时分散到不同 Cell
     最终值 = 所有 Cell 的 sum（读时有轻微不精确）

  3. 减少共享：评估是否真的需要全局原子计数

volatile + CAS 的内存序

// Java volatile：每次读都从主内存读（禁止缓存），每次写都刷到主内存
// volatile 写 happens-before volatile 读（相同变量）

// CAS 默认隐含了 volatile 语义（顺序一致）
// 但 VarHandle 提供了不同强度的内存序（用于性能优化）：

// 普通（无序）：
int v = (int) vh.get(obj);              // relaxed read
// 获取语义（acquire）：
int v = (int) vh.getAcquire(obj);       // 后续操作不能重排到这之前
// 释放语义（release）：
vh.setRelease(obj, 1);                  // 之前的操作不能重排到这之后
// 顺序一致（最强，默认）：
vh.setVolatile(obj, 1);

// 实践：lock-free 数据结构通常需要 acquire/release 配对
// 可观察到一致性，但比 volatile 略快（避免全局内存屏障）

参考资料

• Herlihy, M. (1991). Wait-free synchronization
• Michael, M.M. (2004). Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects
• Java 并发编程实战（Brian Goetz 等）第 15 章
• OpenJDK Unsafe 源码：src/java.base/share/classes/sun/misc/Unsafe.java