Round Robin (OS)

operating-systems scheduling

Definition

Round Robin (RR)

Round Robin (RR) is a preemptive scheduling strategy based on time slicing. The processor allocates fixed-size time intervals, called quanta (or time slices), to processes in cyclic order.

Mechanism

• Selection Function: Same as FCFS (oldest process in the Ready Queue).
• Decision Mode: Preemptive. When a process’s time slice expires (triggered by a clock interrupt), the process is moved to the back of the Ready Queue, and the next process is dispatched.

Performance Considerations

• Quantum Length:
  • If the quantum is very large, RR behaves like FCFS.
  • If the quantum is very small, the overhead of frequent process switching degrades performance.
  • Ideal length: Slightly longer than a typical interactive burst but much longer than the overhead of the interrupt and scheduler.
• I/O Bias: RR disadvantages I/O-intensive processes. These processes typically block before their time slice expires, while CPU-intensive processes use their full quantum. Upon returning from the Blocked state, I/O-bound processes often find themselves “overtaken” by CPU-bound ones.

Virtual Round Robin (VRR)

To address the I/O bias of pure RR, Virtual Round Robin introduces an Auxiliary Queue.

• Logic: Processes that return from an I/O wait are placed in the Auxiliary Queue, which has higher priority than the main Ready Queue.
• Fairness: These processes are allowed to run for the remainder of their unused time slice from before they blocked, ensuring they receive their fair share of the CPU relative to non-blocking tasks.