无锁编程：原理与应用

玻尔百科

核心要点

无锁编程使用诸如比较并交换（Compare-And-Swap, CAS）之类的原子操作来管理共享数据，从而消除了基于锁的系统中存在的死锁和优先级反转问题。
ABA 问题是一个严重缺陷，即一个值发生改变后又恢复原状，这可能破坏无锁数据结构。该问题可通过使用带版本号的指针或安全内存回收等技术来解决。
正确的无锁算法需要通过指数退避等策略来管理活性，并利用内存屏障或释放-获取语义来确保适当的内存排序。
无锁技术在操作系统内核、网络驱动程序、高性能数据结构和垃圾回收器等性能关键领域至关重要。

引言

在并行计算的世界里，协调对共享资源的访问是一个核心挑战。虽然锁提供了一种直接的解决方案，但它们常常引入性能瓶颈、死锁和优先级反转，阻碍了现代多核系统的可扩展性。本文探讨了一种更为复杂的替代方案：无锁编程，这是一种无需互斥即可实现并发操作的范式。然而，放弃锁也引入了一系列新的复杂挑战，需要对硬件和算法的精妙之处有深刻的理解。本指南将带领读者全面深入地了解无锁并发。第一部分“原理与机制”将揭开核心概念的神秘面纱，从构成无锁设计基础的原子操作，到臭名昭著的 ABA 问题及其解决方案。随后，“应用与跨学科联系”部分将展示这些原理在实践中的应用，它们驱动着从操作系统内核到高性能数据库的方方面面，揭示了无锁技术在现代计算中无处不在的影响力。

原理与机制

踏入无锁编程的世界，就是踏上了一段重塑我们对并行执行理解的旅程。这是一种转变，从锁的“野蛮”方式——就像交通警察在十字路口拦下所有车辆只为让一辆车通过——转向一种更流畅、更协作的舞蹈。但这种舞蹈有着复杂的编排，并受严格规则的约束。要掌握它，我们必须首先理解其基本原理、机器的原子心跳，以及当我们放弃锁所带来的那种令人安心的确定性时出现的微妙挑战。

问题的核心：原子操作

多个线程如何在不互相阻止的情况下进行协调？想象一下，你试图更新白板上的一个公共计数器。如果你读取了数字，走回办公桌加一，然后再回来写下新数字，那么在此期间，其他人可能已经改变了它。你的更新就会是错误的。锁就像一个警卫，一次只允许一个人靠近白板。

无锁编程提出了一个不同的问题：如果你能在一个不可分割的瞬间完成整个“读取-增加-写入”序列呢？这就是原子操作的本质。它是由硬件保证一次性执行的命令，任何其他线程都无法看到其执行到一半的状态。

无锁算法中无可争议的主力是一条名为比较并交换（Compare-And-Swap，简称 CAS）的指令。它的逻辑异常简单却功能强大。它实际上是告诉计算机：“我想让你查看这个特定的内存地址。如果它的值仍然是我期望的值（比如 A），那么且仅当此时，才将其更改为这个新值（B）。并请告诉我你是否成功了。”

这是一个内置了干扰检查的条件更新。如果你准备更新时，另一个线程已将值从 A 更改为 C，你的 CAS 就会失败。它不会阻塞或等待，只会返回一个“否”，让你自己决定下一步该怎么做——通常是重试整个过程。

一些架构提供了 CAS 的一个更复杂的近亲，称为加载链接/条件存储（Load-Linked/Store-Conditional, LL/SC）。Load-Linked 指令读取一个值，并对该内存位置设置一个“监视”。相应的 Store-Conditional 只有在期间没有其他线程写入该位置时才会成功。与 CAS 不同，CAS 无法感知一个值从 A 变为 B 再变回 A 的情况，而 [LL/SC](/sciencepedia/feynman/keyword/load_linked_store_conditional) 对写入行为本身很敏感，这使其天生就能免疫无锁编程中一些最微妙的错误，我们稍后将饶有兴趣地回到这一点。

应许之地一瞥：从锁中解放

以原子操作为工具，我们可以开始构建比带锁版本具有显著优势的数据结构。这不仅仅是一个学术练习，它解决了复杂系统中真实存在的、棘手的问题。

从死锁中解放

