Banker’s Algorithm in C
Introduction
Before doing a "s-state" check to look for potential activities and deciding if allocation should be allowed to continue, the banker's algorithm, a resource allocation and deadlock avoidance algorithm, tests resource allocation for predetermined maximum quantities of all resources.
Why is it called the banker's algorithm?
It was created by Edsger Dijkstra. The avoidance algorithm is another name for the Banker's Algorithm. Whenever a resource request is made, it is intended to check the safe state.
The reason the banker's algorithm is so titled is that it uses a bank as an analogy, where customers can request cash withdrawals. Cash is lent to the customer based on some data. More cash than what the customer has asked, and the whole amount of cash on hand cannot be given by the banker. Because it uses a bank analogy, this method is known as the banker's algorithm.
The following list contains the fundamental data structures necessary to implement this algorithm.
Let n represent the overall system process count and m represent the overall system resource type count.
- Available: There is an m-length vector available. It displays the quantity of each sort of resource that is available. If Available[i] = k, then there are k instances of resource Ri available.
- Max: Max is an n-by-m matrix that represents the highest demand for each process. Process If Max I j] = k, Pi can request a maximum of k instances of resource type Rj.
- Allocation: The number of resources of each type that are currently assigned to each process is listed in the allocation matrix, which is a n x m matrix. Pi k instances of the resource type are allocated by allocation I j] = k. Rj.
- Need: Each process' remaining resource requirements are shown in an n-by-m matrix. Process Pi may need k additional instances of resource type Rj to finish the task if Need I j] = k.
Algorithm for Safety
An explanation of the process for figuring out whether a system is in a safe condition is provided below:
1. Assume that Work and Finish are represented by the two vectors m and n, respectively.
Beginning with "Work = Available,"
Finish[i], where I ranges from 1 to n, is false.
2. Find an I so that
a) Finish[i] = false.
b) If there is no such I, proceed to step (4). Needi = Work
3. Allocation[i] is equal to Work + Work Finish[i] as the actual next step (2)
4. If Finish I = true for each and every I the system is in a secure state.
Algorithm for Resource Requests
Let Request be a list of requests to process Pi. Request [j] = k indicates that Process Pi has asked for k instances of resources of type Rj. When process Pi makes a request for resources, the following things take place:
1) If Requesti >= Needi, move on to step 2, otherwise indicate an error condition because there are too many claims for the process to handle.
2) If Requesti = Accessible, if you don't move on to step 3, Pi will have to wait since the resources aren't available.
3) Alter the state so that it appears as though the system has provided Pi with the necessary resources.
Requested minus Available equals Available
Allocationi = Allocationi - Requesti Needi = Needi - Requesti
Program for Banker’s Algorithm in C
#include <stdio.h>
int curr [ 5 ][ 5 ], max_claim [ 5 ][ 5 ] , avlble [ 5 ] ;
int allocation [ 5 ] = { 0, 0, 0, 0, 0 } ;
int maxres [ 5 ], running [ 5 ], safe = 0 ;
int counter = 0, i, j, exec, rsrces, prcesses, z = 1 ;
int main ( )
{
printf ( "\nEnter number of processes: " ) ;
scanf ( "%d", &prcesses ) ;
for ( i = 0 ; i < prcesses ; i++ )
{
running[i] = 1 ;
counter++ ;
}
printf ( "\nEnter number of resources: " ) ;
scanf ( "%d", &rsrces ) ;
printf ( "\nEnter Claim Vector:" ) ;
for ( i = 0 ; i < rsrces ; i++ )
{
scanf ( "%d", &maxres[i] ) ;
}
printf ( "\nEnter Allocated Resource Table:\n" ) ;
for ( i = 0 ; i < prcesses ; i++ )
{
for ( j = 0 ; j < rsrces ; j++ )
{
scanf ( "%d", &curr[i][j] ) ;
}
}
printf ( "\nEnter Maximum Claim Table:\n" ) ;
for ( i = 0 ; i < prcesses ; i++ )
{
for ( j = 0 ; j < rsrces ; j++ )
{
scanf ( "%d", &max_claim[i][j] ) ;
}
}
printf ( "\nThe Claim Vector is: " ) ;
for ( i = 0 ; i < rsrces ; i++ )
{
printf ( "\t%d", maxres[i] ) ;
}
printf ( "\nThe Allocated Resource Table:\n" ) ;
for ( i = 0 ; i < prcesses ; i++ )
{
for ( j = 0 ; j < rsrces ; j++ )
{
printf ( "\t%d", curr[i][j] ) ;
}
printf ( "\n" ) ;
}
printf ( "\nThe Maximum Claim Table:\n" ) ;
for ( i = 0 ; i < prcesses ; i++ )
{
for ( j = 0 ; j < rsrces ; j++ )
{
printf ( "\t%d", max_claim[i][j] ) ;
}
printf ( "\n" ) ;
}
for ( i = 0 ; i < prcesses ; i++ )
{
for ( j = 0 ; j < rsrces ; j++ )
{
allocation[j] += curr[i][j] ;
}
}
printf ( "\nAllocated resources:" ) ;
for ( i = 0 ; i < rsrces ; i++ )
{
printf ( "\t%d", allocation[i] ) ;
}
for ( i = 0 ; i < rsrces ; i++ )
{
avlble[i] = maxres[i] - allocation[i] ;
}
printf ( "\nAvailable resources:" ) ;
for ( i = 0 ; i < rsrces ; i++ )
{
printf ( "\t%d", avlble[i] ) ;
}
printf ( "\n" ) ;
while ( counter != 0 )
{
safe = 0 ;
for ( i = 0 ; i < prcesses ; i++ )
{
if ( running[i] )
{
exec = 1 ;
for ( j = 0 ; j < rsrces ; j++ )
{
if ( max_claim[i][j] - curr[i][j] > avlble[j] )
{
exec = 0 ;
break ;
}
}
if ( exec )
{
printf ( "\nProcess%d is executing\n", i + 1 ) ;
running[i] = 0 ;
counter-- ;
safe = 1 ;
for ( j = 0 ; j < rsrces ; j++ )
{
avlble[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 ( "\nAvailable vector:" ) ;
for ( i = 0 ; i < rsrces ; i++ )
{
printf ( "\t%d", avlble[i] ) ;
}
printf ( "\n" ) ;
}
}
return 0 ;
}
Input:
Enter number of processes: 2
Enter number of resources: 2
Enter Claim Vector:1
Output:
Enter Allocated Resource Table:
Enter Maximum Claim Table:
The Claim Vector is: 1 0
The Allocated Resource Table:
0 0
0 0
The Maximum Claim Table:
0 0
0 0
Allocated resources: 0 0
Available resources: 1 0
Process1 is executing
The process is in safe state
Available vector: 1 0
Process2 is executing
The process is in safe state
Available vector: 1 0
Explanation:
- The processes must be able to predict the maximum quantity of resources needed as they come into the system, which can be done in a timely manner.
- This technique maintains a fixed number of processes, unlike interactive systems.
- This strategy only works if a certain amount of resources are accessible to disperse. In the event that a device malfunctioned and unexpectedly went down, the algorithm would not work.
- When there are multiple processes and resources, the method will incur overhead costs because it needs to be called for each process.