玻尔百科在多核处理器时代，并发编程已不再是一个小众专业，而是构建高效软件的基石。当多个执行线程竞争共享资源时，一个关键问题随之产生：我们如何确保向前进展？尽管许多技术能防止整个系统陷入停顿，但它们往往无法保护单个线程免于无限期地资源饥饿，使其陷入重试循环。本文将通过探索并发设计中最强的进展保障机制——无等待性（wait-freedom）来应对这一挑战。
我们将开启一段分为两部分的旅程。首先，在“原理与机制”部分，我们将剖析无等待性的理论，将其与无锁（lock-freedom）等较弱的保障机制进行对比，并揭示使其强大承诺成为可能的协作性“帮助”机制。然后，在“应用与跨学科联系”部分，我们将看到这些原理的实际应用，探索无等待性如何被用于构建无死锁、可预测且高度可扩展的系统——从操作系统内核到庞大的分布式数据库。
想象一个没有红绿灯的繁忙十字路口。车辆缓缓前行，有时成功通过，有时被别的车插队而不得不等待新的机会。整个路口的交通流量可能保持稳定，但对于你，坐在你的特定车里，情况又如何呢？你的安全通行有保障吗？还是你可能被无限期地困住，眼睁睁看着别人通过？这个简单的问题正是并发编程中最深层挑战之一的核心：确保进展。当许多独立的参与者——计算机程序的线程——试图访问和修改共享资源时，我们需要交通规则。无等待性就是这样的终极规则，它是在并发的混乱中对个体进展的承诺。
让我们从一个看似简单的任务开始我们的旅程：一群线程都想为一个共享计数器加一。一种常见的方法是使用循环：读取当前值（比如 ），计算 ，然后使用一种称为比较并交换（Compare-And-Swap, CAS）的特殊原子指令来更新计数器，但前提是其值仍为 。如果在你计算期间，另一个线程抢先修改了计数器，你的CAS操作就会失败，你必须从头再来。这种CAS循环是许多高性能算法的基础。
这种设计提供了一种称为无锁（lock-freedom）的保障。它承诺系统整体上总能取得进展。在任何给定的时间间隔内，总有某个线程会成功地增加计数器。就像大楼的旋转门一直在转，不断有人通过一样。这是一个强有力的保障，因为它意味着系统永远不会在死锁状态下完全停滞。
但这里有一个陷阱。无锁是一种系统性的而非个体性的保障。虽然系统在向前推进，但单个线程可能永远运气不佳。想象有两个线程， 和 。一个恶意的调度器——CPU的交通警察——可能会永远执行以下序列：
在这种情况下， 执行了无数步骤，却没能完成任何操作。它成了算法性饥饿（algorithmic starvation）或活锁（livelock）的受害者，在原地空转，而系统通过 看起来却运行得非常完美。
这就是更强的承诺——无等待性（wait-freedom）——发挥作用的地方。一个无等待算法保证每个线程都能在有限的自身步骤内完成其操作，无论其他线程的速度或调度如何。这是一种防止饥饿的个体性保障。它承诺你，在你的车里，无论其他司机在做什么，都将在有限的时间内穿过十字路口。它优雅地将一个线程的命运与其同伴的行为解耦。
为了让这幅图景更完整，还有一种更弱的保障，称为无障碍（obstruction-freedom）。它承诺，如果一个线程能隔离运行一段有限的时间，它就能完成其操作。这就像在一块共享的白板上写字：只要其他人能停笔片刻，你就能写完你的句子。这看起来可能很弱，但却可能出奇地有用。例如，在一个精心设计的操作系统内核例程中，我们可以通过在CPU核心上禁用中断和抢占来创造人为的隔离环境。在那个受控环境中，一个用于管理该核心运行队列的简单的无障碍算法就足够了，因为没有其他代理可以干扰其数据结构。这展示了将最弱的必要保障与环境相匹配之美，避免了过度设计。
这个层级——无障碍、无锁和无等待——构成了一个进展保障的谱系，每一种都在性能和可预测性之间提供了不同的权衡。
我们究竟如何才能构建一个能够实现无等待性这一铁定承诺的算法呢？正如我们所见，简单的CAS重试循环仅仅是无锁的。答案在于一种深刻的哲学转变：从自私的竞争转向强制性的合作。这一原则通常被称为帮助（helping）。
想象一下，每个线程不是直接冲上去修改共享资源，而是首先公开宣告其意图。在一个典型的无等待队列设计中，想要执行操作的线程首先会将其意图（例如，“将项目X入队”）写入一个“描述符”（descriptor）——一种小型记录——并放入一个共享数组中，就像在公共布告栏上张贴一个请求一样。
一旦一个请求被宣告，完成它的工作就成了一项公共责任。任何线程，包括最初的请求者，都可以过来读取这些描述符，并以一个明确定义的顺序帮助完成待处理的操作。无等待保障的关键就在于这种协作结构。如果你线程的操作尚未完成，它可以启动一个“帮助阶段”。在此阶段，它会系统地遍历所有待处理请求的列表并执行它们。在完成了这个有界的工作量（通常与线程数 成正比）之后，它已将系统的共享状态推进到足以保证其自身操作已完成的程度。要么是另一个热心的线程已经为它完成了工作，要么是它自己刚刚完成了工作。
这个机制是许多无等待算法的核心，例如实现取并加（fetch-and-add）操作，该操作中线程需要原子地向一个计数器添加一个值并取回旧值。一个无等待设计可以使用一个“合并”（combining）层，线程在此发布它们期望的增量（）作为请求。然后，一个辅助线程可以过来，将所有待处理的请求收集成一个批次，计算总和 ，并通过一次CAS操作应用它。接着，它为批次中的每个请求计算正确的返回值，并将它们标记为完成。一个操作保证会被包含在一个批次中，并在有限次数的“合并阶段”内完成。每个线程对自己工作的调用都有助于所有线程取得进展。
这种优美的、集体主义的方法确保了没有线程会饿死。任何单个线程的进展都与整个系统的进展密不可分。一个线程不会被落下，因为它的同伴有义务拉它前进。
如果无等待性如此强大，为什么不是每个并发算法都是无等待的呢？答案在于一个经典的工程权衡：平均情况下的性能与最坏情况下的可预测性。
在竞争不激烈时，简单的无锁CAS循环既精简又快速。如果只有一个线程活跃，它第一次尝试就会成功。然而，它的性能在压力下会下降。如果有 个线程竞争，任何一个线程成功的概率大约是 ，这意味着预期的尝试次数会随着竞争的加剧而线性增长。预期的步骤复杂度是 。
无等待算法，由于其复杂的帮助机制，具有更高的基线开销。一个线程可能需要扫描并帮助其他 个线程，这意味着其最坏情况下的复杂度通常是 ，或者对于更高级的设计，是一个常数 ，这个常数可能远大于单次CAS尝试的成本。
因此，对于一个以平均吞吐量为关键的“尽力而为”（best-effort）型应用，无锁设计可能更可取。它通常在平均情况下更快。但在任何以保障为首要考虑的领域，情况就完全不同了。考虑一个实时系统，比如汽车的刹车控制器或医疗设备。截止时间是绝对的。一个操作必须在特定的时间窗口内完成。在这种世界里，“通常很快”就等同于“有时会失败”。无锁算法的无界最坏情况是不可接受的。无等待算法，尽管开销更高，却为其执行时间提供了一个确定性的上界。这种可预测性是无价的。你可以用这个最坏情况的上界来证明你的系统将永远满足其截止时间要求。同样的逻辑也适用于关键的操作系统内核路径，比如一个禁用了抢占的中断处理程序。陷入一个无限循环将是灾难性的，因此为一个无等待保障支付更高的“税”是一个明智且必要的选择。
算法的进展保障不是一个存在于真空中的抽象属性。它通过与底层硬件以及至关重要的操作系统调度器的交互而得以实现。即使一个完美的无等待算法，如果调度器决定永不给其线程分配CPU时间，它也是无用的。无等待保障承诺的是在线程自身的有限步骤内完成；而提供这些步骤是调度器的职责。
这种相互作用揭示了非阻塞设计的真正本质。其根本目标是消除对其他线程活性的依赖。如果一个算法中，系统可能因为一个线程被操作系统取消调度而陷入停顿，那么无论它使用什么原语，根据定义，它就是一个阻塞（blocking）算法。一个真正的非阻塞算法能确保一个参与者的暂停不会妨碍其余部分的继续进行。
或许，对这一原则最优雅的表达来自无等待构造的理论基础。想象一下，你只有能解决至多 个参与者共识问题的构建块，但你需要一个针对 个参与者的解决方案，其中 远大于 。你能用这些较弱的工具构建出更强的工具吗？答案是肯定的，通过一种被称为合并树（combining tree）的优美结构。通过将 进程共识对象排列成一个高度为 的 叉树，我们可以为所有 个进程创建一个无等待的共识算法。每个操作在树中向上“竞争胜出”，每一层的失败者则帮助胜利者前进。这种分层结构不仅解决了问题，还揭示了同步原则中深刻而令人满意的统一性：复杂、稳健的保障可以由更简单的组件构建而成，并能随着挑战的规模优雅地扩展。这证明了在面对并发复杂性时，协作式、结构化设计的力量。
在了解了无等待性的原理之后，我们可能感觉自己像是在研究一块奇特而精美手表的复杂齿轮和弹簧。我们理解了它如何工作——原子操作的巧妙运用、对锁的回避、对进展的保障。但现在到了最激动人心的部分：我们能用这块手表做什么？这个看似抽象的进展保障在哪里找到了它的用武之地？
答案是，无处不在。无等待性不仅仅是理论上的好奇心；它是一种强大的设计哲学，重塑了我们构建稳健、可预测和正确软件的方式。它为我们提供了一种解决计算领域中最顽固问题的方法，从操作系统核心到广阔的分布式网络。现在，让我们来探索这个应用领域，不是作为一份枯燥的目录，而是一次发现之旅，看看这个简单的想法如何为复杂的世界带来清晰和秩序。
在并发编程的世界里，阴影中潜伏着一个怪物：死锁（deadlock）。想象有两个线程，我们称之为 和 。 获取了一个资源，比如一个文件句柄，然后试图获取另一个资源，一个数据库连接。但与此同时， 获取了数据库连接，现在正试图获取文件句柄。 等待 ， 等待 。两者都无法继续前进。它们陷入了一个致命的拥抱，一个永远无法逃脱的状态。
我们可以用所谓的“等待图”（wait-for graph）来可视化这些依赖关系，其中从一个线程到另一个线程的箭头 意味着“ 正在等待 ”。死锁就是这个图中的一个环路。传统锁是这些环路的主要构建者。当一个线程试图获取另一个线程持有的锁时，操作系统会使其休眠，从而创建一条“等待”边。你拥有的锁越多，这个依赖关系网就可能变得越纠结，阻止这些环路形成也就越困难。
这正是无等待性不仅提供治疗，而且提供彻底预防的地方。根据其定义，无等待操作不会阻塞。执行无等待算法的线程永远不会因为等待另一个线程释放资源而休眠。它可能会自旋，可能会重试，但从操作系统的角度来看，它总是在运行，总是在取得进展。用我们的图来描述，无等待操作根本不创建“等待”边。
通过为系统的关键、高竞争部分——比如数据库中的共享索引——采用无等待数据结构，我们可以从图中手术般地移除一整类潜在的边。这不仅仅是降低了死锁的几率；它消除了完全由这些操作组成的任何环路。这是一个深刻的转变，从调试一个问题转变为在设计上就将其彻底根除。这是无等待保障最优雅和最强大的后果之一。
虽然消除死锁是正确性上的一大胜利，但无等待性最受称赞的优点或许是它对性能的影响——但不是人们最初可能设想的那种方式。它并不总是关于平均最快；而是关于在最坏情况下最可预测。
想象一下我们正在为多线程应用设计一个内存分配器。我们可以使用一个巧妙的无锁设计，让线程使用原子操作从一个单一的全局池中获取内存。在低负载下，这可能快得令人难以置信。但随着越来越多的线程争夺该池，它们开始互相干扰，导致其原子操作失败并重试。分配内存的平均时间上升，更糟糕的是，*方差*爆炸性增长。一次分配可能耗时一微秒，下一次可能耗时一百微秒。
现在考虑一个无等待的替代方案。一种常见的策略是为每个线程提供自己的小型私有内存池。当线程需要内存时，它从自己的池中满足请求。这个操作没有竞争，因此在有限的步骤内完成——它是无等待的。偶尔，一个线程的私有池会耗尽，它必须去一个全局源获取一批新的内存，这是一个更长但仍然有界的操作。
在直接比较中，简单的无锁设计的平均响应时间在某些条件下甚至可能更低。然而，无等待设计提供了更有价值的东西：延迟的上限。一个线程的性能几乎完全与其它线程的活动解耦。对于构建实时系统、操作系统调度器或高频交易平台来说，这种隔离是革命性的，因为在这些场景中，一个不可预测的延迟就可能是灾难性的。你是在用原始的平均速度换取关于最坏情况的保证。
当然，这是一个工程上的权衡。对于一些高性能结构，比如现代任务调度器中使用的“工作窃取队列”（work-stealing queues），设计者通常会选择一个无锁（但非无等待）的算法。某个线程能取得进展的保障已经足够好，而一个真正的无等待实现的复杂性和开销被认为过高。无等待性是一个强大的工具，但一个明智的工程师知道何时使用，何时不使用。
在领会了无等待性所提供的正确性和可预测性之后，我们现在可以看到它在众多令人惊讶的现代系统中作为一个基本的构建块。
并发系统中最简单也最常见的问题之一是计数：收到的数据包、处理的请求、记录的事件。一种天真的方法是使用一个由锁或单个原子变量保护的全局计数器。这会造成一个普遍的瓶颈，一个所有线程都必须争夺的单点竞争。
一个优美的无等待模式从简单的“分而治之”策略中浮现出来。我们不使用一个全局计数器，而是创建一个计数器数组，每个CPU核心或线程一个。当一个线程需要增加计数时，它只接触自己的私有计数器。由于它是唯一的写入者，这个操作——一个单一的原子fetch-and-add——是平凡的无等待。不存在竞争。
这种“分片”（sharded）或“单写入者”（single-writer）原则可以优美地扩展到更复杂的结构，如向量时钟（vector clocks），这对于在复杂系统中追踪和理解因果关系至关重要。每个线程可以以无等待的方式更新向量时钟中自己的分量，用一个本地的、保证能进展的时间戳来标记事件。唯一的挑战变成了聚合结果——读取所有计数器以获得总和。这个读操作本身通常不是完美同步的（这个属性被称为非线性一致性, non-linearizability），但对于许多统计目的，它提供了一个“足够好”的快照。我们用完美的全局一致性换取了完美的本地进展。
无等待性也是优化我们操作系统的一个关键要素。考虑一个父进程需要知道其子进程何时终止。传统方式涉及信号或阻塞式系统调用，两者都带有显著的开销。
一种更现代的方法，使用像Linux的futex这样的原语，可以为这种通知创建一个“快速路径”。父进程和子进程共享一块内存。当子进程即将退出时，它将其退出码写入这个共享内存位置。父进程想要检查子进程的状态时，只需读取这个内存位置。这个检查是无等待的——一个在有限时间内完成的单一内存读取。如果内存显示子进程已经退出，父进程无需进入内核就得到了答案。只有当子进程仍在运行时，父进程才需要走“慢速路径”，即进行阻塞式系统调用。这种混合设计兼具了两者的优点：针对常见情况的无等待检查的极高速度，以及由传统机制为其余情况提供的稳健性支持。
或许无等待性最具前瞻性的应用是在大规模分布式系统领域。在一个横跨全球数千台机器的系统中，要求所有机器在任何一台能取得进展之前都必须就某个状态达成一致，这无异于让整个系统陷入停顿。
一类新的数据结构，称为冲突无关复制数据类型（Conflict-free Replicated Data Types, CRDTs），采纳了一种与无等待性产生深刻共鸣的哲学。对于像只增计数器（grow-only counter）这样的CRDT，每个副本（或服务器）都可以在本地接受更新，而无需与任何其他副本协调。一次增量操作纯粹是本地的，因此是无等待的。这带来了惊人的可用性和性能。
当然，权衡的是一致性。在任何特定时刻，不同副本对于计数器的“真实”值会有不同的看法。然而，CRDTs的设计具有一种数学结构（一个半格，semilattice），保证如果更新停止，它们最终都会收敛到同一个正确的值。更好的是，我们通常可以根据网络延迟和更新频率等因素，数学上计算出副本之间最大“分歧”或误差的严格上界。无等待性为我们赢得了本地性能，而CRDTs的数学原理则让我们能够可预测地掌握由此产生的全局不一致性。
正如我们所见，无等待性的保障是深刻的。但它们并非没有代价。对这一理想的追求迫使我们直面深层的复杂性并做出深思熟虑的权衡。
首先，是结构性成本。为了确保线程之间不会以违反无等待属性的方式相互干扰，我们常常不得不为它们提供独立的资源。一个引人注目的理论结果表明，要实现一个可供多生产者和多消费者使用的正确无等待队列，至少需要 个独立的原子变量，其中 是队列的容量。其直觉是， 个槽中的每一个都需要自己的原子状态变量来协调访问，以避免产生阻塞依赖，此外还需要两个用于头尾指针。无等待性要求互不干扰，而互不干扰通常需要专有资源。
其次，现实世界硬件的细节中隐藏着魔鬼。一个纸面上绝妙的无等待算法如果实现时不加小心，可能会惨败。在具有“弱”内存模型的现代处理器上，内存操作的顺序可能会被打乱。为了确保写入线程的更新能以正确的顺序对读取线程可见，程序员必须细致地使用内存排序原语，例如release和acquire语义。
此外，还有臭名昭著的ABA问题。一个线程读取了值 ，计算了一个新值，但在它提交更改之前，其他线程将该值从 改为 ，然后再改回 。第一个线程的原子操作本是检查值是否为 ，结果错误地成功了，可能导致数据结构损坏。解决这个问题需要复杂的技术，比如版本戳指针或使用安全内存回收（Safe Memory Reclamation, SMR）方案，以防止在某个线程可能仍引用某个内存位置时该位置被重用。
最后，是性能成本。无等待性消除了阻塞，但它常常用忙等待或自旋来取而代之。在高竞争下，重试其原子操作的线程会消耗大量CPU周期，并用一致性流量淹没系统的内存互联结构，甚至可能导致总吞吐量低于一个行为良好的基于锁的算法。
我们对无等待性应用的探索揭示出，它远不止是一个简单的性能技巧。它是一种范式，迫使我们直面并发的根本挑战。它推动我们设计的系统不仅要快，而且要可证明其正确性、可预测性，并能抵御像死锁这样的整类错误。
从操作系统调度器的核心到分布式数据库的全球规模，无等待性的原则提供了一种统一的语言来推理进展和保障。这是一门要求很高的学科，需要对硬件、内存模型以及并发线程间错综复杂的舞蹈有深刻的理解。但回报是巨大的：能够构建在真正意义上更为完美的系统。对无等待性的追求，归根结底，是为我们所依赖的计算世界寻求一种更好的构建方式。