CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 3 of 6 · 2 min read

The quantum

In plain words: The same toy-passing game shows the effect of the minute. A one-second turn makes everyone feel served, and the children spend more time passing the toy than playing. A one-hour turn makes the game efficient and the last child wait very long. The analogy stops in one place: passing a toy costs seconds, and a context switch costs only about a microsecond (Level 1, page 5).

Run the same four processes with different quanta. All figures below come from a trace like the one in section 1.

Quantum Average turnaround Average waiting Average response Context switches
1 11.00 6.50 0.75 13
2 11.75 7.25 2.00 8
3 10.50 6.00 3.00 5
4 11.50 7.00 4.00 5
8 (longer than any job) 10.25 5.75 5.75 3

Two things stand out.

  1. Response time grows with the quantum. From 0.75 at a quantum of 1 to 5.75 at a quantum of 8. A short quantum puts every new process near the front, so it starts soon.
  2. A quantum longer than every burst gives FCFS. The last row equals the FCFS result of page 1. Round robin with an infinite quantum is FCFS.

Average turnaround does not follow a simple rule. It moved up and down as the quantum changed, because it depends on how the quantum divides the jobs. Round robin does not minimise turnaround. It is worse than SJF (8.50) and SRTF (8.00) on this workload for every quantum, since it spreads the time evenly and delays the short jobs that SJF would finish quickly. It gains in response time and fairness.

Time quantum

The time quantum (or time slice) is the longest period for which a process may run before the timer interrupt returns control to the scheduler, and it is the main tuning parameter of round robin.

Example: with a quantum of 4 ms, a process that computes for 10 ms is interrupted after 4 ms and again after 8 ms, and it finishes in its third turn.

Check yourself: 1. At which quantum was the average response time smallest, and why? 2. Why does a very large quantum make round robin behave like FCFS? 3. Is round robin better than SJF on average turnaround in the table?