e2hang/Operating-System
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
Operating-System/Homework/05第五章 死锁与饥饿.md
e2hang ef7621a1ae New Homework
2026-06-25 00:09:09 +08:00

38 KiB
Raw Permalink Blame History

第五章 死锁与饥饿

一、知识讲解

本章是操作系统的核心重点章节，每年必考大题（银行家算法、安全性算法、资源分配图）。死锁（Deadlock）与饥饿（Starvation）都是进程竞争资源引起的问题，但本质上不同：死锁是"等不到"，饥饿是"等太久"。

5.1 死锁的概念

5.1.1 死锁定义

死锁（Deadlock）：一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程所占有的、因而永远无法得到的资源，这种现象称为进程死锁。

通俗理解：进程A等进程B手里的资源，进程B又在等进程A（或C、D……）手里的资源，环上谁也得不到谁手里的资源，所有人无限等待。

死锁发生的两个时刻：

  1. 无限等待发生时（事后观察）
  2. 等待发生前——已注定死锁（事前预测，如银行家算法拒绝分配就是"提前避免"）

5.1.2 由定义得出的结论

  1. 参与死锁的进程至少有 2 个。
  2. 每个参与死锁的进程均处于等待资源的状态。
  3. 参与死锁的进程中至少有两个进程已经占有资源（否则大家都空手等不到资源，但若没人占有资源则不构成"等待别人资源"的定义）。
  4. 死锁进程是系统中当前进程集合的一个子集（不是全部进程）。

5.2 死锁的类型

1. 资源竞争引起的死锁（最常见）

  • （1）不同资源类：每个进程分别占有对方需要的资源。例如 P1 占有 R1 等 R2，P2 占有 R2 等 R1。
  • （2）同种资源：多个进程反复申请同类资源（如 4 台打印机），P1 申请 8 次每次申请 1 个，P2 申请 4 次每次申请 1 个。典型问题：信号量/缓冲区的死锁。

举例：4 台打印机，P1 的命令序列为 a a a a a a a a（申请 8 次），P2 的命令序列为 a a a a（申请 4 次）。当 P1 占 3 台、P2 占 1 台时，P1 还需 5 台，P2 还需 3 台——总需 8 台 > 4 台，永久等待。

2. 进程通讯引起的死锁（消息通信）

P1: receive(P2, M1);
P2: receive(P3, M2);
P3: receive(P1, M3);

三人各等对方先发消息，谁也等不到，构成死锁。

3. 其它原因

  • "After you / After you" 现象：互相礼让导致谁也不前进（类似活锁）。
  • 进程推进顺序不当（如未按资源序申请）。

5.3 死锁的条件（Coffman 条件，必要条件）

死锁发生的四个必要条件（Coffman 条件）：

条件 英文 含义 举例
互斥使用（资源独占） Mutual Exclusion 资源一次只允许一个进程使用 打印机、临界资源
不可抢占（不可剥夺） Non-preemption 资源只能由占有者自愿释放，不能被强制夺走 打印机已打印一半不能抢走
保持申请（占有并等待） Hold-and-Wait 进程在保持已有资源的同时再去申请新资源 进程已占打印机又申请磁带机
循环等待（环路等待） Circular Wait 存在进程资源环路，P1等P2、P2等P3、……、Pn等P1 经典环路死锁

重要结论：

  • 当每类资源只有一个实例时，这四个条件是充要条件（有环就一定死锁）。
  • 破坏其中任意一个条件即可消除死锁（这是死锁预防的理论基础）。

5.4 死锁的处理（处理策略总览）

处理死锁有 4 种主要策略，下表对比：

策略 英文 思想 时机 难度/开销
死锁预防 Deadlock Prevention 静态地破坏 4 个必要条件之一 运行前 实现简单但资源利用率低
死锁避免 Deadlock Avoidance 动态地保证系统始终处于安全状态 每次分配前 银行家算法，需预知最大需求
死锁检测 Deadlock Detection 允许死锁发生，但定期检测 运行时 检测后需恢复
死锁恢复 Deadlock Recovery 检测到死锁后采取措施 死锁发生后 终止进程或剥夺资源
鸵鸟算法 Ostrich Algorithm 忽略不管 —— 最省事，实际系统多用

5.5 资源分配图（Resource Allocation Graph）

5.5.1 资源分配图定义

资源分配图：G = (V, E)

  • V = P ∪ R（进程集合 ∪ 资源集合）
  • E = 申请边 ∪ 分配边

两类节点：

  • 进程节点 pi（用圆圈表示）
  • 资源节点 rj（用方框表示，方框内的圆点表示实例个数）

两类边：

  • 申请边 (pi, rj)：由进程指向资源类，表示 pi 申请 rj 中一个实例
  • 分配边 (rj, pi)：由资源实例指向进程，表示该实例已分配给 pi

操作规则：

  • 申请：pi 申请 rj 时，由 pi 向 rj 画一条申请边；若系统满足申请，则将该边改为分配边。
  • 释放：删除分配边。

5.5.2 资源分配图的约简（化简）

