第四章无锁编程 (Lock-Free Programming)

一、导读

1.1 本章学习目标

理解无锁（Lock-Free）和无等待（Wait-Free）编程的概念及其与基于锁的编程的区别

掌握 Compare-and-Swap（CAS）操作的原理及其在无锁算法中的核心作用

学会设计和分析简单的无锁数据结构（如无锁栈、无锁队列）

理解无锁编程中的内存管理问题（如 ABA 问题）及其解决方案

掌握无锁编程的正确性标准：线性一致性（Linearizability）

理解无锁编程的优势（避免死锁、优先级反转）和劣势（实现复杂、ABA 问题）

了解无锁编程在实际系统中的应用场景

1.2 为什么本章如此重要

基于锁的并发编程虽然直观，但存在几个根本性的问题：死锁（多个线程互相等待对方持有的锁）、优先级反转（高优先级线程被低优先级线程间接阻塞）、convoy 效应（大量线程排队等待一把锁）。这些问题不仅影响程序的正确性，还严重影响性能和可伸缩性。

无锁编程提供了一种根本性的替代方案：不使用锁，而是通过原子操作（如 CAS）来实现线程间的协调。无锁程序不会发生死锁（因为没有锁可以等待），不会发生优先级反转（因为没有线程被阻塞），也不会发生 convoy 效应（因为线程不需要排队等待）。

然而，无锁编程也带来了新的挑战：算法设计更加复杂，正确性证明更加困难，内存管理问题（如 ABA 问题）需要特殊处理。无锁编程不是万能的——在某些场景下，基于锁的方案可能更简单、更高效。

Herlihy 和 Shavit 在本章中系统地介绍了无锁编程的概念、技术和工具。他们从无等待和锁自由的定义出发，通过具体的数据结构实现来展示无锁编程的方法。这些内容对于理解现代并发数据结构的设计至关重要。

1.3 核心问题引导

什么是无锁（Lock-Free）和无等待（Wait-Free）？它们之间有什么区别？

CAS 操作如何实现？它在无锁算法中扮演什么角色？

如何实现一个无锁的栈或队列？关键的设计挑战是什么？

什么是 ABA 问题？如何解决它？

无锁编程一定比基于锁的编程更快吗？在什么场景下不是？

无锁编程的正确性如何验证？线性一致性意味着什么？

二、核心概念详解

2.1 无锁与无等待的定义

无锁（Lock-Free）和无等待（Wait-Free）是并发对象的两个重要属性，它们描述了系统在没有单个线程失败或暂停时仍能取得进展的能力。

一个并发对象是锁自由的（Lock-Free），如果无论各个线程的执行速度如何，总有一些线程能够在有限步内完成操作。换句话说，系统作为一个整体总是能取得进展，即使某些个别线程可能"饥饿"。

一个并发对象是无等待的（Wait-Free），如果每个线程都能够在有限步内完成操作，无论其他线程的执行速度如何。无等待是比锁自由更强的保证：它不仅要求系统整体能取得进展，还要求每个线程都能取得进展。

两者的关系是：无等待 ⟹ 锁自由 ⟹ 线程安全。无等待的对象一定是锁自由的，但锁自由的对象不一定是无等待的。在无锁（锁自由）的栈中，某些线程的操作可能因为不断重试而延迟，但总有一些线程能成功。在无等待的栈中，每个线程的操作都能在有限步内完成。

2.2 Compare-and-Swap（CAS）

Compare-and-Swap（CAS）是无锁编程中最核心的硬件原语。CAS(addr, expected, new) 原子地执行以下操作：读取 addr 处的值，如果等于 expected，则将 addr 处的值更新为 new；返回原来的值（或布尔值表示是否成功）。

CAS 的强大之处在于它提供了一种"乐观并发控制"的机制：线程先假设没有冲突，修改数据，然后通过 CAS 来检查是否真的有冲突。如果没有冲突（CAS 成功），修改生效；如果有冲突（CAS 失败），线程重试。

CAS 的典型使用模式是"读-改-写"循环：

do {
  old = *addr;
  new = modify(old);
} while (!CAS(addr, old, new));

CAS 在不同架构上有不同的名称：x86 上的 cmpxchg，Java 中的 AtomicReference.compareAndSet()，C++ 中的 atomic::compare_exchange_strong()。

CAS 的一个限制是它只能原子地操作一个内存位置。如果需要同时原子地更新多个位置，需要使用更复杂的机制（如事务内存或多字 CAS）。

