banker2.cpp

bankers algorithm c++ source code

/*	James O' Connor 50703338
	17/12/02
	This is my original work

	Program to implement safety algorithm and bankers algorithm
	for process management / resource allocation.

	It's a bit if a rough hack, not very OO :)
*/

#include <iostream>
#define M 3
#define N 5
using namespace std;

void readMax(int max[N][M]);
void printMax(int max[N][M]);
bool lessEqNeedWork(int index, int need[N][M], int work[M]);
void printSafeStatus(int work[M], bool finish[N], int step);
void printRequestStatus(int request[M], int available[M], int step);
bool isSafe(int max[N][M], int allocation[N][M], int system[N], int need[N][M], int available[M]);

int main(int argc, char **argv)
{
		
	int i, j, k;
	int max[N][M]={	{7,5,3},
					{3,2,2}, 
					{9,0,2}, 
					{2,2,2}, 
					{4,3,3}
					};
	int allocation[N][M]={
					{0,1,0},
					{2,0,0},
					{3,0,2},
					{2,1,1},
					{0,0,2}
					};
	int available[M]={3,3,2};
	int need[N][M]={
					{7,4,3},
					{1,2,2},
					{6,0,0},
					{0,1,1},
					{4,3,1}
					};
	int system[N]={10, 5, 7};
	int work[M]={0};
	int request[N][M]={
						{0, 2, 0},
						{1, 0, 2},
						{1, 0, 0},//request that can be granted immediatly
						{0, 2, 1},//request that can't be granted immediatly
						{3, 3, 0},
					};

	bool step3 = true;
	//initialise arrays
	bool safe = isSafe(max, allocation, system, need, available);
	for(i=0; i<N; i++)
	{
		step3 = true;
		cout << "i: " << i << " j: " << j <<endl;
		for(j=0; j<M; j++)
		{	
			

			if(request[i][j] > need[i][j])
			{	printRequestStatus(request[i], available, 1); //step 1
				cout << "Error condition: request exceeded maximum claim!"<<endl;	
				step3 = false;
				break;
			}
			
			else if(request[i][j] > available[j])
			{	
				printRequestStatus(request[i], available, 2); //step 2
				cout << "Request greater than available resources," <<
						"process must wait"<<endl;
				step3 = false;
				break;
			}

			else if (j == M-1)
				printRequestStatus(request[i], available, 1);
				
		}
		
		if(step3) //step 3
		{	
			
			//allocation_new = allocation_i + request_i
			int allo_temp[N][M];
			for(j=0; j<M; j++)
					allo_temp[i][j] = allocation[i][j] + request[i][j];

			int need_temp[N][M];
			for(j=0; j<M; j++)
					need_temp[i][j] = need[i][j];

			int available_temp[M];
			for(j=0; j<M; j++)
					available_temp[j] = available[j];

			safe = isSafe(max, allo_temp, system, need_temp, available_temp);

			if(!safe)
			{	
				cout << "request not safe, process must wait!"<<endl;
				safe = isSafe(max, allocation, system, need, available);
				printRequestStatus(request[i], available, 3);
			}

			else
			{
				for(j=0; j<M; j++)
					allocation[i][j] = allo_temp[i][j];

				safe = isSafe(max, allocation, system, need, available);
				printRequestStatus(request[i], available, 3);
				cout << "request safe!"<<endl;
			}


		}
			
		
		
		
	}

return 0;
}

void printSafeStatus(int work[M], bool finish[N], int step)
{
	cout << "Step: " << step <<endl;
	cout << "work: ";
	int i, j;
	for(i=0; i<M; i++)			
			cout << work[i] <<" ";

	cout <<endl;
	cout << "finish: ";
	for(j=0; j<M; j++)			
			cout << (finish[j]?"true":"false") <<" ";

	cout <<endl;
	
}

void printRequestStatus(int request[M], int available[M], int step)
{
	cout << "Step: " << step <<endl;
	cout << "request: ";
	int i, j;
	for(i=0; i<M; i++)			
			cout << request[i] <<" ";

	cout <<endl;
	cout << "available: ";
	for(j=0; j<M; j++)			
			cout << available[j] <<" ";

	cout <<endl;
	
}

bool isSafe(int max[N][M], int allocation[N][M], int system[N], int need[N][M], int available[M] )
{	int i, j, k;
	int work[M];
	//Need = Max - Allocation	
	for(i=0; i<N; i++)
		for(j=0; j<M; j++)
			need[i][j] = max[i][j] - allocation[i][j];

	for(i=0; i<M; i++)
	{	
		int sigma =0;		
		for(j=0; j<N; j++)
			sigma = sigma + allocation[j][i];

		available[i] = system[i] - sigma;
	}

		
	for(i=0; i<M; i++)
		work[i] = available[i];
	bool finish[N]={false};
	bool safe = true;
	//Find an i such that both Finish[i] = false and Needi <= Work
	for(i=0; i<N; i++)
	{	
		if(!finish[i] && lessEqNeedWork(i, need, work))
		{
			for(j=0; j<M; j++)
				work[j] = work[j] + allocation[i][j];
			finish[i]= true;
			i=-1;	//when i++, i goes back to zero!
				
		}
	}


	for(i=0; i<N; i++)
		if(finish[i] == false)
			safe = false;

	return safe;
}

bool lessEqNeedWork(int index, int need[N][M], int work[M])
{
	int i=0;
	for(i=0; i<M; i++)
		if(need[index][i] > work[i])
			return false;

	return true;
}


/*

	

*/