约简算法（判断有无死锁）：

  1. 寻找一个非孤立且没有请求边的进程节点 pi。若不存在这样的节点且仍有非孤立节点，算法结束（图中必有环且环上无符合条件的进程）。
  2. 去除 pi 的所有分配边，使其成为孤立节点。
  3. 寻找所有请求边都可满足的进程 pj，将 pj 的所有请求边全部改为分配边（视为可立即满足）。
  4. 转步骤 1。

死锁定理：

  • 若算法结束时所有节点均为孤立节点，则称资源分配图是完全可约简的。
  • 否则称为不可完全约简的。
  • 死锁定理：S 状态为死锁状态的充分必要条件是 S 的资源分配图不可完全约简。

5.5.3 资源分配图典型例子

例 1：无环路，无死锁。

例 2：有环路，有死锁（每类资源只有一个实例时）。

例 3：有环路，无死锁（某类资源有多个实例）：

  • 即使存在环路，环外有空闲实例，环路上的进程仍可能获得资源继续运行，最终环路会消失。
  • 关键判据：约简成功则不死锁，约简失败则死锁。

易错点：有环不等于死锁；只有环上每个资源类只有一个实例时，有环才等价于死锁。

5.6 死锁预防

思想：对进程有关资源的活动加限制，所有进程遵守即可保证不死锁。

  • 优点：简单，系统不需要做什么。
  • 缺点：对进程的约束太强，资源利用率低；若进程违反约束仍可能死锁。

5.6.1 预先分配法

  • 进程：运行前一次性申请所需全部资源。
  • 系统：能全满足则全分配；否则一个也不分配，进程等待。

破坏条件：破坏"hold-and-wait"（保持申请）条件。 缺点：

  • 资源利用效率低（资源被长时间占用）。
  • 进程难以事先知道自己所需全部资源。

5.6.2 有序分配法

  • 给资源集 R = {r1, r2, ..., rn} 定义一个函数 F: R → N（给每个资源类一个唯一编号）。
  • 进程 pi 申请资源 rj 中实例的前提：∀ 占有的资源 rl，F(rl) < F(rj)。
  • 即先申请小编号资源，再申请大编号资源。

无死锁证明（反证法）： 假设死锁，存在环路：

  • t1：p1 等待 rk1（被 p2 占有）
  • t2：p2 等待 rk2（被 p3 占有）
  • …
  • tn：pn 等待 rkn（被 p1 占有）

按有序申请假设：F(rk1) < F(rk2) < ... < F(rkn) < F(rk1) — 矛盾！

优点：与预先分配法相比，资源利用率提高。 缺点：

  • 资源编号困难（人为规定顺序）。
  • 为保持按序申请，某些暂时不用的资源也需提前申请，仍牺牲资源利用率。

5.6.3 死锁预防策略对比

方法 破坏条件 评价
预先分配 保持申请 资源利用率最低，几乎不可用
有序分配 循环等待 实用但需事先定序

5.7 死锁避免——银行家算法（Banker's Algorithm）

5.7.1 基本思想

由 Dijkstra 提出。核心思想：每次资源分配前，模拟分配后是否仍能找到一条安全进程序列，能则分配，不能则拒绝。

5.7.2 安全状态与安全序列

  • 安全状态：存在一个进程序列 ⟨p1, p2, ..., pn⟩，按照此序列分配资源，每个进程都能顺利完成。
  • 不安全状态：不存在这样的安全序列。不安全状态不一定立即死锁，但终将死锁。

5.7.3 银行家算法的数据结构

设 n 个进程 p1..pn，m 类资源 r1..rm：

数据结构 类型 含义
Available array[1..m] of integer 系统当前可用资源数
Claim / Max array[1..n, 1..m] of integer 进程最大需求（事先申明）
Allocation array[1..n, 1..m] of integer 已分配给进程的资源
Need array[1..n, 1..m] of integer 进程还需要的资源 = Claim − Allocation
Request[i] array[1..m] of integer 进程 pi 当前请求

临时变量：

  • Work = Available（安全性算法中模拟可用资源）
  • Finish = array[1..n] of boolean

符号约定：

  • X ≤ Y ⟺ ∀j, X[j] ≤ Y[j]
  • X := Y、 X := c（向量赋值）等按分量进行。

5.7.4 银行家算法（资源分配主流程）

进程 pi 请求资源 Request[i]：

1. 若 Request[i] > Need[i]：报错（超出最大需求）。
2. 若 Request[i] > Available：pi 必须等待。
3. 系统试探分配：
     Available := Available − Request[i]
     Allocation[i] := Allocation[i] + Request[i]
     Need[i] := Need[i] − Request[i]
4. 执行安全性算法：
     若新状态安全 → 真正分配，pi 继续。
     若不安全 → 撤销试探分配，pi 等待。

5.7.5 安全性算法（Safety Algorithm）

输入：Available, Allocation, Need
输出：是否存在安全序列

1. Work := Available
   Finish[i] := false, ∀i

2. 寻找满足下列条件的 i：
     Finish[i] = false  且  Need[i] ≤ Work
   若找不到，转 4。

3. Work := Work + Allocation[i]
   Finish[i] := true
   转 2。

4. 若 ∀i, Finish[i] = true → 安全；
   否则 → 不安全（含死锁可能）。

