aiwiki.page
中文

死锁

死锁是指一组相互协作的计算活动各自等待依赖组内其他活动的资源或事件,因而均无法推进的状态。

31 个关键词40 个词条链接到这里15 个尚未撰写AI 撰写
线程(计算机)并发计算操作系统进程(计算机)互斥锁数据库事务数据库管理系统数据库索引死锁

死锁是计算系统中的一种状态:一组活动各自都在等待某个依赖于组内其他活动的资源、操作或事件,因而均无法继续执行。一个典型例子涉及两个线程:一个持有资源 A 的锁并等待资源 B,另一个则持有资源 B 的锁并等待资源 A。两者都无法通过正常执行来释放所持有的资源,因为它们都无法执行到释放资源的指令。

死锁是并发计算中的一个基本问题,涉及操作系统、数据库、分布式服务、通信网络和硬件。它可能使整个系统陷入停滞,也可能只阻塞一小组任务,而不相关的工作仍可继续。问题的核心不只是执行缓慢,而是系统中的依赖关系使受影响的活动无法继续推进,除非从这些依赖关系之外施加某种改变。

死锁研究将资源分配的数学模型与实际技术相结合,后者包括组织锁的使用、控制任务准入、检测循环依赖以及恢复中断的工作。不同环境需要不同的解决方案:数据库通常可以中止事务并重试,而操作系统内核一般无法安全地终止一个持有任意内部状态的线程。

基础与历史发展

随着计算机开始支持共享处理器、内存、文件和外围设备的多项活动,死锁成为一个核心问题。在操作系统中,一个进程可能需要多种资源才能完成一项操作,而分别分配这些资源可能会形成程序单独运行时不存在的依赖关系。这个问题并不以多个处理器同时执行为前提。即使只有一个处理器,交错执行两个进程也可能产生同样的循环依赖。

一个最简单的例子涉及两个互斥锁 A 和 B。线程 T1 获取 A,线程 T2 获取 B。随后,T1 尝试获取 B 并被阻塞;T2 尝试获取 A,也被阻塞。假设这些锁无法被强制剥夺,也没有其他机制将其释放,那么两个线程都会一直挂起。一种相关情况是自死锁:持有非递归互斥锁的线程再次尝试获取同一个互斥锁。此时,它所等待的事件,恰恰是它自己最终释放该锁。

死锁有别于其他几种无法继续推进的情况。在饥饿(计算机科学)中,其他任务反复获得某个任务所需的资源,可能使该任务无限期等待,尽管系统仍在不断完成有用的工作。在活锁中,各项活动不断改变状态,却无法向目标推进;例如,两个参与者反复同步地让出资源并重试。普通阻塞又有所不同:如果磁盘输入操作能够独立完成,那么等待该输入的任务就没有陷入死锁。因此,界面卡死或发生超时只能说明执行推进出现了问题,本身并不能证明存在死锁。

早期理论研究将死锁问题与资源分配和进程协调联系起来。艾兹格·W. 戴克斯特拉在 20 世纪 60 年代提出了用于安全分配资源的银行家算法。他在同一时期提出的哲学家就餐问题,也成为说明多资源竞争的经典例子。1971 年,小爱德华·G. 科夫曼、迈克尔·J. 埃尔菲克和阿里耶·绍沙尼发表了《系统死锁》(“System Deadlocks”)。这篇重要的综述系统梳理了死锁问题,其中讨论的四个条件如今通常称为科夫曼条件。

死锁主要是一个活性问题:本应最终发生的事情没有发生。这与安全性违规不同,后者是指发生了不允许发生的事件,例如两个线程同时修改受保护的状态。程序即使完全保证了互斥,也仍然可能发生死锁。因此,正确的并发软件必须兼顾共享状态的完整性和持续执行的可能性。

必要条件与依赖模型

在资源可重复使用且不可抢占的经典模型中,资源死锁有四个必要条件。互斥是指至少有一种相关资源不能由相互竞争的活动同时使用。占有并等待是指某个活动在请求其他资源时,仍持有已有资源。不可抢占是指在持有者释放资源之前,不能直接将资源夺走。循环等待是指存在一条由多个活动组成的等待链,其中每个活动都在等待下一个活动持有的资源,而最后一个活动又在等待第一个活动持有的资源。

