银行家算法ppt课件.ppt

1、计算机操作系统,银行家算法,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、2万，R要申请4万. Q1：客户要求分期贷款，一旦得到每期贷款，就能够归还贷款 Q2：银行家应谨慎的贷款，防止出现坏帐,什么是银行家问题？,银行家-操作系统 周转资金-系统资源 贷款客户-进程 当某进程请求分配资源时，系统假定先分配给它，之后若能找到一个进程完成序列（安全序列），说明系统是安全的，可进行实际分配；否则，让申请者等待。,银行家算法的实现思想,4,5,银行家算法中的数据结构,5,6,银行家算法 当Pi发出资源请求，分配一个Request向量 然后系统按下述流程进行执行：,Requesti：是进程Pi的请求向量 如果Requestij=K，表示进程i需要K个Rj类型的资源。,银行家算

3、法实现过程,6,7,7,8,安全性算法实现过程,安全性算法,两个向量：Work和Finish Work表示系统可提供给进程继续运行所需的各类资源数目（即在分配过程中，系统的可用资源数）。 初始值 Work=Available; Finish表示系统是否有足够的资源分配给进程i，使之运行完成。 初始值 Finishi:=false 当有足够资源分配给进程时 Finishi:=true,8,9,9,10,假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如下图所示。,7, 5, 3 3, 2, 2 9, 0,

4、 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）T0时刻系统是否安全？ 执行安全性算法进行检查：, 向量初值 Work :Available(3, 3, 2)； Finish i :false；（i0, 1, , 4）, 在进程集合中找到 Need1(1, 2, 2) Work 且 Finish 1 false；,银行家算法实例,11,12,true,5 3 2,P1,12,13,true,7 4

5、 3,5 3 2,13,14,true,7 5 3,7 4 3,14,15,true,10 5 5,7 5 3,15,16,16,17,发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量 Finish i true；且对应于该向量置为 “true” 的进程编号依次为：1 3 0 2 4，故： 系统存在安全序列 P1，P3，P0，P2，P4 所以，T0 时刻系统处于安全状态！,银行家算法实例,17,18,由分析知：执行完 P1、P3 的资源分配请求之后，系统可用的资源数量可以满足其它 3 个进程的资源请求，则此时的资源分配顺序已无关紧要。所以：,安全序列可以不唯一！,18,19,

6、（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,19,20,Available :AvailableRequest1 (3, 3, 2)(1, 0, 2)(2, 3, 0) Allocation1 :Allocation1R

7、equest1 (2, 0, 0)(1, 0, 2)(3, 0, 2) Need1 :Need1Request1 (1, 2, 2)(1, 0, 2)(0, 2, 0),银行家算法实例,20,21, 执行安全性算法： a. Work :Available(2, 3, 0)； Finish i :false；,在进程集合中找到 Need1(0, 2, 0) Work；,b. 在进程集合中找到 Need3(0, 1, 1) Work（5，3，2） 且 Finish 3 false；,银行家算法实例,21,22,执行安全性算法检查时，仍能够得到安全序列 P1，P3，P0，P2，P4 ，故请求向量 R

8、equest1 (1, 0, 2) 发出时系统安全！,银行家算法实例,22,23,（3）P4发出请求Request(3, 2, 1)，系统能分配资源吗？ 执行银行家算法进行检查：,银行家算法实例,23,24,（4）P0发出请求Request(0, 2, 0)，系统能分配资源吗？ 执行银行家算法进行检查：, Request0(0, 2, 0)Need0(7, 4, 3)； Request0(0, 2, 0)Available(2, 3, 0)； 系统为 P0 作预分配，并修改有关数据：,银行家算法实例,24,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),银行家算法实例,25,26,显然，对于所有进程，条件NeediAvailable，均不成立。因此， P0 此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预