避免死锁同样是属于事先预防的策略,但并不是事先采取某种限制措施,破坏产生死锁必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可能获得较好的系统性能,目前常用此方法来避免发生死锁。
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)安全性算法
①工作向量 Work,它表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work = Available;
② Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。 开始时先做 Finish[i] = false;当有足够资源分配给进程时,再令 Finish[i]= true。
① Finish[i]=false;
② Need[i, j]≤Work[j]; 若找到,执行步骤 3),否则,执行步骤4)。
Work[ j] = Work[ j]+Allocation[i, j];
Finish[i] =true;
go to step 2);
(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分配资源,并修改 Available,Allocation1和Need1向量,由此形成的资源变化情况如图的圆括号所示;
④ 再利用安全性算法检查此时系统是否安全。
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分配资源后的有关资源数据
无
登录后开始许愿
暂无评论,来抢沙发