安全序列的寻找：每轮挑选一个"尚需资源 ≤ 当前可用"的进程，假设它跑完后归还全部资源，再扩大 Work，继续找下一个。

5.7.6 银行家算法完整例题

例题：R = {A(10), B(5), C(7)}，P = {p0, p1, p2, p3, p4}。 初始快照如下：

进程 Claim (A B C) Allocation (A B C) Need (A B C) Available (A B C)
p0 7 5 3 0 1 1 7 4 2 3 3 3
p1 3 2 2 2 0 0 1 2 2
p2 9 0 2 3 0 0 6 0 2
p3 2 2 2 2 1 1 0 1 1
p4 4 3 3 0 0 2 4 3 1

步骤 1：安全性检查（初始状态）

Work = (3,3,3)，Finish = (F,F,F,F,F)

  • p3：Need(0,1,1) ≤ Work(3,3,3) ✓，选 p3。Work := (3,3,3)+(2,1,1)=(5,4,4)，Finish[p3]=T
  • p1：Need(1,2,2) ≤ Work(5,4,4) ✓，选 p1。Work := (5,4,4)+(2,0,0)=(7,4,4)，Finish[p1]=T
  • p4：Need(4,3,1) ≤ Work(7,4,4) ✓，选 p4。Work := (7,4,4)+(0,0,2)=(7,4,6)，Finish[p4]=T
  • p2：Need(6,0,2) ≤ Work(7,4,6) ✓，选 p2。Work := (7,4,6)+(3,0,0)=(10,4,6)，Finish[p2]=T
  • p0：Need(7,4,2) ≤ Work(10,4,6) ✓，选 p0。Work := (10,4,6)+(0,1,1)=(10,5,7)，Finish[p0]=T

安全进程序列：⟨p3, p1, p4, p2, p0⟩，系统安全。

步骤 2：p2 请求 Request[2] = (1, 0, 2)

  1. Request[2] = (1,0,2) ≤ Need[2] = (6,0,2) ✓
  2. Request[2] = (1,0,2) ≤ Available(3,3,3) ✓
  3. 试探分配：
    • Available := (3,3,3)−(1,0,2) = (2,3,1)
    • Allocation[2] := (3,0,0)+(1,0,2) = (4,0,2)
    • Need[2] := (6,0,2)−(1,0,2) = (5,0,0)
  4. 安全性检查：
进程 Need (A B C) Allocation (A B C) Work (A B C) Finish
初始 — — 2 3 1 F,F,F,F,F
p3 0 1 1 2 1 1 2 3 1 ✓ → 4 4 2 T
p1 1 2 2 2 0 0 4 4 2 ✓ → 6 4 2 T
p4 4 3 1 0 0 2 6 4 2 ✓ → 6 4 4 T
p0 7 4 3 0 1 0 6 4 4 ✗ F
p2 5 0 0 4 0 2 6 4 4 ✓ → 10 4 6 T
p0 7 4 3 0 1 0 10 4 6 ✓ → 10 5 6 T

安全进程序列：⟨p3, p1, p4, p2, p0⟩，安全。真正分配给 p2。

步骤 3：p4 请求 Request[4] = (3, 3, 0)

  • Request[4] = (3,3,0) > Available(2,3,1)，不能满足，p4 等待。

步骤 4：p0 请求 Request[0] = (0, 2, 0)

  1. Request[0] = (0,2,0) ≤ Need[0] = (7,4,3) ✓
  2. Request[0] = (0,2,0) ≤ Available(2,3,1) ✓
  3. 试探分配：
    • Available := (2,3,1)−(0,2,0) = (2,1,1)
    • Allocation[0] := (0,1,0)+(0,2,0) = (0,3,0)
    • Need[0] := (7,4,3)−(0,2,0) = (7,2,3)
  4. 安全性检查：
进程 Need (A B C) Allocation (A B C) Work (A B C)
初始 — — 2 1 1
p1 1 2 2 2 0 0 2 1 1 ✗
p3 0 1 1 2 1 1 2 1 1 ✗
p4 4 3 1 0 0 2 2 1 1 ✗
p0 7 2 3 0 3 0 2 1 1 ✗
p2 5 0 0 4 0 2 2 1 1 ✗

找不到可满足的进程，不安全！撤销试探分配，p0 等待。

5.7.7 银行家算法的局限性（保守性）

例：R = {A(1), B(1)}，P = {p1, p2}。p1: a b；p2: b a a b；Available = (1,1)。

  • Allocation 全 0，Need = (1,1)/(1,1)。
  • p1 申请 Request[1] = (1,0)，试探分配后 p1 拿 A。p1 还需 B，可从 Available (0,1) 拿到，p1 完成释放 (1,1)；再给 p2。安全，分配。
  • p2 申请 Request[2] = (0,1)，试探分配后 p2 拿 B。p2 还需 A，但 Available 为 (1,0)，p1 还需 B。可 p1 拿 B 完成释放后给 p2，p2 完成。实际上是安全的，但银行家算法可能因找不到简单路径而误判不安全。

银行家算法是充要条件，但需要"进程给出完整命令序列"才能做到 NP 完全级精确。仅按最大需求判断时是充分不必要的——保守（可能错杀合法分配）。

