# Implementation of Bankers Algorithm to determine the safety of a state

Page 1 of 1

## 8 Replies - 29818 Views - Last Post: 02 July 2012 - 05:16 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=284483&amp;s=37f999dbec19159d9a596222d0a2cad6&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

# Implementation of Bankers Algorithm to determine the safety of a state

Posted 01 July 2012 - 03:24 PM

```/**
* This program implements Bankers algorithm which will determine whether
*	the state of the system that is read in from a file is safe or unsafe
* and output the result back to the user.
*
*/

import java.io.*;
import java.util.StringTokenizer;
import java.util.Scanner;

public class Banker
{
public static void main(String[]args)throws IOException
{

int n = 0;							// Variable to hold the number of processes
int m = 0;							// Variable to hold the number of resources
int count = 0;						// Counter that holds the number of lines in the file
int lineCount = 0;				        // Counter that holds the number of lines in each matrix
int [] sumColumn;				       // Array holding the value of the sum of each column.
int [] sumRow;					       // Array holding the value of the sum of each row.
int [] resourceVector;			       // Array that holds the resource vector
int [] availableVector;			// Array that holds the available vector
int [] work;						// Array that holds the currently available vector
int [] processSequence;			// Array holding the sequence of processes to run to completion
int index = 0;						// Integer for holding the index value of the process sequence
boolean finish[];					// Boolean array that tells if a process has finished
int [][] claimMatrix;			// Array that holds the claim matrix
int [][] allocationMatrix;		// Array that holds the allocation matrix
int [][] needMatrix;				// Array that holds the need matrix ( C-A );
boolean isSafe = false;			// Boolean value that tells if the system is in a safe or unsafe state

// Variables to read in line from a file and tokenize
String line;
String fileIn;
StringTokenizer tokens;

Scanner keyboard = new Scanner(System.in);

System.out.println("Please enter in the name of the file : ");
fileIn = keyboard.nextLine();

// build input stream

n = Integer.parseInt(line);
count++;

m = Integer.parseInt(line);
count++;

// Create each Matrix(n x m) and Vector( m )
claimMatrix = new int[n][m];
allocationMatrix = new int[n][m];
needMatrix = new int [n][m];
resourceVector = new int[m];
availableVector = new int[m];
work = new int[m];
finish = new boolean[n];
processSequence = new int[n];
sumColumn = new int[m];
sumRow = new int[n];

count++;

// Read through file and set Claim Matrix
while(line != null && lineCount < n)
{
tokens = new StringTokenizer(line);

if(tokens.hasMoreTokens())
{
for(int j = 0; j < m; j++)
{
claimMatrix[lineCount][j] = Integer.parseInt(tokens.nextToken());

}

}

lineCount++;
count++;
}

lineCount = 0;

// Read through file and set Allocation Matrix
while(line != null && lineCount < n)
{
tokens = new StringTokenizer(line);

if(tokens.hasMoreTokens())
{
for(int j = 0; j < m; j++)
{
allocationMatrix[lineCount][j] = Integer.parseInt(tokens.nextToken());
}
}

lineCount++;
count++;
}

// Read the last line and set Resource Vector

tokens = new StringTokenizer(line);
while(tokens.hasMoreTokens())
{
for(int i = 0; i < m; i++)
{
resourceVector[i] = Integer.parseInt(tokens.nextToken());
}
}

// Close the bufferreader and file
fr.close();

// Determine the initial need matrix

for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
needMatrix[i][j] = claimMatrix[i][j] - allocationMatrix[i][j];
}
}

// Determine the initial available vector

for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
sumColumn[j] += allocationMatrix[i][j];
sumRow[i] += needMatrix[i][j];
}

}

for(int j = 0; j < m; j++)
{
availableVector[j] = resourceVector[j] - sumColumn[j];
}

// Initialize Work and Finish

for(int j = 0; j < m; j++)
{
work[j]=availableVector[j];
}

for(int i = 0; i < n; i++)
{
finish[i] = false;

}

// Safety Algorithm (checks if the system is in a safe or unsafe state)

boolean found = false;

do
{
found = false;				// Process found flag
int i = 0;

for(; i < n; i++)
{
if ((!finish[i]))
{
boolean good = true;

for (int j = 0; j < m; j++)
{
// If the need is greater than the available, then the process is not able to run to completion
// So it is not good
if(needMatrix[i][j] > work[j])
{
good = false;
break;
}
}

if (!good) continue;			// Try another process
found = true;
break;
}
}

// Process is found that can run to completion, simulate execution
if(found)
{
finish[i] = true;
for (int j = 0; j < m; j++)
{
work[j] += allocationMatrix[i][j];
}

processSequence[index++] = i;
}

}while (found);

// Check if all processes have finished

for(int i = 0; i < n; i++)
{
if(!finish[i])
{
isSafe = false;
}
else
{
isSafe = true;
}
}

// Display output
System.out.println("Number of Processes : " + n);
System.out.println("Number of Resources : " + m + "\n");

System.out.println("Claim Matrix : ");
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
System.out.print(claimMatrix[i][j] + " ");
}

System.out.println();
}

System.out.println("\nAllocation Matrix : ");
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
System.out.print(allocationMatrix[i][j] + " ");
}

System.out.println();

}

System.out.println("\nResource Vector : ");
for(int i = 0; i < m; i++)
{
System.out.print(resourceVector[i] + " " );

}

System.out.println();
System.out.println("\nNeed Matrix : ");
for(int i = 0; i < n; i++)
{
for(int j = 0; j < m; j++)
{
System.out.print(needMatrix[i][j] + " ");
}

System.out.println();
}

System.out.println();
System.out.println("Initial Available Vector : ");
for(int j = 0; j < m; j++)
{
System.out.print(availableVector[j] + " ");

}

System.out.println("\n");

if(isSafe)
{
System.out.print("Process Sequence : ");
for(int i = 0; i < processSequence.length; i++)
{
System.out.print((processSequence[i]+1) + " ");
}

System.out.println();

System.out.println("This system is in a safe state!!!");
}
else
{
System.out.println("This system is not in a safe state!!!");
}

}

}

```

