Lecture 5：知识 - 死锁
408 学习笔记：Lecture 5：知识 - 死锁。保留原有知识内容、公式与图示；有对应原件时提供查看和下载入口。
本页目录
死锁题先判断“是否有资源竞争”和“四个必要条件”，再分清预防、避免、检测、解除四种策略。银行家算法判断的是安全性，不是直接判定系统已经死锁。
5.1 概念与辨析
5.1.1 死锁
在 408 的经典资源分配模型中，死锁是并发环境下多个进程因竞争资源而互相等待对方持有的资源，导致一组进程都处于阻塞状态、无法继续推进的现象；题目通常讨论至少两个进程形成的循环等待。工程语境还存在自死锁：单线程再次获取自己已持有的非递归锁，也会永久阻塞。因此，“死锁必定至少涉及两个进程”只适用于经典考试模型，不应当作所有系统实现中的绝对结论。
| 概念 | 含义 | 进程状态/成因 |
|---|---|---|
| 死锁 | 多个进程相互等待资源，彼此无法推进 | 相关进程阻塞；资源分配和请求关系形成僵局 |
| 饥饿 | 一个进程长期得不到所需资源或 CPU | 可长期处于就绪或阻塞；调度/分配不公平导致 |
| 死循环 | 程序反复执行某段逻辑而不退出 | 可处于运行态；通常是程序逻辑错误 |
| 活锁 | 进程不断改变状态、彼此谦让却没有实际进展 | 仍在活动；常由错误的重试/让步策略造成 |
循环等待是死锁的必要条件，但不充分。例如同类资源存在多个实例时，资源分配图有环不必然表示已经死锁。安全状态说明当前至少存在一条可使全部进程完成的安全序列，因此当前并未死锁；它不是对任意后续分配的永久保证。只有进程申报的最大需求有效，且系统以后按安全序列推进，或每次分配后都保持安全状态，才能保证继续避免死锁。
5.2 产生死锁的四个必要条件
四个条件必须同时满足才可能产生死锁：
- 互斥条件：资源一次只能由一个进程使用。可同时共享的资源不会因竞争本身造成死锁。
- 不可剥夺条件：进程获得的资源在未用完前不能被其他进程强制夺走，只能主动释放。
- 请求和保持条件：进程已保持至少一个资源，又提出新的资源请求；请求不能满足时被阻塞，却仍不释放已有资源。
- 循环等待条件：存在进程资源的环形等待链，每个进程等待下一个进程持有的资源。
记忆：互斥、不可剥夺、请求保持、循环等待。死锁预防的本质是破坏其中至少一个条件。
5.3 死锁处理策略总览
| 策略 | 基本思想 | 何时动作 |
|---|---|---|
| 预防 | 静态破坏四个必要条件之一 | 分配前即限制资源使用方式 |
| 避免 | 每次资源请求都只在仍安全时批准 | 运行中动态判断安全状态 |
| 检测与解除 | 允许发生，定期检测后恢复 | 死锁发生后处理 |
预防限制强、资源利用率可能低；避免需要知道进程最大需求并频繁做安全性检查；检测/解除资源利用率高但恢复代价大。
5.4 死锁预防
5.4.1 破坏互斥条件
尽量把独占资源改为可共享服务。例如使用 SPOOLing：进程把打印输出写入共享磁盘队列，由后台打印进程独占物理打印机，普通进程不再直接竞争打印机。并非所有资源都可共享，故该策略适用范围有限。
5.4.2 破坏不可剥夺条件
可采用两类方式：
- 进程请求新资源不能满足时，立即释放已持有资源，稍后重新申请。
- 在满足安全规则和优先级约束时，由系统剥夺某些进程已持有的资源并分配给更合适的进程。
缺点是实现复杂、可能使前一阶段工作失效；反复释放和重新申请会增加系统开销，并可能导致饥饿。CPU 等资源也不一定能随意剥夺。
5.4.3 破坏请求和保持条件
静态分配法：进程运行前一次申请并获得所需全部资源，资源未满足时不让其投入运行；一旦开始运行，运行中不再申请新资源。
- 优点：实现简单，直接消除“占有又等待”。
- 缺点：资源可能只在很短时间内真正使用，却在整个运行期间被占有，利用率低；有的进程还可能长期等不到全套资源而饥饿。
5.4.4 破坏循环等待条件
顺序资源分配法：为资源编号，规定进程必须按编号递增顺序申请，同类资源通常一次申请完。持有较大编号资源的进程不能回头申请较小编号资源，因此无法形成环路。
例如系统有编号 $1\sim10$ 的资源，某时刻 $P_1$ 持有 $1、3$，$P_2$ 持有 $2、4$，$P_3$ 持有 $5、7$。若所有进程都只能继续申请比自己已持有资源编号更大的资源，那么当前持有全局最大编号资源的进程不可能等待一个更小编号资源；它可以继续推进并释放资源。之后再对剩余进程重复同样推理，循环等待链无法成立。
缺点是资源编号顺序可能与实际使用顺序不一致，造成资源浪费；新增设备会影响编号；用户编程时也必须遵守此顺序。
5.5 死锁避免与银行家算法
5.5.1 安全状态
在各进程最大需求已知且不会临时突破该上限的模型中，若存在一个进程序列 $\langle P_{i_1},P_{i_2},\ldots,P_{i_n}\rangle$，系统按此顺序满足尚需资源时，每个进程都能执行完成并释放已占资源，则该序列为安全序列，当前系统状态是安全的。安全序列可不唯一。
- 找得到至少一个安全序列：当前状态安全、当前没有死锁；若后续只批准仍能保持安全的请求，则可继续保证避免死锁。
- 分配后找不到安全序列：系统不安全；它将来可能发生死锁，但不安全不等于已经死锁。
- 已发生死锁的系统一定不安全。
5.5.2 数据结构与关系
对 $n$ 个进程、$m$ 类资源，银行家算法维护：
| 名称 | 维度 | 含义 |
|---|---|---|
Available[m] |
向量 | 每类当前可用资源数 |
Max[n][m] |
矩阵 | 各进程声明的最大需求 |
Allocation[n][m] |
矩阵 | 已分配给各进程的资源 |
Need[n][m] |
矩阵 | 尚需资源，$Need=Max-Allocation$ |
Request_i[m] |
向量 | 进程 $P_i$ 的本次请求 |
银行家算法属于死锁避免：必须事先掌握最大需求。它可判断当前或试探分配后的系统是否安全，不能直接判定系统是否已经死锁。
5.5.3 安全性算法
- 令
Work = Available，所有进程Finish = false。 - 寻找一个
Finish[i]==false且Need[i] <= Work的进程 $P_i$。 - 假定 $P_i$ 获得所需资源并完成，释放已分配资源：
Work = Work + Allocation[i]，Finish[i]=true，把 $P_i$ 记入安全序列。 - 重复步骤 2；若所有进程都能标为完成，则安全，否则不安全。
手算时每轮只需比较“当前 Work 能否满足某一尚未完成进程的 Need”；选中后把其 Allocation 加回 Work。能选出的顺序就是一条安全序列。
5.5.4 资源请求算法
进程 $P_i$ 提出 Request_i 时：
- 若
Request_i > Need_i，请求超过最大声明，视为错误。 - 若
Request_i > Available，资源暂不足，$P_i$ 等待。 - 否则试探分配：
Available -= Request_i
Allocation_i += Request_i
Need_i -= Request_i
- 对试探后的状态执行安全性算法；安全则正式批准，否则撤销试探分配并让进程等待。
5.5.5 银行家算法完整例题
设系统有三类资源 $A、B、C$，当前可利用资源向量为：
$$ Available=(3,3,2) $$
各进程的最大需求、已分配资源和剩余需求如下。Need 由 Max-Allocation 逐项相减得到。
| 进程 | Max |
Allocation |
Need |
|---|---|---|---|
| $P_0$ | $(7,5,3)$ | $(0,1,0)$ | $(7,4,3)$ |
| $P_1$ | $(3,2,2)$ | $(2,0,0)$ | $(1,2,2)$ |
| $P_2$ | $(9,0,2)$ | $(3,0,2)$ | $(6,0,0)$ |
| $P_3$ | $(2,2,2)$ | $(2,1,1)$ | $(0,1,1)$ |
| $P_4$ | $(4,3,3)$ | $(0,0,2)$ | $(4,3,1)$ |
从 Work=(3,3,2) 开始执行安全性算法，可以得到一条安全序列：
$$ \langle P_1,P_3,P_0,P_2,P_4\rangle $$
| 轮次 | 选中进程 | 判定依据 Need <= Work |
进程完成后 Work = Work + Allocation |
|---|---|---|---|
| 初始 | - | - | $(3,3,2)$ |
| 1 | $P_1$ | $(1,2,2)\le(3,3,2)$ | $(3,3,2)+(2,0,0)=(5,3,2)$ |
| 2 | $P_3$ | $(0,1,1)\le(5,3,2)$ | $(5,3,2)+(2,1,1)=(7,4,3)$ |
| 3 | $P_0$ | $(7,4,3)\le(7,4,3)$ | $(7,4,3)+(0,1,0)=(7,5,3)$ |
| 4 | $P_2$ | $(6,0,0)\le(7,5,3)$ | $(7,5,3)+(3,0,2)=(10,5,5)$ |
| 5 | $P_4$ | $(4,3,1)\le(10,5,5)$ | $(10,5,5)+(0,0,2)=(10,5,7)$ |
五个进程都能完成，所以当前状态安全。安全序列不唯一；只要每一步都满足 Need <= Work，并最终能让全部进程完成，就是合法安全序列。
现在 $P_0$ 发出请求：
$$ Request_0=(2,1,1) $$
先做两项前置检查：
$$ Request_0=(2,1,1)\le Need_0=(7,4,3) $$
$$ Request_0=(2,1,1)\le Available=(3,3,2) $$
两项均满足，可以试探分配。试探后的关键数据为：
$$ Available'=(3,3,2)-(2,1,1)=(1,2,1) $$
$$ Allocation'_0=(0,1,0)+(2,1,1)=(2,2,1) $$
$$ Need'_0=(7,4,3)-(2,1,1)=(5,3,2) $$
对试探后的状态重新执行安全性算法，可取安全序列：
$$ \langle P_3,P_1,P_0,P_2,P_4\rangle $$
| 轮次 | 选中进程 | 判定依据 Need <= Work |
完成后 Work |
|---|---|---|---|
| 初始 | - | - | $(1,2,1)$ |
| 1 | $P_3$ | $(0,1,1)\le(1,2,1)$ | $(1,2,1)+(2,1,1)=(3,3,2)$ |
| 2 | $P_1$ | $(1,2,2)\le(3,3,2)$ | $(3,3,2)+(2,0,0)=(5,3,2)$ |
| 3 | $P_0$ | $(5,3,2)\le(5,3,2)$ | $(5,3,2)+(2,2,1)=(7,5,3)$ |
| 4 | $P_2$ | $(6,0,0)\le(7,5,3)$ | $(7,5,3)+(3,0,2)=(10,5,5)$ |
| 5 | $P_4$ | $(4,3,1)\le(10,5,5)$ | $(10,5,5)+(0,0,2)=(10,5,7)$ |
试分配后仍能找到安全序列，因此系统仍处于安全状态，可以正式批准 $P_0$ 的请求。若试分配后找不到安全序列，则必须恢复试分配前的数据并让 $P_0$ 等待。
5.6 资源分配图、死锁检测与解除
5.6.1 资源分配图
- 圆形结点表示进程；矩形结点表示一类资源，矩形内的小圆点表示该类资源实例数。
- 请求边：进程 → 资源，表示该进程正在申请该类资源的一个实例。
- 分配边：资源 → 进程，表示该资源的一个实例已分配给该进程。
5.6.2 图化简检测算法
检测策略允许死锁先发生。反复执行：
- 在资源分配图中找一个既不阻塞又不是孤点的进程：它的所有资源请求都可由当前空闲实例满足。
- 假定该进程获得资源、执行完成并释放其全部分配资源，删除与该进程相连的请求边和分配边。
- 用新释放的资源继续寻找可完成进程。
若最终所有边都能删除，图可完全化简，系统无死锁；若化简后仍有边相连，仍连着边的那些进程处于死锁状态。注意：系统中并非所有进程都会因一组死锁而死锁。
5.6.3 死锁解除
| 方法 | 做法 | 代价/风险 |
|---|---|---|
| 资源剥夺 | 挂起或回收某些死锁进程的资源，分配给其他进程 | 被剥夺者可能饥饿；需选择牺牲者并保存恢复信息 |
| 撤销进程 | 强制撤销部分或全部死锁进程，释放资源 | 简单但损失大，可能浪费已完成的大量工作 |
| 进程回退 | 让一个或多个进程回到安全检查点（还原点）后重新执行 | 需维护检查点和恢复机制 |
选择牺牲进程时，可考虑：进程优先级、已执行时间、距完成还需多长时间、已占资源量、是交互式还是批处理任务等。目标是在解除死锁的同时尽量减少损失并避免同一进程反复被牺牲。
相关知识
- 科目导航：操作系统导航
- 阅读顺序：上一篇：同步与互斥 · 下一篇：内存管理基础
- 关联专题：资源分配图所需的图概念
5.7 本节复盘
- 死锁是多个阻塞进程因资源相互等待而无法推进；饥饿和死循环不是死锁。
- 四个必要条件为互斥、不可剥夺、请求和保持、循环等待；必要不等于充分。
- 预防是破坏条件，避免是保持安全，检测是发生后化简图，解除是剥夺/撤销/回退。
- $Need=Max-Allocation$；银行家算法找安全序列。当前安全即当前未死锁；在最大需求有效且后续始终保持安全的前提下可继续避免死锁；不安全未必已经死锁。
- 资源分配图中进程→资源为请求，资源→进程为分配；化简后仍有边相连的进程才是死锁进程。