Round-Robin Scheduling: Giving Every Process a Turn

The core idea and its one invariant

Round-robin is first-come-first-served plus preemption. Every runnable process sits in a single FIFO ready queue. The scheduler dequeues the head, runs it for at most one time quantum q (a fixed slice, typically 10–100 ms), and when the quantum expires — signalled by a hardware timer interrupt — it preempts the process, appends it to the tail of the queue, and dequeues the new head. If a process blocks or finishes before its quantum is up, it leaves voluntarily and the next one starts early.

The defining property is the bounded-wait invariant: with n runnable processes, once a process is enqueued it will be scheduled again within at most (n − 1)·q time units, because at most n − 1 others sit ahead of it and each can hold the CPU for no more than q. This is what makes RR starvation-free — no process, however unlucky, waits unboundedly. It is also why RR feels responsive: with n = 10 and q = 50 ms, every task gets the CPU at least every 450 ms, comfortably below the human perception threshold.

• Fairness: over any window each process receives roughly an equal 1/n share of CPU time.
• No priorities in the classic form — every process is equal (weighted RR and MLFQ relax this).
• Order preserved: the FIFO discipline means the queue rotates like a carousel, hence "round robin."

How it works, step by step

The mechanism needs exactly three things: a queue supporting O(1) push/pop, a countdown timer programmed to fire after q, and a context-switch routine. On each timer interrupt or voluntary yield the scheduler runs:

enqueue(P):            # new/ready process
    ready.push_back(P)

schedule():            # called on tick / block / exit
    P = running
    if P.state == RUNNING:      # quantum expired
        P.state = READY
        ready.push_back(P)      # to the TAIL
    elif P.blocked_or_done:
        pass                    # not re-enqueued here
    if ready.empty(): idle()
    Q = ready.pop_front()       # next victim
    Q.state = RUNNING
    timer.arm(q)                # reset the clock
    context_switch(P, Q)

• Data structure: a doubly-linked list or a ring buffer — both give O(1) at both ends. A plain array-backed queue with head/tail indices also works.
• Timer: the OS programs a per-CPU timer (e.g. the local APIC timer or a high-resolution hrtimer on Linux) so the interrupt arrives after exactly q.
• Tail re-insertion is the crucial detail: a preempted process goes to the back, not the front, so everyone cycles before it runs again — that is what enforces the invariant.
• Early exit: if q remaining > 0 when the process blocks on I/O, the residual time is not credited; the next process starts with a full fresh quantum.

Complexity analysis

Per-decision cost is O(1). A scheduling event does one pop_front, at most one push_back, and one timer re-arm — all constant time regardless of how many processes are runnable. This is RR's headline advantage over cost-minimizing schedulers like SRTF (shortest-remaining-time-first), which must find the minimum-remaining job and therefore pay O(log n) per operation with a binary heap, or O(n) with a scan.

Space is O(n) — one queue node per runnable process, plus each process's control block. There is no auxiliary tree or heap.

Throughput of scheduling itself depends on the quantum. Let the fixed context-switch cost be c. A process needing total CPU time T is interrupted ⌈T/q⌉ times, so scheduling overhead per process is ⌈T/q⌉·c and the overhead fraction is ≈ c/(q + c). Two regimes fall out:

• q → ∞: RR degenerates into FCFS — one process runs to completion, no fairness, overhead → 0.
• q → c: the CPU spends ~50% of its time context-switching — a livelock-adjacent pathology where useful work collapses.

The standard rule of thumb: pick q so that ~80% of CPU bursts finish within one quantum, keeping c/(q+c) at a few percent. For turnaround time, RR is deliberately not optimal — SJF minimizes average turnaround (a classic exchange-argument result), while RR trades a higher average turnaround for far lower response time and bounded latency, which is the right trade for interactive workloads.

The trade-offs and when to reach for it

RR optimizes response time and fairness, not average completion time. Concretely:

