Banker algorithm: java implementation (based on textbook)
attribute
Needs to be passed in the constructor
- Integer Resources, used for the table name and the number of available Resources. There are several Resources in total
- Integer Process, used for the number of table name processes. There are several processes in total
- Integer array Available, used for the table name and the number of Available resources of each type
- The shaping matrix Max is used for the table name and the total amount of resources required by each process
- The integer matrix Allocation is used to represent the number of resources of each type that each process currently has
Other properties
- The Need matrix represents the number of resources needed by each process
- Available2, allocation2 and need2 are backup of the above three data structures respectively for security detection without breaking the original data structure
- Integer array work, used to represent the number of resources currently available (used when detecting security)
- Boolean array finish. When each process is completed during security detection, the corresponding index is changed to true
method
public
- BankerAlgorithm() construction method
- Algorithm
- UpdateResources() algorithm for updating data
private
- setNeed() method of constructing Need matrix
- reSetNeed() method of refreshing requirement matrix
- reCopying() method of copying backup
- rebuild() is used to initialize the methods of work and finish
- reFinish() method for refreshing work and finish arrays
- able() is used to judge whether the value in work is enough or not
- isSecurity() is the method used to determine whether the request is secure or not
- findThePath() is used to arrange the methods of a security combination if it is safe
General implementation process
After calling the construction method with the passed in parameter, the banker Algorithm() is used to pass in the request parameter (what resources does the process apply for and how much)
Algorithm() calls setNeed() to establish the Need matrix. After two initial judgments, the isSecurity() method is used to determine whether the request is secure.
isSecurity() establishes work and finish, and returns Boolean value to Algorithm() after judgment. If it is safe, it calls findThePath() to find the security combination and output it
In the test class, you can choose to update data or not to update data UpdateResources()
Need attention
All attributes seem to be created before the construction method at the beginning of object creation,
That is, if the size of the attribute array is determined by other numeric attributes (which need to be assigned by the construction method),
Because the initial value used before the assignment of the construction method is 0, that is to say, the size of the attribute array is zero,
Therefore, any such array attribute can be replaced by dynamic array (ArrayList/LinkedList)
code
Algorithm class
import java.util.ArrayList;
public class BankerAlgorithm {
public int Resources; //Number of resources
public int Process; //Number of processes
public int[] Available; //Available resource vector
public int[][] Max; //Maximum demand matrix
public int[][] Allocation; //Distribution matrix
public BankerAlgorithm(int Resources, int Process, int[] Available, int[][] Max, int[][] Allocation){
//Construction method
this.Process = Process;
this.Resources = Resources;
this.Allocation = Allocation;
this.Max = Max;
this.Available = Available;
}
/**
* All attributes seem to be created before the construction method at the beginning of object creation,
* That is, if the size of the attribute array is determined by other numeric attributes (which need to be assigned by the construction method),
* Because the initial value used before the assignment of the construction method is 0, that is, the size of the attribute array is zero
* Therefore, any such array attribute can be replaced by dynamic array (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();
}
//Backup of 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(){ //For copy backup
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){ //Process i makes a resource request to the system
reSetNeed();
boolean f = true; //The required quantity is less than the required quantity
for(int j=0;j<Resources;j++){
if (Request[j] > Need.get(i).get(j)) {
f = false;
break;
}
}
if(f){
boolean f2 = true; //The required quantity is less than the remaining quantity
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("This request is not secure!");
}
}else
System.out.println("Request failed: The number of requested resources is greater than the number of existing resources!");
}else
System.out.println("Request failed: The number of applied resources is greater than its own needs!");
}
//work and finish
private final ArrayList<Integer> work = new ArrayList<>();
private final ArrayList<Boolean> finish = new ArrayList<>();
private void rebuild(){ //Used to initialize work and 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(){ //Used to refresh the work and finish arrays
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){ //Used to judge whether the value in work is enough or not
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(){ //Used to judge whether it is safe
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(){ //Used to arrange a safe combination
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){ //Perform operations and update data
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]);
}
}
}
}
Test class (two test cases)
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 sends a Request(1,0,2) and executes the banker algorithm
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();
}
}