I also have attached two sample input files for a safe and unsafe state
line 1 : number of processes
line 2: number of resources
lines 3- 6 : claim matrix
lines 7-10 : allocation matrix
line 11 - resource vector

Safe Sample Input
-----------
4
3
3 2 2
6 1 3
3 1 4
4 2 2
1 0 0
6 1 3
2 1 1
0 0 2
9 3 6

-----------

Any feedback will be greatly appreciated.

#### Attached File(s)

•  Safe.txt (67bytes)
•  Unsafe.txt (57bytes)

Is This A Good Question/Topic? 0

## Replies To: Implementation of Bankers Algorithm to determine the safety of a state

### #2 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 01 July 2012 - 04:41 PM

I'm completely new to this algorithm but am intrigued by the problem, and I have a question.

I notice that the Wikipedia discussion assumes that the processes will occur in numerical order, P1, P2, P3, etc. Your implementation "seems" (because I'm uncertain) to take the processes and determine if they can be ordered so that they can be completed in a way to keep the system in a safe state. I assume this because for the Safe.txt condition, your program states that the process sequence is 2 1 3 4, which I assume means that if the processes occur in the order P2, P1, P3, and P4, the system will maintain a safe state while the processes are accomplished. For the Unsafe.txt condition, your program does not provide a process sequence, so I assume that the possible process sequences were checked and no sequence could be found that could be completed while keeping the system in a safe state.

Am I right?

If I'm right, is it possible that your algorithm should only consider whether the system can maintain a safe state while the processes are accomplished in the order given by the file: P1, P2, P3, etc?

### #3 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 01 July 2012 - 04:59 PM

Hi Greg thanks for the quick reply,

You are correct in my program I am checking if it is possible for any process to run to completion, ( i.e. use up all the claimed/max resources) , and once the process does run to completion it adds its resources back in to the available vector. The algorithm doesn't check in an arbitrary order, its just a hypothetical order in which every process can run to completion, which would mean that the system is in a safe state. Both of the sample inputs I provided worked just as they should have but my TA deducted points off, and I asked what sample input was used and I never got a response, so I am going crazy trying to see how my program could possibly be producing the wrong output, I wasn't even supposed to display anything except for a message stating whether the system was in a safe state or not. I went beyond just for clarity and displayed every matrix and the sequence of processes that would run to completion if the system was safe. This algorithm is used in deadlock avoidance, it doesn't matter what order the processes run to completion but that they can run. In my sample input for the unsafe state no process could get all its resources to run to completion, so no process could give its used resources back to the available vector, so the system was in a unsafe state. So if hypothetically a request came in to use a resource for a certain process and that request would put the system in an unsafe state, then that request would be blocked/suspended. I don't know what could be wrong, I thought my implementation was correct but I have been doubting myself lately lol.

Thanks,

### #4 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 01 July 2012 - 05:09 PM

Sorry I don't know how to edit posts but Instead of arbitrary order I meant to say its doesn't check in a certain sequence like p1 then p2 then p3, it just checks any sequence that would allow all the processes to run to completion (hypothetical).

### #5 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 02 July 2012 - 12:10 PM

Ok so it turns out that the TA made a mistake and misread the output for the unsafe case and has now changed my grade and given me full credit. So the program did not have any fault and was implemented correctly. Sorry for not contributing/asking a good question in the forum, I will be sure not to doubt myself again and give you guys a headache lol. If the moderators could please mark this thread as solved or completed I would appreciate it, and thanks Greg for your input.

### #6 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 02 July 2012 - 02:23 PM

Glad it worked out, sorry I wasn't more help. I'm still intrigued and will add it to my list of designs TODO someday.

### #7 GregBrannon

• D.I.C Lover

Reputation: 2250
• Posts: 5,340
• Joined: 10-September 10

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 02 July 2012 - 04:20 PM

Oops.

I have been studying your algorithm, and I think there's an error. According to the two discussions I've read, when a process completes successfully, it returns its maximum resources (what you called the Claim Matrix) to the system. I believe you're attempting to return the resources with this code:
Line 214:
```for (int j = 0; j < m; j++)
{
work[j] += allocationMatrix[i][j];
}
```

But the code above returns the process' allocated resources rather than all available resources. The correct code would be:
```// release the completed process' resources to the system
for (int j = 0; j < m; j++)
{
work[j] += claimMatrix[i][j];
}
```

After the code is changed as I've shown, it still returns the expected results for the examples you gave, but they're pretty simple examples with a trivial failure mode (no processes can complete a run) in Unsafe.txt and a wide success path in Safe.txt.

My familiarity with this subject is very immature, so I could be wrong. Thanks for sharing the problem.

### #8 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 02 July 2012 - 04:59 PM

Thanks for catching that you are right , I made a mistake and meant to write claim matrix instead of allocation matrix, I even explained that in the previous post about a process returning its resources lol but messed up on line 214 haha. Thanks again

### #9 ShazamSam69

Reputation: 0
• Posts: 6
• Joined: 08-August 11

## Re: Implementation of Bankers Algorithm to determine the safety of a state

Posted 02 July 2012 - 05:16 PM

I used the "Work" Array as a temporary array used when simulating the execution of a process and when a process completes it is supposed to return all of its claimed/max resources back to the available vector. I don't know why I put the allocation matrix on that line, I had the idea right and just wrote the wrong array name. Thanks for your help, thankfully the TA has already given me credit so I hope I don't have anything to worry about since the results were correct but you are right those examples are very simple cases. Thanks again