#CAS 原理与 ABA 问题

候选人小冯在面试京东 P6 时，面试官问道：

"并发编程中，AtomicInteger 的 incrementAndGet() 是怎么实现的？"

小冯说："用了 CAS..."面试官追问："什么是 CAS？它的底层是怎么实现的？"

小冯说："Compare And Swap..."面试官继续追问："CAS 有什么问题？ABA 问题是什么？怎么解决？"

小冯支支吾吾答不上来了...

#一、核心问题：CAS 原理 🔴

#1.1 问题拆解

第一层：概念（什么是 CAS？）
  "CAS 是什么？它解决了什么问题？"
  考察点：Compare And Swap、乐观锁思想、无锁算法

第二层：底层实现（怎么做？）
  "CAS 在 CPU 层面是怎么实现的？x86 的 CMPXCHG 指令是什么？"
  考察点：总线锁、CMPXCHG、lock 前缀

第三层：ABA 问题（有什么坑？）
  "什么是 ABA 问题？什么场景下会出问题？"
  考察点：是否理解 CAS 的局限性、实战经验

第四层：解决方案（怎么解决？）
  "ABA 问题有哪些解决方案？版本号机制、AtomicStampedReference、AtomicMarkableReference 的区别是什么？"
  考察点：解决方案的权衡与适用场景

#1.2 ❌ 错误示范

候选人原话 A："CAS 就是乐观锁，不需要加锁，性能更好。"

问题诊断：这个说法太笼统。CAS 的"乐观"体现在假设没有竞争，但如果竞争激烈（多个线程同时 CAS 失败），会导致大量自旋重试，反而比加锁更慢。乐观锁适用于低竞争场景。

候选人原话 B："ABA 问题就是值从 A 变成 B 再变回 A，CAS 会认为没变。"

问题诊断：这个理解正确，但不够完整。ABA 问题的真正危害在于：如果值从 A 变成 B 再变回 A，在这个过程中如果有其他线程做了一些依赖 A 状态的中间操作，这些操作的结果会被覆盖。

#1.3 标准回答

#P5 级别：CAS 概念与原子类应用

CAS（Compare And Swap）：

CAS 是一种无锁算法，包含三个操作数：

• 内存位置 V：要更新的变量的地址
• 期望值 A：认为当前应该持有的值
• 新值 B：要写入的新值

CAS 的语义是：只有当 V 的当前值等于 A 时，才将 V 更新为 B；否则什么都不做。整个过程是原子的。

AtomicInteger 的 incrementAndGet() 实现：

// JDK 8 的 AtomicInteger.incrementAndGet()
public final int incrementAndGet() {
    return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

// Unsafe.getAndAddInt 的 CAS 循环
public final int getAndAddInt(Object o, long offset, int delta) {
    int expected;
    do {
        expected = this.getIntVolatile(o, offset);  // 获取当前值（volatile 读）
    } while (!this.compareAndSwapInt(o, offset, expected, expected + delta));
    // CAS 失败？自旋重试
    return expected;
}

这个 do-while 循环会一直重试，直到 CAS 成功。线程不会阻塞，而是在用户态自旋。

#P6 级别：底层实现与 CPU 指令

x86 架构的 CAS 实现：

CAS 在 x86 上对应 lock cmpxchg 指令（Compare and Exchange）：

; EAX = expected, [ebx+offset] = memory location, ECX = new value
lock cmpxchg [ebx+offset], ecx

; 如果 [ebx+offset] == EAX，设置 [ebx+offset] = ECX，ZF = 1
; 否则，EAX = [ebx+offset]（将内存中的值加载到 EAX），ZF = 0

lock 前缀的作用：

1. 总线锁：在多核 CPU 上，发送 LOCK# 信号锁定总线，确保当前内存操作是原子的
2. 缓存一致性：使其他 CPU 的缓存行失效（类似 MESI 协议的 invalidate 广播）
3. 内存屏障：禁止后续指令重排序到 lock 操作之前

为什么需要自旋而不是一次成功？

因为 CAS 是乐观的——假设大多数时候没有竞争。但如果竞争存在（多个线程同时修改同一变量），CAS 会失败并重试。这种自旋 + CAS 的组合称为 CAS 循环。

graph TD
    A[获取期望值 A] --> B{CAS 成功?}
    B -->|是| C[写入新值 B, 返回]
    B -->|否| A
    A -->|CAS 失败| A

CAS 的性能特征：

• 单次 CAS 操作约 10~50 纳秒（跨核通信约 100 纳秒）
• 竞争激烈时，大量线程同时自旋 → CPU 空转 → 性能退化
• 适合场景：低竞争、单个变量更新、多读少写

#P7 级别：ABA 问题与三种解决方案

ABA 问题的场景：

// 栈的 push 操作
Node top = stack.top();     // 读取栈顶 A
Node newNode = new Node(B, top);  // 新节点，next 指向 A
// ← 其他线程可能在这里修改了栈！
stack.setTop(newNode);      // CAS 更新栈顶

如果线程 A 读取栈顶为 A，其他线程 P 将栈顶改为 B 再改为 A，此时线程 A 的 CAS 仍然成功（因为值为 A），但栈的结构可能已经被破坏。

解决方案一：版本号（Timestamp/Stamp）

每次修改不仅改变值，还增加版本号：

class VersionedRef<T> {
    T value;
    long version;

    boolean compareAndSet(T expectedValue, T newValue, long expectedVersion) {
        if (value == expectedValue && version == expectedVersion) {
            value = newValue;
            version++;
            return true;
        }
        return false;
    }
}

JDK 的实现：AtomicStampedReference

// AtomicStampedReference 使用 Pair 存储值和版本
private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
}

