Bankers Algorithm Program in C

The Banker's Algorithm, a key deadlock avoidance and detection tool, strategically allocates resources by simulating their distribution to predetermined maximums. This process includes an 's-state' safety check to decide if resource allocation can proceed without leading to a deadlock condition.

Working on Bankers' algorithm

Let us assume that there are 5 processes, P1, P2, P3, P4, and P5 have resources A, B, and C allocated to each process. Their maximum need is provided and we need to use Banker's algorithm to find the remaining need and get a sequence of processes that is in a safe state. Total resources available are A=10, B=5 and C=7.

Let's see how the algorithm works by finding the available resources and filling in the table below.

Here, Remaining need = (Max need- Allocation)

We have to find the Available resources, Available resources = (Total - Allocation)

For A, Total= [0+2+3+2+0]=7 Available= [10-7]=3 For B, Total= [1+0+0+1+0]=2 Available= [5-2]=3 For C, Total= [0+0+2+1+2]=5 Available= [7-5]=2

For 1st iteration,

Now we have to check which processes can utilize the available resources. Compare the Remaining needs of each process with the available resources.

P1 needs 7, 4, and 3 but available are 3, 3, 2. It can't use the resources. P2 needs 1, 2, and 2, and available are 3, 3, and 2. It can be used. So add P2 as the first process in the sequence < P2 >

and find newly available from P2 and perform the above steps again. new available= allocation of P2+ available (2+3),(0+3),(0+2)=[ 5, 3, 2 ]

2nd iteration

P3 needs 6, 0, 0 but available is 5, 3, 2. So move to P4 P4 needs 2, 1, 1, and available are 5, 3, 2. P4 can use the resources. Add P4 to the sequence < P2, P4 >

Now available using P4= (5+2),(3+1),(2+1)=7, 4, 3

3rd iteration

P5 needs 5, 3, 1, and available are 7,4,3 so P5 can utilize the resources.

Add P5 to the sequence < P2, P4, P5 >

Now available using P5=(0+7),(0+4),(2+3)=(7,4,5)

4th iteration

For P1, available in 7,4,5, and required is 7, 4, 3. Hence P1 can utilize the resources.

Add P1 to the sequence. < P2, P4, P5, P1 >

Now available using P1=(0+7),(1+4),(0+5)=(7,5, 5)

5th iteration

For P3 available is 7, 5, 5, and required is 6, 0, 0. Hence, it can use the resources. Add P3 to the sequence. < P2, P4, P5, P1, P3 >

Hence, the order of processes to occur to avoid deadlock is < P2, P4, P5, P1, P3 >.

Algorithm

We consider n= number of processes and m=number of resource types.

Allocation:

• Specifies the number of resources currently allocated to a process.
• 2-D array of size n*m.
• Allocation[i,j]=k, ie, 'k' instances of a resource Rj is allocated to process Pi.

Max need:

• Specifies the number of resources needed by a process.
• 2-D array of size n*m.
• Maxneed[i,j]=Max[i,j]-Allocation[i,j].

Available:

• Specifies the number of available resources for a process.
• 1-D array of size m.
• Available[j]=k, ie, resource type Rj has k instances.

Remaining need(Max):

• Specifies the maximum demand of each process in a system.
• 2-D array of size n*m.
• Max[i,j]=k, Resource type Rj requests at most k instances of process Pi.

Banker's Algorithm follows two algorithms.

• Safety algorithm - This algorithm checks if a system is in a safe state.
• Resource-Request Algorithm - This algorithm performs actions based on requests.

Safety Algorithm

Resource-Request Algorithm

Bankers Algorithm Program in C

Output:

Time Complexity

Time complexity of Banker's Algorithm is $O(n^3a)$ where, n=number of processes a=number of resources

Space Complexity

The space Complexity of thBanker's Algorithm is $O(n)$.