基于回溯思想的银行家算法优化.doc

基于回溯思想的银行家算法优化
银行家算法是一个古典的测试系统安全状态的方法。所谓系统安全状态,是指系统能按某种顺序如<P1,P2,…,Pn>(称<P1,P2,…,Pn>序列为安全序列),来为每个进程分配其所需资源,直至最大需求,使每个进程都可顺序完成。若系统不存在这样一个安全序列,则称系统处于不安全状态。
传统的银行家算法思想:
(1)当进程首次申请资源,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量,则按当前的申请量分配资源,否则就推迟分配。
(2)当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。
传统的银行家算法能保证在任何时刻某一进程可以得到所需要的全部资源而执行到结束,执行结束后归还的资源加入到系统的剩余资源中。它只能保证当前的进程资源分配,而不能保证所有进程都能在有限时间内得到需要的全部资源。相反有可能将原来系统安全状态变成不安全状态。
下面举例说明银行家算法的资源分配规则。
系统有3类资源A,B,C,资源类A,B,C的总资源分别为10,5,7。现有5个进程P1,P2,…,P5,它们对各类资源的最大申请量和第一次请求分配资源量如下表所示。
进程
资源请求

最大需求量
第一次申请量
A
B
C
A
B
C
P1
7
5
3
0
1
0
P2
3
2
2
2
0
0
P3
9
0
2
3
0
2
P4
2
2
2
2
1
1
P5
4
3
3
0
0
2
如果进程P1,P2,P3,P4,P5依次向系统提出申请资源的请求,系统为进程P1和P2分配资源后剩余的资源为A类8个,B类4个,C类7个。当进程P3申请资源时由于A类资源只剩8个,不能满足P3对A类资源的最大需求量(9个)被拒绝,故对进程P3的资源分配需推迟。但是,对后继的进程P4和进程P5的请求可以接收并为它们分配资源。
如果申请资源的进程次序为P3,P1,P2,P5,P4,则系统都能为这5个进程进行第一次的分配,此时系统是安全的。现把分配后的情况列表如下所示。
进程
资源请求

尚存资源量
已占资源量
A
B
C
A
B
C
P1
7
4
3
0
1
0
P2
1
2
2
2
0
0
P3
6
0
2
3
0
2
P4
0
1
1
2
1
1
P5
4
3
1
0
0
2
通过上例,我们看到传统银行家算法确实能保证系统时时刻刻都处于安全状态,但实际操作上,存在一些问题:
1、逐条输入(逐条检测),在检测到该进程的时候可能是错误了,要求重新输入,这可能使本来是安全的系统,检测成不安全。
2、如果在输入最大需求量和第一次申请量后,键入进程序列,然后要求程序检测,可能会因为进程序列的序列较多,不能完全判断该系统是不安全的,此时必须检测所有的进程序列分配方案是不可行的。而检测系统的安全性也存在着一定的偶然性,当你输入进程序列后,可能是第一次就恰巧是可行的,也可