Round Robin & Time Quantum
Scenario
If you are sharing a single game console among four friends, the only fair way to play is setting a 10-minute timer for each person's turn.
Mental model
Round Robin is First-Come, First-Served, but with a strict time limit per turn.
Every process gets a small slice of CPU time (a time quantum). If a process isn't finished when its time runs out, it is forcibly paused and sent to the back of the line, ensuring everyone gets a fair share of attention.
Explanation
Round Robin (RR) is the foundational scheduling algorithm for modern time-sharing and interactive operating systems. It is essentially the First-Come, First-Served (FCFS) algorithm upgraded with preemption. The system defines a small unit of time called a time quantum (or time slice), typically ranging from 10 to 100 milliseconds. The ready queue is treated as a circular queue.
The CPU scheduler picks the first process in the queue, sets a hardware timer to interrupt after exactly one time quantum, and dispatches the process. If the process has a CPU burst less than the time quantum, it finishes on its own, releases the CPU, and the scheduler moves to the next process. However, if the process is still running when the timer goes off, the OS forcibly preempts it, saves its state (a context switch), and places it at the tail of the ready queue.
The beauty of Round Robin is absolute fairness and guaranteed responsiveness. If there are 'N' processes in the ready queue and the time quantum is 'Q', then no process will ever wait longer than (N-1) * Q time units before getting its next turn. This makes it impossible for the convoy effect or starvation to occur. Every process is guaranteed to make continuous, incremental progress.
The performance of Round Robin depends entirely on the size of the time quantum. If the quantum is extremely large, RR degrades into standard FCFS scheduling, bringing back the convoy effect. If the quantum is extremely small, the system spends more time performing context switches than actually executing user code. Context switching requires saving registers, updating memory maps, and flushing caches, which is computationally expensive.
Therefore, OS designers must tune the time quantum carefully. A rule of thumb is that the time quantum should be large enough that roughly 80% of CPU bursts finish within a single quantum. This minimizes context switching overhead while still maintaining snappy response times for user interactions.
Key points
- Time Quantum (Slice): The fixed maximum amount of time a process is allowed to run before being preempted.
- Guaranteed Responsiveness: Ensures that every process gets CPU time regularly, preventing starvation and long wait times for small tasks.
- Context Switch Overhead: If the time quantum is too small, the system wastes too much CPU time swapping processes in and out.
- Degradation to FCFS: If the time quantum is infinitely large, Round Robin behaves exactly like First-Come, First-Served.
Common mistakes
- Thinking Round Robin has the best turnaround time: Round Robin is excellent for response time, but its turnaround time is often worse than SJF because it forces all processes to share the CPU, extending the time it takes for any single process to fully complete.
- Assuming a smaller quantum is always better: A smaller quantum improves responsiveness but severely degrades throughput and CPU utilization due to the massive overhead of constant context switching.
Glossary
- Round Robin (RR)
- A fair scheduling method where the operating system gives every running program a tiny, equal turn on the processor before moving to the next one.
- time quantum
- The strict, tiny fraction of a second that a program is allowed to use the CPU before it gets interrupted and forced to wait its turn again.
- circular queue
- A waiting line that wraps around on itself, so when you reach the end of the line, you loop right back to the beginning.
Recall questions
- What happens if a process finishes its task before its time quantum expires?
- What is the consequence of setting the time quantum too small?
- How does Round Robin prevent starvation?
Questions & answers
A system has 4 processes in the ready queue, and a time quantum of 10ms. What is the maximum time a process will wait before getting CPU time?
30 milliseconds.
Approach: The maximum wait is (N-1) * Q. With 4 processes and a 10ms quantum, a process waits for the other 3 processes to each take their 10ms turn (3 * 10 = 30ms).
If your interactive OS is feeling 'sluggish' and unresponsive to keyboard clicks, should you increase or decrease the time quantum?
You should decrease the time quantum.
Approach: A sluggish system means high response time. Decreasing the quantum means the system cycles through processes faster, ensuring the keyboard handler process gets CPU time sooner, making the system feel more responsive.
Continue learning
Previous: Scheduling Criteria