玻尔百科在并发计算的世界里，同时执行多个任务的能力是巨大力量和效率的源泉。然而，这种并行性也带来了复杂的挑战，独立进程之间可能会以灾难性的方式相互干扰。其中最严重的失败是死锁（一种完全瘫痪的状态）和饥饿（进程持续被剥夺其取得进展所需的资源）。本文旨在弥合一个关键的知识鸿沟：从认识到系统可能“卡住”，到理解导致这种情况的确切条件。要构建真正健壮和公平的系统，我们必须首先学会诊断这些“病症”。接下来的章节将引导您掌握这些核心知识。首先，在“原理与机制”中，我们将定义死锁，剖析其四个构成条件，并探讨饥饿和活锁等相关的活性失败。随后，在“应用与跨学科联系”中，我们将看到这些理论概念如何变得鲜活，考察它们在经典计算机科学问题、现代软件工程模式以及大规模分布式系统中的表现形式。
在我们理解并发进程复杂协作的旅程中，我们已经看到，当许多事情同时发生时，它们有时会互相干扰。但有些失误比其他失误更严重。有时，进程不仅仅是跌跌撞撞；它们会陷入一种相互瘫痪、无法解脱的状态。这就是死锁及其更微妙的“近亲”——饥饿和活锁的世界。理解它们，就是理解系统“卡住”的本质，以及我们如何设计一个能够永远保持运转的系统。
想象有两位抄写员，Peter和Paul，负责更新一部大账本。账本有两卷，卷一和卷二。为了确保一致性，抄写员必须锁定他们正在使用的任何一卷，防止他人在同一时间修改。这条互斥规则是合情合理的；它是秩序的基础。
一天，Peter拿起了卷一并将其锁定。然而，他的任务还需要卷二中的一条信息。他伸手去拿。与此同时，正在执行另一项任务的Paul，已经拿起并锁定了卷二。他继而发现需要交叉引用卷一中的某些内容。
现在来看看这个局面。Peter持有卷一，等待卷二。Paul持有卷二，等待卷一。谁也无法继续。谁也不会让步。他们被冻结在时间里，陷入了“致命拥抱”。这就是死锁。它不仅仅是缓慢；它是一种永久性的结构性瘫痪，没有外界干预就无法摆脱。
我们可以用一种称为等待图（Wait-For Graph）的简单图示来形象化这种困境。我们为每个进程和每个资源画一个点。从进程到资源的箭头表示“正在等待”，从资源到进程的箭头表示“被持有”。在我们抄写员的状态下，图会显示一个闭环：Peter等待卷二，卷二被Paul持有，而Paul又等待卷一，卷一被Peter持有。这个环路，这个循环，就是死锁明确无误的标志。
就像火需要燃料、氧气和热量才能燃烧一样，死锁的发生也必须同时满足四个特定条件。这是一条极其有力的知识，因为它告诉我们，只要能打破其中任意一个条件，我们就能完全防止死锁的发生。让我们来看看这四个死锁末日的“骑士”。
互斥：至少有一个资源是不可共享的。我们的账本卷宗，或者现实世界中的打印机，就属于这种情况。这个条件通常是资源本身固有的，我们不易消除。
持有并等待：一个进程必须在持有一个或多个资源的同时，等待获取另一个资源。这正是我们抄写员所做的事情。Peter持有卷一，同时等待卷二。
如果我们制定一条新规则：“在最开始就请求你需要的一切，否则什么也得不到”，情况会怎样？一个进程必须预先声明它需要卷一和卷二。只有当两者都空闲时，它才被允许启动。在这种策略下，进程永远不会在持有一个资源的同时等待另一个。持有并等待条件被打破，死锁变得不可能！这是一个优美而简洁的解决方案。但它代价高昂。想象一个进程在一小时的计算中需要使用打印机五分钟。这项策略会迫使它在整个小时内都占用打印机，导致打印机在55分钟内闲置，对他人毫无用处。我们防止了死锁，但代价是严重损害了资源利用率。系统设计的艺术往往在于权衡这些利弊。
不可抢占：资源不能被强制地从一个进程中夺走。一个进程必须自愿释放资源。这就是“我的就是我的”规则。
如果我们违反这条规则会怎样？想象系统里有一个看门狗计时器。如果一个进程等待新资源的时间过长——比如说，超过几秒钟——看门狗就可以介入并抢占它的资源，迫使它释放已经持有的锁。这将打破死锁循环。然而，这是一个危险的游戏。如果该进程正在更新银行账户的半途中，强制夺走它的锁可能会使账户数据处于损坏、不一致的状态。这是一种安全违规。
能否抢占完全取决于资源的性质。我们可以轻易地从一个进程中抢占几页计算机内存（RAM）并分配给另一个进程；原始进程的状态可以安全地保存到磁盘。但我们无法抢占一台正在打印半页纸的打印机而不造成混乱。一个智能的死锁恢复系统明白这一点，它会选择首先抢占成本最低、最安全的资源，比如从一个进程拿走RAM以满足另一个进程，然后才诉诸于像完全中止一个进程这样代价高昂且具有破坏性的行动[@problem_d:3676667]。
循环等待：必须存在一个构成环形的等待进程链。Peter等待Paul，Paul等待Peter。或者更一般地，等待一个由持有的资源，等待一个由持有的资源，...，等待一个由持有的资源。
这个条件为我们提供了或许是最优雅且应用最广泛的死锁预防策略：施加层级结构。想象我们颁布一条全局法则：世界上所有资源都被编号，每个进程都必须按递增顺序获取资源。你可以在获得2号资源后请求5号资源，但绝不能在持有5号资源后请求2号资源。在这条法则下，循环等待在逻辑上是不可能的。要形成一个的环路，将意味着资源编号存在一个的顺序，这在逻辑上是不可能的。通过简单地强制执行一个通用顺序，我们可以在不牺牲资源利用率（像一次性全部分配那样）或冒着抢占风险的情况下，使死锁在结构上变得不可能。
通过打破四个条件之一，我们可以建立一个堡垒来抵御死锁的瘫痪。但我们的系统仍然可能以更微妙、更幽灵般的方式无法取得进展。
想象两个极其礼貌的人在狭窄的走廊里试图擦肩而过。A向他自己的右边移动让路；B在完全相同的时间也向他自己的右边移动。他们仍然互相挡着路。他们都注意到了，并立即都向自己的左边移动。他们仍然被挡住。他们永远处于活动状态，不断移动，却无法取得任何进展。
这就是活锁。系统不像死锁那样被冻结；进程是活跃的，状态在改变。但它们被困在一个同步的、无效的循环中。一个常见的技术例子是，系统中的进程试图乐观地获取锁。线程抓取锁，然后尝试获取，但发现它已被占用。为了避免死锁，它的策略是立即释放然后重试。线程也做同样的事情，抓取但未能获得。它们有可能进入一个完美的、徒劳的节奏：抓取，抓取；在上失败并释放，在上失败并释放；无限重复。他们在忙于做无用功。
比活锁更微妙的是饥饿。在这里，系统作为一个整体正在取得进展。其他进程正在完成它们的工作并继续前进。但一个可怜、不幸的进程却永远被忽视。它在等待一个资源，而每当这个资源变为空闲时，总有别人先得到它。
想象一下机场值机柜台的高优先级队列。航空公司的政策是总是先为任何新到达的头等舱乘客服务，然后再为经济舱队伍中的任何人服务。如果头等舱乘客源源不断地到来，经济舱队伍里的人可能要等上永远，尽管值机柜台很忙，系统也在处理旅客。这就是饥饿。这里没有死锁循环——经济舱乘客只是在等待柜台。但他的等待时间可能变得实际上无限长。
我们甚至可以设计一个“解决”了死锁却制造了饥饿的系统。考虑一个由进程组成的环，每个进程都在等待下一个，形成一个完美的死锁循环。我们引入一个超时机制：如果你等待太久，你就会被“回滚”并必须重试。这打破了死锁。但是谁会被回滚呢？自然是那个超时时间最短的进程。如果系统迅速重新形成死锁循环，同一个进程，因其同样最短的超时时间，将一次又一次地被选为牺牲品。它被那个本应拯救它的机制饿死了。
那么，我们如何构建不仅免于瘫痪，而且公正的系统呢？指导原则是公平性。我们必须找到一种方法来打破这种永远运气不佳的模式。
实现这一目标最巧妙、最深刻的思想之一是老化（aging）。系统必须学会识别并优先处理那些等待时间最长或受害最深的进程。
回想那个因超时时间总是最短而饿死的进程。如果我们应用老化机制会怎样？每当那个进程被回滚时，我们人为地增加它下一轮的超时值。几次回滚之后，它的超时将不再是最短的。另一个进程将被选为牺牲品。通过为受害者“老化”，我们确保了恢复的负担是分担的，没有单个进程会被无限期地牺牲。这保证了每个进程最终都会轮到自己。
这种老化的原则，即记住过去的苦难以确保未来的公平，是贯穿许多这些微妙问题解决方案的一条线索。走廊里礼貌的人可以通过其中一人随机决定多等一会儿来摆脱他们的活锁。在锁上饥饿的进程可以通过锁维持一个公平的队列（确保先进先出服务）来得到拯救。其核心在于，构建健壮、有活力的系统不仅仅是防止死锁的灾难性失败，更是要融入公平的原则，以确保系统的每个部分都有机会实现其目的。
在上一章中，我们剖析了死锁和饥饿的抽象本质，将它们定义为并发的病态——进程陷入循环等待的致命拥抱，以及一个进程因被反复拒绝而陷入的永恒而不公的等待。然而，这些概念远非仅仅是理论上的好奇。它们是萦绕在机器运行各个层面的幽灵，从最基础的算法到庞大的全球互联网架构。在本章中，我们将去“猎鬼”。我们将探索这些幻影在现实世界中何处显现，并学习工程师们为驱除它们而设计的巧妙、有时甚至是优美的技术。
我们的旅程始于计算机科学中常见的场景——哲学家的晚宴。“哲学家就餐”问题，即哲学家们必须共享有限数量的叉子来进食，它几乎是任何独立代理必须竞争共享资源的系统的完美缩影。它不仅仅是一个谜题；它是从竞争表锁的数据库事务到争用缓冲空间的网络路由器等一切事物的模型。
为了防止每个哲学家都拿起左手边的叉子并永远等待右手边叉子的死锁，一个最初的直观解决方案是简单地限制参与者的数量。如果你有个哲学家和把叉子，为什么不设置一个一次只能容纳人的“餐厅”呢？这个限制并发的简单举动保证了在任何时刻，桌上至少有一把叉子是空闲的，从而打破了完全循环等待的可能性。系统现在是无死锁的。
但在这里我们遇到了一个更狡猾的恶魔。即使在这个无死锁的餐厅里，如果某个特别有耐心的哲学家（比如说Socrates）的两个邻居是吃饭速度非常快的人，情况又会如何？他们可能吃完饭，思考片刻，然后在Socrates有机会拿到叉子之前又设法再次抓起叉子。如果关于谁能拿到下一把空闲叉子的规则不是严格公平的——如果是一场混战而不是有序排队——Socrates原则上可能会永远等待。他没有死锁，因为其他人正在取得进展，但他被饿死了。这揭示了一个深刻的真理：死锁是依赖关系导致的结构性问题，而饥饿通常是公平策略导致的问题。
另一种防止哲学家死锁的优雅方法是打破他们行动的对称性。如果我们规定所有奇数号的哲学家必须先拿起左边的叉子，而所有偶数号的哲学家必须先拿起右边的叉子，会怎么样？这个简单的规则对叉子的获取施加了一个部分排序，使得循环的“持有并等待”链成为不可能。然而，这种针对死锁的巧妙结构性修复同样没有提供对饥饿的内在保护。一个不公平的调度器，扮演着一个恶意的主人，可能会密谋总是在一个哲学家的邻居需要叉子时运行他们，从而确保那个哲学家永远吃不到饭。系统整体上得以存活，但一个成员却被判处无限期的饥饿。
从哲学家的寓言世界转向实际的编程世界，我们在日常使用的工具——锁的设计中发现了同样的挑战。一个读写锁（RWL）是一种复杂的锁，它允许多个“读者”线程并发访问资源，但要求“写者”线程拥有独占访问权。这非常高效，但当读者和写者同时到达时会发生什么？
一个常见的实现策略是“写者优先”：如果一个写者在等待，就不允许新的读者进入。这个策略优先考虑数据一致性，确保写操作能及时发生。但想象一下，一个连续的写者流到达一个热门的数据结构。一个孤独的读者线程可能会发现自己被一连串无尽的写者永远推到队尾。写者来了又走，系统在取得进展，但读者却被饿死，永远没有机会执行其工作。这不是死锁——没有循环——但它是由策略决策产生的严重活性失败。
死锁也可能从这些锁的看似无害的操作中出现。考虑一个常见的模式，一个线程在持有读锁时意识到需要修改数据。它需要将其共享的读锁“升级”为独占的写锁。如果两个读者线程，我们称之为和，都同时决定升级会发生什么？持有它的读锁并等待的读锁被释放，以便它能获得独占访问权。同时，持有它的读锁并等待的锁被释放。它们被锁在一个致命的拥抱中——一个经典的死锁，不是由bug引起，而是由一个常见的、理想的功能引起。这里的解决方案是一个具有深远重要性的工程模式：串行化。锁必须设计一个内部“门”，一次只允许一个线程处于“升级”状态。这打破了循环等待，将混乱的竞争变成了有序的队列。
死锁和饥饿不仅限于我们的应用程序代码中；它们常常源于我们的程序与底层操作系统之间意想不到的危险交互。其中最著名的例子是优先级反转。
想象一个有三个任务的系统：一个高优先级任务，一个低优先级任务，以及一群中等优先级的任务。假设获取了一个关键资源的锁。就在那时，唤醒，并且由于优先级更高，抢占了。现在尝试获取同一个锁，但它被持有，所以必须阻塞并等待。现在，调度器会运行谁？不是，因为它被阻塞了。也不是，因为处于就绪状态的中等优先级任务的优先级都高于。结果是一场噩梦：中等优先级的任务运行，永远阻止低优先级的任务运行。由于无法运行，它就无法释放锁。而由于锁永远不被释放，系统中最重要的任务将永远等待。这在传统意义上不是死锁——没有循环等待——而是一个由锁和调度交互引起的严重饥饿问题。这个场景在1997年曾困扰过NASA的Mars Pathfinder任务。
其解决方案之巧妙，堪比问题之棘手：优先级继承。一个智能的操作系统可以检测到其最高优先级的任务正在等待一个由低微的持有的资源。在那一刻，系统将的高优先级“借给”。现在，可以抢占所有中等优先级的任务，运行其临界区，并释放锁。一旦锁被释放，就恢复其正常的低优先级，而现在不再阻塞，终于可以继续执行。
调度和锁之间的这种交互甚至可以产生一个真正的死锁。考虑一个高优先级线程使用自旋锁，这是一种通过消耗CPU周期来忙等待而不是睡眠的锁。现在，想象一个低优先级线程获取了这个自旋锁，然后被系统事件抢占（例如，它需要做一些磁盘I/O）。高优先级线程唤醒，发现锁被持有，并开始自旋。在单CPU机器上，它将永远自旋，消耗100%的CPU。低优先级线程虽然现在已准备好运行并释放锁，但将永远不会被调度，因为一个更高优先级的线程总是“就绪”。这里我们有一个真正的死锁循环：高优先级线程持有CPU并等待锁，而低优先级线程持有锁并等待CPU。这揭示了并发编程的一条基本原则：绝不在持有自旋锁时执行阻塞操作（如I/O）。对于可能阻塞的临界区，正确的工具是互斥锁（mutex），它会让等待的线程进入睡眠状态而不是让它们自旋，从而释放CPU供其他线程使用。
死锁和饥饿的原理并不局限于单台机器。它们可以扩展到全球分布式系统的层面，在这里，“线程”是运行在不同大陆的整个服务，“锁”是跨网络的同步调用。
考虑一个现代的微服务架构。一个请求进入服务，为了完成它，调用服务。接着又调用。但是，如果由于复杂的依赖关系，需要回调来获取一些数据呢？如果所有这些调用都是同步的（调用者阻塞并等待被调用者响应），我们就面临一个分布式死锁：等待，等待，等待。这个循环可以跨越一个数据中心或整个地球，但其逻辑与我们的哲学家就餐问题完全相同。
在分布式系统中，对抗此类死锁最常用的武器是超时。如果在比如说毫秒内没有收到的回复，它就会放弃，取消请求，并打破等待依赖。这并不能阻止死锁的形成，但它提供了一种从中恢复的机制。然而，这种恢复可能会产生其自身的病态。如果的策略是立即重试任何失败的请求，它可能在打破死锁循环的瞬间就重新建立了它。系统随后进入活锁状态：一片繁忙的景象——死锁、超时、重试——但实际上没有任何工作得以完成。这些请求实际上因无法完成而陷入饥饿。
最后，我们可以从安全的角度来看待死锁和饥饿的挑战。如果一个进程不仅仅是有缺陷，而是主动恶意的呢？一个恶意的哲学家可能会试图通过获取一把叉子并永远持有它来使系统崩溃，故意饿死它的邻居并降低整个系统的性能。
为了构建一个真正健壮的系统，内核本身必须扮演一个警惕而公平的仲裁者，执行连恶意代码都无法破坏的规则。这导致了将资源管理视为安全问题的高级操作系统设计。这样的系统可能会使用：
通过结合这些机制，操作系统可以创建一个堡垒。它不仅保证了无死锁，还保证了无饥饿和限制，确保一个组件的失败或恶意行为不会拖垮整个系统。
从一个简单的餐桌谜题，我们穿越了操作系统的核心，跨越了全球网络，并深入到安全系统设计的核心。死锁和饥饿的原理是普适的。它们告诉我们，任何协作代理的系统——无论是线程、计算机还是人——都必须建立在清晰的规则、公平的策略和健壮的恢复机制的基础上，以避免陷入停顿。理解这些幽灵是构建未来弹性、高效和公平的计算世界的第一步。