考虑一个拥有两个资源的系统，比如一个工作队列和一个数据缓存，每个都由自己的锁 $m_Q$ 和 $m_C$ 保护。一种类型的线程可能需要先锁住缓存，再锁住队列（ $m_C \rightarrow m_Q$ ）。另一种类型可能反向操作（ $m_Q \rightarrow m_C$ ）。这就是死锁的温床。如果线程1持有 $m_C$ 并等待 $m_Q$ ，而线程2持有 $m_Q$ 并等待 $m_C$ ，它们将永远等待下去，陷入“致命拥抱”。

用计算机科学的语言来说，我们可以将其可视化为资源分配图中的一个环路，其中线程和资源是节点。一个线程在持有一个资源的同时请求另一个资源，就可能产生循环依赖。

现在，想象一下我们用一个基于 CAS 的无锁版本替换了带锁的队列。锁 $m_Q$ 就这样消失了。当一个线程想要访问队列时，它不再请求锁资源。如果它的 CAS 尝试因竞争而失败，它不会阻塞，也不会在我们的图中创建一条“等待”边。它只会重试。通过消除锁，我们在结构上打破了任何涉及该锁的死锁循环。导致我们系统冻结的那个特定的循环等待变得不可能了。这是一个深刻而优雅的解决方案：你不是去解决死锁，而是通过设计使其不复存在。

从优先级反转中解放

并发系统中的另一个隐患是优先级反转。想象一下医院的急诊室。一位高优先级病人（一个关键任务）需要一件特定的设备，而这件设备正被一位低优先级病人（一个后台日志任务）用于一个长时间的操作。更糟糕的是，一位中优先级病人（一个计算密集型任务）虽然不需要特殊设备，但因为其优先级高于日志任务，获得了医生的全部注意力（CPU）。高优先级病人只能等待，完全被一个持有资源的低优先级任务和一个消耗CPU的中优先级任务的组合所阻塞。

这种情况在实时和嵌入式系统中确实会发生。一个高优先级的中断服务程序（ISR）可能需要写入一个共享缓冲区，但锁却被一个低优先级线程持有。ISR不能阻塞——它必须立即运行并完成——所以它被卡住了。无锁数据结构再次成为英雄。通过使用原子操作，ISR可以在完全不需要锁的情况下更新缓冲区。它从不等待，因此永远不会被低优先级任务阻塞，从而确保系统对关键事件保持响应。

伊甸园之蛇：ABA 问题

到目前为止，CAS 似乎是一个完美的工具。但其简单的逻辑——“值是否仍是我期望的？”——隐藏着一个微妙而危险的陷阱。CAS 检查的是值，而不是值的历史。如果值改变了，然后又变回来了呢？

让我们来看一个关于无锁栈的经典警示故事。栈顶由一个共享指针 $T$ 管理。

Alice 的回合： 你的线程，我们称之为 Alice，想要弹出一个元素。它读取栈顶指针 $T$ ，发现它指向地址为 A 的一个节点。Alice 勤奋地记下这一点，并读取了节点 A 内部的下一个指针，该指针指向 B。她现在准备好执行 CAS(T, A, B)，将栈顶指针指向 B。
一次中断： 在 Alice 执行她的 CAS 之前，操作系统抢占了她；她被暂停去处理一个紧急电话。
一阵风驰电掣的操作： 在 Alice 离开期间，另一个线程 Bob 开始工作。
- Bob 弹出了 A。栈顶现在是 B。Bob 的线程很整洁，释放了节点 A 曾使用的内存。
- 接着 Bob 推入一个新节点 C。栈现在是 C \rightarrow B。
- 这里是命运的残酷转折：Bob 需要推入另一个新节点。他向系统请求内存，而内存分配器为了高效，给了他刚刚被释放的那个块——地址为 A 的那个。Bob 在这个相同的地址创建了一个新节点 A'，并将其推入栈。栈现在是 A' \rightarrow C \rightarrow B。
Alice 回来了： Alice 的电话打完了，她从中断的地方继续执行。她正要执行 CAS(T, A, B)。她检查 $T$ 的当前值。它指向节点 A'，该节点位于地址 A。她的 CAS 问道：“ $T$ 的值仍然是 A 吗？” 硬件查看地址后说：“是的，没错！”

