Banker's algorithm:- The Banker's 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 EWD108. The name is by analogy with the
way that bankers account for liquidity constraints.
1. limitations:-
Specifically, it needs to know how much of each
resource a process could possibly request. In most systems, this information is
unavailable, making it impossible to implement the Banker's algorithm. Also, it
is unrealistic to assume that the number of processes is static since in most systems
the number of processes varies dynamically. Moreover, the requirement that a
process will eventually release all its resources is sufficient for the correctness of the
algorithm, however it is not sufficient for a practical system. Waiting for
hours for resources to be released is
usually not acceptable.
2. Algoritm:-
it is a step by step process.These parts are following as:
(1.) Resources:-
For the Banker's algorithm to work, it needs to know three things:
How much of each resource each
process could possibly request[CLAIMS]
How much of each resource each
process is currently holding[ALLOCATED]
How much of each resource the
system currently has available[AVAILABLE]
Claims: The Banker's Algorithm derives its name from the fact that this
algorithm could be used in a banking system to ensure that the bank does not
run out of resources, because the bank would never allocate its money in such a
way that it can no longer satisfy the needs of all its customers.
Available: A vector of length m indicates the number of available resources
of each type. If Available[j] = k, there are k instances of resource type Rj
available.
Allocation: An n×m matrix defines
the number of resources of each type currently allocated to each process. If
Allocation[i,j] = k, then process Pi is currently allocated k instance of
resource type
Example:-
Assuming that the system distinguishes between four types of resources, the
following is an example of how those resources could be distributed. Note that
this example shows the system at an instant before a new request for resources
arrives. Also, the types and number of resources are abstracted. Real systems,
for example, would deal with much larger quantities of each resource.
Total resources in system:
A B C D
2 1 0 0
Available system resources are:
A B C D
2 1 0 0
Processes :
A B C D
P1 0 0 1 2
P2 2 0 0 0
P3 0 0 3 4
Processes :
A B C D
P1 0 0 1 2
P2 2 7 5 0
P3 6 6 5 6
Need= maximum resources - currently allocated resources
Processes :
A B C D
P1 0 0 0 0
P2 0 7 5 0
P3 6 6 2 2
(2.) Safe and Unsafe States:-
It is possible for all processes to finish
executing . 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.
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. Any state where no such set exists is an unsafe state.
Example:-
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
[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
[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
[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 6D
(3.) 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
straight forward 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
Whether the system denies or postpones an
impossible or unsafe request is a decision specific to the operating system.
Example:-
The
new state of the system d be:
A B C
D
Free 2 1 0 0
Processes :
A B C
D
P1 0 0 1
2
P2 2 0 0
0
P3 0 0 3
0
Processes :
A B C
D
P1 0 0 1
2
P2 2 7 5
0
P3 6 6 5
6
Determine if this new state is safe
P1
can acquire 2 A, 1 B and 1 D resources and terminate
Then, P2 can acquire 2 B and 1 D resources and terminate
Finally, P3 can acquire 1B and 3 C resources and terminate
Assuming the request is granted, the new state would be:
Available system resources:
A B C
D
Free 3 0 1 2
Processes:
A B C
D
P1 1 2 2
1
P2 1 1 3
3
P3 1 2 1
0
Processes:
A B C
D
P1 3 3 2
2
P2 1 2 3
4
P3 1 3 5
0
Is this
state safe? Assuming P1, P2, and P3 request more of resource B and C.
P1
is unable to acquire enough B resources
P2
is unable to acquire enough B resources
P3
is unable to acquire enough B resources
/*PROGRAM TO IMPLEMENT BANKER'S ALGORITHM
*
--------------------------------------------*/
#include <stdio.h>
int curr[5][5], maxclaim[5][5], avl[5];
int alloc[5] = {0,0,0,0,0};
int maxres[5], running[5], safe=0;
int count = 0, i, j, exec, r, p,k=1;
int main()
{
printf("\nEnter the number of processes: ");
scanf("%d",&p);
for(i=0;i<p;i++)
{
running[i]=1;
count++;
}
printf("\nEnter the number of resources: ");
scanf("%d",&r);
for(i=0;i<r;i++)
{
printf("\nEnter the resource for instance %d: ",k++);
scanf("%d",&maxres[i]);
}
printf("\nEnter maximum resource table:\n");
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
scanf("%d",&maxclaim[i][j]);
}
}
printf("\nEnter allocated resource table:\n");
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
scanf("%d",&curr[i][j]);
}
}
printf("\nThe resource of instances: ");
for(i=0;i<r;i++)
{
printf("\t%d",maxres[i]);
}
printf("\nThe allocated resource table:\n");
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
printf("\t%d",curr[i][j]);
}
printf("\n");
}
printf("\nThe maximum resource table:\n");
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
printf("\t%d",maxclaim[i][j]);
}
printf("\n");
}
for(i=0;i<p;i++)
{
for(j=0;j<r;j++)
{
alloc[j]+=curr[i][j];
}
}
printf("\nAllocated resources:");
for(i=0;i<r;i++)
{
printf("\t%d",alloc[i]);
}
for(i=0;i<r;i++)
{
avl[i]=maxres[i]-alloc[i];
}
printf("\nAvailable resources:");
for(i=0;i<r;i++)
{
printf("\t%d",avl[i]);
}
printf("\n");
//Main
procedure goes below to check for unsafe state.
while(count!=0)
{
safe=0;
for(i=0;i<p;i++)
{
if(running[i])
{
exec=1;
for(j=0;j<r;j++)
{
if(maxclaim[i][j] -
curr[i][j] > avl[j]){
exec=0;
break;
}
}
if(exec)
{
printf("\nProcess%d is
executing\n",i+1);
running[i]=0;
count--;
safe=1;
for(j=0;j<r;j++) {
avl[j]+=curr[i][j];
}
break;
}
}
}
if(!safe)
{
printf("\nThe processes are in unsafe state.\n");
break;
}
else
{
printf("\nThe process is in safe state");
printf("\nSafe sequence is:");
for(i=0;i<r;i++)
{
printf("\t%d",avl[i]);
}
printf("\n");
}
}
}
/*SAMPLE
OUTPUT
-----------------
Disadvantages of the Banker's
Algorithm:-
It
requires the number of processes to be fixed; no additional processes can start
while it is executing.
It
requires that the number of resources remain fixed; no resource may go down for
any reason without the possibility of deadlock occurring.
It
allows all requests to be granted in finite time, but one year is a finite
amount of time.
Similarly, all of the processes guarantee that the resources loaned to
them will be repaid in a finite amount of time. While this prevents absolute
starvation, some pretty hungry processes might develop.
All
processes must know and state their maximum resource need in advance.
SUBMITTED BY = MANDEEP KAUR
CLASS=BSC (CS) 2ND YEAR
ROLL NO. =2304
