# 2.7 死锁

## 一、死锁的概念

### 1.1 什么是死锁

**死锁（Deadlock）**：一组进程中，每个进程都持有至少一个资源，并等待另一个被其他进程持有的资源，导致所有进程都无法继续执行。

### 1.2 死锁的例子

**例子1：哲学家进餐问题**
- 五个哲学家同时拿起左边筷子
- 都在等待右边筷子
- 形成死锁

**例子2：资源申请**
- 进程P1持有资源R1，申请资源R2
- 进程P2持有资源R2，申请资源R1
- 互相等待，形成死锁

### 1.3 死锁产生的原因

1. **竞争资源**：多个进程竞争有限的资源
2. **进程推进顺序非法**：进程请求和释放资源的顺序不当

---

## 二、死锁产生的必要条件

死锁产生必须同时满足以下四个条件：

### 2.1 互斥条件（Mutual Exclusion）

**定义**：资源一次只能被一个进程占用。

**说明**：
- 资源具有排他性
- 如果资源可以被共享，就不会产生死锁

### 2.2 请求和保持条件（Hold and Wait）

**定义**：进程已经持有了至少一个资源，但又提出了新的资源请求。

**说明**：
- 进程持有资源的同时等待其他资源
- 如果进程一次性申请所有资源，就不会产生死锁

### 2.3 不可剥夺条件（No Preemption）

**定义**：进程持有的资源在未使用完之前不能被剥夺。

**说明**：
- 资源只能由持有进程自愿释放
- 如果资源可以被强制剥夺，就不会产生死锁

### 2.4 循环等待条件（Circular Wait）

**定义**：存在一个进程等待链，链中的每个进程都在等待下一个进程持有的资源。

**说明**：
- 形成循环等待链
- 这是死锁的充分条件（前三个是必要条件）

**四个条件的关系**：
- 互斥、请求保持、不可剥夺是必要条件
- 循环等待是充分条件
- 四个条件同时满足时，死锁必然发生

---

## 三、死锁的处理策略

### 3.1 预防死锁

**思想**：破坏死锁产生的四个必要条件之一。

#### 破坏互斥条件

**方法**：使资源可以共享。

**缺点**：
- 很多资源无法共享（如打印机）
- 不现实

#### 破坏请求和保持条件

**方法**：要求进程一次性申请所有需要的资源。

**优点**：简单有效
**缺点**：
- 资源利用率低
- 进程可能长时间等待
- 需要预先知道所有需要的资源

#### 破坏不可剥夺条件

**方法**：允许资源被强制剥夺。

**实现**：
- 当进程申请新资源失败时，释放已持有的资源
- 或者允许系统剥夺某些进程的资源

**缺点**：
- 实现复杂
- 不适用于某些资源（如打印机）

#### 破坏循环等待条件

**方法**：对资源进行编号，要求进程按编号顺序申请资源。

**实现**：
- 给每个资源分配唯一的编号
- 进程只能按编号递增的顺序申请资源

**优点**：
- 实现简单
- 不需要预先知道所有资源

**缺点**：
- 资源编号困难
- 可能增加资源等待时间

### 3.2 避免死锁

**思想**：在资源分配时，判断是否会导致死锁，如果会则不分配。

#### 安全状态

**定义**：系统能按某种顺序为每个进程分配资源，直到满足每个进程的最大需求，使每个进程都能顺利完成。

**安全序列**：使系统处于安全状态的进程执行顺序。

#### 银行家算法

**思想**：借鉴银行家放贷的策略，确保系统始终处于安全状态。

**数据结构**：
- Available：可用资源向量
- Max：最大需求矩阵
- Allocation：已分配矩阵
- Need：需求矩阵，Need = Max - Allocation

**算法步骤**：
1. 当进程申请资源时，检查申请是否小于等于Need
2. 检查申请是否小于等于Available
3. 试分配资源，更新数据结构
4. 检查系统是否处于安全状态
5. 如果是安全状态，正式分配；否则，拒绝分配

**安全性算法**：
1. 初始化Work = Available，Finish = false
2. 寻找进程Pi，满足Finish[i] = false且Need[i] ≤ Work
3. 如果找到，Work = Work + Allocation[i]，Finish[i] = true，重复步骤2
4. 如果所有进程的Finish都为true，系统处于安全状态

### 3.3 检测死锁

**思想**：允许死锁发生，但定期检测死锁，一旦发现就解除。

#### 资源分配图

**定义**：描述进程和资源分配情况的有向图。

**图的组成**：
- 进程节点（圆形）
- 资源节点（方形，其中的圆点表示资源实例）
- 请求边：进程 → 资源
- 分配边：资源 → 进程

**死锁检测**：
- 如果图中存在环路，可能存在死锁
- 每种资源只有一个实例时，环路就是死锁
- 每种资源有多个实例时，环路不一定是死锁

#### 死锁检测算法

**数据结构**：
- Available：可用资源向量
- Allocation：已分配矩阵
- Request：请求矩阵

**算法**：
1. 初始化Work = Available，Finish = false（如果Allocation[i] ≠ 0）或true（如果Allocation[i] = 0）
2. 寻找进程Pi，满足Finish[i] = false且Request[i] ≤ Work
3. 如果找到，Work = Work + Allocation[i]，Finish[i] = true，重复步骤2
4. 如果存在Finish[i] = false的进程，系统处于死锁状态

### 3.4 解除死锁

**方法**：

#### 剥夺资源

**方法**：从其他进程剥夺资源给死锁进程。

**考虑因素**：
- 选择哪个进程剥夺（优先级、已执行时间、剩余执行时间）
- 剥夺哪些资源
- 如何保存和恢复进程状态

#### 撤销进程

**方法**：撤销死锁进程，释放资源。

**策略**：
- 撤销全部死锁进程
- 逐个撤销，直到死锁解除

**选择标准**：
- 进程优先级
- 进程已执行时间
- 进程剩余执行时间
- 进程持有的资源数量

#### 进程回退

**方法**：让进程回退到某个安全状态。

**要求**：
- 系统保存进程的历史信息
- 可以回退到检查点

---

## 四、死锁与饥饿、死循环的区别

| 特性 | 死锁 | 饥饿 | 死循环 |
|-----|------|------|--------|
| 进程状态 | 阻塞 | 阻塞或就绪 | 运行 |
| 资源占用 | 占有资源 | 不占有资源 | 不占有资源 |
| 产生原因 | 循环等待 | 调度策略不公平 | 代码逻辑错误 |
| 解决方法 | 预防、避免、检测解除 | 公平调度 | 修改代码 |

---

## 五、考研重点

1. **死锁的定义**：一组进程互相等待
2. **死锁产生的四个必要条件**：互斥、请求保持、不可剥夺、循环等待
3. **死锁的处理策略**：预防、避免、检测、解除
4. **预防死锁的方法**：破坏四个条件
5. **银行家算法**：安全状态、安全序列、算法步骤
6. **资源分配图**：检测死锁
7. **死锁解除的方法**：剥夺资源、撤销进程
8. **死锁与饥饿的区别**

---

*第二章完，进入第三章：处理机调度*