2.3 无锁栈的实现

无锁栈（Lock-Free Stack）是无锁数据结构的经典案例。它使用 CAS 来实现无锁的 push 和 pop 操作。

栈使用链表实现，top 指针指向栈顶节点。

push 操作：

void push(T value) {
  Node* newNode = new Node(value);
  newNode->next = top.load();
  while (!top.compare_exchange_weak(newNode->next, newNode));
}

pop 操作：

T pop() {
  Node* oldTop = top.load();
  while (true) {
    if (oldTop == nullptr) throw EmptyException();
    Node* next = oldTop->next;
    if (top.compare_exchange_weak(oldTop, next)) {
      T value = oldTop->value;
      delete oldTop;
      return value;
    }
  }
}

这个实现的关键观察是：push 操作只需要修改 top 指针，而新节点的 next 在 CAS 失败时自动更新为最新的 top（这就是为什么 newNode->next 作为 expected 参数传入 CAS）。

这个简单实现存在一个问题：在 pop 操作中，读取 oldTop->next 和 CAS 之间，另一个线程可能已经 pop 了 oldTop 并将其释放（delete），导致 oldTop 成为悬空指针。这是无锁数据结构中的经典内存管理问题。

2.4 ABA 问题

ABA 问题是无锁编程中最棘手的挑战之一。它发生在 CAS 操作中：线程 1 读取地址的值为 A，准备将其更新为 B；在线程 1 执行 CAS 之前，线程 2 将值从 A 改为 B，然后又改回 A；线程 1 的 CAS 成功（因为值仍然是 A），但实际上值已经发生了变化。

在链表数据结构中，ABA 问题可能导致严重的错误。例如，在线程 1 读取 oldTop->next 和 CAS 之间，另一个线程可能 pop 了节点 A，push 了新的节点，然后又 push 了一个节点（其地址恰好是被释放的 A 的地址被重新分配）。线程 1 的 CAS 成功，但 oldTop->next 可能已经指向了无效的位置。

解决 ABA 问题的常见方法包括：

标记-清除（Tagged Pointer）：在指针中附加一个版本号（tag），每次修改指针时递增版本号。CAS 同时比较指针和版本号，即使指针值回到 A，版本号也不同。

延迟释放（Hazard Pointer）：使用 hazard pointer 来标记正在使用的节点，确保这些节点不会被其他线程释放。

无分配（Allocation-Free）设计：使用数组代替动态分配的节点，避免地址重用。

2.5 无锁队列的实现

Michael-Scott 队列是无锁队列的经典实现。它使用一个哑节点（dummy node）来简化边界条件的处理，维护 head 和 tail 两个指针。

入队操作：创建一个新节点，通过 CAS 将 tail->next 从 null 更新为新节点，然后通过 CAS 将 tail 更新为新节点。如果第一个 CAS 失败（说明另一个线程也在入队），重试。

出队操作：读取 head->next，通过 CAS 将 head 更新为 head->next。如果 CAS 失败，重试。

Michael-Scott 队列是锁自由的，但不是无等待的：在高争用下，某些线程可能因为 CAS 不断失败而长时间重试。但它保证了系统的整体进展——总有一些线程能成功完成操作。

三、深入分析与讨论

3.1 无锁 vs 有锁：性能对比

无锁编程并不总是比基于锁的编程更快。在低争用场景下，基于锁的方案可能更快，因为锁的获取（无争用时）只需要一次 CAS 操作，而无锁算法可能需要多次 CAS 重试。在高争用场景下，无锁方案的优势才明显——它避免了锁争用导致的线程阻塞和上下文切换。

无锁方案的另一个优势是可伸缩性：基于锁的方案在高线程数下性能可能急剧下降（所有线程竞争同一把锁），而无锁方案的性能下降通常更平缓。

但无锁方案的劣势是实现的复杂性：无锁算法需要处理重试逻辑、内存管理（ABA 问题）和内存序（Memory Ordering）等问题，代码复杂度远高于基于锁的方案。

3.2 内存管理在无锁编程中的挑战

在基于锁的编程中，内存管理相对简单：在持有锁时，可以安全地访问和释放数据结构中的节点。但在无锁编程中，一个线程可能在访问某个节点时，另一个线程已经释放了该节点。

Hazard Pointer 是一种优雅的解决方案：每个线程在访问一个节点之前，先将自己的 hazard pointer 指向该节点。释放节点时，先检查所有线程的 hazard pointer，如果没有任何线程指向该节点，才真正释放。这种方法的开销是 O(线程数) 的检查，但避免了 ABA 问题和悬空指针。

Epoch-Based Reclamation（EBR）是另一种方案：将时间划分为若干 epoch，节点在被标记为可回收后，等待两个 epoch 才真正释放（假设在两个 epoch 内，所有对旧节点的引用都已经消失）。EBR 的开销更低，但可能延迟释放。

3.3 无等待 universality

Herlihy 的无等待通用构造（Wait-Free Universality）是一个理论上的重要结果：任何可以被顺序实现的对象，都可以被无等待地实现。这个构造基于一致性数（Consensus Number）的概念：一个对象的一致性数是指它能解决一致性问题的最大线程数。

CAS 的一致性数为 2（可以解决 2 线程的一致性问题），因此基于 CAS 可以构建任意线程数的无等待对象（但效率可能不高）。这个理论结果保证了无等待编程的可行性，但实际的高效实现仍然需要针对具体问题设计专门的算法。

四、实践案例

4.1 无锁计数器

最简单的无锁数据结构：使用 CAS 实现的原子计数器。

java

class AtomicCounter {
  private AtomicInteger count = new AtomicInteger(0);
  
  public void increment() {
    count.incrementAndGet(); // 内部使用 CAS
  }
  
  public int get() {
    return count.get();
  }
}

Java 的 AtomicInteger.incrementAndGet() 在 x86 上编译为 lock xadd 指令，是真正的硬件原子操作。在高争用下，它的性能优于使用 synchronized 的计数器。

4.2 无锁链表集合

一个支持 add、contains 和 remove 操作的无锁有序链表集合。使用乐观排序策略：先不加锁地遍历链表找到目标位置，然后使用 CAS 来修改指针。

这种实现的挑战在于：遍历时节点可能被其他线程删除，需要处理悬空指针。使用 hazard pointer 或标记位（mark bit，在删除时先标记节点为"已删除"，然后再安全地释放）可以解决这个问题。

五、常见误区与注意事项

5.1 无锁总是更快

无锁编程在低争用场景下可能比基于锁的方案更慢。CAS 重试循环在争用激烈时会消耗大量 CPU 时间。选择无锁还是基于锁应该根据具体的争用程度和性能需求来决定。

5.2 忽视内存序问题

CAS 操作有不同的内存序（Memory Ordering）选项。在弱内存模型的处理器（如 ARM）上，使用错误的内存序可能导致可见性问题。默认使用 seq_cst（顺序一致性）是最安全的选择，但可能影响性能。

5.3 忽视 ABA 问题

在链表等使用指针的无锁数据结构中，ABA 问题可能导致严重的数据损坏。必须使用 tagged pointer、hazard pointer 或其他机制来解决 ABA 问题。

5.4 无锁代码难以调试

无锁代码的 bug 通常是间歇性的，难以复现和调试。编写无锁代码时，应该通过形式化推理来验证正确性，并使用工具（如 ThreadSanitizer、Relacy）来检测数据竞争。

六、本章小结

本章介绍了无锁编程的概念、技术和挑战。无锁（锁自由）保证系统整体能取得进展，无等待保证每个线程都能取得进展。CAS 是无锁编程的核心硬件原语，通过"读-改-写"循环实现乐观并发控制。无锁栈和队列是无锁数据结构的经典案例，但面临 ABA 问题和内存管理的挑战。无锁编程的优势是避免死锁和优先级反转，劣势是实现复杂且在某些场景下性能不如基于锁的方案。

七、思考题与练习

实现一个基于 CAS 的无锁计数器，比较其与基于锁的计数器在不同争用程度下的性能。

分析无锁栈实现中的 ABA 问题场景，设计一个使用 tagged pointer 的解决方案。

实现 Michael-Scott 无锁队列，验证其锁自由属性。

证明：一个只使用读-写寄存器的对象不可能实现锁自由的共识（consensus）。

实现 hazard pointer 机制，用于安全地释放无锁数据结构中的节点。

比较无锁栈和基于锁的栈在不同线程数和争用程度下的吞吐量。

设计一个无锁的有序集合，支持 add、contains 和 remove 操作。

讨论：在什么场景下，无锁编程是不合适的？给出你的判断标准。

第四章 无锁编程 (Lock-Free Programming)