【摘要】银行家算法 : java实现(基于课本)
属性
需要在构造方法中传入的
整型Resources , 用于表名可用资源种类数量, 共有几种资源整型Process, 用于表名进程数量, 共有几个进程整型数组Available, 用于表名每类可用资源的数量整形矩阵Max, 用于表名每个进程所需的总的资源量整型矩阵Allocation, 用于表示每个进程目前已经拥有的每类…

银行家算法 : java实现(基于课本)

属性

需要在构造方法中传入的

整型Resources , 用于表名可用资源种类数量, 共有几种资源
整型Process, 用于表名进程数量, 共有几个进程
整型数组Available, 用于表名每类可用资源的数量
整形矩阵Max, 用于表名每个进程所需的总的资源量
整型矩阵Allocation, 用于表示每个进程目前已经拥有的每类资源资源的资源数量

其他属性

整形矩阵Need, 用于表示每个进程目前需要的每类资源资源的资源数量
Available2, Allocation2, Need2, 分别时以上三个数据结构的备份, 用于安全性检测, 不破环原数据结构
整型数组work, 用于表示目前可用的资源数(在检测安全性时使用)
布尔数组finish, 安全性检测时每一个进程完成后, 对应的索引改为true

方法

public

BankerAlgorithm() 构造方法
Algorithm() 银行家算法
UpdateResources() 更新数据的算法

private

setNeed() 构造Need矩阵的方法
reSetNeed() 刷新需求矩阵的方法
reCopying() 复制备份的方法
rebuild() 用于初始化work和finish的方法
reFinish() 用于刷新work和finish数组的方法
able() 用于判断work中的值够不够减的方法
isSecurity() 用于判断请求是不是安全的方法
findThePath() 如果安全,用于排列出一个安全组合的方法

大体执行流程

传入参数调用构造方法后, 使用银行家算法Algorithm(), 传入请求参数(那个进程申请什么资源多少)

Algorithm()调用setNeed()建立Need矩阵, 经过两部初始判断后调用isSecurity()方法判断请求是否安全,

isSecurity()建立work和finish, 通过判断后返回布尔值给Algorithm(), 如果安全就调用findThePath()找到安全组合, 并输出

测试类中可选择更新数据, 也可选择不更新数据UpdateResources()

需要注意

所有的属性貌似在对象创建之初先于构造方法创建,
也就是说如果属性数组的大小由其他数值属性(需要被构造方法赋值)来确定时,
因为在构造方法赋值前,所使用的初始数值为0, 所以就是说属性数组大小为零,
所以任何此类数组属性都可由动态数组代替(ArrayList/LinkedList).

代码

算法类

import java.util.ArrayList;

