CSE Roadmap

Core tier · about 4 hours · 6 parts

Part 4 of 6 · 2 min read

Overhead

In plain words: Switching is not free. Every switch spends a short time saving and loading context and refilling caches (Level 1, page 5). If this time is s and the quantum is q, then in each cycle q is useful and s is lost, so the useful fraction is

q ÷ (q + s)

Level 1 measured about 1 microsecond for a switch on this machine, and the figure s is taken as 1 microsecond below (the cache refill that follows adds more, and makes the true cost larger):

Quantum q Useful fraction q ÷ (q + s) Time lost
10 ms 0.9999 0.01 per cent
1 ms 0.999 0.1 per cent
10 µs 0.909 9.1 per cent
1 µs 0.5 50 per cent

A quantum in milliseconds loses almost nothing. A quantum in microseconds wastes much of the machine. The choice is a balance: short enough for a quick response, long enough that switching is a small fraction of the time.

The same effect shows up in the small example. If each switch costs half a time unit (made up to show the idea), the end time of the whole workload grows with the number of switches:

Quantum Switches End time (18 + 0.5 × switches)
1 13 24.5
2 8 22.0
3 5 20.5
4 5 20.5
8 3 19.5

Small quanta delay the end of the work by about a third.

A rule of thumb from the books: most CPU bursts should be shorter than the quantum. Then an I/O-bound process finishes its burst and waits before the timer fires, and the quantum affects mostly the long, CPU-bound processes. Real systems use quanta in the range of a few milliseconds to tens of milliseconds.

Context-switch overhead

Context-switch overhead is the share of processor time spent switching between processes instead of running them, equal to s ÷ (q + s) for a switch cost s and a quantum q.

Example: with a 1 ms quantum and a 1 µs switch, the overhead is 0.001 ÷ 1.001, about 0.1 per cent.

Check yourself: 1. What is the useful fraction for a 100 µs quantum and a 1 µs switch? 2. Why is a quantum of 1 µs a bad choice? 3. Why does the real cost of a switch exceed the measured 1 µs?