CAS 成功了。Alice 将栈顶指针 $T$ 指向了 B。这样做，她刚刚从栈中抹去了节点 A' 和 C。数据结构被破坏，数据丢失。这就是臭名昭著的 ABA 问题。指针值 A 回来了，但它的含义，它的身份，已经完全改变了。这是一个严重的身份混淆案例，其中“一个指针值对应一个唯一对象状态”这一基本不变量被违反了。

驯服毒蛇：ABA 问题的解决方案

ABA 问题是一个强大的挑战，但计算机科学家们设计了几种巧妙的解决方案来驯服它。这些解决方案之所以优美，是因为它们要么增强了 CAS 使用的信息，要么从根本上解决了问题的原因：过早的内存重用。

解决方案 1：使用带标签的指针进行版本控制

最简单的想法是认识到仅凭地址 A 的信息是不够的。我们需要追踪它的历史。我们可以通过将指针与一个版本计数器（或标签）配对来实现。共享变量不再只是一个指针，而是一个包含指针及其版本的更宽的结构。

在我们的故事中，Alice 读取的将不仅仅是 A，而是 (A, version 7) 这个对。在 Bob 风驰电掣的操作期间，每次成功的 CAS 都会增加版本号。弹出 A 会将栈顶变为 (B, version 8)。推入 C 使其变为 (C, version 9)。推入 A' 使其变为 (A, version 10)。当 Alice 回来时，她的 CAS 现在检查栈顶是否仍然是 (A, version 7)。硬件查看当前的栈顶 (A, version 10)，发现版本不匹配。CAS 失败了，正如它应该的那样，灾难得以避免。

这提出了一个实际的工程问题：版本标签需要多大？如果太小，标签本身可能会“回绕”（例如，从255变回0），从而在更高层次上重新制造 ABA 问题。答案取决于最大更新速率和线程可能被暂停的时间窗口。对于一个每秒执行 $1.2 \times 10^8$ 次更新的系统，要保证在仅仅3小时内不发生回绕，就需要一个至少41位的标签！这表明无锁设计涉及真实的、定量的权衡。

解决方案 2：安全内存回收

这种方法从根源上解决问题：节点 A 的内存在 Alice 可能仍在使用它时被重用了。安全内存回收方案确保一块内存在被证明可以安全回收之前不会被循环使用。

危险指针（Hazard Pointers）：这项技术就像挂起一块“油漆未干”的牌子。在 Alice 访问地址为 A 的节点之前，她通过将 A 放在一个对所有线程可见的、每个线程专属的特殊列表中，公开声明 A 是一个“危险”指针。当 Bob 弹出 A 并试图释放它时，内存分配器会检查所有的危险指针列表。看到 Alice 的牌子，它就不会释放 A。它会将该节点放在一个“稍后释放”的列表中。现在，当 Bob 需要新内存时，他不可能得到地址为 A 的内存块。ABA 场景被阻止了，因为地址无法被重用 [@problem__id:3621240]。
基于纪元的回收（Epoch-Based Reclamation, EBR）：这是一种略有不同的、面向批处理的方法。可以把系统想象成在“纪元”或时代中运行。当一个线程进入一个关键操作时，它会记下当前的全局纪元，比如纪元7。当 Bob 弹出节点 A 时，他不会释放它。他会把它放在一个标有纪元7的退役列表中。所有在纪元7中退役的节点的内存，只有在系统中每一个线程都签到并宣布“我已经通过一个静止点，现在在纪元8或更高版本中操作”之后，才能被回收。这保证了没有线程仍然持有旧纪元的指针，从而可以安全地释放退役的节点。危险指针和基于纪元的方案都增加了开销，在它们之间进行选择涉及到性能和内存使用上的权衡。

更深层的魔法：活性与内存模型

即使解决了 ABA 问题，我们的旅程也还未结束。还剩下两个更深层次的复杂性：确保公平性和遵守硬件本身的微妙规则。

活性、饥饿和退避

一个无锁算法保证了系统作为一个整体能够取得进展。总会有某个线程能完成其操作。这是一个防止死锁的绝佳属性。然而，它对任何单个线程都没有保证。

