死锁

核心定义

死锁 是多个进程因争夺资源而相互等待、无法继续执行的状态。

死锁产生的四个必要条件：互斥条件（资源不能共享）、请求并保持条件（持有资源又请求新资源）、不可剥夺条件（已分配资源不能强行回收）、循环等待条件（进程等待链形成环）。四个条件必须同时满足才会发生死锁。

死锁处理的四种策略：死锁预防（静态破坏必要条件）、死锁避免（动态判断系统是否安全）、死锁检测（事后发现死锁）、死锁解除（剥夺资源或终止进程）。

银行家算法 是经典的死锁避免算法，通过判断分配资源后系统是否处于安全状态（是否存在 安全序列）来决定是否允许资源请求。

安全状态定义：系统能按某种顺序为每个进程分配所需资源，使所有进程都能完成，即 $\exists$ 安全序列 $\langle P_1, P_2, \dots, P_n \rangle$。

资源分配图 用于检测死锁：若图中存在环且每类资源只有一个实例，则系统死锁；若每类资源有多个实例，环是死锁的必要不充分条件。

死锁 $\neq$ 饥饿：死锁是彼此等待、全部阻塞；饥饿是某个进程长期得不到资源，其他进程可能正常运行。

关键细节 / 操作步骤

1. 判断死锁前提：是否存在多个进程竞争多个不可共享资源。
2. 验证四条件：逐条检查互斥、请求并保持、不可剥夺、循环等待是否同时满足。
3. 死锁预防策略：破坏互斥（难以实现）、破坏请求并保持（预分配全部资源）、破坏不可剥夺（可抢占）、破坏循环等待（顺序资源分配法）。
4. 银行家算法步骤：① 初始化 Available、Max、Allocation、Need 矩阵；② 收到请求后检查 Request $\leq$ Need 且 Request $\leq$ Available；③ 试探分配后检查是否存在安全序列；④ 安全则正式分配，不安全则等待。
5. 安全性算法：设 Work = Available，找 Need $\leq$ Work 的进程，模拟完成并回收资源，循环直到所有进程完成（安全）或无法继续（不安全）。
6. 资源分配图化简：依次消除不阻塞的进程（已获全部资源的进程），若最终所有进程都可消除则无死锁。
7. 死锁解除方法：剥夺资源（从某进程强行收回）、回滚（恢复到检查点）、终止进程（代价最大）。
8. 若题目给资源分配图：先找环，再结合资源实例数判断是否一定死锁。
9. 若题目问”预防 vs 避免”：预防是事前破坏条件（静态规则），避免是运行时动态判断安全性。
10. 若题目问”检测 vs 避免”：检测是事后发现（允许死锁发生再处理），避免是事前预防（不允许进入不安全状态）。

银行家算法详解

本节是死锁避免的旗舰算法，整合自原「银行家算法」专题笔记。

背景与思想

• 银行家算法是一种经典的死锁避免算法，由 Dijkstra 提出。
• 核心思想：在资源分配前，预先判断此次分配是否会导致系统进入不安全状态。若会，则拒绝分配；否则予以分配。
• 类比银行放贷：银行不会将全部资金借给单个客户，必须保留足够资金满足其他客户的最大需求，避免资不抵债而”死锁”。

数据结构

设系统中有 $n$ 个进程、$m$ 类资源。

核心关系：Need = Max - Allocation，Available = 系统总资源 - 所有已分配资源之和。

安全性算法（Safety Algorithm）

用于检测系统是否处于安全状态，能否找到一个安全序列。

步骤：

1. 设 Work = Available，Finish[i] = false（i=0..n-1）。
2. 查找满足如下条件的进程 i：
   • Finish[i] == false
   • Need[i] <= Work（向量比较，每个分量均 ≤）
3. 若找到，则：
   • Work = Work + Allocation[i]
   • Finish[i] = true
   • 将该进程加入安全序列
   • 返回步骤 2
4. 若无法找到且还有未完成进程 → 系统处于不安全状态，可能发生死锁。 若所有进程 Finish[i] == true → 系统处于安全状态，输出安全序列。

时间复杂度：$O(n^2 \times m)$。安全序列不唯一，只要能找到一个即证明系统安全。

注意：安全状态 ⇒ 无死锁；不安全状态 ≠ 死锁，只是有死锁风险。

资源请求算法（Resource-Request Algorithm）

当进程 i 发起资源请求 Request[i]（向量）时：

1. 若 Request[i] > Need[i] → 拒绝（出错，请求超过声明的最大需求）。
2. 若 Request[i] > Available → 进程必须等待。
3. 否则系统试探性分配：

   Available = Available - Request[i]
   Allocation[i] = Allocation[i] + Request[i]
   Need[i] = Need[i] - Request[i]

