死锁避免,预防,检测算法

1. 死锁预防 (Deadlock Prevention)

死锁预防是最严格的策略。其核心思想是通过在系统设计时施加特定的限制，从结构上破坏死锁产生的四个必要条件中的至少一个，从而使得死锁永远不会发生。这更像是一系列静态策略或协议，而不是动态运行的算法。

• 破坏“互斥”条件 (Break Mutual Exclusion)

  • 方法: 允许资源被同时访问。但这只适用于那些本质上可共享的资源（如只读文件）。对于打印机、处理器等临界资源，互斥是无法被破坏的。

  • “伪共享”技术: 对于打印机这类独占设备，可以使用 SPOOLing 技术 (假脱机技术)。进程并不直接访问打印机，而是将打印数据输出到一个共享的磁盘缓冲区（Spool），由系统的一个服务进程统一、依次地从缓冲区读取并打印。对进程而言，它感觉自己可以随时“打印”，但实际上对物理打印机的访问依然是互斥的。这种方法绕过了互斥的限制，但并未真正破坏它。

  • 考纲地位: 思路简单，但应用场景有限。

• 破坏“请求与保持”条件 (Break Hold and Wait)

  • 方法1：一次性申请 (Request All at Once)

    • 协议: 规定进程在开始运行前，必须一次性地申请其执行过程中所需的全部资源。若系统能满足其所有请求，则分配给它；否则，一个资源也不给它，让其等待。

    • 缺点: 资源浪费严重（很多资源在进程后期才用到，但一开始就被占用），且可能导致“饥饿”（一个需要很多资源的进程可能永远无法满足所有请求）。

  • 方法2：先释放再申请 (Release then Request)

    • 协议: 允许进程动态申请资源，但在申请新资源前，必须先释放它所有已占有的资源。

    • 缺点: 实现复杂，代价高昂。进程多次执行的数据可能需要保存和恢复，严重影响效率。

• 破坏“不可剥夺”条件 (Break No Preemption)

  • 方法: 允许操作系统强行“剥夺”已被占有的资源。

  • 协议: 当一个已持有某些资源的进程申请新资源被阻塞时，它必须释放其当前持有的所有资源。另一种更复杂的协议是，当进程P申请的资源被进程Q占用时，若Q的优先级低于P，则系统可以剥夺Q的资源给P。

  • 缺点: 实现非常复杂，且只适用于状态可以轻易保存和恢复的资源（如CPU、内存），不适用于打印机等设备。

• 破坏“循环等待”条件 (Break Circular Wait)

  • 方法: 资源有序分配法 (Resource Ordering/Hierarchy)

    • 协议: 将系统中所有资源类型进行线性排序，并赋予它们唯一的序号（如 R1, R2, ..., Rn）。规定任何进程在申请资源时，必须严格按照序号递增的顺序进行申请。

    • 举例: 若一个进程已持有 Ri，则它接下来只能申请序号大于 i 的资源 Rj (j > i)。这样绝对不会形成 P1等P2、P2等P1 的环路。

    • 优点: 相较于前几种破坏方式，这是实现相对简单、代价较小且应用最广的预防策略。

    • 缺点: 限制了进程申请资源的灵活性，可能导致资源使用不便；且需要为所有资源编号，给系统设计带来负担。

2. 死锁避免 (Deadlock Avoidance)

死锁避免是一种比预防更宽松的策略。它不要求破坏必要条件，而是在资源分配的过程中，通过一个动态运行的算法来判断本次分配是否会将系统带入“不安全状态”。如果会，则拒绝分配，让进程等待；否则，执行分配。

核心思想: 确保系统始终处于安全状态。所谓安全状态，是指系统能找到一个安全序列 <P1, P2, ..., Pn>，即按照这个序列的顺序为每个进程分配其所需资源，可以使所有进程都顺利完成。不安全状态不一定是死锁状态，但可能导致死锁。

• 算法：银行家算法 (Banker's Algorithm)

  • 这是死锁避免策略的最著名、也是唯一的考纲核心算法。它适用于每种资源有多个实例的系统。

  • 所需数据结构:

    • Available: 一个向量，表示每种资源当前可用的实例数。

    • Max: 一个矩阵，表示每个进程完成其任务所需各类资源的最大数量。

    • Allocation: 一个矩阵，表示当前已分配给每个进程的各类资源实例数。

    • Need: 一个矩阵，表示每个进程还需要多少资源才能完成任务。Need[i, j] = Max[i, j] - Allocation[i, j]。

3. 死锁检测与解除 (Deadlock Detection and Recovery)

这是最宽松的策略。它允许系统进入死锁状态，但要求系统能检测出死锁的发生，并采取措施解除死锁。

• 死锁检测算法:

  • 基于资源分配图 (适用于每类资源只有一个实例):

    • 方法: 系统维护一个等待图 (Wait-for Graph)，它是资源分配图的简化版，只包含进程节点和它们之间的等待关系。如果进程 Pi 等待进程 Pj 拥有的资源，则画一条从 Pi 到 Pj 的有向边。

    • 算法: 定期地在等待图中运行一个环路检测算法 (如深度优先搜索)。如果检测到环路，则证明系统发生了死锁。

  • 类似于银行家算法的检测算法 (适用于每类资源有多个实例):

    • 该算法与安全性算法非常相似，但不使用Max或Need矩阵，而是使用Request矩阵表示进程当前申请的资源。

    • 数据结构: Available, Allocation, Request。

    • 步骤:

      1. 初始化 Work = Available, Finish (所有为 false)。

      2. 寻找一个进程 Pi，满足 Finish[i] == false 且 Request[i] <= Work。注意，这里判断的是Request而非Need。

      3. 若找不到，跳转到第5步。

      4. 若找到，说明 Pi 的请求可以被满足，它不会被永久阻塞。我们假定它能运行完并释放已分配的资源。更新 Work = Work + Allocation[i], Finish[i] = true，返回第2步。

      5. 算法结束时，如果存在某个进程 Pi 的 Finish[i] 仍为 false，则该进程 Pi 就是死锁进程。

• 死锁解除方法 (Deadlock Recovery):

  • 1. 进程终止 (Process Termination)

    • 方法一：终止所有死锁进程。简单粗暴，代价巨大。

    • 方法二：逐个终止死锁进程。每终止一个，就重新运行死锁检测算法，直到环路被打破。选择终止哪个进程，通常会考虑进程优先级、已运行时间、已占用资源等因素，以求代价最小。

  • 2. 资源剥夺 (Resource Preemption)

    • 方法: 强行从一个或多个死锁进程中剥夺资源，分配给其他死锁进程，以打破环路。

    • 需要考虑的问题:

      • 选择牺牲者 (Victim Selection): 剥夺哪个进程的哪个资源，代价最小？

      • 回滚 (Rollback): 进程的资源被剥夺后，其状态必须回退到某个安全的时间点（检查点），并重新开始。这可能导致该进程“饥饿”。

      • 饥饿 (Starvation): 如果总是选择同一个进程作为牺牲者，它可能永远无法完成。需要有机制确保公平性。