Banker's Algorithm
The Banker algorithm, sometimes referred to as the detection algorithm, is a resource allocation and deadlock avoidance algorithm developed by Edsger Dijkstra that tests for safety by simulating the allocation of predetermined maximum possible amounts of all resources, and then makes an "s-state" check to test for possible deadlock conditions for all other pending activities, before deciding whether allocation should be allowed to continue.
The algorithm was developed in the design process for the THE operating system and originally described (in Dutch) in EWD108.[1] When a new process enters a system, it must declare the maximum number of instances of each resource type that it may ever claim; clearly, that number may not exceed the total number of resources in the system. Also, when a process gets all its requested resources it must return them in a finite amount of time.
Example
Total system resources are:
A B C D
6 5 7 6
Available system resources are:
A B C D
3 1 1 2
Processes (currently allocated resources):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0
Processes (maximum resources):
A B C D
P1 3 3 2 2
P2 1 2 3 4
P3 1 3 5 0
Need = maximum resources - currently allocated resources
Processes (possibly needed resources):
A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0
Safe and Unsafe States
A state (as in the above example) is considered safe if it is possible for all processes to finish executing (terminate). Since the system cannot know when a process will terminate, or how many resources it will have requested by then, the system assumes that all processes will eventually attempt to acquire their stated maximum resources and terminate soon afterward. This is a reasonable assumption in most cases since the system is not particularly concerned with how long each process runs (at least not from a deadlock avoidance perspective). Also, if a process terminates without acquiring its maximum resource it only makes it easier on the system. A safe state is considered to be the decision maker if it's going to process ready queue.
Given that assumption, the algorithm determines if a state is safe by trying to find a hypothetical set of requests by the processes that would allow each to acquire its maximum resources and then terminate (returning its resources to the system). Any state where no such set exists is an unsafe state.
We can show that the state given in the previous example is a safe state by showing that it is possible for each process to acquire its maximum resources and then terminate.
P1 acquires 2 A, 1 B and 1 D more resources, achieving its maximum
[available resource: <3 1 1 2> - <2 1 0 1> = <1 0 1 1>]
The system now still has 1 A, no B, 1 C and 1 D resource available
P1 terminates, returning 3 A, 3 B, 2 C and 2 D resources to the system
[available resource: <1 0 1 1> + <3 3 2 2> = <4 3 3 3>]
The system now has 4 A, 3 B, 3 C and 3 D resources available
P2 acquires 2 B and 1 D extra resources, then terminates, returning all its resources
[available resource: <4 3 3 3> - <0 2 0 1> + <1 2 3 4> = <5 3 6 6>]
The system now has 5 A, 3 B, 6 C and 6 D resources
P3 acquires 1 B and 4 C resources and terminates.
[available resource: <5 3 6 6> - <0 1 4 0> + <1 3 5 0> = <6 5 7 6>]
The system now has all resources: 6 A, 5 B, 7 C and 6 D
Because all processes were able to terminate, this state is safe
For an example of an unsafe state, consider what would happen if process 2 was holding 2 units of resource B at the beginning.
Requests
When the system receives a request for resources, it runs the Banker's algorithm to determine if it is safe to grant the request. The algorithm is fairly straightforward once the distinction between safe and unsafe states is understood.
Can the request be granted?
If not, the request is impossible and must either be denied or put on a waiting list
Assume that the request is granted
Is the new state safe?
If so grant the request
If not, either deny the request or put it on a waiting list.
Program
/*Program to implement Banker's algorithm with p processes and 1 resource having multiple instances, where 1<=p<=10
Variable description: p -> number of processes, allocation[ ]- the number of allocated resources, max[ ]-number of maximum resources required, need=max-allocation, available-number of instances of resource available,flag->to keep track of processes which have been allocated the needed resources, sequence->to save safe sequence */
#include<stdio.h>
int main()
{
int p, allocation[10], max[10], need[10], available,i,j,flag[10],x=0,sequence[10],c=0;
printf("Enter the number of process \n");
scanf("%d",&p);
for (i=0;i<p;i++)
{
flag[i]=0; //initially no process's need is fulfilled
}
for(i=0;i<p;i++)
{
printf("Enter the allocation for process P[%d]\n",i);
scanf("%d",&allocation[i]);
printf("Enter the max for process P[%d]\n",i);
scanf("%d",&max[i]);
}
printf("Enter the available resources");
scanf("%d",&available);
for(i=0;i<p;i++)
{
need[i]=max[i]-allocation[i];
}
for(i=0;i<p;i++)
{
printf("Need of P[%d] is %d\n",i,need[i]);
}
for(i=0;i<p;i++)
{
for(j=0;j<p;j++)
{
if(flag[j]==0&&need[j]<=available)
{
available=available+allocation[j];
flag[j]=1;
printf("Process %d has been allocated resources\n",j);
sequence[c]=j;
c++;
}
}
}
for(i=0;i<p;i++)
{
if(flag[i]==0)
{
printf("system is in unsafe state\n");
x=1;
break;
}
}
if(x==0)
{
printf("System is in safe state\n");
printf("Safe sequence is \n");
for(i=0;i<p;i++)
{
printf("P[%d],",sequence[i]);
}
}
printf("\n");
}
Program
/*Program to implement
Banker's algorithm with p processes and r resources, where 1<=p<=100,
1<=r<=100
Variable description: p
-> number of processes, r->number of resources, allocation[ ][ ]- number
of allocated resources, max[ ][ ]-number of maximum resources required,
need=max-allocation, available[]-number of instances of each resource available
with system,flag->to keep track of processes which have been allocated
resources, sequence->to save safe sequence, count->to check whether need
for all the resources of a process can be granted */
#include<stdio.h>
int main()
{
int p,r, allocation[100][100],
max[100][100], need[100][100],
available[100],i,j,k,flag[100],x=0,sequence[100],c=0,count;
printf("Enter the number of
process \n");
scanf("%d",&p);
printf("Enter the number of
resources \n");
scanf("%d",&r);
for (i=0;i<p;i++)
{
flag[i]=0; //none of the process's need is
satisfied initially
}
for(i=0;i<p;i++) //loop for process
{
for(j=0;j<r;j++) //loop for resources
{
printf("Enter the allocation for process P[%d] of resource
%d\n",i,j);
scanf("%d",&allocation[i][j]);
printf("Enter the max for process P[%d] of resource
%d\n",i,j);
scanf("%d",&max[i][j]);
}
}
for(i=0;i<r;i++)
{
printf("Enter the available instances of resource %d\n", i);
scanf("%d",&available[i]);
}
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
need[i][j]=max[i][j]-allocation[i][j]; //need of each process
}
}
for(i=0;i<p;i++) //loop to print the calculated
need
{
printf("Need of P[%d] is:",i);
for(j=0;j<r;j++)
{
printf("%d ",need[i][j]);
}
printf("\n");
}
for(i=0;i<p;i++) //loop for iteration
{
for(j=0;j<p;j++) //loop
for process
{
count=0;
for(k=0;k<r;k++) //loop
for resource
{
if(flag[j]==0&&need[j][k]<=available[k]) //need[j][k] means need of jth process's kth resource
{
available[k]=available[k]+allocation[j][k];
count++;
if(count==r) //if true means need for all the resources can be satisfied
{
flag[j]=1; // process has been allocated resources
printf("Process %d has
been allocated resources\n",j);
sequence[c]=j; // array sequence stores the safe sequence. jth process is added to
safe sequence
c++;
}
continue; //if need of one resource is satisfied then we
check for next resource
}
break; // if need for
any resource of a process can not be satisfied, break the loop and check
the
//need of next process
}
}
}
for(i=0;i<p;i++)
{
if(flag[i]==0)
{
printf("system is in unsafe state\n");
x=1;
break;
}
}
if(x==0)
{
printf("System is in safe
state\n");
printf("Safe sequence is
\n");
for(i=0;i<p;i++)
{
printf("P[%d],",sequence[i]);
}
}
printf("\n");
}
