银行家算法ppt课件.ppt
计算机操作系统,银行家算法,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)； Finish i :false；（i0, 1, , 4）, 在进程集合中找到 Need1(1, 2, 2) Work 且 Finish 1 false；,银行家算法实例,12,true,5 3 2,P1,13,true,7 4 3,5 3 2,14,true,7 5 3,7 4 3,15,true,10 5 5,7 5 3,16,17,发现：目前可执行的所有资源分配工作完成之后，各个进程对应的状态向量 Finish i true；且对应于该向量置为 “true” 的进程编号依次为：1 3 0 2 4，故： 系统存在安全序列 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)； Finish i :false；,在进程集合中找到 Need1(0, 2, 0) Work；,b. 在进程集合中找到 Need3(0, 1, 1) Work（5，3，2） 且 Finish 3 false；,银行家算法实例,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 此次资源请求预分配的结果，使系统进入不安全状态，故应撤消此次预分配。,银行家算法实例,27,练习,在银行家算法中，若出现下面的资源分配情况：,
