Round-Robin Scheduling Algorithm

The Story That Explains Round-Robin

Round-Robin (RR) is the CPU scheduling algorithm designed specifically for time-sharing systems. It is essentially preemptive FCFS with a time limit. Each process gets a fixed slice of CPU time called the time quantum (or time slice). When the quantum expires, the process is preempted and moved to the tail of the ready queue, and the next process is dispatched.

Why Round-Robin Exists — The Timesharing Problem

Before RR, systems used FCFS (First-Come-First-Served). A single long-running job could hog the CPU for hours while everyone else waited. As soon as multiple users had to share one computer interactively, this became unbearable. RR was invented to make every user feel like they had the computer to themselves.

Key Terms & The Time Quantum

The Ready Queue — A Circular FIFO

The ready queue in Round-Robin is a FIFO circular queue. The scheduler picks from the head, and preempted or newly-arrived processes go to the tail. Understanding this ordering is the single most common source of exam mistakes.

Numerical 1 — Basic Round-Robin, Same Arrival

We'll start with the simplest case: all processes arrive at t=0. Time quantum q = 2.

Step-by-Step Queue Evolution (q = 2)

Animated Gantt Chart (q = 2)

Final Metrics Table

Numerical 2 — Different Arrival Times (q = 2)

Now the tricky case that trips up students: processes arrive at different times. We must decide whether new arrivals or preempted processes go into the queue first. Rule: new arrival is enqueued before the preempted process at the same instant.

Animated Gantt Chart with Arrival Markers

Final Table

The Time Quantum — Small vs Large

The single most important design decision in Round-Robin is the value of the time quantum q. Get it wrong and RR degenerates into something worse than what it replaced.

Numerical 3 — Same Workload, Two Different Quanta

Let's see the effect of quantum choice on the same workload. Processes: P1 (AT=0, BT=6), P2 (AT=0, BT=3), P3 (AT=0, BT=1), P4 (AT=0, BT=7).

Context Switch Overhead — The Hidden Cost

Textbook numericals usually ignore context switching. Real systems can't. A context switch requires saving all CPU registers, program counter, memory map pointers, and cache invalidation. On modern hardware this costs roughly 1–10 microseconds per switch.

Turnaround Time vs Quantum — The Rule of 80%

Python Implementation

Complete Round-Robin Simulator

# Round-Robin Scheduling — event-driven simulator
# Convention: new arrival enqueued BEFORE the preempted process at the same instant

from collections import deque

def round_robin(processes, quantum):
    # processes: list of dicts { 'pid', 'at', 'bt' }
    n         = len(processes)
    remaining = {p['pid']: p['bt'] for p in processes}
    completed = {}
    ready     = deque()

    # Sort processes by arrival time
    procs = sorted(processes, key=lambda p: p['at'])
    i     = 0
    t     = procs[0]['at']

    # Enqueue processes that have arrived at time t
    while i < n and procs[i]['at'] <= t:
        ready.append(procs[i])
        i += 1

    while ready:
        curr = ready.popleft()
        run  = min(quantum, remaining[curr['pid']])
        start_t = t
        t += run
        remaining[curr['pid']] -= run

        # CRITICAL ORDERING:
        # First, enqueue all NEW arrivals that came in during (start_t, t]
        while i < n and procs[i]['at'] <= t:
            ready.append(procs[i])
            i += 1

        # Then, if the current process still has work, put it at the tail
        if remaining[curr['pid']] > 0:
            ready.append(curr)
        else:
            completed[curr['pid']] = {
                'ct':  t,
                'tat': t - curr['at'],
                'wt':  (t - curr['at']) - curr['bt'],
            }

        # If queue is empty but processes remain, jump to next arrival
        if not ready and i < n:
            t = procs[i]['at']
            while i < n and procs[i]['at'] <= t:
                ready.append(procs[i])
                i += 1

    return completed


# Example — Numerical 2
procs = [
    {'pid': 'P1', 'at': 0, 'bt': 4},
    {'pid': 'P2', 'at': 1, 'bt': 5},
    {'pid': 'P3', 'at': 2, 'bt': 2},
    {'pid': 'P4', 'at': 4, 'bt': 1},
    {'pid': 'P5', 'at': 6, 'bt': 2},
]

result = round_robin(procs, quantum=2)

print("PID  CT  TAT  WT")
for pid in sorted(result):
    m = result[pid]
    print(f"{pid:3} {m['ct']:3} {m['tat']:4} {m['wt']:3}")

avg_tat = sum(m['tat'] for m in result.values()) / len(result)
avg_wt  = sum(m['wt']  for m in result.values()) / len(result)
print(f"\nAvg TAT = {avg_tat:.2f}, Avg WT = {avg_wt:.2f}")

Round-Robin vs Other Scheduling Algorithms

Advantages & Disadvantages

Real-World Applications

Common Exam Traps & Pitfalls

Golden Rules — Round-Robin Scheduling