Skip to content

Commit 27c5237

Browse files
amritesh19amritesh19
authored
Add Banker's Algorithm (TheAlgorithms#2799)
1 parent 7abd239 commit 27c5237

File tree

1 file changed

+186
-0
lines changed

1 file changed

+186
-0
lines changed

‎Others/BankersAlgorithm.java

Lines changed: 186 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,186 @@
1+
package Others;
2+
3+
/**
4+
* This file contains an implementation of BANKER'S ALGORITM
5+
* Wikipedia: https://en.wikipedia.org/wiki/Banker%27s_algorithm
6+
*
7+
* The algorithm for finding out whether or not a system is in a safe state can be described as follows:
8+
* 1. Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
9+
* Initialize: Work= Available
10+
* Finish [i]=false; for i=1,2,……,n
11+
* 2. Find an i such that both
12+
* a) Finish [i]=false
13+
* b) Need_i<=work
14+
*
15+
* if no such i exists goto step (4)
16+
* 3. Work=Work + Allocation_i
17+
* Finish[i]= true
18+
* goto step(2)
19+
* 4. If Finish[i]=true for all i,
20+
* then the system is in safe state.
21+
*
22+
* Time Complexity: O(n*n*m)
23+
* Space Complexity: O(n*m)
24+
* where n = number of processes and m = number of resources.
25+
*
26+
* @author AMRITESH ANAND (https://github.com/amritesh19)
27+
*/
28+
29+
import java.util.Scanner;
30+
31+
public class BankersAlgorithm {
32+
33+
/**
34+
* This method finds the need of each process
35+
*/
36+
static void calculateNeed(int needArray[][], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
37+
{
38+
for (int i = 0 ; i < totalProcess ; i++){
39+
for (int j = 0 ; j < totalResources ; j++){
40+
needArray[i][j] = maxArray[i][j] - allocationArray[i][j];
41+
}
42+
}
43+
}
44+
45+
/**
46+
* This method find the system is in safe state or not
47+
* @param processes[] int array of processes (0...n-1), size = n
48+
* @param availableArray[] int array of number of instances of each resource, size = m
49+
* @param maxArray[][] int matrix(2-D array) of maximum demand of each process in a system, size = n*m
50+
* @param allocationArray[][] int matrix(2-D array) of the number of resources of each type currently allocated to each process, size = n*m
51+
* @param totalProcess number of total processes, n
52+
* @param totalResources number of total resources, m
53+
*
54+
* @return boolean if the system is in safe state or not
55+
*/
56+
static boolean checkSafeSystem(int processes[], int availableArray[], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
57+
{
58+
int [][]needArray = new int[totalProcess][totalResources];
59+
60+
calculateNeed(needArray, maxArray, allocationArray, totalProcess, totalResources);
61+
62+
boolean []finishProcesses = new boolean[totalProcess];
63+
64+
int []safeSequenceArray = new int[totalProcess];
65+
66+
int []workArray = new int[totalResources];
67+
68+
for (int i = 0; i < totalResources ; i++)
69+
workArray[i] = availableArray[i];
70+
71+
int count = 0;
72+
73+
// While all processes are not finished or system is not in safe state.
74+
while (count < totalProcess)
75+
{
76+
boolean foundSafeSystem = false;
77+
for (int m = 0; m < totalProcess; m++)
78+
{
79+
if (finishProcesses[m] == false)
80+
{
81+
int j;
82+
83+
for (j = 0; j < totalResources; j++)
84+
if (needArray[m][j] > workArray[j])
85+
break;
86+
87+
if (j == totalResources)
88+
{
89+
for (int k = 0 ; k < totalResources ; k++)
90+
workArray[k] += allocationArray[m][k];
91+
92+
safeSequenceArray[count++] = m;
93+
94+
finishProcesses[m] = true;
95+
96+
foundSafeSystem = true;
97+
}
98+
}
99+
}
100+
101+
// If we could not find a next process in safe sequence.
102+
if (foundSafeSystem == false)
103+
{
104+
System.out.print("The system is not in the safe state because lack of resources");
105+
return false;
106+
}
107+
}
108+
109+
System.out.print("The system is in safe sequence and the sequence is as follows: ");
110+
for (int i = 0; i < totalProcess ; i++)
111+
System.out.print("P"+safeSequenceArray[i] + " ");
112+
113+
return true;
114+
}
115+
116+
/**
117+
* This is main method of Banker's Algorithm
118+
*/
119+
public static void main(String[] args){
120+
int numberOfProcesses, numberOfResources;
121+
122+
Scanner sc = new Scanner(System.in);
123+
124+
System.out.println("Enter total number of processes");
125+
numberOfProcesses = sc.nextInt();
126+
127+
System.out.println("Enter total number of resources");
128+
numberOfResources = sc.nextInt();
129+
130+
int processes[] = new int[numberOfProcesses];
131+
for(int i = 0; i < numberOfProcesses; i++){
132+
processes[i] = i;
133+
}
134+
135+
System.out.println("--Enter the availability of--");
136+
137+
int availableArray[] = new int[numberOfResources];
138+
for( int i = 0; i < numberOfResources; i++){
139+
System.out.println("resource "+ i +": ");
140+
availableArray[i] = sc.nextInt();
141+
}
142+
143+
System.out.println("--Enter the maximum matrix--");
144+
145+
int maxArray[][] = new int[numberOfProcesses][numberOfResources];
146+
for( int i = 0; i < numberOfProcesses; i++){
147+
System.out.println("For process "+ i + ": ");
148+
for( int j = 0; j < numberOfResources; j++){
149+
System.out.println("Enter the maximum instances of resource "+ j);
150+
maxArray[i][j] = sc.nextInt();
151+
}
152+
}
153+
154+
System.out.println("--Enter the allocation matrix--");
155+
156+
int allocationArray[][] = new int[numberOfProcesses][numberOfResources];
157+
for( int i = 0; i < numberOfProcesses; i++){
158+
System.out.println("For process "+ i + ": ");
159+
for( int j = 0; j < numberOfResources; j++){
160+
System.out.println("Allocated instances of resource "+ j );
161+
allocationArray[i][j] = sc.nextInt();
162+
}
163+
}
164+
165+
checkSafeSystem(processes, availableArray, maxArray, allocationArray, numberOfProcesses, numberOfResources);
166+
167+
sc.close();
168+
}
169+
}
170+
171+
/*
172+
Example:
173+
n = 5
174+
m = 3
175+
176+
Process Allocation Max Available
177+
0 1 2 0 1 2 0 1 2
178+
179+
0 0 1 0 7 5 3 3 3 2
180+
1 2 0 0 3 2 2
181+
2 3 0 2 9 0 2
182+
3 2 1 1 2 2 2
183+
4 0 0 2 4 3 3
184+
185+
Result: The system is in safe sequence and the sequence is as follows: P1, P3, P4, P0, P2
186+
*/

0 commit comments

Comments
 (0)