银行家算法 - 操作系统

¶介绍[^1]

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。
它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

¶背景[^1]

在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。
银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。

¶算法

对于如图的资源分配表:
Allocation(已经分配出去的资源), MAX(最多需要多少资源), Available(空闲资源)

首先计算出Need (Need = MAX - Allocation), 即还需要多少资源:

然后加一个全为False的字段(FINISH, 表示当前进程是否满足, 也可以不加,记着就行):

接下来找到 Need 比 Available 小的(即空闲资源可以满足当前进程所需):

P2进程的需求能够得到满足, 所以现在满足它, P2已经完成了, 然后就要回收他的资源:

注意加的是Allocation的值,即回收的是已经分配给该进程的那部分资源, 而不是进程所需要的(Need)

P2回收完成, 标记Finish:

以此类推直到Finish全为True即为安全状态(进程完成的顺序即为安全序列):

¶参考资料

[^1]: WiKi: 银行家算法