死锁与资源分配

资源持有与等待关系

多个任务可能在持有部分资源的同时申请其他资源。当每个任务都等待同一组任务中的其他成员释放资源时，这组任务可能无法继续。资源包括互斥锁、有限数量的缓冲区、设备和连接，也包括只能由特定任务产生的事件。分析死锁需要明确谁持有什么、正在等待什么，以及资源在什么条件下释放。

死锁

在给定资源和执行模型中，若一组任务中的每个任务都在等待只能由该组内其他等待任务触发的事件，且不存在使其中任务继续的外部动作，则这组任务处于死锁。判断时需要把超时、取消、资源抢占和故障恢复等可能的外部动作纳入模型。

对可重复使用的互斥资源，经典分析通常检查四个条件：资源排他使用；任务持有已有资源并等待新资源；资源无法被系统强制收回；等待关系形成循环。破坏其中任一必要条件，可以排除对应模型下的死锁。四个条件描述的是等待结构，不能仅凭程序使用了两把锁就断定已经发生死锁。

死锁、饥饿和活锁还需要分别识别。饥饿任务长期得不到服务，但其他任务仍在进展；活锁中的任务持续执行重试或退让，却没有完成业务工作。超时后立即以完全相同节奏重试，可能把阻塞变成反复冲突，因此恢复策略还应考虑退避和公平性。

单实例资源的等待图

每种资源只有一个实例时，可以构造任务等待图：若任务甲正在等待任务乙持有的资源，就画一条从甲指向乙的有向边。在资源无抢占、持有者只有继续执行才能释放的模型中，等待图中的环给出死锁。若资源类型有多个实例，仅看到类型层面的环还不足以判断，因为其他实例可能被组外任务释放。

两把锁的循环等待

任务甲已经持有锁一，接着等待锁二；任务乙已经持有锁二，接着等待锁一。两者都在获得第二把锁后才释放第一把锁，且没有超时或取消。等待图包含甲指向乙与乙指向甲两条边，形成长度为二的环。

我们检查两个释放条件：甲要先获得乙持有的锁二，乙要先获得甲持有的锁一，当前没有任务能达到释放位置。因此两项任务死锁。若所有任务都按锁一、锁二的顺序申请，则其中一个任务在获取锁一时就等待，尚未持有锁二；另一个任务能够依次完成并释放，两节点环不会形成。

更一般地，为每把锁赋予全局唯一序号，并要求任务按严格递增次序获取。假设存在环，沿环每一步都表示任务持有较小序号、等待较大序号；绕回起点就要求起点序号严格小于自己，产生矛盾。这个论证要求所有获取路径都遵守同一顺序，回调、异常处理和动态选锁也必须纳入检查。

多实例资源与安全序列

有多种、多实例资源时，系统可以记录总量、已分配量与任务声明的最大需求。设资源类型数为 $m$，任务数为 $n$。向量 $\mathbf A$ 表示当前空闲资源数，矩阵 $C_{ij}$ 表示已经分配给任务 $i$ 的第 $j$ 类资源，$M_{ij}$ 表示该任务声明的最大需求，剩余需求为

$N_{ij}=M_{ij}-C_{ij}.$

这里各元素均为非负整数，向量比较按分量进行。若能找到一个任务顺序，使每个任务的剩余需求都由当前空闲资源满足，并在完成后归还它已经持有的资源，就得到安全序列。安全状态保证存在这样一种完成顺序，前提是最大需求声明准确，资源最终会归还，任务在得到所需资源后能完成。

两类资源的安全性检查

资源甲、乙总量分别为六和四。三个任务的已分配向量依次为 $(1,1)$、$(2,0)$、$(1,1)$，最大需求依次为 $(3,2)$、$(4,1)$、$(2,2)$。因此空闲向量为 $(2,2)$，剩余需求依次为 $(2,1)$、$(2,1)$、$(1,1)$。

我们先完成第三个任务：其剩余需求不超过 $(2,2)$，完成后归还已分配量 $(1,1)$，检查用的空闲量增加为 $(3,3)$。随后第一个任务完成，空闲量变为 $(4,4)$；第二个任务完成后变为 $(6,4)$，与总资源量一致。由此得到安全序列第三、第一、第二。

若第二个任务此时额外申请 $(2,1)$，申请没有超过剩余需求，也没有超过当前空闲量。但试分配后空闲量变为 $(0,1)$，各任务剩余需求依次为 $(2,1)$、$(0,0)$、$(1,1)$；第二个任务能够先完成并归还它试分配后的 $(4,1)$，因此该请求仍保持安全。安全检查要在试分配后的完整状态上执行，不能只检查空闲资源是否够用。

