死锁

本节导读

大纲的「死锁」列了：死锁的基本概念、死锁预防、死锁避免、死锁检测和解除。这一节的计算集中在银行家算法：求 Need 和 Available、找安全序列、判断一个请求能否满足；另一类计算是「至少要多少资源才不会死锁」。

学完你应该能说出死锁的四个必要条件，分清预防、避免、检测三种思路，并能完整地走一遍银行家算法。

死锁的概念与必要条件

多个进程因竞争资源而互相等待，没有外力作用时谁都无法向前推进，这种状态叫死锁。产生死锁的原因有两个：竞争不可剥夺的资源（数量不够分），以及进程推进的顺序不当。

死锁的四个必要条件（缺一个就不会死锁）：

• 互斥：资源一次只能被一个进程使用；
• 不剥夺：进程已获得的资源在用完之前不能被强行夺走；
• 请求并保持：进程已经保持了资源，又提出新的请求，新请求得不到满足时也不释放已有的资源；
• 循环等待：存在一个进程等待链，链中每个进程都在等下一个进程占有的资源。

资源分配图用圆圈表示进程、方框表示一类资源（框内的点表示这类资源的个数），请求边从进程指向资源，分配边从资源指向进程。化简资源分配图时，找一个请求都能满足的进程，消去它的全部边（相当于它运行完、释放了资源），反复进行；能消去所有边称为可完全化简。死锁定理：系统处于死锁状态，当且仅当它的资源分配图不可完全化简。

至少需要多少资源：n 个进程竞争同一类资源、每个最多需要 m 个时，最坏情况是每个进程都已拿到 m − 1 个、都还差 1 个。只要资源总数不少于 $n(m-1)+1$n(m−1)+1，就至少有一个进程能拿够、运行完并释放资源，系统就不会死锁。

死锁预防

预防是事先破坏四个必要条件中的一个：

破坏的条件	做法	缺点
互斥	把只能互斥使用的资源改造成可共享的，如用 SPOOLing 技术把独占的打印机变成逻辑上共享	很多资源的互斥是正确使用的前提，一般行不通
不剥夺	进程的新请求得不到满足时，释放已保持的全部资源，以后再重新申请	实现复杂，已做的工作可能作废，只适合状态容易保存和恢复的资源
请求并保持	预先静态分配：进程运行前一次申请它需要的全部资源	资源利用率低，还可能让某些进程长期凑不齐资源而饥饿
循环等待	顺序资源分配：给资源编号，进程只能按编号递增的顺序申请	编号要相对稳定，申请顺序与使用顺序不一致时会浪费资源

死锁避免与银行家算法

避免不事先破坏必要条件，而是在每次分配前判断：这次分配会不会让系统进入不安全状态。如果系统能找到一个进程序列，按这个顺序给每个进程分配它还需要的资源，大家都能运行完，这个序列叫安全序列，系统处于安全状态。安全状态一定不会死锁；不安全状态不一定死锁，但有可能。

银行家算法用到四个数据结构：Available（各类资源的可用数）、Max（各进程的最大需求）、Allocation（已分配数）、Need = Max − Allocation（还需要的数）。进程 Pi 提出请求时：

1. 请求量 ≤ Pi 的 Need，否则出错（超过了它宣布的最大需求）；
2. 请求量 ≤ Available，否则 Pi 等待（资源不够）；
3. 试分配：Available 减去请求量，Pi 的 Allocation 加上、Need 减去请求量；
4. 执行安全性算法，安全就正式分配；不安全就撤销试分配，Pi 等待。

安全性算法：令 Work = Available，找一个还没完成、Need ≤ Work 的进程，假定它运行完，Work 加上它的 Allocation，标记它已完成；反复进行，所有进程都能标记完成则系统安全。

死锁检测和解除

检测：不预先限制，允许死锁发生，系统定时或在请求得不到满足时运行检测算法。检测算法与安全性算法相似，只是拿各进程当前的请求量（而不是 Need）与 Work 比较，最后不能完成的进程就是死锁进程。也可以用资源分配图化简来判断。

解除：

• 资源剥夺法：挂起某些死锁进程，抢占它们的资源分给其他死锁进程，要防止被挂起的进程长期得不到资源；
• 撤销进程法：强制撤销部分甚至全部死锁进程，按优先级和撤销代价选择撤销对象；
• 进程回退法：让一个或多个进程回退到足以解除死锁的地步，要求系统保存进程的历史信息、设置还原点。

易错提醒

• ❌ 系统处于不安全状态，说明已经发生了死锁。✅ 不安全状态只是有可能死锁，而死锁状态一定是不安全状态。因为不安全状态下，进程不一定真会按最大需求去申请资源。