3.6 预防死锁的方法

一、预防死锁

二、系统安全状态

三、利用银行家算法避免死锁

预防死锁和避免死锁这两种方法，实质上都是通过施加某些限制条件，来预防发生死锁：

两者的区别主要在于：

预防死锁：
施加的限制条件比较严格，往往会影响进程的并发执行。
避免死锁：
施加的限制条件比较宽松，这给进程的运行提供了较为宽松的环境，有利于进程的并发执行。

一、预防死锁

产生死锁的必要条件

1、互斥条件
2、请求和保持条件
3、不剥夺条件
4、环路等待条件

预防死锁的方法是使四个必要条件中的第2,3,4条件之一不能成立，来避免发生死锁。

必要条件1，因为它是由设备的固有条件所决定的，不仅不能改变，还应加以保证。

1、摒弃“请求和保持”条件

系统规定所有进程在开始运行之前，都必须一次性的申请其在整个运行过程中所需的全部资源。此时若系统有足够的资源就分配给该进程，该进程在运行期间不会提出资源要求，从而摒弃了“请求”条件。若系统没有足够的资源分配给它，就让该进程等待。因而也摒弃了“保持”条件，从而避免发生死锁。

优点：算法简单、易于实现且很安全。
缺点：资源浪费严重和进程延迟运行。

2、摒弃“不剥夺”条件

系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，提出新的要求不被满足时必须释放它已经保持的所有资源，待以后需要时再重新申请。从而摒弃了“不剥夺”条件。

某一进程已经占有的资源，在运行过程中会被暂时释放掉，认为是被剥夺了。
实现起来比较复杂且付出很大代价。可能会前功尽弃，反复申请和释放等情况，延长了周转时间，增加系统开销。

与前两种策略比较，资源利用率和系统吞吐量都有较明显的改善。但也存在着严重问题：

1、为资源编号限制新设备的增加；
2、进程使用设备顺序与申请顺序不同，浪费资源
3、限制用户编程自由。

二、系统安全状态

在预防死锁的几种方法中，都施加了较强的限制条件；在避免死锁的方法中，所施加的限制条件较弱，又能获得令人满意的系统性能。
该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可避免发生死锁。

思路：

允许进程动态地申请资源，但在资源分配前，应先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，令进程等待。

安全状态

1、是否可以找到一个进程推进执行的顺序，从而满足每一个进程资源的最大需求，如果能则系统安全，否则不安全。

T0时刻：可用的有3台，可以先分配给进程B2台，然后B可以执行，执行完成以后释放4台，加上可用的1台，再分配给A，A执行完成以后，释放全部资源10台，再拿出9台可以分配给C。
所以系统存在一个合理的进程执行的推进顺序：B-A-C，因此在T0时刻系统是安全的。

2、T0以后，如果C再申请一台，那么剩下可用的还有两台，则这两台可以分配进程B，B执行完以后释放4台，此时A需要5台，C需要6台，进程A和C都不能继续执行，就无法进行分配，这样系统是不安全的。

三、利用银行家算法避免死锁

3、安全性算法

银行家算法例题

（1）判断T0时刻的安全性

1、初始时work= available，finish = FALSE

2、从进程集合中找到一个能够满足下列条件的进程：

 finish[i] = false, need[i,j] <= work,则 P1，P3满足条件。
 假设让P1先执行，从【3,3,2】中拿出【1,2,2】分配给P1，那么P1可以执行，执行完以后释放资源，
 则work=【2,1,0】+【3,2,2】=【5,3,2】且finish[1] = true。
 从P0,P2,P3,P4中找出满足finish[i] = false, need[i,j] <= work的条件。
 发现P3和P4满足条件，假设让P3先执行。
 则从【5,3,2】中拿出【0,1,1】分配给P3，P3可以执行，执行完以后释放资源。
 则work = 【5,3,2】+【2,1,1】=【7,4,3】，且finish[3] = TRUE。