第四章：死锁

4.1 死锁的基本概念

死锁是指多个进程因争夺资源而陷入的一种互相等待的状态——每个进程都在等待其他进程释放资源，谁也无法继续推进。

类比：四人过独木桥，A在等B让路，B在等C让路，C在等D让路，D在等A让路——四人都过不去。

4.1.1 死锁的产生原因

  1. 竞争不可抢占资源（如打印机、共享数据区）。
  2. 进程推进顺序不当（如P1拿了资源R1想拿R2，P2拿了R2想拿R1）。

4.1.2 死锁与饥饿的区别

概念 含义
死锁 多个进程互相等待，谁也动不了
饥饿 一个进程长期得不到资源（但其他进程可以推进）

饥饿≠死锁。比如短进程优先算法中，长进程可能一直得不到CPU（饥饿），但其他短进程正常运行，这不是死锁。

4.2 死锁产生的四个必要条件

四个条件缺一不可：

条件 含义 类比
互斥 资源一次只给一个进程使用 一把伞一次只能一个人打
不剥夺 资源不能被OS强行夺走，只能由占有者主动释放 借出去的伞不能抢回来
请求并保持 进程已占有一些资源，又请求新资源，但新资源被其他进程占用 拿着伞还要抢雨衣
循环等待 存在一个进程-资源的循环等待链 A等B伞→B等C伞→C等A伞

💡 记忆技巧：四个条件首字母记为 Mutual exclusion, Hold and wait, No preemption, Circular wait → MHNC（"没钱还吃"——死锁因为资源不够）。

4.3 死锁预防

预防就是破坏四个必要条件中的至少一个：

4.3.1 破坏互斥条件

把资源改为共享——但有些资源天生不能共享（如打印机）。可行性低。

4.3.2 破坏不剥夺条件

当进程请求新资源被拒时，OS强制释放其已占有的资源。

  • 缺点：实现复杂，可能造成前功尽弃（如已写到一半的数据丢失）。

4.3.3 破坏请求并保持条件

静态分配：进程在运行前一次性申请所有需要的资源。只要有一个不满足就不运行。

  • 缺点：资源利用率低（"宁多勿少"——很多资源空闲却不能给别人用）。

4.3.4 破坏循环等待条件

顺序资源分配法：给资源编号，进程只能按递增顺序请求资源。

  • 缺点：编号困难，限制编程。

📌 408考点提示：死锁预防的四种方法是选择题常考内容。注意各方法的优缺点对比。

4.4 死锁避免（重点）

死锁避免比死锁预防更宽松——允许进程动态地申请资源，但每次分配之前检查是否会导致系统进入不安全状态。

4.4.1 安全状态与安全序列

  • 安全状态：系统能按某种顺序（安全序列）为所有进程分配资源，使它们都能完成。
  • 不安全状态：不存在任何安全序列。
  • 死锁一定在不安全状态中，但不安全状态不一定会死锁（可能只是无法完成序列，但还没死锁）。

4.4.2 银行家算法（Dijkstra提出，必考）

银行家算法的数据结构：

  • Available[m]：各类资源的可用数量。
  • Max[n][m]：每个进程对各类资源的最大需求。
  • Allocation[n][m]：每个进程已分配的资源数。
  • Need[n][m]：每个进程还需要的资源数（Need = Max - Allocation）。

银行家算法的步骤（当一个进程请求资源Request[i]时）：

  1. 检查请求量是否 ≤ Need：若超过，出错。
  2. 检查请求量是否 ≤ Available：若不够，等待。
  3. 试分配：Available -= Request; Allocation[i] += Request; Need[i] -= Request;
  4. 调用安全性检查算法：
    • 设置临时向量 Work = Available, Finish[k] = false
    • 找一个满足 Finish[k]==false 且 Need[k] ≤ Work 的进程
    • 找到则 Work += Allocation[k]; Finish[k] = true; 重复
    • 若所有 Finish 都是 true，安全；否则不安全，回滚分配。

📌 408考点提示：银行家算法的安全性检查是408计算题的重点。通常给几个进程的Max和Allocation，让你判断某次请求是否安全，写出安全序列。

💡 记忆技巧：银行家算法就像银行贷款——银行（OS）不能无限借钱（资源），需要评估借出去后还能不能收回（完成所有进程）。关键判断：当前剩余资源能不能满足某个进程的剩余需求，能满足就让它跑完释放资源，逐步推进。

