沃以的小站

Appearance

进程死锁 ​

一、产生原因 ​

死锁的根本原因是：不可剥夺资源的竞争与进程推进顺序的不当共同作用的结果。

  • 不可剥夺资源：指一旦被进程占用，该资源不能被系统强行回收，必须由占用进程主动释放（如打印机、磁带机、文件写锁等）。
  • 竞争资源：多个并发进程同时请求数量有限的不可剥夺资源。
  • 推进顺序不当：操作系统在资源分配时未对进程的资源请求顺序进行有效约束，导致出现循环等待。

上述因素在特定条件下同时发生，将导致一组进程永久阻塞，即死锁。

二、解决方案 ​

处理死锁的策略可分为两类：静态预防/避免（不让死锁发生）和动态检测/恢复（允许发生但事后处理）。

1. 预防（Prevention） ​

死锁预防通过设计资源分配策略，破坏死锁发生的四个必要条件之一，从而在根本上杜绝死锁。其四种具体方法如下：

（1）破坏互斥条件 ​

  • 原理：使资源可被多个进程同时访问。
  • 可行性：对大多数物理设备（如打印机）或需要独占访问的逻辑资源（如写操作）而言，互斥是其固有属性，无法破坏。
  • 结论：此方法在实际系统中基本不可行，仅适用于少数可共享资源（如只读文件）。

（2）破坏不可剥夺条件 ​

  • 原理：允许系统在特定情况下强制回收进程已占有的资源。
  • 实现方式：当某进程请求新资源而无法立即满足时，系统可要求其释放所有已占资源，待以后重新申请时一并获取。
  • 缺点：
    • 系统开销大：需保存和恢复进程状态；
    • 可能导致进程饥饿：频繁被剥夺资源的进程难以完成任务；
    • 降低系统吞吐量。

（3）破坏请求并保持条件（Hold and Wait） ​

  • 原理：要求进程在开始执行前，必须一次性申请其在整个运行过程中所需的所有资源。
  • 实现方式：进程启动时提出全部资源请求，只有当系统能满足全部需求时才予以分配，否则进程阻塞等待。
  • 缺点：
    • 资源利用率低：已分配的资源在进程未使用期间处于空闲状态；
    • 可能导致进程饥饿：若所需资源总量较大，进程可能长期等待；
    • 延长进程周转时间。

（4）破坏循环等待条件 ​

  • 原理：对系统中所有资源类型进行线性排序，规定进程只能按序号递增的顺序申请资源。
  • 实现方式：为每类资源分配唯一序号，进程在申请资源时，其请求的资源序号必须严格大于当前已占资源的最高序号。
  • 缺点：
    • 编程复杂性增加：应用程序需了解资源编号；
    • 可能导致资源浪费：为满足序号要求，进程可能提前申请并不立即使用的资源；
    • 资源序号的分配可能与实际使用逻辑不符，降低灵活性。

2. 避免（Avoidance） ​

死锁避免不预先限制进程行为，而是在每次资源分配前，动态检查系统的状态是否安全。若分配后系统仍处于安全状态，则允许分配；否则，拒绝请求，让进程等待。

  • 安全状态：指系统存在一个进程执行序列，使得每个进程都能获得其所需的最大资源并顺利完成。该序列称为安全序列。
  • 核心算法：银行家算法（Banker's Algorithm）。
    • 前提：系统需事先知道每个进程的最大资源需求。
    • 过程：在分配资源前，模拟分配操作，利用安全性检查算法验证是否存在安全序列。
    • 优点：相比预防策略，资源利用率更高。
    • 缺点：
      • 要求进程预先声明最大需求，这在实际中难以准确预知；
      • 算法执行开销较大，尤其在资源和进程数量较多时；
      • 不适用于动态变化的进程集合。

3. 检测与解除（Detection and Recovery） ​

该策略允许死锁发生，但通过周期性检测发现死锁，并采取措施解除。

（1）死锁检测 ​

  • 方法：使用资源分配图（Resource Allocation Graph, RAG）或其简化形式进行检测。
    • 图中包含进程节点和资源节点；
    • 通过化简算法（如消去无请求边的进程）判断图中是否存在环；
    • 若存在环，则系统处于死锁状态。
  • 特点：检测算法本身有计算开销，检测频率需权衡（过高影响性能，过低延迟恢复）。

