Banker's Algorithm - Deadlock Avoidance
Tags: c, algorithms
Published: 2023-05-21 07:05:30

**Banker's algorithm is one of the most representative algorithms to avoid deadlock. However, the system calculates the security of resource allocation before allocating resources. If the allocation does not cause the system to enter an insecure state, the system will allocate resources. Otherwise, the system will wait. In order to implement banker algorithm, the system must set up several data structures.**

_In this article, I will introduce Banker's Algorithm and show the implementation code in C language step by step._


**Banker's Algorithm**

 
To explain the Banker's algorithm, let me first explain the operating system's secure and insecure states.

- 
**Safe State**
If there is a security sequence P1 consisting of all processes in the system... , Pn, the system is in the secure state. The security state must be that no deadlock occurs

- 
**Unsafe State**
There is no security sequence. An unsafe state does not necessarily lead to a deadlock.

Now, we can initialize some sample data as the input parameters of isSafe function. Later I will show you the code of isSafe function which implement the banker's algorithm.

``` C
#include <stdio.h>
#include <stdbool.h>

#define MAX_PROCESSES 4
#define MAX_RESOURCES 3

int main() {
    // allocated resources for each process
    int allocation[MAX_PROCESSES][MAX_RESOURCES] = {
        {1, 2, 2},
        {1, 0, 3},
        {1, 2, 1},
        {0, 2, 1}
    };
    // max demanded resources of each process
    int max_demand[MAX_PROCESSES][MAX_RESOURCES] = {
        {3, 3, 2},
        {1, 2, 3},
        {1, 3, 1},
        {0, 0, 1}
    };
    // current available resources
    int available[MAX_RESOURCES] = {1, 1, 2};

    int num_processes = MAX_PROCESSES;
    int num_resources = MAX_RESOURCES;

    // Check if the system is in a safe state
    if (isSafe(available, max_demand, allocation, num_processes, num_resources)) {
        printf("\nSystem is in a safe state.\n");
    } else {
        printf("\nSystem is in an unsafe state. Deadlock detected!\n");
    }

    return 0;
}
```

**Explanation of the code:**

The isSafe function checks if the system is in a safe state by implementing the Banker's safety algorithm. It takes the following parameters:

- 
`available[]`: An array representing the number of currently available instances of each resource.

- 
`max_demand[][]`: A 2D array representing the maximum demand of each process for each resource. Row represents process and column represents resources.

- 
`allocation[][]`: A 2D array representing the currently allocated resources to each process. Row represents process and column represents resources.

- 
`num_processes`: The number of processes.

- 
`num_resources`: The number of resources.

I draw a table diagram for your better understanding of those parameters. In the matrix, row is processes(P0, P1, P2, P3) and column is resources(R0,R1,R2).

![The image shows sample data of allocation matrix, max_demand matrix and available array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4z681erd44qvywj3mh6n.png)

Let's move on to our core part, isSafe function

``` C
bool isSafe(int available[], int max_demand[][MAX_RESOURCES], int allocation[][MAX_RESOURCES], int num_processes, int num_resources) {
    
    // max_demand resources - allocated resources = need resources
    int need[MAX_PROCESSES][MAX_RESOURCES];
    // set all process as 'not finished' state
    bool finish[MAX_PROCESSES] = { false };
    // current availiable resources
    int work[MAX_RESOURCES];
    // possible safe execution sequence that can avoid deadlock
    int safe_sequence[MAX_PROCESSES];
    // index to traverse the list
    int i, j, k;

    // Initialize the need matrix
    for (i = 0; i < num_processes; i++) {
        for (j = 0; j < num_resources; j++) {
            need[i][j] = max_demand[i][j] - allocation[i][j];
        }
    }
    // Initialize the work array
    for (i = 0; i < num_resources; i++) {
        work[i] = available[i];
    }

    // Perform the Banker's safety algorithm
    int count_finish = 0;  // count of finished processes
    // traverse the whole process list if count < number of processes
    // until all processes are finished or no process can be executed
    while (count_finish < num_processes) {
        bool found = false;
        for (i = 0; i < num_processes; i++) {
            if (!finish[i]) {
                // check current process can be executed or not
                bool runnable = true;
                for (j = 0; j < num_resources; j++) {
                    if (need[i][j] > work[j]) { // resources are insufficient
                        runnable = false;   // cannot be executed
                        break;
                    }
                }
                if (runnable) { // if current process can be executed
                    for (k = 0; k < num_resources; k++) {
                        work[k] += allocation[i][k]; // release resources
                    }
                    finish[i] = true; // finish current process
                    found = true;
                    safe_sequence[count_finish] = i;
                    count_finish++;
                }
            }
        }
        if (!found) {
            break;  // No process found that can be executed
        }
    }

    // Check if all processes are finished
    if (count_finish == num_processes){
        printf("\nSafe sequence found:\n");
        for (i = 0; i < num_processes; i++) {
            printf("%d ", safe_sequence[i]);
        }
        printf("\n");
        return true;
    }
    return false;
}
```
Inside this isSafe function, the `need[][]` matrix is initialized by calculating the difference between the `max_demand[][]` and the current `allocation[][]` (both are input parameters of the isSafe function. I also draw the data table in the previous image) for each process and resource. 


