Round Robin Scheduling

Introduction

Think about how you would share a single PlayStation with four friends. You would not let one person play until they finish the entire game. Instead, each person gets a fixed amount of time — say 15 minutes — and then passes the controller to the next person. Everyone gets a fair share, and nobody waits too long for their turn. This is Round Robin scheduling.

Round Robin (RR) is the most widely used CPU scheduling algorithm for time-sharing systems. It is designed for fairness — every process gets an equal share of CPU time. The key idea is a time quantum (also called a time slice): each process runs for at most one quantum before being preempted and moved to the back of the ready queue.

How Round Robin Works

1. Maintain a circular FIFO queue of ready processes
2. Pick the process at the front of the queue
3. Let it execute for one time quantum (or until it finishes, whichever is shorter)
4. If it finishes, remove it from the system
5. If the quantum expires and the process is not done, move it to the back of the queue
6. Pick the next process from the front and repeat

Detailed Example

Consider these processes with a time quantum of 4 ms:

Step-by-Step Execution

Gantt Chart

Calculations

Average Waiting Time = (12 + 3 + 13 + 9) / 4 = 9.25 ms Average Turnaround Time = (22 + 7 + 18 + 12) / 4 = 14.75 ms

The Critical Choice: Time Quantum Size

The time quantum dramatically affects performance:

If Quantum is Too Large

If the quantum is larger than the longest burst time, Round Robin degenerates into FCFS. Processes finish before their quantum expires, so no preemption occurs.

If Quantum is Too Small

If the quantum is very small (say 1 ms), context switching happens too frequently. The CPU spends more time switching between processes than actually executing them. Context switches typically take 1-10 microseconds, so a 1 ms quantum means up to 1% overhead per switch.

The Sweet Spot

A good rule of thumb: the time quantum should be large enough that 80% of CPU bursts complete within a single quantum. In practice, most systems use 10-100 ms.

Implementation in C

Advantages and Disadvantages

Advantages

• Fair — Every process gets equal CPU time, no starvation
• Good response time — Suitable for interactive/time-sharing systems
• Simple to implement — Circular queue with a timer interrupt
• No starvation — Every process gets a turn in every round

Disadvantages

• Context switching overhead — Frequent switches consume CPU time
• Higher average waiting time than SJF for batch workloads
• Quantum selection is tricky — No universally optimal value
• Does not consider priority — Urgent processes wait their turn like everyone else

Real-World Usage

Round Robin is the foundation of scheduling in most modern time-sharing systems. Linux's CFS scheduler is conceptually similar (fair sharing of CPU time), and Windows uses Round Robin within each priority level. Even network routers use Round Robin to fairly distribute bandwidth among competing flows.

Key Takeaways

• Round Robin gives each process a fixed time quantum before preempting it
• It ensures fairness and prevents starvation — ideal for interactive systems
• Time quantum choice is critical: too small wastes time on context switches, too large becomes FCFS
• The rule of thumb is that 80% of CPU bursts should complete within one quantum
• RR typically has higher average waiting time than SJF but much better response time
• Most modern OS use Round Robin as a component within more complex scheduling frameworks