考点频率★★★☆☆选择题常考下午题偶尔结合资源分配图考查难度⭐⭐⭐建议掌握资源分配图的简化方法理解死锁恢复的两种策略及适用场景1️⃣ 回顾死锁处理的四种策略整个死锁处理策略可以分为四个层次前两篇已经讲了预防和避免策略时机核心思想预防系统设计时破坏四个必要条件之一避免银行家算法分配时每次分配前检查是否安全检测运行中定期检查是否存在死锁恢复死锁发生后解除死锁让系统继续运行本篇聚焦于后两个策略检测和恢复。2️⃣ 死锁检测2.1 检测的时机定时检测系统每隔一段时间如每10分钟运行一次死锁检测算法事件触发当进程等待超时或资源请求被阻塞时触发检测2.2 核心工具资源分配图资源分配图是一种有向图用于描述进程与资源之间的占用和等待关系是死锁检测的核心工具。节点矩形表示资源类型圆圈内数字表示资源数量圆形表示进程边资源 → 进程分配边表示该资源已被分配给该进程进程 → 资源请求边表示该进程正在请求该资源2.3 资源分配图的简化判断是否死锁简化步骤在资源分配图中找出一个既不阻塞又非孤立的进程结点该进程所请求的所有资源都能被满足请求边能全部变为分配边如果存在这样的进程则它可以运行完毕并释放所有资源释放该进程占用的所有资源删除该进程的所有边重复步骤1-2直到所有进程都能被简化删除无死锁或剩余进程无法简化有死锁判定结论如果资源分配图可以完全简化所有进程都被删除→ 无死锁如果资源分配图中存在环路且无法简化→ 有死锁环路中的进程就是死锁进程2.4 单资源 vs 多资源实例资源类型环路与死锁的关系说明每类资源只有1个实例环路 ⇔ 死锁有环必死锁等价关系每类资源有多个实例环路 ≠ 死锁有环不一定死锁可能通过其他实例满足软考常考画出资源分配图要求判断是否发生死锁并说明理由。3️⃣ 死锁恢复检测到死锁后系统需要采取措施解除死锁让进程继续运行。3.1 恢复策略一终止进程最常用强制终止一个或多个死锁进程回收其占用的资源。终止策略的选择终止所有死锁进程简单粗暴但代价大逐个终止每次终止一个进程释放资源后重新检测直到死锁解除选择终止哪个进程的依据考虑因素说明进程优先级先终止优先级低的已执行时间先终止运行时间短的损失小占用资源数量先终止占用资源多的释放资源多剩余执行时间先终止剩余时间长的进程类型交互式进程优先于批处理进程3.2 恢复策略二资源抢占从死锁进程中强行剥夺部分资源分配给其他进程打破循环等待。资源抢占的三个问题选择被抢占的资源通常选择代价最小的资源如CPU寄存器状态比打印机缓冲区更容易保存被抢占进程的回滚必须将进程回滚到某个安全状态如检查点防止饥饿同一个进程不能被反复抢占否则永远无法完成3.3 两种恢复策略的对比对比项终止进程资源抢占实现复杂度简单复杂需回滚机制恢复速度快较慢损失终止进程的全部工作丢失仅丢失部分工作可回滚适用场景批处理系统、对实时性要求高的系统交互式系统、事务型系统如数据库4️⃣ 死锁、饥饿、活锁的对比这是软考中容易混淆的三个概念对比项死锁饥饿活锁定义多个进程互相等待对方占有的资源某个进程长期得不到所需资源进程不断改变状态但始终无法推进进程状态所有相关进程阻塞被饿死的进程阻塞其他进程可能正常运行进程在运行非阻塞但没有实质性进展能否自行解除不能需要外部干预如果调度策略改变如优先级老化可能自行解除可能自行解除如果冲突碰巧解决典型场景A等BB等A低优先级任务永远等不到CPU两个进程在走廊里互相让路但总是让到同一侧永远过不去资源占用每个进程都占有一些资源被饿死的进程可能没有资源一直在等待进程可能在占用资源但无法推进区分要点死锁是“大家都在等”饥饿是“你一个人在等”活锁是“大家都在动但没人前进”。5️⃣ 经典例题例题1某系统资源分配图如下资源R1有1个实例被P1占用P2正在请求R1资源R2有1个实例被P2占用P1正在请求R2问系统是否发生死锁解析分配边R1→P1R2→P2请求边P1→R2P2→R1形成环路P1 → R2 → P2 → R1 → P1每个资源都是单实例环路上的进程无法继续推进答案发生了死锁死锁进程为P1和P2。例题2下列关于死锁检测和恢复的叙述中正确的是 。A. 资源分配图中存在环路则系统一定发生死锁B. 死锁检测只能在系统死锁后才能进行C. 终止所有死锁进程是常用的死锁恢复方法D. 资源抢占策略不需要进程回滚解析A错误多实例资源场景下存在环路不一定死锁B错误检测可以定期运行不一定要等到系统完全卡死C正确终止进程是最常用的恢复策略D错误资源抢占通常需要进程回滚答案C例题3活锁辨析两个进程P1和P2共享两个资源R1和R2它们都在不断尝试获取两个资源每次拿到一个后发现另一个被占用就释放已拿到的资源如此反复。这种情况属于 。A. 死锁B. 饥饿C. 活锁D. 互斥解析进程没有阻塞每次尝试都在运行但始终无法取得两个资源完成工作属于活锁。选C。6️⃣ 记忆口诀死锁检测看资源图简化删除找路径。全部删除算安全剩环说明已死锁。恢复终止或抢占终止简单回滚难。死锁活锁与饥饿三者区分要记全。7️⃣ 小测验评论区对答案某系统有3个进程P1、P2、P3资源R1和R2各有1个实例。当前分配R1被P1占用R2被P2占用。P1请求R2P2请求R1P3正在运行且不请求任何资源。问当前系统是否发生了死锁如果死锁发生死锁进程是哪些本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅第一时间接收新内容#软考中级 #软件设计师 #死锁检测 #死锁恢复 #资源分配图 #操作系统
)