5.7.8 Remarks（讨论）

  1. 银行家算法基于"进程所需资源最大量"信息，对充要性分析是不够的（如上例保守性问题）。
  2. 若能预先给出进程完整资源命令序列，则可给出死锁避免的充要性算法，但复杂度为 NP 完全。
  3. 预先给出完整命令序列是困难的（程序有分支、循环）。

5.8 死锁的检测

5.8.1 死锁检测的数据结构

数据结构 含义
Available 系统可用资源
Allocation 已分配
Request 进程当前请求
Work（临时） 模拟可用资源
Finish（临时） 进程是否"完成"

5.8.2 死锁检测算法

1. Work := Available
   若 Allocation[i] = 0，则 Finish[i] := true，否则 Finish[i] := false
2. 寻找 i 满足：
     Finish[i] = false  且  Request[i] ≤ Work
   若不存在，转 4。
3. Work := Work + Allocation[i]
   Finish[i] := true
   转 2。
4. 若 ∃i, Finish[i] = false → 死锁；
   否则 → 无死锁。

两个关键备注：

  • 算法可检测到参与死锁的全部进程，包括占有资源和不占有资源的进程。
  • 若只想检测占有资源的进程（因为只有占资源的进程需要恢复），则初始化时改为： 对所有 Allocation[i] = 0 的 i，置 Finish[i] = true（认为空手的进程不会卡死别人）。
  • 设 P 是所有进程集合，P' ⊆ P 是所有占有资源的进程集合，则 P 死锁 ⟺ P' 死锁。因此只检测 P' 可缩小检测范围、降低开销。

5.8.3 死锁检测算法例题

R = {A(7), B(3), C(6)}，P = {p0, p1, p2, p3, p4}

进程 Allocation (A B C) Request (A B C) Available (A B C)
p0 0 1 0 0 0 0 0 1 0
p1 2 0 0 2 0 2
p2 3 0 3 0 0 0
p3 2 1 1 1 0 0
p4 0 0 2 0 0 2

步骤：

  • Work = (0,1,0)；Finish = (F,F,F,F,F)
  • p0：Request(0,0,0) ≤ Work(0,1,0) ✓，Work := (0,1,0)+(0,1,0) = (0,2,0)，Finish[p0]=T
  • p2：Request(0,0,0) ≤ Work(0,2,0) ✓，Work := (0,2,0)+(3,0,3) = (3,2,3)，Finish[p2]=T
  • p1：Request(2,0,2) ≤ Work(3,2,3) ✓，Work := (3,2,3)+(2,0,0) = (5,2,3)，Finish[p1]=T
  • p3：Request(1,0,0) ≤ Work(5,2,3) ✓，Work := (5,2,3)+(2,1,1) = (7,3,4)，Finish[p3]=T
  • p4：Request(0,0,2) ≤ Work(7,3,4) ✓，Work := (7,3,4)+(0,0,2) = (7,3,6)，Finish[p4]=T

所有 Finish = true，未死锁。

若 p2 再请求 Request[2] = (0,0,1)：

进程 Allocation Request
p0 0 1 0 0 0 0
p1 2 0 0 2 0 2
p2 3 0 3 0 0 1
p3 2 1 1 1 0 0
p4 0 0 2 0 0 2
  • Work = (0,1,0)，找满足 Request ≤ Work 的进程：p0（Request 全 0）✓ → Work = (0,2,0)
  • p2 Request(0,0,1) > Work(0,2,0) ✗；p1 ✗；p3 Request(1,0,0) > (0,2,0) ✗；p4 Request(0,0,2) > (0,2,0) ✗
  • 算法终止，p1, p2, p3, p4 的 Finish 仍为 false → 死锁，参与死锁的进程集合 = {p1, p2, p3, p4}。

5.8.4 死锁检测的时机

检测时机 优点 缺点
每次资源等待时检测 发现早，恢复代价小 开销大（频繁）
定时检测（如每小时） 开销可控 死锁到恢复有延迟
CPU 利用率下降时检测 动态适应 阈值难调，可能漏检

5.9 死锁的恢复

检测到死锁后，必须打破循环。三种恢复方法：

  1. 重新启动系统：最简单，代价最大，会影响未参与死锁的进程。
  2. 终止进程（Process Termination）：
    • 终止环路上占有资源的进程。
    • (a) 一次性全部终止；(b) 逐步终止（按优先级、代价函数选择）。
  3. 剥夺资源（Resource Preemption）+ 进程回退（Rollback）：
    • 选定受害者（victim）→ 剥夺其资源。
    • 进程回退到某个安全状态（保存 snapshot）。
    • 问题：保存快照代价大；消除影响困难；可能造成饥饿（starvation）。

5.10 鸵鸟算法（Ostrich Algorithm）

视而不见——假装死锁不会发生。

  • 支持方（工程师）：死锁发生频率 < 其它故障引起系统瘫痪的频率；死锁处理开销 > 死锁危害。
  • 反对方（数学家）：必须处理，无论代价如何。
  • 现实：大多数实际操作系统（如 UNIX、Linux、Windows）采用鸵鸟算法。UNIX 进程数上限 50 多即由此考虑（避免复杂资源分配图）。
  • 结论：是工程权衡的产物，不是"好的"理论方案。

