Practical 13: Write a C program to implement Banker's Algorithm in Operating System for deadlock avoidance
2024, April 3
13. Implementation of Banker's Algorithm in Operating System for deadlock avoidance
Banker's Algorithm is a resource allocation and deadlock avoidance algorithm used in operating systems to ensure that a computer system will not enter into a deadlock state. It simulates the allocation of predetermined resources to multiple processes in a way that avoids deadlock. The algorithm is named after the banking system, where the bank never allocates available cash in such a way that it can no longer satisfy the needs of all of its customers.
13.1. Concepts and Definitions
The Banker's Algorithm uses several data structures to keep track of the resources. The key concepts include:
- Available: A vector that indicates the number of available instances of each resource.
- Max: A matrix that represents the maximum demand of each process.
- Allocation: A matrix that represents the current allocation of each resource to each process.
- Need: A matrix indicating the remaining resource need of each process, which is calculated as Max - Allocation.
The algorithm proceeds by simulating each request and deciding whether it is safe to fulfill the request. A state is considered safe if there is at least one sequence of all processes in the system such that each process can request and obtain additional resources necessary to complete its designated task without causing a deadlock.
13.1.1. Algorithm of Banker's Algorithm
- Step 1: Initialize data structures to represent the number of available, allocated, maximum demand, and remaining need of resources for each process.
- Step 2: Find a sequence of processes where the remaining need of each process can be satisfied by the current available resources plus the resources held by all previously finished processes in the sequence.
- Step 3: If such a sequence exists, go to the next step. If no sequence is found, the system is in a deadlock state.
- Step 4: When a process requests a resource, determine if granting the request will leave the system in a safe state. A safe state is one where there exists a sequence that allows all processes to complete.
- Step 5: If the system remains in a safe state after the resource is allocated to the requesting process, grant the request. Otherwise, the process must wait for the resource.
- Step 6: Once a process has finished its job, it releases its resources and the available resources are updated.
- Step 7: Repeat the algorithm for each new resource request and release by the processes.
- Step 8: If all processes can be completed without any remaining unmet needs, then the system is in a safe state and free of deadlocks.
13.1.2. Implementation of Banker's Algorithm in C
The following C program demonstrates the implementation of the Banker's Algorithm. It assumes that there are a fixed number of resources and processes. Users will need to enter the maximum required resources, the allocation matrix, and the available resources at runtime.
#include <stdio.h>
#define P 5 // Number of processes
#define R 3 // Number of resources
// Function prototypes
void calculateNeed(int need[P][R], int max[P][R], int allot[P][R]);
int isSafe(int processes[], int avail[], int max[][R], int allot[][R]);
int main() {
int processes[] = {0, 1, 2, 3, 4};
// Available instances of resources
int avail[] = {3, 3, 2};
// Maximum R that can be allocated to 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}
};
// Check system is in safe state or not
isSafe(processes, avail, max, allot);
return 0;
}
void calculateNeed(int need[P][R], int max[P][R], int allot[P][R]) {
for (int i = 0; i < P; i++)
for (int j = 0; j < R; j++)
need[i][j] = max[i][j] - allot[i][j];
}
int isSafe(int processes[], int avail[], int max[][R], int allot[][R]) {
int need[P][R];
calculateNeed(need, max, allot);
int finish[P] = {0};
int safeSeq[P];
int work[R];
for (int i = 0; i < R; i++)
work[i] = avail[i];
int count = 0;
while (count < P) {
int found = 0;
for (int p = 0; p < P; p++) {
if (!finish[p]) {
int j;
for (j = 0; j < R; j++)
if (need[p][j] > work[j])
break;
if (j == R) {
for (int k = 0; k < R; k++)
work[k] += allot[p][k];
safeSeq[count++] = p;
finish[p] = 1;
found = 1;
}
}
}
if (!found) {
printf("System is not in a safe state\n");
return 0;
}
}
printf("System is in a safe state.\nSafe sequence is: ");
for (int i = 0; i < P; i++)
printf("%d ",safeSeq[i]);
printf("\n");
return 1;
}This program will check for the safe state of the system after any resource request and prints a safe sequence if one exists.
13.1.3. Alternate Implementation of Banker's Algorithm in C
Below is an alternate implementation for the Banker's Algorithm in C.
// Banker's Algorithm
#include <stdio.h>
int main()
{
// P0 , P1 , P2 , P3 , P4 are the Process names here
int n , m , i , j , k;
n = 5; // Number of processes
m = 3; // Number of resources
int alloc[ 5 ] [ 3 ] = { { 0 , 1 , 0 }, // P0 // Allocation Matrix
{ 2 , 0 , 0 } , // P1
{ 3 , 0 , 2 } , // P2
{ 2 , 1 , 1 } , // P3
{ 0 , 0 , 2 } } ; // P4
int max[ 5 ] [ 3 ] = { { 7 , 5 , 3 } , // P0 // MAX Matrix
{ 3 , 2 , 2 } , // P1
{ 9 , 0 , 2 } , // P2
{ 2 , 2 , 2 } , // P3
{ 4 , 3 , 3 } } ; // P4
int avail[3] = { 3 , 3 , 2 } ; // Available Resources
int f[n] , ans[n] , ind = 0 ;
for (k = 0; k < n; k++) {
f[k] = 0;
}
int need[n][m];
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++)
need[i][j] = max[i][j] - alloc[i][j] ;
}
int y = 0;
for (k = 0; k < 5; k++){
for (i = 0; i < n; i++){
if (f[i] == 0){
int flag = 0;
for (j = 0; j < m; j++) {
if(need[i][j] > avail[j]){
flag = 1;
break;
}
}
if ( flag == 0 ) {
ans[ind++] = i;
for (y = 0; y < m; y++)
avail[y] += alloc[i][y] ;
f[i] = 1;
}
}
}
}
int flag = 1;
for(int i=0;i<n;i++)
{
if(f[i] == 0)
{
flag = 0;
printf(" The following system is not safe ");
break;
}
}
if (flag == 1)
{
printf(" Following is the SAFE Sequence \ n ");
for (i = 0; i < n - 1; i++)
printf(" P%d -> " , ans[i]);
printf(" P%d ", ans[n - 1]);
}
return(0);
}