Assignment3.cpp

/*
Title: CPU Scheduling Algorithms (FCFS, SJF, Priority, Round Robin)
Description: Menu driven simple implementation with Gantt charts.
Time Complexity: Depends on algorithm (O(n²) worst)
Space Complexity: O(n)
*/

#include <iostream>
using namespace std;

struct Process {
    int pid;
    int at;
    int bt;
    int priority;
    int rt;     // Remaining time (RR)
};

// ------------------------------------------------------------
// Utility : Print Gantt Chart
// ------------------------------------------------------------
void printGantt(int gantt[], int times[], int len) {
    cout << "\nGantt Chart:\n ";
    for (int i = 0; i < len; i++) {
        cout << "|  P" << gantt[i] << "  ";
    }
    cout << "|\n";

    cout << times[0];
    for (int i = 1; i <= len; i++) {
        cout << "      " << times[i];
    }
    cout << "\n";
}

// ------------------------------------------------------------
// FCFS
// ------------------------------------------------------------
void FCFS(Process p[], int n) {
    // sort by arrival time
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - i - 1; j++)
            if (p[j].at > p[j + 1].at) {
                Process temp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = temp;
            }

    int wt[20], tat[20], ct[20];
    int gantt[20], times[21];

    ct[0] = p[0].at + p[0].bt;
    tat[0] = ct[0] - p[0].at;
    wt[0] = tat[0] - p[0].bt;

    for (int i = 1; i < n; i++) {
        if (ct[i - 1] < p[i].at)
            ct[i] = p[i].at + p[i].bt;
        else
            ct[i] = ct[i - 1] + p[i].bt;

        tat[i] = ct[i] - p[i].at;
        wt[i] = tat[i] - p[i].bt;
    }

    float totalWT = 0, totalTAT = 0;

    times[0] = p[0].at;
    for (int i = 0; i < n; i++) {
        gantt[i] = p[i].pid;
        times[i + 1] = ct[i];
        totalWT += wt[i];
        totalTAT += tat[i];
    }

    cout << "\n--- FCFS Scheduling ---\n";
    cout << "PID\tAT\tBT\tWT\tTAT\n";
    for (int i = 0; i < n; i++) {
        cout << "P" << p[i].pid << "\t" << p[i].at << "\t" << p[i].bt
             << "\t" << wt[i] << "\t" << tat[i] << "\n";
    }

    cout << "Average WT = " << totalWT / n << "\n";
    cout << "Average TAT = " << totalTAT / n << "\n";

    printGantt(gantt, times, n);
}

// ------------------------------------------------------------
// SJF (non-preemptive)
// ------------------------------------------------------------
void SJF(Process p[], int n) {
    bool done[20];
    int wt[20], tat[20];
    int gantt[20], times[21];
    int completed = 0, t = 0, gi = 0;

    for (int i = 0; i < n; i++) done[i] = false;
    times[0] = 0;

    while (completed < n) {
        int idx = -1, minBT = 99999;

        for (int i = 0; i < n; i++) {
            if (!done[i] && p[i].at <= t && p[i].bt < minBT) {
                minBT = p[i].bt;
                idx = i;
            }
        }

        if (idx == -1) {
            t++;
            continue;
        }

        gantt[gi] = p[idx].pid;
        t += p[idx].bt;
        times[gi + 1] = t;

        tat[idx] = t - p[idx].at;
        wt[idx] = tat[idx] - p[idx].bt;

        done[idx] = true;
        completed++;
        gi++;
    }

    float totalWT = 0, totalTAT = 0;

    cout << "\n--- SJF Scheduling ---\n";
    cout << "PID\tAT\tBT\tWT\tTAT\n";

    for (int i = 0; i < n; i++) {
        cout << "P" << p[i].pid << "\t" << p[i].at << "\t" << p[i].bt
             << "\t" << wt[i] << "\t" << tat[i] << "\n";
        totalWT += wt[i];
        totalTAT += tat[i];
    }

    cout << "Average WT = " << totalWT / n << "\n";
    cout << "Average TAT = " << totalTAT / n << "\n";

    printGantt(gantt, times, completed);
}

