博客

* 银行家算法解读

**Dijkstra, 1965年提出银行家算法。

**• 一个银行家把他的固定资金（capital）代给若干顾客。只要不出现一个顾客借走所有资金后还还不够，银行家的资金应是安全的。银行家需要一个算法保证借出去的资金在有限时间内可收回。
**• 假定顾客分成若干次进行；并在第一次借款时，能说明他的最大借款额。

• 具体算法：
– 顾客的借款操作依次顺序进行，直到全部操作完成；
– 银行家对当前顾客的借款操作进行判断， 以确定其安全性（能否支持顾客借款，直 到全部归还）；
– 安全时，贷款；否则，暂不贷款。

银行家算法的特点:
• 允许互斥、部分分配和不可抢占，可提高资源利用率；
• 要求事先说明最大资源要求，在现实中很困难；**

*示例
某系统有4类资源，R1,R2,R3,R4, 有5个并发进程P0,P1,P2,P3,P4。各进程的最大资源请求和已分配的资源矩阵以及当前资源的剩余向量如下表。


判断系统当前是否处于安全状态。

解答：
Step1:建立当前各进程需求矩阵（最大需求量减去已分配向量）

Step2:确定执行顺序
1、P0已获得所需的全部资源，执行后释放资源（0,0,1,2），则当前资源剩余量更新为：

2、此时可以执行P2或P3，选择一种即可。P2获取所需资源（1,0,0,2），执行P2时，

执行P2后， 释放资源（2,3,5,6），

3、分配资源（0,0,2,0）给P3，
P3执行后，释放资源（0,6,5,2），

4、P1或P4执行，选择一种即可。P1执行，分配资源（0,7,5,0）

P1执行后，释放资源（1,7,5,0）

5、P4执行，分配资源（0,6,4,2）

P4执行后，释放资源（0,6,5,6）

Step3:结论，未发生死锁，安全。
检验：