---
title: "05-死锁：僵局的形成与化解"
aliases:
  - 死锁
created: 2026-08-29
tags:
  - 基础与理论
  - 操作系统
  - "408"
---

# 死锁：僵局的形成与化解

> 本篇对应王道第二章收尾（原 11 篇）。上一章管好了同步互斥，这一章处理极端情况：**多个进程互相等待，谁也动不了**。

## 一、死锁是什么

**定义**：多个进程因竞争资源而造成的一种**僵局**（相互等待），若无外力作用，这些进程都将无法向前推进。

**独木桥比喻**：河上一座窄桥，一次只能过一辆车。左右两端各驶上一辆车——左边车占着左半段，要等右边车让出右半段；右边车占着右半段，要等左边车让出左半段。双方都只肯向前，谁也过不去。

计算机里的对应版本：系统只有一台打印机和一台输入设备。P1 占着输入设备，又要申请打印机；打印机正被 P2 占着，而 P2 在释放打印机之前又申请输入设备。两个进程无休止地互相等待，都执行不下去了。

### 死锁产生的原因

1. **系统资源的竞争**：不可剥夺资源数量不足以满足多个进程需要，争夺陷入僵局（磁带机、打印机等）。**只有对不可剥夺资源的竞争才可能死锁**——可剥夺资源（CPU、内存）抢了也就是被抢走，不会等
2. **进程推进顺序非法**：请求和释放资源的顺序不当。P1、P2 分别持有 R1、R2，又互相申请对方的——经典交叉
3. **信号量使用不当**：进程 A 等 B 的消息，B 又等 A 的消息——不是竞争同一资源，而是在等对方，一样死锁

## 二、四个必要条件

产生死锁必须**同时满足**以下四条；任意一条不成立，死锁就不会发生。

| 条件 | 含义 |
| --- | --- |
| **互斥** | 资源排他性使用，一段时间内某资源仅一个进程占有，别人请求只能等 |
| **不剥夺** | 资源未用完之前**不能被强行夺走**，只能由占有者主动释放 |
| **请求并保持** | 已保持至少一个资源，又提出新请求被阻塞时，**对已有资源保持不放** |
| **循环等待** | 存在循环等待链：P1 等 P2 的资源，P2 等 P3 的……Pn 等 P1 的 |

![[image-95a49746.png]]

![[image-56f61f03.png]]

**苹果例子区分两对概念**：

- 你手里拿着一个苹果，即使你不打算吃，别人也不能从你手上拿走——这是**不剥夺**（别人不能抢）
- 你左手拿着一个苹果，**允许**你右手再去拿另一个苹果——这是**请求并保持**（自己不放手）

### 循环等待 ≠ 死锁（高频辨析）

循环等待看起来和死锁定义一样，其实**死锁要求的条件更严**：它要求 Pi 等待的资源**必须**由 Pi+1 满足，循环等待没有这个限制。

反例：系统两台输出设备，P0 占一台，Pk 占一台（**Pk 不在等待环里**），Pn 也占一台。Pn 等一台输出设备，可以从 P0 获得，也可能从 Pk 获得。虽然 Pn、P0 等形成了循环等待，但 **Pk 释放一台设备就能打破循环**——没死锁。

所以：**资源分配图含圈而系统不一定死锁**，原因是同类资源数大于 1；若**每类资源只有一个**，含圈才是死锁的充分必要条件。

## 三、三种处理策略

| 策略 | 思路 | 特点 |
| --- | --- | --- |
| **死锁预防** | 设置限制条件，**破坏 4 个必要条件之一或几个** | 限制严、实现简单，但效率低、资源利用率低 |
| **死锁避免** | 动态分配过程中**防止系统进入不安全状态** | 限制宽松、性能好，但要跑算法判断，实现复杂 |
| **检测和解除** | 不加限制，允许死锁发生，**检测到再解除** | 无事前开销，事后补救 |

![[66792fe75c8dcc9a9893c700e00f859c_720-b358f30a.png]]

## 四、死锁预防：逐个破坏必要条件

### 破坏互斥条件

把资源改成可共享就不会死锁——但有些资源天生不能共享（打印机只能互斥使用，其实用 SPOOLing 虚拟化可以实现共享），且有的场合**应该保护互斥性**。**不太可行**。

### 破坏不剥夺条件

进程请求新资源得不到满足时，**必须释放已保持的全部资源**，以后再重新申请。已占有的资源被暂时剥夺。

实现复杂，**释放已获得的资源可能导致前一阶段工作失效**，反复申请释放也增加开销、降低吞吐量。适用于**状态易保存恢复**的资源（CPU 寄存器、内存），不能用于打印机——第一行打印了文档 A、第二行打印文档 B……全乱了。

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

