死锁产生的原因和必要条件及预防死锁的方法及死锁的检测与解除

超、凢脫俗 2022-09-23 11:00 311阅读 0赞

产生死锁的原因和必要条件：

产生死锁的原因：通常是源于多个进程对资源的争夺，不仅对不可抢占资源进行争夺时会引起死锁，而且对可消耗资源进行争夺时，也会引起死锁。

1.竞争不可抢占行资源引起死锁：

通常系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要，使得进程在运行过程中，会因争夺资源而陷入僵局。

![Center][]

2.竞争可消耗资源引起消耗

![Center 1][]

3.进程推进顺序不当引起死锁

![Center 2][]

产生死锁的四个必要条件：

（1） 互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内，某资源只能被一个进程占用，如果此时还有其他进程请求该资源，则请求进程只能等待，直至占有该资源进程用毕释放。

（2） 请求与保持条件：进程已经保持至少一个资源，又请求新的资源而失败，此时请求进程被阻塞，但对自己已获得的资源保持不放

（3） 不可抢占条件:进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时自己释放。

（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

处理死锁的方法：

1.预防死锁  2.避免死锁 3.检测死锁 4.解除死锁

预防死锁的方法：

1.破坏“互斥”条件:就是在系统里取消互斥。若资源不被一个进程独占使用，那么死锁是肯定不会发生的。但一般来说在所列的四个条件中，“互斥”条件是无法破坏的。因此，在死锁预防里主要是破坏其他几个必要条件，而不去涉及破坏“互斥”条件。

2.破坏“占有并等待”条件:破坏“占有并等待”条件，就是在系统中不允许进程在已获得某种资源的情况下，申请其他资源。即要想出一个办法，阻止进程在持有资源的同时申请其他资源。

方法一：创建进程时，要求它申请所需的全部资源，系统或满足其所有要求，或什么也不给它。这是所谓的 “ 一次性分配”方案。  
方法二：要求每个进程提出新的资源申请前，释放它所占有的资源。这样，一个进程在需要资源S时，须先把它先前占有的资源R释放掉，然后才能提出对S的申请，即使它可能很快又要用到资源R。

3.破坏“不可抢占”条件：破坏“不可抢占”条件就是允许对资源实行抢夺。  
方法一：如果占有某些资源的一个进程进行进一步资源请求被拒绝，则该进程必须释放它最初占有的资源，如果有必要，可再次请求这些资源和另外的资源。  
方法二：如果一个进程请求当前被另一个进程占有的一个资源，则操作系统可以抢占另一个进程，要求它释放资源。只有在任意两个进程的优先级都不相同的条件下，方法二才能预防死锁。

4.破坏“循环等待”条件：破坏“循环等待”条件的一种方法，是将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出。这样做就能保证系统不出现死锁。

利用银行家[算法][Link 1]避免死锁：

银行家算法:

设进程i提出请求Request\[j\]，则银行家算法按如下规则进行判断。

(1) 如果Request\[j\]≤Need\[i,j\]，则转向（2），否则认为出错。

(2) 如果Request\[j\]≤Available\[j\]，则转向（3）；否则表示尚无足够资源，Pi需等待。

(3) 假设进程i的申请已获批准，于是修改系统状态：

Available\[j\]=Available\[j\]-Request\[i\]

Allocation\[i,j\]=Allocation\[i,j\]+Request\[j\]

Need\[i,j\]=Need\[i,j\]-Request\[j\]

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。

安全性检查：

(1) 设置两个工作向量Work=Available；Finish\[i\]=False

(2) 从进程集合中找到一个满足下述条件的进程，

Finish \[i\]=False;

Need\[i,j\]≤Work\[j\];

如找到，执行(3)；否则，执行(4)

(3) 设进程获得资源，可顺利执行，直至完成，从而释放资源。

Work\[j\]=Work\[i\]+Allocation\[i,j\];

Finish\[i\]=True;

go to step 2;

(4) 如所有的进程Finish\[i\]=true，则表示安全；否则系统不安全。

代码实现：https://github.com/wangiijing/banker-s-algorithm

死锁的检测与解除：

资源分配图：

系统死锁，可利用资源分配图来描述。如图2-17所示，用圆圈代表一个进程，用框代表一类资源。由于一种类型的资源可能有多个，用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边，表示该进程申请一个单位的该类资源；从资源到进程的边叫分配边，表示该类资源已经有一个资源被分配给了该进程。  
![Center 3][]

在图2-17所示的资源分配图中，进程P1已经分得了两个R1资源，并又请求一个R2 资源；进程P2分得了一个R1和一个R2资源，并又请求一个R1资源。  
死锁定理：

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下：

1) 在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配边，使之成为孤立的结点。在图2-18(a)中，P1是满足这一条件的进程结点，将P1的所有边消去，便得到图248(b)所示的情况。

2) 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在图2-17中，进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边，则称该图是可完全简化的，如图2-18(c)所示。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。

死锁的解除：

一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。死锁解除的主要方法有：

1) 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。

2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。

![Center 4][]

3) 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

[Center]: /images/20220720/86c919057a2a4cfca476c952ff7c94e6.png
[Center 1]: /images/20220720/61319d7b3eb641fbb8c86545e56cf5fd.png
[Center 2]: /images/20220720/e125b7eacf954aa08203ef95568b1ef0.png
[Link 1]: http://lib.csdn.net/base/31
[Center 3]: /images/20220720/a13eb637ab6f4c0eb139dd7c42256b18.png
[Center 4]: /images/20220720/447603e600bb4b0088aebc724be7bd7e.png