想象一个非常拥挤的 CAS 循环。一个不幸的线程，我们称之为 Charlie，可能会持续“输掉竞争”。每当它要执行 CAS 时，另一个线程总是抢先成功。Charlie 被迫一次又一次地重试，可能永远如此。这是一种活锁或饥饿，它违反了一个称为有界等待的经典公平性条件。

解决方案不是更猛烈地推进，而是更聪明地行动。当 CAS 失败时，线程不应立即重试，而应退避并等待一小段时间。但是什么样的退避呢？如果每个人都等待相同的固定时间，他们可能会同步重试并再次冲突。优雅的解决方案是随机化指数退避。在每次连续失败后，线程在一个*指数增长的区间内等待一个随机*的时间。这使得竞争的线程去同步化，并优雅地适应竞争的程度。这就像人们试图离开一个拥挤的房间；一点随机、礼貌的谦让比所有人同时猛推更能有效地疏通堵塞。

无形的基础：内存一致性模型

最后，我们来到了最深刻、最基本的原理。所有这一切都建立在处理器如何将内存变化传达给其他处理器的基础上。程序员可能会按顺序编写两行代码：

初始化节点数据：newNode->value = 42;
发布该节点：tail->next = newNode;

我们假设任何看到第二个更改的线程也一定能看到第一个。但在像 ARM 这样的“弱序”处理器架构上，这并不能保证！为了性能，CPU 可能会对操作进行重排序，导致另一个核心在看到对 newNode->value 的写入之前就看到了 tail->next 指针的更新。一个出队线程可能因此读取到一个指向数据尚未初始化的节点的指针，从而导致灾难。

这就是内存屏障和释放-获取语义变得至关重要的地方。这些是给 CPU 和编译器的明确指令，告诉它们“不要跨越这条线重排序内存操作”。

一个释放操作（如此处发布 newNode 的存储操作）就像一个屏障。它保证程序中在其之前的所有内存写入都在该释放操作本身完成之前完成。
一个获取操作（如此处读取 newNode 的加载操作）则是一个与之配套的屏障。它保证在其之后的所有内存读取都不会在获取操作完成之前发生。

当一个线程中的 release 存储与另一个线程中对同一变量的 acquire 加载配对时，它们创建了一种 synchronizes-with（同步于）关系。这建立了一个“happens-before”（先行发生）的保证，确保了数据初始化在指针被使用之前是可见的。这是线程之间通过内存精心安排的一次正式握手，它使得无锁编程在不同硬件架构上成为可能并保持正确。

应用与跨学科联系

现在我们已经像钟表匠组装复杂时计的齿轮一样，把玩了原子操作的精巧机制，让我们退后一步，欣赏我们能制造出的奇妙时钟。这些无锁并发的概念不仅仅是理论玩具或学术奇观。它们是驱动我们现代计算世界的无形、无声的引擎。每当你搜索网页、在手机上收到通知或与基于云的应用程序交互时，你都在见证这场为摆脱锁的笨重而进行不懈探索所结出的硕果。我们所探讨的原理贯穿计算机系统的每一层，揭示了在解决千差万别的问题时方案的高度统一性。让我们踏上一段旅程，从机器核心的硅片到遍布全球的庞大数据中心，去看看这些思想在实践中的应用。

机器的心脏：操作系统与硬件接口

操作系统（OS）是共享资源的终极管理者。它是无数CPU、内存和网络请求汇集的中央总站。在这个繁忙的环境中，一个放置不当的锁就可能让整个系统陷入停顿。正是在这里，在内核的核心地带，无锁技术不仅是一种优化，更是在现代硬件高速世界中生存的必需品。

想象一个高性能网络接口控制器（NIC），它是连接服务器与互联网的网关。这样的设备每秒可以处理数千万个网络数据包。NIC（“生产者”）将已完成操作的通知——比如一个接收到的数据包——放入一个共享内存区域，通常是一个环形缓冲区。操作系统的驱动程序线程（“消费者”）随后处理这些通知。如果获取一个通知需要加锁，那么如此高的访问频率会造成一个极其严重的瓶颈，以至于服务器永远无法跟上网络流量。

