在银行家算法中,若出现下列的资源分配情况:试问:ProcessAllocationNeedAvailableP00 0 3 20 0 1 21 6 2 2P11 0 0 01 7 5 0P21 3 5 42 3 5 6P30 3 3 20 6 5 2P40 0 1 40 6 5 6(1)该状态是否安全?(2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
在银行家算法中,若出现下列的资源分配情况:
试问:
Process
Allocation
Need
Available
P0
0 0 3 2
0 0 1 2
1 6 2 2
P1
1 0 0 0
1 7 5 0
P2
1 3 5 4
2 3 5 6
P3
0 3 3 2
0 6 5 2
P4
0 0 1 4
0 6 5 6
(1)该状态是否安全?
(2)若进程P2提出请求Request(1,2,2,2)后,系统能否将资源分配给它?
题目解答
答案
答:这是5个进程,对4种资源的分配。Allocation是各进程已获得的资源,Need是尚缺的资源,Available是系统剩余的资源。
(1) 该状态是否安全?
进行安全性检查:
Process | Work | Need | Allocation | Work+Allo | Finish |
ABCD | ABCD | ABCD | ABCD | ||
P0 | 1 6 2 2 | 0 0 1 2 | 0 0 3 2 | 1 6 5 4 | True |
P3 | 1 6 5 4 | 0 6 5 2 | 0 3 3 2 | 1 9 8 6 | True |
P4 | 1 9 8 6 | 0 6 5 6 | 0 0 1 4 | 1 9 9 10 | True |
P1 | 1 9 9 10 | 1 7 5 0 | 1 0 0 0 | 2 9 9 10 | True |
P2 | 2 9 9 10 | 2 3 5 6 | 1 3 5 4 | 3 12 14 14 | True |
在该时刻存在着一个安全序列{P0,P3,P4,P1,P2},所以该状态安全。
(2) 若进程P2提出请求Request(1,2,2,2)后,首先要运行银行家算法的第一部分,进行预分配(模拟分配)。
①Request2(1,2,2,2)≤Need2(2,3,5,6),该条件满足,请求合法。
②Request2(1,2,2,2)≤Available (1,6,2,2),该条件满足。
③系统暂先假设可为P2分配资源,并修改相关数据,预分配后系统状态如下:
Process | Allocation | Need | Available |
P0 | 0 0 3 2 | 0 0 1 2 | 0 4 0 0 |
P1 | 1 0 0 0 | 1 7 5 0 | |
P2 | 3 5 7 6 | 1 1 3 4 | |
P3 | 0 3 3 2 | 0 6 5 2 | |
P4 | 0 0 1 4 | 0 6 5 6 |
④然后运行银行家算法的第二部分,找安全序列。很显然,Available(0,4,0,0)不能满足任何一个进程的Need,不存在安全状态。所以,P2提出的请求Request(1,2,2,2)现在不能分配。
解析
本题主要考察银行家算法中安全状态的判断及资源分配的可行性分析，具体涉及两个核心问题：一是判断当前系统状态是否安全，二是判断进程提出资源请求后系统能否分配资源并保持安全。
（1）判断当前状态是否安全
安全状态的判断步骤：从Available资源出发，寻找Need ≤ Work的未完成进程，将其Allocation加入Work，标记为Finish，重复直至所有进程完成或无法找到可完成进程。
步骤如下：
- 初始状态：
Work = Available = (1,6,2,2)，Finish均为False。 - 选择P0：
Need0=(0,0,1,2) ≤ Work=(1,6,2,2)，分配后Work = Work+Allocation0=(1+0,6+0,2+++3,2+2）=(1,6,5,4)，Finish0=True。 - 选择P3：
Need3=(0,6,5,2) ≤ Work=(1,6,5,4)，分配后Work=(1+0,6++3,5+3,4+2)=(1,9,8,6)，Finish3=True。 - 选择P4：
Need4=(0,6,5,6) ≤ Work=(1,9,8,6)，分配后Work=(1+0,9+0,8+1,6+4)=(1,9,9,10)，Finish4=True。 - P1：
Need1=(1,7,5,0) ≤ Work=(1,9,9,10)，分配后=(2,9,9,10)，Finish1=True。 - P2：
Need2=(2,3,5,6) ≤ Work=(2,9,9,10)，分配后=(3,12,14,14)，Finish2=True。
所有进程Finish均为True，存在安全序列{P0,P3,P4,P1,P2}，故当前状态安全。
（2）判断P2请求Request(1,2,2,2)是否可分配
银行家算法需两步：预分配+安全性检查。
步骤1：预分配可行性检查
- **请求合法性：
Request2=(1,2,2,2) ≤ Need2=(2,3,5,6)（满足）； - 系统资源足够：
Request2 ≤ Available=(1,6,2,2)（满足）。
步骤2：预分配后状态
Allocation2变为(1+1,3+2,5+2,4+2)=(2,5,7,6)？（原答案此处写为3,5,7,6，应为笔误，正确为2,5,7,6）；Need2变为(2-1,3-2,5-2,6-2)=(1,1,3,4)；Available变为(1-1,6-2,2-2,2-2)=(0,4,0,0)。
步骤3：安全性检查
预分配后Available=(0,4,0,0)，检查所有进程Need：
- P0: Need=(0,0,1,2)→A=0≤0，但D=2>0→不满足；
- P1: Need=(1,7,5,0)→A=1>0→不满足；
- P2: Need=(1,1,3,4)→D=4>0→不满足；
- P3: Need=(0,6,5,2)→B=6>4→不满足；
- P4: Need=(0,6,5,6)→B=6>4→不满足。
无进程可完成，系统进入不安全状态，故拒绝分配。