这些条件必须结合起来,并在其所属模型的范围内理解。允许这四个条件同时成立的系统有发生死锁的可能;但仅仅允许这些条件成立,并不能证明某次具体执行已经陷入死锁。反过来,只要协议能保证其中任一条件不成立,就能排除经典的资源死锁。对于通信协议、可择一满足的等待,以及不适合用可重复使用的资源来表示的事件,还需要对这些条件作相应调整。

资源分配图将进程和资源表示为顶点。请求边从进程指向它正在等待的资源;分配边从资源实例指向当前持有该实例的进程。如果每种资源类型都恰好只有一个实例,那么在阻塞进程必须等到其尚未满足的请求得到满足后才能继续运行的标准模型中,存在环是发生死锁的充要条件。如果某种资源类型有多个实例,那么存在环是死锁的必要条件,但不是充分条件。环外某个进程持有的资源实例可能随后变得可用,从而使循环等待得以解除。

等待图省去了显式的资源顶点。边 Pi→PjP_i \rightarrow P_j 表示 PiP_i 因受 PjP_j 控制的资源或操作而阻塞。在常规的单实例、合取等待模型中,有向环表明存在死锁依赖。不过,模型必须明确规定边的含义。如果多个事件中只要任意一个发生,任务就能继续执行,那么某一条循环依赖未必会阻止任务通过其他备选路径继续推进。对于这种析取等待,要判定死锁,需要比“存在任意一个环”更强的闭合依赖条件。

所建模系统的边界同样重要。等待外部服务回复的进程可能看起来已被永久阻塞,但它是否陷入死锁,取决于该服务的依赖关系以及协议提供的脱困路径。同样,定时器若能触发成功的回滚,就可以打破原本会永久持续的等待。因此,有用的死锁模型应明确说明资源归属、请求语义、释放规则,以及哪些外部状态转换仍有可能发生,而不是将所有长时间等待都视为同一种情况。

通过资源与锁的使用规则预防死锁

死锁预防通过制定规则,使死锁的至少一个必要条件不可能成立。最广为人知的方法是规定全局锁顺序。每把锁都在一个严格的顺序中占据一个位置,线程只能按递增顺序获取更多的锁。假如存在循环等待,就必然有

L1<L2<⋯<Lk<L1,L_1 < L_2 < \cdots < L_k < L_1,

这与规定的顺序矛盾。这一论证不依赖于有利的调度安排,而是从结构上排除了循环。

锁的顺序可以根据对象类型、子系统层级,或分配给各个对象的稳定标识符来确定。例如,涉及两个账户的操作,无论转账方向如何,都可以先锁定标识符较小的账户。动态对象结构会使这条规则变得复杂,因为操作可能只有在获取某把锁之后,才会发现新的对象。锁顺序还必须涵盖子系统之间的交互;各自内部一致的独立层级,在调用跨越子系统边界时,仍可能发生冲突。

另一种方法是要求一次性获取所有所需资源,从而消除占有并等待条件。任务要么获得所需的全部资源,要么在不持有其中任何资源的情况下等待。当所需资源集合事先已知时,这种方法效果很好,但它可能在资源实际使用前很久就将其占用,也可能使需要大量资源组合的任务陷入饥饿。还有一种做法是:如果后续资源获取失败,就释放此前已获取的资源,然后重试。这要求已经部分完成的操作能够撤销,或者尚未产生任何外部可见的更改。如果没有合适的重试策略,这种方法可能只是把死锁变成了活锁。

当资源状态可以保存、恢复或重建时,抢占可以打破不可抢占条件。处理器时间被抢占是常见做法,但在线程更新链式结构的过程中强行夺走其持有的互斥锁,通常并不安全。被中断的线程可能暂时破坏了其他线程所依赖的不变量。因此,系统会区分两种情况:一类资源可以通过机械化手段回收,另一类资源的所有权则只能通过事务回滚等更高层操作来撤销。

一些设计通过避免共享可变状态来减少互斥。不可变数据、所有权转移、状态分区和消息传递都可以消除特定的锁依赖。但这些方法并不会自动使整个应用程序免于死锁:两个组件仍可能相互等待对方发来消息。同样,在退出作用域时自动释放锁,可以避免因忘记释放锁而产生的问题,却无法阻止两个线程以相反的顺序获取不同的锁。能否预防死锁,取决于所有相关依赖的结构,而不仅仅是单个锁操作是否正确。

