Banker's Algorithm- Deadlock Detection
The Banker's Algorithm is a deadlock avoidance algorithm used in operating systems to prevent deadlocks in a system with limited resources. It was developed by Edsger Dijkstra in 1965. The algorithm ensures that the system will allocate resources in such a way that it will avoid deadlock, even if resources are requested in an arbitrary order.
Let's break down the Banker's Algorithm into steps:
1. System Initialization:- At the beginning, the system must know the total number of resources of each type and the maximum demand of each process.
- It also needs to keep track of the currently available resources of each type.
- When a process requests resources, the system must check if granting those resources would put it in an unsafe state (i.e., could potentially lead to a deadlock).
- If the request can be granted without causing an unsafe state, the resources are allocated.
- Otherwise, the process must wait until the requested resources can be safely allocated.
- The safety algorithm employs a method similar to the concept of a banker managing loans. It checks if there's enough resources in the system to satisfy the maximum needs of some processes.
- It does this by temporarily allocating resources to processes, assuming they finish and release their resources. Then, it checks if there are enough resources to satisfy the needs of other processes.
- If there's a sequence of allocations and deallocations that allows all processes to complete, then the system is safe, and the resources can be allocated. Otherwise, the system must deny the resource request.
Let's say you have three types of resources (A, B, and C) with the following available instances: (3,3, 2). You also have 5 processes P0-P4, each with maximum resource needs and allotment as follows:
Let max matrix represent max resource needs
Max Requirement
7-5-3-P0
3-2-2-P1
9-0-2-P2
2-2-2-P3
4-3-3-P4
Let allot matrix represent current resource allotment
Resource Allotment
0-1-0-P0
2-0-0-P1
3-0-2-P2
2-1-1-P3
0-0-2-P4
The need matrix represent additional need ( max - allot)
7-4-3-P0
1-2-2-P1
6-0-0-P2
0-1-1-P3
4-3-1-P4
Let avail array represent the available resources [3,3,2]
Bankers algorithm checks whether this can lead to a safe state.It is noted that P1 can complete the task if the instance [1,2,2] is available.Now the available resources will be avail=avail+allot=[4,5,4].Now P3's resource requirement can be satisfied.If we proceed in the order
P1-P3-P4-P0-P2
Then all the processes can complete the task with out leaving the system into a deadlock state and hence this is a safe state.
Conclusion:
The Banker's Algorithm ensures that resources are allocated in a way that avoids deadlock by only granting requests that won't put the system into an unsafe state. It's an essential tool in operating systems for managing resource allocation efficiently and safely.
//****************************************
// C -Implementation Bankers Algorithm
//****************************************
#include<stdio.h>
// Define the maximum number of processes and resources
#define P 5 // Number of processes
#define R 3 // Number of resources
void print(int m[][R])
{
for(int i=0;i<P;i++)
{
for(int j=0;j<R;j++)
printf("%d-",m[i][j]);
printf("\n");
}
}
// Function to check if the requested resources can be allocated to the process safely
int isSafe(int processes[], int available[], int max[][R], int allot[][R]) {
int need[P][R];
int finish[P] = {0}; // Initialize finish array to track whether a process has finished
// Calculate need matrix
for (int i = 0; i < P; i++) {
for (int j = 0; j < R; j++) {
need[i][j] = max[i][j] - allot[i][j];
}
}
printf("Resource need\n");
print(need);
int work[R];
for (int i = 0; i < R; i++) {
work[i] = available[i];
}
int count = 0;
while (count < P)
{
int found = 0; // Flag to check if a process can be allocated resources in this iteration
for (int i = 0; i < P; i++)
{
if (finish[i] == 0)
{
int j,flag=1;
for (j = 0; j < R; j++)
{
if (need[i][j] > work[j])
{
flag=0;break;
}
}
if (flag == 1)
{
// Process can be allocated resources
printf("Available Resources");
for (int k = 0; k < R; k++)
{printf("-%d",work[k]);}
printf("\nprocess-p%d can be allocated resources",i);
for (int k = 0; k < R; k++)
{printf("-%d",need[i][k]);}
for (int k = 0; k < R; k++)
{
work[k] += allot[i][k];
}
printf("\n");
finish[i] = 1;
found = 1;
count++;
}
}
}
if (found == 0)
{
// If no process can be allocated resources, the system is not in a safe state
return 0;
}
}
// If all processes are allocated resources safely, the system is in a safe state
return 1;
}
// Banker's Algorithm function to allocate resources to processes
void bankerAlgorithm(int processes[], int available[], int max[][R], int allot[][R]) {
if (isSafe(processes, available, max, allot)) {
printf("Safe state, allocating resources...\n");
// Allocate resources to processes (for example)
// Your code to allocate resources goes here
} else {
printf("Unsafe state, cannot allocate resources. Possible deadlock.\n");
}
}
int main() {
int processes[] = {0, 1, 2, 3, 4}; // Process IDs
int available[] = {3, 3, 2}; // Available instances of resources
// Maximum resource needs of processes
int max[P][R] = {
{7, 5, 3},
{3, 2, 2},
{9, 0, 2},
{2, 2, 2},
{4, 3, 3}
};
// Resources currently allocated to processes
int allot[P][R] = {
{0, 1, 0},
{2, 0, 0},
{3, 0, 2},
{2, 1, 1},
{0, 0, 2}
};
printf("Max Requirement\n");
print(max);
printf("Resource Allotment\n");
print(allot);
bankerAlgorithm(processes, available, max, allot);
return 0;
}
Max Requirement
7-5-3-
3-2-2-
9-0-2-
2-2-2-
4-3-3-
Resource Allotment
0-1-0-
2-0-0-
3-0-2-
2-1-1-
0-0-2-
Resource need
7-4-3-
1-2-2-
6-0-0-
0-1-1-
4-3-1-
Available Resources-3-3-2
process-p1 can be allocated resources-1-2-2
Available Resources-5-3-2
process-p3 can be allocated resources-0-1-1
Available Resources-7-4-3
process-p4 can be allocated resources-4-3-1
Available Resources-7-4-5
process-p0 can be allocated resources-7-4-3
Available Resources-7-5-5
process-p2 can be allocated resources-6-0-0
Safe state, allocating resources...
Comments
Post a Comment