银行家算法PPT学习课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,计算机操作系统,银行家算法,1,2,死锁的“,3W”,What,Why,How,什么是死锁？,为什么会发生死锁？,怎么解决死锁？,2,3,死锁的处理方法,（1）预防死锁,：,通过某些限制条件的设置，去破坏产生死锁的四个必要条件；,（2）避免死锁,：,在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；,（3）检测死锁,：,及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；,（4）解除死锁,：,撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。,3,4,避免死锁,银行家算法,设银行家有,10,万周转资金，,P,Q,R,分别需要,8,3,9,万元搞项目，如果,P,已申请到了,4,万，,Q,要申请,2,万，,R,要申请,4,万,.,Q1,：,客户要求分期贷款，一旦得到每期贷款，就能够归还贷款,Q2,：,银行家应谨慎的贷款，防止出现坏帐,什么是银行家问题？,银行家,-,操作系统 周转资金,-,系统资源 贷款客户,-,进程,当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。,银行家算法的实现思想,4,5,表 示 形 式,含 义,Available,（,可用资源数组）,Available j k,现有资源,j,的数目为,k,Max,（,最大需求矩阵）,Max i,j k,进程,i,对资源,j,的最大需求数目为,k,Allocation,（,分配矩阵）,Allocation i,j k,进程,i,当前已分得的资源,j,的数目为,k,Need,（,需求矩阵）,Need i,j k,进程,i,尚需分配的资源,j,的数目为,k,银行家算法中的数据结构,5,6,银行家算法,当Pi发出资源请求，,分配一个,Request,向量,然后,系统按下述,流程,进行,执行,：,Request,i,：,是进程,P,i,的请求向量,如果Request,i,j,=K，表示进程i需要K个R,j,类型的资源。,银行家算法实现过程,6,7,7,8,安全性算法实现过程,安全性算法,两个向量：Work,和,Finish,Work,表示系统可提供给进程继续运行所需的各类资源数目,（即在分配过程中，系统的可用资源数）。,初始值,Work=Available;,Finish,表示系统是否有足够的资源分配给进程,i,，使之运行完成。,初始值,Finishi:=false,当有足够资源分配给进程时 Finishi:=true,8,9,9,10,假定系统中有五个进程,P,0,P,1,P,2,P,3,P,4,和三类资源,A,B,C，,各种资源的数量分别为10、5、7，在,T,0,时刻的资源分配情况如下图所示。,P,4,P,3,P,2,P,1,P,0,Available,A,B,C,Need,A,B,C,Allocation,A,B,C,Max,A,B,C,进 程,资源,情况,7,5,3,3,2,2,9,0,2,2,2,2,4,3,3,0,1,0,2,0,0,3,0,2,2,1,1,0,0,2,7,4,3,1,2,2,6,0,0,0,1,1,4,3,1,3,3,2,银行家算法实例,10,11,（1）,T,0,时刻系统是否安全？,执行安全性算法进行检查：,向量初值,Work:Available,(3,3,2),；,Finish i:false；（i0,1,4）,在进程集合中找到,Need,1,(1,2,2),Work,且,Finish 1 false；,则设,P,1,顺利执行完成，从而有：,Work,:WorkAllocation,1,(3,3,2)(2,0,0),(5,3,2),Finish 1:true,银行家算法实例,11,12,Chapter 3,处理机调度与死锁,Finish,Work+Allocation,Allocation,Need,Work,true,5 3 2,2 0 0,1 2 2,3 3 2,P1,Allocation,Need,P0,0 1 0,7 4 3,P1,2 0 0,1 2 2,P2,3 0 2,6 0 0,P3,2 1 1,0 1 1,P4,0 0 2,4 3 1,12,13,Chapter 3,处理机调度与死锁,Finish,Work+Allocation,Allocation,Need,Work,true,7 4 3,5 3 2,2 1 1,0 1 1,P3,true,5 3 2,2 0 0,1 2 2,3 3 2,P1,Allocation,Need,P0,0 1 0,7 4 3,P1,2 0 0,1 2 2,P2,3 0 2,6 0 0,P3,2 1 1,0 1 1,P4,0 0 2,4 3 1,13,14,Chapter 3,处理机调度与死锁,Finish,Work+Allocation,Allocation,Need,Work,true,7 5 3,7 4 3,0 1 0,7 4 3,true,7 4 3,2 1 1,0 1 1,5 3 2,true,5 3 2,2 0 0,1 2 2,3 3 2,P0,P3,P1,Allocation,Need,P0,0 1 0,7 4 3,P1,2 0 0,1 2 2,P2,3 0 2,6 0 0,P3,2 1 1,0 1 1,P4,0 0 2,4 3 1,14,15,Chapter 3,处理机调度与死锁,Finish,Work+Allocation,Allocation,Need,Work,true,10 5 5,7 5 3,true,7 5 3,0 1 0,7 4 3,7 4 3,3 0 2,6 0 0,true,7 4 3,2 1 1,0 1 1,5 3 2,true,5 3 2,2 0 0,1 2 2,3 3 2,P0,P2,P3,P1,Allocation,Need,P0,0 1 0,7 4 3,P1,2 0 0,1 2 2,P2,3 0 2,6 0 0,P3,2 1 1,0 1 1,P4,0 0 2,4 3 1,15,16,Chapter 3,处理机调度与死锁,Allocation,Need,P0,0 1 0,7 4 3,P1,2 0 0,1 2 2,P2,3 0 2,6 0 0,P3,2 1 1,0 1 1,P4,0 0 2,4 3 1,true,10 5 7,0 0 2,4 3 1,10 5 5,P4,Finish,Work+Allocation,Allocation,Need,Work,true,10 5 5,7 5 3,true,7 5 3,0 1 0,7 4 3,7 4 3,3 0 2,6 0 0,true,7 4 3,2 1 1,0 1 1,5 3 2,true,5 3 2,2 0 0,1 2 2,3 3 2,P0,P2,P3,P1,16,17,发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量,Finish i true；,且对应于该向量置为“,true”,的进程编号依次为：1,3,0,2,4，故：系统存在安全序列,P,1,，P,3,，P,0,，P,2,，P,4,所以，,T,0,时刻系统处于安全状态！,银行家算法实例,17,18,Chapter 3,处理机调度与死锁,由分析知：执行完,P,1,、P,3,的资源分配请求之后，系统可用的资源数量可以满足其它 3 个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：,安全序列可以不唯一,！,true,10 5 7,0 0 2,4 3 1,10 5 5,P4,Finish,Work+Allocation,Allocation,Need,Work,true,10 5 5,7 5 3,true,7 5 3,0 1 0,7 4 3,7 4 3,3 0 2,6 0 0,true,7 4 3,2 1 1,0 1 1,5 3 2,true,5 3 2,2 0 0,1 2 2,3 3 2,P0,P2,P3,P1,18,19,（2）,P,1,发出请求,Request(1,0,2),，系统能分配资源吗？,执行银行家算法：,Request,1,(1,0,2),Need,1,(1,2,2)；,Request,1,(1,0,2),Available(3,3,2)；,系统为,P,1,进行,预分配,，并修改,Available，Allocation,1,和,Need,1,向量：,银行家算法实例,Request,1,(1,0,2),，,Need,1,，,Available,19,20,Available,:AvailableRequest,1,(3,3,2)(1,0,2),(2,3,0),Allocation,1,:Allocation,1,Request,1,(2,0,0)(1,0,2),(3,0,2),Need,1,:Need,1,Request,1,(1,2,2)(1,0,2),(0,2,0),银行家算法实例,20,21,执行安全性算法,：,a.Work:Available,(2,3,0),；Finish i:false；,在进程集合中找到,Need,1,(0,2,0),Work；,b.,在进程集合中找到,Need,3,(0,1,1),Work,（,5,，,3,，,2,）,且,Finish 3 false；,c.,则设,P,1,可顺利执行完成，从而有：,Work,:WorkAllocation,1,(2,3,0)(3,0,2),(5,3,2),Finish,1,:true,银行家算法实例,21,22,c.,则设,P,3,顺利执行完成，从而有：,Work,:WorkAllocation,3,(5,3,2)(2,1,1),(7,4,3),Finish 3:true,执行安全性算法检查时，仍能够得到安全序列,P1,，,P3,，,P0,，,P2,，,P4,，故请求向量,Request,1,(1,0,2),发出时系统安全！,银行家算法实例,22,23,（3）,P,4,发出请求,Request(3,2,1),，系统能分配资源吗？,执行银行家算法进行检查：,Request,4,(3,2,0),Need,4,(4,3,1)；,Request,4,(3,2,1),Available(2,3,0),故：,P,4,资源请求失败，让其等待！,银行家算法实例,23,24,（4）,P,0,发出请求,Request(0,2,0),，系统能分配资源吗？,执行银行家算法进行检查：,Request,0,(0,2,0),Need,0,(7,4,3)；,Request,0,(0,2,0),Available(2,3,0)；,系统为,P,0,作预分配，并修改有关数据：,银行家算法实例,24,25,Available,:AvailableRequest,0,(2,3,0)(0,2,0),(2,1,0),Allocation,0,:Allocation,0,Request,0,(0,1,0)(0,2,0),(0,3,0),Need,0,:Need,0,Request,0,(7,4,3)(0,2,0),(7,2,3),银行家算法实例,25,26,Max,Allocation,Need,Available,P0,7 5 3,0 3 0,7 2 3,2 1 0,P1,3 2 2,3 0 2,0 2 0,P2,9 0 2,3 0 2,6 0 0,P3,2 2 2,2 1 1,0 1 1,P4,4 3 3,0 0 2,4 3 1,显然，对于所有进程，条件,Need,i,Available,，均不成立。,因此，,P,0,此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。,银行家算法实例,26,27,练习,资源,进程,Allocation,Need,Available,r1 r2 r3,r1 r2 r3,r1 r2 r3,P0,P1,P2,P3,P4,3 1 1,0 0 0,1 1 0,1 0 1,0 0 0,1 0 0,0 1 2,3 0 0,0 1 0,2 1 0,1 2 0,在银行家算法中，若出现下面的资源分配情况：,27,28,试问：,该状态是否安全？,如果进程,P2,提出请求,Request(0,，,1,，,0),，系统能否将资源分配给它？,如果系统立即满足,P2,的上述请求，则系统是否立即进入死锁状态？,练习,28,