死锁的预防、检测与解除
在上一文中，我们对死锁的定义、危害，产生死锁的四个必要条件，和处理死锁的四种方法来进行细致的讨论，但是由于篇幅问题，没来得及详细讨论，今天，我们来一起详细的研究如何处理死锁。
本文主要讨论死锁的预防，如何检测死锁和解除死锁；对于避免死锁，涉及到一个重点----银行家算法，因此会有一篇文章单独讨论。
1.预防死锁
预防死锁是通过破坏产生死锁的四个必要条件中的一个或几个，以避免发生死锁。由于互斥条件是临界资源所必须的，不仅不能改变，还应加以保证，因此主要是破坏产生死锁的后三个条件，即请求和保持、不可抢占与循环等待。
不过随着技术的发展，互斥条件也是可以加以“破坏”的，比如Spooling系统（假脱机），将独占设备改造为共享设备，例如实现共享打印机系统。
1.破坏请求和保持条件：为了能破坏请求和保持条件，OS必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源。实现方式有两种协议：第一种协议：所有进程在开始运行之前，必须一次性的申请其在整个运行过程中所需的全部资源（And型信号量）；第二种协议：允许进程只获得初期所需的资源后，便可开始执行，进程在运行过程中在逐步释放已分配给自己的、且已经使用完毕的全部资源，然后在请求所需的新的资源。
两种协议明显的第二种的效率要更高一些，因为可以让进程的并发性更高，因为少量的资源就可以保证进程线运行起来，这个思想有点暗合虚拟存储器的思想，这个我们后面再提。
2.破坏不可抢占条件：当一个已经保持了某些不可抢占资源的进程，提出新的请求而不能得到满足时，他必须释放已经保持的所有资源，待以后再全部重新申请。
该方法实现起来较为复杂，且会付出很大的代价，因为一个未使用完毕的不可抢占资源，释放之后可能会导致前一阶段所有的工作的失效（在这个时间断内，不可抢占资源有可能被两个进程访问，数据的一致性无法保证，有点像分布式下数据一致性）；这种策略还需导致进程反复的申请、释放资源致使进程的执行被无限地推迟，这不仅延长了周转时间，还增加了系统开销，降低了系统吞吐量。
3.破坏循环等待条件：通过对系统中的所有资源进行线性排序，并赋予不同的序号。当新申请的资源的序号大于之前持有资源的序号，才可以申请新资源。
2.死锁的检测
在某些系统中，为了追求系统更高的并发性和资源利用率，其对死锁问题采取“鸵鸟策略”，既不采取死锁预防措施，也未配有死锁避免算法。在这种情况下，就需要系统配有死锁检测算法和死锁解除算法，可以保证系统中发生死锁也不会无限的等待下去，即死锁定义中所说的外力，可以打破死锁的僵局。
死锁检测算法的实现，需要OS中保存有关资源的请求和分配信息，然后通过检测算法来判断系统是是否发生死锁。
2.1 资源分配图
我们可以使用有向图来描述资源分配情况，该图是由一组节点N和一组边E所组成的。其中N由两个互斥的子集组成，分别是进程节点P={p1,p2,…,pn}和资源节点P={p1,p2,…,pn}，N=P∪R。对于集合E中的一个遍e∈E，都连接着P中的一个节点和R中的一个节点，因为是有向图，所以如果e=<pi,rj>，则是资源请求边，由进程pi指向资源rj，表示进程pi申请一个单位的资源rj；如果e=<rj,pi>，则是资源分配边，由资源rj指向进程pi，表示资源rj已经分配给进程pi。
一个资源分配图如下如图所示，P={p1,p2}，R={r1,r2}，N=P∪R={p1,p2}∪{r1,r2}，E={<p1,r2>,<r2,p2>,<p2,r1>,<r1,p2>,<r1,p1>}.
使用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源，请求边是由进程指向方框中资源，分配边起始于方框中的一个点。上图中，我们可以看到，进程p1已经获取两个r1资源，并有申请一个r2资源；进程p2已经或得一个r1资源和一个r2资源，并又请求r1资源。
2.2 死锁检测方法
我们可以利用资源分配图加简化方法来检测系统处于此状态S时是否为死锁状态。简化方法如下：
- 在资源分配图中，找出一个既不阻塞又非独立的进程节点pi。因为pi进程没有阻塞，且占有着资源（非独立节点），当其顺利执行完毕后，就可释放其所占有的全部资源，这相当于消除pi请求的边和分配的边，将其变为孤立节点。
- 某进程释放资源后，就可满足别的进程获得资源而继续运行；
- 在进行一系列的化简后，如果所有的边都可以被消除，即资源分配图可以完全简化，则证明当前状态没有产生死锁；若无法完全简化，则说明发生了死锁。
这里涉及到一个死锁定理：S为死锁状态的充分条件是：当且仅当前状态S的资源分配图是不可完全简化的。可能部分同学觉得这里应该是充要条件，两者应该是可以相互推断的。这里，我在另一篇博客中详细的讨论了这个问题，大家可以移步看下，篇幅有限，就不在本文展开。
上图为一个资源分配图简化的一个例子，首先P1进程为一个既不阻塞又非独立的进程节点，其可以运行完毕，且会释放资源，即可以消除两条资源分配边和一条资源申请边。资源释放后，进程P2也可以申请到资源得以运行，最终也可释放资源，一样可以消除边。最终资源分配图中的所有边都被简化，所以此状态没有发生死锁。
下面给出一个回发生死锁的例子，读者可以自行看下:
3.死锁的解除
如果死锁检测算法检测到死锁，则就应采取相应的措施，以解除死锁。常采用的解除死锁的方法为两种：
- 抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以接触死锁状态；
- 终止（或撤销）进程，终止系统中的一个或多个死锁进程，直至大批循环环路，是系统从死锁状态中出来。
其实在我们使用电脑的过程中，也是会遭遇死锁的，比如word无响应，电脑死机，某文件被进程占用无法打开等等，其实都和死锁有些关系，我们大多数的解决方法也都是关闭程序，杀死进程或是重启了，这也是为啥重启能解决99%的“新手”问题，因为资源被全部重新分配，所有的进程都是重新开始竞争资源。
又到了分隔线以下，本文到此就结束了，本文内容全部都是由博主自己进行整理并结合自身的理解进行总结，如果有什么错误，还请批评指正。
如有兴趣，还可以查看我的其他几篇博客，都是OS的干货，喜欢的话还请点赞、评论加关注_。
转载：https://blog.csdn.net/qq_34666857/article/details/104117321