4.5 死锁检测和解除

4.5.1 资源分配图

资源分配图由进程结点（圆圈）、资源结点（方框，小圆点表示资源实例数量）、请求边（进程→资源）和分配边（资源→进程）组成。

4.5.2 资源分配图简化法判断死锁

步骤：

  1. 找一个不阻塞的进程（该进程请求的资源都能被满足）。
  2. 让它运行，释放其占有的所有资源。
  3. 重复，直到所有进程都可化简（无死锁）或存在不可化简的进程（有死锁）。

判断标准：如果资源分配图不可完全简化，则系统处于死锁状态。

📌 408考点提示：简化资源分配图判断死锁是常考题型。注意区分资源结点中的小圆点（资源实例）和分配边/请求边的方向。

4.5.3 死锁解除

方法 做法 优点 缺点
资源剥夺 从一些进程夺走资源给死锁进程 简单 可能造成进程中断
撤销进程 强制终止死锁进程 彻底 代价大（可能丢失数据）
进程回退 回滚到检查点 保留部分工作 需要系统支持回退

示例题

示例1（银行家算法）：系统中有5个进程（P0-P4）和3类资源（A:10个, B:5个, C:7个）。在T0时刻如下：

进程 Allocation(A,B,C) Max(A,B,C) Need(A,B,C)
P0 (0,1,0) (7,5,3) (7,4,3)
P1 (2,0,0) (3,2,2) (1,2,2)
P2 (3,0,2) (9,0,2) (6,0,0)
P3 (2,1,1) (2,2,2) (0,1,1)
P4 (0,0,2) (4,3,3) (4,3,1)

Available = (10,5,7) - (7,2,5) = (3,3,2)

问题1：T0时刻是否安全？ 解：

步骤 Work 可满足的进程 完成后Work
初始 (3,3,2) P1需要(1,2,2) ≤ (3,3,2) → P1满足 (3,3,2)+(2,0,0)=(5,3,2)
第2步 (5,3,2) P3需要(0,1,1) ≤ (5,3,2) → P3满足 (5,3,2)+(2,1,1)=(7,4,3)
第3步 (7,4,3) P4需要(4,3,1) ≤ (7,4,3) → P4满足 (7,4,3)+(0,0,2)=(7,4,5)
第4步 (7,4,5) P2需要(6,0,0) ≤ (7,4,5) → P2满足 (7,4,5)+(3,0,2)=(10,4,7)
第5步 (10,4,7) P0需要(7,4,3) ≤ (10,4,7) → P0满足 (10,4,7)+(0,1,0)=(10,5,7)

安全序列：P1 → P3 → P4 → P2 → P0（答案不唯一，只要能找到安全的顺序即可）。

问题2：P1请求资源(1,0,2)，是否应分配？ 解：Request = (1,0,2)

  • 检查Request ≤ Need(1,2,2)：(1,0,2) ≤ (1,2,2) ✓
  • 检查Request ≤ Available(3,3,2)：(1,0,2) ≤ (3,3,2) ✓
  • 试分配后：
    • Available = (3,3,2) - (1,0,2) = (2,3,0)
    • Allocation(P1) = (2,0,0) + (1,0,2) = (3,0,2)
    • Need(P1) = (1,2,2) - (1,0,2) = (0,2,0)

重新检查安全性：Work=(2,3,0)，先找Need ≤ Work的进程：

  • P0需要(7,4,3) > (2,3,0) ✗
  • P1需要(0,2,0) ≤ (2,3,0) ✓ → 运行后Work=(2,3,0)+(3,0,2)=(5,3,2)
  • P3需要(0,1,1) ≤ (5,3,2) → Work=(5,3,2)+(2,1,1)=(7,4,3)
  • 后续类似，可以找到安全序列。

结论：安全，可以分配。

示例2（资源分配图化简）：考虑一个系统，有资源R1（3个实例）、R2（2个实例）。当前资源分配和请求情况如下：

  • P1持有R1的1个实例，请求R2的1个实例。
  • P2持有R2的1个实例，请求R1的1个实例。
  • P3持有R1的1个实例，不请求任何资源。
  • P4持有R1的1个实例和R2的1个实例，请求R2的1个实例。