• Response time — time from ready to first run — is excellent and bounded by (n−1)·q. This is why time-sharing systems and shells use it: you want the cursor to blink, not the batch job to finish 3% sooner.
• Turnaround and waiting time are worse than SJF because short jobs get chopped up and interleaved with long ones. RR can turn a 10 ms job that arrived behind three 100 ms jobs into a job that finishes far later than SJF would allow.
• No convoy effect unlike FCFS: a single CPU-hog can't block everyone behind it, because preemption caps its hold to q.

Reach for RR when: burst lengths are unknown or highly variable, fairness is a requirement, interactivity matters, and you cannot afford the O(log n) bookkeeping of a priority queue. Avoid RR when: you have hard deadlines (use priority/EDF), when average turnaround is the metric (use SJF/SRTF), or when jobs have wildly different importance (use weighted fair queuing or MLFQ). Modern general-purpose kernels actually moved past plain RR for normal tasks — Linux's default class is now CFS/EEVDF, which weights by nice value and tracks virtual runtime — precisely because equal 1/n shares are too blunt for mixed desktop workloads.

Where round-robin actually runs

RR is everywhere the moment you need equal turns cheaply:

• Linux real-time class: the SCHED_RR policy (POSIX 1003.1b) is genuine round-robin among threads of equal real-time priority, with a tunable quantum exposed at /proc/sys/kernel/sched_rr_timeslice_ms (default 100 ms). Higher-priority RT threads always preempt it; ties rotate.
• The old O(1) scheduler: Linux 2.6's pre-CFS scheduler ran RR-style rotation within 140 priority levels using two "active" and "expired" runqueue arrays and a bitmap to find the highest non-empty level in O(1).
• Load balancing: Nginx, HAProxy, AWS ELB, and DNS round-robin distribute incoming requests to backends in strict rotation — the same carousel idea applied to servers instead of CPU bursts. Weighted round-robin gives beefier servers more turns.
• Network schedulers: deficit round-robin (DRR) and weighted fair queuing generalize RR to packets of unequal size, tracking a per-flow deficit counter so a flow of large packets doesn't cheat.
• Embedded/RTOS: FreeRTOS and many microkernels use RR among equal-priority tasks as the default time-slicing policy.

Pitfalls, edge cases, and variants

The classic mistakes:

• Quantum too small: context-switch overhead dominates. Each switch flushes pipeline state, pollutes L1/L2 caches, and may invalidate the TLB — the true cost of a switch is far more than the register save/restore, often thousands of cycles of cache re-warming. This is why q of a few microseconds is a bug, not a feature.
• Quantum too large: RR silently becomes FCFS and interactivity dies.
• New-arrival placement: where does a process that just unblocked go — head or tail? Different implementations differ, and it subtly changes fairness; put it at the tail to preserve the invariant.
• Timer accounting drift: if you don't reset the quantum when a process yields early, a process that repeatedly blocks just under q can starve others of full slices. Charge actual CPU time, not wall-clock.

Key variants:

• Weighted RR (WRR): process i gets wᵢ consecutive quanta or wᵢ turns per cycle — the basis of fair-share scheduling.
• Deficit RR: O(1) fair queuing for variable-size units (packets), using a per-queue deficit counter.
• Multilevel feedback queue (MLFQ): stacks multiple RR queues at different priorities with increasing quanta, demoting CPU-bound jobs and promoting I/O-bound ones — approximating SJF without knowing burst lengths in advance.
• Virtual-time schedulers (CFS/EEVDF): replace fixed quanta with a red-black tree keyed on accumulated virtual runtime, achieving proportional fairness in O(log n) — RR's conceptual successor for general-purpose CPUs.

Round-robin vs. common CPU scheduling policies

Policy	Preemptive	Pick-next cost	Starvation	Best for
Round-Robin	Yes (quantum)	O(1)	No	Fair time-sharing, interactivity
FCFS / FIFO	No	O(1)	No (but convoy)	Batch, low overhead
SJF / SRTF	SRTF: yes	O(log n) heap	Yes (long jobs)	Min avg turnaround
Priority (static)	Optional	O(log n)	Yes (low prio)	Real-time deadlines
MLFQ	Yes	O(1) per level	Mitigated by aging	Mixed unknown workloads