**预先静态分配**：运行前一次性申请完所有资源，不满足就不投入运行；一旦运行，资源全归它，不再提新请求。

实现简单，缺点明显：资源被**严重浪费**（有的资源只在运行初期或快结束时用，甚至不用，却一直被占着）；还会**饥饿**（个别资源长期被占，等待它的进程迟迟不能开始）；而且有些资源是**运行中才发现要用的**，事先根本不知道。

### 破坏循环等待条件

**顺序资源分配法**：给所有资源编号，进程必须**按编号递增**的顺序请求（同类一次申请完）。申请了 Ri 以后就只能申请编号大于 Ri 的——环画不出来了。

问题：编号必须相对稳定，**限制新设备的增加**；作业实际使用顺序可能与规定顺序不同，造成浪费；给编程带来麻烦。

## 五、死锁避免：安全状态与银行家算法

不事先破坏条件，而是**每次分配前算一笔账**：这次分配会不会让系统进入不安全状态？会就不给，让进程等。

### 安全状态

> 系统能按某种进程推进顺序，为每个进程分配所需资源直到满足其最大需求，使每个进程都可顺序完成——这个顺序就是**安全序列**。找不到安全序列 = **不安全状态**。

**磁带机例子**：三个进程 P1、P2、P3，共 12 台磁带机。P1 总共需要 10 台，P2 需要 4 台，P3 需要 9 台。T0 时刻 P1、P2、P3 已分别获得 5、2、2 台，剩 3 台空闲。

![[image-ecb51590.png]]

T0 是**安全**的，安全序列 P2 → P1 → P3：3 台全给 P2（满足最大需求 4），P2 完成归还后系统有 5 台；再给 P1 凑满 10，P1 完成归还后剩 10 台；最后给 P3 凑 9 台，全部顺利完成。

若此刻多分 1 台给 P3，系统剩 2 台——**不安全**了：剩下 2 台给 P2，P2 完成只能释放 4 台，既不满足 P1（还差 5）也不满足 P3（还差 7），全都推进不了，僵住。

**关键结论**：

- 并非所有不安全状态都是死锁状态，但不安全状态**可能**导致死锁
- 反过来，**处于安全状态就一定不会死锁**

### 银行家算法

最著名的死锁避免算法。思想：**把 OS 当银行家**，资源当资金，进程申请资源相当于贷款。规则：进程运行前先声明**最大需求量**；执行中再申请时，先测试"已占有 + 本次申请"是否超过声明值（超过 → 拒绝），再测试系统现存资源能否满足它尚需的最大量（能 → 分配；不能 → 推迟）。

**四个数据结构**（n 个进程、m 类资源）：

| 结构 | 含义 |
| --- | --- |
| **Available** | 当前可用资源向量 |
| **Max** | 各进程对各类资源的最大需求（n×m 矩阵） |
| **Allocation** | 已分配给各进程的资源（n×m 矩阵） |
| **Need** | 尚需资源：**Need = Max − Allocation** |

**流程**：进程请求 → 超过 Need 或超过 Available？拒绝 → 否则**试探分配**（Available 减、Allocation 加、Need 减）→ 跑**安全性算法** → 安全则正式分配，不安全则**撤回试探分配**让进程等待。

**安全性算法**：

1. Work = Available；Finish[i] = false
2. 找一个 Finish[i]=false 且 **Need[i] ≤ Work** 的进程
3. 假定它执行完并释放资源：Work += Allocation[i]，Finish[i] = true
4. 重复 2-3，直到找不到这样的进程
5. 所有 Finish 都为 true → 安全

例子图：

![[59281c08c3b1ddbf8e29109451b027ee-bd3a6bbc.png]]

![[239379948328590d6d8e6e34f84b1ade_720-8233901c.png]]

银行家算法举例：

![[522c5e570a11c4c086a54bf1d8d3346c-3dc65e05.png]]

![[9ec4ba1ca4181b77cbbd5145412cbf89_720-23fa054a.png]]

自己实现的 C 版（经典五进程三资源数据）：

