《银行家算法例题——四步走解题.doc》由会员分享，可在线阅读，更多相关《银行家算法例题——四步走解题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、银行家算法例题系统中原有三类资源A、B、C和五个进程P1、P2、P3、P4、P5，A资源17，B资源5，C资源20。当前（T0时刻）系统资源分配和进程最大需求如下表。 资源进程AllocationMaxA B CA B CP1 2 1 2 5 5 9P2 4 0 2 5 3 6 P3 4 0 5 4 0 11 P4 2 0 4 4 2 5P5 3 1 44 2 41、现在系统T0时刻是否处于安全状态？2、是否可以允许以下请求？(1)T1时刻：P2 Request2=(0,3,4)(2)T2时刻：P4 Request4=(2,0,1)(3)T3时刻：P1 Request1=(0,2,0)注：T0
2、 T1 T2 T3时刻是前后顺序，后一时刻是建立在前一时刻的基础上。解：由题设可知Need=Max-Allocation AvailableA=17-(2+4+4+2+3)=2(原有-分配) 同理AvailableB=3,AvailableC=3 可得T0时刻资源分配表如下所示（表中数据顺序均为A B C）：ProcessAllocationMaxNeedAvailableP1 2 1 2 5 5 93 4 72 3 3P2 4 0 2 5 3 61 3 4 P3 4 0 5 4 0 110 0 6 P4 2 0 4 4 2 52 2 1 P5 3 1 4 4 2 41 1 01、判断T0时刻
3、是否安全，需要执行安全算法找安全序列，过程如下表：WorkNeedAllocationWork+AllocationFinishP42 3 32 2 12 0 44 3 7TrueP34 3 70 0 64 0 58 3 12TrueP28 3 121 3 44 0 212 3 14 TrueP512 3 141 1 03 1 415 4 18TrueP115 4 183 4 72 1 217 5 20TrueT0时刻能找到一个安全序列P4,P3,P2,P5,P1,故T0时刻系统处于安全状态。2、判断T1 T2 T3时刻是否满足进程请求进行资源分配。（1）T1时刻，P2 Request2=(0
4、,3,4)/第一步 判断条件满足Request2=(0,3,4)=Need2(1,3,4)不满足Request2=(0,3,4)=Available(2,3,3)故系统不能将资源分配给它，此时P2必须等待。（2）T2时刻，P4 Request4=(2,0,1)/第一步 判断条件满足Request4=(2,0,1)=Need4(2,2,1) 满足Request4=(2,0,1)=Available(2,3,3)/第二步 修改Need、Available、Allocation的值 Available=Available-Request4= (0,3,2) Allocation4=Allocatio
5、n4+Request4=(4,0,5) Need4=Need4-Request4=(0,2,0)/第三步 执行安全算法，找安全序列(注解：先写上work，其初值是系统当前进行试分配后的Available(0,3,2) ，找五个进程中Need小于work的进程，比如Need4=Work满足，则将P4写在第一行的最前面，同时写出P4的Need和 Allocation，以此类推)WorkNeedAllocationWork+AllocationFinishP40 3 20 2 04 0 54 3 7TrueP24 3 71 3 44 0 28 3 9TrueP38 3 90 0 64 0 512 3
6、 14TrueP512 3 141 1 03 1 415 4 18TrueP115 4 183 4 72 1 217 5 20True/第四步 在此时刻（T2时刻）存在安全序列P4,P2,P3,P5,P1,则满足Request4请求，将Request4=(2,0,1)分配给P4。（3）T3时刻，P1 Request1=(0,2,0)/第一步 判断条件满足Request1=(0,2,0)=Need1(3,4,7) 满足Request1=(0,2,0)=Available(2,3,3)/第二步 修改Need、Available、Allocation的值 Available=Available-Re
7、quest1= (0,1,2) (T2时刻基础上) Allocation=Allocation1+Request1=(2,3,0) Need1=Need1-Request1=(3,2,7)/第三步 执行安全算法，找安全序列对于所有Needi均不小于Work(初值是Available (0,1,2)，找不到安全序列，故系统不能将资源分配给它，P1必须等待。归纳总结银行家算法解题总结为四步走：第一步：判断银行家算法中的条件，看是否满足，如果满足跳转第二步（判断条件）Requesti=NeediRequesti=Available第二步：试图分配，修改Need、Available、Allocation的值（修改NAA）Available=Available-Requesti Allocationi=Allocationi+RequestiNeedi=Needi-Requesti第三步：执行安全算法，找安全序列（找安全序列）第四步：找到了安全序列，说明此时系统满足进程Pi的请求Requesti系统不会进入不安全状态，可以将Requesti分配给进程Pi。（真分配）判断条件真分配修改NAA找安全序列
