vault

Round-Robin Scheduling

15 min read

Round-Robin Scheduling

Round-robin scheduling assigns each runnable thread an equal slice of CPU time in circular order, preempting the running thread at the end of its slice and rotating to the next. It is, as Wikipedia puts it, the scheme in which “time slices (also known as time quanta) are assigned to each process in equal portions and in circular order, handling all processes without priority” (Wikipedia, “Round-robin scheduling”). Its mechanism is small enough to fit in twenty lines of kernel code: a circular ready queue, a programmable timer interrupt to mark the end of a slice, and a context switch from the expired thread to the next one in the queue. Its appeal is fairness: every thread gets the same chance to run, no thread waits forever, and the worst-case waiting time is bounded by (n - 1) * q for n runnable threads at quantum q. Its limitations are the converse: it has no notion of “important” or “interactive,” and the choice of quantum is a hard trade between context-switch overhead and responsiveness. Modern general-purpose operating systems have largely moved past pure round-robin (Linux now uses EEVDF as of kernel 6.6, after a 16-year run of CFS), but it remains the default scheduler in microkernels, real-time operating systems, and educational kernels because it is correct, predictable, and trivial to implement.

Mental Model

gantt
  title Round-robin schedule, 5 ready tasks, 10 ms quantum
  dateFormat X
  axisFormat %s ms
  section CPU
  T1 (run)            :active, t1a, 0, 10
  T2 (run)            :active, t2a, 10, 10
  T3 (run)            :active, t3a, 20, 10
  T4 (run)            :active, t4a, 30, 10
  T5 (run)            :active, t5a, 40, 10
  T1 (run)            :active, t1b, 50, 10
  T2 (run)            :active, t2b, 60, 10
  T3 blocks on I/O    :crit, t3b, 70, 5
  T4 (run)            :active, t4b, 75, 10
  T5 (run)            :active, t5b, 85, 10

Five ready tasks T1 through T5 share a CPU under round-robin with a 10 ms time quantum. What it shows: at each quantum boundary the timer interrupt fires, the kernel saves the running task’s context and switches to the next task in the circular ready queue. When T3 blocks on I/O part-way through its second quantum (the red bar at the 70 ms mark), the scheduler simply skips it: the rotation continues with T4, T5, T1, T2 and rejoins T3 only when its I/O completes and it re-enters the ready queue. The insight to take: the algorithm has no state beyond “the queue” and “the timer.” There is no priority, no virtual-runtime accounting, no fairness weighting. The only knob is the quantum length.

How It Actually Works

The mechanism has four moving parts.

  1. The ready queue. A FIFO of all threads that are runnable (not blocked on I/O, not waiting on a semaphore, not waiting on an IPC partner). Adding a thread enqueues to the tail; the scheduler dequeues from the head when it wants to run someone. A circular doubly linked list or a fixed-size circular buffer both work; the canonical Wikipedia formulation describes “a circular queue data structure” (Wikipedia, “Round-robin scheduling”).
  2. The time quantum (also called the “time slice”). A fixed duration measured in units of the system tick. Linux’s real-time SCHED_RR policy uses a per-thread quantum retrievable via sched_rr_get_interval(2) (Linux man-pages, “sched(7)”). The OSTEP textbook notes that “in practice, most modern systems have time quanta ranging from 10 to 100 milliseconds” (Arpaci-Dusseau, OSTEP, ch. 7).
  3. The timer interrupt. A periodic hardware timer (on RISC-V, the CLINT machine timer fires when mtime >= mtimecmp) generates an interrupt at the end of each quantum. The interrupt handler is the scheduler’s entry point.
  4. The context switch. When the timer fires, the handler saves the current thread’s register file and program counter, looks up the next thread in the ready queue, restores its registers and program counter, and resumes execution. The expired thread is enqueued at the tail of the ready queue. If a thread blocks before its quantum ends (calls sleep, waits on a synchronization primitive, blocks in IPC), it is removed from the queue entirely until whatever event it is waiting on re-runs it.

The cooperative variant of round-robin keeps the queue but removes the timer. A thread runs until it explicitly calls yield. The advantage is zero pre-emption cost; the disadvantage is that a buggy or compute-heavy thread can monopolize the CPU. Cooperative round-robin is what early operating systems (classic Mac OS up to System 9, Windows 3.x) used; it persists today in some embedded systems and in user-space coroutine schedulers (Go’s runtime is preemptive round-robin, but most async-await runtimes are cooperative).

The Quantum Trade-off

