Operating-System/Exam/05第五章 死锁与饥饿.md

# 第五章 死锁与饥饿

## 一、知识讲解

本章是操作系统的**核心重点章节**，每年必考**大题**（银行家算法、安全性算法、资源分配图）。死锁（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 → 可能死锁。