Round-Robin Scheduling
Imagine ten students sharing one professor's office hour. Each needs help immediately. Round-Robin (RR) scheduling solves exactly this problem for CPUs. Give every process a fixed slice of time, called a quantum. Then move on to the next one in line. No process waits an unbounded amount of time behind a long-running neighbor. Nobody monopolizes the processor forever. This matters because real systems must feel responsive. Many programs often compete for one CPU. A batch scheduler like First-Come First-Served Scheduling is simple and starvation-free in order. But a single long process can block short interactive ones for seconds or minutes. That delay is intolerable for a text editor or a web browser. Round-Robin was designed precisely to fix this. It is the foundation of time-sharing operating systems. This mechanism makes a modern multitasking OS feel like every program runs simultaneously, even on a single core. The big picture is a tradeoff dial with one knob: the quantum length `q`. Turn it small and the system behaves like idealized processor sharing. This gives excellent response time but pays heavily in context-switch overhead. Turn it large and RR degenerates toward FCFS. This sacrifices fairness and responsiveness for throughput. Understanding this single knob is key. Reasoning about it quantitatively is the entire intellectual content of the algorithm. This article derives the RR algorithm precisely. It gives working pseudocode for a circular-queue implementation. It computes waiting and turnaround times on a worked trace. It proves a fairness bound, and honestly analyzes the overhead-versus-responsiveness tradeoff. It closes by connecting RR to its descendants. These are Priority Scheduling and Multilevel Feedback Queue Scheduling, which fix RR's blindness to process importance.
- Round-Robin runs each ready process for at most one time quantum `q`, then preempts it to the back of a FIFO ready queue.
- It is preemptive, fair by construction, and guarantees no process waits more than `(n-1)·q` time units between CPU bursts, where `n` is the number of ready processes.
- Average waiting time is highly sensitive to `q`: too small wastes CPU on context switches; too large approaches First-Come First-Served Scheduling behavior.
- The classic rule of thumb: choose `q` so that roughly 80% of CPU bursts complete within one quantum.
- RR ignores priority and job length entirely — every process gets identical treatment, which is both its main strength (fairness) and main weakness (no urgency awareness).
- RR is the structural ancestor of Multilevel Feedback Queue Scheduling, which layers priority and adaptive quanta on top of the same circular-queue mechanism.
Round-Robin guarantees fairness and bounded response time by capping every process's CPU turn at a fixed quantum and cycling through a queue — trading some throughput for predictability.
The idea
Round-Robin scheduling assigns the CPU to the process at the head of a ready queue for a fixed time quantum `q` (typically 10–100 milliseconds). If the process's remaining CPU burst is shorter than `q`, it finishes or blocks voluntarily and the CPU is given to the next process immediately. If the burst is longer than `q`, a timer interrupt fires at the end of the quantum, the OS preempts the running process, saves its context, and appends it to the tail of the ready queue. The scheduler then dispatches the new head of the queue. This cycle repeats forever. The defining data structure is a circular FIFO queue of ready Processes (or threads). Unlike FCFS, which runs each process to completion before touching the next, RR interleaves execution: it converts one long queue-traversal into many short ones. The key parameter is `q`. When `q → ∞`, RR is identical to FCFS. When `q → 0`, RR approximates an idealized model called processor sharing, in which every ready process appears to progress simultaneously at rate `1/n` — but real hardware cannot do this for free, because every preemption costs a fixed context-switch overhead `s` (saving/restoring registers, flushing pipelines, updating memory-management state). This overhead is the crux of the entire design tradeoff and is why `q` cannot be driven to zero in practice. RR is a preemptive scheduling discipline, distinguishing it from non-preemptive FCFS and non-preemptive Shortest-Job-First. Preemption is triggered by a hardware timer, not by the process itself, so RR requires no cooperation from user code — a crucial property for protecting the system from misbehaving or infinite-looping programs. RR is evaluated with the same Scheduling Performance Metrics used elsewhere: waiting time (time spent ready but not running), turnaround time (completion time minus arrival time), response time (time from arrival to first CPU access), and CPU utilization. RR's signature strength is bounding response time and worst-case waiting time simultaneously, something FCFS cannot do.
How it works
The mechanism has three moving parts: the ready queue, the timer, and the dispatcher. On every scheduling decision, the OS either (a) admits a newly arrived process to the tail of the queue, (b) re-queues a preempted process to the tail, or (c) dispatches the head of the queue to the CPU and arms a timer for `q` time units. ``` ALGORITHM RoundRobin(processes[], quantum q) // processes[i] = (pid, arrival_time, burst_time) // remaining[pid] tracks CPU time still needed readyQueue = empty FIFO remaining = map(pid -> burst_time) for all processes completion_time = map(pid -> 0) currentTime = 0 notYetArrived = all processes sorted by arrival_time n_finished = 0 // Admit any processes that have arrived by currentTime function admitArrivals(t): while notYetArrived not empty and notYetArrived.peek().arrival_time <= t: readyQueue.enqueue(notYetArrived.pop()) admitArrivals(currentTime) if readyQueue is empty and notYetArrived not empty: currentTime = notYetArrived.peek().arrival_time admitArrivals(currentTime) while n_finished < len(processes): p = readyQueue.dequeue() runTime = min(q, remaining[p.pid]) currentTime = currentTime + runTime remaining[p.pid] -= runTime // New arrivals during this slice join the queue // BEFORE the just-run process is re-queued (standard convention) admitArrivals(currentTime) if remaining[p.pid] == 0: completion_time[p.pid] = currentTime n_finished += 1 else: readyQueue.enqueue(p) // preempted, back to tail if readyQueue is empty and notYetArrived not empty: currentTime = notYetArrived.peek().arrival_time admitArrivals(currentTime) return completion_time ``` Two subtleties determine correctness. First, the arrival-admission order: when a process finishes its quantum at the same instant a new process arrives, the convention (used above) is to enqueue the arrival before re-queueing the just-run process — this is the standard tie-break and affects exact numeric answers but not asymptotic behavior. Second, idle-time handling: if the ready queue empties because all admitted processes are finished and the next arrival is in the future, the clock must jump forward to that arrival — otherwise the algorithm stalls.
Complexity & correctness
Time complexity per scheduling decision. Enqueue and dequeue on a circular FIFO (implemented as a ring buffer or linked list) are both `O(1)`. Simulating the entire schedule for `n` processes with total remaining work `W` and quantum `q` takes `O(W/q)` dispatch steps in the worst case, since each dispatch advances progress by at most `q`. Each step is `O(1)`, so total simulation cost is `O(W/q)` — this is a property of simulating RR, not an inherent cost of running it, since in a real OS the timer interrupt drives dispatch for free in hardware. The per-decision scheduling overhead itself is `O(1)`, which is why RR scales to systems with thousands of runnable threads better than sorting-based disciplines like Shortest-Remaining-Time-First, which need `O(log n)` per decision with a priority queue.
Space complexity is `O(n)`: one queue slot per ready process, plus `O(1)` metadata (remaining burst time) per process.
Correctness — the bounded-wait invariant. The central claim to prove is: > In pure Round-Robin with `n` ready processes and quantum `q` (ignoring new arrivals and context-switch overhead), no ready process waits longer than `(n-1)·q` time units before its next CPU turn. Proof sketch. Fix a process `P` that has just been placed at the tail of the queue (or is waiting for its first turn). Ahead of it in the queue are at most `n-1` other processes. Each one runs for at most `q` time units before either finishing (leaving the queue, which only helps `P`) or being preempted back to the tail behind `P` (since `P` was already enqueued before them in this cycle). Either way, each of the `n-1` processes ahead contributes at most `q` time units before the CPU reaches `P`. Summing gives an upper bound of `(n-1)·q` — establishing the invariant. This bound is what distinguishes RR from FCFS: FCFS gives no such bound, since one process's burst can be arbitrarily long and every process behind it waits for the entire burst, not a capped slice of it. ∎
Fairness. The same argument shows every ready process is guaranteed to receive at least `q/n` fraction of CPU time on average over any window in which it and `n-1` others remain runnable — this is the discrete analogue of ideal processor sharing.
Honest tradeoffs. RR's `O(1)` fairness guarantee comes at real cost:
- Context-switch tax. If a switch costs `s` time units, then effective useful work per cycle is `q/(q+s)` of the total, so throughput approaches 100% only as `q ≫ s`. If `q ≈ s`, roughly half the CPU is wasted on switching — a serious efficiency failure.
- Average waiting time is not necessarily minimized by RR for any fixed `q`; Shortest-Job-First variants can beat it on mean waiting time, at the cost of starvation risk and unfairness. RR trades optimal average-case waiting time for a bounded worst case and interactive responsiveness.
- Turnaround time can be non-monotonic in `q`: increasing the quantum does not always decrease turnaround time, because it changes the interleaving pattern non-linearly. This is demonstrated in the worked example below.
Worked example
Consider four processes arriving over time, quantum `q = 4`, with zero context-switch overhead assumed for clarity (a following note adds overhead back in).
| Process | Arrival | Burst |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
Trace the Gantt schedule step by step. New arrivals are admitted to the queue before the just-run process is re-queued, per the pseudocode convention.
| Time interval | Running | Ready queue after this slice | Event |
|---|---|---|---|
| 0–4 | P1 (rem 8→4) | P2, P3, P4, P1 | P2 arrived t=1, P3 t=2, P4 t=3; P1 preempted, requeued |
| 4–8 | P2 (rem 4→0) | P3, P4, P1 | P2 finishes at t=8 |
| 8–12 | P3 (rem 9→5) | P4, P1, P3 | P3 preempted, requeued |
| 12–16 | P4 (rem 5→1) | P1, P3, P4 | P4 preempted, requeued |
| 16–20 | P1 (rem 4→0) | P3, P4 | P1 finishes at t=20 |
| 20–24 | P3 (rem 5→1) | P4, P3 | P3 preempted, requeued |
| 24–25 | P4 (rem 1→0) | P3 | P4 finishes at t=25 |
| 25–26 | P3 (rem 1→0) | — | P3 finishes at t=26 |
Now compute the metrics.
| Process | Arrival | Burst | Completion | Turnaround (C−A) | Waiting (TAT−Burst) |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 20 | 20 | 12 |
| P2 | 1 | 4 | 8 | 7 | 3 |
| P3 | 2 | 9 | 26 | 24 | 15 |
| P4 | 3 | 5 | 25 | 22 | 17 |
Average waiting time = (12 + 3 + 15 + 17)/4 = 47/4 = 11.75. Average turnaround time = (20 + 7 + 24 + 22)/4 = 73/4 = 18.25. Compare against FCFS on the same input (run in arrival order P1, P2, P3, P4, no preemption): completions would be P1@8, P2@12, P3@21, P4@26, giving waiting times 0, 7, 10, 18 → average waiting = 8.75. FCFS wins on average waiting time here — expected, since RR pays a fairness tax. But note the worst-case wait bound: with `n = 4` ready and `q = 4`, no process waits more than `(4-1)·4 = 12` units between turns under RR (P1's wait of 12 hits this bound exactly), while under FCFS, P4 could in principle wait for the sum of three arbitrarily long bursts ahead of it — RR's guarantee is structural, FCFS's is not.
Adding context-switch overhead. If each preemption costs `s = 1`, the trace above has 7 preemption/dispatch events, adding 7 units of pure overhead, pushing the last completion from t=26 to roughly t=33 and inflating every waiting time proportionally — illustrating concretely why `q` must be chosen large relative to `s`.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Quantum too small | Context-switch overhead `s` dominates; CPU spends more time switching than computing | Ensure `q ≫ s`; empirically target `q` so ~80% of bursts finish within one quantum |
| Quantum too large | RR degenerates to FCFS-like behavior; response time for short jobs suffers | Cap `q` based on desired response-time bound, not just throughput |
| Wrong tie-break on simultaneous arrival/preemption | Ambiguous ordering changes numeric wait times, hides bugs in simulators | Fix and document a convention (e.g., arrival enqueued before requeue) and apply consistently |
| Forgetting to advance the clock on empty queue | Simulation deadlocks or double-counts idle time when queue drains before next arrival | Explicitly detect empty ready queue and jump `currentTime` to next arrival |
| Treating average waiting time as the only metric | RR can lose to SJF/FCFS on averages while still being the better system choice | Also report response time and worst-case bound — RR's real advantage is there |
| Ignoring I/O-bound vs CPU-bound distinction | Short I/O-bound bursts get needlessly split by an oversized quantum | Combine RR with multilevel queues or feedback (see Multilevel Feedback Queue Scheduling) |
Pioneers & history
Round-Robin's roots lie in the shift from batch processing to time-sharing systems in the 1960s, when researchers needed a way to let many interactive terminal users share one expensive mainframe without any one user noticing the others. The algorithm's simplicity — a queue and a timer — made it the natural default scheduler for early time-sharing kernels and it remains a building block inside virtually every general-purpose OS scheduler today, layered underneath priority and feedback mechanisms.
Origins · 1 minFernando J. Corbató and how this was discovered
Where this matters
Round-Robin is rarely deployed in pure form today, but its mechanism is everywhere. The Linux kernel's older `SCHED_RR` real-time policy is literal textbook Round-Robin among equal-priority real-time tasks. Windows and BSD-derived schedulers use Round-Robin within each priority level of a Multilevel Feedback Queue Scheduling system, so a process descends or ascends priority levels but is always time-sliced Round-Robin-style at its current level. Network routers and switches use Round-Robin (and weighted variants) for fair packet-queue servicing across flows, directly reusing the same bounded-wait argument. Load balancers distribute requests across backend servers in Round-Robin order for the same fairness guarantee. Anywhere a shared, preemptible resource must be divided fairly among many bounded-priority claimants — CPU cores, network links, disk I/O schedulers — the Round-Robin idea of "everyone gets a capped turn, then goes to the back of the line" reappears as the fairness primitive underneath more sophisticated policies.
Ask the tutor: How should I pick the quantum size if I know the distribution of CPU burst lengths in my workload?
Why does Round-Robin usually have worse average waiting time than FCFS or SJF?
RR interleaves execution, so long processes get repeatedly interrupted and requeued, which delays the moment any single process finishes. FCFS and especially SJF minimize average completion order by letting jobs run to completion (SJF specifically favors short jobs first). RR sacrifices this optimization deliberately: it prioritizes bounding the worst-case wait and giving fast response time to every process, including ones that arrived late. The tradeoff is intentional — RR is designed for interactive fairness, not throughput optimality, and in real interactive systems that bounded worst case matters more than shaving a few units off the average.
How should an operating system actually choose the quantum size in practice?
Empirically, kernels pick `q` in the range of roughly 10–100 milliseconds, tuned against typical process behavior. A common heuristic is to target a quantum so that about 80% of CPU bursts complete within a single quantum, based on measured burst-length distributions. This keeps most processes running to natural completion (or voluntary block) without artificial preemption, while still bounding worst-case wait for the minority of long-running processes. Modern kernels don't use a single fixed `q` at all — they adapt quantum size based on priority and recent behavior, which is precisely the idea behind Multilevel Feedback Queue Scheduling.
Does Round-Robin ever starve a process?
No — this is one of its defining guarantees. Because every ready process is guaranteed a turn within `(n-1)·q` time units (ignoring new arrivals extending the queue indefinitely), no process can be starved of CPU time forever, unlike naive priority schedulers where a low-priority process can wait forever behind a stream of higher-priority arrivals. This starvation-freedom is a major reason RR remains attractive even though it is not throughput-optimal — predictability and fairness are sometimes more valuable than raw average performance.
How does Round-Robin interact with I/O-bound versus CPU-bound processes?
An I/O-bound process typically issues a short CPU burst before blocking on I/O, often finishing well within a single quantum. A CPU-bound process usually consumes the entire quantum and gets preempted. Pure RR treats both identically once they're in the ready queue, which can under-serve I/O-bound processes relative to their natural need for quick turnaround (so they can issue their next I/O request promptly and keep devices busy). This limitation motivates extensions like Multilevel Feedback Queue Scheduling, which detects burst patterns and gives I/O-bound processes preferential treatment.
Is Round-Robin still used in modern operating systems, or is it obsolete?
It's far from obsolete — it's foundational. Pure Round-Robin appears directly as a real-time scheduling class (e.g., Linux's `SCHED_RR`) for time-slicing among equal-priority tasks. More broadly, virtually every modern general-purpose scheduler uses Round-Robin as the mechanism for time-slicing processes at the same priority level, wrapped inside a more elaborate policy layer (priorities, feedback, fairness weighting) — see Priority Scheduling and Multilevel Feedback Queue Scheduling. The circular-queue-plus-timer mechanism is a durable building block, not a legacy relic.
What's the relationship between Round-Robin and processor-sharing models used in queueing theory?
As the quantum `q` shrinks toward zero (with zero context-switch overhead, an idealization), Round-Robin's behavior converges to the mathematical model of egalitarian processor sharing (PS), where all `n` present jobs are served simultaneously at rate `1/n` each. This is a standard analytical tool in queueing theory for modeling fair time-sharing systems, and it explains why RR is sometimes called a discretized, overhead-bearing approximation of ideal processor sharing — useful for deriving closed-form performance formulas that approximate real RR behavior for small `q`.
How do new process arrivals mid-quantum affect the algorithm's correctness?
They don't break correctness, but they do affect the exact schedule via a tie-break convention: does a process that arrives exactly when another's quantum ends get queued before or after the just-preempted process? Different textbooks and real kernels choose differently, and this choice changes numeric waiting times but not the algorithm's fundamental guarantees — the bounded-wait invariant and starvation-freedom hold under either convention, since both still place the arrival and the requeued process at defined, finite positions in the same FIFO queue.