// ------------------------------------------------------------
// Priority Scheduling (Non-preemptive)
// ------------------------------------------------------------
void Priority(Process p[], int n) {
    bool done[20];
    int wt[20], tat[20];
    int gantt[20], times[21];
    int completed = 0, t = 0, gi = 0;

    for (int i = 0; i < n; i++) done[i] = false;
    times[0] = 0;

    while (completed < n) {
        int idx = -1, minP = 99999;

        for (int i = 0; i < n; i++) {
            if (!done[i] && p[i].at <= t && p[i].priority < minP) {
                minP = p[i].priority;
                idx = i;
            }
        }

        if (idx == -1) {
            t++;
            continue;
        }

        gantt[gi] = p[idx].pid;
        t += p[idx].bt;
        times[gi + 1] = t;

        tat[idx] = t - p[idx].at;
        wt[idx] = tat[idx] - p[idx].bt;

        done[idx] = true;
        completed++;
        gi++;
    }

    float totalWT = 0, totalTAT = 0;

    cout << "\n--- Priority Scheduling ---\n";
    cout << "PID\tAT\tBT\tPR\tWT\tTAT\n";

    for (int i = 0; i < n; i++) {
        cout << "P" << p[i].pid << "\t" << p[i].at << "\t" << p[i].bt
             << "\t" << p[i].priority << "\t" << wt[i] << "\t" << tat[i] << "\n";
        totalWT += wt[i];
        totalTAT += tat[i];
    }

    cout << "Average WT = " << totalWT / n << "\n";
    cout << "Average TAT = " << totalTAT / n << "\n";

    printGantt(gantt, times, completed);
}

// ------------------------------------------------------------
// Round Robin
// ------------------------------------------------------------
void RoundRobin(Process p[], int n, int quantum) {
    int wt[20], tat[20];
    int gantt[200], times[201];
    int g = 0;

    int t = 0;
    times[0] = 0;

    for (int i = 0; i < n; i++) {
        p[i].rt = p[i].bt;
        wt[i] = tat[i] = 0;
    }

    bool done;

    do {
        done = true;
        for (int i = 0; i < n; i++) {
            if (p[i].rt > 0) {
                done = false;

                gantt[g] = p[i].pid;

                if (p[i].rt > quantum) {
                    t += quantum;
                    p[i].rt -= quantum;
                } else {
                    t += p[i].rt;
                    wt[i] = t - p[i].bt;
                    p[i].rt = 0;
                }
                g++;
                times[g] = t;
            }
        }
    } while (!done);

    for (int i = 0; i < n; i++)
        tat[i] = wt[i] + p[i].bt;

    float totalWT = 0, totalTAT = 0;

    cout << "\n--- Round Robin Scheduling ---\n";
    cout << "PID\tBT\tWT\tTAT\n";

    for (int i = 0; i < n; i++) {
        cout << "P" << p[i].pid << "\t" << p[i].bt << "\t"
             << wt[i] << "\t" << tat[i] << "\n";
        totalWT += wt[i];
        totalTAT += tat[i];
    }

    cout << "Average WT = " << totalWT / n << "\n";
    cout << "Average TAT = " << totalTAT / n << "\n";

    printGantt(gantt, times, g);
}

// ------------------------------------------------------------
// MAIN MENU
// ------------------------------------------------------------
int main() {
    int n;
    cout << "Enter number of processes (max 20): ";
    cin >> n;

    Process p[20], backup[20];

    for (int i = 0; i < n; i++) {
        p[i].pid = i + 1;
        cout << "\nEnter Arrival Time for P" << i + 1 << ": ";
        cin >> p[i].at;
        cout << "Enter Burst Time for P" << i + 1 << ": ";
        cin >> p[i].bt;
        cout << "Enter Priority for P" << i + 1 << ": ";
        cin >> p[i].priority;
        backup[i] = p[i];
    }

    int choice, quantum;

    do {
        cout << "\n\nCPU Scheduling Menu\n";
        cout << "1. FCFS\n";
        cout << "2. SJF\n";
        cout << "3. Priority\n";
        cout << "4. Round Robin\n";
        cout << "5. Exit\n";
        cout << "Enter choice: ";
        cin >> choice;

        // Reset processes before each algo
        for (int i = 0; i < n; i++)
            p[i] = backup[i];

        switch (choice) {
            case 1: FCFS(p, n); break;
            case 2: SJF(p, n); break;
            case 3: Priority(p, n); break;
            case 4:
                cout << "Enter Time Quantum: ";
                cin >> quantum;
                RoundRobin(p, n, quantum);
                break;
            case 5:
                cout << "Exiting...\n";
                break;
            default:
                cout << "Invalid choice!\n";
        }

    } while (choice != 5);

    return 0;
}