南昌建设医院网站,做仿牌网站,网站建设方案书原件,建设银行网站的目的是什么意思文章目录 2.4_4 死锁的检测和解除#xff08;一#xff09;死锁的检测#xff08;二#xff09;死锁的解除 总结 2.4_4 死锁的检测和解除 如果系统中既不采取预防死锁的措施#xff0c;也不采取避免死锁的措施#xff0c;系统就很可能发生死锁。在这种情况下#xff0c;… 文章目录 2.4_4 死锁的检测和解除一死锁的检测二死锁的解除 总结 2.4_4 死锁的检测和解除 如果系统中既不采取预防死锁的措施也不采取避免死锁的措施系统就很可能发生死锁。在这种情况下系统应当提供两个算法 1.死锁检测算法用于检测系统状态以确定系统中是否发生了死锁。 2.死锁解除算法当认定系统中已经发生了死锁利用该算法可将系统从死锁状态中解脱出来。
一死锁的检测 为了能对系统是否已发生了死锁进行检测必须 1.用某种数据结构来保存资源的请求和分配信息 2.提供一种算法利用上述信息来检测系统是否已进入死锁状态。 注如果学习过数据结构中的“图”则可以尝试着具体定义一下这个数据结构。 如果系统中剩余的可用资源数足够满足进程的需求那么这个进程暂时是不会阻塞的可以顺利地执行下去。 例如上图中的进程P1它申请了1个R2资源此外R2资源此时分配了1个给P2进程。所以P1进程对于R2资源的请求是可以被满足的不会被阻塞可以顺利执行下去。 但是对于P2进程请求R1来说由于此时R1资源已经分配出去了2个给P1、1个给P2那么P2对于R1资源再次的请求1个就无法被满足。 如果这个进程执行结束了把资源归还系统就可能使某些正在等待资源的进程被激活并顺利地执行下去。 刚才说了P1对于R2资源的请求是可以顺利执行的。那么等到P1执行完毕就会归还它所使用的资源。 注某个进程在进行请求资源、使用完毕、归还资源之后该进程所对应的“请求边”、“分配边”就可以从图中删去如下图所示。 刚刚我们说了P2对于R1资源的请求是无法满足、阻塞的。然而当此时P1归还系统资源后R1资源的数量又足够满足P2了因此P2就会被唤醒并正常执行。 同理等P2执行完之后它也会归还所有的资源。所以我们也可以把P2相连的边全部删去如下图所示。 如果按上述过程分析最终能消除所有边就称这个图是可完全简化的。此时一定没有发生死锁相当于能找到一个安全序列。 其本质其实和上一小节银行家算法的过程是一致的。我们经过比对发现P1能够满足于是把P1加入安全序列让P1执行执行完毕归还资源。归还资源后我们再次经过比对发现P2能够满足于是把P2加入安全序列让P2执行…… 如果最终不能消除所有边那么此时就是发生了死锁。 最终还连着边的那些进程就是处于死锁状态的进程。 例子 如图。此时可以顺利执行的只有P3进程。当P3执行完毕之后归还资源。 此时可以发现P1想要申请R2资源但无法满足因此P1会被阻塞P2想要申请R1资源但无法满足因此P2也会被阻塞。 我们无法消除这些边系统发生了死锁。 检测死锁的算法 1.在资源分配图中找出既不阻塞又不是孤点的进程Pi。消去它所有的请求边和分配边使之成为孤立的结点。在下图中P1是满足条件的进程结点于是将P1的所有边消去。 “不阻塞”的意思是这个进程申请的资源数量足够满足它的需求比如像P1进程就是不阻塞的进程而P2进程就是阻塞的进程。 “孤点”的意思是这个图中没有任何边与这个结点相连则这个结点就是孤点。下图中P1、P2此时都不是孤点。 因此此时满足“既不阻塞、又不是孤点”的进程就是P1进程。 2.进程Pi所释放的资源可以唤醒某些因等待这些资源而阻塞的进程原来的阻塞进程可能变为非阻塞进程。在下图中P2就满足这样的条件。同理依旧按照“1”中的处理逻辑对其进行简化。 按照第1步中的逻辑进行同样的操作。在下图中“既不阻塞、又不是孤点”的进程就是P2我们消去它所有的请求边和分配边即可。 最终若能消去图中所有的边则称该图是可完全简化的。 死锁定理如果某时刻系统的资源分配图是不可完全简化的那么此时系统死锁。 至此我们已经解决了第一步问题——我们已经可以有办法检测出“系统是否发生了死锁”。 接下来我们就可以想办法——“怎么解除死锁”。 二死锁的解除 一旦检测出死锁的发生就应该立即解除死锁。 注意系统中有死锁的发生并不代表着系统中所有的进程都是死锁状态。我们在用死锁检测算法化简资源分配图后还连着边的那些进程就是死锁进程。 解除死锁的主要方法 1.资源剥夺法 挂起即暂时放到外存上某些死锁进程并抢占它的资源将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。 注意既然“挂起某些死锁进程”那么我们要挂起的进程就不能是非死锁进程。如下图此时P1、P2处于死锁而P3并不是死锁。因此我们就不能挂起P3而只能挂起P1或者P2。 2.撤销进程法或称终止进程法 强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。这种方式的优点是实现简单但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间已经接近结束了一旦被终止可谓是功亏一篑以后还得从头再来。 3.进程回退法 让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息设置还原点。 如上图中对于P1进程我们可以让它回退到“P1只持有1个R1资源”的时候。回退到此便能够保证P2进程顺利执行下去从而解决死锁问题。 思考如何决定“对谁动手” 即无论使用上述三种方法中的哪一种总之我们要对哪个死锁进程下手或者说让哪个进程做出牺牲——剥夺它的资源 / 终止它 / 回退它。 可以从以下这些角度来做出考虑。 1.进程优先级。 优先级低的我们可以对它下手。 2.已执行多长时间。 执行时间越长说明对它下手所付出的代价可能会更大。所以我们可以选择“已执行时间”更短的进程。 3.还要多久能完成。 对于“马上就能完成了”的资源我们可以保证它的继续运行转而去牺牲别的进程。 4.进程已经使用了多少资源。 如果一个进程已经拥有了很多资源的话那么我们把它剥夺就会释放出很多资源从而让原本死锁的局面最大程度地得到缓解。因此我们可以对“此时拥有资源最多”的进程下手。 5.进程是交互式的还是批处理式的。 “交互式”就意味着这个进程当前是正在与用户进行交互的。如果对交互式进程下手把它干掉的话那么用户体验就会变差。 而对于批处理式的进程它只是计算机自身在进行一系列的处理而用户对它的反馈并不那么在意。所以我们可以优先对“批处理进程”下手。 总结
