😋 发布且更更新于个人小破站：进去瞅瞅

银行家算法介绍

之所以叫做银行家算法是因为该算法原本是为银行系统设计的，以确保银行在发放现金贷款的时候，不会发生不能满足所有客户要求的情况。在 OS 中也可以用来避免死锁。

为了实现银行家算法，每一个进程在进入系统时，它必须申明在运行过程中可能需要煤种资源类型的最大单元数目，其数目不能超过系统所拥有的资源总量。当进程请求一组资源的时候，系统必须首先确定是否有足够的资源分配给该进程。若有，再进一步计算，在将这些资源分配给进程之后，是否会使系统处于不安全状态，如果不会，才将资源分配给他，否则让进程等待。

为了实现银行家算法，在系统中必须要设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。

1. 可利用资源向量 Available ，它是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源的数目，其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源的分配和回收而动态地改变。如果Available[j]=k，表是系统中现有 Rj 类资源 k 个。

2. 最大需求矩阵 Max，这是一个 n×m 的矩阵，它定义了系统中 n 个进程中的每一个进程对 m 类资源的最大需求。如果Max[i,j]=k，表示进程 i 需要 Rj 类资源的最大数目为 k 。

3. 分配矩阵 Allocation ，这是一个 n×m 的矩阵，它定义了系统中的每类资源当前一分配到每一个进程的资源数。如果Allocation[i,j]=k，表示进程 i 当前已经分到 Rj 类资源的数目为 k。Allocation[i] 表示进程 i 的分配向量，有矩阵 Allocation 的第 i 行构成。

4. 需求矩阵 Need ，这是一个n×m的矩阵，用以表示每个进程还需要的各类资源的数目。如果Need[i,j]=k，表示进程 i 还需要 Rj 类资源 k 个，才能完成其任务。Need[i] 表示进程 i 的需求向量，由矩阵 Need 的第 i 行构成。

上述三个矩阵间存在关系：Need[i,j]=Max[i,j]-Allocation[i,j];

银行家算法

设 Request 是进程Pi的请求向量，如果 Requesti[j] = K，表示进程 Pi 需要 K 个 Rj 类型的资源。当 Pi 发出资源请求后，系统按下述步骤进行检査:

1. 如果 Requesti[j] ≤ Need[i,j]便转向步骤 2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。

2. 如果 Requesti[j] ≤ Available[j]，便转向步骤 3；否则，表示尚无足够资源，Pi须等待。

3. 系统试探着把资源分配给进程 Pi，并修改下面数据结构中的数值

   Available[j] = Available[j] - Requesti[j]; // 分配出去
   Allocation[i,j] = Allocation[i,j] + Requesti[j]; // 获得资源
   Need[i,j] = Need[i,j] - Requesti[j];　　　　// 需求减少
   

4. 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi ，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程 Pi 等待。

安全性算法

系统所执行的安全性算法可描述如下:

1. 设置两个向量：① 工作向量 Work ，它表示系统可提供给进程继续运行所需的各类资源数目，它含有 m 个元素，在执行安全算法开始时，Work = Available；② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。默认全部为 False。

2. 从进程集合中找到一个能满足下述条件的进程

   • Finish[i] = False;

   • Need[i] ≤ Work; （向量比较）

   若找到，执行步骤 3，否则，执行步骤 4 ；

3. 当进程 Pi 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
   Work = Work + Allocation[i] （向量运算）
   Finish[i] = True;
   转到步骤 2

4. 如果所有进程的 Finish[i] = True都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

具体实现

相信上过这门的的同学都已经对这个算法有了一定的了解，那么按照书上面的步骤来写代码的话问题也不是很大，但是在实现的时候需要很多的细节，相信这篇文章会在你一筹莫展的提供一些思路。

数据结构的构建

通过前面的介绍我们已经了解到，「银行家算法」至少要涉及到 4 个数据结构，所以第一步就是如何获取这四个数据结构；

def main():"""主循环算法"""m = int(input("输入资源种类数 m: "))temp = input("输入进程数资源，空格隔开：").split()available = np.array(temp, dtype=int)n = int(input("输入进程数 n: "))max_table = np.zeros([n, m], dtype=int)allocation = np.zeros([n, m], dtype=int)# 输入最大需求资源for i in range(n):temp = input("输入进程 P{} 的最大需求向量 Max：".format(i)).split()max_table[i] = np.array(temp, dtype=int)if (available < max_table[i]).any():print("[ERROR] 输入有误，重新输入")i -= 1# 输入已分配资源for i in range(n):temp = input("输入进程 P{} 的已分配资源 Max：".format(i)).split()allocation[i] = np.array(temp, dtype=int)if (max_table[i] < allocation[i]).any():print("[ERROR] 输入有误，重新输入")i -= 1# 导入测试数据，不用一次次手动输入# available, max_table, allocation = loadTestData()need = max_table - allocation# 剩余部分代码暂时省略，后面会介绍

在测试的时候一次次测试比较麻烦，其实最方便的办法就是预先定义一份测试数据，然后使用 loadTestData() 来获取，下面的这一份数据是从书本上摘抄的，可以用来作为测试数据。

