// ============================================================
// Banker's Algorithm in C++ — Deadlock Avoidance
// Determines if the current resource allocation is in a safe state
// System: 4 processes (P0–P3), 4 resource types (R0–R3)
// ============================================================

#include <iostream>
using namespace std;

int main() {

    const int PROCESS_COUNT  = 4;   // Number of processes
    const int RESOURCE_COUNT = 4;   // Number of distinct resource types

    // Currently available units of each resource type
    int availableResources[RESOURCE_COUNT] = {3, 1, 1, 2};

    // Resources currently allocated to each process
    // allocatedResources[i][j] = units of resource j held by process i
    int allocatedResources[PROCESS_COUNT][RESOURCE_COUNT] = {
        {1, 2, 2, 1},   // Process 0 currently holds: R0=1, R1=2, R2=2, R3=1
        {1, 1, 3, 3},   // Process 1 currently holds: R0=1, R1=1, R2=3, R3=3
        {1, 1, 1, 0},   // Process 2 currently holds: R0=1, R1=1, R2=1, R3=0
        {3, 2, 1, 1}    // Process 3 currently holds: R0=3, R1=2, R2=1, R3=1
    };

    // Maximum resources each process may ever need
    // maximumResources[i][j] = max units of resource j process i may request
    int maximumResources[PROCESS_COUNT][RESOURCE_COUNT] = {
        {3, 3, 2, 2},   // Process 0 may need at most: R0=3, R1=3, R2=2, R3=2
        {1, 7, 3, 4},   // Process 1 may need at most: R0=1, R1=7, R2=3, R3=4
        {1, 1, 5, 0},   // Process 2 may need at most: R0=1, R1=1, R2=5, R3=0
        {2, 2, 3, 3}    // Process 3 may need at most: R0=2, R1=2, R2=3, R3=3
    };

    // -------------------------------------------------------
    // Step 1: Compute Need matrix = Maximum - Allocated
    // -------------------------------------------------------
    int needMatrix[PROCESS_COUNT][RESOURCE_COUNT];
    for (int proc = 0; proc < PROCESS_COUNT; proc++) {
        for (int res = 0; res < RESOURCE_COUNT; res++) {
            needMatrix[proc][res] =
                maximumResources[proc][res] - allocatedResources[proc][res];
        }
    }

    // -------------------------------------------------------
    // Step 2: Display the system state
    // -------------------------------------------------------
    cout << "\n Allocated Resources:";
    for (int proc = 0; proc < PROCESS_COUNT; proc++) {
        cout << "\n  P" << proc << ": ";
        for (int res = 0; res < RESOURCE_COUNT; res++)
            cout << allocatedResources[proc][res] << " ";
    }
    cout << "\n\n Maximum Resources:";
    for (int proc = 0; proc < PROCESS_COUNT; proc++) {
        cout << "\n  P" << proc << ": ";
        for (int res = 0; res < RESOURCE_COUNT; res++)
            cout << maximumResources[proc][res] << " ";
    }
    cout << "\n\n Need Matrix (Maximum - Allocated):";
    for (int proc = 0; proc < PROCESS_COUNT; proc++) {
        cout << "\n  P" << proc << ": ";
        for (int res = 0; res < RESOURCE_COUNT; res++)
            cout << needMatrix[proc][res] << " ";
    }
    cout << "\n\n Available Resources: ";
    for (int res = 0; res < RESOURCE_COUNT; res++)
        cout << availableResources[res] << " ";

    // -------------------------------------------------------
    // Step 3: Safety Algorithm
    // workPool[] simulates the available pool as processes finish.
    // finished[] tracks which processes have completed.
    // -------------------------------------------------------
    int  workPool[RESOURCE_COUNT];                       // Simulated available pool
    bool finished[PROCESS_COUNT] = {false};              // All processes unfinished initially
    int  safeSequence[PROCESS_COUNT];                    // Stores the safe execution order
    int  scheduledCount = 0;                             // Number of processes scheduled so far

    // Initialize work pool with current available resources
    for (int res = 0; res < RESOURCE_COUNT; res++)
        workPool[res] = availableResources[res];

    bool progressMade;
    do {
        progressMade = false;
        for (int proc = 0; proc < PROCESS_COUNT; proc++) {
            if (!finished[proc]) {
                // Check if ALL resource needs of this process can be satisfied
                bool canFinish = true;
                for (int res = 0; res < RESOURCE_COUNT; res++) {
                    if (needMatrix[proc][res] > workPool[res]) {
                        canFinish = false;   // Not enough of resource 'res' available
                        break;
                    }
                }
                if (canFinish) {
                    // Process can complete — add its allocation back to the work pool
                    for (int res = 0; res < RESOURCE_COUNT; res++)
                        workPool[res] += allocatedResources[proc][res];

                    safeSequence[scheduledCount++] = proc;  // Add to safe sequence
                    finished[proc] = true;                   // Mark as done
                    progressMade = true;                     // At least one process progressed
                }
            }
        }
    } while (progressMade);  // Keep scanning until no more progress is possible

    // -------------------------------------------------------
    // Step 4: Determine if system is safe or unsafe
    // -------------------------------------------------------
    if (scheduledCount == PROCESS_COUNT) {
        cout << "\n\n System is in a SAFE STATE.";
        cout << "\n Safe Sequence: ";
        for (int i = 0; i < PROCESS_COUNT; i++) {
            cout << "P" << safeSequence[i];
            if (i < PROCESS_COUNT - 1) cout << " -> ";
        }
    } else {
        cout << "\n\n System is in an UNSAFE STATE — Deadlock may occur!";
        cout << "\n Processes that could NOT be scheduled: ";
        for (int proc = 0; proc < PROCESS_COUNT; proc++)
            if (!finished[proc]) cout << "P" << proc << " ";
    }

    cout << endl;
    return 0;
}