5.11 有关问题的讨论

  1. 充要性算法：已知进程资源活动序列即可给出充要性算法，但困难在于程序有分支与循环，复杂度为 NP 完全。
  2. 生灭资源问题：消耗性资源（如消息、信号）与可重用资源（如打印机、内存）并存时，死锁分析更复杂。
  3. 两阶段封锁（2PL）：数据库领域，增长阶段有可能死锁（仍需检测）。

5.12 饥饿与活锁（Starvation & Livelock）

5.12.1 饥饿定义

饥饿（Starvation）：当等待时间给进程推进和响应带来明显影响时，称发生进程饥饿。饥饿到一定程度，进程即使完成也不再具有实际意义时，称该进程被饿死（starved to death）。

本质：等待时间没有上界（但不是"永远等不到"）。

5.12.2 饥饿与活锁的关系

  • 排队等待（如信号量 P 操作阻塞）→ 不会活锁。
  • 忙式等待（如自旋锁）→ 等待时间没上界 → 可能饿死。
  • 忙式等待条件下发生的饥饿，称为活锁（LiveLock）。

活锁：进程一直在运行（"忙着"），但推进无效。如两进程在走廊相遇，互相礼让 → 反复让路 → 永远过不去。

5.12.3 死锁与饥饿的对比（必考对比表）

维度 死锁（Deadlock） 饥饿/饿死（Starvation）
等待状态 一定处于等待 死锁进程等待，饿死可能忙等（活锁）
等待资源 永远得不到 资源可能被释放，但不会分给自己，等待无上界
循环等待 一定有循环等待 不一定有循环
涉及进程数 至少 2 个 可能只有 1 个
检测 资源分配图化简 通常依赖公平调度策略（FIFO、优先级老化等）
解决方案 预防/避免/检测+恢复 公平调度、优先级老化（Aging）

5.13 死锁的例子——过河问题（Bridge Crossing）

问题描述：一座独木桥，两岸有人要过河。桥同一方向可并行，反方向不行。

死锁可能：东、西两个方向各有 1 人上桥，双方互相等待对方先下桥。

预防方案：同一时刻只允许一个方向通行（互斥）。

  • 用信号量 mutex 保护计数器 east_crossing、west_crossing、east_wait、west_wait、wq、eq。
  • 西面过河者：若 east_crossing > 0，则排队到 wq；否则上桥 west_crossing++；过河完后唤醒东面等待者。

课后思考：给出"无饿死"的解法（提示：用 FIFO 队列严格排队，避免某方向一直插队）。

第二个过河问题（带路径约束）

桥上有 8 段（1-2-3-4-...），W→E 与 E→W 各走特定路径：

  • W→E：1→2→3→4→5→6→...（P(s1)→P(s2)→...）
  • E→W：5→6→7→8→1→2→...（P(s5)→P(s6)→...）
  • 全局信号量 S 初值 5，s1..s8 初值 1。
  • 要求：(1) 无死锁；(2) 无饿死；(3) 并行度高。

通过在每段设置信号量并按路径顺序 P、V，并控制对向并发数 ≤ 5，实现解。

5.14 简单组合资源死锁的静态分析

已知：每个进程关于资源的活动序列（申请、释放顺序）。 判断：有无死锁可能性。

步骤：

  1. 以每个进程"占有资源、申请资源"作为一个状态，记作：(pi : aj : ak1, ..., akn) = (进程 : 请求 : 占有)。
  2. 以每个状态为一个节点。
  3. 若 s1 所申请资源为 s2 所占有，则由 s1 向 s2 画有向弧（相同进程之间不画）。
  4. 找出所有环路。
  5. 判断环路上状态是否能同时到达：
    • 环路中有相同进程 → 不能到达 → 无死锁。
    • 环路中有相同被占有资源 → 不能到达 → 无死锁。

典型例题：R = {A, B, C, D, E, F, G}，三进程：

p1: c d c a b d a b
p2: d e d b f e b f
p3: c e e f a e f a

画出状态图，找到环路后用反证法证明某条环路不可达（线1不可达，反证线1可达则线2可达，又推出矛盾）。

5.15 同种组合资源死锁的必要条件

条件：只有一种资源类，但数量有限。

设：

  • M：该类资源的总数量
  • N：使用该类资源的进程数量
  • Σ：所有进程所需该类资源的总量（每个进程一个最大需求）

定理：当 Σ < M + N 时，一定没有死锁；当 Σ ≥ M + N 时，至少存在某种交叉有死锁可能。

证明思路：假设死锁，n 个进程参与了死锁（2 ≤ n ≤ N）。

  • 参与死锁的进程所需资源总量 ≥ M + n（因为死锁状态下，所有 M 个资源都被持有，且至少多 1 个被循环等待）。
  • 未参与死锁的进程所需资源总量 ≥ N − n（每个未参与的进程至少需要 1 个，因已假设都"可能等"）。
  • 故 Σ ≥ M + n + (N − n) = M + N。