public class BankerAlgorithm { public int Resources; //资源数量 public int Process; //进程数量 public int[] Available; //可用资源向量 public int[][] Max; //最大需求矩阵 public int[][] Allocation; //分配矩阵 public BankerAlgorithm(int Resources, int Process, int[] Available, int[][] Max, int[][] Allocation){ //构造方法 this.Process = Process; this.Resources = Resources; this.Allocation = Allocation; this.Max = Max; this.Available = Available; } /** * 所有的属性貌似在对象创建之初先于构造方法创建, * 也就是说如果属性数组的大小由其他数值属性(需要被构造方法赋值)来确定时, * 因为在构造方法赋值前,所使用的初始数值为0,所以就是说属性数组大小为零 * 所以任何此类数组属性都可由动态数组代替(ArrayList/LinkedList) * */ private final ArrayList<ArrayList<Integer>> Need = new ArrayList<>(); private void setNeed(){ for(int i=0;i<Process;i++){ Need.add(i,new ArrayList<>()); for(int j=0;j<Resources;j++){ Need.get(i).add(j,(Max[i][j] - Allocation[i][j])); } } } private void reSetNeed(){ Need.clear(); setNeed(); } //Available Allocation Need的备份 private final ArrayList<Integer> Available2 = new ArrayList<>(); private final ArrayList<ArrayList<Integer>> Allocation2 = new ArrayList<>(); private final ArrayList<ArrayList<Integer>> Need2 = new ArrayList<>(); private void reCopying(){ //用于复制备份 Available2.clear(); Allocation2.clear(); Need2.clear(); for(int i=0;i<Process;i++){ Allocation2.add(i,new ArrayList<>()); Need2.add(i,new ArrayList<>()); for(int j=0;j<Resources;j++){ Allocation2.get(i).add(j,Allocation[i][j]); Need2.get(i).add(j,Need.get(i).get(j)); } } for(int i=0;i<Resources;i++){ Available2.add(i,Available[i]); } } public void Algorithm(int i, int[] Request){ //进程i向系统提出资源请求 reSetNeed(); boolean f = true; //要求量小于需求量 for(int j=0;j<Resources;j++){ if (Request[j] > Need.get(i).get(j)) { f = false; break; } } if(f){ boolean f2 = true; //要求量小于剩余量 for(int j=0;j<Resources;j++){ if (Request[j] > Available[j]) { f2 = false; break; } } if(f2){ reCopying(); for(int j=0;j<Resources;j++){ Available2.set(j,Available2.get(j)-Request[j]); Allocation2.get(i).set(j,(Allocation2.get(i).get(j)+Request[j])); Need2.get(i).set(j,(Need2.get(i).get(j)-Request[j])); } if(isSecurity()){ ArrayList<Integer> path = findThePath(); for(int p:path) System.out.print("p"+p+" "); }else { System.out.println("此请求不安全!"); } }else System.out.println("请求不通过: 请求资源数量大于现有资源量!"); }else System.out.println("请求不通过: 申请资源数量大于自身所需!"); } //work和finish private final ArrayList<Integer> work = new ArrayList<>(); private final ArrayList<Boolean> finish = new ArrayList<>(); private void rebuild(){ //用于初始化work和finish for(int i=0;i<Resources;i++){ work.add(Available2.get(i)); } for(int i=0;i<Process;i++) finish.add(false); } private void reFinish(){ //用于刷新work和finish数组 work.clear(); for(int i=0;i<Resources;i++){ work.add(Available2.get(i)); } finish.clear(); for(int i=0;i<Process;i++) finish.add(false); } private boolean able(int i){ //用于判断work中的值够不够减 boolean f = true; for(int j=0;j<Resources;j++){ if (work.get(j) < Need2.get(i).get(j)) { f = false; break; } } return f; } private boolean isSecurity(){ //用于判断是不是安全 rebuild(); boolean flag = false; for(int n=0;n<Process;n++) { if(!flag) { flag = true; for (int i = 0; i < Process; i++) { if (able(i) && !finish.get(i)) { for (int j = 0; j < Resources; j++) { work.set(j,work.get(j)+Allocation2.get(i).get(j)); Allocation2.get(i).set(j,0); } finish.set(i,true); } } for (int i = 0; i < Process; i++) { if (!finish.get(i)) { flag = false; break; } } } } return flag; } private ArrayList<Integer> findThePath(){   //用于排列出一个安全组合 reCopying(); rebuild(); reFinish(); ArrayList<Integer> Path = new ArrayList<>(); boolean flag = false; for(int n=0;n<Process;n++) { if(!flag) { flag = true; for (int i = 0; i < Process; i++) { if (able(i) && !finish.get(i)) { for (int j = 0; j < Resources; j++) { work.set(j,work.get(j)+Allocation2.get(i).get(j)); Allocation2.get(i).set(j,0); } finish.set(i,true); Path.add(i); } } for (int i = 0; i < Process; i++) { if (!finish.get(i)) { flag = false; break; } } } } return Path; } public void UpdateResources(int n, int[] Request){  //执行操作, 并更新数据 if(isSecurity()) { for (int i = 0; i < Resources; i++) { Available[i] = Available[i] - Request[i]; Allocation[n][i] = Allocation[n][i] + Request[i]; Need.get(n).set(i, Need.get(n).get(i) - Request[i]); } } }

}
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201

测试类(两个测试案例)

public class Test { public static void test1(){ int Resources = 3; int Process = 5; int[] Available = new int[]{3,3,2}; int[][] Max = new int[Process][Resources]; int[][] Allocation = new int[Process][Resources]; int[] max = new int[]{ 7,5,3,3,2,2,9,0,2,2,2,2,4,3,3 }; int[] allocation = new int[]{ 0,1,0,2,0,0,3,0,2,2,1,1,0,0,2 }; for(int i=0;i<Process;i++){ for(int j=0;j<Resources;j++){ Max[i][j] = max[i*Resources+j]; Allocation[i][j] = allocation[i*Resources+j]; } } BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation); int[] request1 = new int[]{1,0,2}; //P1发出请求Request(1,0,2)，执行银行家算法 banker.Algorithm(1,request1); banker.UpdateResources(1,request1); System.out.println(); int[] request2 = new int[]{3,3,0}; banker.Algorithm(4,request2); banker.UpdateResources(1,request1); } public static void test2(){ int Resources = 3; int Process = 5; int[] Available = new int[]{2,1,0}; int[][] Max = new int[Process][Resources]; int[][] Allocation = new int[Process][Resources]; int[] max = new int[]{ 7,5,3,3,2,2,9,0,2,2,2,2,4,3,3 }; int[] allocation = new int[]{ 0,3,0,3,0,2,3,0,2,2,1,1,0,0,2 }; for(int i=0;i<Process;i++){ for(int j=0;j<Resources;j++){ Max[i][j] = max[i*Resources+j]; Allocation[i][j] = allocation[i*Resources+j]; } } BankerAlgorithm banker = new BankerAlgorithm(Resources,Process,Available,Max,Allocation); int[] request0 = new int[]{0,2,0}; banker.Algorithm(0,request0); } public static void main(String[] args) { test1(); System.out.println(); test2(); }

}
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64