操作系统的第二篇翻死锁这座山。死锁在上午题里占 1~2 分考法高度固定四个必要条件概念、最少需要多少资源才不死锁套公式、银行家算法判断安全序列填表体力活。这篇挨个拆透顺便把资源分配图有环这个经典误会讲清楚。一、什么是死锁独木桥问题一条只容一车通过的独木桥两头各来一辆车开到桥中间相遇——谁也不肯退谁也过不去。双方都占着对方需要的东西都在等对方先放手于是永远僵住。这就是死锁两个或多个进程互相等待对方占有的资源结果所有进程都无法推进。二、四个必要条件缺一不可死锁要发生必须同时满足四个条件上午题直接考互斥资源一次只能一个进程用独木桥一次只能过一辆车占有且等待手里攥着资源不放同时伸手要新的车占着半座桥还要对方那半座不可剥夺资源不能被抢走只能等占用者主动释放谁也不能把对方推下桥循环等待形成你等我、我等他、他等你的环形等待链。四个条件缺一不可——所以预防死锁的思路就一句话随便破坏一个破坏谁怎么破坏备注占有且等待进程开工前一次性申请全部资源要不齐就不开工资源利用率低不可剥夺申请不到新资源时主动释放已占有的实现麻烦循环等待资源编号按序号递增申请最常用考点互斥基本破坏不了资源本性了解即可按序号递增申请为什么能破环你申请了 3 号资源就永远不许回头要 2 号——等待链只能朝编号大的方向延伸永远绕不回起点环无从形成。三、三种处理策略概念题的分层死锁预防事前立规矩破坏四条件之一静态、保守死锁避免资源分配前先算账确认这么分不会出事才分——银行家算法就属于避免高频考点问银行家算法属于哪类策略死锁检测与解除放任发生事后查账发现死锁再剥夺资源或撤销进程。记忆预防是不许你危险避免是危险来临前刹车检测是出了事再救。四、最少多少资源才不死锁一个公式经典题型n 个进程每个进程最多需要 k 个同类资源系统至少配多少个资源m才能保证不发生死锁m ≥ n × (k - 1) 1推导懂了就不用背想象最坏的情况——每个进程手里都捏着 k-1 个资源都只差 1 个就能完工。此时共被占住 n×(k-1) 个资源。只要系统里还剩 1 个富余这个资源无论给谁那个进程就凑够了 k 个跑完后把手里的 k 个全部释放连锁反应大家陆续解套。所以 n(k-1)1 个就稳了少一个就可能全员捏着 k-1 个干瞪眼——死锁。例3 个进程、每个最多要 4 台打印机 → 3×31 10 台。五、银行家算法安全序列是填出来的银行家算法回答一个问题当前这个分配方案下系统还安全吗存在至少一条让所有进程都能跑完的序列就安全。手里三张表已分配 Allocation、还需求 Need、系统可用 Available。检查步骤就两步循环找一个Need ≤ Available的进程它现在要的东西系统给得起假设它跑完Available 回收它的 AllocationAvailable Allocation回到第 1 步。所有进程都能排进序列 →安全卡住了 →不安全注意不安全 ≠ 已经死锁是可能死锁银行家因此拒绝分配。例题系统有 A、B 两类资源Available (1, 2)进程AllocationNeedP1(2, 0)(1, 2)P2(0, 1)(2, 1)先试 P1Need(1,2) ≤ Available(1,2) ✓ → 假设跑完Available (1,2)(2,0) (3,2)再看 P2Need(2,1) ≤ (3,2) ✓ → 跑完全部完成系统安全安全序列P1, P2。若先试 P2Need(2,1) ≤ (1,2)21 ✗此路不通。所以序列唯一P1→P2。考场上就是把这张表推演一遍零技巧纯体力。六、资源分配图有环 ≠ 死锁资源分配图里进程指向资源是请求资源指向进程是占有。有环不一定死锁每类资源只有一个实例有环 死锁独木桥场景资源有多个实例有环也可能解开环上某个进程的资源可能被环外的进程释放。这是软考爱挖的坑记住单实例有环必死锁多实例有环不一定。七、10 道练习题基础题1~51.死锁是指 。A. 进程被系统撤销 B. 多个进程互相等待对方占有的资源都无法推进 C. CPU 长时间空闲 D. 内存容量不足2.下列各项中不是死锁产生必要条件的是 。A. 互斥 B. 占有且等待 C. 可剥夺 D. 循环等待3.通过破坏四个必要条件之一来防止死锁发生的策略称为 。A. 死锁预防 B. 死锁避免 C. 死锁检测 D. 死锁解除4.银行家算法属于 。A. 死锁预防 B. 死锁检测 C. 死锁解除 D. 死锁避免5.给系统内所有资源编号规定进程只能按序号递增的顺序申请资源该方法破坏的是 。A. 互斥 B. 循环等待 C. 占有且等待 D. 不可剥夺进阶题6~10带坑6.系统中有 3 个进程每个进程最多需要 4 台同类资源如打印机系统至少配备 台才能保证不发生死锁。A. 12 B. 10 C. 9 D. 137.系统中有 5 个进程每个进程最多需要 3 个同类资源系统至少配备 个资源才能保证不发生死锁。A. 15 B. 10 C. 11 D. 68.某时刻系统可用资源 Available (1, 2)进程 P1 的 Allocation (2, 0)、Need (1, 2)P2 的 Allocation (0, 1)、Need (2, 1)则系统的安全序列是 。A. P2, P1 B. 两个序列都安全 C. P1, P2 D. 系统不安全9.关于资源分配图与死锁的关系下列说法正确的是 。A. 每类资源只有一个实例时图中有环则必发生死锁 B. 图中只要有环就必定发生死锁 C. 图中无环也可能发生死锁 D. 图中有环时撤销环上任意一个进程即可解除死锁10.关于死锁下列说法错误的是 。A. 四个必要条件必须同时满足才可能发生死锁 B. 银行家算法在分配资源前先检查系统是否仍处于安全状态 C. 破坏循环等待的常用方法是资源按序分配 D. 只要系统中存在循环等待就一定发生了死锁八、答案与详解1. B死锁的关键词互相等待、都无法推进。A、C、D 都是干扰跟循环等待资源无关。2. C四条件是互斥、占有且等待、不可剥夺、循环等待。选项把不可剥夺换成了可剥夺——恰恰相反能剥夺反而有助于破解死锁。3. A破坏四条件 预防事前立规矩。和避免的区别预防是静态设限避免是动态算账分配前查安全性。4. D高频考点银行家算法属于死锁避免——分配前先用安全性算法检查分完之后系统是否还有安全序列有则分无则拒。5. B按序递增申请等待链只能朝大编号延伸绕不回起点——破坏的正是循环等待。这是四种破坏法里软考唯一爱考的。6. B套公式 n(k-1)1 3×31 10 台。选 A123×4的是直接乘了需求量——那是人人同时拿满过度富裕不是至少选 C9的忘了1那临门一脚。7. Cn(k-1)1 5×21 11 个。再验一遍最坏情况5 个进程各捏 2 个共 10 个第 11 个无论给谁那人凑够 3 个跑完释放连锁解套 ✓。8. C填表推演P1 Need(1,2) ≤ Available(1,2) ✓跑完回收 → Available (3,2)P2 Need(2,1) ≤ (3,2) ✓。安全序列P1, P2。而先走 P2Need(2,1) ≤ (1,2) 不成立——所以序列唯一选 B 的没有真的动手算。9. A单实例资源 有环 必死锁多实例时有环不一定环外可能有人释放资源解套。B 错在只要……就C 错无环必无死锁D 想当然环上进程可能握着多份资源撤一个未必解环。10. D选错误的A、B、C 是正文原话。D 错——多实例资源存在循环等待时仍可能由环外进程释放资源而解开只有单实例场景下循环等待 死锁才成立。这是本篇前后呼应的同一个坑考的就是你是否真的消化了。九、五句话带走死锁 互相等待、谁也无法推进四条件缺一不可互斥、占有且等待、不可剥夺、循环等待预防 破坏其一银行家算法 死锁避免分配前先查安全序列不死锁资源数n(k-1)1安全序列找 Need ≤ Available → 回收 Allocation → 循环单实例有环必死锁多实例有环不一定。下一篇预告操作系统第三站——存储管理分页式存储的地址转换、FIFO 和 LRU 页面置换的缺页率怎么算。给了页面访问序列拿张纸画格子就能算分但 LRU 的格子画法和 FIFO 有本质不同错一步全错。