Deadlock Prevention Using Bankers Algorithm In C

The banker's algorithm derives its name from its application in the banking industry to evaluate loan approvals for individuals. In a scenario where a bank manages n account holders, each with a distinct balance of S, loan requests trigger a review process. The bank initiates by subtracting the loan amount from its total funds, proceeding to authorize the loan solely if the remaining balance surpasses S. This precaution ensures that in the event all account holders decide to withdraw their funds simultaneously, the bank can facilitate the transactions without any issues. Essentially, the bank prioritizes maintaining a secure and reliable financial position to meet all client demands without compromise.

The Banker's Algorithm is executed utilizing the subsequent data structures:

Let n represent the quantity of processes within the system, while m denotes the number of types of resources available.

Available:

✅ This 1-d array of size 'm' lists the number of resources of each category that are currently available.
✅ There are 'k' instances of the resource type if Available[j] = Rj
✅ The maximum demand of each process in a system is specified by a 2-d array of size 'n*m'.
✅ Process Pi may request a maximum of 'k' instances of resource type Rj if Max[i, j] = k.

The current distribution of resources for each process is defined by a two-dimensional array of dimensions 'n*m'.

Each process's resource allocation is represented as Allocation[i, j] = k, indicating that process Pi currently holds 'k' units of the j-th resource type.

Need:

✅ The remaining resource needs of each process are shown in a 2-d array of size 'n*m'.
✅ Process is shown by Need[i, j] = k. Right now, Pi requires "k" instances of the resource type. Rj
✅ Allocation[i, j] - Maximum[i, j] = Need[i, j]

The resources assigned to handle Pi are recognized as Allocationi, while the additional resources required by process Pi to complete its tasks are identified as Needi.

The security procedure and the asset requisition algorithm together form the banker's algorithm.

Algorithm for Safety

The method for checking whether a system is in a secure state can be detailed as follows:

Example


1) Assume Work and Finish are two vectors, each with lengths of m and n.
Initialize: Work = Available
Finish[i] is false when i=1, 2, 3, 4...n
2) Find an I such that both 
a) Finish[i] = false 
b) Needi <= Work 
if such an I does not exist. goto  step (4)
3) Work = Work + Allocation[i]
Finish[i] = true 
go to step (2)
4) If Finish[i] = true for each and every i
then system is in a secure state.

Algorithm for Resource Requests

Let Requesti denote the action of process Pi requesting an array of resources. Process Pi asks for k instances of resource type Rj, specified by Requesti[j] = k. The actions that occur when process Pi requests resources are as follows:

Example


1) Proceed to step 2 if Requesti >= Needi; otherwise, report an error condition because the process has made more claims than it can handle.
2) Proceed to step (3) if Requesti <= Accessible; otherwise, Pi will have to wait since the resources are not available.
3) Change the state in such a way that the system appears to have given Pi the required resources:
Requested - Available = Available
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti

Below is the implementation of Banker's Algorithm

Example


// 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);
}

Output


Following is the SAFE Sequence
 P1 -> P3 -> P4 -> P0 -> P2
........................................................
Process execute din 1.33 seconds
Press any key to continue.

Explanation:

✅ The processes must anticipate the maximum number of resources required as they enter the system, which may be done in a reasonable amount of time.
✅ In contrast to interactive systems, this method maintains a fixed number of processes.
✅ A specific number of resources must be available to distribute in order for this technique to work. The algorithm would not function if a gadget broke and went unexpectedly offline.
✅ The method will incur overhead costs since it must be invoked for each process when there are several processes and resources.

Algorithm for Safety

Algorithm for Resource Requests

Below is the implementation of Banker's Algorithm

Input Required