Question: Suppose your own example data for Banker's Algorithm. Implement banker's algorithm by your familiar computer language, and run to check your example is in a safe state or not.

 

Solution:

 

#include<iostream>

#include<cstring>

#define m 3

#define n 4

 

struct state{

int resource[m];

int available[m];

int claim[n][m];

int alloc[n][m];

}P;

using namespace std;

int request[m];

//judge the current state according to banker's algorithm

bool is_Safe(state tmp, int x){

bool status[n];

int cnt = 1, pos;

memset(status, 0, sizeof(status));

status[x] = 1;

bool flag = 0;

while(1){

bool flag=0;

for(int i = 0; i <n; i++){

if(!status[i]){

flag=1;

for(int j=0; j<m; j++){

flag = 0;

break;

}

}

if(flag){

pos = i;

status[i] = 1;

break;

}

}

}

if(flag){

cnt++;

for(int i = 0; i <m; i++){

tmp.available[i] + = tmp.alloc[pos][i];

tmp.alloc[pos][i] = 0;

tmp.claim[pos][i] = 0;

}

}

else break;

}

if(cnt == n) return true;

else return false;

}

//update the state if legal

void Update(state tmp)

{

for(int i = 0; i<m; i++)

P.available[i] = tmp.available[i];

P.resource[i] = tmp.resource[i];

for(int i = 0; i<n; i++){

for(int j = 0; j<m; j++){

P.claim[i][j] = tmp.claim[i][j];

P.alloc[i][j] = tmp.alloc[i][j];

}

}

}

//calculate the requested amount

void Create_request(int x){

for(int i = 0; i <m; i++)

requested[i] = P.claim[x][i] - P.alloc[x][i])

}

int Allocate(int x){

//Exception

for(int i = 0; i <m; i++)

if(P.alloc[x][i] + request[i] > P.claim[x][i])

return 1;

// Suspend process

for(int i = 0; i <m; i++)

if(request[i] > P.available[i])

return 2;

//Define a new state

state tmp;

for(int i = 0; i<n; i++)

for (int j = 0; j<m; j++)

tmp.claim[i][j] = P.claim[i][j];

for(int i = 0; i<m; i++)

{

tmp.resource[i] = P.resource[i];

tmp.claim[x][i] = 0;

tmp.available[i] = P.available[i] + P.alloc[x][i];

tmp. alloc[x][i] = 0;

}

/*Judge whether the new state is safe or not, if it is, update the state or return the exception message.*/

if(is_Safe(tmp, x))

{

Update(tmp);

return 0;

}

else return 2;

}

bool Initialize()

{

for (int i =0; i <m; i++)

{

P.available[i] = P.resource[i];

for(int j = 0; j<n ; j++)

P.available[i] -= P.alloc[j][i];

if(P.available[i] < 0)

return false;

}

int main()

{

//get resource amount

printf("Resource Amount:\n");

for (int i =0; i <m; i++)

scanf("%d", &P.resource[i]);

//get claim matrix

printf("Claim matrix:\n");

for(int i = 0; i <n; i++)

for (int j =0; j <m; j++)

scanf("%d", &P.claim[i][j]);

//get allocation matrix

printf("Allocation matrix:\n");

for(int i = 0; i <n; i++)

for (int j =0; j <m; j++)

scanf("%d", &P.alloc[i][j]);

//Calculate request

if(Initialize())

{

print("Please input the ID of the process you want to chech.\n");

int x;

scanf(%d", &x);

//calculate the requested resource amount

Create_request(x);

printf("Requested Amount:\n");

for(int i = 0; i <m; i++)

printf("%d", request[i]);

printf("\n");

int flag = Allocate(x);

if(!flag)

prinf("P%d is Okey!\n");

else if(flag==1)

printf("An execution has occured!\n");

else

printf("P%d has been suspended!\n", x);

}

else

{printf("An exception has occured!\n");

}

return 0;

}