死锁问题.ppt

*安全状态的例子例:假定系统有三个进程P1、P2、P3,共有12台磁带机。进程P1总共要求10台磁带机,P2和P3分别要求4台和九台。设在T0时刻,进程P1、P2和P3已经获得5台、2台和2台,还有3台空闲没有分配。进程最大需求已分配可用P11053P2P34229T0时刻系统时安全的。这时存在一个安全序列<P2,P1,P3>*虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便有可能进入死锁状态;反之只要系统处于安全状态,系统便可避免进入死锁状态。因此,避免死锁的实质是如何使系统不进入不安全状态。系统的状态可能通过下述来描述:进程剩余申请数=最大申请数-占有数。可分配资源数=总数-占有数之和。*银行家算法银行家算法是最有代表性的避免死锁算法,是Dijkstra提出的银行家算法。这是由于该算法能用于银行系统现金贷款的发放而得名。为实现银行家算法,系统中必须设置若干数据结构。*一、银行家算法中的数据结构1可利用资源向量Available是一个含有m个元素,其中的每一个元素代表一类可利用的资源数目,其初值是系统中所配置的该类全部可用资源数目。如果Available[j]=k, 表示系统中现有Rj类资源k个。2最大需求矩阵Max是一个含有nm的矩阵,它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max(i,j)=k, 表示进程i需要Rj类资源的最大数目为k。Available=354283861*3分配矩阵Allocation是一个含有nm的矩阵,它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation(i,j)=k, 表示进程i当前已分得Rj类资源k个。4需求矩阵Need是一个含有nm的矩阵,用以表示每一个进程尚需的各类资源数。如果Need(i,j)=k, 表示进程i还需要Rj类资源k个,方能完成其任务。Need(i,j)=Max(i,j)-Allocation(i,j)*二、银行家算法设Requesti是进程Pi的请求向量,如果进程Pi需要K个Rj类资源,当Pi发出资源请求后,系统按下述步骤进行检查:1如果Requesti≤Needi,则转向步骤2;否则认为出错。(因为它所需要的资源数已超过它所宣布的最大值。2如果Requesti≤Available,则转向步骤3;否则,表示系统中尚无足够的资源,Pi必须等待3系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值:Available:=Available-Requesti;Allocation:=Allocation+Requesti;Needi:=Needi-Requesti;4系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,正式将资源分配给进程Pi,以完成本次分配;否则,将试探分配作废,恢复原来的资源分配状态,让进程Pi等待。*三、安全性算法系统所执行的安全性算法可描述如下:1设置两个向量①,它含有m个元素,执行安全算法开始时,Work:=Available。②,使之运行完成。开始时先做Finish[i]:=false;当有足够的资源分配给进程时,令Finish[i]:=:①Finish[i]=false;②Needi≤,执行步骤3;否则执行步骤4。3当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故执行:Work:=Work+Allocation;Finish[i]:=true;Gotostep2;4如果所有进程的Finish[i]=true,则表示系统处于安全状态;否则,系统处于不安全状态。要记住的一些变量的名称1Available(可利用资源向量)某类可利用的资源数目,其初值是系统中所配置的该类全部可用资源数目。2Max最大需求矩阵某个进程对某类资源的最大需求数3Allocation分配矩阵某类资源当前非配给某进程的资源数。4Need需求矩阵某个进程还需要的各类资源数。Need=Max-Allocation系统把进程请求的资源分配给它以后要修改的变量Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request;*银行家算法之例假定系统中有五个进程{P0、P1、P2、P3、P4}和三种类型的资源{A,B,C},每一种资源的数量分别为10、5、7,eedABCAvailableABCP0P1P2P3P4010322902222433200(302)3022**********(020)0