The single most-discussed parameter in scheduling. Three competing forces shape the choice.

Context-switch overhead wants the quantum large. A context switch costs the time to save and restore the integer register file (32 registers on RISC-V, plus PC and a few CSRs), the floating-point register file if the FPU is used, possibly the SIMD state, plus the indirect cost of cold caches and a flushed TLB after the switch. OSTEP makes the indirect cost concrete: “when programs run, they build up a great deal of state in CPU caches, TLBs, branch predictors, and other on-chip hardware. Switching to another job causes this state to be flushed and new state relevant to the currently-running job to be brought in, which may exact a noticeable performance cost” (OSTEP, ch. 7). The rule of thumb is concrete: if the context switch costs 10 percent of the quantum, then 10 percent of the CPU is lost to switching overhead.

Responsiveness wants the quantum small. Average response time (the time from when a thread becomes runnable to when it actually runs) under round-robin is bounded above by (n - 1) * q for n runnable threads at quantum q. A keyboard event that needs the foreground UI thread to wake up within 50 ms is constrained: at five runnable threads, the quantum must be at most 12.5 ms.

Throughput prefers a moderate quantum. A short quantum maximizes responsiveness but pays the context-switch tax; a long quantum minimizes overhead but turns into FCFS for any thread that does not yield early. The Linux real-time documentation does not even publish an officially recommended default quantum, leaving it as a tunable through /proc/sys/kernel/sched_rr_timeslice_ms (Linux man-pages, “sched(7)”). The OSTEP advice is to amortize: “make the time slice long enough to amortize the cost of switching without making it so long that the system is no longer responsive” (OSTEP, ch. 7).

A worked example. Suppose four CPU-bound threads each need 100 ms to complete, and the context-switch cost is 0.1 ms.

  • At quantum q = 10 ms: each thread completes after roughly 400 ms wall time (it has to wait through three slices of the others before each of its own). Context switches happen at 10 ms intervals, costing 39 * 0.1 = 3.9 ms total overhead across the 400 ms run.
  • At quantum q = 1 ms: each thread still completes after 400 ms wall time, but context switches happen every 1 ms, costing 399 * 0.1 = 39.9 ms of overhead. The system is now using 10 percent of its CPU on context switching alone.
  • At quantum q = 100 ms: the schedule degenerates to FCFS. The first thread completes at 100 ms, the fourth at 400 ms. One context switch’s worth of overhead total, but the average response time is 250 ms instead of 10 ms.

The Wikipedia article on round-robin notes a complementary perspective: “if context-switch time is added in, the average turnaround time increases for a smaller time quantum, since more context switches are required” (Wikipedia, “Round-robin scheduling”).

Comparison with the Other Classic Schedulers

First-Come First-Served (FCFS) runs each thread to completion in arrival order. It has the lowest possible overhead (one context switch per job, at job end) but suffers the “convoy effect”: one long job blocks everyone behind it (Wikipedia, “First-come, first-served”). Round-robin trades the higher overhead of preemption for the elimination of convoys.

Shortest Job First (SJF) minimizes average waiting time by always running the thread with the smallest expected runtime. It is provably optimal for that metric (Wikipedia, “Shortest job next”) but requires knowing each job’s runtime in advance (rarely possible) and starves long-running jobs (a steady stream of short jobs can prevent any long job from ever running). Round-robin gives up the optimal average-wait-time guarantee to get bounded waiting time and no starvation.

Priority scheduling runs the highest-priority runnable thread. It is the natural choice when some threads matter more than others (an interrupt handler, a UI thread, a real-time audio thread) but suffers starvation of low-priority threads if high-priority threads keep arriving. Round-robin treats all threads equally; it cannot express “this thread matters more.”

Multilevel feedback queue (MLFQ) combines priority and round-robin. Threads start at a high priority; each time they exhaust their quantum without yielding, they drop one priority class; periodic boosts return them to the top to prevent starvation. MLFQ approximates “interactive jobs are short, batch jobs are long” without needing oracle knowledge of job lengths (Wikipedia, “Multilevel feedback queue”). Round-robin is what runs within each MLFQ class.

Lottery scheduling gives each thread a number of lottery tickets proportional to its desired CPU share and draws a winner at each scheduling decision (Wikipedia, “Lottery scheduling”). It is probabilistically fair (over long runs each thread gets its share) without the determinism (and the worst-case bounds) of round-robin.

