Banker's Algorithm & Safe State Verification

Explanation

Avoidance checks future worst-case Need, contrasting with detection which checks current Request.

Key points

• Need Matrix Formula: Need[i][j] = Max[i][j] - Allocation[i][j]
• Safety Algorithm: Finds a safe sequence <P1, P2, ... Pn> where each process can finish with Work + Allocation
• Resource-Request Algorithm: Allocates tentatively and checks safety before committing

Example

Code examples

// C++ Banker's Safety Algorithm
bool isSafe(int n, int m, vector<int> avail, vector<vector<int>> maxM, vector<vector<int>> allot) {
    vector<vector<int>> need(n, vector<int>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            need[i][j] = maxM[i][j] - allot[i][j];
    vector<bool> finish(n, false);
    vector<int> work = avail;
    int count = 0;
    while (count < n) {
        bool found = false;
        for (int p = 0; p < n; p++) {
            if (!finish[p]) {
                int j;
                for (j = 0; j < m; j++) if (need[p][j] > work[j]) break;
                if (j == m) {
                    for (int k = 0; k < m; k++) work[k] += allot[p][k];
                    finish[p] = true; found = true; count++;
                }
            }
        }
        if (!found) return false; // Unsafe state
    }
    return true;
}

Exam questions

• Given Allocation, Max, and Available matrices, calculate Need matrix and determine if the system is in a safe state.
• If process P1 makes a request for (1, 0, 2), can the request be granted immediately? Justify using Banker's Algorithm.