![The image shows the calculated need array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h5k0gfvo94x5uky54ggj.png)

The `finish[]` array is used to keep track of which processes have finished executing. It is initialized with all elements set to false. The `work[]` array represents the currently available resources. It is initialized with the `available[]` array. The `work[]` array will be added on once processes are released. The `safe_sequence[]` array is to record the possible safe execution sequence that can avoid deadlock, and it will be printed at the end of the function if the system is in the safe state.

The Banker's safety algorithm is performed using a while loop. It continues until all processes have been marked as finished `count == num_processes` or no process can be executed `if(!found)`. In each iteration of the while loop, the algorithm checks for a process that is not finished and can be executed. If such a process is found, it checks if the resources needed by the process are available `need[i][j] <= work[j]` for all resources. If a process is found that can be executed, the algorithm updates the `work[]` array by adding the allocated resources in `allocation[][]` matrix of that process.

- In the first while loop, we found that p0 cannot be executed because current available resource in `work[]` array for `R0` is insufficient.
![The image shows that P0 cannot be executed because resource R0 is insufficient](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e6layim39jua6f1257dv.png)

p1 also cannot be executed because resource `R1` is insufficient. But p2 seems can be executed because all the resource is sufficient. Therefore, the process is marked as finished `finish[i] = true` and the count is incremented `count++`.  I mark p2 as finished by using the red color in the image.

![The image shows that P2 cannot be executed because all the resources R0,R1,R2 are sufficient](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/aj91uimo20ptkzk8kwqp.png)

Then we need to update the `work[]` array by adding on the `allocation[][]` resources of process `P2`, because now we assume process `P2` has been finished, and we have to release the resources which was hold by `P2`.

![The image shows that, after releasing the process P2, we need to update the work array by adding on the allocated resources of P2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n6p7arloqo5grldi5dl1.png)

Process `P3` is the same logic, it can be execute because current available resources in updated `work[]` are enough.

![The image shows that process P3 can be executed as well because the same logic](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1gogyontgkkommylut1v.png)

Now we have finished the first while loop, and already executed and released the process `P2` and `P3`. So the value of `found` is true, which means program will skip the `break;` statement, and move on to check next while loop condition. Then we check if all processes have been marked as finished `count == num_processes`. 

- 
The result is no, so we continue to the second while loop.
In the second while loop, we found that `P1` and `P2` all can be executed:


![The image shows that process P1 and P2 can be executed, because current work array has enough resources.](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h3ip5zr9jlvqcomouuyd.png)

Then we check the while loop condition, `count < num_processes` will be false, so that we can exit the while loop. After the loop ends, the algorithm checks if all processes have been marked as finished `count == num_processes`. If this condition is true, it means the system is in a safe state.

In the main function, the sample data for the allocation, maximum demand, and available resources are provided. The isSafe function is called with the sample data to determine if the system is in a safe state. Finally, the program prints the appropriate message based on the result of the isSafe function. Here's the sample output screenshot.


![This image shows the output of sample data, which shows one of the possible safe sequence 2 3 0 1, and system is in the safe state](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/fhn94k9h7kldxziogazm.png)

Thanks for watching, if you like this article and think it is helpful, please click the like button and subscribe my channel.