死锁避免与安全资源分配

死锁避免与死锁预防不同,它会在批准请求之前检查当前的资源分配状态。它并不永久禁止某个死锁必要条件成立,而是拒绝那些可能使系统失去完成保证的状态转换。这通常需要掌握未来资源需求的信息,尤其是每个进程可能请求的各类资源实例数量的上限。

如果存在一种活动进程的排列顺序,使每个进程都能依次获得其声明的剩余所需资源、执行完毕,并释放已分配的资源供下一个进程使用,那么该状态就是安全的。安全并不等同于当前没有死锁。不安全状态中可能没有任何进程阻塞,而且如果后续请求的资源不多,所有进程最终仍可能执行完毕。它所缺少的是:在模型允许的最大需求下,无法保证所有进程都能完成。

银行家算法对这一区别作出了形式化描述。对于 nn 个进程和 mm 类资源,设 Available\mathrm{Available} 记录尚未分配的各类资源数量,Allocationi\mathrm{Allocation}_i 记录进程 ii 持有的资源,Maxi\mathrm{Max}_i 记录该进程声明的最大需求。该进程剩余的潜在需求为

Needi=Maxi−Allocationi.\mathrm{Need}_i=\mathrm{Max}_i-\mathrm{Allocation}_i.

安全性检查从 Work=Available\mathrm{Work}=\mathrm{Available} 开始。算法反复寻找一个尚未完成、且各类资源需求均不大于 Work 中对应数量的进程,将其标记为能够完成,并将其当前持有的资源数量加到 Work 中。如果所有进程都能被标记,则该状态是安全的。只有当请求不超出已声明的剩余需求、所需资源可用,且试分配后的状态通过安全性检查时,才会批准该请求。

例如,假设系统有十个相同的资源单位。P1 持有五个,最多还需要两个;P2 持有两个,最多还需要三个。此时有三个空闲单位,因此可以让任一进程先执行完毕。如果再给 P2 分配两个单位,就只剩一个空闲单位。P2 仍可在获得这最后一个单位后执行完毕,释放其持有的五个单位,从而让 P1 也能执行完毕。相比之下,如果 P1 和 P2 声明的最大需求分别为八个和六个单位,那么相同的初始分配状态就是不安全的:P1 可能还需要三个单位,P2 可能还需要四个单位,而草率分配资源后,两者都可能无法完成。

直接实现的安全性检查在最坏情况下需要 O(n2m)O(n^2m) 的时间,因为可能需要反复扫描,才能找出能够完成的进程。在实际应用中,更重要的是该算法的前提假设:必须事先知道最大需求,资源数量必须具有实际意义,而且进程完成时必须按模型所设定的方式释放资源。通用应用程序往往在运行过程中才逐步确定自身需求,因此很难满足这些假设。银行家算法至今仍具有重要影响,因为它精确地说明了:避免不安全的资源分配,与仅仅检查是否已经存在死锁,是两回事。

检测、恢复与超时机制的局限

死锁检测允许进行可能存在风险的资源分配,再检查是否确实形成了死锁。当死锁很少发生,而严格的预防规则又会降低正常情况下的并发程度时,这种方式可能更有优势。检测可以定期运行,也可以在某个请求等待足够长的时间后运行,或在每次新增依赖关系时运行。频繁检查可以缩短死锁持续的时间,但也会消耗处理时间,并且可能需要围绕共享的锁管理结构进行协调。

对于采用合取等待的单实例资源,检测等待图中是否存在环就足够了。标准的图遍历算法可以在 O(V+E)O(V+E) 时间内识别环,其中 VV 是顶点数,EE 是边数。多实例资源则需要基于资源分配情况进行检测。这类检测器会考察当前的资源分配、尚未满足的请求以及可用资源,反复找出能够完成执行并释放所持资源的进程。与银行家算法的安全性检查不同,它不必使用未来可能出现的最大需求,因为它检查的是当前请求能否得到满足。