（2）死锁解除 ​

一旦检测到死锁，系统可采用以下方法恢复：

  • 终止进程：
    • 终止所有死锁进程：简单直接，但代价高昂；
    • 逐个终止：按优先级、已执行时间、资源占用量等标准选择牺牲者，逐步打破死锁环。
  • 资源剥夺：
    • 从一个或多个死锁进程中强行回收资源，分配给其他死锁进程；
    • 被剥夺资源的进程需回滚到安全状态，并可能需重新执行；
    • 需要系统支持检查点和回滚机制，实现复杂。

4. 忽略（鸵鸟算法） ​

  • 原理：假设死锁在实际运行中极少发生，故选择不处理。
  • 适用场景：死锁发生概率极低，且解除死锁的代价远高于其带来的损失（如通用操作系统 Windows、UNIX）。
  • 实践：依赖系统稳定性和应用程序良好设计来避免死锁，或通过重启等粗粒度手段恢复。

三、银行家算法（Banker's Algorithm）详细讲解 ​

一、基本思想 ​

银行家算法是一种死锁避免策略，其核心思想来源于银行贷款系统的风险管理：

银行在向客户发放贷款前，会评估： “如果我满足此客户的全部贷款请求，是否仍能保证所有客户（包括此客户）未来都能获得所需资金并最终归还？” 若答案为“是”，则发放贷款；否则，拒绝请求，让客户等待。

在操作系统中：

  • 银行 ⇨ 操作系统
  • 客户 ⇨ 进程
  • 资金 ⇨ 系统资源（如内存、设备）
  • 贷款请求 ⇨ 进程的资源请求

该算法通过模拟资源分配，确保系统始终处于安全状态，从而避免死锁。

二、前提条件 ​

要使用银行家算法，系统必须满足以下前提：

  1. 进程数量固定（或可预知）；
  2. 每类资源的总量固定；
  3. 每个进程必须预先声明其对各类资源的最大需求量（Max）；
  4. 进程的资源请求不能超过其声明的最大需求。

⚠️ 这些前提在实际系统中往往难以完全满足，因此该算法主要用于理论教学和特定批处理环境。

三、核心数据结构 ​

假设系统中有 n 个进程（P₀, P₁, ..., Pₙ₋₁）和 m 类资源（R₀, R₁, ..., Rₘ₋₁），则定义以下数据结构：

数据结构类型说明
Available长度为 m 的向量Available[j] 表示当前系统中可用的第 j 类资源数量。
Maxn × m 的矩阵Max[i][j] 表示进程 Pᵢ 对第 j 类资源的最大需求量。
Allocationn × m 的矩阵Allocation[i][j] 表示当前已分配给进程 Pᵢ 的第 j 类资源数量。
Needn × m 的矩阵Need[i][j] = Max[i][j] - Allocation[i][j]，表示进程 Pᵢ 仍需的第 j 类资源数量。

所有数据均为非负整数。

四、算法流程 ​

银行家算法包含两个核心子算法：资源请求处理算法和安全性检查算法。

（1）资源请求处理算法 ​

当进程 Pᵢ 请求资源向量 Requestᵢ 时，系统执行以下步骤：

步骤 1：合法性检查 若 Requestᵢ[j] > Need[i][j] 对任意 j 成立，则拒绝请求（请求超过声明的最大需求）。

步骤 2：可用性检查 若 Requestᵢ[j] > Available[j] 对任意 j 成立，则进程阻塞等待（当前资源不足）。

步骤 3：试探性分配 假设分配成功，更新状态：

text
Available = Available - Requestᵢ
Allocation[i] = Allocation[i] + Requestᵢ
Need[i] = Need[i] - Requestᵢ

步骤 4：安全性检查 调用安全性检查算法（见下文）。

  • 若系统仍处于安全状态，则正式分配资源；
  • 否则，撤销试探性分配（恢复原状态），并让进程 Pᵢ 等待。

（2）安全性检查算法 ​

该算法用于判断当前资源分配状态是否安全。

