==============================================================
  Experiment 12: Banker's Algorithm
  (Safety Algorithm & Deadlock Detection)
==============================================================
  [Back to Index]
--------------------------------------------------------------

THEORY:
  The Banker's Algorithm is a deadlock avoidance algorithm.
  It checks whether granting a resource request will leave
  the system in a safe state.

  Key Matrices:
    Allocation[i][j] - Resources currently allocated to process i
    Max[i][j]        - Maximum resources process i may need
    Need[i][j]       - Max[i][j] - Allocation[i][j]
    Available[j]     - Currently available resources of type j

--------------------------------------------------------------

ALGORITHM STEPS (Safety Algorithm):
  1. Initialize Work = Available
  2. Set Finish[i] = false for all processes
  3. Find a process such that:
       Need[i] <= Work and Finish[i] == false
  4. Allocate resources:
       Work = Work + Allocation[i]
       Finish[i] = true
  5. Repeat until all processes finish or no such process exists

==============================================================
  PART 1: Banker's Safety Algorithm
==============================================================

SOURCE CODE: bankers_safe.c

--------------------------------------------------------------
#include <stdio.h>

int main() {
    int n = 5, m = 3;
    int alloc[5][3] = {
        {0,1,0},
        {2,0,0},
        {3,0,2},
        {2,1,1},
        {0,0,2}
    };

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

    int avail[3] = {3,3,2};
    int need[5][3];
    int finish[5] = {0};
    int safeSeq[5];
    int work[3];

    for (int i = 0; i < m; i++)
        work[i] = avail[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = max[i][j] - alloc[i][j];

    int count = 0;
    while (count < n) {
        int found = 0;
        for (int i = 0; i < n; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < m; j++)
                    if (need[i][j] > work[j])
                        break;

                if (j == m) {
                    for (int k = 0; k < m; k++)
                        work[k] += alloc[i][k];

                    safeSeq[count++] = i;
                    finish[i] = 1;
                    found = 1;
                }
            }
        }
        if (!found) {
            printf("System is in UNSAFE state\n");
            return 0;
        }
    }

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

    return 0;
}
--------------------------------------------------------------

COMPILE: gcc -o bankers_safe bankers_safe.c

==============================================================
  PART 2: Deadlock Detection Using Banker's Algorithm
==============================================================

THEORY:
  Uses the same Safety Algorithm to detect deadlock.
  If any Finish[i] == false after the algorithm completes,
  those processes are deadlocked.

--------------------------------------------------------------

SOURCE CODE: deadlock_detect.c

--------------------------------------------------------------
#include <stdio.h>

int main() {
    int n = 3, m = 2;

    int allocation[3][2] = {
        {1, 0},
        {0, 1},
        {1, 1}
    };

    int max[3][2] = {
        {1, 1},
        {1, 1},
        {2, 2}
    };

    int available[2] = {0, 0};

    int need[3][2];
    int finish[3] = {0};
    int work[2];
    int safeSeq[3];
    int count = 0;

    // Calculate Need matrix
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = max[i][j] - allocation[i][j];

    // Initialize Work = Available
    for (int i = 0; i < m; i++)
        work[i] = available[i];

    // Safety Algorithm
    while (count < n) {
        int found = 0;
        for (int i = 0; i < n; i++) {
            if (!finish[i]) {
                int j;
                for (j = 0; j < m; j++) {
                    if (need[i][j] > work[j])
                        break;
                }

                if (j == m) {
                    for (int k = 0; k < m; k++)
                        work[k] += allocation[i][k];

                    safeSeq[count++] = i;
                    finish[i] = 1;
                    found = 1;
                }
            }
        }
        if (!found)
            break;
    }

    // Deadlock Detection Result
    if (count == n) {
        printf("System is in SAFE state\nSafe sequence: ");
        for (int i = 0; i < n; i++)
            printf("P%d " , safeSeq[i]);
        printf("\n");
    } else {
        printf("System is in DEADLOCK (UNSAFE STATE)\nDeadlocked processes: ");
        for (int i = 0; i < n; i++)
            if (!finish[i])
                printf("P%d ", i);
        printf("\n");
    }

    return 0;
}
--------------------------------------------------------------

COMPILE: gcc -o deadlock_detect deadlock_detect.c

==============================================================
  [Prev: Exp 11]  |  [Next: Exp 13]
==============================================================