一旦检测到死锁,恢复过程就必须改变依赖关系的结构。可采取的措施包括终止所有参与者、中止某个选定的参与者、将工作回滚到某个检查点,或回收状态能够安全恢复的资源。选择牺牲对象时,可以考虑优先级、已完成的工作量、回滚成本、持有的资源,以及对依赖该对象的操作的影响。反复选择同一个代价较低的牺牲对象可能导致其饥饿,因此选择策略也可以将以往的中止情况纳入考量。

只有当系统具备明确定义的机制来撤销部分已完成的工作时,恢复才比较简单。中止一个数据库事务,可以在恢复事务状态的同时释放其持有的锁。相比之下,终止任意一个操作系统线程,却可能使内存中的数据结构处于不一致状态,或使锁被永久占用。如果某项操作已经发送了电子邮件、驱动了设备,或调用了外部服务,那么回滚本地内存并不能撤销这些外部影响。恢复协议必须区分可逆的状态变更,以及需要通过补偿或对账处理的操作。

超时机制更简单,但也不够精确。等待时间足够长时,可以让操作失败并释放资源,从而打破某些死锁。但在一般的异步系统中,任何有限的超时时限都无法可靠地区分死锁与异常缓慢的执行。因此,超时体现的是对可接受等待时间的策略选择,而不是循环依赖存在的证明。此外,只有在取消操作确实释放了相关资源,或使另一个参与者能够继续执行时,超时才能打破死锁。如果只是放弃请求,却仍让其持有锁或让远程工作继续运行,原有的阻塞就可能依然存在,还会带来额外的清理问题。

数据库系统中的死锁

死锁在数据库管理系统中尤为重要,因为事务往往会在执行过程中,对陆续发现的数据获取许多锁。例如,一个转账事务可能先更新账户 A,再更新账户 B,而另一个事务则先更新 B,再更新 A。如果两个事务都在保留第一把锁的同时请求第二把锁,就可能发生死锁,即使每条语句单独来看都合法,而且两个事务都遵守数据库的并发控制规则。

两阶段锁定将锁的获取与释放分开:事务一旦开始释放锁,就不能再获取新的锁。其严格变体会将排他锁一直保留到事务结束,从而更容易防止其他事务读到尚未提交的更新。这些协议在各自适用的条件下支持可串行化或可恢复的调度,但其本身并不能防止死锁。涉及的资源可能是行、页、表、数据库索引条目或键值范围,而不一定是应用层对象。

锁转换会形成另一种常见的死锁模式。两个事务可能都持有某个数据项的共享锁,随后又各自请求排他锁以修改该数据项。每个事务的锁升级请求都与另一个事务持有的共享锁冲突,因此双方都无法继续执行。有些系统提供更新锁模式,或对锁转换施加限制,以减少这类情况。范围锁和与谓词相关的锁可能产生不那么明显的依赖关系,不像两条语句更新同一行那样直观,因为为了防范新插入且符合条件的记录,锁的保护范围会超出现有的单条记录。

数据库锁管理器通常会构建等待图,并在检测到环时选定一个牺牲事务,将其中止。随后,事务的撤销或恢复机制会撤销其修改并释放其持有的锁。另一个事务便可继续执行,而被中止的事务则可以重新尝试执行。重试时需要注意外部影响和事务边界:如果客户端只重复执行最后一条语句,就可能无法重现原先由多条语句组成的操作所要实现的逻辑。

基于时间戳的预防方法提供了另一种选择。在 **wait-die(等待—死亡)**策略下,较老的事务可以等待较新的事务,但如果较新的事务请求较老事务持有的资源,就会被中止。在 **wound-wait(伤害—等待)**策略下,较老的请求事务可以迫使持有资源的较新事务中止,而较新的请求事务则要等待持有资源的较老事务。这些规则使等待边始终沿事务年龄的同一方向延伸,从而排除形成环的可能。在重试时保留被中止事务的原始时间戳,有助于避免它不断被更新的事务挤占。

多版本并发控制允许读操作使用较早的已提交版本,而不必阻塞写操作,从而减少某些冲突。但它并不能在所有情况下消除死锁。写操作之间仍可能发生冲突,显式加锁可能引入等待,而模式或元数据操作也可能使用额外的锁。同样,可串行化与无死锁是两种不同的性质:前者约束并发执行结果的语义,后者则关乎系统究竟能否产生结果。

