3.7　避免死锁

3.7.1 系统安全状态 

  1．安全状态

  安全状态:系统能按某种进程顺序来为每个进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统找到这样一个安全序列，则称系统处于安全状态。

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

  2．安全状态举例

   假定系统中有三个进程P1、P2和P3，共有12台磁带机。假设在T0时刻，三进程资源分配如下表所示：若此时 P3又请求1台磁带机，试判断系统状态。

3.7.2　利用银行家算法避免死锁

  银行家算法原理：

1.只要用户对资金的需求量不超过银行家现有资金，即可接纳用户；

2.用户可分期贷款,只要申请总数不超过最大需求；

3.当银行家现有资金不足时就推迟贷款的发放；

4.用户得到所需全部资金,周转后能归还所有资金；

   银行家算法用于操作系统，OS相当于银行家，OS管理的资源相当于银行资金。

1.银行家算法中的数据结构(1个一维,3个二维数组）

     (1)资源向量Available[m]：一维数组，每一个元素代表一类资源数目,如Available[j]=K表示系统中现有j类资源K个。

       其初始值是系统中该类资源的全部数目，其值随该类资源的分配和回收动态地改变。

    (2)最大需求矩阵Max[n×m]:定义系统中每个进程对每类资源的最大需求。如Max[i,j]=K，表示进程i需要j类资源的最大数目为K。

    (3)分配矩阵Allocation[n×m]：定义当前系统中每一进程已分配的资源数。如Allocation[i,j]=K，表示进程i当前已分得j类资源K个。

    (4)需求矩阵Need[n×m]：表示每一个进程尚需的各类资源数。如Need[i,j]=K，表示进程i还需要j类资源K个。

  上述三个矩阵间存在下述关系：

       Need[i, j] +Allocation[i, j] =Max[i,j]

2．银行家算法

   设某时刻进程P i发出资源请求：Requesti[j]=K。系统按步骤进行检查

3．安全性算法

   (1) 设置两个向量：

     ①工作向量Work[m]:系统提供给进程的各类资源数目，如work[i]=k。初始时Work:=Available。

     ②Finish[n]:系统是否有足够的资源分配给进程，使之运行完成。开始时Finish[i]:=false；当有足够资源分配给进程时，Finish[i]:=true。

  (2)从进程集合中找到一个能满足下述条件的进程：①Finish[i]=false；

    ②Need[i,j]≤Work[j]；若找到，执行步骤(3)， 

           否则，执行步骤(4)。

(3)当进程Pi获得资源后可顺利执行，直至完成并释放出分配给它的资源，故应执行：

Work[j]:=Work[j]+Allocation[i,j]；

Finish[i]:=true；

go tostep 2；

  (4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

4．银行家算法之例

    假定系统中有五个进程{P0，P1，P2，P3，P4}和三类资源{A，B，C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图3-16所示。

(1) T0时刻的安全性：

   利用安全性算法分析可知：在T0时刻存在着一个安全序列{P1，P3，P4，P2，P0}，故系统是安全的。

(2) 若t0时刻P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查：

    ①Request1(1，0，2)≤Need1(1，2，2)

　②Request1(1，0，2)≤Available1(3，3，2)

　③系统先假定可为P1分配资源，并修改Available，Allocation1和Need向量，由此形成的资源变化情况。

④再利用安全性算法检查此时系统是否安全。如下图。

(3)P1分配资源后P4请求资源：Request4(3，3，0)，系统按银行家算法进行检查：

　①Request4(3，3，0)≤Need4(4，3，1)；

　②Request4(3，3，0)＞Available(2，3，0)，P4等待。

(4)P1分配资源后P0请求资源：Requst0(0，2，0)，系统按银行家算法进行检查：

　　①Request0(0，2，0)≤Need0(7，4，3)；

　　②Request0(0，2，0)≤Available(2，3，0)；

　　③系统暂时先假定可为P0分配资源，并修改有关数据，如图3-19所示。

(5)进行安全性检查：可用资源Available(2，1，0)已不能满足任何进程的需要，故系统进入不安全状态，此时系统不分配资源。

3.8　死锁的检测与解除

3.8.1　死锁的检测

　　系统若能检测和解除死锁则必须做到：

(1) 保存有关资源的请求和分配信息；

(2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。————资源分配图

1．资源分配图(ResourceAllocation Graph)

    由一组结点N和一组边E所组成，具有下述形式的定义和限制：

(1)N分为两个互斥的子集：

  一组进程结点P={p1，p2，…，pn}；

  一组资源结点R={r1，r2，…，rn}，N=P∪R。

    (2)E中每一个带箭头边e∈E，都连着P中的一个结点和R中的一个结点。

     请求边:由进程指向资源；

     分配边:由资源指向进程。

圆圈代表一个进程；

方框代表一类资源；

方框中的一个点代表一类资源中的一个资源。

2．死锁定理

    利用把资源分配图加以简化的方法(图3-21)，来检测当系统处于S状态时是否为死锁状态。

(1)在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。分配Pi所需资源，运行完毕再释放其占有的全部资源。相当于消去pi所求的请求边和分配边，使之成为孤立的结点。

    (2)在进行一系列的简化后，若能使所有的进程结点都成为孤立结点，则称该图是可完全简化的；否则称该图是不可完全简化的。

死锁定理：

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

     若分配图不能完全简化，则所有的简化顺序，都将得到相同的不可简化图。

     例题：若有P1、P2两进程，A,B两种资源，A共3个，B共2个。S状态：P1占有2个A资源，1个B资源，又申请1个A资源；P2占有1个A资源又申请1个B资源。

试用资源分配图检测S状态是否是deadlock。

3．死锁检测中的数据结构

(1)资源向量Available:表示每一类资源的可用数目；

(2)把不占用资源的进程记入L表中，即Li∪L。

    (3)从进程集合中找到一个Requesti≤Work的进程执行：

  ①将其资源分配图简化,释放出资源,增加工作向量 

          Work:=Work + Allocation i；

  ②将它记入L表中；

    (4) 若不能把所有进程都记入L表中,表明状态S的资源分配图是不可完全简化的。该系统状态将发生死锁。

Work:=Available；

L:={Li|Allocation i=0∩Request i=0}

for allLiL  do

begin

for allRequest i≤Work do

begin

Work:=Work +Allocationi；

Li∪L；

end

end

deadlock:=┓(L={p1，p2，…，pn})；

3.8.2　死锁的解除

常采用解除死锁的两种方法是：

(1)剥夺资源。

      剥夺其它进程的资源给死锁进程；

      剥夺死锁进程本身资源；

(2)撤消进程。

       最简单的方法：全部死锁进程都撤销；

       稍微温的方法：按照某种顺序逐个地撤消进程，直至死锁状态消除为止。

　　撤消进程策略：撤消的进程数目最小；撤消进程所付出的代价最小等。

方法一：撤销进程的过程毫无算法，茫无目的，   

                 抓着一个进程就撤销一个。

    缺点：花费的代价较大。

   方法二：每次都选取代价最小的进程撤销，直到 

                  死锁解除