Skip to content

Implemented Banker's Algorithm #2799

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 5 commits into from
Nov 2, 2021
Merged

Implemented Banker's Algorithm #2799

Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
514e5db
Implemented program to find nth Catalan number
amritesh19 Oct 6, 2021
dc3a835
some fixes according to convention
amritesh19 Oct 6, 2021
16e8b28
Merge branch 'master' into master
siriak Oct 11, 2021
6626af0
Implemented Banker's Algorithm
amritesh19 Oct 31, 2021
1d6d9d0
Merge branch 'master' into master
siriak Nov 2, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
186 changes: 186 additions & 0 deletions Others/BankersAlgorithm.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,186 @@
package Others;

/**
* This file contains an implementation of BANKER'S ALGORITM
* Wikipedia: https://en.wikipedia.org/wiki/Banker%27s_algorithm
*
* The algorithm for finding out whether or not a system is in a safe state can be described as follows:
* 1. Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
* Initialize: Work= Available
* Finish [i]=false; for i=1,2,……,n
* 2. Find an i such that both
* a) Finish [i]=false
* b) Need_i<=work
*
* if no such i exists goto step (4)
* 3. Work=Work + Allocation_i
* Finish[i]= true
* goto step(2)
* 4. If Finish[i]=true for all i,
* then the system is in safe state.
*
* Time Complexity: O(n*n*m)
* Space Complexity: O(n*m)
* where n = number of processes and m = number of resources.
*
* @author AMRITESH ANAND (https://github.com/amritesh19)
*/

import java.util.Scanner;

public class BankersAlgorithm {

/**
* This method finds the need of each process
*/
static void calculateNeed(int needArray[][], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
{
for (int i = 0 ; i < totalProcess ; i++){
for (int j = 0 ; j < totalResources ; j++){
needArray[i][j] = maxArray[i][j] - allocationArray[i][j];
}
}
}

/**
* This method find the system is in safe state or not
* @param processes[] int array of processes (0...n-1), size = n
* @param availableArray[] int array of number of instances of each resource, size = m
* @param maxArray[][] int matrix(2-D array) of maximum demand of each process in a system, size = n*m
* @param allocationArray[][] int matrix(2-D array) of the number of resources of each type currently allocated to each process, size = n*m
* @param totalProcess number of total processes, n
* @param totalResources number of total resources, m
*
* @return boolean if the system is in safe state or not
*/
static boolean checkSafeSystem(int processes[], int availableArray[], int maxArray[][], int allocationArray[][], int totalProcess, int totalResources)
{
int [][]needArray = new int[totalProcess][totalResources];

calculateNeed(needArray, maxArray, allocationArray, totalProcess, totalResources);

boolean []finishProcesses = new boolean[totalProcess];

int []safeSequenceArray = new int[totalProcess];

int []workArray = new int[totalResources];

for (int i = 0; i < totalResources ; i++)
workArray[i] = availableArray[i];

int count = 0;

// While all processes are not finished or system is not in safe state.
while (count < totalProcess)
{
boolean foundSafeSystem = false;
for (int m = 0; m < totalProcess; m++)
{
if (finishProcesses[m] == false)
{
int j;

for (j = 0; j < totalResources; j++)
if (needArray[m][j] > workArray[j])
break;

if (j == totalResources)
{
for (int k = 0 ; k < totalResources ; k++)
workArray[k] += allocationArray[m][k];

safeSequenceArray[count++] = m;

finishProcesses[m] = true;

foundSafeSystem = true;
}
}
}

// If we could not find a next process in safe sequence.
if (foundSafeSystem == false)
{
System.out.print("The system is not in the safe state because lack of resources");
return false;
}
}

System.out.print("The system is in safe sequence and the sequence is as follows: ");
for (int i = 0; i < totalProcess ; i++)
System.out.print("P"+safeSequenceArray[i] + " ");

return true;
}

/**
* This is main method of Banker's Algorithm
*/
public static void main(String[] args){
int numberOfProcesses, numberOfResources;

Scanner sc = new Scanner(System.in);

System.out.println("Enter total number of processes");
numberOfProcesses = sc.nextInt();

System.out.println("Enter total number of resources");
numberOfResources = sc.nextInt();

int processes[] = new int[numberOfProcesses];
for(int i = 0; i < numberOfProcesses; i++){
processes[i] = i;
}

System.out.println("--Enter the availability of--");

int availableArray[] = new int[numberOfResources];
for( int i = 0; i < numberOfResources; i++){
System.out.println("resource "+ i +": ");
availableArray[i] = sc.nextInt();
}

System.out.println("--Enter the maximum matrix--");

int maxArray[][] = new int[numberOfProcesses][numberOfResources];
for( int i = 0; i < numberOfProcesses; i++){
System.out.println("For process "+ i + ": ");
for( int j = 0; j < numberOfResources; j++){
System.out.println("Enter the maximum instances of resource "+ j);
maxArray[i][j] = sc.nextInt();
}
}

System.out.println("--Enter the allocation matrix--");

int allocationArray[][] = new int[numberOfProcesses][numberOfResources];
for( int i = 0; i < numberOfProcesses; i++){
System.out.println("For process "+ i + ": ");
for( int j = 0; j < numberOfResources; j++){
System.out.println("Allocated instances of resource "+ j );
allocationArray[i][j] = sc.nextInt();
}
}

checkSafeSystem(processes, availableArray, maxArray, allocationArray, numberOfProcesses, numberOfResources);

sc.close();
}
}

/*
Example:
n = 5
m = 3

Process Allocation Max Available
0 1 2 0 1 2 0 1 2

0 0 1 0 7 5 3 3 3 2
1 2 0 0 3 2 2
2 3 0 2 9 0 2
3 2 1 1 2 2 2
4 0 0 2 4 3 3

Result: The system is in safe sequence and the sequence is as follows: P1, P3, P4, P0, P2
*/