244_死锁的处理策略—检测和解除
# 2.4_4_死锁的处理策略—检测和解除
各位同学大家好，在这个小节中我们会学习死锁处理的最后一种策略，死锁的检测和解除。
那么在之前的小节当中，我们学习了预防死锁和避免死锁这两种策略，这两种方式都不会允许死锁的发生。如果我们不采取这两种策略的话，系统当中就很有可能发生死锁，所以我们就需要设计一种算法，用来检测出此时系统当中是否发生死锁，并且还要设计一种算法，当我们发生发现已经有死锁发生的时候，需要把死锁想办法解除掉。
# 死锁的检测
所以我们先来看一下第一个死锁的检测要怎么实现。我们可以设置一个数据结构，用来保存系统资源的请求和分配信息，之后还再根据这个数据结构记录的信息，在设计一种算法，用来检测这个系统当中是否已经进入了死锁状态。
我们可以用一种叫做资源分配图的数据结构来保存系统当中的各种资源的情况。在这种图当中会有两种结点，第一种叫做进程结点，每一个结点对应一个进程，第二种叫做资源结点，一每一个结点对应一类资源，注意是一类资源
那么一般来说会用一个矩形来表示一类资源，矩形当中的这一些小圆就是表示这一类资源有几个，比如说在这个图当中 r2 这种资源就有两个，r1 这种资源有三个。
另外资源分配图当中有两种边，一种是进程结点指向资源结点的边，这种边又称作为请求边，就是用来表示一个进程对某一种资源的请求，每一条边对应的就是一个资源，所以在这个情况来看， p1 进程此时正在请求被分配一个 r2 资源。p2 进程此时正在被正在请求分配一个 r1 资源
另外还有资源结点指向进程结点的边，这种边又称作分配边，表示这种资源已经给各个进程分配了几个。同样的每一条边也对应一个资源，比如说现在这个系统当中已经给 p1 进程分配了两个 r1 资源，给 p2 进程分配了一个 r1 资源，而 r2 资源只给 P2 分配了一个。学习过数据结构的同学可以动手试一下，要怎么定义出这样一个图的数据结构。
那么接下来既然有了数据结构，我们再来考虑一下怎么基于这种数据结构来分析系统此时是否处于死锁状态，我们可以这么考虑，如果说系统当中剩余的可用资源数足够满足进程的需求进程的请求的话，那么理论上进程就不应该被阻塞，它可以顺利的执行下去。
比如说像图中 p1 进程，他请求一个单位的 r2 资源，而 r2 资源现在只被分配出去了，一个它的总数是两个，所以 r2 资源现在剩余空闲的还有一个，所以 p1 进程的这种请求是可以被满足的，所以 p1 进程应该不会被阻塞，它可以顺利的执行下去
但是 p2 进程此时请求一个单位的 r1 资源，而由于 r1 资源此时已经分配出去了三个，所以 r1 资源已经没有空闲的，因此 p2 进程的请求不能被满足
而 p1 进程既然可以顺利的执行下去的话，那么等 p1 进程顺利的执行完了，他就可以把自己现在手里的资源全部归还给系统，并且等 P1 结束之后，他应该也不会再请求使用任何一种资源。
所以假设现在 p1 顺利的执行结束了，那么我们就可以把和 p1 相连的所有的这些边全部干掉，就像这样子。
p1 把 r1 资源归还之后，现在 r1 资源空闲的还有两个，而 p2 只需要一个，所以 p2 进程的请求接下来也可以被满足，所以 p2 本来是阻塞的，现在 p2 就可以被唤醒，然后正常的执行下去，等 p2 执行完了之后，他也会归还所有的这些资源，并且会并且不会再对任何一种资源提出请求，所以我们接下来也可以把 p2 相连的这些边全部干掉。
那么当 p2 归还了这些系统资源之后，也有可能会有别的进程被唤醒，只不过在这个图当中只有两个进程，所以到这步为止，我们就可以认为这些进程实际上是可以顺利的依次执行结束的。因此如果我们按照刚才所说的这一系列方法，能够消除所有的这些相连的边的话，那么我们就称资源分配图是可完全简化的，那么既然可完全简化，就意味着此时并没有死锁发生。
我们还可以从另外一个角度来考虑，其实刚才我们分析的过程相当于找到了一个安全序列，优先的把资源分配给 p1，那么 p1 可以执行结束，等 p1 执行结束之后，p2 也可以执行结束。所以如果按 p1，p2 这样的序列来依次执行的话，那么所有的进程是都可以顺利的执行结束的。这就和上一小节介绍的安全序列其实是一种原理，那么既然我们能够找到一个安全序列，就说明此时系统是处于安全状态的，既然处于安全状态，就意味着此时系统肯定没有发生死锁。
相反的，如果我们不能把所有的边都消除的话，那么就说明此时系统已经发生了死锁。我们再来看一个不能消除所有边的情况，我们把刚才的资源分配图稍微的改一下，让 p1 申请两个 r2 资源，然后再增加一个持有 r2 资源的 p3 进程，还是用刚才的方法来分析。
P1 进程此时请求两个 r2 资源，而 r2 资源已经全部分配出去了，没有空闲了，所以 p1 进程应该被阻塞。
而 p2 进程此时请求 r1 资源，r1 资源也全部分配出去了，也没有空闲的，所以 p2 进程也需要被阻塞。
此时可以顺利执行下去的只有 p3 进程，那么当 p3 执行结束之后，会归还他所拥有的全部资源。
接下来 r2 资源已经有一个空闲的，但是由于 p1 进程需要的是两个 r2 资源，所以此时 r2 这种资源的数量依然不够满足 p1 的需求，所以 p1 依然会被阻塞。 p2 进程也一样，此时没有空闲的 r1 资源，所以 p2 进程也会继续阻塞，所以我们就不能像刚才那样把 p1，p2 相连的这些边给干掉，那么到这一步为止我们就不能继续化解下去了。所以这种情况就是不能消除所有边的情况，这种情况下系统就发生了死锁。
大家可以结合这个图来分析一下，此时是否满足此所发生的 4 个必要条件。
如果我们不能消除所有的边的话，最终还连着一些边的那些进程，就是处于死锁状态的进程。 像刚才的 p3 进程可以把与它相连的所有边都干掉，所以 p3 进程并不是死锁状态，只有 p1 和 p2 是死锁状态的进程，这就是死锁检测的一个思想
那么我们用刚才的这种方式理解了它的原理之后，课本上的这一段描述就应该更容易理解了。我们需要在资源分配图当中找到一个既不阻塞又不是孤点的进程 pi，不阻塞的意思是说进程申请的这些资源的数量足够满足他的需求。比如说像 p1 进程就是不阻塞的进程，而 p2 进程申请的 r1 资源已经没有足够的剩余资源可以分配给他了，所以 p2 进程是一个阻塞的进程，
另外不是孤点，这个条件指的是与进程至少有一个边相连，那么 p1 和 p2 显然都不是孤点，所以在这个状态下，满足既不阻塞又不是孤点的进程，就只有 p1 进程。接下来我们可以消去他所有的请求边和分配边，也就是把和 P1 相连的所有的边都干掉，使之成为孤立的结点。
由于此时已经没有边和它相连了，所以此时 p1 就变成了之前所提到的所谓的孤点。
那么当 p1 释放了之前持有的资源之后，p2 进程就可以被唤醒，于是 p2 也变成了既不阻塞又不是孤点的进程。所以接下来我们就需要把 p2 相连的所有的这些边给干掉，那么由于我们可以用这种方式干掉所有的边，所以这个图是可完全简化的。因此此时系统并没有发生死锁现象。
如果这个图不可以完全简化的话，此时系统就发生了死锁，这就是著名的死锁定理。感兴趣的同学可以上网看，查一下文献他是怎么证明的。现在我们已经迈出了第一步，我们已经可以有办法检测出此时系统是否发生了死锁。接下来我们就要想办法怎么解除死锁
一旦检测出死锁的发生，就应该立即解除死锁。这儿需要补充的一点是，并不是系统中所有的进程都处于死锁状态，用死锁检测算法化简资源分配图之后，还连着边的那些进程就是死锁进程。比如说刚才提到这个例子，p3 就是没有死锁的，而 p1 和 p2 是处于死锁状态的进程
解除死锁有这样的几种方法
- 第一种叫做资源剥夺法，就是会暂时挂起某一些死锁进程，既然挂起的是死锁进程，那么就意味着我们此时不能把 p3 挂起，因为它不处于死锁状态，我们可以选择 p1 和 p2 之间的某一个进程把它暂时挂起，也就是暂时放到外存上，然后并且抢占他现在持有的这些资源，把这些资源分配给所需要的进程。但是同时我们也应该防止被挂起的进程，长时间得不到资源而导致饥饿的现象。
- 第二种方法叫做撤销进程法，或者叫终止进程法，就是可以强制的撤销部分，甚至是全部的死锁进程，并且剥夺这些进程的资源。但这种方式简单粗暴，但是需要付出的代价可能会很大，因为有的进程它有可能已经运行了很长时间了，已经接近结束了，但如果这个时候把它强行撤销的话，就意味着之前的那些工作全部白做，功亏一篑，之后还必须从头再来，所以撤销进程法的代价其实是很大的。
- 那第三种方法叫做进程回退法，可以选择一个或者多个死锁进程，让他们回退到足以避免死锁的地步。比如说我们可以让 P1 进程一直回退到他只持有一个 r1 资源的那个时候，这样的话就可以空出一个 r1 资源，先分配给 p2 进程，至少先保证 p2 进程时可以顺利的执行下去了。但是要实现这种所谓的进程，回退操作系统就需要记录这些进程的执行历史信息，设置还原点，所以进程回退法其实也不太容易实现
接下来我们再来考虑一下，我们可以用什么样的方式来决定到底要让哪一个进程做出牺牲，比如剥夺他的资源或者直接把他干掉，或者让他回退，可以从这样一些角度来考虑，
- 进程优先级，当然进程优先级低的，我们可以对它下手
- 已执行时间。可以看这些进程到底执行了多长，时间执行时间越长，说明让他回退或者是把它撤销的话，我们付出的代价就会更大。毕竟之后还需要从头再来。所以我们可以选择执行时间更少的进程，让他做出牺牲
- 还需要时间。我们还可以考虑各个进程到底还有多久可以完成，那显然我们可以优先让马上就可以执行结束的那些进程，优先的获得资源，然后牺牲别的那些进程。
- 可以考虑进程已经使用了多少种资源，如果一个进程持有很多个资源的话，把进程撤销或把进程的资源给剥夺的话，那就意味着死锁的局面就可以被尽快的解除，所以我们可以优先把拥有更多资源的进程，先把让他做出牺牲
- 可以考虑这些进程是交互式的还是批处理式的。交互式的就意味着这些进程是在和用户交互的，如果把交互式的进程干掉的话，那么对用户肯定是极其不爽的。而对于批处理式的这些进程来说，它无非就是在做一些计算，用户对于这种类型的进程的及时反馈，其实并不是那么在意，所以我们可以优先牺牲批处理式的进程，那么这就是死锁解除的一些策略。
# 小结
这个小节我们介绍了死锁的检测和解除，考试当中比较容易常考的是死锁检测相关的部分，需要理解资源分配图的这两种结点和两种边分别是什么意义，另外更需要着重理解并记住死锁检测算法，其实我们可以用一种更精简的语言把死锁检测算法把它概括出来，其实无非就是依次消除与不阻塞进程相连的边，直到无边可消。而所谓不阻塞进程指的其实就是申请的资源数还足够的那些进程。所以我们其实可以用这样一句话，就把死锁检测算法整个给概括出来。
死锁检测算法相关的题一般来说是会直接画出资源分配图的，但是大家也要小心和数据结构结合考察，所以如果到后期时间充裕的话，也可以自己尝试动手实现一下，死锁检测算法其实也并不复杂，对于死锁的解除一般来说只会在选择题里进行考察，稍微有个印象就可以了。