例题：

  • 例 1：M=15, N=4, P1(4)+P2(6)+P3(1)+P4(7) = 18 < M+N = 19 → 无死锁可能。
  • 例 2：M=15, N=4, P1(5)+P2(6)+P3(1)+P4(7) = 19 ≥ M+N = 19 → 有死锁可能。
    • 一种死锁情形：P1 占 5、P2 占 5、P3 占 1、P4 占 4，总共 15 个，全部分光且仍在循环等待。

二、考点总结

考点 1：死锁的定义与四个必要条件（Coffman 条件）

  • 内容：
    1. 互斥使用（Mutual Exclusion）
    2. 不可抢占（Non-preemption）
    3. 保持申请（Hold-and-Wait）
    4. 循环等待（Circular Wait）
    • 四条件同时满足才可能死锁（必要条件）；每类资源单实例时为充要条件。
    • 破坏任一条件即可预防死锁。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. 死锁的四个必要条件是什么？它们之间是什么关系？ 答：见上"内容"；4 个条件同时成立是死锁的必要条件；每类资源仅一个实例时是充要条件。
    2. （选择）破坏哪个条件能预防死锁？ A. 互斥 B. 不可抢占 C. 保持申请 D. 以上均可 答：D（破坏任一条件均可消除死锁）。

考点 2：死锁与饥饿的对比

  • 内容：见 5.12.3 对比表，特别强调：
    • 死锁：等待永远得不到的资源；一定有循环等待；至少 2 个进程。
    • 饥饿：等待可能释放但分不到自己的资源，等待无上界；可能没有循环；可能只涉及 1 个进程。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. （选择）下列关于死锁与饥饿的说法错误的是？ A. 死锁一定涉及循环等待 B. 饥饿可能只涉及一个进程 C. 死锁进程一定处于等待状态 D. 饥饿进程的等待时间一定有上界 答：D（饥饿的关键是"无上界"）。
    2. 简述活锁与死锁的区别。 答：活锁是忙式等待条件下的饥饿，进程"忙着"但无进展；死锁是等待永远不会释放的资源。活锁可在运行，死锁必阻塞。

考点 3：死锁处理的四种策略及鸵鸟算法

  • 内容：预防（静态）、避免（动态，银行家算法）、检测+恢复、鸵鸟算法（忽略）。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. （简答）死锁预防、避免、检测三种策略的优缺点对比。 答：
      • 预防：静态，破坏必要条件，资源利用率低。
      • 避免：动态，运行时检查安全性（如银行家算法），需预知最大需求。
      • 检测+恢复：允许死锁，定期检测，再终止或剥夺，开销低但恢复有代价。
    2. （选择）UNIX 采用哪种死锁处理策略？ 答：鸵鸟算法（Ostrich）。

考点 4：资源分配图与化简

  • 内容：申请边、分配边、约简算法、死锁定理。
  • 考查方式：选择、填空、综合题（画图+判定）。
  • 可能的题目：
    1. （画图+判定）给定进程资源关系，画资源分配图，并判断是否死锁。 答：按规则：申请边从进程指向资源类（虚线），分配边从资源实例指向进程（实线）。化简时反复找"无请求边"的进程，删除其所有分配边。若最终全孤立 → 安全；否则死锁。
    2. （选择）有环路的资源分配图是否一定死锁？ 答：不一定；只有每类资源仅一个实例时，有环才等价于死锁。多实例时可能通过环外资源打破死锁。

考点 5：死锁预防——预先分配法与有序分配法

  • 内容：
    • 预先分配法：一次性申请全部资源 → 破坏"保持申请"。
    • 有序分配法：按资源编号递增申请 → 破坏"循环等待"。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. （选择）有序分配法破坏 Coffman 条件的哪个？ 答：循环等待。
    2. （简答）有序分配法为何能防止死锁？（反证法说明） 答：假设死锁，存在环路 p1→p2→...→pn→p1，按有序申请规则有 F(rk1) < F(rk2) < ... < F(rkn) < F(rk1)，矛盾。

考点 6：银行家算法的数据结构

  • 内容：Available、Claim/Max、Allocation、Need、Request；以及临时变量 Work、Finish。
  • 考查方式：填空、简答。
  • 可能的题目：
    1. （填空）Need[i] = __________ − Allocation[i]。 答：Claim[i]（或 Max[i]）。
    2. （简答）银行家算法的 5 个数据结构和 2 个临时变量名称及含义。 答：见 5.7.3 表格。