这是一个无锁队列的完美应用场景。驱动程序线程可以使用原子性的比较并交换（CAS）来推进一个共享的 head 指针，以领取它们的下一个工作任务。但在这里，臭名昭著的 ABA 问题从理论领域浮现出来，变成了一个极其现实的威胁。一个驱动程序线程可能读取了头指针，然后被短暂中断，就在这短暂的停顿中，数百万个完成操作可能已经被处理，导致环形缓冲区完全回绕，头指针回到其原始值。该线程随后醒来，它的 CAS 会基于陈旧信息而成功，系统对网络状态的理解将被破坏，可能导致数据丢失或系统崩溃。

解决方案异常简单：我们给指针添加一个版本计数器，或称为“代际标签”。每当环形缓冲区回绕时，我们就增加这个标签。现在，线程的 CAS 不仅检查指针的地址，还检查复合值 $\langle \text{address}, \text{tag} \rangle$ 。要让 ABA 问题发生，指针不仅要回到相同的地址，还要回到相同的标签值，这将需要天文数字般的操作次数。工程师可以通过考虑最大可能的操作速率和最长的线程延迟，计算出这个标签所需的最小位数，确保标签不会在那个关键窗口内回绕。这项优雅的技术将一个高风险的竞态条件转变为硬件与软件之间一个健壮、高吞吐量的通信通道。

操作系统还必须管理自己的内存。当创建新进程或内核任务需要缓冲区时，必须分配内存。内存分配器上的一个全局锁会成为另一个系统范围的瓶颈。在这里，无锁结构再次提供了答案。一个简单有效的方法是使用空闲空间位图，其中每一位代表一个内存块是空闲还是在使用中。线程可以通过在位图的一个字中找到一个零位，然后对该字使用单个 CAS 原子地将该位翻转为一，来分配一个块。这个操作快如闪电，并且避免了任何中心化的锁。另一个经典方法是维护一个可用内存块的空闲列表，作为一个无锁栈。这需要小心处理 ABA 问题，通常通过使用带版本或“带戳记的”头指针，就像我们的 NIC 例子中一样。

最后，考虑观察一个运行中系统的挑战。我们如何追踪内核事件，比如调度器在进程间的切换，而又不让追踪机制本身改变系统的行为？如果我们的日志工具使用锁，它会引入延迟并改变我们希望测量的时序——一个经典的观察者效应。一个优美的无锁模式解决了这个问题。每个 CPU 都被赋予其自己的、用于日志记录的每 CPU 环形缓冲区。由于只有一个 CPU 的调度器会写入它自己的日志，我们就有了一个“单生产者”场景。为了让来自任何 CPU 的读取线程能够安全地消费这些日志，而不会看到撕裂的、部分写入的记录，我们使用了一个巧妙的序列协议。写入者在更新一条记录之前，将记录槽位中的一个序列号加一，使其变为奇数。在写入所有数据之后，它再次增加序列号，使其变为偶数。读取者在读取数据前后检查序列号。如果数字相同且为偶数，读取者就知道它拥有一个一致的快照。这种数字的优雅舞蹈为每 CPU 数据提供了安全的、无锁的、多消费者的访问，并且是高性能内核插桩的基石。

架构师的工具箱：高性能数据结构

有了硬件提供并由操作系统利用的基础原子操作，我们现在可以构建一个丰富的高性能并发数据结构工具箱。这些是现代可扩展软件的构建模块。

哈希表可能是编程中最无处不在的数据结构。制造一个可以被多个线程同时安全高效访问的哈希表是一项艰巨的挑战。一个幼稚的设计会在整个表上放置一个单一的锁，从而摧毁所有并行性的机会。一个稍好的设计可能会在每个桶上使用细粒度锁，但这增加了复杂性，并且仍然可能导致竞争。然而，一个真正的无锁哈希表，可以仅仅使用 CAS 来构建。在一种这样的设计中，表中的每个槽位都是一个原子变量，它不仅持有指向数据的指针，还持有一个表示其状态的标签：Empty（空）、Full（满）或 Tombstone（逻辑删除标记，用于标记已删除项而不破坏其他项的探测链）。插入操作变成了一个试图将 Empty 或 Tombstone 槽位变为 Full 的 CAS。删除操作则是一个将 Full 变为 Tombstone 的 CAS。即使是调整整个表的大小——一个令人生畏的并发操作——也可以无锁地完成。分配一个更大的新表，然后线程们合作地帮助将旧表中的项复制到新表中，使用 CAS 将旧槽位标记为 Moved。这种“帮助”行为是无锁设计中的一个关键主题：线程不是等待，而是为整个系统的向前推进做出贡献。虽然这些操作修改了数据结构内部的指针，但整体更新被认为是“原地”算法，因为它直接改变现有结构而不是创建一个全新的副本。

