死锁
死锁
复习定位
两个或多个进程互相等待只有对方才能释放的资源——且没有一个愿意让出已占有的资源——形成闭环——所有参与进程永远无法继续执行——这就是死锁。研究死锁不是为了真在OS里实现复杂避免——多数操作系统采取鸵鸟策略(假装没有死锁问题)——但数据库事务中死锁是真实存在的——InnoDB通过等待图检测并回滚一个事务。
死锁的四个必要条件
这四个条件必须同时满足才可能发生死锁——只要破坏任意一个——死锁就不会发生。
互斥(Mutual Exclusion)：资源不能被共享——一次只能被一个进程使用(打印机互斥访问、写同一个文件句柄等)。可共享的资源如只读文件——多个进程可同时打开——不会产生死锁。
持有并等待(Hold and Wait)：进程持有一部分资源——同时在等待另外的资源——而且不释放已持有的资源。
不可剥夺(No Preemption)：已分配给进程的资源不能被强行夺走——只能由占有它的进程主动释放。
环路等待(Circular Wait)：存在一个进程集合{P1,P2,...,Pn}——P1等待P2持有的资源——P2等待P3——...——Pn等待P1持有的资源——形成闭环。
死锁预防——破坏四个条件
破坏互斥——将资源改为可共享——但许多资源本质上是互斥的(打印机一次只能打一张纸)无法真正共享。
破坏持有并等待——进程在开始执行前申请其全部资源——如果无法一次性获得所有资源则一个都不分配给它——这样进程不会等待额外资源。这一做法导致了严重的资源浪费——一个进程需要磁带机1小时但打印机只需要用1秒——但按此策略磁带机被占用整整1小时。
破坏不可剥夺——当进程申请新资源被拒时——主动释放已持有的资源——如果资源可被重新调度再分配。这增加了不必要的保存和恢复开销。
破坏环路等待——给所有资源类型编号——进程申请资源时必须按照编号升序申请(先申请编号小的、再申请编号大的)。这样——一个进程持有高编号资源时不可能再等低编号资源——循环等待的环路不可能形成。
死锁避免——银行家算法
银行家算法在实际分配之前模拟分配后的系统是否处于安全状态——如果不会导致死锁——才允许分配——否则让进程等待进程。
工作过程：系统有m种资源——每种资源总量已知——每个进程声明它的最大需求。分配请求时:
- 判断Request_i <= Need_i(不超过声明最大)
- 判断Request_i <= Available(系统目前有足量资源)
- 试探性分配——更新Available、Allocation、Need向量
- 执行安全性检查算法——Work = Available, Finish=false
- 找一个Finish=false且Need <= Work的进程——Work+=Allocation, Finish=true——重复直到所有Finish=true(安全)或找不到可满足的进程(不安全)。
- 如果安全——正式分配——否则撤销试探并让进程等待
银行家算法在现实中很少实现——因为它需要每个进程预先声明最大资源需求(通常不可知)。算法时间复杂度O(m×n²)——n个进程、m种资源——也是可观的开销。
死锁检测——等待图化简
如果系统不采取预防或避免——死锁是可能发生的。死锁检测定期扫描等待图(有向图——顶点是进程、边P→R→Q表示P等待Q持有的资源)。如果等待图中存在环——则检测到死锁。在多资源实例环境中——用化简资源分配图的算法：找到一个可满足全部资源要求的进程→释放其所有资源→从图中移除→重复。如果所有节点均可被消除(图可化简)——无死锁。否则不可化简的节点集合就是死锁进程集合。
Linux内核的lockdep工具在开发模式下主动追踪锁的获取顺序——在违反"锁顺序"时产生告警。这属于一种"运行时死锁检测"——但仅针对内核内部的spinlock/mutex锁——不针对用户态的信号量。
处理死锁的策略总结
| 策略 | 描述 | 代价 | 适用场景 |
|---|---|---|---|
| 预防 | 破坏四个必要条件之一 | 资源利用率低 | 嵌入式系统、简单OS |
| 避免 | 银行家算法仔细安全分配 | 需要先验需求知识 | 实时系统(有限固定进程) |
| 检测+恢复 | 定时检测等待图→回滚事务 | 死锁进程影响大 | 数据库InnoDB |
| 鸵鸟 | 假装不存在 | 最低 | 通用操作系统Windows/Linux |
主流操作系统通用(鸵鸟)策略：死锁发生频率极低——一个很少发生的问题侦测算法的CPU开销(每次锁分配都检查环路)成本太高。当系统死锁时罕见到用户一般选择重启而不是拔掉网线——所以在通用OS中不部署复杂的死锁处理是完全合理的。
复习检查
死锁的四个必要条件缺一不可——如果"不可剥夺"不成立(OS可以从进程夺走资源)但其他三个条件成立——系统还会死锁吗？
银行家算法中"安全状态"与"不安全状态"的区别是什么？不安全状态是否必然导致死锁？
一种破坏环路等待的通用方法是对所有资源进行全局编号——进程必须按递增顺序申请资源——这种措施的合理性由什么来保证？
教材编写中死锁预防的例子——分配所有资源后才执行的严重资源浪费实际为什么在大多数通用系统不可用？
数据库事务为什么比操作系统更倾向于使用死锁检测而不是鸵鸟策略——事务能够回滚(undo)这一特性与OS进程无法整体回滚有什么不同？