Write a C program to avoid Deadlock using Banker’s Algorithm.

by
Introduction to Banker’s Algorithm

The Banker’s Algorithm, introduced by Edsger Dijkstra, is a resource allocation and deadlock avoidance algorithm. It is designed to manage the allocation of resources in a system to multiple processes while ensuring that the system remains in a safe state, avoiding deadlock situations.

Key Concepts:
  1. Safe State: A system is in a safe state if there exists a sequence of processes such that each process can obtain its maximum resource request with the currently available resources plus the resources held by all preceding processes in the sequence.
  2. Resource Allocation: The algorithm simulates the allocation of resources by a “banker” (hence the name), who only allocates resources if the system remains in a safe state afterward.
  3. Resource Request: When a process requests resources, the algorithm checks if granting the request keeps the system in a safe state. If it does, the resources are allocated; otherwise, the process must wait.
Steps of the Algorithm:
  1. Check Request Validity: Ensure the requested resources do not exceed the process’s maximum claim.
  2. Check Availability: Ensure the requested resources are available.
  3. Simulate Allocation: Temporarily allocate the requested resources.
  4. Check Safety: Verify if the system remains in a safe state after the allocation.
  5. Grant or Deny Request: If the system is safe, the request is granted; otherwise, it is denied, and the temporary allocation is rolled back.

By following these steps, the Banker’s Algorithm ensures that resources are allocated safely and deadlock is avoided, making it a crucial algorithm for operating systems and resource management.

C program to avoid Deadlock using Banker’s Algorithm

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

#define P 5 // Number of processes
#define R 3 // Number of resources

// Function to check if the system is in a safe state
bool isSafe(int processes[], int avail[], int max[][R], int allot[][R]) {
    int need[P][R];
    for (int i = 0; i < P; i++)
        for (int j = 0; j < R; j++)
            need[i][j] = max[i][j] - allot[i][j];

    bool finish[P] = {0};
    int safeSeq[P];
    int work[R];
    for (int i = 0; i < R; i++)
        work[i] = avail[i];

    int count = 0;
    while (count < P) {
        bool found = false;
        for (int p = 0; p < P; p++) {
            if (!finish[p]) {
                int j;
                for (j = 0; j < R; j++)
                    if (need[p][j] > work[j])
                        break;

                if (j == R) {
                    for (int k = 0; k < R; k++)
                        work[k] += allot[p][k];
                    
                    safeSeq[count++] = p;
                    finish[p] = 1;
                    found = true;
                }
            }
        }

        if (!found) {
            printf("System is not in a safe state\n");
            return false;
        }
    }

    printf("System is in a safe state.\nSafe sequence is: ");
    for (int i = 0; i < P; i++)
        printf("%d ", safeSeq[i]);
    printf("\n");

    return true;
}

// Function to request resources
bool requestResources(int processes[], int avail[], int max[][R], int allot[][R], int pid, int request[]) {
    int need[P][R];
    for (int i = 0; i < P; i++)
        for (int j = 0; j < R; j++)
            need[i][j] = max[i][j] - allot[i][j];

    for (int i = 0; i < R; i++)
        if (request[i] > need[pid][i]) {
            printf("Error: Process has exceeded its maximum claim\n");
            return false;
        }

    for (int i = 0; i < R; i++)
        if (request[i] > avail[i]) {
            printf("Error: Resources are not available\n");
            return false;
        }

    for (int i = 0; i < R; i++) {
        avail[i] -= request[i];
        allot[pid][i] += request[i];
        need[pid][i] -= request[i];
    }

    if (isSafe(processes, avail, max, allot))
        return true;

    for (int i = 0; i < R; i++) {
        avail[i] += request[i];
        allot[pid][i] -= request[i];
        need[pid][i] += request[i];
    }

    printf("Request cannot be granted as it leads to an unsafe state\n");
    return false;
}

int main() {
    int processes[] = {0, 1, 2, 3, 4};

    int avail[] = {3, 3, 2};

    int max[P][R] = {
        {7, 5, 3},
        {3, 2, 2},
        {9, 0, 2},
        {2, 2, 2},
        {4, 3, 3}
    };

    int allot[P][R] = {
        {0, 1, 0},
        {2, 0, 0},
        {3, 0, 2},
        {2, 1, 1},
        {0, 0, 2}
    };

    isSafe(processes, avail, max, allot);

    int request1[] = {1, 0, 2};
    requestResources(processes, avail, max, allot, 1, request1);

    return 0;
}

Output:

Markdown
System is in a safe state.
Safe sequence is: 1 3 4 0 2
Explanation:
  1. isSafe Function: This function checks if the system is in a safe state by trying to find a safe sequence of processes.
  2. requestResources Function: This function handles resource requests from processes. It first checks if the request is valid, then it checks if the request can be granted without leading to an unsafe state. If the request can be safely granted, the function updates the allocation and availability matrices.
  3. main Function: This initializes the system with processes, available resources, maximum resource needs, and the resources currently allocated to each process. It then calls the isSafe function to check the initial state and requestResources to process a resource request.

This program demonstrates the Banker’s Algorithm, ensuring that it avoids deadlock by only granting requests that lead to safe states.

A step-by-step algorithm for the Banker’s Algorithm

1. Initialization

1.1 Define constants P (number of processes) and R (number of resources).

1.2 Define the processes array to hold process IDs.

1.3 Define the avail array to hold the available amount of each resource.

1.4 Define the max matrix to hold the maximum demand of each process for each resource.

1.5 Define the allot matrix to hold the currently allocated resources for each process.

2. Calculate Need Matrix

2.1 For each process iii and resource jjj:

  • Compute need[i][j] as max[i][j] - allot[i][j].
3. Check Safety of the System (isSafe function)

3.1 Initialize finish array to false for all processes, indicating none are finished yet.

3.2 Initialize work array to be a copy of the avail array.

3.3 Initialize safeSeq array to store the safe sequence of processes.

3.4 Repeat while count < P (number of processes):

  • Set found to false.
  • For each process ppp:
    • If finish[p] is false and the process’s need can be met with the available resources:
      • Update work to include the resources allocated to process ppp.
      • Add process ppp to safeSeq.
      • Mark process ppp as finished (finish[p] = true).
      • Set found to true.
  • If no such process is found in an iteration (found remains false), print “System is not in a safe state” and return false.

3.5 If all processes are finished, print “System is in a safe state” and return true.

4. Request Resources (requestResources function)

4.1 Calculate need matrix as in step 2.

4.2 For the requesting process pid:

  • Check if the request exceeds the process’s need. If yes, print an error and return false.
  • Check if the request exceeds the available resources. If yes, print an error and return false.

4.3 Temporarily allocate the requested resources:

  • Update avail, allot, and need arrays.

4.4 Call isSafe function to check if the system is still in a safe state after the allocation:

  • If the system is safe, return true.
  • If the system is not safe, rollback the allocation, print an error, and return false.
5. Main Function

5.1 Initialize the processes, avail, max, and allot arrays.

5.2 Call isSafe to check the initial safety of the system.

5.3 Define a resource request array and call requestResources to process the request.

Pseudocode

Here’s a Pseudocode for Banker’s Algorithm,

Plaintext
Initialize P, R
Initialize processes[], avail[], max[P][R], allot[P][R]

Function isSafe(processes[], avail[], max[P][R], allot[P][R]):
    Calculate need[P][R] = max[P][R] - allot[P][R]
    Initialize finish[] = {false}
    Initialize work[] = avail[]
    Initialize safeSeq[] = {}
    count = 0

    while count < P:
        found = false
        for p in 0 to P-1:
            if not finish[p] and need[p][j] <= work[j] for all j:
                Update work[j] += allot[p][j]
                Add p to safeSeq
                finish[p] = true
                found = true

        if not found:
            Print "System is not in a safe state"
            return false

    Print "System is in a safe state"
    Print "Safe sequence is: safeSeq"
    return true

Function requestResources(processes[], avail[], max[P][R], allot[P][R], pid, request[]):
    Calculate need[P][R] = max[P][R] - allot[P][R]

    for i in 0 to R-1:
        if request[i] > need[pid][i]:
            Print "Error: Process has exceeded its maximum claim"
            return false

    for i in 0 to R-1:
        if request[i] > avail[i]:
            Print "Error: Resources are not available"
            return false

    Temporarily allocate resources:
    for i in 0 to R-1:
        avail[i] -= request[i]
        allot[pid][i] += request[i]
        need[pid][i] -= request[i]

    if isSafe(processes, avail, max, allot):
        return true

    Rollback allocation:
    for i in 0 to R-1:
        avail[i] += request[i]
        allot[pid][i] -= request[i]
        need[pid][i] += request[i]

    Print "Request cannot be granted as it leads to an unsafe state"
    return false

Main:
    Initialize processes[], avail[], max[P][R], allot[P][R]
    Call isSafe(processes, avail, max, allot)
    Define request1[] = {1, 0, 2}
    Call requestResources(processes, avail, max, allot, 1, request1)

This algorithm outlines the steps followed in the C program to implement the Banker’s Algorithm for deadlock avoidance.