Completely Fair Scheduler (CFS) was Linux’s default from 2.6.23 (October 2007) to 6.5. CFS tracks a per-thread “virtual runtime” (vruntime) and always runs the thread with the lowest vruntime, stored in a per-CPU red-black tree (Wikipedia, “Completely Fair Scheduler”). It is fair in expectation under all priorities, has O(log n) operation cost, and was a clean theoretical model. Round-robin is a special case of CFS in which all threads have equal weight and the quantum is the “sched_min_granularity” parameter.

Earliest Eligible Virtual Deadline First (EEVDF) replaced CFS as Linux’s default scheduler in kernel 6.6 (October 2023). It “employs notions of virtual time, eligible time, virtual requests and virtual deadlines for determining scheduling priority” and was designed to “remove the need for CFS latency nice patches” (Wikipedia, “EEVDF”). EEVDF is a dynamic-priority proportional-share scheduler for soft real-time systems. Round-robin can be seen as a degenerate EEVDF in which everyone has the same eligibility and the same deadline.

The pattern: every general-purpose scheduler since 1990 is more sophisticated than round-robin. None of them are simpler.

Where Round-Robin Still Wins

Microkernels and small kernels. seL4’s default scheduler is “preemptive round-robin scheduling with a small number of priorities,” and the kernel supports “a configurable timeslice length and a configurable scheduling latency” (Heiser, seL4 whitepaper, section 5). The kernel code budget is fixed at roughly 10,000 lines of C; a CFS-class scheduler would not fit. Round-robin among equal-priority threads is what the L4 family has always used, and it is what microkernels still default to when they ship.

Real-time operating systems (RTOS). FreeRTOS runs equal-priority tasks in round-robin: when “configUSE_TIME_SLICING” is enabled (the default), tasks of the same priority share the CPU in equal slices of one tick each, the tick rate being whatever configTICK_RATE_HZ is set to (typically 1000 Hz, giving a 1 ms quantum) (FreeRTOS, “Scheduling Algorithm Overview”). Higher-priority tasks always preempt lower-priority ones, but within a priority class the scheduler is round-robin. The Linux real-time SCHED_RR policy is the same pattern: a real-time priority dominates SCHED_OTHER threads, but within a priority class the threads share the CPU in equal quanta (Linux man-pages, “sched(7)”).

Network packet scheduling. Wikipedia notes that “in best-effort packet switching and other statistical multiplexing, round-robin scheduling can be used as an alternative to first-come first-served queuing” (Wikipedia, “Round-robin scheduling”). A network switch with per-flow queues serves them round-robin to prevent one heavy flow from starving the others. Variants (Deficit Round Robin, Weighted Round Robin) extend the basic algorithm to handle variable packet sizes and per-flow weights, but the core mechanic is the same.

Educational use. Every operating-systems textbook starts the scheduler chapter with round-robin because the algorithm fits on one slide and exposes the time-quantum trade-off cleanly.

Configuration and Code: A Minimal Round-Robin Scheduler

A skeleton in Rust for a small RISC-V kernel:

pub struct ReadyQueue {
    head: Option<TaskId>,
    tail: Option<TaskId>,
}
 
pub struct Task {
    id: TaskId,
    regs: SavedRegisters,
    next: Option<TaskId>,    // for the ready-queue link
    state: TaskState,        // Ready, Running, Blocked(Reason)
}
 
pub fn schedule_tick() {
    let prev = current_task();
    if prev.state == TaskState::Running {
        prev.state = TaskState::Ready;
        ready_queue.push_back(prev.id);
    }
    let next_id = ready_queue.pop_front().unwrap_or(IDLE_TASK);
    let next = tasks.get_mut(next_id);
    next.state = TaskState::Running;
    set_current_task(next_id);
    context_switch(&mut prev.regs, &next.regs);
    // Re-arm CLINT mtimecmp for the next quantum.
    clint::set_mtimecmp(clint::mtime() + QUANTUM_TICKS);
}

Line-by-line: schedule_tick is the timer-interrupt handler. The previously running task (if it was actually running, rather than already blocked or sleeping) goes back to the ready queue. The next task is popped from the head; if the queue is empty, the kernel falls through to a dedicated idle task that simply executes wfi (wait-for-interrupt). The CPU registers of the outgoing task are saved into its Task struct and the registers of the incoming task are restored. Finally the CLINT mtimecmp register is reprogrammed so the next timer interrupt fires QUANTUM_TICKS ticks from now. The entire scheduler fits in maybe 80 lines of Rust including the queue, the task struct, and the context-switch assembly. There is no virtual runtime, no priority logic, no red-black tree, no eligibility calculation. That is the appeal.

