Round Robin (RR) Scheduling
The Round Robin (RR) scheduling algorithm is designed primarily for time-sharing systems. It is very similar to FCFS scheduling, but preemption is added to enable the system to switch between processes.
A small unit of time, called a time quantum or time slice, is defined. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to one time quantum.
Real-Life Example
Imagine you and three friends are sharing a single video game controller. You agree that each person gets exactly 10 minutes to play (the time quantum). Once your 10 minutes are up, you must pause the game, hand the controller to the next person, and go to the back of the line to wait for your turn again. If someone's game finishes in only 5 minutes, they hand the controller over early. This guarantees that nobody hogs the controller all day!
Example 1: Processes Arriving at the Same Time
Let's look at a mathematical example. Consider the following set of processes, assuming they all arrive at time 0. We will use a Time Quantum of 2 ms:
| Process | Burst Time (ms) |
|---|---|
| P1 | 5 |
| P2 | 4 |
| P3 | 3 |
The ready queue initially contains [P1, P2, P3]. Here is how execution unfolds:
1. P1 runs for 2 ms (rem 3). Queue: [P2, P3, P1]
2. P2 runs for 2 ms (rem 2). Queue: [P3, P1, P2]
3. P3 runs for 2 ms (rem 1). Queue: [P1, P2, P3]
4. P1 runs for 2 ms (rem 1). Queue: [P2, P3, P1]
5. P2 runs for 2 ms (finishes!). Queue: [P3, P1]
6. P3 runs for 1 ms (finishes!). Queue: [P1]
7. P1 runs for 1 ms (finishes!). Queue: Empty
Here is the execution timeline (Gantt chart):
+----+----+----+----+----+--+--+
| P1 | P2 | P3 | P1 | P2 |P3|P1|
+----+----+----+----+----+--+--+
0 2 4 6 8 10 11 12Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 12 ms: 12 - 0 = 12 ms.
- P2 finishes at 10 ms: 10 - 0 = 10 ms.
- P3 finishes at 11 ms: 11 - 0 = 11 ms.
The Average Turnaround Time is: (12 + 10 + 11) / 3 = 11 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 12 - 5 = 7 ms.
- P2: 10 - 4 = 6 ms.
- P3: 11 - 3 = 8 ms.
The Average Waiting Time is: (7 + 6 + 8) / 3 = 7 ms.
Example 2: Processes Arriving at Different Times
Now let's look at a scenario with different arrival times. We will keep the Time Quantum at 2 ms.
| Process | Arrival Time (ms) | Burst Time (ms) |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 5 |
| P3 | 2 | 2 |
| P4 | 3 | 1 |
Tracking the queue here requires paying close attention to exactly when a new process arrives versus when an executing process gets preempted.
Here is the Gantt chart:
+----+----+----+----+--+----+--+
| P1 | P2 | P3 | P1 |P4| P2 |P2|
+----+----+----+----+--+----+--+
0 2 4 6 8 9 11 12Let's calculate the Turnaround Time (Completion Time - Arrival Time):
- P1 finishes at 8 ms: 8 - 0 = 8 ms.
- P2 finishes at 12 ms: 12 - 1 = 11 ms.
- P3 finishes at 6 ms: 6 - 2 = 4 ms.
- P4 finishes at 9 ms: 9 - 3 = 6 ms.
The Average Turnaround Time is: (8 + 11 + 4 + 6) / 4 = 7.25 ms.
Let's calculate the Waiting Time (Turnaround Time - Burst Time):
- P1: 8 - 4 = 4 ms.
- P2: 11 - 5 = 6 ms.
- P3: 4 - 2 = 2 ms.
- P4: 6 - 1 = 5 ms.
The Average Waiting Time is: (4 + 6 + 2 + 5) / 4 = 4.25 ms.
The Impact of the Time Quantum
The performance of the Round Robin algorithm depends heavily on the size of the time quantum. If the time quantum is extremely large, the RR policy is essentially the same as the FCFS policy. If the time quantum is extremely small, the RR approach can result in a large number of context switches.
A good rule of thumb is that 80% of CPU bursts should be shorter than the time quantum.
Advantages of Round Robin
- Every process gets an equal share of the CPU, preventing starvation.
- Provides excellent response times, making it ideal for interactive and time-sharing systems.
- It is simple to implement and does not require complex predictions of burst times.
Disadvantages of Round Robin
- If the time quantum is too small, context switching overhead severely degrades system performance.
- If the time quantum is too large, it degrades into FCFS scheduling and loses its interactivity.
- Average waiting times and turnaround times are typically higher than SJF.
Time Quantum Trade-offs
Question 1 of 1Test your understanding of the Time Quantum in Round Robin.