Assignment4.cpp

/*
Title: Banker's Algorithm (Deadlock Avoidance)
Class: SY-A
Roll No.: 41
Description: Implements the Banker's algorithm to determine if the system is in a safe state.
Time Complexity: O(n^2 * m)
Space Complexity: O(n * m)
*/

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cout << "Enter the number of processes: ";
    cin >> n;
    cout << "Enter the number of resource types: ";
    cin >> m;

    vector<vector<int>> alloc(n, vector<int>(m)); // Allocation matrix
    vector<vector<int>> maxm(n, vector<int>(m));  // Maximum matrix
    vector<vector<int>> need(n, vector<int>(m));  // Need matrix
    vector<int> avail(m);                         // Available resources
    vector<int> finish(n, 0);                     // Finished processes
    vector<int> safeSeq(n);                       // Safe sequence

    // Input Allocation matrix
    cout << "\nEnter Allocation Matrix (" << n << " x " << m << "):\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> alloc[i][j];
        }
    }

    // Input Maximum Requirement matrix
    cout << "\nEnter Maximum Requirement Matrix (" << n << " x " << m << "):\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> maxm[i][j];
        }
    }

    // Input Available Resources
    cout << "\nEnter Available Resources (" << m << "):\n";
    for (int i = 0; i < m; i++) {
        cin >> avail[i];
    }

    // Calculate Need matrix = Max - Alloc
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            need[i][j] = maxm[i][j] - alloc[i][j];
        }
    }

    int count = 0;
    while (count < n) {
        bool found = false;

        for (int i = 0; i < n; i++) {
            if (finish[i] == 0) { // If process not finished
                int j;
                for (j = 0; j < m; j++) {
                    if (need[i][j] > avail[j]) {
                        break;
                    }
                }

                if (j == m) { // All resources available for this process
                    for (int k = 0; k < m; k++) {
                        avail[k] += alloc[i][k]; // Release resources
                    }
                    safeSeq[count++] = i;
                    finish[i] = 1;
                    found = true;
                }
            }
        }
        
        if (!found) {
            cout << "\nSystem is in UNSAFE state.\n";
            return 0;
        }
    }

    // Print safe sequence
    cout << "\nSystem is in SAFE state.\nSafe sequence is: ";
    for (int i = 0; i < n; i++) {
        cout << "P" << safeSeq[i] << " ";
    }
    cout << "\n";

    return 0;
}