rr.cpp

/*
Title: Round Robin CPU Scheduling (with Arrival Time)
Description: Simple implementation of Round Robin scheduling using arrival time and a ready queue.
Time Complexity: O(n * m)
Space Complexity: O(n)
*/

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

struct Process
{
    int pid, at, bt, rt, wt, tat;
};

void printGantt(const vector<int> &gantt, const vector<int> &time)
{
    cout << "\nGantt Chart:\n ";
    for (int pid : gantt)
        cout << "|  P" << pid << "  ";
    cout << "|\n";

    cout << time[0];
    for (int i = 1; i < time.size(); i++)
        cout << "      " << time[i];
    cout << "\n";
}

int main()
{
    int n, quantum;
    cout << "Enter number of processes: ";
    cin >> n;

    vector<Process> p(n);
    for (int i = 0; i < n; i++)
    {
        p[i].pid = i + 1;
        cout << "\nEnter details for Process " << p[i].pid << "\n";
        cout << "Arrival Time: ";
        cin >> p[i].at;
        cout << "Burst Time: ";
        cin >> p[i].bt;
        p[i].rt = p[i].bt;
        p[i].wt = p[i].tat = 0;
    }

    cout << "Enter Time Quantum: ";
    cin >> quantum;

    queue<int> q;
    vector<int> gantt, time(1, 0);
    int completed = 0, t = 0;

    vector<bool> inQ(n, false);

    for (int i = 0; i < n; i++)
    {
        if (p[i].at == 0)
        {
            q.push(i);
            inQ[i] = true;
        }
    }

    while (completed < n)
    {

        // if queue empty → jump to next arrival
        if (q.empty())
        {
            int next = INT_MAX;
            for (int i = 0; i < n; i++)
                if (p[i].rt > 0)
                    next = min(next, p[i].at);

            t = next;
            time.push_back(t);
            gantt.push_back(0); // idle
            for (int i = 0; i < n; i++)
                if (!inQ[i] && p[i].at <= t)
                {
                    q.push(i);
                    inQ[i] = true;
                }
            continue;
        }

        int i = q.front();
        q.pop();

        gantt.push_back(p[i].pid);

        int run = min(quantum, p[i].rt);
        p[i].rt -= run;
        t += run;

        // push arrivals that came during run
        for (int j = 0; j < n; j++)
            if (!inQ[j] && p[j].at <= t)
            {
                q.push(j);
                inQ[j] = true;
            }

        if (p[i].rt > 0)
            q.push(i); // not finished
        else
        {
            completed++;
            p[i].tat = t - p[i].at;
            p[i].wt = p[i].tat - p[i].bt;
        }

        time.push_back(t);
    }

    // Result table
    cout << "\n--- Round Robin Scheduling ---\n";
    cout << "PID\tAT\tBT\tWT\tTAT\n";

    float totalWT = 0, totalTAT = 0;
    for (auto &x : p)
    {
        cout << "P" << x.pid << "\t" << x.at << "\t" << x.bt
             << "\t" << x.wt << "\t" << x.tat << "\n";
        totalWT += x.wt;
        totalTAT += x.tat;
    }

    cout << "Average Waiting Time = " << totalWT / n << "\n";
    cout << "Average Turnaround Time = " << totalTAT / n << "\n";

    printGantt(gantt, time);

    return 0;
}