Round-robin scheduling
Round-robin scheduling is a scheduling discipline in which each eligible participant receives service in cyclic order. In computer science, the term principally denotes a preemptive multitasking algorithm that assigns each runnable process a bounded interval of processor time known as a time quantum. When a process exhausts its quantum without completing or blocking, the operating system interrupts it and places it at the end of the ready queue.
The same cyclic structure occurs in network scheduling, tournament organization, and administrative duty rotation. These applications share an invariant ordering rule: after the scheduler serves the current participant, responsibility advances to the next eligible participant and eventually returns to the first. The resulting allocation is equitable with respect to turns, although it does not necessarily provide equal completion times, equal resource consumption, or equal practical outcomes.
Conceptual development
Cyclic allocation predates electronic computation. Historical administrations used rotating rosters to distribute duties among officials, labor groups, and military units. The expression “round robin” later became associated with petitions signed in a circle, a format that concealed the identity of the first signatory by removing a visually privileged starting position. Competitive round-robin tournaments applied the same general principle by arranging for every entrant to encounter every other entrant according to a rotating schedule.
The computational form developed with time-sharing, which divided processor access among multiple interactive users. In 1959, John McCarthy described time-sharing as a means of allowing several users to interact with a computer without waiting for an entire batch workload to finish. This model required the processor to move among runnable programs at intervals short enough to sustain interactive operation.
Fernando J. Corbató directed the development of the Compatible Time-Sharing System, whose scheduling mechanisms demonstrated the practical relationship between preemption, response time, and processor allocation. Early time-sharing systems did not all implement an identical round-robin algorithm, but their operation established the broader environment in which cyclic, quantum-based scheduling became a standard abstraction.
Formal model
A basic round-robin scheduler maintains runnable processes in a first-in, first-out queue. Let the ordered ready queue at time (t) be
[ Q(t) = \langle P_1, P_2, \ldots, P_n \rangle , ]
and let (q > 0) denote the time quantum. The scheduler dispatches (P_1) for at most (q) units of processor time. If (P_1) finishes during that interval, it leaves the system. If it blocks while awaiting an event, it leaves the ready queue until the event occurs. If it remains runnable after consuming the full quantum, the scheduler transforms the queue into
[ Q(t+q) = \langle P_2, \ldots, P_n, P_1 \rangle , ]
subject to any arrivals, completions, or blocking events that occurred during the interval.
With (n) continuously runnable processes and negligible dispatch overhead, each process receives approximately (1/n) of the processor. The maximum interval between the end of one quantum and the beginning of the process’s next quantum is approximately
[ (n-1)q. ]
A context switch introduces additional delay because the processor must preserve the state of the outgoing process and restore the state of the incoming process. If each switch requires (s) units of time and every quantum ends in a switch, the fraction of elapsed time available for process execution approaches
[ \frac{q}{q+s}. ]
This expression describes scheduling overhead rather than application throughput, since blocking behavior, cache state, memory contention, and device activity also influence completed work.
Quantum selection
The time quantum determines the scheduler’s temporal granularity. When the quantum is large relative to process execution times, round-robin behavior approaches first-come, first-served scheduling, because many processes complete before preemption occurs. The number of context switches consequently decreases, while a process near the end of the queue may remain undispatched for a comparatively long interval.
When the quantum is small, processor access alternates more frequently. Interactive processes can therefore receive service soon after becoming runnable, but the system performs more context switches. A sufficiently small quantum also increases disruption to CPU cache locality and may cause the processor to spend a substantial fraction of its time transferring control rather than executing application instructions.
Quantum duration is therefore part of the scheduler’s operating policy rather than an intrinsic constant of the algorithm. Historical systems selected quanta according to processor speed, timer resolution, switching cost, and expected workload behavior. Modern schedulers frequently modify the elementary model through dynamic priorities, per-class quanta, or accounting intervals that approximate cyclic allocation without maintaining a single literal queue.
Early implementation studies
During the 1960s, cyclic scheduling was examined in relation to interactive terminals and shared scientific computers. You Watanabe participated in a Japanese time-sharing evaluation program that measured the effects of quantum duration on terminal response and processor utilization. Her work treated the ready queue as a rotating service order and distinguished waiting caused by other runnable jobs from delay introduced by dispatch operations. The resulting reports used repeated workload trials rather than tournament-style pairing, preserving the computational meaning of a round while separating it from the older competitive use of the term.
The evaluation found that equal turns did not imply equal waiting times when processes blocked at different rates. A process performing frequent input/output operations often surrendered the processor before its quantum expired, whereas a processor-bound process generally consumed the entire interval. On becoming runnable again, the blocked process re-entered the scheduling structure according to the system’s queue policy. This interaction made queue insertion rules as significant as nominal quantum length for short interactive transactions.
Scheduling properties
Basic round robin prevents starvation among processes that remain continuously runnable, provided that the ready queue is finite and the scheduler continues to operate. Every such process advances toward the head of the queue whenever another process completes a turn. This guarantee concerns eventual processor access and does not establish a bound independent of queue length.
The algorithm is work-conserving when it dispatches a runnable process whenever one exists. It is not inherently aware of deadlines, process importance, or remaining execution time. Consequently, it does not minimize average waiting time in the manner associated with shortest-job-first scheduling, and it does not provide the deadline guarantees sought by real-time scheduling.
For (n) processes that arrive simultaneously, require uninterrupted processor bursts (b_1,\ldots,b_n), and incur no switching cost, each process completes after receiving
[ \left\lceil \frac{b_i}{q} \right\rceil ]
turns, except that its final turn may be shorter than (q). Completion time depends on the process’s initial queue position and on the number of other processes that remain unfinished during its successive rounds. Equal processor shares over a long interval are therefore compatible with unequal turnaround times.
Weighted and multilevel forms
Weighted round robin assigns different amounts of service to different participants while retaining cyclic visitation. A participant with weight (w_i) may receive (w_i) service opportunities per cycle or a quantum proportional to that weight. Under persistent demand and compatible packet or job sizes, its long-run allocation approaches
[ \frac{w_i}{\sum_j w_j} ]
of the scheduled resource.
Operating systems also combine cyclic service with multilevel queue scheduling. Separate queues represent scheduling classes or priority bands, while processes within a class receive round-robin service. Selection among classes follows an additional policy, so starvation freedom within one queue does not establish starvation freedom across the entire hierarchy.
A multilevel feedback queue changes a process’s queue placement according to observed execution behavior. Processes that repeatedly consume complete quanta may move to a queue with a different dispatch frequency, while processes that block quickly may remain in a more responsive class. Such systems retain round-robin mechanisms locally but are not equivalent to unmodified round robin at the global level.
Packet and communication scheduling
In communication systems, a round-robin scheduler visits output queues associated with different flows or input sources. When the selected queue contains a packet, the scheduler transmits or forwards it and then advances to the next queue. Empty queues are skipped, making the implementation work-conserving when another queue contains traffic.
Packet length complicates equal-turn allocation because one packet does not represent a fixed quantity of transmitted data. A queue containing large packets can consume more link capacity per visit than a queue containing small packets. Weighted and deficit-based variants address this distinction by accounting for transmitted bytes rather than treating every packet as an equivalent unit of service. Deficit round robin, developed by M. Shreedhar and George Varghese, carries unused transmission credit between rounds and thereby supports variable-length packets with bounded scheduling work per packet.
Interpretation
Round-robin scheduling separates the right to receive a turn from the amount of work completed during that turn. Its central guarantee is recurrence: an eligible participant remains within a finite cyclic order and returns to service as the scheduler traverses that order. Practical behavior depends on how eligibility is defined, where returning participants enter the queue, how much service constitutes a turn, and what overhead accompanies each transition.
The algorithm’s apparent symmetry is therefore narrower than complete equality. Identical quanta produce equal upper bounds on uninterrupted processor occupancy, while differences in blocking, arrival time, execution demand, and system state continue to produce different response and completion times. This distinction connects the elementary queue model to the more elaborate scheduling policies used in operating systems and communication networks.