进程管理(十二)-死锁

什么是死锁

死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。

以生产者/消费者问题为例来看死锁的概念。

设生产者进程已获得对缓冲区队列的操作权，但此时缓冲队列内所有缓冲区都是满的，因此生产者进程进入等待状态。

消费者进程此时申请对缓冲队列操作的操作权。但由于生产者进程掌握缓冲队列的操作权且不会自动释放它，从而消费者进程也进入等待状态。
因而陷入死锁。

并发进程P1, P2, … , Pn，它们共享资源R1, R2, …, Rm（n>0，m>0，n>=m）。其中，每个Pi（1≤i≤n）拥有资源Rj（1 ≤j ≤m），直到不再有剩余资源。同时，各Pi又在不释放Rj 的前提下要求得到Rk（k≠j，1 ≤k≤m），从而造成资源的互相占有和互相等待。

在没有外力驱动的情况下，该组并发进程停止往前推进，陷入永久等待状态。

死锁的起因是并发进程的资源竞争。

产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。

需要适当的资源分配算法，以消除死锁

并发进程所要求和占有的资源不能同时被两个以上进程使用或操作，进程对需要的资源进行排他性控制。

不剥夺条件。进程获得的资源在未使用完毕之前，不能被其他进程强行剥夺，只能由获得该资源的进程自己释放

部分分配。进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。

环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。

预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。

1.一种方法是打破资源的互斥和不可剥夺这两个条件

例如允许进程同时访问某些资源等。

缺点:这种方法不能解决访问那些不允许被同时访问的资源时所带来的死锁问题

2.打破资源的部分分配这个死锁产生的必要条件

即预先分配各并发进程所需要的全部资源。如某个进程的资源得不到满足时，则安排一定的等待次序让其他进程释放资源。

缺点:

(1)在许多情况下，一个进程在执行之前不可能提出它所需要的全部资源。
(2) 无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行。
(3) 对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费。
(4) 降低了进程的并发性。

3.打破死锁的环路条件

即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。

如有m种资源，则列出R1＜R2＜…＜Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（Ri ＜Rj ）。释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。

缺点:限制了进程对资源的请求，而且对资源的分类编序也耗去一定的系统开销。

概述:死锁避免采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免，也称为动态预防。

基本模式:把进程分为多个步，其中每个步所使用的资源是固定的，且在一个步内，进程所保持的资源数不变。即进程的资源请求、使用与释放要依靠不同的步完成。

死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进程从死锁状态中恢复出来。

死锁检测:
当进程进行资源请求时死锁检测算法检查并发进程组是否构成资源的请求和保持环路

判断方法:
1.有限状态转移图
2.petriNet

恢复方法:
1.终止各锁住进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程时为止。
2.从被锁住进程强迫剥夺资源以解除死锁。