```c
#include <stdio.h>
#include <stdbool.h>

#define P 5  // 进程数量
#define R 3  // 资源种类数量

// 计算需求矩阵 Need = Max - Allocation
void calculateNeed(int need[P][R], int max[P][R], int allot[P][R]) {
    for (int i = 0; i < P; i++)
        for (int j = 0; j < R; j++)
            need[i][j] = max[i][j] - allot[i][j];
}

// 检查系统是否安全
bool checkSystemSafety(int processes[], int avail[], int max[][R], int allot[][R]) {
    int work[R];
    for (int i = 0; i < R; i++) work[i] = avail[i];
    bool finish[P] = {false};

    while (true) {
        bool found = false;
        for (int i = 0; i < P; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < R; j++)
                    if (need[i][j] > work[j]) break;
                if (j == R) {                       // Need[i] <= Work
                    for (int k = 0; k < R; k++)
                        work[k] += allot[i][k];     // 假定执行完，回收资源
                    finish[i] = true;
                    found = true;
                }
            }
        }
        if (!found) break;
    }

    for (int i = 0; i < P; i++)
        if (!finish[i]) return false;
    return true;
}

int main() {
    int avail[] = {3, 3, 2};
    int max[P][R] = {
        {7, 5, 3}, {3, 2, 2}, {9, 0, 2}, {2, 2, 2}, {4, 3, 3}
    };
    int allot[P][R] = {
        {0, 1, 0}, {2, 0, 0}, {3, 0, 2}, {2, 1, 1}, {0, 0, 2}
    };
    int need[P][R];
    calculateNeed(need, max, allot);
    if (checkSystemSafety(NULL, avail, max, allot))
        printf("The system is currently in a safe state.\n");
    else
        printf("The system is not safe.\n");
    return 0;
}
```

## 六、死锁检测和解除

前面两招都是事前限制；若系统分配资源时不采取任何措施，就得提供**事后检测和解除**手段。

### 资源分配图

圆圈 = 进程，方框 = 一类资源（框内圆点 = 该类资源中的一个实例）。

- **请求边**：进程 → 资源，表示申请一个单位
- **分配边**：资源 → 进程，表示已分配一个单位

![[image-fdc97f2b.png]]

图中：P1 已分得两个 R1，又请求一个 R2；P2 分得一个 R1 和一个 R2，又请求一个 R1。

### 死锁定理：图简化

**简化资源分配图可以检测系统 S 是否处于死锁状态**：

1. 找出**既不阻塞又不孤立**的进程 Pi——与它相连的所有请求边，申请数量都 ≤ 系统中该资源的空闲数量，则它能运行到完成，**消去它的所有边**（释放全部资源）
2. Pi 释放的资源可能唤醒原本阻塞的进程，继续按同样方法简化
3. 一系列简化后**能消去图中所有边** → 图**可完全简化**，无死锁

![[824bee7e28d54e00b8f3b6c7263c2651_720-4dcad077.png]]

> 💡 判断某资源有没有空闲：**资源总数 − 该资源在图中的出度**。比如 R1 资源数 3、出度 3 → 没空闲；R2 资源数 2、出度 1 → 有 1 个空闲。

**死锁定理**：S 为死锁状态 **当且仅当 S 状态的资源分配图是不可完全简化的**。

### 死锁解除

检测出死锁后，三种解除办法：

1. **资源剥夺法**：挂起某些死锁进程，抢占它的资源分给别的死锁进程。要防止被挂起的进程长期得不到资源而**饥饿**
2. **撤销进程法**（终止进程法）：强制撤销部分甚至全部死锁进程并剥夺资源。撤销原则：按进程**优先级**和**撤销代价**高低
3. **进程回退法**：让一个（或多个）进程回退到足以回避死锁的地步，回退时**自愿**释放资源而非被剥夺。代价：系统必须保持进程的历史信息、设置**还原点**

## 七、盲点总复习

1. 只有**不可剥夺资源**的竞争才可能死锁；CPU、内存这类可剥夺资源不会
2. 信号量也能造成死锁：互相等对方的消息
3. 四条件是**必要**条件，缺一不可；破坏任意一个即可预防
4. 不剥夺（别人不能抢）vs 请求并保持（自己不肯放）——苹果例子
5. 循环等待 ≠ 死锁：同类资源 >1 时含圈不一定死；每类资源只有 1 个时含圈才是充要条件
6. 安全状态 ⇒ 不会死锁；死锁 ⇒ 不安全；不安全 ⇏ 死锁（只是**可能**）
7. 银行家算法四矩阵，核心：Need = Max − Allocation；试探分配 + 安全性检查 + 不安全就撤回
8. 图简化判断空闲资源 = 总数 − 出度
9. 死锁定理：不可完全简化 ⇔ 死锁
10. 解除三法：剥夺、撤销、回退——回退是自愿释放，撤销是被剥夺

## 思维导图源件

- [[2.4死锁.xmind|2.4死锁.xmind]]（XMind 源文件，可用 XMind 打开继续编辑）


---

内存是另一座大头：装不下怎么办？下一章讲内存管理 → [[06-内存管理]]

⬅️ 🏠 [[00-操作系统总览]] ➡️ [[06-内存管理]]