第 20 讲：死锁、银行家算法与资源分配图

死锁不是“程序慢”，也不是“某个锁被占用”。它是一组执行流中，每一个都在等待只能由该组内其他成员产生的资源/事件，没有外力就永远不会前进。

资源既可以是用完后释放、可反复分配的锁和设备，也可以是消息、信号等产生后被消费的临时资源。因此死锁不只来自“两把互斥锁”：通信双方以错误顺序互等消息、先持有缓冲槽再等对方数据，也能形成同样的等待环。

一个最小死锁

P1: acquire(file)          P2: acquire(printer)
    acquire(printer)           acquire(file)
    ...                        ...

若 P1 已有 file、P2 已有 printer，再各等对方资源，就形成环。“再等一会”不会改变任何资源状态。

资源可分为：

  • 可剥夺：系统能安全收回，例如通过保存上下文收回 CPU；
  • 不可剥夺：强行收回会破坏操作，如打印到一半的打印机；
  • 可消耗/临时性资源：一个进程产生、另一个消费的消息、中断等，错误的接收—发送顺序也会环路等待。

死锁的四个必要条件

  1. 互斥：资源同时只能给有限进程使用；
  2. 请求并保持：进程持有旧资源时继续等新资源；
  3. 不可剥夺：资源只能由占有者主动释放；
  4. 循环等待：P1P_1 等 P2P_2 的资源，…，PnP_n 又等 P1P_1 的资源。

四者同时成立才可能死锁。破坏任一条可预防死锁，但往往以便利性、并发度或资源利用率为代价。

死锁、活锁和饥饿

现象执行流是否运行为什么不完成
死锁通常阻塞等待环内不可能自发产生的条件
活锁一直在改状态/重试彼此过度礼让或同步重试，没有有效进展
饥饿其他人在进展调度/锁策略让某个人长期得不到资源

随机退避可打破活锁的同步节奏，公平队列和 aging 可缓解饥饿；它们不是同一个问题的三个名字。

四类处理态度

  1. 忽略：假定极少发生，由应用/人工重启；
  2. 预防：用静态规则破坏四个必要条件之一；
  3. 避免：保留四个条件的灵活性，但每次分配前预测是否仍安全；
  4. 检测与解除：允许死锁发生，定期/按需找出，再终止、回滚或剥夺。

死锁预防：每种方法付出什么

破坏互斥

只适用本来就可共享或能虚拟化的资源。例如 SPOOLing 把多个打印请求先写到磁盘队列，由唯一后台进程真正占用打印机。但同一物理时刻的打印机仍是互斥的。

破坏请求并保持

要求进程开始前一次申请全部资源，或申请新资源前先释放已有资源。问题是需求可能事先不可知，而且很早占着暂时不用的资源，利用率低。

破坏不可剥夺

申请新资源失败时，强制释放/回滚已有资源。只适合能保存和恢复状态的资源；强行收回正在输出的设备可能产生不可恢复外部效果。

破坏循环等待

为所有资源类型设置全局序号，只允许按递增序申请。如果等待边永远从小编号指向大编号，就无法绕回起点。这是锁层次和 lock ordering 常用的工程方法，但全局顺序设计和遵守有成本。

安全状态不等于当前没死锁

安全状态：存在一个进程顺序，使每个进程都能用当时可用资源加上前面已完成进程释放的资源，获得其最大剩余需求并完成。

不安全状态表示 OS 已经无法保证所有进程在声明的最大需求内都能完成；它可能尚未死锁，因为进程未必真的同时要满。但避免策略不允许走入这种无保证状态。

银行家算法的数据结构

设 nn 个进程、mm 类资源：

  • Available[m]：当前未分配的每类资源数；
  • Max[n][m]：每进程声明的最大需求；
  • Allocation[n][m]：当前已分配；
  • Need=Max-Allocation：完成最多还可能需要多少。

进程 PiP_i 提出 Request_i 时：

  1. 检查 Request_i <= Need_i，否则超出自己声明；
  2. 检查 Request_i <= Available，否则现在只能等；
  3. 暂时扣减 Available、增加 Allocation_i、减少 Need_i；
  4. 执行安全性算法；
  5. 仍安全才真正批准，否则回滚试分配并让进程等待。

安全性算法完整例子

资源总量 A/B/C = 10/5/7，当前：

进程AllocationMaxNeed
P00 1 07 5 37 4 3
P12 0 03 2 21 2 2
P23 0 29 0 26 0 0
P32 1 12 2 20 1 1
P40 0 24 3 34 3 1

已分配合计为 7/2/5，因此 Available = 3 3 2。设 Work=Available：

  1. P1 的 Need 1/2/2 ≤\le 3/3/2，可完成，Work += Allocation1 = 5 3 2；
  2. P3 的 0/1/1 ≤\le 5/3/2，完成后 Work = 7 4 3；
  3. P4 的 4/3/1 ≤\le 7/4/3，完成后 Work = 7 4 5；
  4. P0 的 7/4/3 ≤\le 7/4/5，完成后 Work = 7 5 5；
  5. P2 的 6/0/0 ≤\le 7/5/5，完成。

所以 <P1,P3,P4,P0,P2> 是一条安全序列。安全序列不唯一；每一步都只需找一个 Need <= Work 的未完成进程。

试分配一个请求

若 P1 请求 1/0/2：

  • 1/0/2 ≤\le P1 Need 1/2/2；
  • 1/0/2 ≤\le Available 3/3/2；
  • 试分配后 Available=2/3/0，P1 Allocation=3/0/2，Need=0/2/0。

此时 P1 可先完成，Work 从 2/3/0 变为 5/3/2，后面仍可按 P3、P4、P0、P2 完成，所以请求可批准。

银行家算法为什么不是免费午餐

  • 进程必须事先声明最大需求，而现实程序可能动态决定；
  • 资源总数和进程集应相对稳定；
  • 每次请求要执行矩阵检查；
  • 为保持安全，可能暂拒一个当前明明有资源可满足的请求。

它保留了比静态预防更高的利用率，但前提是系统能得到可信的最大需求。

资源分配图（RAG）

图中：

  • 进程结点 PiP_i；
  • 资源类结点 RjR_j，结点内可有多个实例；
  • Pi→RjP_i\to R_j 是请求边；
  • Rj→PiR_j\to P_i 是分配边。

如果每类资源只有一个实例，有向环与死锁等价。有多实例时，有环只说明可能死锁：环外的某个资源实例可能先被释放，使环能打开。

资源分配图中有环且死锁与有环但不死锁的对比

课件还用“化简”表述检测：反复找出当前未阻塞、其剩余请求可被可用资源满足的进程，假想它完成并释放资源，删去相关边。若最终仍有无法化简的边/进程集，它们就是死锁候选。

检测到之后怎么解除

  • 终止所有死锁进程：快，但损失大；
  • 每次终止一个，重新检测：可减少损失，但检测开销增加；
  • 剥夺资源：需选牺牲者，并能回滚到一致检查点；
  • 选牺牲者时可考虑优先级、已运行时间、还需多少资源、已产生外部效果等；
  • 需防止总选中同一进程导致饥饿。

“释放它所有锁然后继续运行”通常不安全：进程可能已在共享对象上做了半套更新。解锁必须同时考虑状态回滚或重启。

死锁题的四步过滤

  1. 先画清“谁持有什么、还等什么”；
  2. 检查四条必要条件，说清方案破坏了哪一条；
  3. 银行家题先重算 Need=Max-Allocation 和 Available=Total-sum(Allocation)；
  4. 安全性检查每一步都写 Work 怎么因完成进程而增加，不要只凭感觉列序列。

评论