Algorithm and Implementation of Banker algorithm to avoid dead lock or finding safe sequence
Banker algorithm is responsible for find the safe sequence so that we can able avoid Deadlock.
IN order to implement this we are going to make use c programming language. lets first discuss about algorithm to find the safe sequence
here we are going to make use of following matrix
alloc[ ][ ] it is to maintain the record of allocated resources to the processes
max[ ][ ] it is to maintain the record of maximum requirement resources to the processes
avail[ ] it is to maintain the available number of resources or number of copy of each resources available.
need[][] it is to store the need of each and every process.
stat[] it is to maintain the status of process where -1 indicate not executed
seq[] it is to maintain or store the safe sequence of resources.
Algorithm
Step1: Take the input form the user like number of allocated resources, maximum need of each process, number of process number of resources, and available instance of resources in respective matrix.
Step2: Calculate the need of each and every process
need[i][j] = max[i][j] – alloc[i][j];
Step3: Now find the process whose need can be satisfied mean if need[][] is less than avai[]
execute the process and add the allocated resources to available
Update the status of process in stat[]
add the process in seq[] list
Step4: if all the process status get updated then display the safe sequence otherwise no safe sequence exist.
Implementation code for Banker algorithm in C language
#include <stdio.h>
void main()
{
// P0, P1, P2, P3, P4 are the Process names here
int n, m, i, j, k,status=1;
int alloc[5][3];
int max[5][3];
int avail[3];
printf(“enter the no of processn”);
scanf(“%d”,&n);
// Number of processes
printf(“enter the no of resourcesn”);
scanf(“%d”,&m);
// Number of resources
printf(“enter the allocated matrixn”);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf(“%d”,&alloc[i][j]);
}
}
printf(“now enter the maximum need of processn”);
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
scanf(“%d”,&max[i][j]);
}
}
printf(“now enter the available instance of resourcesn”);
for(k=0;k<m;k++)
{
scanf(“%d”,&avail[k]);
}
int stat[n],ind=0,seq[n];
for (k = 0; k < n; k++) {
stat[k] = -1;
}
int need[n][m];
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
need[i][j] = max[i][j] – alloc[i][j];
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{ if(stat[i]==-1)
{
if(need[i][0]<=avail[0] && need[i][1]<=avail[1]&& need[i][2]<=avail[2])
{
avail[0]=avail[0]+ alloc[i][0];
avail[1]=avail[1]+ alloc[i][1];
avail[2]=avail[2]+ alloc[i][2];
stat[i]=ind;
seq[ind]=i;
ind++;
}
}
}
}
for(i=0;i<n;i++)
{
if(stat[i]==-1)
{
status=0;
}
}
if(status==0)
{
printf(“no safe state exist”);
}
else
{
printf(“safe sequence for process isn”);
for(i=0;i<n;i++)
{
printf(“P%d,”,seq[i]);
}
}
getch();
}
