操作系统之银行家算法

约定不等于承诺〃 2022-08-20 13:21 223阅读 0赞

一.概念引入

银行家算法（ banker's algorithm ）由 Dijkstra于1965提出，关键是将死锁的问题演示为一个银行家贷款的模型，由于能用于银行系统的现金贷款而出名。一个银行家向一群客户发放信用卡，每个客户有不同的信用额度。每个客户可以提出信用额度内的任意额度的请求，直到额度用完后再一次性还款。银行家承诺每个客户最终都能获得自己需要的额度。所谓“最终”，是说银行家可以先挂起某个额度请求较大的客户的请求，优先满足小额度的请求，等小额度的请求还款后，再处理挂起的请求。这样，资金能够永远流通。所以银行家算法其核心是：保证银行家系统的资源数至少不小于一个客户的所需要的资源数。

银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但银行家算法在系统在进行资源分配之前(并不是真的不分配，这样就没法做了，只不过是试探性分配，不满足的话再恢复)，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指存在一个进程序列\{P1，…，Pn\}是安全的，不会死锁(至少两个线程占有某资源A，但是都不满足，剩余的资源A分配给谁仍然无法满足)，安全状态如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态，安全状态一定是没有死锁发生；不安全状态不存在一个安全序列，不安全状态不一定导致死锁。

本算法在理论上是出色的，能非常有效地避免死锁，但从某种意义上说，它缺乏实用价值，因为很少有进程能够在运行前就知道其所需资源的最大值，且进程数也不是固定的，往往在不断地变化（如新用户登录或退出），况且原来可用的资源也可能突然间变成不可用（如打印机、磁带机可能被损坏）。

二.算法原理

银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。每分配一次资源就测试一次是否安全，不是资源全部就位后才测试，注意理解checkError函数的循环顺序。

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。  
为保证资金的安全，银行家规定：

1.  当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客(试探性分配)
2.  顾客可以分期贷款，但贷款的总数不能超过最大需求量(可能一次并不能满足所需要的全部资源)
3.  当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款(不存在死锁)
4.  当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金(运行后释放)

操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能存在安全状态，则按当前的申请量分配资源，否则也要推迟分配。

三.算法的代码实现

详见：

[银行家算法的C实现][C]

[银行家算法的C++实现][C 1]

详址：

http://blog.csdn.net/zhouyelihua/article/details/6720346

http://blog.csdn.net/zhouyelihua/article/details/6721180

四.银行家算法例题：某系统有四种互斥资源R1,R2,R3和R4，可用资源数分别是3、5、6和8。假设在T0时刻有P1、P2、P3和P4四个进程，并且这些进程对资源的最大需求量和已分配资源数如下表所示，那么在T0时刻系统中R1、R2、R3和R4的剩余资源数分别为（1）。如果从T0时刻开始进程按 （2）  顺序逐个调度执行，那么系统状态是安全的。

![1349318661_5054.png][]

（1）A.3、5、6和8 B.3、4、2和2

C.0、1、2和1 D.0、1、0和1

（2）A.P1→P2→P4→P3 B.P2→P1→P4→P3

C.P3→P2→P1→P4 D.P4→P2→P3→P1

①求剩余资源数

用可用资源数减去那些已分配的资源数：

![1349318987_5818.png][]

R1=3-(1+0+1+1)=3-3=0

R2=5-(1+1+1+1)=5-4=1

R3=6-(2+2+1+1)=6-6=0

R4=8-(4+2+0+1)=8-7=1

所以（1）选择D。

②求出还需资源数

![1349320796_9357.png][]

分析，因为剩余的可用资源为（0,1,0,1），与上面的还需资源数比较，只有满足P3的还需资源数，所以，淘汰了ABD，选择C。

验证C.P3→P2→P1→P4

![1349321440_1145.png][]

[C]: http://blog.csdn.net/zhouyelihua/article/details/6720346
[C 1]: http://blog.csdn.net/zhouyelihua/article/details/6721180
[1349318661_5054.png]: https://img-my.csdn.net/uploads/201210/04/1349318661_5054.png
[1349318987_5818.png]: https://img-my.csdn.net/uploads/201210/04/1349318987_5818.png
[1349320796_9357.png]: https://img-my.csdn.net/uploads/201210/04/1349320796_9357.png
[1349321440_1145.png]: https://img-my.csdn.net/uploads/201210/04/1349321440_1145.png