Bankers Algorithm In C

The banker's algorithm gets its name from its application in the banking industry for assessing loan approvals. In a scenario where a bank has n customers with individual balances of S each, the process involves deducting the loan amount from the bank's total funds before sanctioning the loan only if the remaining balance exceeds S. This precaution is necessary to ensure that the bank can meet all withdrawal demands from its account holders simultaneously.

In simpler terms, the financial institution would always organize its capital in a manner that ensures it can fulfill the requirements of all its customers. The bank would aim to uphold security consistently.

Implementing the Banker's Algorithm involves the utilization of the specified data structures.

Consider a scenario where there are n processes within the system and m distinct types of resources available.

Available:

✅ It is a 1-d array of size "m" that lists the total amount of resources of each type that are accessible.
✅ There are 'k' instances of the resource type if Available[j] = k. 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.

✅ In the context of resource management, the allocation status is represented by a two-dimensional array with dimensions 'n*m', detailing the quantity of each resource type assigned to every process.
✅ For instance, the allocation for a specific process is denoted by Allocation[i, j] = k, indicating that Process Pi currently possesses 'k' instances of the particular resource type.

Need:

✅ It is a 2-d array of size 'n*m' that shows how much more each process needs in terms of resources.
✅ Need I j] = k denotes that process Pi need 'k' instances of the resource type at this time. Rj
✅ Allocation [i, j] - Maximum [i, j] = Need [i, j]

The resources currently assigned for processing Pi are recognized as Allocation, whereas the additional resources required by process Pi to complete its tasks are identified as Need.

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

Algorithm for Safety

The subsequent explanation outlines the procedure for verifying the safety status of a system:

Example


1) Assume Work and Finish are two vectors, m and n, respectively.
Start with Work = Available.
Finish[i] = false; where i = 1 through n
2) Locate an I such that 
         a) Finish[i] = false 
         b) Needi = Work if such an I is not present visit step (4)
3) Allocation[i] = Work + Work
Finish[i] = actual go-to step (2)
4) The system is in a safe condition if Finish i = true for all i.

Algorithm for Resource Requests

Let the term "Request" denote the action of Process Pi requesting an array of resources. In this context, Process Pi specifically requests k instances of resource type Rj, with this request being represented by Request[j] = k. When Process Pi initiates a resource request, the following events unfold:

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
Requesti = Requesti - Allocationi Needi = Needi - Requesti

Banker's algorithm source code

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:

Output


Following is the SAFE Sequence
 P1 -> P3 -> P4 -> P0 -> P2
.......................................................
Process executed in 2.32 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

Banker's algorithm source code

Input Required