考点频率★★★★★死锁预防考概念银行家算法是计算题常客难度⭐⭐⭐建议掌握四种死锁预防方法及其对应的破坏条件理解银行家算法的数据结构与安全序列判断1️⃣ 回顾死锁的必要条件上一篇文章提到死锁必须同时满足四个条件互斥资源一次只能给一个进程使用。持有并等待进程占着已有的资源同时等待新的资源。不可抢占进程已获得的资源只能自己释放不能被强行剥夺。循环等待多个进程形成一个首尾相接的资源等待环。处理死锁有三种策略预防破坏条件、避免分配前检查安全、检测与恢复事后处理。今天重点讲前两种。2️⃣ 死锁预防破坏必要条件预防的思想很简单既然四个条件必须同时满足才能死锁那就主动破坏其中至少一个条件。必要条件破坏方法思路缺点互斥尽量让资源可共享如只读文件改造资源属性大多数硬件资源如打印机无法共享难以实现持有并等待进程一次性申请所有资源要么全给要么一个不给资源利用率低可能发生饥饿某个进程长期申请不到全量资源不可抢占允许强行剥夺资源进程申请新资源被拒时必须释放已有资源实现复杂适用于状态易保存的资源如CPU不适用于打印机这种循环等待资源有序分配给资源编号必须按编号顺序申请按统一顺序申请避免环编号需要合理规划实际使用中可能不够灵活软考常考给定一个场景问“该措施破坏了死锁的哪个条件”——找出措施对应的破坏对象即可快速作答。3️⃣ 死锁避免银行家算法预防是“硬性规定”比较粗暴。避免则是“动态判断”——每次分配资源前先模拟分配看看系统是否会进入不安全状态如果会就暂不分配让进程等待。3.1 安全状态与不安全状态安全状态系统能按某种顺序为所有进程分配所需资源使它们都能顺利完成。这种顺序称为安全序列。不安全状态不存在这样的分配顺序。系统进入不安全状态后有可能发展为死锁。注意不安全状态 ≠ 死锁。不安全状态是“可能发生死锁”的危险区银行家算法的目标就是避免进入不安全状态。3.2 银行家算法的数据结构以nnn个进程、mmm类资源为例数据结构含义示例Available长度为mmm当前系统中各类资源的可用数量Available (2, 1)表示资源A剩2个资源B剩1个Maxn×mn \times mn×m矩阵每个进程对各类资源的最大需求量Max[P1] (3, 2)表示P1最多需要A资源3个、B资源2个Allocationn×mn \times mn×m矩阵每个进程已经获得的各类资源数量Allocation[P1] (1, 0)表示P1已获得A资源1个Needn×mn \times mn×m矩阵每个进程尚需的各类资源数量Need Max - AllocationNeed[P1] (2, 2)表示P1还需要A资源2个、B资源2个3.3 安全性检查算法寻找安全序列这是银行家算法的核心判断流程后续请求分配时都要调用它。设置两个向量Work Available当前可用资源Finish false所有进程初始标记为未完成。寻找一个进程PiP_iPi​满足Finish[i] falseNeed[i] Work即当前可用资源能满足该进程的剩余需求若找到则假设该进程运行完毕释放它所占用的资源Work Work Allocation[i]Finish[i] true记录PiP_iPi​到安全序列。重复步骤2-3。若所有进程的Finish都为true则系统处于安全状态否则为不安全状态。3.4 银行家算法的请求处理流程当进程PiP_iPi​发出资源请求Request_i长度为mmm的向量时操作系统按以下步骤处理合法性检查如果Request_i Need[i]则报错进程申请的量超过了它宣称的最大值。可用性检查如果Request_i Available则进程需等待当前资源不够。试分配先假装把资源分给进程Available Available - Request_iAllocation[i] Allocation[i] Request_iNeed[i] Need[i] - Request_i安全性检查执行 3.3 节的算法。如果系统处于安全状态则正式分配否则撤销试分配让进程等待。试分配 回滚 是银行家算法的精髓宁可现在不让它通过也不冒险进入不安全状态。4️⃣ 死锁预防 vs 死锁避免对比项死锁预防死锁避免银行家算法时机系统设计时静态约束运行时动态判断手段破坏四个必要条件之一分配前检查是否安全资源利用率较低一次性分配或限制顺序较高按需分配实现复杂度简单较复杂需维护矩阵、运行安全性检查适用场景小型嵌入式系统、资源可预知的场景资源可动态申请的系统如银行、数据库对进程的要求无特殊要求进程必须预先声明最大需求Max5️⃣ 经典例题例题1死锁预防某系统规定进程必须一次性申请所有需要的资源只有全部资源都可用时才分配。该措施破坏了死锁的哪个必要条件A. 互斥B. 持有并等待C. 不可抢占D. 循环等待解析一次性申请所有资源要么全给要么全不给。进程在等待时不会持有任何资源因此破坏了“持有并等待”条件。选B。例题2银行家算法-安全序列判断某系统有 3 个进程 P1、P2、P3两类资源 A、B总数分别为(5, 3)。当前分配情况如下进程AllocationMaxP1(1, 0)(3, 2)P2(2, 1)(4, 2)P3(0, 1)(2, 1)求当前系统是否存在安全序列。解计算 NeedNeed[P1] (3,2) - (1,0) (2,2)Need[P2] (4,2) - (2,1) (2,1)Need[P3] (2,1) - (0,1) (2,0)计算 Available已分配总量Allocation_Total (120, 011) (3, 2)Available (5,3) - (3,2) (2,1)执行安全性检查Work (2,1)。寻找Need[i] Work的进程。P1:Need(2,2) (2,1)不满足第二个数 2 1。P2:Need(2,1) (2,1)满足。将 P2 加入安全序列Work (2,1) Allocation[P2](2,1) (4,2)标记 P2 完成。继续找P1:Need(2,2) (4,2)满足。将 P1 加入Work (4,2) (1,0) (5,2)。P3:Need(2,0) (5,2)满足。将 P3 加入。所有进程完成。安全序列为P2 → P1 → P3。答案存在安全序列P2 → P1 → P3系统处于安全状态。6️⃣ 记忆口诀预防死锁破四因一次申请或排序。避免死锁银行家分配之前先检查。Available 看余量Need 等于 Max 减 Allocation。找到 Need 小于 Work完成释放 Work 加。7️⃣ 小测验评论区对答案在上题中若 P3 此时发出请求Request (1, 0)银行家算法是否应分配给 P3提示先检查 Request Need[P3] 和 Request Available然后试分配再判断安全性。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #死锁预防 #银行家算法 #死锁避免 #操作系统