4. 执行安全性算法：
   • 若安全 → 正式分配，进程继续。
   • 若不安全 → 回滚试探分配，进程等待。

记忆口诀

“先看请求超不超，二看资源够不够，试探分配算工效，安全通过真给力，不安全就回滚等。“

经典例题：5 进程银行家算法

题目：假设系统中有 5 个进程 {P0,P1,P2,P3,P4} 和 3 类资源 {A,B,C}，资源总数分别为 (10,5,7)。在 T0 时刻：

问：T0 时刻系统是否安全？若安全，给出安全序列。

解答：

1. 计算 Available = (10,5,7) - 各进程已分配之和。Allocation 之和 = (7,2,5)，故 Available = (3,3,2)。
2. 计算 Need = Max - Allocation：

3. 执行安全性算法：
   • Work = (3,3,2)，先找 Need ≤ Work 的进程：P1 (1,2,2) 满足，P3 (0,1,1) 也满足。选 P1。
   • 分配后 Work = Work + Allocation[1] = (3,3,2)+(2,0,0) = (5,3,2)，Finish[1]=true。
   • 接着 P3：Work = (5,3,2)+(2,1,1) = (7,4,3)，Finish[3]=true。
   • 接着 P4：Need(4,3,1)≤(7,4,3)，Work = (7,4,3)+(0,0,2) = (7,4,5)。
   • 接着 P0：Need(7,4,3)≤(7,4,5)，Work = (7,4,5)+(0,1,0) = (7,5,5)。
   • 接着 P2：Need(6,0,0)≤(7,5,5)，全部完成。

答案：系统处于安全状态，一个安全序列为 $\langle$ P1 → P3 → P4 → P0 → P2 $\rangle$（不唯一）。

⚠️ 易错辨析

• 四个条件是必要不充分条件：满足它们只说明”可能死锁”，不能直接等同于已死锁。若题目问”满足四条件就一定死锁吗”，答案是否。
• 银行家算法属于死锁避免，不是死锁检测，也不是死锁预防。三者出发点不同：预防破坏条件、避免判断安全、检测事后发现。
• 银行家算法必须预先知道每个进程的最大需求 Max，这是它区别于检测/预防算法的关键前提，也是它在实际系统中受限的原因。
• 死锁 $\neq$ 饥饿：死锁是互相等待、全部卡住，饥饿是某个进程等不到资源但系统整体可能还在运行。
• 单实例资源类型中，资源分配图的环与死锁等价；多实例资源类型中，环是死锁的必要不充分条件。
• 安全状态 $\Rightarrow$ 无死锁，但无死锁 $\not\Rightarrow$ 安全状态（可能处于不安全但恰好未死锁）。
• “循环等待危险”的核心原因是请求链形成闭环，任一进程都无法独立推进。

💡 技巧与口诀

• 口诀：互斥占有不可抢，成环等待就危险。
• 应用场景：题目提到”资源申请顺序""进程阻塞""无法推进”，先检查死锁四条件。
• 看到”安全序列”先想到银行家算法和系统是否处于安全状态。
• 比较”预防/避免/检测/解除”最稳妥方法：先给定义，再给典型算法或手段。
• 顺序资源分配法（给资源编号，按序申请）是破坏循环等待的常见预防手段。

📝 真题闭环 题目：系统中有 3 种资源 R1、R2、R3，可用数量分别为 (3, 3, 2)。有 4 个进程 P1-P4，当前分配和最大需求如下表。判断当前系统是否处于安全状态，若安全给出安全序列。

进程	Allocation	Max
P1	(1,0,1)	(2,1,1)
P2	(1,1,0)	(2,2,1)
P3	(0,1,0)	(1,2,1)
P4	(0,0,1)	(1,1,2)

解题思路：

• 审题抓”安全状态判断”，切入点是银行家算法安全性检查。
• 计算 Available = 总资源 - 已分配 = (3,3,2) - (2,2,2) = (1,1,0)。
• 计算 Need = Max - Allocation：P1(1,1,0)，P2(1,1,1)，P3(1,1,1)，P4(1,1,1)。
• 第 1 轮：找 Need $\leq$ Work(1,1,0) 的进程 $\to$ P1 满足，P1 完成后 Work = (1,1,0)+(1,0,1) = (2,1,1)。
• 第 2 轮：找 Need $\leq$ Work(2,1,1) $\to$ P2、P3、P4 都可能满足，选 P2，Work = (2,1,1)+(1,1,0) = (3,2,1)。
• 第 3 轮：选 P3，Work = (3,2,1)+(0,1,0) = (3,3,1)。第 4 轮：选 P4，Work = (3,3,1)+(0,0,1) = (3,3,2)。
• 所有进程均可完成，存在安全序列。

答案：系统处于 安全状态，一个安全序列为 $\langle$ P1, P2, P3, P4 $\rangle$。