（四）死锁

1. 死锁的基本概念

1.1. 死锁的定义

• 在一组进程发生死锁的情况下，每一个进程都在等待另一个死锁进程所占有的资源；

• 如果每一个进程都在等待仅由该组进程中其他进程才能引发的事件，那么发生死锁；

1.2. 死锁发生的必要条件

• 产生死锁必须同时具备以下四个条件：

  • 1）互斥：对资源的访问和操作是互斥的；

  • 2）请求和保持：在进程已经占有部分资源的同时，请求其他资源；

  • 3）不可抢占：不允许资源的抢占式访问；

  • 4）循环等待：进程之间互相的等待关系构成环路；

1.3. 死锁发生的原因

• 竞争不可抢占式资源：OS 中某类不可抢占的资源数量不足，不能满足多进程的需要，引发竞争；

• 竞争可消耗资源：例如生产者产生的消息；

  • 情景：三个进程 $P_1,P_2,P_3$，$P_1$ 给 $P_2$ 发送消息，并从 $P_3$ 接收消息，$P_2$ 发给 $P_3$ 并从 $P_1$ 接收，$P_3$ 同理。若 3 个进程同时开始等待接收消息，然后才能发送消息，则会陷入死锁；

• 进程推进顺序不当：主要是指对资源的申请和释放顺序是否合法；

  • 例：有两个进程 $P_1,P_2$，两个资源 $R_1,R_2$。两个进程分别要执行 4 个操作，$P_1$ 的为：申请 $R_1$，申请 $R_2$，释放 $R_1$，释放 $R_2$；$P_1$ 的为：申请 $R_2$，申请 $R_1$，释放 $R_2$，释放 $R_1$；

  • 分析：

    • 若完全按照顺序执行，先 $P_1$ 再 $P_2$ 或反之，则不会发生死锁；

    • 若在 $P_1$ 或 $P_2$ 的两次申请之间发生了另一进程的申请，则一定会发生死锁；

    • 图示

      

      • 横坐标为 $P_1$ 执行顺序，纵坐标为 $P_2$ 的；

      • 阴影区域 D 为不安全状态，会发生死锁；

      • 图中的实线按照左下到右上为执行顺序；

2. 死锁的预防

• 通过破坏四个必要条件中的一个或几个，以避免发生死锁；

  • 因为大多数 IO 设备必须具有互斥属性，无法更改，因此通常是破坏后面几个条件；

2.1. 破坏 “请求与保持” 条件

• 即：规定进程在请求不可抢占式资源时，不能同时持有不可抢占资源；

• 实现：两个协议：

  • 协议 1：一次性申请

    • 规定：进程开始运行前，必须一次性申请其运行过程中所需的全部资源；

    • 缺点：资源浪费，产生饥饿；

  • 协议 2：改进协议 1

    • 允许进程获取运行初期所需资源后就开始运行；

2.2. 破坏 “不可抢占” 条件

• 规定：当一个已持有某些不可抢占资源的进程提出的申请不能得到满足时，它必须释放已经持有的资源，重新申请；

• 缺点：实现复杂，代价较高；

2.3. 破坏 “循环等待” 条件

• 规定：对 OS 管理的资源编号，并规定所有进程必须按照编号递增的顺序申请资源；

• 缺点：对资源编号的管理和新加入的资源处理较为麻烦；

3. 死锁的避免

• 区分：死锁的 “预防” 是采取限制策略，破坏死锁产生的条件；死锁的 “避免” 是在 OS 分配资源过程中，为防止系统进入 “不安全状态” 而加以较弱的限制条件，可获得更好的系统性能；

3.1. 系统的 “安全状态”

• 系统处于 “安全状态” 时，不会发生死锁；处于“不安全状态” 时，可能发生死锁；

• 定义：指 OS 能按某个顺序 $P_1,P_2,\cdots ,P_n$ 来为每个进程 $P_i$ 分配资源，满足每个进程对资源的最大需求，使每个进程都能顺利完成。称此序列为安全序列；

• 例：OS 中有 3 个进程 $P_1,P_2,P_3$ 和 12 个共享资源。$P_1,P_2,P_3$分别需要$10,4,9$ 个资源。在某个时刻 $T_0$，$P_1,P_2,P_3$ 已经得到了 $5,2,2$ 个资源，还剩 3 个资源。

• 分析：在此情况下，3 个进程分别还需 $5,2,7$ 个资源，则首先应分配给 $P_2$，$P_2$ 结束后剩余 5 个，再分给 $P_1$，最后给 $P_3$。所以一个安全的序列就是 $(P_2,P_1,P_3)$；

• 分析 2：若在 $T_0$ 时刻，$P_3$ 抢先申请 1 个资源并得到分配，则 3 个进程分别得到 $5,2,3$ 个资源，还剩 2 个资源，此时无论如何分配都无法满足 3 个进程的需要，系统进入不安全状态，可能发生死锁；

3.2. 银行家算法（by Dijkstra）

• 数据结构：设置 4 个数据结构，描述系统中资源分配和进程的资源需求情况；

  • 1）可利用的资源向量 $\text{bold}\mathrm{Avail}$；

  • 2）所有进程的最大需求矩阵 $\text{bold}\mathrm{Max}$；

  • 3）所有进程已分配的资源矩阵 $\text{bold}\mathrm{Allocated}$；

  • 4）此时所有进程还需要的资源数量矩阵 $\text{bold}\mathrm{Need}$；

