Part 2 of 6 · 3 min read
Round robin
In plain words: Children share one toy by passing it round a circle, each keeping it for one minute, whatever is happening. Nobody keeps it for ever, and nobody needs to guess how long a child wants it. The analogy stops in one place: a child may give the toy up early when bored, and so may a process, by waiting for input.
Round robin (RR) keeps the ready queue in a circle. The scheduler takes the process at the front and lets it run for at most one time quantum (also called a time slice), a fixed length of time. If the process finishes or waits within the quantum, the scheduler picks the next one at once. If the quantum ends first, a timer interrupt (Level 0) stops the process, and it goes to the back of the queue. Round robin is preemptive.
Trace the workload of pages 1 and 2 (A, B, C, D arriving at 0, 1, 2, 3 with CPU times 5, 3, 8, 2) with a quantum of 3. One rule is needed for ties: when a process arrives at the same moment another's quantum ends, the new arrival goes into the queue first. (Other books use the opposite rule, so a table from another source may differ.)
| Time | Event | Queue after the event | Running |
|---|---|---|---|
| 0 | A starts | (empty) | A |
| 1, 2 | B and C arrive | B, C | A |
| 3 | D arrives, A's quantum ends (A has 2 left) | B, C, D, A | B |
| 6 | B ends | C, D, A | C |
| 9 | C's quantum ends (C has 5 left) | D, A, C | D |
| 11 | D ends | A, C | A |
| 13 | A ends | C | C |
| 18 | C ends | (empty) | none |
The timeline is A 0 to 3, B 3 to 6, C 6 to 9, D 9 to 11, A 11 to 13, C 13 to 18. At time 16, C's second quantum ends with 2 left, but the queue is empty, so C continues without a switch.
| Process | Finish | Turnaround | Waiting | Response |
|---|---|---|---|---|
| A | 13 | 13 | 8 | 0 |
| B | 6 | 5 | 2 | 2 |
| C | 18 | 16 | 8 | 4 |
| D | 11 | 8 | 6 | 6 |
The averages are turnaround 42 ÷ 4 = 10.50, waiting 24 ÷ 4 = 6.00 and response 12 ÷ 4 = 3.00.
A useful property: with n ready processes and a quantum of q, no process waits more than (n − 1) × q before its next turn. Nobody starves.
Round robin
Round robin is a preemptive scheduling policy that keeps the ready processes in a first-in, first-out queue and runs the process at the front for at most one time quantum before moving it to the back, so that each of n ready processes waits at most (n − 1) quanta between turns.
Example: with a quantum of 3 and three ready processes, each process runs for 3 units and then waits for the other two, so its wait between turns is at most 6 units.
Check yourself: 1. In the trace, why did B run at time 3 and not A? 2. What happens at time 16 when C's quantum ends? 3. What is the largest wait between turns for 5 ready processes and a quantum of 4 ms?