// CAS 操作同时检查引用和版本
public boolean compareAndSet(V expectedReference, V newReference,
                               int expectedStamp, int newStamp) {
    Pair<V> current = pair;
    return expectedReference == current.reference &&
           expectedStamp == current.stamp &&
           ((newReference == current.reference &&
             newStamp == current.stamp) ||
            casPair(current, Pair.of(newReference, newStamp)));
}

解决方案二：AtomicMarkableReference

使用布尔标记而非版本号，适合"一次性"操作（删除后不再使用）：

AtomicMarkableReference<String> ref = new AtomicMarkableReference<>("A", false);

// CAS：只有当 reference=A 且 mark=false 时才更新
ref.compareAndSet("A", "B", false, true);

解决方案三：Double CAS（双 CAS）

对两个相关变量同时 CAS，确保它们的原子性。但这不能从根本上解决 ABA 问题——如果两个变量的版本号同步增加，仍然可能"巧合地"通过检查。

【面试官心理】 这道题我能问到 P7 级别，是因为 CAS 涉及 CPU 指令、并发算法、ABA 问题三个维度。能说出 lock cmpxchg 指令细节的候选人说明他对底层有了解。能说出 ABA 问题的具体场景（如栈的 push/pop）的候选人说明他有实战经验，而不是只会背概念。

#1.4 追问升级

追问 1：CAS 和 synchronized 的性能差异？

维度	CAS（自旋）	synchronized（阻塞）
等待方式	自旋（CPU 空转）	阻塞（挂起线程）
适用场景	竞争不激烈、单次操作快	竞争激烈、临界区操作复杂
响应延迟	无等待延迟（立即知道结果）	线程切换延迟（OS 调度）
CPU 消耗	竞争激烈时 CPU 飙升	阻塞时不消耗 CPU
死锁风险	无	有（持有多把锁时）

一般规律：自旋超过 10 次（或阈值可动态调整）仍未成功，说明竞争激烈，应该切换到阻塞模式（轻量锁膨胀为重量锁）。

追问 2：AtomicInteger 和 LongAdder 哪个更好？

• 低竞争：AtomicInteger 更好，因为 LongAdder 有额外的 Cell 数组开销
• 高竞争：LongAdder 更好，因为分段热点减少竞争
• 需要原子加减：AtomicLong（JDK 8）或 LongAdder（JDK 8+）
• 需要复合操作：AtomicInteger（如 updateAndGet()、accumulateAndGet()）

#二、CAS 的 ABA 实战场景 🟡

#2.1 栈的并发问题

// 并发栈的 push 操作（ABA 问题演示）
public void push(E item) {
    Node<E> oldTop = top.get();       // 读取 A
    Node<E> newTop = new Node<>(item, oldTop);
    // ← 如果其他线程: A→B→A，此时 newTop.next 指向的还是旧的 A
    while (!top.compareAndSet(oldTop, newTop)) {  // CAS A→C，但 B 可能已破坏结构
        oldTop = top.get();           // 重试
        newTop = new Node<>(item, oldTop);
    }
}

解决方案：使用 AtomicStampedReference，每次 push/stack 操作都递增 stamp。

#2.2 链表操作中的 ABA

在无锁链表中删除节点时，如果被删除节点被其他线程重新插入链表，可能导致数据丢失。JDK 的 ConcurrentLinkedQueue 使用 CAS + p.markAsUnlinked() 标记避免了这个问题。

#三、生产避坑

#3.1 LongAdder 的 sum() 不是实时值

LongAdder adder = new LongAdder();
adder.add(1);
long sum = adder.sum();  // 不是原子操作！
// sum() 只是将 base + 所有 cell 的值相加
// 调用 sum() 时其他线程可能正在 add()

风险：如果用 LongAdder.sum() 作为精确计数（如库存扣减），可能有误差。应该用 LongAdder.sumThenReset() 或考虑使用 AtomicLong。

#3.2 AtomicReference 的泛型陷阱

AtomicReference<User> 只保证引用的原子性，不保证 User 内部字段的原子性：

AtomicReference<User> userRef = new AtomicReference<>(new User());

// 线程 A
userRef.get().setName("Alice");

// 线程 B
userRef.get().setAge(25);

// 虽然 userRef 的引用是线程安全的，但 User 对象的字段操作可能交错