引言
说起银行家算法,实际上是自己本科计算机操作系统的1个课程设计。由于在项目中用到相关的内容,因此便简单进行下回顾。
在并发编程中,当多个进程或线程对某个不可抢占资源进行争夺时会引起死锁的问题,而使用银行家算法主要的目的是为了避免系统产生死锁,对于死锁我们可以将其理解为坏账。
银行家算法思想
银行家算法原本是为银行系统设计的,确保银行在发放现金贷款时,不会发生不能满足所有客户需要的情况。而这里,我们通过借鉴该算法来避免死锁的发生。
在银行系统中,当客户到银行贷款时,需要提交自己期望的最大金额申请,其数目不能超过当前银行所拥有的现金总额。而银行在接收到客户的申请后,需要首先确定当前是否有足够的现金可以分配给该客户。然后,需要进一步计算在将这些金额分配给该客户后,银行是否还有剩余可用的现金可以提供给下1个客户。如果还有剩余可用的现金,才会批准该客户的贷款申请,否则延缓该客户的请求,让其进行等待。
银行家算法实例
我们假定有甲乙丙这3个客户和3种资金来源A、B、C,而每种资金的数量分别是10,5,7。每个客户首先需要告诉银行每种资金需要的数目,而银行根据实际情况进行分配发放。为了银行的周转,并不会一次性将所有资金都分配给客户,当客户提出自己的分配申请后,银行会根据业务情况选择性进行分配。
假设在某一时刻其资金分配情况为:
| 客户/资金情况 | 最大需求 | 已分配 | 仍需要 | 当前可用 |
| 甲 | 7 5 3 | 0 1 0 | 7 4 3 | 4 4 5 |
| 乙 | 3 2 2 | 2 0 0 | 1 2 2 | - |
| 丙 | 9 0 2 | 4 0 2 | 6 0 0 | - |
其中客户甲对每种资金的需求分别是7万、5万和3万,而当前银行方面每种资金已经分别给他分配发放了0万、1万和0万。那么客户甲还需要的资金为:
仍需要 = 最大需求 - 已分配
以此类推,当前每种资金已分配的总额分别为6万、1万和2万,因此当前银行每种资金分别可用的还有4万、4万和5万。
此时如果客户乙提出要下一期贷款发放要求,需要每种资金数量分别为1万、0万、2万。此时系统根据银行家算法会进行如下检查:
- 客户乙提交的每种资金的数量是否小于他当前仍然需要的金额
- 客户乙提交的每种资金的数量是否小于当前银行每种资金可用的金额
如果通过上述检验后,系统会假定批准客户乙的申请,并对客户乙已分配、仍需要及系统当前可用资金情况进行修改,从而得到类似下表的结果。
| 客户/资源 | 仍可用 | 仍需要 | 已分配 | 回收后可用 | 是否可行 |
| 乙 | 3 4 3 | 0 2 0 | 3 0 2 | 6 4 5 | 是 |
| 丙 | 6 4 5 | 6 0 0 | 4 0 2 | 10 4 7 | 是 |
| 甲 | 10 4 7 | 7 4 3 | 0 1 0 | 10 5 7 | 是 |
银行尝试将每种资金按照数量1,0,2分配给客户乙,此时可用资源数量为(4,4,5)-(1,0,2)=(3,4,3)。 而当客户乙将已经分配的资金还款后,此时银行每种资金可用的数量为(3,4,3)+(3,0,2)=(6,4,5)。
此时,可以看到满足客户丙的贷款要求,此时可以借款给客户丙。而当客户丙偿还之前的贷款金额后,此时银行每种资金可用的数量为(10,4,7)。
这个时候,就满足客户甲的贷款要求了,从而得到1个可行的方案。因此,银行可以立即批准客户乙的申请要求。
Java的实现
下面我们通过Java程序来演示下银行家算法的过程,对上述过程进行演示。
我们编写1个Banker的类,其内容为:
import java.util.ArrayList; import java.util.Scanner; public class Banker { int[] Available = {10,5,7}; int[][] Max = new int[3][3]; int[][] Allocation = new int[3][3]; int[][] Need = new int[3][3]; int[][] Request = new int[3][3]; int[] Work = new int[3]; String[] customers = {"甲","乙","丙"}; int num = 0; Scanner in = new Scanner(System.in); public Banker() { setMax(); setAllocation(); } public void setMax() { //初始化资金需求量 for(int i=0;i<3;i++) { System.out.println(String.format("请输入客户%s的最大资金需求量: ", customers[i])); for(int j=0;j<3;j++) { Max[i][j] = in.nextInt(); } } } public void setAllocation() { //初始化资金分配情况 for(int i=0;i<3;i++) { System.out.println(String.format("请输入客户%s的分配资源: ", customers[i])); for(int j=0;j<3;j++) { Allocation[i][j] = in.nextInt(); } } //设置可用资源 for(int i=0;i<3;i++) { for(int j=0;j<3;j++) { Available[i] = Available[i] - Allocation[j][i]; Need[i][j] = Max[i][j] - Allocation[i][j]; } } } public void print_variable() { //打印资金分配情况 System.out.println("资金分配情况: "); System.out.println("客户 | 最大需求| 已分配| 仍需要 | 当前可用 "); for(int i=0;i<3;i++) { System.out.print(String.format("%s ",customers[i])); System.out.print(" | "); for(int j=0;j<3;j++) { System.out.print(String.format("%d ", Max[i][j])); } System.out.print(" | "); for(int j=0;j<3;j++) { System.out.print(String.format("%d ", Allocation[i][j])); } System.out.print(" | "); for(int j=0;j<3;j++) { System.out.print(String.format("%d ", Need[i][j])); } System.out.print(" | "); for(int j=0;j<3;j++) { System.out.print(String.format("%d ", Available[j])); } System.out.println(); } } public void sendRequest() { //客户提出申请 System.out.println("请输入请求资金的用户编号: "); num = in.nextInt(); System.out.println("请输入请求各种资金的数量: "); for(int j=0;j<3;j++) { Request[num][j] = in.nextInt(); } int[] req = Request[num]; System.out.println(String.format("客户%s对各资金请求(%d,%d,%d)", customers[num],req[0],req[1],req[2])); BankerAlgorithm(); } public void BankerAlgorithm() { //银行家算法 boolean T = true; int[] req = Request[num]; int[] need = Need[num]; if(req[0]<=need[0]&&req[1]<=need[1]&&req[2]
在这里我们初始化了4个二维数组变量Max、Allocation、Need、Request用于存储系统最大需求、已分配资金、仍需资金及请求的资金。在该类调用时需要用户输入相关的数值进行初始化操作。
而在初始化相关数值后,当用户输入请求的客户名称及资金数量后,调用sendRequest方法发送请求,之后调用银行家算法实现的BankerAlgorithm方法进行检查,并返回相关信息。
最后是编写对应的测试类BankTest:
import java.util.Scanner; public class BankTest { public static void main(String[] args) { boolean choose = true; String c; Scanner in = new Scanner(System.in); Banker bank = new Banker(); while(choose==true) { bank.sendRequest(); System.out.println("您是否还要进行请求：y/n?"); c = in.nextLine(); if(c.endsWith("q")||c.endsWith("n")) { choose = false; } } } }
我们通过Scanner从窗口中读取输入的数值,然后调用sendRequest方法模拟发送客户的请求。其中,客户甲乙丙对应的编号分别为0,1,2。系统根据银行家算法进行检查,并反馈其相关信息。
其结果如下所示:
