Write a C Program for the Implementation of Deadlock – Banker’s Algorithm

by

Aim:

To Write a C Program for the Implementation of Deadlock – Banker’s Algorithm.

Description:

  • The Banker’s Algorithm was designed and developed by a Dutch Computer Scientist, Edsger Djikstra. The Banker’s Algorithm is a Resource Allocation and a Deadlock Avoidance Algorithm.
  • This algorithm takes analogy of an actual bank where clients request to withdraw cash.
  • The Banking Authorities have some data according to which the cash is lent to the client.
  • The Banker cannot give more cash than the client’s request and the total cash available in the bank.

The Banker’s Algorithm is divided into two parts:

  1. Safety Test Algorithm: This algorithm checks the current state of the system to maintain its Safe State.
  2. Resource Request Handling Algorithm: This algorithm verifies if the requested resources, after their allocation to the processes affects the Safe State of the System. If it does, then the request of the process for the resource is denied, thereby maintaining the Safe State.

A State is considered to be Safe if it is possible for all the Processes to Complete its Execution without causing any Deadlocks. An Unsafe State is the one in which the Processes cannot complete its execution.

Exercise:

Consider the following snapshot of a system:

Answer the following questions using the banker’s algorithm:

  1. What is the content of the matrix Need?
  2. Is the system in a safe state?
  3. If a request from process P1 arrives for (0, 4, 2, 0), can the request be granted immediately?

Algorithm:

  1. The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources 
  2. Then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
  3. Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.

Program:

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int need[100][100],avai[100];
struct process{
int pc;
bool status;
}pno[100];
bool check(int i,int m)
{
int j;
for(j=0;j<m;j++)
{
if(need[i][j]>avai[j])
return 0;
}
return 1;
}
void disp(int n)
{
int i;
printf("SYSTEM IN SAFE STATE\nSAFE SEQUENCE = ");
for(i=0;i<n;i++)
{
printf("P%d ",pno[i].pc);
}
}
void banker(int alloc[][100],int max[][100],int n,int m)
{
int i,j,ck=0,ic=0,flag=0;
bool checker=0;
printf("NEED MATRIX :\n");
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
need[i][j]=max[i][j]-alloc[i][j];
printf("%d ",need[i][j]);
pno[i].status=0;
}
printf("\n");
}
while(ck<n)
{
if(check(ic,m)==1&&pno[ic].status==0)
{
int ac=0;
pno[ck].pc=ic;
ck++;
pno[ic].status=1;
checker=1;
for(ac=0;ac<m;ac++)
{
avai[ac]=avai[ac]+alloc[ic][ac];
}
}
if(ic==n-1&&checker==0)
{
printf("SYSTEM UNSAFE\n");
flag=1;
ck=n;
}
if(ic==n-1)
{
ic=-1;
checker =0;
}
ic++;
}
if(flag==0)
disp(n);

}

int main()
{
int alloc[100][100],max[100][100],n,m,i,j;
printf("ENTER THE NO PROCESS AND RESOURCES : ");
scanf("%d%d",&n,&m);
printf("\nENTER ALLOCATION MATRIX : \n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&alloc[i][j]);
printf("ENTER MAX MATRIX : \n");
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&max[i][j]);
printf("ENTER AVAILABLE :\n");
for(i=0;i<m;i++)
scanf("%d",&avai[i]);
banker(alloc,max,n,m);
return 0;
}

Execution:

Input:
5 4 0 0 1 2 1 0 0 0 1 3 5 4 0 6 3 2 0 0 1 4 0 0 1 2 1 7 5 0 2 3 5 6 0 6 5 2 0 6 5 6 1 5 2 0

Output:

ENTER THE NO PROCESS AND RESOURCES : 
ENTER ALLOCATION MATRIX : 
ENTER MAX MATRIX : 
ENTER AVAILABLE :
NEED MATRIX :
0 0 0 0 
0 7 5 0 
1 0 0 2 
0 0 2 0 
0 6 4 2 
SYSTEM IN SAFE STATE
SAFE SEQUENCE = P0 P2 P3 P4 P1

Result:

Thus Dead lock bankers algorithm program was executed Successfully.

Leave a Comment