解： 步骤1：检查各资源剩余可用数。 R1：总量3，已分配P1=1, P3=1, P4=1 → 剩余R1=0。 R2：总量2，已分配P2=1, P4=1 → 剩余R2=0。

步骤2：找出不阻塞的进程。

  • P1：请求R2的1个实例，但R2剩余为0 — 阻塞。
  • P2：请求R1的1个实例，但R1剩余为0 — 阻塞。
  • P3：无请求 — 不阻塞。
  • P4：请求R2的1个实例，但R2剩余为0 — 阻塞。

步骤3：P3可执行，释放其持有的R1的1个实例。R1剩余变为1。

步骤4：重新检查。

  • P2：请求R1的1个实例，R1剩余=1 ≥ 1 → P2可执行。释放P2（R2的1个实例），R2剩余变为1。
  • 然后P1或P4也能满足。

结论：该资源分配图可完全化简，无死锁。

示例3（死锁检测）：假设一个系统中有两个进程P1、P2和两种资源R1（1个实例）、R2（1个实例）。P1持有R1并请求R2，P2持有R2并请求R1。请判断是否存在死锁。

解： 分析：R1被P1持有，R2被P2持有。P1请求R2（被P2持有），P2请求R1（被P1持有）。形成了循环等待链：P1→R2→P2→R1→P1。

用资源分配图表示：

  • 分配边：R1→P1, R2→P2
  • 请求边：P1→R2, P2→R1

每个资源只有一个实例，所以分配边和请求边形成了环。死锁成立——两个进程互相等待，谁也前进不了。

408易混点：死锁、饥饿、活锁的区别：

  • 死锁：多个进程循环等待，谁也无法推进。
  • 饥饿：某个进程长时间得不到资源，但其他进程可以推进（如SJF中长进程的饥饿）。
  • 活锁：进程没有阻塞（一直在运行），但一直在做无用功——例如两个进程互相谦让，都检测到对方想进临界区就退让，导致谁也进不去。

示例4：死锁预防与避免的区别。

解：

  • 预防：通过破坏四个必要条件之一，静态地防止死锁发生。资源利用率低。
  • 避免：允许动态申请，但在分配时通过银行家算法检查安全性，动态地避免进入不安全状态。需要预先知道进程的最大需求（Max）。资源利用率较高。
  • 检测：不预防也不避免，允许死锁发生，定期检测后解除。

银行家算法的局限性与注意事项：

  1. 需要预先知道每个进程的最大需求（Max）——实际系统中很难准确预估。
  2. 进程数量必须是固定的（不支持动态创建进程）。
  3. 资源数量必须是固定的（不支持热插拔）。
  4. 这是最保守的方法——即使实际不会死锁，只要判定为"不安全状态"就拒绝分配。
  5. 假设进程会释放所有已分配资源——如果进程不释放（如死循环），算法无法处理。
  6. 银行家算法的名称来源于"银行家不会把所有钱都贷出去"的类比——银行家（OS）必须保留足够的资金（资源）以满足所有客户（进程）的最大需求。

补充：银行家算法中安全状态和不安全状态的区别示例：

考虑一个系统：只有1类资源A（10个），3个进程P1、P2、P3当前状态如下：

进程 Allocation Need
P1 3 5
P2 2 6
P3 2 3

Available = 10 - (3+2+2) = 3

判断是否安全： Work = 3

  • P3：Need=3 ≤ Work=3 → P3完成，Work=3+2=5
  • P1：Need=5 ≤ Work=5 → P1完成，Work=5+3=8
  • P2：Need=6 ≤ Work=8 → P2完成

安全序列：P3→P1→P2，状态安全。

如果Available只剩1个（即P1=3,P2=2,P3=4,剩余=1）：

  • 各进程Need都>1，都不可满足——不安全状态。

注意：不安全状态不代表一定会死锁——如果进程以后释放资源而不申请新资源，实际可能不会死锁。但OS为了保险起见，不分配资源给会导致不安全状态的请求。

本章小结

死锁是并发系统中的重要问题。需要重点掌握：死锁的四个必要条件、死锁预防的四种方式（破坏四个条件）、银行家算法的安全性判断和请求处理（408计算题重点）、资源分配图的简化方法。在操作系统大题中，银行家算法计算题和死锁相关的分析题出现频率很高，务必熟练掌握安全序列的推导过程。