Failure Modes and Common Misunderstandings

  • Quantum too small: the system runs but spends a significant fraction of its time context-switching rather than running user code. The visible symptom is a high irq or system CPU percentage in monitoring tools without any single hot path. Diagnose by raising the quantum and watching whether useful throughput improves.
  • Quantum too large: response time of interactive workloads degrades; one CPU-bound thread can stall a UI for a full quantum. The visible symptom is choppy interactive behaviour despite low overall CPU utilization.
  • Mistaking responsiveness for throughput: a small quantum does not make CPU-bound jobs complete sooner. The total wall-clock time to finish n threads of length t is roughly n * t whatever the quantum is; the quantum only affects the spreading of those completions across time.
  • Convoying by I/O: if all n ready threads are CPU-bound, round-robin is fair. If one thread is short-lived and the others are long-lived, the short-lived thread benefits massively: it finishes in close to one quantum, while the long-lived threads wait (n - 1) * q ms between their own slices. This is the opposite failure mode of FCFS’s convoy effect.
  • Priority inversion under pure round-robin: round-robin has no notion of priority, so there is no priority inversion to worry about. The moment priorities are added (as in SCHED_RR or in Round-Robin within MLFQ classes), priority-inversion handling (priority inheritance, priority ceiling protocols) becomes necessary.
  • “Round-robin is fair” is true under a strict reading: every thread gets exactly the same CPU share when there are n ready threads. It is unfair under any other reading: a thread that needs only 1 ms of CPU and a thread that needs 1000 ms are treated identically, and any thread that arrives one tick later than another waits a full round to start.

Alternatives and When to Choose Them

For a microkernel or RTOS aiming for predictable latency and minimal code, plain preemptive round-robin with a few priority classes (so interrupts and the kernel housekeeping thread can preempt user work) is the sweet spot. seL4, FreeRTOS, Zephyr, and most automotive RTOSes converge on this design.

For a general-purpose desktop or server OS, modern CFS or EEVDF (Linux), the Multimedia Class Scheduler Service in Windows, or the priority-decayed MLFQ in macOS dominate. The mechanism overhead is justified by the variety of workloads they have to handle: interactive UI, batch compute, real-time audio, network servers.

For a batch system or scientific cluster, scheduling moves up one level (Slurm, Kubernetes scheduler) and is more concerned with placing jobs on machines than with multiplexing CPU on one machine; the per-machine scheduler is whatever the OS provides, but the choice rarely matters because each job effectively owns its CPUs.

For a packet switch or network device, deficit round-robin (DRR) or weighted fair queueing (WFQ) handle variable packet sizes correctly while preserving round-robin’s no-starvation property.

For the definitely-not-esp32 kernel v1.0, preemptive round-robin with a fixed 10 ms quantum is the explicit design choice. Up to four user tasks, one quantum each, time-sliced by the CLINT machine timer firing every 10 ms. Priority is not added until v2.0; the v1.0 commitment is “correct and obviously correct” over “fast and clever.”

Production Notes

  • Linux SCHED_RR: present since the early 2.x kernels. The default quantum is documented in /proc/sys/kernel/sched_rr_timeslice_ms and is typically 100 ms on contemporary kernels (Linux man-pages, “sched(7)”). It is used for soft real-time work (industrial control, audio processing) where the threads must preempt all SCHED_OTHER work but should still share the CPU fairly among themselves.
  • FreeRTOS: shipping in roughly 13 billion devices according to the project’s own count, round-robin within priority is the scheduler that runs on most of them. Configuration knobs are minimal: configTICK_RATE_HZ for tick frequency, configUSE_TIME_SLICING for whether equal-priority tasks share, configUSE_PREEMPTION for whether the kernel preempts at tick or only at explicit yield (FreeRTOS, “Scheduling Algorithm Overview”).
  • seL4: “preemptive round-robin scheduling with a small number of priorities” plus an explicit mixed-criticality extension that lets the kernel “support both round-robin and priority-based scheduling for separate scheduling domains” (Heiser, seL4 whitepaper, section 5). The kernel uses round-robin not because it could not implement something more sophisticated but because more sophisticated schedulers do not survive the formal verification budget.
  • Liedtke’s L4 (1993 onward): documented round-robin among the simpler primitives, with the assumption that a userspace policy server can be layered on top if richer scheduling is needed. The kernel does not impose policy (Liedtke, “Toward Real Microkernels,” CACM 1996).

See Also

Graph View

Backlinks