CSE Roadmap

Core tier · about 4 hours · 6 parts

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?