• 银行家算法：

  • 设 ${\text{bold}\mathrm{Req}}_i$ 是 $P_i$ 所申请的资源数向量，${\text{bold}\mathrm{Req}}_i[j]=k$ 表示 $P_i$ 需要 $k$ 个类型为 $j$ 的资源；

  • OS 收到资源请求向量后，按以下步骤进行检查：

    • 1）检查 ${\text{bold}\mathrm{Req}}_i[j]\le \text{bold}\mathrm{Need}[i][j]$，若不满足，说明 $P_i$ 申请的数量已超过最大值，驳回申请；

    • 2）检查 ${\text{bold}\mathrm{Req}}_i[j]\le \text{bold}\mathrm{Avail}[j]$，若不满足，说明此时资源不够，$P_i$ 需要等待；

    • 3）尝试分配给定数量的资源，并更新数据结构：

      • $\text{bold}\mathrm{Avail}[j]=\text{bold}\mathrm{Avail}[j]-{\text{bold}\mathrm{Req}}_i[j]$；

      • $\text{bold}\mathrm{Allocated}[i][j]=\text{bold}\mathrm{Allocated}[i][j]+{\text{bold}\mathrm{Req}}_i[j]$；

      • $\text{bold}\mathrm{Need}[i][j]=\text{bold}\mathrm{Need}[i][j]-{\text{bold}\mathrm{Req}}_i[j]$

    • 4）利用安全性算法，检查此次分配后系统是否还处于安全状态，若不满足，则取消分配，恢复数据结构；

• 安全性算法：

  • 1）设置两个向量：

    • 工作向量 $\text{bold}\mathrm{Work}$，表示当前 OS 可提供的各类资源数目，开始时 $\text{bold}\mathrm{Work}=\text{bold}\mathrm{Avail}$；

    • 布尔向量 $\text{bold}\mathrm{Finish}$，表示 OS 是否有足够的资源分配给进程，使之运行完成。开始时 $\text{bold}\mathrm{Finish}=\text{bold}\mathrm{false}$，当有足够资源给 $P_i$ 时，$\text{bold}\mathrm{Finish}[i]=true$；

  • 2）从进程集合中，找到一个满足下列条件的进程 $P_i$：

    • 2.1）先令 $\text{bold}\mathrm{Finish}[i]=false$；

    • 2.2）检查 $\text{bold}\mathrm{Need}[i][j]\le \text{bold}\mathrm{Work}[j]$，不满足则退出；

    • 2.3）假设 $P_i$ 获得资源后立即执行完成，并释放资源；

    • 2.4）令 $ \mathrm{\bold{Work}}[j]=\mathrm{\bold{Work}}[j]+\mathrm{\bold{Allocated}}[i][j]$；

    • 2.5）令 $\text{bold}\mathrm{Finish}[i]=true$；

  • 3）重复执行第 2 步，直到全部的 $\text{bold}\mathrm{Finish}$ 变为 true 或退出。若全部的 $\text{bold}\mathrm{Finish}$ 都变为 true,就表示系统安全；否则系统不安全；

4. 死锁的检测与解除

4.1. 死锁的检测

• 定义：保存 OS 中资源的请求和分配信息，并提供一种算法，检测 OS 是否已进入死锁；

• 资源分配图（Resource Allocation Graph）

  • 由一组节点 $N$ 和边 $E$ 组成的有向图 $G=(N,E)$；

  • 节点 $N$ 有两个互斥子集：进程节点集合 $\text{bold}\mathrm{P}$ 和资源节点集合 $\text{bold}\mathrm{R}$，$N=\text{bold}\mathrm{P}\cup \text{bold}\mathrm{R}$；

  • 每条边 $\mathrm{\forall }e\in E$，都连接着 $\text{bold}\mathrm{P}$ 中的一个点和 $\text{bold}\mathrm{R}$ 中的一个点；

    • 资源请求边 $e=\{{\text{bold}\mathrm{P}}_i,{\text{bold}\mathrm{R}}_j\}$：表示 $P_i$ 请求一个单位的资源 $R_j$；

    • 资源分配边 $e=\{{\text{bold}\mathrm{R}}_i,{\text{bold}\mathrm{P}}_j\}$：表示将一个单位的 $R_i$ 分配给 $P_j$；

  • 图示：

    

• 死锁定理

  • 1）在分配图中，找出一个不阻塞且非独立的进程 $P_i$，假设其运行完毕并释放资源，则消去与 $P_i$ 相连的所有分配边和请求边；

  • 2）反复执行第 1 步，直到所有进程节点都成为孤立节点，若能消去图中所有边，则称该图能完全简化，否则是不可完全简化的；

  • 当某个状态的系统对应的资源分配图是不可完全简化的，则此时系统进入死锁；

4.2. 死锁的解除

• 终止进程

  • 终止所有死锁进程：简单高效，但是代价较为昂贵；

  • 逐个终止：按照某种顺序逐个终止死锁进程，直到系统解除死锁；

    • 缺点：复杂，代价较大，每次终止一个进程都要进行判断，且终止顺序不好选择；