这种哲学延伸到了大规模数据处理。考虑对一个大小为TB级的文件进行排序——这远大于内存容量。标准算法是外部排序，包括创建较小的、已排序的“分块”，然后将它们合并在一起。为了并行化这个过程，我们可以分配不同的工作线程来合并这些分块的不同子集。但是我们如何将它们本地合并的输出组合成一个单一的、全局排序的最终输出呢？一个共享工作队列似乎是个答案，但这只会重新引入一个中心瓶颈。真正可扩展的解决方案是并发设计的杰作。每个工作线程将其排序后的输出推送到其自己专用的无锁队列中。一个单一的“协调器”线程随后从这些队列中消费。至关重要的是，协调器维护一个由每个工作线程队列的头部元素组成的最小堆。为了产生最终排序输出的下一个元素，它只需从其堆中提取最小值。这种设计使用了单生产者单消费者（SPSC）队列，这是已知的最高效的无锁结构之一，并且它将最终的合并逻辑本地化到单个线程中，从而精美地划分了问题以最小化竞争。

机器中的幽灵：更深层的联系

无锁思想的影响甚至延伸得更远，塑造了我们构建的硬件和使用的编程语言的设计。软件和硬件之间的对话是双向的，而无锁算法与机器进行着尤为深刻的对话。

当一个 CPU 核心执行一条 CAS 指令时，它不是一个神奇的、孤立的事件。它是与系统的内存和缓存一致性协议之间的一场复杂谈判。为了原子地更新一个内存位置，一个核心通常必须获得相应缓存行的独占所有权，在系统总线上发出一个“请求所有权读取”（Read-For-Ownership, RFO）请求。这个请求作为一个广播消息，告诉所有其他核心使其本地的该缓存行副本失效。现在，考虑我们的 CAS 重试循环。来自不同核心的每一次失败的 CAS 尝试都可能触发另一次昂贵的 RFO 和另一波失效。这意味着像 ABA 问题这样的现象不仅是正确性风险；它们可以表现为性能病态，产生一场看不见的一致性流量风暴，从而降低系统吞吐量。这为设计能够最小化重试和竞争的无锁算法提供了强有力的、硬件层面的动机。

最后，无锁原理是现代编程语言运行时的核心，尤其是在它们最复杂的组件之一：并发垃圾回收器（GC）中。在像 Java、Go 或 C# 这样的语言中，程序员从手动内存管理的负担中解放出来。一个 GC 在后台运行，查找并回收不再使用的内存。为了使应用程序保持响应，GC 必须与应用程序线程（“修改器”，mutators）并发运行。这引入了一个根本性的冲突。GC 通过构建一个可达对象的图来工作，通常使用“三色标记法”，其中对象被涂成白色（未访问）、灰色（已访问但其子节点未访问）或黑色（完全扫描）。这个过程的一个核心不变量是，一个黑色对象绝不能指向一个白色对象；否则，白色对象可能会被收集器错过并被错误地释放。

当一个修改器线程使用无锁 CAS 更新一个黑色对象中的字段，使其指向一个白色对象时，会发生什么？它直接违反了 GC 的不变量！解决方案是一个“写屏障”——编译器在指针更新后立即插入的一小段代码。在 CAS 成功后，这个屏障代码会检查新安装指针的目标的颜色。如果它指向一个白色对象，屏障会“将其涂成灰色”，确保 GC 会处理它及其后代。这种优雅的协调使得应用程序和垃圾收集器能够和谐工作，这是无锁更新和自动内存管理的美妙结合。

从操作系统的最底层到应用程序逻辑的最高层，无锁设计的原理为构建健壮、可扩展和高性能的并发系统提供了一种统一的方法。这段旅程向我们展示，通过理解原子性变化的根本性质，我们可以在计算的所有层面上协调复杂的交互，实现一种系统性的和谐，而无需让音乐停下来。