银行家算法PPT课件

.,1,计算机操作系统,银行家算法,.,2,死锁的“3W”,WhatWhyHow,什么是死锁？,为什么会发生死锁？,怎么解决死锁？,.,3,死锁的处理方法,（1）预防死锁：通过某些限制条件的设置，去破坏产生死锁的四个必要条件；（2）避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态；（3）检测死锁：及时检测死锁的发生，并确定与之相关的进程、资源，从而采取措施清除死锁；（4）解除死锁：撤消或挂起某些进程以回收一些资源，用于解脱另一些处于死锁的进程。,.,4,避免死锁银行家算法,设银行家有10万周转资金，P,Q,R分别需要8,3,9万元搞项目，如果P已申请到了4万，Q要申请2万，R要申请4万.Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款Q2：银行家应谨慎的贷款，防止出现坏帐,什么是银行家问题？,银行家-操作系统周转资金-系统资源贷款客户-进程当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。,银行家算法的实现思想,.,5,银行家算法中的数据结构,.,6,银行家算法当Pi发出资源请求，分配一个Request向量然后系统按下述流程进行执行：,Requesti：是进程Pi的请求向量如果Requestij=K，表示进程i需要K个Rj类型的资源。,银行家算法实现过程,.,7,.,8,安全性算法实现过程,安全性算法,两个向量：Work和FinishWork表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。初始值Work=Available;Finish表示系统是否有足够的资源分配给进程i，使之运行完成。初始值Finishi:=false当有足够资源分配给进程时Finishi:=true,.,9,.,10,假定系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。,7,5,33,2,29,0,22,2,24,3,3,0,1,02,0,03,0,22,1,10,0,2,7,4,31,2,26,0,00,1,14,3,1,3,3,2,银行家算法实例,.,11,（1）T0时刻系统是否安全？执行安全性算法进行检查：,向量初值Work:Available(3,3,2)；Finishi:false；（i0,1,4）,在进程集合中找到Need1(1,2,2)Work且Finish1false；,银行家算法实例,.,12,true,532,P1,.,13,true,743,532,.,14,true,753,743,.,15,true,1055,753,.,16,.,17,发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量Finishitrue；且对应于该向量置为“true”的进程编号依次为：13024，故：系统存在安全序列P1，P3，P0，P2，P4所以，T0时刻系统处于安全状态！,银行家算法实例,.,18,由分析知：执行完P1、P3的资源分配请求之后，系统可用的资源数量可以满足其它3个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：,安全序列可以不唯一！,.,19,（2）P1发出请求Request(1,0,2)，系统能分配资源吗？,执行银行家算法：,Request1(1,0,2)Need1(1,2,2)；Request1(1,0,2)Available(3,3,2)；系统为P1进行预分配，并修改Available，Allocation1和Need1向量：,银行家算法实例,Request1(1,0,2)，Need1，Available,.,20,Available:AvailableRequest1(3,3,2)(1,0,2)(2,3,0)Allocation1:Allocation1Request1(2,0,0)(1,0,2)(3,0,2)Need1:Need1Request1(1,2,2)(1,0,2)(0,2,0),银行家算法实例,.,21,执行安全性算法：a.Work:Available(2,3,0)；Finishi:false；,在进程集合中找到Need1(0,2,0)Work；,b.在进程集合中找到Need3(0,1,1)Work（5，3，2）且Finish3false；,银行家算法实例,.,22,执行安全性算法检查时，仍能够得到安全序列P1，P3，P0，P2，P4，故请求向量Request1(1,0,2)发出时系统安全！,银行家算法实例,.,23,（3）P4发出请求Request(3,2,1)，系统能分配资源吗？执行银行家算法进行检查：,银行家算法实例,.,24,（4）P0发出请求Request(0,2,0)，系统能分配资源吗？执行银行家算法进行检查：,Request0(0,2,0)Need0(7,4,3)；Request0(0,2,0)Available(2,3,0)；系统为P0作预分配，并修改有关数据：,银行家算法实例,.,25,Available:AvailableRequest0(2,3,0)(0,2,0)(2,1,0)Allocation0:Allocation0Request0(0,1,0)(0,2,0)(0,3,0)Need0:Need0Request0(7,4,3)(0,2,0)(7,2,3),银行家算法实例,.,26,显然，对于所有进程，条件NeediAvailable，均不成立。因此，P0此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。,银行