Round Robin Scheduling Algorithm

Round Robin is the foundation of time-sharing operating systems. The entire concept of multiple users sharing a single CPU — interactive sessions feeling responsive while background jobs also make progress — rests on preemptive Round Robin scheduling. Your Linux system's scheduler (CFS) is a generalisation of Round Robin with variable quanta based on process priority and recent CPU usage.

The quantum size is the algorithm's central design decision, and getting it wrong has measurable user impact. Windows historically used 15-20ms quanta. Linux's CFS targets roughly 20ms 'scheduling period' divided among ready processes. Too short and context switch overhead dominates. Too long and interactive applications feel sluggish.

Round Robin Implementation

Use a deque as the ready queue. Each process runs for min(remaining, quantum) time units.

from collections import deque

def round_robin(processes: list[dict], quantum: int) -> list[dict]:
    procs = sorted(processes, key=lambda p: p['arrival'])
    remaining = {p['pid']: p['burst'] for p in procs}
    queue = deque()
    results = {}
    time = 0
    i = 0  # index into sorted processes
    # Add processes that arrive at time 0
    while i < len(procs) and procs[i]['arrival'] <= time:
        queue.append(procs[i])
        i += 1
    while queue:
        p = queue.popleft()
        run_time = min(remaining[p['pid']], quantum)
        time += run_time
        remaining[p['pid']] -= run_time
        # Add newly arrived processes
        while i < len(procs) and procs[i]['arrival'] <= time:
            queue.append(procs[i])
            i += 1
        if remaining[p['pid']] == 0:
            ct  = time
            tat = ct - p['arrival']
            wt  = tat - p['burst']
            results[p['pid']] = {'pid':p['pid'],'burst':p['burst'],
                                  'arrival':p['arrival'],'ct':ct,'tat':tat,'wt':wt}
        else:
            queue.append(p)  # back of queue
    return list(results.values())

processes = [
    {'pid':'P1','arrival':0,'burst':24},
    {'pid':'P2','arrival':0,'burst':3},
    {'pid':'P3','arrival':0,'burst':3},
]
for q in [4, 1, 100]:
    results = round_robin(processes, q)
    avg_wt = sum(r['wt'] for r in results) / len(results)
    print(f'Q={q:3}: Avg WT={avg_wt:.2f}')

Choosing the Right Quantum

The quantum size fundamentally affects performance:

Too small (q→0): Approaches processor sharing — perfectly fair but enormous context switching overhead. Each switch costs ~1-100μs in real systems.

Too large (q→∞): Degrades to FCFS — good throughput but poor response time.

Rule of thumb: 80% of CPU bursts should be shorter than q. Typical values: 10-100ms for interactive systems.

Response time guarantee: With n processes and quantum q, worst-case response time ≤ (n-1)×q.

Comparing Algorithms

With the same process set (P1:BT=24, P2:BT=3, P3:BT=3):

| Algorithm | Avg WT | |---|---| | FCFS | 16.00 | | SJF | 3.00 | | Round Robin (q=4) | 8.67 |

SJF has minimum average WT but poor response for long processes. RR balances fairness and response time.

Frequently Asked Questions