文章声明：转载来源：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）饥饿（在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品）