避免死锁
标签: 操作系统
学习人数: 5062

避免死锁同样是属于事先预防的策略,但并不是事先采取某种限制措施,破坏产生死锁必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可能获得较好的系统性能,目前常用此方法来避免发生死锁。

 

1.系统安全状态

在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程必须等待。

所谓安全状态,是指系统能按某种进程顺序(P1,P2,...,Pn),来为每个进程 Pi 分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺利地完成。此时称(P1,P2,...,Pn)为安全序列。若系统无法找到一个安全序列,则称系统处于不安全状态。反之,只要系统处于安全状态,系统便不会进入死锁状态。因此,避免死锁的实质在于,系统在进行资源分配时,应使系统不进入不安全状态。

假定系统中有三个进程 P1、P2和P3,共有12台磁带机。进程P1总共要求10台磁带机,P2和P3分别要求 4 台和 9 台。 假设在T0时刻,进程 P1、P2和P3已分别获得5台、2台和2台磁带机,尚有3台空闲未分配,如下表所示:

在T0时刻是安全的,因为存在一个安全序列P1,P2,P3,只要系统按此进程序列分配资源,那么每个进程都能顺利完成。也就是说,当前可用磁带机为3台,先把3台磁带机分配给P2以满足其最大需求,P2 结束并归还资源后,系统有5 台磁带机可用;接下来给P1分配5 台.磁带机以满足其最大需求,P1结束并归还 资源后,剩余10台磁带机可用;最后分配7 台磁带机给P3,这样P3也能顺利完成。

若在T0时刻后,系统分配1 台磁带机给P3,系统剩余可用资源数为2 , 此时系统进入不安全状态,因为此时已无法再找到一个安全序列。当系统进入不安全状态后,便可能导致死锁。例如,把剩下的2 台磁带机分配给P2,这样,P2完成后只能释放4 台磁带机,既不能满足P1又不能满足P3,致使它们都无法推进到完成,彼此都在等待对方释放资源,陷入僵局,即导致死锁

 

2.银行家算法

(1)银行家算法的数据结构

最有代表性的避免死锁的算法是 Dijkstra 的银行家算法。由于该算法原本是为银行系统设计的,以确保银行在发放现金贷款时,不会发生不能 满足所有客户需要的情况。

为了实现银行家算法,必须设置四个数据结构,分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配,以及所有进程还需要多少资源的情况。

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

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

 

(2)银行家算法

Requesti是进程Pi的请求向量,如果Requesti[j]=K,表示进程Pi需要 K 个 j类型的资源。当Pi发出资源请求后,系统按下述步骤进行检查:

①如果 Requesti[j]≤Need[i, j],便转向步骤②;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

②如果 Requesti[j]≤Available[j],便转向步骤③;否则,表示尚无足够资源,Pi须等待。

③系统试探着把资源分配给进程 Pi,并修改下面数据结构中的数值:

Available[j] = Available[j]-Requesti[j];

Allocation[i,j]=Allocation[i,j]+Requesti[j];

Need[i,j] = Need[i,j]-Requesti[j];

④系统执行安全性算法,检查此次资源分配后系统是否处于安全状态。若安全,才正式将资源分配给进程 Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程 Pi等待。

 

(3)安全性算法

  1. 设置两个向量:

①工作向量 Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work = Available;

② Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。 开始时先做 Finish[i] = false;当有足够资源分配给进程时,再令 Finish[i]= true。

  1. 从进程集合中找到一个能满足下述条件的进程:

① Finish[i]=false;

② Need[i, j]≤Work[j]; 若找到,执行步骤 3),否则,执行步骤4)。

  1. 当进程 Pi 获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:

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

Finish[i] =true;

go to step 2);

  1. 如果所有进程的 Finish[i]=true 都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

 

(4)银行家算法之例

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

时刻的资源分配表

(1) T0时刻的安全性:利用安全性算法对T0时刻的资源分配情况进行分析可知,在T0时刻存在着一个安全序列{P0, P1, P2, P3, P4},故系统是安全的。

时刻的安全序列

(2) P1请求资源:P1发出请求向量Request1(1, 0, 2),系统按银行家算法进行检查:

① Request1(1, 0, 2)≤Request1(1, 2, 2);

② Request1(1, 0, 2)≤Request1(3, 3, 2);

③ 系统先假定可为P1分配资源,并修改 AvailableAllocation1Need1向量,由此形成的资源变化情况如图的圆括号所示;

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

P1申请资源时的安全性检查

(3) P4请求资源:P0发出请求向量 Request4(3,3,0),系统按银行家算法进行检查:

① Request4(3,3,0)≤Need4(4,3,1);

② Request4(3,3,0)>Available(2,3,0),让 等待。

(4)P0请求资源:P0发出请求向量 Request0(0,2,0),系统按银行家算法进行检查:

① Request0(0,2,0)≤Need0(7,4,3);

② Request0(0,2,0)≤Available(2,3,0);

③ 系统暂时先假定可为 分配资源,并修改有关数据。

P0分配资源后的有关资源数据

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

 



课后作业


登录后发布评论

暂无评论,来抢沙发