8 Replies - 8866 Views - Last Post: 02 July 2012 - 05:16 PM Rate Topic: -----

#1 ShazamSam69  Icon User is offline

  • New D.I.C Head

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

Implementation of Bankers Algorithm to determine the safety of a state

Posted 01 July 2012 - 03:24 PM

Hello everyone, this is my first time posting in these forums, I am currently pursuing my BS degree in Computer Science and I have a question that I would like to ask about my project that I turned in. I haven't been able to get any constructive feedback from anyone so I figured I could ask a question on this forum. The purpose of the assignment was to implement bankers algorithm, which included reading in data from a .txt file and then determining if the system was in a safe or unsafe state. I have posted my code below, and I just wanted to see if anyone could tell me if there is anything wrong with my code, I have ran it against several sample inputs and all of my output has been correct, this assignment was for a operating systems course that I just completed and this assignment has already been graded but I received points off because the TA said that "unsafe case is being stated as safe ". I tried to get in contact in order to get better feedback on what exactly was wrong because I have used sample inputs from multiple books and others that I have created and all of my results have been correct. I already read the Wikipedia page about the algorithm and I know what a safe and unsafe state is and how to go about the determination. I was just interested in seeing what I did wrong because I don't think I did and I am being told otherwise! lol
/**
 * 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
  		FileReader fr = new FileReader(fileIn);    
	   
		// Use Buffered reader to read one line at a time
		BufferedReader bufRead = new BufferedReader(fr);
		
		// Read first line
		line = bufRead.readLine();
		n = Integer.parseInt(line);
		count++;
		
		// Read second line
		line = bufRead.readLine();
		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];
		
		
		line = bufRead.readLine();
		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());
					
				}
				
			}
			
			
			line = bufRead.readLine();
			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());
				}
			}
			
			line = bufRead.readLine();
			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
		bufRead.close();
		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)

  • Attached File  Safe.txt (67bytes)
    Number of downloads: 457
  • Attached File  Unsafe.txt (57bytes)
    Number of downloads: 329


Is This A Good Question/Topic? 0
  • +

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

#2 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • 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?
Was This Post Helpful? 0
  • +
  • -

#3 ShazamSam69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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,
Was This Post Helpful? 0
  • +
  • -

#4 ShazamSam69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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).
Was This Post Helpful? 0
  • +
  • -

#5 ShazamSam69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#6 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • 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.
Was This Post Helpful? 0
  • +
  • -

#7 GregBrannon  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2198
  • View blog
  • Posts: 5,226
  • 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.
Was This Post Helpful? 1
  • +
  • -

#8 ShazamSam69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#9 ShazamSam69  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1