考点 7：银行家算法——资源分配主流程（必考大题）

  • 内容：

    1. Request ≤ Need?
    2. Request ≤ Available?
    3. 试探分配。
    4. 安全性检查 → 安全则真正分配；不安全则撤销试探，进程等待。

  • 考查方式：计算大题。

  • 可能的题目（计算）：

    1. 系统有 5 个进程 P0..P4，3 类资源 A(10)、B(5)、C(7)，初始快照如下。P2 请求 (1,0,2)，P4 请求 (3,3,0)，P0 请求 (0,2,0)，分别判断能否分配。
    进程 Max (A B C) Allocation (A B C) Need (A B C) Available (A B C)
    P0 7 5 3 0 1 1 7 4 2 3 3 3
    P1 3 2 2 2 0 0 1 2 2
    P2 9 0 2 3 0 0 6 0 2
    P3 2 2 2 2 1 1 0 1 1
    P4 4 3 3 0 0 2 4 3 1

    解答：

    (a) P2 请求 (1,0,2)：

    • Request(1,0,2) ≤ Need(6,0,2) ✓
    • Request(1,0,2) ≤ Available(3,3,3) ✓
    • 试探分配后 Available=(2,3,1), Allocation[P2]=(4,0,2), Need[P2]=(5,0,0)
    • 安全性检查：⟨P3, P1, P4, P2, P0⟩ 是安全序列 → 安全，真正分配。

    (b) P4 请求 (3,3,0)：

    • Request(3,3,0) > Available(2,3,1) → 不满足，P4 等待。

    (c) P0 请求 (0,2,0)（此时 Available 已是 (2,3,1)）：

    • Request(0,2,0) ≤ Need(7,4,3) ✓
    • Request(0,2,0) ≤ Available(2,3,1) ✓
    • 试探分配后 Available=(2,1,1), Allocation[P0]=(0,3,0), Need[P0]=(7,2,3)
    • 安全性检查：无可满足进程（P1 需 (1,2,2) > (2,1,1) 等） → 不安全，撤销分配，P0 等待。

考点 8：安全性算法（必考大题）

  • 内容：见 5.7.5，五个步骤。
  • 考查方式：计算大题（每年必考）。
  • 可能的题目：见考点 7。

考点 9：银行家算法的保守性

  • 内容：基于"最大需求"判断是充分不必要的，可能拒绝本可分配的资源。
  • 考查方式：选择、简答。
  • 可能的题目：
    1. （简答）简述银行家算法的局限性。 答：(1) 要求进程预知最大需求，实际困难；(2) 进程数量与资源类别增加时代价大；(3) 基于最大需求判断，对实际安全序列可能"误判不安全"，具有保守性；(4) 程序有分支循环，无法预知完整序列，精确算法为 NP 完全。

考点 10：死锁检测算法

  • 内容：与银行家算法的安全性算法类似，但用 Request 替代 Need。

  • 考查方式：计算大题。

  • 可能的题目：

    系统 R = {A(7), B(3), C(6)}，P = {p0, p1, p2, p3, p4}。当前快照：

    进程 Allocation (A B C) Request (A B C) Available (A B C)
    p0 0 1 0 0 0 0 0 1 0
    p1 2 0 0 2 0 2
    p2 3 0 3 0 0 0
    p3 2 1 1 1 0 0
    p4 0 0 2 0 0 2

    此时 p2 又请求 (0,0,1)，请用死锁检测算法判断系统是否死锁，并列出参与死锁的进程。

    解答：

    • 新 Request 矩阵：p2 改为 (0,0,1)。
    • Work = (0,1,0)，Finish 初始化：p0 Allocation≠0 → F；p2 Allocation≠0 → F；p1, p3, p4 同理 F。
    • 选 p0：Request(0,0,0) ≤ (0,1,0) ✓ → Work = (0,1,0)+(0,1,0) = (0,2,0)，Finish[p0]=T
    • 检查剩余：p1 需 (2,0,2) > (0,2,0) ✗；p2 需 (0,0,1) > (0,2,0) ✗；p3 需 (1,0,0) > (0,2,0) ✗；p4 需 (0,0,2) > (0,2,0) ✗
    • 算法终止，p1, p2, p3, p4 的 Finish 仍为 false → 系统死锁，参与死锁进程集合 = {p1, p2, p3, p4}。

考点 11：死锁检测时机与恢复方法

  • 内容：三种检测时机（等待时、定时、CPU 利用率下降）；三种恢复方法（重启、终止、剥夺）。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. （选择）死锁恢复的代价从小到大排列？ 答：剥夺部分资源 < 终止部分进程 < 重启系统。
    2. （填空）剥夺资源 + 进程回退方案的最大问题是 ________ 和 ________。 答：保存 snapshot 代价大；可能造成 starvation（饥饿）。

考点 12：鸵鸟算法（Ostrich Algorithm）

  • 内容：忽略死锁，工程权衡，实际系统常用。
  • 考查方式：选择、简答。
  • 可能的题目：
    1. （选择）UNIX、Linux、Windows 采用哪种死锁处理策略？ 答：鸵鸟算法。
    2. （简答）为何实际系统多用鸵鸟算法？ 答：死锁发生频率极低，处理开销（检测+恢复）反而更大；从工程角度"忽略"是最优选择。

考点 13：组合资源死锁的静态分析

  • 内容：画状态转移图、找环路、判断环路是否可达（相同进程或相同占有资源 → 不可达）。

  • 考查方式：综合题。

  • 可能的题目：

    R = {A,B,C,D,E,F,G}，三进程活动序列如下。判断有无死锁可能。

    p1: c d c a b d a b
p2: d e d b f e b f
p3: c e e f a e f a

    思路：以"进程：请求：占有"为节点画有向图，找环路 → 用反证法证明环路不可达（线1不可达；反设线1可达，则线2可达，进而 p2 先于 p1、p3 先于 p2、p1 先于 p3，矛盾）。结论：无死锁可能性。