银行家算法把每次请求先放入临时状态，检查请求上限、当前可用量和安全序列，只有通过后才正式分配。安全性检查可能需要反复扫描任务，朴素实现的成本约为 $O(n^2m)$。对难以提前声明最大需求、资源经常变化的应用，这些前提可能难以满足，需要选择其他管理方式。

不安全状态与当前死锁

不安全状态表示无法保证所有任务都按最大需求完成，当前任务仍可能只请求较少资源并顺利结束。死锁检测则使用已经发生的等待请求，判断现时是否存在无法继续的任务。把未来最大需求和当前请求混为一谈，会高估当前死锁范围，也会错误理解安全性拒绝的原因。

考虑一种总量为四的资源，两个任务各持有两个实例，每个任务声明最多需要三个。系统没有空闲实例，任何任务都可能再申请一个，所以按最大需求计算没有安全序列。如果两者尚未发出新申请，其中一个实际只需现有两个就能结束，系统仍能继续；如果两者都申请第三个且必须等到获得后才能释放，便出现当前死锁。

检测多实例资源时，可从空闲资源开始，反复选取当前请求能够被满足的任务，把它视为完成并归还已持有资源。若仍有持有资源的等待任务无法消去，应进一步检查这部分任务的依赖。检测结果还应与任务取消、资源释放通知和设备状态结合，避免在不一致的观察时刻把短暂等待误判为永久阻塞。

预防与恢复的工程约束

一次申请全部所需资源能减少持有并等待，但会让尚未使用的资源提前被占据，降低利用率。按全局顺序申请锁通常实现成本较低，但动态资源集合需要先排序或采用分阶段设计。允许抢占适用于状态能够保存和恢复的资源；对已经发出的外部操作或半完成的文件修改，强制回收还需要补偿措施。

检测后终止某个任务可能打破等待环，也可能留下不完整业务状态。恢复策略要确定终止对象、处理已经完成的外部动作，并防止重试重复写入。数据库中的事务回滚提供了一种受控恢复机制，普通线程持锁执行的任意代码则通常没有自动回滚能力。

定位问题时，记录锁获取位置、持有者、等待者和时间能够重建等待图。对有超时的接口，日志还应区分等待结束是成功获得资源还是超时退出。我们分析一次故障时先复原具体环，再检查所有路径中的锁顺序；仅增加超时可能缩短单次停顿，却保留原来的依赖错误。

资源分配练习

练习标记完成

所属知识

锁顺序

难度

2/5

甲持有锁一等待锁二，乙持有锁二等待锁三，丙持有锁三等待锁一。画出等待关系，并给出一项预防规则。

查看解答

等待边为甲到乙、乙到丙、丙到甲，形成环。给锁建立统一顺序，例如一、二、三，并要求所有嵌套获取按递增次序执行，能够破坏循环等待条件。

练习标记完成

所属知识

剩余需求

难度

2/5

某任务最大需求为三、五，已经分配一、二。求剩余需求，并列出批准新申请的条件。

查看解答

逐分量相减，剩余需求为 $3-1=2$、$5-2=3$，因此向量为 (2,3)。申请还需要同时不超过剩余需求和当前可用资源，并通过试分配后的安全性检查。

练习标记完成

所属知识

安全序列

难度

3/5

一种资源总量四，两个任务分别持有一和二，最大需求分别为二和四。检查是否存在安全完成顺序。

查看解答

先满足第一个任务还需的一份资源，它完成后归还已持有的一份，使检查用空闲量变为两份。第二个任务还需两份，随后完成，因此顺序第一、第二安全。

练习标记完成

所属知识

状态判断

难度

3/5

安全性检查没有找到安全序列，能否据此断定所有任务当前已经死锁？说明判断还需要哪些信息。

查看解答

不安全只表示无法按声明的最大需求保证完成。若任务实际需求较小，它仍可能完成并释放资源。确认当前死锁还需查看已经发出的请求、持有关系以及超时或外部释放等进展条件。

死锁分析参考资料

Operating Systems: Three Easy Pieces

Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau · 2023 · Arpaci-Dusseau Books

打开官方来源

OSTEP 的 Concurrency Bugs 章节讨论死锁条件、锁顺序与避免循环等待的办法。参考这些条件时，应先写出资源实例数量和释放规则，再决定采用等待图、最大需求检查还是当前请求检测。

xv6: a simple, Unix-like teaching operating system

Russ Cox, Frans Kaashoek, Robert Morris · 2025 · Massachusetts Institute of Technology

打开官方来源

MIT xv6 教材第 7.4 节结合内核中的嵌套锁说明获取顺序，第 9 章给出睡眠与唤醒依赖。资源分配表的算例是本章为说明多实例安全性构造的小模型，阅读内核实现时还需补充中断、取消和进程退出的约束。