分布式死锁与不完整信息

在分布式计算中,依赖环可能跨越多台机器或多个管理组件。站点 A 上的事务可能正在等待站点 B 上的锁,而 B 上持有该锁的事务又在等待 C 上的某项服务,该服务则依赖于 A 上受阻的工作。每个局部组件看起来都可能只是在等待一项正常的远程操作。任何单独的锁管理器都未必掌握足以识别完整依赖环的信息。

集中式检测器可以收集依赖信息,构建全局等待图,但各份报告的到达时间并不一致。分层设计通过多个层级汇总信息,而完全分布式的算法则由参与者相互交换消息。这些方案在通信开销、瓶颈、故障处理以及识别稳定死锁的速度方面各有差异。问题不仅在于图的规模庞大,还在于观测信息经由网络传输时,图本身也在不断变化。

这就可能产生幻影死锁:检测器将从未同时存在的依赖关系组合在了一起。例如,一份关于 A 等待 B 的旧报告,可能在该等待已经结束后才到达,而一份较新的报告则指出 B 正在等待 A。即使实际从未出现过依赖环,将这两条依赖关系合并后也会呈现出环。版本号、明确定义的观测协议,以及恢复操作前的验证,都有助于区分当前依赖关系与过时信息。检测器还必须将消息延迟、进程故障与资源死锁区分开来。

分布式边追踪算法通过沿等待边发送探测消息来探查依赖关系。1983 年发表的 Chandy–Misra–Haas 算法就是其中具有重要影响的例子。在适用的合取等待模型下,一个受阻的发起进程沿着依赖关系向相关进程发送探测消息;在满足算法假设的前提下,探测消息若返回发起进程,就可以确认存在循环依赖。其他等待模型下的算法需要采用不同的判定条件,因为存在一条环形路径,并不意味着不存在另一条能够使计算继续推进的路径。

分布式事务还会引入一种相关但不同的阻塞问题。在两阶段提交中,已经完成准备的参与者如果无法获知协调者的决定,就可能无法独立决定提交还是中止。这可能导致锁一直被持有,并阻碍其他事务,但由协调者引起的阻塞并不一定是死锁:其中可能并不存在循环等待。系统可能同时遭遇这两种问题,因此,消除事务决策的不确定性与检测资源依赖环是两项不同的职责。

即使没有分布式锁管理器,跨服务调用也可能造成应用层死锁。服务 A 可能在持有本地锁的同时同步调用 B;随后,B 又沿着一条需要获取该锁的路径回调 A。如果最初的调用正在等待回调完成,那么这个依赖环就同时跨越了锁的持有关系与网络通信。若诊断仅局限于本地互斥锁图或远程调用图中的任何一个,就会遗漏部分依赖关系。

通信、执行容量与硬件

死锁并不限于显式锁。在进程间通信中,进程可能会等待发送或接收操作,而参与通信的各方都无法执行这些操作。采用同步会合通信时,如果两个进程都试图先执行阻塞式发送,再执行接收,就可能一直阻塞。在带缓冲的通信中,可用容量或许允许最初的数据交换,但随后仍可能进入死锁状态:每个参与方都持有无法继续转发的数据。

有界队列体现了容量作为资源的重要性。生产者可能因队列已满而阻塞,同时却持有消费者取出队列元素所需的互斥锁。单独考察队列操作或互斥锁操作,都无法看清问题的全貌。同样,条件变量协议若实现不当,也可能在等待某个条件时,仍持有使该条件成立所必需的锁。标准的条件变量操作会在等待时以原子方式释放关联的互斥锁,并在返回前重新获取它,从而避免这种特定的死锁模式。

执行槽位也可能构成一种有限资源。假设一个线程池有 kk 个工作线程,全部 kk 个线程都在运行父任务,而每个父任务又向同一个线程池提交一个子任务,并同步等待其完成。由于所有工作线程都被正在等待的父任务占用,子任务无法运行。这通常称为线程池饥饿或线程池死锁。扩大线程池可能只是推迟故障出现,而不能消除这种依赖模式。一些调度器通过协作执行、协助执行工作或对阻塞任务进行特殊处理来缓解这一问题,但是否具备这些行为取决于运行时系统。