def loadTestData():return (np.array([10, 5, 7], dtype=int),np.array([[7, 5, 3],[3, 2, 2],[9, 0, 2],[2, 2, 2],[4, 3, 3]], dtype=int),np.array([[0, 1, 0],[2, 0, 0],[3, 0, 2],[2, 1, 1],[0, 0, 2]], dtype=int))

银行家算法

银行家算法实际上就是一个循环，循环获取资源请求，然后对资源请求进行判断，判断该请求的合法性以及安全性：

# main() 函数内部，接上
while (need != 0).any():proc_ind, req = input("输入请求，如：P1, 1 0 1: ").split(',')proc_ind = int(proc_ind[1:])req = np.array(req.split(), dtype=int)# 判断合法性if (req > max_table[proc_ind]).any():print("[ERROR] 输入有误，重新输入")# 判断安全性else:available -= reqallocation[proc_ind] += reqneed[proc_ind] -= req# security 是安全性算法，下面会解释到if security(available.copy(), need, allocation):# printTable 是打印当前状态，具体实现可以看文末完整代码printTable(available, max_table, allocation, need)continueelse:print("[ERROR] 不安全，不能分配")available += reqallocation[proc_ind] -= reqneed[proc_ind] += req

安全性算法

上面的代码中 security(available.copy(), need, allocation) 是安全性算法，因为 avaiable 传到该函数之后会被当做 work 变量使用，会导致该数据被修改，所以这里采用的是 avaiable.copy()来复制一份；

def security(work, need, allocation):"""安全性算法"""n = need.shape[0]finish = np.array([False] * n, dtype=bool)while not(finish.all()):flag = Falsefor i in range(n):if not finish[i] and (need[i] <= work).all():print("P{}".format(i), end=' -> ')flag = Truework += allocation[i]finish[i] = Truebreakif not flag:return Falseprint()return True

在安全性算法里面，是按照书上的流程写出来的，只不过在判断是否安全的时候，添加了一个 flag 变量，当一次完整的 for 循环结束之后，flag 为 False，也就是说没有找到满足条件的进程，就代表此时这个分配是不安全的，当所有的进程都为 True 之后才是安全的。

运行结果

完整代码代码以及参考资料

import numpy as npdef security(work, need, allocation):"""安全性算法"""n = need.shape[0]finish = np.array([False] * n, dtype=bool)while not(finish.all()):flag = Falsefor i in range(n):if not finish[i] and (need[i] <= work).all():print("P{}".format(i), end=' -> ')flag = Truework += allocation[i]finish[i] = Truebreakif not flag:return Falseprint()return Truedef printTable(available, max_table, allocation, need):"""输出表格"""print("=="*30)print("进程\tMax\tAllo\tNeed")for i in range(5):print("P{}\t{}\t{}\t{}".format(i, max_table[i], allocation[i], need[i]))print("当前剩余资源:", available)def loadTestData():"""导入测试数据"""return (np.array([10, 5, 7], dtype=int),np.array([[7, 5, 3],[3, 2, 2],[9, 0, 2],[2, 2, 2],[4, 3, 3]], dtype=int),np.array([[0, 1, 0],[2, 0, 0],[3, 0, 2],[2, 1, 1],[0, 0, 2]], dtype=int))def main():"""主循环算法"""m = int(input("输入资源种类数 m: "))temp = input("输入进程数资源，空格隔开：").split()available = np.array(temp, dtype=int)n = int(input("输入进程数 n: "))max_table = np.zeros([n, m], dtype=int)allocation = np.zeros([n, m], dtype=int)# 输入最大需求资源for i in range(n):temp = input("输入进程 P{} 的最大需求向量 Max：".format(i)).split()max_table[i] = np.array(temp, dtype=int)if (available < max_table[i]).any():print("[ERROR] 输入有误，重新输入")i -= 1# 输入已分配资源for i in range(n):temp = input("输入进程 P{} 的已分配资源 Max：".format(i)).split()allocation[i] = np.array(temp, dtype=int)if (max_table[i] < allocation[i]).any():print("[ERROR] 输入有误，重新输入")i -= 1# 导入测试数据，不用一次次手动输入# available, max_table, allocation = loadTestData()need = max_table - allocation# 计算出剩余资源for i in allocation:available -= iprintTable(available, max_table, allocation, need)while (need != 0).any():proc_ind, req = input("输入请求，如：P1, 1 0 1: ").split(',')proc_ind = int(proc_ind[1:])req = np.array(req.split(), dtype=int)# 判断合法性if (req > max_table[proc_ind]).any():print("[ERROR] 输入有误，重新输入")# 判断安全性else:available -= reqallocation[proc_ind] += reqneed[proc_ind] -= reqif security(available.copy(), need, allocation):printTable(available, max_table, allocation, need)continueelse:print("[ERROR] 不安全，不能分配")available += reqallocation[proc_ind] -= reqneed[proc_ind] += reqif __name__ == '__main__':main()

[1] 西安电子科技大学出版社《计算机操作系统（第四版）》汤子瀛等编著