Deadlock Avoidance Program In C
Introduction:
Banker's Algorithm is referred as the Deadlock avoidance algorithm and is widely used as a Deadlock detecting Algorithm. When there is a Mutual Exclusion, Circular Wait, No Participation, or Circular Wait circumstance, a stalemate condition develops.
The banker's Algorithm checks for a safe state, analyses the situation for probable activities, and determines whether to continue the distribution of resources or not.
Characteristics of Banker’s Algorithm:
Important aspects of the banker's algorithm include the following:
- Maintain a large number of resources that at least one client can use.
- Once a process has received all of its resources, it must return them within a set time frame.
- A process must wait when it makes a resource request.
- The system only has so many resources available.
- Maximum resource allocation feature in advance.
Notations of Banker’s Algorithm:
X: Denotes the system's overall process count.
Y: Denotes how many resources are available overall in the system.
Available- [I: Y]:
Specifies which resources can be accessed and available.
Max- [l:X,l:Y]:
Expression of the maximum number of resources of type j or processes,
Allocation- [l:X,l:Y]:
Provide the process where you acquired the resource of type j.
Example for Banker’s Algorithm:
An illustration of Banker's algorithm:
- Assume that there are 5 processes, with resources A, B, and C allotted to P1, P2, P3, P4, and P5.
- Their total requirement has been met, and we must now utilise Banker's method to determine their remaining requirement and obtain a series of processes that is in a secure condition.
- A total of 10, B five, and C seven resources are provided.
- By locating the accessible resources and populating the table below, let's examine how the algorithm functions.
In this case, Remaining Need = (Maximum Need – Allocation).
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 7 4 3 | |
P2 | 2 0 0 | 3 2 2 | 1 2 2 | |
P3 | 3 0 2 | 9 0 2 | 6 0 0 | |
P4 | 2 1 1 | 4 2 2 | 2 1 1 | |
P5 | 0 0 2 | 5 3 3 | 5 3 1 |
To determine the resources that are available, we must multiply the total by the allocation.
Total = [0+2+3+2+0] = 7 for A.
Available = [10-7] = 3
Total for B is [1+0+0+1+0] =2.
Available = [5-2] = 3
Total = [0+0+2+1+2] =5 for C.
Available = [7-5] = 2
1st Iteration:
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 1 2 2 | |
P3 | 3 0 2 | 9 0 2 | 6 0 0 | |
P4 | 2 1 1 | 4 2 2 | 2 1 1 | |
P5 | 0 0 2 | 5 3 3 | 5 3 1 |
- We now need to determine which processes can make use of the resources that are available. Compare the remaining requirements for each process to the resources at hand.
- P1 requires 7, 4, and 3, but has only 3, 2, and 3. The resources are unavailable to it. P2 requires 1, 2, and 2, while having access to 3, 3, and 2. It is workable. As a result, P2 should be added as the first process in the series.
- and find new available from P2, then repeat the previous stages. Allocation of P2+ new available (2+3), (0+3), (0+2) = [5, 3, 2]
2nd Iteration:
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 5 3 2 | 1 2 2 |
P3 | 3 0 2 | 9 0 2 | 6 0 0 | |
P4 | 2 1 1 | 4 2 2 | 2 1 1 | |
P5 | 0 0 2 | 5 3 3 | 5 3 1 |
P3 requires 6, 0, 0, but has only 5, 3, 2. So switch to P4 P4 has 5, 3, 2, but needs 2, 1; it has 1. The resources are used by P4. Add P4 to the formula: <P2, P4>
As of right now, P4 = (5+2), (3+1), (2+1) = 7, 4, 3.
3rd Iteration:
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 5 3 2 | 1 2 2 |
P3 | 3 0 2 | 9 0 2 | 7 4 3 | 6 0 0 |
P4 | 2 1 1 | 4 2 2 | 2 1 1 | |
P5 | 0 0 2 | 5 3 3 | 5 3 1 |
P5 needs 5, 3, 1, and there are 7, 4, 3 resources available, thus P5 can use them.
P5 should be added after< P2, P4, and P5>
Utilising P5=(0+7),(0+4),(2+3)=(7,4,5) is now possible.
4th Iteration:
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 5 3 2 | 1 2 2 |
P3 | 3 0 2 | 9 0 2 | 7 4 3 | 6 0 0 |
P4 | 2 1 1 | 4 2 2 | 7 4 5 | 2 1 1 |
P5 | 0 0 2 | 5 3 3 | 5 3 1 |
P1 is available in 7,4,5, and P1 is necessary in 7,4,3. P1 can use the resources as a result.
P1 is added to the sequence. < P2, P4, P5, P1 >
With P1=(0+7),(1+4),(0+5)=(7,5, 5) it is now possible.
5th Iteration:
Processes | Allocation | Max Need | Available | Remaining Need |
A B C | A B C | A B C | A B C | |
P1 | 0 1 0 | 7 5 3 | 3 3 2 | 7 4 3 |
P2 | 2 0 0 | 3 2 2 | 5 3 2 | 1 2 2 |
P3 | 3 0 2 | 9 0 2 | 7 4 3 | 6 0 0 |
P4 | 2 1 1 | 4 2 2 | 7 4 5 | 2 1 1 |
P5 | 0 0 2 | 5 3 3 | 7 5 5 | 5 3 1 |
P3 has 7, 5, 5 available and 6, 0 necessary. It can therefore use the resources. P3 is added to the sequence. < P2, P4, P5, P1, P3 >
In order to avoid a deadlock, the processes should run in the following order: < P2, P4, P5, P1, and P3>.
Algorithm for deadlock Avoidance:
The total number of processes is taken to be n, and the number of resource categories is taken to be m.
Allocation:
- Defines the quantity of resources that are currently devoted to a process.
- 2-D array, n*m in size.
- Allocate[i,j]=k means that processing Pi will use 'k' instances of the resource Rj.
Maximum need:
- Specifies how many resources a process will require.
- 2-D array, n*m in size.
- Max_need[i,j]=Max[i,j]-Allocate[i,j].
Available:
- Specifies how many resources are available for a process.
- m-dimensional 1-D array.
- The resource type Rj has k instances, therefore Available[j]=k.
Max Remaining need:
- Establishes the maximum demand for each system process.
- 2-D array, n*m in size.
- The resource type Rj requires a maximum of k instances of the process Pi when Max[i,j] = k.
Two algorithms are used in the Banker's Algorithm.
Safety algorithm: This algorithm determines whether the system exists in a safe state.
Resource-Request Algorithm: This algorithm executes operations in response to requests.
Algorithm for Safe State:
1) Assume that Work and Finish are vectors of size m and n, respectively.
Initialization: Work = Avail
Finish[i] = false; for i=1, 2,...n
2) Look for such that 'i'
a) Finish[i] = false
b) Need [i] <= Work
if such a 'i' doesn't exist
proceed to step (4)
3) Work = Work + Allocate[i]
Finish[i] = true
proceed to step (2)
4) if Finish [i] is equal to true for all i
The system is in a secure or safe state.
Algorithm for Resource Request:
Consider a Request for Process Pi that is a vector.
Process Pi needs k instances of Resource Rj, as shown by Request[i][j]=k.
1) If Req[i] <= Need[i]
Proceed to step (2) ;
else
As the procedure exceeds its maximum claim, raise an error condition.
2) If Req[i] <= Avail
Proceed to step (3);
else
Wait because there aren't any resources at this time.
3)By updating the state as follows, pretend to have assigned the resources required to process Pi.
Avail = Avail – Req[i]
Allocate[i] = Allocate[i] + Req[i]
Need[i] = Need[i]– Req[i]
Program for Implementing the Deadlock Avoidance Algorithm (Banker’s Algorithm):
#include <stdio.h>
#include <conio.h>
void main()
{
int k=0,a=0,b=0,instance[5],avail[5],op[5],allocate[10][5],need[10][5],MAX[10][5],n_process,P[10],n_resources, c=0,i, j;
printf("\nEnter no of resources required: ");
scanf("%d", &n_resources);
printf("\n Enter the maximum number of each resource instances :\n");
for (i=0;i<n_resources;i++)
{
avail[i]=0;
printf("%c= ",(i+97));
scanf("%d",&instance[i]);
}
printf("\n Enter no of processes : ");
scanf("%d", &n_process);
printf("\n Enter allocation matrix \n ");
for (i=0;i<n_resources;i++)
printf(" %c",(i+97));
printf("\n");
for (i=0;i <n_process;i++)
{
P[i]=i;
printf("P[%d] ",P[i]);
for (j=0;j<n_resources;j++)
{
scanf("%d",&allocate[i][j]);
avail[j]+=allocate[i][j];
}
}
printf("\nEnter MAX matrix \n ");
for (i=0;i<n_resources;i++)
{
printf(" %c",(i+97));
avail[i]=instance[i]-avail[i];
}
printf("\n");
for (i=0;i <n_process;i++)
{
printf("P[%d] ",i);
for (j=0;j<n_resources;j++)
scanf("%d", &MAX[i][j]);
}
printf("\n");
A: a=-1;
for (i=0;i <n_process;i++)
{
c=0;
b=P[i];
for (j=0;j<n_resources;j++)
{
need[b][j] = MAX[b][j]-allocate[b][j];
if(need[b][j]<=avail[j])
c++;
}
if(c==n_resources)
{
op[k++]=P[i];
for (j=0;j<n_resources;j++)
avail[j]+=allocate[b][j];
}
else
P[++a]=P[i];
}
if(a!=-1)
{
n_process=a+1;
goto A;
}
printf("\t <");
for (i=0;i<k;i++)
printf(" P[%d] ",op[i]);
printf(">");
getch();
}
OUTPUT:
![Deadlock Avoidance Program In C](https://static.tutorialandexample.com/c/deadlock-avoidance-program-in-c1.png)
Banker’s Algorithm Constraints:
- The processes must have to predict the maximum number of resources required as soon as they are been accessible to the system, which is impossible to be predicted in before.
- Unlike interactive systems, this algorithm maintains a fixed number of processes, which is impossible.
- For this algorithm to work, the available resources must be a fixed number. The algorithm would fail if a component of infrastructure is detected and went unexpectedly offline.
- Because the method must be executed for each and every process when there are several processes and resources, the overhead cost caused by the algorithm may be substantial.
Advantages of Banker’s Algorithm:
The banker's algorithm has a few benefits, which are as follows:
- The process can utilize the most resources available thanks to this algorithm's max resource attribute.
- It aids in the management of all resources by the operating system.
- At least one process can always be satisfied by some of its resources.
- The process returns every resource it was given after it has been used.
Disadvantages of Banker’s Algorithm:
The following are disadvantages of utilizing the banker's algorithm:
- It prevents the process from changing its maximum need during processing.
- It enables all requests to be granted in a constrained amount of time, but one year is the set duration.
- All processes must be aware of and explicitly specify their maximum resource requirements.
Conclusion:
- Deadlock Avoidance Algorithm is the name given to Banker's Algorithm.
- Furthermore, it serves as a deadlock detection algorithm.
- By figuring out how to allocate the most resources possible, it checks for the safe condition.
- Interactive systems are not conceivable since there are a fixed number of processes.
- Consequently, the necessity for a dynamic system exists.