文章声明:转载来源:https://blog.csdn.net/qq_27225851/article/details/51752988
本文是对操作系统概念(第七版)——死锁的学习总结,不足之处,欢迎批评指正。
本文讨论的两块内容是死锁检测和死锁恢复。
1、死锁检测
首先针对每种资源类型只有一个实例的情况。
该算法使用资源分配图的一个变种,称为等待图。
从资源分配图中,删除所有资源类型的节点,合并合适边,就可以得到等待图。
合并的过程如下:如果pi指向资源rj,而rj右指向pk,那么删除节点rj之后,直接得到pi->pk这样的结果。当前仅当等待图中有一个环,系统中存在死锁。检测环的算法复杂度为o(n^2)
第二种情况是每种资源类型还有多个实例的情况。
这种算法和银行家算法是类似的。具体内容见上篇文章的银行家算法。不同的是在第(4)步:
如果对某个i,finish[i]=false,那么说明系统处于死锁状态,且进程i死锁,时间复杂度为o(m*n^2)。
2、死锁恢复
打破死锁有两种方法:
(1)简单地终止一个或多个进程以打破循环等待。——进程终止
(2)从一个或多个死锁进程那里抢占一个或多个资源。——资源抢占
进程终止有以下两中方法:
(i)终止所有死锁进程。
(II)一次只终止一个进程直到取消死锁循环为止。
如果选择资源抢占,那么将必须考虑三个问题:
(i)选择一个牺牲品
(II)回滚
(III)饥饿(在代价因素中加上回滚次数,回滚的越多则越不可能继续被作为牺牲品)
看完解析才知道应该是这样的思路
大佬,能转载下吗?
简单易懂,很容易理解,谢谢