BANKER's ALGORITHM
Bankers's Algorithm is basically a deadlock-avoidance algorithm.It means that you should be smart enough while allocating resources and if a deadlock occurs you should rollback immediately.
Consider the following scenario:
You have 10 R1 type of resources,5 R2 type of resources and 7 R3 type of resources.For simplicity you can consider:
R1 - You can assume that these are printers.
R2 - You can assume that these are scanners.
R3 - You can assume that these are CD-Writers.
Now assume that there are 5 processes namely P1,P2,P3,P4,and P5. These processes will need combinations of these resources to get complete.As soon as a process gets over,the resources allocated to it are taken back and can be given to others.All you have to do is that when a particular process requests for resources, allocate resources and immediately check that whether it is leading to deadlock or not.By deadlock I mean that no further process is able to complete due to lack of resources.If deadlock can occur you should rollback i.e. take back the resources you just allocated to a process and wait for a new request.
We have used 3 important functions that do the job for us:
accept() : To accept the requests from processes.
safety() : To check whether deadlock will occur or not
rollback(): In case of possible deadlock,rollback to previous state.
The code below illustrates the concept:
#include<stdio.h>
#include<stdlib.h>
int avail[10],maxim[20][20],allo[20][20],m,n,need[20][20];
void accept()
{
int i,j,val;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
printf("\nENTER THE MAX REQUIRED VALUE for P%d,R%d: ",i,j);
loop: scanf("%d",&val);
if(val>avail[j])
{
printf("ERROR!!THE ENTERED VALUE IS GREATER THAN THE AVAILABLE VALUE i.e %d .PLZ ENTER THE VALUE AGAIN: ",avail[j]);
goto loop;
}
else
maxim[i][j]=val;
}
}
}
void rollback(int roll[],int pro)
{
int k;
for(k=0;k<m;k++)
{
avail[k]=avail[k]+roll[k];
allo[pro][k]=allo[pro][k]-roll[k];
need[pro][k]=allo[pro][k]+roll[k];
printf("\nWE ARE ROLLING BACK");
}
}
int safety()
{
int i,j,work[10],finish[10],flag=0,k,cnt=0,cn,flag1=0,ans;
//char ans;
printf("\nTHE ALTERED ALLOCATION TABLE IS:\n");
printf("PROCESS");
for(i=0;i<m;i++)
{
printf("\tR%d\t",i);
}
printf("\n");
for(i=0;i<n;i++)
{
printf("\nP%d\t",i);
for(j=0;j<m;j++)
{
printf("%d\t\t",allo[i][j]);
}
}
j=0;
for(i=0;i<m;i++)
{
work[j]=avail[i];
j++;
}
for(i=0;i<n;i++)
{
finish[i]=0;
}
while(cnt<=10)
{
for(i=0;i<n;i++)
{
if(finish[i]==0)
{
for(j=0;j<m;j++)
{
if(need[i][j]<=work[j])
{
flag=1;
}
else
{
flag=0;
break;
}
}
if(flag==1)
{
printf("\nTHE PROCESS P%d RAN SUCCESSFULLY",i);
finish[i]=1;
for(k=0;k<m;k++)
{
work[k]=work[k]+allo[i][k];
}
}
}
}
for(cn=0;cn<n;cn++)
{
if(finish[cn]==1)
{
flag1=1;
}
else
{
flag1=0;
break;
}
}
cnt++;
if(flag1==1)
{
printf("\nTHE SYSTEM IS IN SAFE STATE\n");
ans=0;
break;
}
}//end of while
if(flag1==0)
{
printf("\nTHE SYSTEM IS NOT IN SAFE STATE\n");
ans=1;
}
return ans;
}
void request()
{
int pro,val,i,ans1,k,roll[10];
char ans;
while(1)
{
printf("\nDO YOU HAVE A REQUEST?(y/n)");
scanf("%c",&ans);
scanf("%c",&ans);
k=0;
if(ans=='y'||ans=='Y')
{
printf("ENTER THE PROCESS REQUESTING(0,1,2,3..): ");
scanf("%d",&pro);
for(i=0;i<m;i++)
{
printf("ENTER THE REQUIRED VALUE OF RESOURCE R%d: ",i);
loop1: scanf("%d",&val);
if(val>maxim[pro][i])
{
printf("ERROR!!THE ENTERED VALUE IS GREATER THAN THE MAX VALUE REQD. i.e %d .PLZ ENTER THE VALUE AGAIN: ",maxim[pro][i]);
goto loop1;
}
else
{
allo[pro][i]=allo[pro][i]+val;
avail[i]=avail[i]-val;
need[pro][i]=need[pro][i]-val;
roll[k]=val;
k++;
}
}
ans1=safety();
if(ans1==1)
{
rollback(roll,pro);
}
}
else
{
exit(0);
}
}
}
int main()
{
int i,val,j;
printf("\nWELCOME TO BANKER'S ALGORITHM\n");
printf("\nENTER THE NUMBER OF RESOURCES: ");
scanf("%d",&m);
printf("\nENTER THE NUMBER OF PROCESS(s): ");
scanf("%d",&n);
for(i=0;i<m;i++)
{
printf("\nENTER THE MAX AVAILABLE VALUE FOR RESOURCE R%d: ",i);
scanf("%d",&val);
avail[i]=val;
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
allo[i][j]=0;
}
}
accept();
printf("\nTHE TABLE ENTERED FOR MAX NEEDED IS:\n");
printf("PROCESS");
for(i=0;i<m;i++)
{
printf("\tR%d\t",i);
}
printf("\n");
for(i=0;i<n;i++)
{
printf("\nP%d\t",i);
for(j=0;j<m;j++)
{
printf("%d\t\t",maxim[i][j]);
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
need[i][j]=maxim[i][j]-allo[i][j];
}
}
request();
return 0;
}
/* OUTPUT:
WELCOME TO BANKER'S ALGORITHM
ENTER THE NUMBER OF RESOURCES: 3
ENTER THE NUMBER OF PROCESS(s): 5
ENTER THE MAX AVAILABLE VALUE FOR RESOURCE R0: 10
ENTER THE MAX AVAILABLE VALUE FOR RESOURCE R1: 5
ENTER THE MAX AVAILABLE VALUE FOR RESOURCE R2: 7
ENTER THE MAX REQUIRED VALUE for P0,R0: 7
ENTER THE MAX REQUIRED VALUE for P0,R1: 5
ENTER THE MAX REQUIRED VALUE for P0,R2: 3
ENTER THE MAX REQUIRED VALUE for P1,R0: 3
ENTER THE MAX REQUIRED VALUE for P1,R1: 2
ENTER THE MAX REQUIRED VALUE for P1,R2: 2
ENTER THE MAX REQUIRED VALUE for P2,R0: 9
ENTER THE MAX REQUIRED VALUE for P2,R1: 0
ENTER THE MAX REQUIRED VALUE for P2,R2: 2
ENTER THE MAX REQUIRED VALUE for P3,R0: 2
ENTER THE MAX REQUIRED VALUE for P3,R1: 2
ENTER THE MAX REQUIRED VALUE for P3,R2: 2
ENTER THE MAX REQUIRED VALUE for P4,R0: 4
ENTER THE MAX REQUIRED VALUE for P4,R1: 3
ENTER THE MAX REQUIRED VALUE for P4,R2: 3
THE TABLE ENTERED FOR MAX NEEDED IS:
PROCESS R0 R1 R2
P0 7 5 3
P1 3 2 2
P2 9 0 2
P3 2 2 2
P4 4 3 3
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 0
ENTER THE REQUIRED VALUE OF RESOURCE R0: 0
ENTER THE REQUIRED VALUE OF RESOURCE R1: 1
ENTER THE REQUIRED VALUE OF RESOURCE R2: 0
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 0 1 0
P1 0 0 0
P2 0 0 0
P3 0 0 0
P4 0 0 0
THE PROCESS P0 RAN SUCCESSFULLY
THE PROCESS P1 RAN SUCCESSFULLY
THE PROCESS P2 RAN SUCCESSFULLY
THE PROCESS P3 RAN SUCCESSFULLY
THE PROCESS P4 RAN SUCCESSFULLY
THE SYSTEM IS IN SAFE STATE
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 1
ENTER THE REQUIRED VALUE OF RESOURCE R0: 2
ENTER THE REQUIRED VALUE OF RESOURCE R1: 0
ENTER THE REQUIRED VALUE OF RESOURCE R2: 0
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 0 0 0
P3 0 0 0
P4 0 0 0
THE PROCESS P0 RAN SUCCESSFULLY
THE PROCESS P1 RAN SUCCESSFULLY
THE PROCESS P2 RAN SUCCESSFULLY
THE PROCESS P3 RAN SUCCESSFULLY
THE PROCESS P4 RAN SUCCESSFULLY
THE SYSTEM IS IN SAFE STATE
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 2
ENTER THE REQUIRED VALUE OF RESOURCE R0: 3
ENTER THE REQUIRED VALUE OF RESOURCE R1: 0
ENTER THE REQUIRED VALUE OF RESOURCE R2: 2
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 0 0 0
P4 0 0 0
THE PROCESS P1 RAN SUCCESSFULLY
THE PROCESS P2 RAN SUCCESSFULLY
THE PROCESS P3 RAN SUCCESSFULLY
THE PROCESS P4 RAN SUCCESSFULLY
THE PROCESS P0 RAN SUCCESSFULLY
THE SYSTEM IS IN SAFE STATE
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 3
ENTER THE REQUIRED VALUE OF RESOURCE R0: 2
ENTER THE REQUIRED VALUE OF RESOURCE R1: 1
ENTER THE REQUIRED VALUE OF RESOURCE R2: 1
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 0
THE PROCESS P1 RAN SUCCESSFULLY
THE PROCESS P3 RAN SUCCESSFULLY
THE PROCESS P4 RAN SUCCESSFULLY
THE PROCESS P0 RAN SUCCESSFULLY
THE PROCESS P2 RAN SUCCESSFULLY
THE SYSTEM IS IN SAFE STATE
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 4
ENTER THE REQUIRED VALUE OF RESOURCE R0: 0
ENTER THE REQUIRED VALUE OF RESOURCE R1: 0
ENTER THE REQUIRED VALUE OF RESOURCE R2: 2
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 0 1 0
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
THE PROCESS P1 RAN SUCCESSFULLY
THE PROCESS P3 RAN SUCCESSFULLY
THE PROCESS P4 RAN SUCCESSFULLY
THE PROCESS P0 RAN SUCCESSFULLY
THE PROCESS P2 RAN SUCCESSFULLY
THE SYSTEM IS IN SAFE STATE
DO YOU HAVE A REQUEST?(y/n)y
ENTER THE PROCESS REQUESTING(0,1,2,3..): 0
ENTER THE REQUIRED VALUE OF RESOURCE R0: 1
ENTER THE REQUIRED VALUE OF RESOURCE R1: 1
ENTER THE REQUIRED VALUE OF RESOURCE R2: 2
THE ALTERED ALLOCATION TABLE IS:
PROCESS R0 R1 R2
P0 1 2 2
P1 2 0 0
P2 3 0 2
P3 2 1 1
P4 0 0 2
THE SYSTEM IS NOT IN SAFE STATE
WE ARE ROLLING BACK
WE ARE ROLLING BACK
WE ARE ROLLING BACK
DO YOU HAVE A REQUEST?(y/n)n
*/
In case you have any confusion in understanding the code or the concept,please feel free to ask.If you have any suggestion to improve this article,please let us know and thanks a lot in advance:)
No comments:
Post a Comment
Thanks for your valuable comment