Round Robin RR - CPU Scheduling

 

ROUND ROBIN CPU SCHEDULING

---

1. AIM

To simulate the Round Robin (RR) CPU Scheduling Algorithm using arrival time, burst time and a fixed time quantum, and compute:

• Completion Time (CT)

• Turnaround Time (TAT)

• Waiting Time (WT)

• Average Waiting Time (AWT)

---

2. THEORY

Round Robin Scheduling

• A preemptive CPU scheduling algorithm commonly used in time-sharing systems.

• Each process is assigned a fixed Time Quantum (TQ).

• Processes are executed in circular order.

• If a process's burst time is greater than the time quantum, the CPU is taken away and given to the next process in the ready queue.

Advantages

• Fair scheduling — no starvation.

• Good for time-sharing systems.

Disadvantages

• Large TQ → behaves like FCFS

• Too small TQ → too many context switches

Formulae

1. Turnaround Time (TAT)

   $$TAT=CT-AT$$

2. Waiting Time (WT)

   $$WT=TAT-BT$$

---

3. ALGORITHM

1. Input number of processes n.

2. For each process:

   • Process ID

   • Arrival Time (AT)

   • Burst Time (BT)

3. Input Time Quantum (TQ).

4. Maintain a ready queue.

5. At each time:

   • Add all processes that have arrived.

   • Dequeue the process at the front.

   • Execute for min(BT, TQ) time.

   • If remaining BT > 0, enqueue it again.

   • Else mark the process as completed and compute CT.

6. Compute TAT, WT and Average WT.

7. Print the results.

---

4. C PROGRAM – ROUND ROBIN USING STRUCTURES

#include <stdio.h>

struct Process {
    int pid;
    int at;
    int bt;
    int rt;  // Remaining Time
    int ct;
    int tat;
    int wt;
};

int main() {
    int n, tq, time = 0, completed = 0;

    printf("Enter number of processes: ");
    scanf("%d", &n);

    struct Process p[n];

    for (int i = 0; i < n; i++) {
        p[i].pid = i + 1;
        printf("Enter Arrival Time of P%d: ", i + 1);
        scanf("%d", &p[i].at);
        printf("Enter Burst Time of P%d: ", i + 1);
        scanf("%d", &p[i].bt);
        p[i].rt = p[i].bt;
    }

    printf("Enter Time Quantum: ");
    scanf("%d", &tq);

    int queue[100], front = 0, rear = 0;
    int inQueue[n];
    for (int i = 0; i < n; i++) inQueue[i] = 0;

    // Start by adding all processes that arrive at time 0
    for (int i = 0; i < n; i++) {
        if (p[i].at == 0) {
            queue[rear++] = i;
            inQueue[i] = 1;
        }
    }

    while (completed != n) {
        if (front == rear) {
            time++; // CPU idle
            for (int i = 0; i < n; i++)
                if (p[i].at == time && !inQueue[i]) {
                    queue[rear++] = i;
                    inQueue[i] = 1;
                }
            continue;
        }

        int idx = queue[front++];
        
        // Execute process
        int execTime = (p[idx].rt < tq ? p[idx].rt : tq);
        time += execTime;
        p[idx].rt -= execTime;

        // Add newly arrived processes
        for (int i = 0; i < n; i++)
            if (p[i].at <= time && !inQueue[i]) {
                queue[rear++] = i;
                inQueue[i] = 1;
            }

        if (p[idx].rt > 0) {
            queue[rear++] = idx; // Re-queue
        } else {
            p[idx].ct = time;
            completed++;
        }
    }

    // Calculate TAT and WT
    float totalWT = 0;
    printf("\nRR Scheduling Result:\n");
    printf("PID\tAT\tBT\tCT\tTAT\tWT\n");

    for (int i = 0; i < n; i++) {
        p[i].tat = p[i].ct - p[i].at;
        p[i].wt = p[i].tat - p[i].bt;
        totalWT += p[i].wt;

        printf("P%d\t%d\t%d\t%d\t%d\t%d\n",
               p[i].pid, p[i].at, p[i].bt, p[i].ct,
               p[i].tat, p[i].wt);
    }

    printf("\nAverage Waiting Time = %.2f\n", totalWT / n);

    return 0;
}

---

5. SAMPLE INPUT

Enter number of processes: 4

P1: AT = 0, BT = 5  
P2: AT = 1, BT = 4  
P3: AT = 2, BT = 2  
P4: AT = 3, BT = 1  

Enter Time Quantum: 2

---

6. GANTT CHART

Time Quant → 2 units

0    2    4    6    7    9    11    12
| P1 | P2 | P3 | P1 | P4 | P2 | P1 | P2 |

---

7. SAMPLE OUTPUT

RR Scheduling Result:
PID   AT   BT   CT   TAT   WT
P1    0    5    11   11    6
P2    1    4    12   11    7
P3    2    2    6    4     2
P4    3    1    7    4     3

Average Waiting Time = 4.50

---

8. RESULT

The Round Robin CPU Scheduling algorithm was successfully executed.
The program computed:

• Completion Time

• Turnaround Time

• Waiting Time

• Average Waiting Time

A Gantt chart was drawn to clearly represent process execution order.