考点 14：同种资源死锁的充要条件（Σ vs M+N）

  • 内容：M 资源数、N 进程数、Σ 总需求。
    • Σ < M + N → 一定无死锁。
    • Σ ≥ M + N → 至少存在某种交叉有死锁可能。
  • 考查方式：计算题、判断题。
  • 可能的题目：
    1. M=6, N=3, P1(3)+P2(2)+P3(4)=9, 是否可能死锁？ 答：M+N = 9, Σ = 9 ≥ 9 → 可能死锁（存在如 P1 占 3、P2 占 2、P3 占 1 并循环等待等死锁情形）。
    2. M=6, N=3, P1(2)+P2(2)+P3(3)=7 < 9 → 一定无死锁。

考点 15：死锁类型（同种/异种资源、通讯死锁、活锁）

  • 内容：
    • 不同类资源死锁（最常见）：两进程互持对方所需资源。
    • 同类资源死锁：资源数不够用且请求总和超量。
    • 通讯死锁：进程互等消息。
    • 活锁："After you / After you"，忙等无进展。
  • 考查方式：选择、填空。
  • 可能的题目：
    1. （选择）4 台打印机，P1 申请 8 次、P2 申请 4 次，是否会死锁？ 答：当 P1 占 3、P2 占 1 时，P1 还需 5、P2 还需 3，总需 8 > 4，可死锁。

考点 16：过河问题（综合应用题）

  • 内容：使用信号量 mutex + wq/eq 实现"同方向可并发，反方向必须互斥"。要求：无死锁、无饿死、并行度高。
  • 考查方式：综合应用题（写出信号量初值、P/V 操作）。
  • 可能的题目：
    1. 写出"无死锁、无饿死"的过河问题完整解法（含信号量定义和 P/V 序列）。 答要点：
      • 全局信号量 S（限制总桥上人数）、分段信号量 s1..s8（控制每段互斥）。
      • 西→东：P(S); P(s1); …; P(s4); 走过; V(s4); …; V(s1); V(S);
      • 东→西：P(S); P(s5); …; P(s8); 走过; V(s8); …; V(s5); V(S);
      • 通过 FIFO 队列与计数变量保证无饿死（见 PPT 5.13 的代码）。

考点 17：死锁定理（资源分配图约简）

  • 内容：S 是死锁状态 ⟺ 资源分配图不可完全约简。
  • 考查方式：选择、简答。
  • 可能的题目：
    1. （简答）叙述死锁定理及其证明思路。 答：资源分配图可完全约简 ⟺ 无死锁。证明思路：若可完全约简，可按约简顺序找到安全序列；反之若无死锁，必有进程可推进并最终释放资源，对应化简步骤，故可完全约简。逆否：不可完全约简 → 死锁。

考点 18：饥饿的解决方案

  • 内容：公平调度、优先级老化（Aging）、FIFO 队列。
  • 考查方式：简答。
  • 可能的题目：
    1. （简答）饥饿有哪些常见解决方案？ 答：
      • 公平调度（FIFO、先来先服务）。
      • 优先级老化（等待越久优先级越高）。
      • 多队列反馈调度。
      • 避免选同一进程作为剥夺受害者（防饥饿）。

考点 19：死锁检测的初始化差异（重要细节）

  • 内容：两种初始化方式：
    • 默认：所有 Finish=false，按 Request ≤ Work 找。
    • 改进：对 Allocation[i]=0 的进程直接 Finish[i]=true（空手的进程不会卡别人）。
    • 后者只检测占有资源的进程 P'，不影响结论（P 死锁 ⟺ P' 死锁）。
  • 考查方式：选择、填空。
  • 可能的题目：
    1. （填空）死锁检测算法中，为减少开销，对 Allocation[i]=0 的进程应设 Finish[i] = ________。 答：true。

考点 20：死锁 vs 活锁 vs 饥饿（三概念辨析）

  • 内容：
    • 死锁：阻塞等待 + 永远得不到。
    • 活锁：忙式等待 + 看似在跑但实际无进展（如两进程互相让路）。
    • 饥饿：等待时间无上界但未必死锁（资源可能被释放但分不到）。
  • 考查方式：选择、填空、简答。
  • 可能的题目：
    1. （选择）两进程在独木桥两端互相礼让、谁也过不去，属于？ A. 死锁 B. 活锁 C. 饥饿 D. 正常调度 答：B（活锁）。
    2. （简答）举例说明死锁、活锁、饥饿的典型场景。 答：
      • 死锁：A 占 R1 等 R2，B 占 R2 等 R1。
      • 活锁：两进程在走廊相遇互相让路，重复让路→永远过不去。
      • 饥饿：低优先级进程长期得不到 CPU（虽然 CPU 空闲着）。

本章复习建议：

  1. 必背：Coffman 4 条件、银行家算法的 5 数据结构 + 2 临时变量、安全性算法流程、死锁定理。
  2. 必练：每年至少做 3 道银行家算法计算题（含初始安全性检查 + 多个请求处理）。
  3. 必理解：资源分配图化简、死锁检测算法（与安全性算法对比）。
  4. 必对比：死锁 vs 饥饿 vs 活锁；预防 vs 避免 vs 检测 vs 恢复。
  5. 必记：Σ < M+N → 一定无死锁；Σ ≥ M+N → 可能死锁。
Reference in New Issue View Git Blame Copy Permalink