输入：当前 Available、Allocation、Need 矩阵 输出：安全序列（若存在）或“不安全”

步骤：

  1. 初始化：

    • Work = Available（工作向量，表示当前可用资源）
    • Finish[0..n-1] = false（标记进程是否已完成）

  2. 寻找满足以下条件的进程 Pᵢ：

    • Finish[i] == false
    • Need[i] ≤ Work（即对所有 j，Need[i][j] ≤ Work[j]）

  3. 若找到这样的 Pᵢ：

    • 假设 Pᵢ 获得所需资源并完成，释放其占用资源：

      text
      Work = Work + Allocation[i]
Finish[i] = true

    • 将 Pᵢ 加入安全序列，返回步骤 2。

  4. 若找不到这样的 Pᵢ：

    • 检查是否所有 Finish[i] == true：
      • 若是，则系统安全，返回安全序列；
      • 否则，系统不安全。

✅ 安全状态的定义：存在一个进程执行序列 <P₁, P₂, ..., Pₙ>，使得每个 Pᵢ 都能在有限时间内获得其所需资源（Need[i] ≤ 当前可用资源）并完成，从而释放其占用的所有资源。

五、算法示例（简化） ​

假设：

  • 资源类型：A, B, C

  • 总资源：Total = (10, 5, 7)

  • 当前状态：

    进程AllocationMaxNeed
    P₀(0,1,0)(7,5,3)(7,4,3)
    P₁(2,0,0)(3,2,2)(1,2,2)
    P₂(3,0,2)(9,0,2)(6,0,0)
    P₃(2,1,1)(2,2,2)(0,1,1)
    P₄(0,0,2)(4,3,3)(4,3,1)

  • Available = Total - ΣAllocation = (3,3,2)

问：若 P₁ 请求 (1,0,2)，系统是否应分配？

解：

  1. 合法性：Request=(1,0,2) ≤ Need[1]=(1,2,2) → 合法。
  2. 可用性：Request=(1,0,2) ≤ Available=(3,3,2) → 可用。
  3. 试探分配后：Available = (2,3,0)
  4. 安全性检查：
    • Work = (2,3,0)
    • 可完成 P₃（Need=(0,1,1) ≤ Work）
    • 释放后 Work = (2,3,0)+(2,1,1) = (4,4,1)
    • 可完成 P₄（Need=(4,3,1) ≤ Work）
    • 释放后 Work = (4,4,1)+(0,0,2) = (4,4,3)
    • 可完成 P₁（Need=(0,2,0) ≤ Work）
    • 释放后 Work = (4,4,3)+(3,0,2) = (7,4,5)
    • 可完成 P₀、P₂ → 存在安全序列 <P₃, P₄, P₁, P₀, P₂>，安全，可分配。

六、优缺点分析 ​

优点 ​

  • 避免了死锁，同时比死锁预防策略具有更高的资源利用率；
  • 逻辑清晰，为理解安全状态提供了理论框架。

缺点 ​

  • 要求进程预先声明最大资源需求，这在交互式或动态系统中难以实现；
  • 进程数量必须固定，不适用于动态创建/销毁进程的环境；
  • 算法开销大：每次资源请求都需执行 O(n²m) 的安全性检查；
  • 可能导致进程饥饿：若某进程的请求长期使系统不安全，它将永远等待。

七、实际应用 ​

尽管银行家算法在通用操作系统中较少直接使用，但其思想影响深远：

  • 数据库管理系统：事务调度中的死锁避免；
  • 实时系统：在资源受限环境下进行安全调度；
  • 理论研究：作为死锁避免的经典模型，用于教学和算法设计。

总结 ​

死锁处理策略的选择需在系统开销、资源利用率、实现复杂度和可靠性之间进行权衡：

  • 预防策略简单但保守，适用于资源类型固定、进程行为可预知的场景；
  • 避免策略灵活性高，但依赖进程的完整需求信息，适用于批处理系统；
  • 检测与解除策略资源利用率最高，但实现复杂，适用于对性能要求高且能容忍短暂死锁的系统；
  • 忽略策略适用于死锁风险极低的通用系统。

上次更新于: