什么是无锁编程（lock-free programming）和 CAS？解释 ABA 问题以及何时使用它。

Question

IT Interview Practice · Accepted Answer

**无锁编程在不使用互斥量的情况下协调线程，使用原子的 compare-and-swap（CAS）循环，使得即便其他线程停滞，至少总有一个线程能取得进展。**没有线程会因另一个线程持有锁而被阻塞。

## CAS

**Compare-and-swap** 只有在某个位置仍持有预期的旧值时，才原子地把它设为新值；否则失败并让你重试。它是无锁栈、队列和计数器背后的原语。

```text
CAS(addr, expected, new):
  if *addr == expected: *addr = new; return true   # 原子的，不可分割
  else: return false
```

```java
// 通过 CAS 重试循环实现无锁自增
int old, next;
do {
    old  = value.get();
    next = old + 1;
} while (!value.compareAndSet(old, next));  // 如果别人抢先了就重试
```

## ABA 问题

CAS 只检查值是否仍是预期的那个 —— 而不检查它是否从未改变过。如果它在你的读取和 CAS 之间经历了 A → B → A，CAS 会成功，但世界已经在你脚下变了（例如一个被释放并重用的节点）。

```text
线程 1: 读 A ............... CAS(A→X) 成功 ✗ (但链表已改变!)
线程 2:      弹出 A，压入 B，再压入 A
```

**修复**：把指针与一个版本计数器配对（`AtomicStampedReference`、带标记的指针），使 带标记1的A ≠ 带标记2的A，或者使用 hazard pointer / epoch 回收来保证内存安全。

## 何时使用

- **使用**于热点、细粒度的共享状态（计数器、单生产者队列），当锁争用占主导，或当一个线程绝不能阻塞时（实时系统、信号处理程序）。
- **避免**把它当作默认选择：它很难做对，容易引入 ABA 和内存排序 bug，而且在低争用下往往并不比一把好的互斥量更快。

## 为什么这很重要

无锁结构提供了进展保证，并避免死锁和优先级反转，但正确性的门槛很高。懂得 CAS、ABA 和回收问题，表明你能在内存模型层面进行推理 —— 而且，至关重要的是，知道何时*不该*动用它。

CAS

ABA 问题

相关问题

何时使用

为什么这很重要