如何求解银行家算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,死锁、银行家算法,1.,死锁概念,指多个进程因竞争共享资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前推进。,即：一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到的资源，这种现象称为进程死锁，这一组进程就称为死锁进程。,思考：,如果系统中有,n,个进程，则在等待队列中进程的个数最多为（）个,有,n,个进程的系统出现死锁时，死锁进程的个数,k,应满足的条件是（）,产生死锁的原因,1.,竞争资源（资源不足）,2.,进程的推进顺序不当,1.,竞争系统资源,若系统中只有一台打印机,R1,和一台读卡,机,R2,，,可供进程,P1,和,P2,共享。若,形成环路,，这样会产生死锁,。,由于进程的调度是独立的，请求和释放操作可按如下序列进行：,A,r1,A,r2,A,r3,A,r4,B,r1,B,r2,B,r3,B,r4,B,r1,B,r2,B,r3,B,r4,A,r1,A,r2,A,r3,A,r4,A,r1,A,r2.,B,r1,A,r3,A,r4,B,r2,B,r3,B,r4,A,r1,B,r1,A,r2,B,r2,A,r3,A,r4,B,r3,B,r4,对序列,三个进程都能顺利进行，,则会产生死锁。,进程,A,、,B,对资源的请求和释放,2.,进程推进顺序不当引起死锁,思考：,某系统中有,3,个并发进程都需要,4,个同类资源，该系统不会发生死锁的最少资源是（）个,P341,例,8,2.,死锁避免,死锁避免定义,:,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。,由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。,3.,安全状态与不安全状态,安全状态指系统能按某种进程顺序,P,1,，,，,P,n,来为每个进程,P,i,(1,i,n,）分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。如果存在，则称序列,为安全序列。,说 明,并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进入死锁。,安全状态一定是没有死锁发生的。,避免死锁的实质：系统进行资源分配时，如何使系统不进入不安全状态。,2),安全状态之例,假定系统中有三个进程,P,1,、,P,2,和,P,3,，,共有,12,台磁带机。进程,P,1,总共要求,10,台磁带机，,P,2,和,P,3,分别要求,4,台和,9,台。假设在,T,0,时刻，进程,P,1,、,P,2,和,P,3,已分别获得,5,台、,2,台和,2,台磁带机,，尚有,3,台空闲未分配，如下表所示：,进 程,最 大 需 求,已 分 配,可 用,P,1,P,2,P,3,10,4,9,5,2,2,3,问：,T,0,时刻是否安全？,3),由安全状态向不安全状态的转换,如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。,例如，在,T,0,时刻以后，,P,3,又请求,1,台磁带机，若此时系统把剩余,3,台中的,1,台分配给,P,3,，,则系统便进入不安全状态。因为，此时也无法再找到一个安全序列，例如，把其余的,2,台分配给,P,2,，,这样，在,P,2,完成后只能释放出,4,台，既不能满足,P,1,尚需,5,台的要求，也不能满足,P,3,尚需,6,台的要求，致使它们都无法推进到完成，彼此都在等待,对方释放资源，即陷入僵局，结果导致死锁。,P3,的请求应拒绝。,安全状态与不安全状态,不安全状态,:,不存在一个安全序列，不安全状态不一定导致死锁,4.,利用银行家算法避免死锁,1),银行家算法中的数据结构,(1),可利用资源向量,Available,。,这是一个含有,m,个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果,Available,j,=K,，,则表示系统中现有,R,j,类资源,K,个。,(2),最大需求矩阵,Max,。,这是一个,n,m,的矩阵，它定义了系统中,n,个进程中的每一个进程对,m,类资源的最大需求。如果,Max,i,j,=K,，,则表示进程,i,需要,R,j,类资源的最大数目为,K,。,(3),分配矩阵,Allocation,。,这也是一个,n,m,的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果,Allocation,i,j,=K,，,则表示进程,i,当前已分得,R,j,类资源的数目为,K,。,(4),需求矩阵,Need,。这也是一个,n,m,的矩阵，用以表示每一个进程尚需的各类资源数。如果,Need,i,j,=,K,，则表示进程,i,还需要,Rj,类资源,K,个，方能完成其任务。,Need,i,j,=Max,i,j,-Allocation,i,j,2),银行家算法,设,Request,i,是进程,P,i,的请求向量，如果,Request,i,j,=,K,，,表示进程,P,i,需要,K,个,R,j,类型的资源。当,P,i,发出资源请求后，系统按下述步骤进行检查：,(1),如果,Request,i,j,Need,i,j,，,便转向步骤,2,；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。,(2),如果,Request,i,j,Available,j,，,便转向步骤,(3),；否则，表示尚无足够,资源，,P,i,须等待。,(3),系统试探着把资源分配给进程,P,i,，,并修改下面数据结构中的数值：,Available,j,=Available,j,-,Request,i,j,;,Allocation,i,j,=Allocation,i,j,+,Request,i,j,;,Need,i,j,=Need,i,j,-,Request,i,j,;,(4),系统执行,安全性算法,，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程,P,i,，,以完成本次分配；否则，将本次的试探分配作废，恢复,原来的资源分配状态，让进程,P,i,等待。,3),安全性算法,(1),设置两个向量：,工作向量,Work:,它表示系统可提供给进程继续运行所需的各类资源数目，它含有,m,个元素，在执行安全算法开始时，,Work=Available;,Finish:,它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做,Finish,i,=false;,当有足够资源分配给进程时，再令,Finish,i,=true,。,(2),从进程集合中找到一个能满足下述条件的进程：,Finish,i,=false;Need,i,j,Work,j,；,若找到，执行步骤,(3),，否则，执行步骤,(4),。,(3),当进程,P,i,获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：,Work,j,=Work,i,+Allocation,i,j,;,Finish,i,=true;,go to step 2;,(4),如果所有进程的,Finish,i,=true,都满足，则表示系统处于安全状态；否则，系统,处于不安全状态。,4),银行家算法之例,假定系统中有五个进程,P,0,P,1,P,2,P,3,P,4,和三类资源,A,B,C,，,各种资源的数量分别为,10,、,5,、,7,，在,T,0,时刻的资源分配情况如,图,3-16,所示。,图,3-16,T,0,时刻的资源分配表,(1),T,0,时刻的安全性检查,图,3-17,T,0,时刻的安全序列,(2)P,1,请求资源：,P,1,发出请求向量,Request,1,(1,，,0,，,2),，,系统按银行家算法进行检查：,Request,1,(1,0,2)Need,1,(1,2,2),Request,1,(1,0,2)Available,1,(3,3,2),系统先假定可为,P,1,分配资源，并修改,Available,Allocation,1,和,Need,1,向量，由此形成的资源变化情况如图,3-16,中的圆括号所示。,再利用安全性算法检查此时系统是否安全。如图,3-18,图,3-18 P,1,申请资源时的安全性检查,(3)P,4,请求资源：,P,4,发出请求向量,Request,4,(3,，,3,，,0),，,系统按银行家算法进行检查：,Request,4,(3,3,0)Need,4,(4,3,1);,Request,4,(3,3,0)Available(2,3,0),，让,P,4,等待。,(4)P,0,请求资源：,P,0,发出请求向量,Requst,0,(0,，,2,，,0),，,系统按银行家算法进行检查：,Request,0,(0,2,0)Need,0,(7,4,3);,Request,0,(0,2,0)Available(2,3,0);,系统暂时先假定可为,P,0,分配资源，并修改有关数据，如图,3-19,所示。,图,3-19,为,P,0,分配资源后的有关资源数据,（,5,）安全性检查：,Available(2,1,0),不能满足任何进程的需求，系统进入不安全状态，不能分配资源。,思考：,P,0,请求改为,Request,0,(0,，,1,，,0),，系统是否能分配资源？,