Banker's Algorithm - Deadlock Avoidance

Ryanangry07 — Sun, 21 May 2023 07:05:30 +0000

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.

#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).

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

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 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.

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.

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.

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

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:

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.

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

DEV Community: Ryanangry07

Banker's Algorithm - Deadlock Avoidance