银行家算法

Miracle 2017年8月15日20:32:53IT相关银行家算法已关闭评论1,77221390字阅读4分38秒阅读模式

转自网页文章源自联网快讯-https://x1995.cn/1003.html

目的:避免死锁的产生。文章源自联网快讯-https://x1995.cn/1003.html

算法思想:文章源自联网快讯-https://x1995.cn/1003.html

1、假分配检测:Request < Need文章源自联网快讯-https://x1995.cn/1003.html

Request < Available文章源自联网快讯-https://x1995.cn/1003.html

2、安全序列检测算法文章源自联网快讯-https://x1995.cn/1003.html

 文章源自联网快讯-https://x1995.cn/1003.html

实例列举:文章源自联网快讯-https://x1995.cn/1003.html

某系统有R1,R2,R3共3中资源,在T0时刻P0,P1,P2,P3和P4这5个进程对资源的占用和需求情况如下表1,此时系统的可用资源向量为(3,3,2)。试问:文章源自联网快讯-https://x1995.cn/1003.html

1、T0时刻系统是否存在安全序列?文章源自联网快讯-https://x1995.cn/1003.html

2、P1请求资源:P1发出请求向量Request(1,0,2),系统是否接受该请求?请使用银行家算法检查文章源自联网快讯-https://x1995.cn/1003.html

3、P4请求资源:P4发出请求向量Request(3,3,0),系统按银行家算法检查.文章源自联网快讯-https://x1995.cn/1003.html

4、P0请求资源:P0发出请求向量Request(0,2,0),系统按银行家算法检查.文章源自联网快讯-https://x1995.cn/1003.html

表1 T0时刻的资源分配表文章源自联网快讯-https://x1995.cn/1003.html

MAXAllocationNeedAvailable
P07 5 30 1 07 4 3 3 3 2
P13 2 22 0 01 2 2
P29 0 23 0 26 0 0
P32 2 22 1 10 1 1
P44 3 30 0 24 3 1

 文章源自联网快讯-https://x1995.cn/1003.html

an:文章源自联网快讯-https://x1995.cn/1003.html

1、T0时刻系统是否存在安全序列?文章源自联网快讯-https://x1995.cn/1003.html

Available > Need1 ----> 可用资源分配给P1,直到P1进程执行完成,然后Available = Available + Allocation1 = (5,3,2)文章源自联网快讯-https://x1995.cn/1003.html

Available > Need3 -----> 可用资源分配给P3,直到P3进程执行完成,然后Available = Available + Allocation3 = (7,4,3)文章源自联网快讯-https://x1995.cn/1003.html

Available> Need4.....文章源自联网快讯-https://x1995.cn/1003.html

得到安全序列为:P1,P3,P4,P2,P0文章源自联网快讯-https://x1995.cn/1003.html

2、P1请求资源:P1发出请求向量Request(1,0,2),系统是否接受该请求?请使用银行家算法检查文章源自联网快讯-https://x1995.cn/1003.html

第一步(假分配检查):把Request分配给P1,必须满足Request要小于Available,Request要小于Need。文章源自联网快讯-https://x1995.cn/1003.html

Request(1,0,2)< Available(3,3,2)文章源自联网快讯-https://x1995.cn/1003.html

Request(1,0,2)< Need(1,2,2)文章源自联网快讯-https://x1995.cn/1003.html

因为满足第一步检查,进入第二层检查(安全序列检查)。文章源自联网快讯-https://x1995.cn/1003.html

第二步(安全序列检查):建立安全性检查表文章源自联网快讯-https://x1995.cn/1003.html

WorkNeedAllocationWork+AllocationFinish
P12 3 00 2 03 0 2

如果 Work > Need ,那么执行Work+Allocation,得到:文章源自联网快讯-https://x1995.cn/1003.html

WorkNeedAllocationWork+AllocationFinish
P12 3 00 2 03 0 2 5 3 2 true
5 3 2

找到Need<Work的进程,如果没有找到这样的进程而进程集合没有执行,则算法返回,得到不存在安全序列结果,否则继续执行该算法。文章源自联网快讯-https://x1995.cn/1003.html

这里我们找到了P3进程。修改安全序列检查表:文章源自联网快讯-https://x1995.cn/1003.html

WorkNeedAllocationWork+AllocationFinish
P12 3 00 2 03 0 2 5 3 2 true
P35 3 20 1 12 1 1 7 4 3 true
7 4 3

这样一直执行到所有的进程到完成,以完成该安全序列检查表:文章源自联网快讯-https://x1995.cn/1003.html

WorkNeedAllocationWork+AllocationFinish
P12 3 00 2 03 0 2 5 3 2 true
P35 3 20 1 12 1 1 7 4 3 true
P47 4 34 3 10 0 2 7 4 5 true
P07 4 57 4 30 1 0 7 5 5 true
P27 5 56 0 03 0 210 5 7 true

这样就找到了整个安全序列为:P1,P3,P4,P0,P2文章源自联网快讯-https://x1995.cn/1003.html

3、4小问也是同样的解题过程。这里不赘述...文章源自联网快讯-https://x1995.cn/1003.html

继续阅读
Miracle
  • 本文由 发表于 2017年8月15日20:32:53