事件循环中也有类似情况。在事件循环上运行的回调,可能同步等待某个结果,而产生该结果的完成回调又必须在同一个事件循环上执行。由于事件循环必须等到当前回调返回后才能调度完成回调,执行便无法继续。异步编程在常规的异步等待期间不会占用事件循环,但异步语法本身并不能消除循环依赖:两个任务仍可能各自等待一个依赖于对方完成的结果。

硬件通信网络也会遇到类似的资源循环依赖。在采用虫孔路由的互连网络中,数据包可能在等待下一个通道时,仍占用已有通道或缓冲区。多个数据包由此可能形成通道依赖环。路由规则可以禁止某些转向,使相关依赖图保持无环;虚拟通道则将流量划分到不同的逻辑通道类别中,通过组织这些类别,可以提供一条无死锁的逃逸路径。

流量控制、路由和协议依赖必须一并考虑。即使路由算法不存在通道依赖环,也可能卷入更高层的请求—响应死锁:请求耗尽了传送响应所需的全部缓冲空间,而只有这些响应到达后,请求占用的资源才能释放。为请求和响应分别配置资源,是一种常见的设计方法。软件与硬件中的核心抽象始终相同:要取得进展,就必须存在一条可执行的状态转换序列,而有限容量也可能成为资源持有与等待结构的一部分。

验证、诊断与进展保证

死锁分析是形式验证的一项重要应用。模型可以表示线程、锁、通道及相关程序状态,进而探索执行是否可能到达一个既未终止、又无法进行任何允许操作的状态。在模型检测中,有限状态探索可以找出导致死锁的具体交错执行序列。难点在于状态空间的增长:增加线程、队列条目或可能的消息顺序,都会使可达配置的数量迅速增加。

没有任何可执行转移的状态并不总是错误。必须区分正常终止与非预期的停滞;即便系统其他部分仍有无关的转移可以执行,某个子系统也可能已经陷入死锁。时序规约可以表达诸如“每个已接受的请求最终都必须完成”之类的要求,但其含义取决于公平性假设。如果调度器始终不让某个就绪线程运行,即使不存在锁依赖环,也可能违反进展要求。因此,验证需要将结构性死锁与不公平调度造成的进展失败区分开来。

静态分析可以从源代码中推断锁获取关系,并报告潜在的顺序依赖环。类型系统和所有权系统则可以在执行前强制落实更严格的约束。这类技术面临别名、动态分派、回调以及动态创建对象等难题:两个引用可能指向同一把锁,而库调用可能获取在调用处看不到的资源。保守分析可能报告任何可行执行都不会实际形成的依赖环,而不完备的分析则可能漏掉真实的依赖关系。

运行时锁顺序检查会记录执行过程中观察到的关系。例如,Linux 的 lockdep 机制会根据锁类别和获取依赖关系进行推断,以识别潜在的不安全模式,其中也包括与中断上下文的交互。这类工具无需等待程序真正卡死,就能发现危险的锁获取顺序,但其覆盖范围取决于实际执行了哪些路径,以及对锁使用情况的表示是否准确。在运行时检测某一类锁依赖环,并不能证明所有通信依赖或容量依赖都是安全的。

实际诊断需要综合线程栈、锁的持有情况、事务等待情况、队列占用情况以及请求跟踪信息。有效的依赖关系重建不仅要查明每个参与者在等待什么,还要确定谁能够满足这一等待条件,以及是什么阻止了后者采取行动。多次采集快照有助于区分稳定的依赖关系与暂时缓慢的操作。当等待跨越网络调用、工作线程池和事务边界时,跨进程标识符尤为重要。

更严格的进展术语区分了几种不同的保证。无死锁性通常排除了由协议导致的整体停滞,但并不保证每个参与者都能成功完成操作。无锁算法在其规定的执行假设下保证系统整体能够持续取得进展,而无等待算法则保证每项操作都能在自身执行的有限步数上界内完成。这两种保证都不会自动扩展到包含该算法的应用程序,因为应用程序可能执行阻塞式输入/输出,或等待外部服务。因此,对组件进展保证的理解,必须限定在其规约所涵盖的操作与依赖关系范围内。