王道操作系统笔记视频链接2.4.4 死锁的处理策略—检测和解除知识总览死锁的处理不允许死锁发生静态策略预防死锁动态策略避免死锁允许死锁发生死锁的检测和解除本节内容死锁的检测死锁的解除如果系统中既不采取预防死锁的措施也不采取避免死锁的措施系统就很可能发生死锁。在这种情况下系统应当提供两个算法①死锁检测算法用于检测系统状态以确定系统中是否发生了死锁。②死锁解除算法当认定系统中已经发生了死锁利用该算法可将系统从死锁状态中解脱出来。死锁的检测为了能对系统是否已发生了死锁进行检测必须①用某种数据结构来保存资源的请求和分配信息②提供一种算法利用上述信息来检测系统是否已进入死锁状态。数据结构——资源分配图两种结点进程结点对应一个进程资源结点对应一类资源一类资源可能有多个两种边进程结点→ \to→资源结点表示进程想申请几个资源每条边代表一个资源结点→ \to→进程结点表示已经为进程分配了几个资源每条边代表一个PS一般用矩形表示资源结点矩形中的小圆代表该类资源的数量。如图所示分析过程如果系统中剩余的可用资源数足够满足进程的需求那么这个进程暂时是不会阻塞的可以顺利地执行下去。如果这个进程执行结束了把资源归还系统就可能使某些正在等待资源的进程被激活并顺利地执行下去。相应的这些被激活的进程执行完了之后又会归还一些资源这样可能又会激活另外一些阻塞的进程……如果按上述过程分析最终能消除所有边就称这个图是可完全简化的。此时一定没有发生死锁相当于能找到一个安全序列比如第2点中的示例图按照P1、P2的顺序执行就是一个安全序列如果最终不能消除所有边那么此时就是发生了死锁一个新的例子由于R1和R2资源都被分配完毕所以P1、P2都会被阻塞只有P3运行P3运行完毕后返还一个R2资源由于P1申请两个所以资源数量不够于是P1、P2都无法继续运行发生了死锁如图所示最终还连着边的那些进程就是处于死锁状态的进程比如第4点中的例子在P3返还资源后的图如下此时P1、P2就是处于死锁状态的进程P3不是检测死锁的算法①在资源分配图中找出既不阻塞又不是孤点的进程 Pi 即找出一条有向边与它相连且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中R1没有空闲资源R2有一个空闲资源。若所有的连接该进程的边均满足上述条件则这个进程能继续运行直至完成然后释放它所占有的所有资源消去它所有的请求边和分配边使之称为孤立的结点。在下图中P1是满足这一条件的进程结点于是可以将P1的所有边消去。②进程 Pi 所释放的资源可以唤醒某些因等待这些资源而阻塞的进程原来的阻塞进程可能变为非阻塞进程。在下图中P2 就满足这样的条件。根据①中的方法进行一系列简化后若能消去途中所有的边则称该图是可完全简化的。图死锁定理如果某时刻系统的资源分配图是不可完全简化的那么此时系统死锁。PS可自行搜索该定理的证明过程死锁的解除一旦检测出死锁的发生就应该立即解除死锁。并不是系统中所有的进程都是死锁状态用死锁检测算法化简资源分配图后还连着边的那些进程就是死锁进程解除死锁的主要方法有①资源剥夺法挂起暂时放到外存上某些死锁进程并抢占它的资源将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。②撤销进程法或称终止进程法强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。这种方式的优点是实现简单但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间已经接近结束了一旦被终止可谓功亏一篑以后还得从头再来。③进程回退法让一个或多个死锁进程回退到足以避免死锁的地步。比如之前死锁的检测中第五点的例子让P1回退到只拥有一个R1的情况此时就可以空出一个R1给P2用这就要求系统要记录进程的历史信息设置还原点。所以也不太容易实现如何决定“对谁动手”进程优先级优先级越低撤销代价越小已执行多长时间执行时间越长代表撤销代价越大还要多久能完成需要时间越短返还资源速度越快进程已经使用了多少资源使用资源越多撤销后返还的资源越多进程是交互式的还是批处理式的交互式实时性强撤销会严重破坏用户体验批处理式实时性弱撤销代价相对交互性小知识回顾与重要考点考试中常考的是死锁检测的部分需要理解资源分配图的两种结点和边着重理解并记住死锁检测算法一句话就是“依次消除与不阻塞进程相连的边直到无边可消”题中一般会给出资源分配图。不过也要小心与数据结构结合考察。死锁的解除一般只会在选择题进行考察稍微有个印象即可。