7 Deadlocks¶
说明
本文档正在更新中……
说明
本文档仅涉及部分内容，仅可用于复习重点知识
1 The Deadlock Problem¶
死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种互相等待的现象。这些进程都无法继续执行，因为它们需要的资源被另一个等待中的进程持有
2 Deadlock Characterization¶
如果以下四个条件同时成立，就可能出现死锁：
- mutual exclusion：某些资源本质上是独享的，不能同时被多个进程共享
- hold and wait：进程已经持有了部分资源，但在等待其他资源时不会释放已持有的资源
- no preemption：进程已获得的资源不能被强制剥夺，只能由进程主动释放
- circular wait：存在一个进程资源的循环等待链，每个进程都在等待下一个进程持有的资源
这四个条件是死锁发生的必要条件：如果发生死锁，这四个条件一定同时成立；如果这四个条件同时成立，可能会发生死锁（但不一定立即发生）；要预防死锁，只需破坏其中至少一个条件即可
3 System Model¶
系统中有多种资源类型，用 \(R_1, R_2, \cdots, R_m\) 表示。每个资源类型可能有多个相同的实体，称为实例，\(W_i\) 表示资源类型 \(R_i\) 的可用实例数量
每个进程在使用任何资源时都遵循标准的三步操作：
- request：进程请求获取资源实例
- use：进程在获得资源后执行其任务
- release：进程完成任务后主动归还资源
resource-allocation graph 包含一组顶点 \(V\) 和一组边 \(E\)。\(V\) 被划分为两种类型：\(P\) 包含系统中所有进程的集合，\(R\) 包含系统中所有资源类型的集合
- request edge：有向边 \(P_i \rightarrow R_j\)，进程正在请求一个资源实例
- assignment：有向边 \(R_j \rightarrow P_i\)，一个资源实例已经分配给了进程
- 如果资源分配图中没有任何循环（环），那么系统一定没有发生死锁
-
如果资源分配图中有环
- 如果每类资源只有一个实例，则一定发生死锁
- 如果至少某类资源有多个实例，则可能发生死锁
4 Methods for Handling Deadlocks¶
操作系统处理死锁问题的方法：
- 死锁预防：通过破坏死锁发生的四个必要条件之一来确保系统永远不会进入死锁状态
- 死锁检测与恢复：允许死锁发生，但能够检测到死锁并恢复系统
- 鸵鸟算法：忽略死锁问题，假设死锁不会发生或极少发生。被大多数通用操作系统（如 Linux 和 Windows）采用。因为死锁在实际系统中相对罕见，预防和检测的代价可能超过死锁发生的代价，通过重启系统等简单方式就能解决偶尔发生的死锁（例如通过任务管理器终止进程）
4.1 Deadlock Prevention¶
破坏死锁发生的四个必要条件之一
- mutual exclusion：尽可能使用可共享资源来避免互斥。对于只读文件等可共享资源，多个进程可以同时访问，无需互斥；但对于打印机等不可共享资源，互斥是固有的，无法破坏此条件。此条件通常难以完全破坏，因此重点放在其他条件上
-
hold and wait：确保进程在请求资源时不持有任何其他资源。存在的问题：资源利用率低（资源可能被提前占用但长时间未使用）；可能饥饿（需要大量资源的进程可能永远无法获得所有资源）；不切实际（进程通常无法预知所有需要的资源）
- 一次性分配：进程在开始执行前必须申请并获得所有需要的资源。缺点是资源可能长时间闲置，利用率低
- 动态请求：进程只有在不持有任何资源时才能请求新资源，需要额外资源时，必须先释放当前持有的所有资源，再重新申请。缺点是资源频繁释放和重新申请，效率低下
-
no preemption：当进程请求新资源无法立即获得时，系统会强制释放该进程当前持有的所有资源。这些被抢占的资源会被记录，该进程需要等待重新获得所有资源（包括原有的和新请求的）。缺点是实现复杂，代价高昂；可能导致进程重复执行部分工作，降低系统效率
- circular wait：为所有资源类型建立全局顺序（全序关系），要求所有进程必须按编号递增顺序申请资源。为每类资源分配唯一编号，进程必须先申请编号小的资源，再申请编号大的资源，如果需要先申请高编号资源，必须先释放所有低编号资源。优点在于相比其他方法更实用，系统开销较小
4.2 Deadlock Avoidance¶
死锁避免不像预防那样严格限制资源请求方式，而是通过动态决策来避免系统进入不安全状态
- 先验信息要求：系统需要预先知道每个进程对各类资源的最大需求，这是算法进行决策的基础信息
- 动态检查机制：在每次资源分配前，算法会检查分配后的系统状态是否安全，只允许不会导致死锁的资源分配，通过避免循环等待条件来预防死锁
- 资源分配状态：包括可用资源（当前系统中可用的各类资源数量）、已分配资源（每个进程当前持有的资源数量）、最大需求（每个进程最终可能需要的最大资源数量）
工作原理：当进程请求资源时，系统会检查如果满足该请求，系统是否会保持在安全状态。安全状态意味着存在某种进程执行顺序，使得所有进程都能顺利完成。只有在安全的情况下才批准资源分配
与 deadlock prevention 的区别
- 死锁预防：通过限制资源请求方式（静态）
- 死锁避免：通过动态分析资源分配状态（动态）
4.2.1 Safe State¶
安全状态是指系统能够按照某种顺序（称为安全序列）为所有进程分配资源，确保所有进程都能顺利完成
安全序列的条件：对于安全序列 \(<P_1, P_2, \cdots, P_n>\) 中的每个进程 \(P_i\)，\(P_i\) 的剩余资源需求 ≤ 当前可用资源 + 前面所有进程 \(P_j\ (j<i)\) 释放的资源。这意味着每个进程都能按顺序获得所需资源并完成执行
下面的系统是否处于安全状态
一共有 12 个资源实例，当前可用的有 3 个
- 首先执行 T1：完成后释放 2 个，现在可用的有 5 个
- 接下来就可以执行 T0：完成后释放 5 个，可用的有 10 个
- 最后可以执行 T2
因此，确实处于安全状态
下面的这个系统不处于安全状态
- 如果系统处于安全状态，那么没有死锁
- 如果系统不处于安全状态，那么可能死锁
而死锁避免的核心目标就是始终保持安全状态。在每次资源分配时进行检查，只批准那些分配后系统仍处于安全状态的请求，通过这种方式，系统永远保持在安全区域内
4.2.2 Resource-Allocation Graph¶
适用条件：每类资源只有一个实例
Claim edge（声明边）：虚线箭头 \(P_i \rightarrow R_j\)，表示进程未来可能请求资源
边的状态转换：
- 初始状态：声明边（虚线）。表示进程可能在未来请求该资源
- 请求资源：声明边 → 请求边（实线）。进程实际发出资源请求
- 分配资源：请求边 → 分配边（实线）。系统将资源分配给进程
- 释放资源：分配边 → 声明边（虚线）。进程完成任务后释放资源，回到初始状态
进程在开始执行前必须预先声明所有可能需要的资源类型，这是该算法有效的前提条件
在分配资源前，系统检查转换后图中是否存在环，如果分配会导致环出现，则拒绝分配（即使资源可用），通过这种方式确保系统永远不会进入不安全状态
4.2.3 Banker's Algorithm¶
适用条件：每类资源有多个实例
算法前提假设：
- 资源多实例：每类资源有多个相同实例
- 预先声明：进程开始前必须声明其最大资源需求
- 等待机制：请求不被立即满足时需要等待
- 有限占用：进程完成后必须在有限时间内释放所有资源
核心数据结构：
- available（可用资源向量）：记录当前可用的各资源数量。维度：m（资源类型数）。
Available[1] = 3表示资源 R₁ 有 3 个可用实例 - max（最大需求矩阵）：记录每个进程声明的最大资源需求。维度：n × m（进程数 × 资源类型数）。
Max[2, 3] = 5表示进程 P₂ 最多需要 5 个 R₃ 资源 - allocation（分配矩阵）：记录当前已分配给各进程的资源数量。维度：n × m。
Allocation[0, 2] = 1表示进程 P₀ 当前持有 1 个 R₂ 资源 - need（需求矩阵）：记录每个进程尚需的资源数量。维度：n × m。
Need = Max - Allocation