Round Robin Scheduling — 200ms Quantum Causes 10s Delays

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.

The beauty of Round Robin is its bounded-response guarantee — no process ever waits more than (n-1)×q time units before getting the CPU again. That guarantee makes it predictable in a way priority or SJF never can be. But trade-offs are real: every context switch costs μs-level overhead, and if your quantum is too small you spend more time switching than working.

Round Robin Implementation

A deque as the ready queue is the most natural implementation. Each process runs for min(remaining_burst, quantum) time units, then if unfinished is appended to the tail of the deque. This preserves the circular order. The code below demonstrates with three processes and varying quantum sizes.

Key detail: the ready queue must be a queue that supports O(1) insert/remove from both ends? No, only tail insert and head remove – a simple FIFO queue works. But a deque helps if you want to implement priority boosting or SJF hybrid. For pure Round Robin, a basic queue (collections.deque in Python) is perfect.

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
    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
        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.

Context switch overhead per process per second: (1/q) × overhead_cost. For q=10ms and overhead 50μs, overhead = 0.5% per process. With 100 processes it's 50% overhead — effectively wasting half the CPU on switching.

Context Switching Overhead Analysis

Every time the CPU switches from one process to another, it must save the current process state (registers, program counter, stack pointer, memory map) and load the next process's state. This is a context switch. In a Round Robin system, a context switch happens at the end of every quantum for every process that is preempted.

Formula for overhead percentage: Overhead% = (overhead_per_switch) / quantum × 100

Example: overhead_per_switch = 10μs, quantum = 1ms → overhead = 1% But if quantum = 10μs → overhead = 100% (no useful work done)

In production, context switch rate is a key metric. High rates indicate either too many runnable threads (overcommitting CPU) or too small quantum. For CPU-bound workloads, target less than 20k switches/second per core. For IO-bound interactive workloads, 50k-100k is acceptable if each switch is cheap.

Response Time and Fairness Analysis

Round Robin guarantees that every process gets a chance to run within a bounded time. The maximum wait time for a process to get its first quantum is at most (n-1)×q (if it arrives to an empty queue, it runs immediately). This is the best possible bounded-response guarantee among preemptive schedulers.

Fairness is measured by how equally CPU time is distributed over a long interval. In Round Robin, each process gets exactly 1/n of CPU time over any interval long enough to give each process one quantum. This is proportional fairness – no process starves.

Contrast with SJF: shortest processes get CPU quickly but long processes may starve. FCFS: order based on arrival, no starvation but no response guarantee either.

However, Round Robin fairness can be violated if a process frequently blocks on I/O. Blocked processes don't consume quantum, so they effectively get less CPU. To compensate, OS schedulers like Linux give higher priority to processes that have been sleeping (interactive boost).

Comparing Algorithms

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

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

When q → ∞, RR becomes FCFS (identical avg WT). When q → 0, RR approaches processor sharing (avg WT approaches SJF? Not exactly – overhead dominates).

The table shows that RR with a large quantum gives same waiting time as FCFS. The sweet spot is where quantum is larger than most bursts (80% rule) but small enough to keep response time low.

In practice, real systems use hybrid approaches: RR within priority classes (multilevel feedback queues).

Practical Quantum Selection Guidelines

Choosing the right quantum in production involves measuring your workload's burst distribution and context switch cost. Here's a step-by-step approach:

1. Collect burst data: Use perf or eBPF to measure CPU burst lengths for each process.
2. Plot the CDF: Find the 80th percentile burst length – set quantum to at least that value.
3. Calculate overhead: Measure context switch cost on your hardware (typically 1-10μs). Compute overhead% = (cost / quantum) * 100. Keep under 5%.
4. Validate response time: For interactive processes, ensure (n_max_bursts × (n-1) × quantum) is within acceptable latency.
5. Monitor: Track context switch rate, CPU sys%, and tail latency. Adjust quantum if sys% > 20% or response time exceeds SLO.

Linux provides sched_rr_timeslice_ms (for SCHED_RR) and /proc/sys/kernel/sched_latency_ns (for CFS) to tune. For most production systems, the default CFS settings are optimal. Only override for hard real-time workloads.

Frequently Asked Questions