PROGRAM 4
Simulate Bankers Algorithm for Deadlock
Avoidance
DEADLOCK AVOIDANCE
❖ Simplest and useful model
❖ Process is required to declare max no. of resources of each type
needed.
❖ Resource allocation state is defined by:
1. Available resources
2. Allocated resources
3. Max. demand of process
SAFE STATE
❖ When a process requires an available resource, the system must
decide if immediate allocation leaves the system in safe state.
❖
❖
➢ Safe state => No Deadlocks.
➢ Unsafe state => Possibility of deadlock.
➢ Avoidance => System will never enter an unsafe state.
AVOIDANCE ALGORITHM
❖ Resource allocation graph uses a Single Instance.
❖ Banker’s Algorithm uses Multiple Instances.
BANKER’S ALGORITHM
❖ Multiple Instances
❖ When a process requests a resource, it may have to wait.
❖ When a process gets all the needed resources, it must return them
in a Finite amount of time.
❖ Each process must a priority claim maximum use.
DATA STRUCTURES FOR BANKER’S ALGORITHM
Let n = number of processes
m = number of resource types.
Available = vector of length m.
If available[j] = k, there are k instances of
resource types are Rj available.
Max = n x m Matrix.
If Max[i, j] = k, then process Pi may request at most
k instances of resources type Rj.
Allocation = n x m Matrix.
If Allocation[i, j] = k, then Pi is currently
currently allocated k instances of Rj.
Need = n x m Matrix.
If need[i, j] = k, then Pi may need k more
Instances of Rj to complete its tasks.
Need[i ,j] = Max[i, j] - Allocation[i, j]
PROBLEM FOR BANKER’S ALGORITHM
P ALLOCATION MAX AVAILABLE NEED
R1 R2 R3 R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 0 1 0 7 5 3 3 3 2 7 4 3
P2 2 0 0 3 2 2 1 1 2
P3 3 0 2 9 0 2 6 0 0
P4 2 1 2 2 2 2 0 1 1
P5 0 0 2 4 3 3 4 3 1
Step 1
To find need
Need = Max - Allocated
P1 => max = [7 ,5 ,3] ; allocated = [0 ,1 ,0]
need = [7 ,5 ,3] - [0 ,1 ,0]
= [7 ,4 ,3]
P2 => max = [3 ,2 ,2] ; allocated = [2 ,0 ,0]
need = [3 ,2 ,2] - [2 ,0 ,0]
= [1 ,2 ,2]
P3 => max = [9 ,0 ,2] ; allocated = [3 ,0 ,2]
need = [9 ,0 ,2] - [3 ,0 ,2]
= [6 ,0 ,0]
P4 => max = [2 ,2 ,2] ; allocated = [2 ,1 ,1]
need = [2 ,2 ,2] - [2 ,1 ,1]
= [0 ,1 ,1]
P5 => max = [4 ,3 ,3] ; allocated = [0 ,0 ,2]
need = [4 ,3 ,1] - [0 ,0 ,2]
= [4 ,3 ,1]
Step 2
To verify the condition for each process.
Need <= Available
P1 -> need [7 ,4 ,3] !<= [3 ,3 ,2] available
Not Satisfied
P2 -> need [1, 2, 2] <= [3, 3, 2] available
Condition Satisfied
[New Available = Actual Available + Allocated]
=>New available = [3 ,3 ,2] + [2 ,0 ,0] = [5 ,3 ,2]
P3 -> need [6 ,0 ,0] !<= [5 ,3 ,2] available
Not Satisfied.
P4 -> need [0 ,1 ,1] <= [5, 3, 2] available
Condition Satisfied.
=>New available = [5 ,3 ,2] + [2 ,1 ,1] = [7 ,4 ,3]
P5 -> need [4 ,3 ,7] <= [7, 4, 3] available
Condition Satisfied.
=>New available = [7 ,4 ,3] + [0 ,0 ,2] = [7 ,4 ,5]
Step 3
Now checking the condition again for P1 & P3
P1 => need [7 ,4 ,3] !<= [7 ,4 ,5] available
Not Satisfied as not Possible.
P3 => need [6 ,0 ,0] <= [7, 4, 5] available
Condition Satisfied.
=>New available = [7 ,4 ,5] + [3 ,0 ,2] = [10 ,4 ,7]
P1 => need [7 ,4 ,3] <= [10 ,4 ,7] available
Condition Satisfied.
=>New available = [10 ,4 ,7] + [0 ,1 ,0] = [10 ,5 ,7]
Therefore,
Safe Sequence is {P2, P4, P5, P3, P1}
C CODE IMPLEMENTATION FOR BANKERS ALGORITHM
#include<stdio.h>
int main()
{
int p, c, count = 0, i, j, alc[5][3], max[5][3], need[5][3], safe[5],
available[3], done[5], terminate = 0;
printf("Enter the number of process and resources : ");
scanf("%d %d", & p, & c);
printf("enter allocation of resource of all process %dx%d matrix : ", p,
c);
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
scanf("%d", & alc[i][j]);
}
}
printf("enter the max resource process required %dx%d matrix : ", p,
c);
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
scanf("%d", & max[i][j]);
}
}
printf("enter the available resource : ");
for (i = 0; i < c; i++)
scanf("%d", & available[i]);
printf("\n need resources matrix are\n");
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
need[i][j] = max[i][j] - alc[i][j];
printf("%d\t", need[i][j]);
}
printf("\n");
}
for (i = 0; i < p; i++) {
done[i] = 0;
}
while (count < p)
{
for (i = 0; i < p; i++)
{
if (done[i] == 0)
{
for (j = 0; j < c; j++)
{
if (need[i][j] > available[j])
break;
}
if (j == c)
{
safe[count] = i;
done[i] = 1;
for (j = 0; j < c; j++)
{
available[j] += alc[i][j];
}
count++;
terminate = 0;
}
else
{
terminate++;
}
}
}
if (terminate == (p - 1)) {
printf("safe sequence does not exist");
break;
}
}
if (terminate != (p - 1))
{
printf("\n available resource after completion :\n");
for (i = 0; i < c; i++)
{
printf("%d\t", available[i]);
}
printf("\n safe sequence are :\n");
for (i = 0; i < p; i++)
{
printf("p%d\t", safe[i]);
}
}
return 0;
}
#include<stdio.h>
int main()
{
int p, c, count = 0, i, j, alc[5][3], max[5][3], need[5][3], safe[5],
available[3], done[5], terminate = 0;
printf("Enter the number of process and resources : ");
scanf("%d %d", & p, & c);
printf("enter allocation of resource of all process %dx%d matrix : ", p,
c);
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
scanf("%d", & alc[i][j]);
}
}
printf("enter the max resource process required %dx%d matrix : ", p,
c);
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
scanf("%d", & max[i][j]);
}
}
printf("enter the available resource : ");
for (i = 0; i < c; i++)
scanf("%d", & available[i]);
printf("\n need resources matrix are\n");
for (i = 0; i < p; i++) {
for (j = 0; j < c; j++) {
need[i][j] = max[i][j] - alc[i][j];
printf("%d\t", need[i][j]);
}
printf("\n");
}
for (i = 0; i < p; i++) {
done[i] = 0;
}
while (count < p)
{
for (i = 0; i < p; i++)
{
if (done[i] == 0)
{
for (j = 0; j < c; j++)
{
if (need[i][j] > available[j])
break;
}
if (j == c)
{
safe[count] = i;
done[i] = 1;
for (j = 0; j < c; j++)
{
available[j] += alc[i][j];
}
count++;
terminate = 0;
}
else
{
terminate++;
}
}
}
if (terminate == (p - 1)) {
printf("safe sequence does not exist");
break;
}
}
if (terminate != (p - 1))
{
printf("\n available resource after completion :\n");
for (i = 0; i < c; i++)
{
printf("%d\t", available[i]);
}
printf("\n safe sequence are :\n");
for (i = 0; i < p; i++)
{
printf("p%d\t", safe[i]);
}
}
return 0;
}
OUTPUT
