Round-robin scheduling is a preemptive CPU scheduling algorithm in which runnable tasks take turns using a processor for a limited interval called a time quantum or time slice. If a task remains runnable when its quantum expires, it is interrupted and moved to the back of the ready queue. The scheduler then selects the next task. Widely associated with time-sharing systems, round robin provides a straightforward way to distribute processor access without requiring advance knowledge of how long each task will run.
Basic operation
In the simplest model, an operating system maintains a first-in, first-out queue of ready tasks. These tasks may be processes or independently schedulable threads, depending on the system.
The scheduling cycle follows these rules:
- Select the task at the front of the ready queue.
- Allow it to execute for at most one quantum.
- If it finishes, remove it from scheduling.
- If it blocks—for example, while waiting for input or output—remove it from the ready queue until it becomes runnable again.
- If its quantum expires while it remains runnable, place it at the back of the queue.
- Select the next ready task.
Newly runnable tasks normally join the back of the queue in the basic model. Actual systems may use different insertion rules for newly created tasks, waking tasks, or tasks whose priorities change.
Round robin is preemptive because the operating system can interrupt a running task rather than waiting for it to give up the processor. A timer provides the mechanism for enforcing the quantum. The kernel handles expiration and, when necessary, performs a context switch: saving the current task’s execution state and restoring another task’s state.
A quantum is a maximum allocation, not a requirement to keep a task running. A task may finish, block, or yield before its quantum ends. If no other task is ready, the current task can continue running; expiration need not cause a switch to a different task.
Worked example
Consider three tasks, all arriving at time , in the initial order A, B, C. Their required processor times are 5, 3, and 1 time units respectively. Let the quantum be 2 units, with scheduling and context-switch overhead ignored.
| Time interval | Running task | Outcome |
|---|---|---|
| – | A | 3 units remain |
| – | B | 1 unit remains |
| – | C | Completes |
| – | A | 1 unit remains |
| – | B | Completes |
| – | A | Completes |
Several measures describe the result:
- Response time is the time from arrival until first execution.
- Turnaround time is the time from arrival until completion.
- Waiting time is the total time spent ready but not running.
For this example:
| Task | Response time | Completion time | Waiting time |
|---|---|---|---|
| A | 0 | 9 | 4 |
| B | 2 | 8 | 5 |
| C | 4 | 5 | 4 |
Because every task arrives at time zero, completion times equal turnaround times. Because none blocks, waiting time equals turnaround time minus required processor time.
The example illustrates a central trade-off: every task receives an early opportunity to execute, but short tasks may still wait behind other tasks, and long tasks may require several turns before completion.
Choosing the time quantum
The quantum strongly affects both responsiveness and overhead.
Small quanta
A smaller quantum allows ready tasks to receive service more frequently. This can improve responsiveness for interactive workloads, particularly when many tasks compete for the CPU.
However, frequent preemption can increase:
- Time spent saving and restoring execution state.
- Scheduler execution overhead.
- Disruption to CPU caches and other processor-local state.
For a simplified saturated workload in which every turn consumes a full quantum , and each turn incurs overhead , the fraction of time spent executing useful task instructions is approximately
This expression is illustrative rather than a complete performance model. It does not account for early blocking, variable switching costs, or additional cache-related effects.
Large quanta
A larger quantum reduces the frequency of scheduling events but makes other ready tasks wait longer between turns.
If every task completes its current CPU burst within one quantum, and there are no other reasons for preemption, round robin behaves like first-come, first-served scheduling for those bursts. It loses much of the responsiveness advantage associated with frequent rotation.
There is no universally optimal quantum. Suitable values depend on workload characteristics, processor performance, scheduling overhead, and latency requirements. A quantum should not be confused with a hardware timer period: an operating system can measure and enforce scheduling intervals without making them identical to a single periodic timer tick.
Fairness and performance properties
Equal opportunities for runnable tasks
For a fixed set of continuously runnable tasks on one processor, with equal quanta and negligible overhead, each task receives approximately of processor time over a sufficiently long interval.
This is fairness per schedulable task, not necessarily per user or application. An application with many runnable threads may receive more total processor time than one with a single runnable thread unless the system also applies group-based accounting.
Bounded intervals between turns
Under the same fixed-set assumptions, a task placed at the back of the queue waits at most approximately
before its next turn. Each of the other tasks can run for at most one quantum before it.
This bound excludes switching overhead and assumes that tasks cannot repeatedly enter ahead of the waiting task. It is not a general deadline guarantee for a real operating system, where higher-priority tasks, interrupts, or other kernel activity may delay execution.
Starvation and completion time
In the basic single-queue model, round robin prevents indefinite postponement of a runnable task, provided the queue is finite at each insertion and every task ahead of it eventually relinquishes the processor through quantum expiration or earlier departure.
It does not generally minimize average waiting or turnaround time. When execution lengths are known, policies that favor shorter jobs can produce lower average completion times. Round robin instead emphasizes regular access and avoids needing predictions of task duration.
Equal turn-taking also does not imply equal completion times: tasks with greater computational requirements naturally need more turns.
Historical role
Round robin became important with the development of interactive time-sharing systems. Unlike batch processing, in which long jobs could occupy a machine for extended periods, time sharing sought to support many users with sufficiently prompt responses.
Rotating short execution intervals among runnable tasks offered a simple mechanism for sharing a processor. It also limited how long a CPU-bound task could run uninterrupted while others waited.
As operating systems evolved, many adopted more elaborate policies incorporating priorities, feedback from task behavior, and proportional allocation. Round robin remains useful both as a basic scheduling model and as a component within more complex schedulers.
Variants and practical implementations
Priority-based round robin
A system may maintain separate queues for different priorities and apply round robin only among tasks at the same priority. A higher-priority runnable task can then take precedence over all lower-priority queues.
This preserves cyclic sharing within a priority level but does not prevent starvation across levels. A continuously runnable higher-priority workload can prevent lower-priority tasks from executing.
POSIX defines the SCHED_RR scheduling policy, which combines fixed priorities with round-robin allocation among threads at the same priority. Linux supports this policy. It is distinct from the scheduling policies normally used for ordinary Linux workloads. Under Linux SCHED_RR, a thread preempted by a higher-priority thread retains the unused portion of its quantum when it resumes.
Weighted and adaptive variants
Weighted round robin assigns different service allocations to different participants, for example through different numbers of turns or different quantum lengths. The intended share then reflects assigned weights rather than equal treatment.
Adaptive variants change the quantum according to workload conditions or task characteristics. Their behavior depends on the adaptation rule; they should not be assumed to retain every property of fixed-quantum round robin.
A multilevel feedback queue may use round robin within individual queues while moving tasks between levels according to their behavior. The overall policy is therefore more than simple round robin.
Multiprocessor scheduling
On systems using multiple processors, scheduling may involve a shared ready queue or separate queues for individual processors. Per-processor queues reduce contention but require mechanisms for load balancing.
Processor affinity, cache locality, and non-uniform memory access can make strict global rotation undesirable. Consequently, a multiprocessor scheduler may provide round-robin behavior within a local queue without producing one universal execution order across the machine.
Related uses and limitations
The term round robin also describes cyclic selection outside CPU scheduling, including request distribution among servers and service among communication queues. These uses share the turn-taking principle but do not necessarily involve timed preemption.
For example, assigning one request per server does not guarantee equal computational load if request costs differ. Similarly, in packet switching, sending one packet from each queue does not guarantee equal bandwidth when packet sizes vary.
For CPU scheduling, the principal limitations are:
- No inherent deadline awareness: cyclic access alone cannot establish the timing guarantees needed by a real-time operating system.
- Overhead sensitivity: overly short quanta can consume substantial resources in scheduling and switching.
- Workload-insensitive allocation: equal turns do not account directly for urgency, user importance, or remaining execution time.
- Variable responsiveness under load: waiting between turns grows as the number of runnable tasks increases.
- Limited scope of fairness: processor access does not ensure fair access to memory, storage, locks, or other shared resources.
A runnable task can receive regular turns while another task remains blocked on a mutex or other resource. Round robin therefore addresses allocation of processor execution time, not every source of delay in a concurrent system.