第 5 章 · 死锁

死锁：一组进程互相持有对方想要的资源、又都等待对方释放，永远无法前进。

5.1 四个必要条件

死锁成立当且仅当四个条件同时满足：

1. 互斥：资源一次只能给一个进程。
2. 占有并等待：已占一些资源，又申请新的。
3. 不可剥夺：已获得的资源不能强行抢走。
4. 循环等待：存在进程-资源环形等待链。

破坏任意一个即可预防死锁。前三个是资源特性，第四个是结果。

资源分配图：进程（圆）→ 资源（方框）为请求边，资源 → 进程为分配边。成环且资源单实例 ⇒ 必死锁；多实例时环只是必要条件。

P1 ──请求──→ R2        R1（1 实例）←──持有── P2
P2 ──请求──→ R1        R2（1 实例）←──持有── P1
→ 成环，死锁

5.2 预防 / 避免 / 检测解除

• 预防（prevention）：事前破坏一个条件。① 破坏互斥（资源做成可共享）——不现实；② 破坏占有等待（一次性申请全部资源）——利用率低；③ 破坏不可剥夺（可抢占）——不适合打印机等；④ 破坏循环等待（给资源编号，按序申请）——常用。
• 避免（avoidance）：运行时动态判断是否安全，只允许进入安全状态。代表：银行家算法。
• 检测与解除（detection & recovery）：允许死锁发生，周期性检测（资源分配图 + 进程等待图）发现环则解除：抢占资源 / 回滚 / 终止进程（代价大）。

5.3 银行家算法

银行家算法基于「安全状态」：存在一个资源分配序列能让所有进程完成，则系统安全，可分配。

// Available[j]：资源 j 剩余；Max[i][j]：i 最多需要；Allocation[i][j]：已分配
// Need[i][j] = Max - Allocation
// 安全性检查：反复找「Need[i] ≤ Available」的进程，假设它完成并释放资源

一个进程申请资源时：若 Request[i] > Need[i] 或 > Available 拒绝；否则试探分配，跑安全性算法，安全才真正分配，不安全则撤销（让进程等待）。

缺陷：需预知最大需求 Max（现实难给）、每次申请都跑检查（开销大），故实际系统几乎不用，多靠「预防 + 检测」。

5.4 三种策略对比

策略	时机	代价	资源利用率	适用
预防	事前（破坏条件）	低（设计时定死）	低	简单固定资源
避免	运行时	中（每次申请检查）	中	需求可预知
检测解除	事后	高（终止/回滚）	高	死锁极少发生

死锁 = 谁也动不了（循环等待）；饥饿 = 有人一直得不到（SJF 长作业饿死，见第 3 章），更低一级的公平问题。