§10.3–10.7Cache Affinity … Summary

Hardware keeps caches coherent, locks keep updates safe — one performance truth remains before we can pick a scheduler architecture.

10.3 One Final Issue: Cache Affinity

A process running on a CPU builds up state in that CPU’s caches and TLB. Run it there again and it flies; run it elsewhere and it must reload everything (correct either way — coherence guarantees that — just slow). That preference is cache affinity cache affinity A process runs faster on the CPU whose caches/TLB already hold its state; schedulers should prefer keeping it there. defined in ch. 10 — open in glossary , and a multiprocessor scheduler should honor it when it can.

10.4 Single-Queue Scheduling (SQMS)

The obvious first design: keep one queue of ready jobs — single-queue multiprocessor scheduling sqms Single-queue multiprocessor scheduling — one shared queue feeds all CPUs; simple and balanced, but lock-limited and affinity-blind. defined in ch. 10 — open in glossary — and have each of N CPUs pick the next best job. Maximum reuse of everything from chapters 7–9. Two problems, though. Scalability: the shared queue needs a lock, and lock contention grows with CPU count — the machine spends ever more time on overhead. And affinity:

Most SQMS implementations patch this with an affinity mechanism — keep most jobs home, migrate a chosen few:

Workable, but complex — and the lock problem remains untouched.

10.5 Multi-Queue Scheduling (MQMS)

The alternative: one queue per CPU — multi-queue multiprocessor scheduling mqms Multi-queue multiprocessor scheduling — per-CPU queues scheduled independently; scalable and affine, but prone to load imbalance. defined in ch. 10 — open in glossary . An arriving job is placed on one queue (randomly, or the shortest) and scheduled there independently: no shared lock, and affinity comes free — jobs simply stay put. But a new, fundamental problem appears the moment jobs finish unevenly — load imbalance load imbalance Some CPUs oversubscribed while others idle — MQMS's fundamental failure mode when jobs finish unevenly. defined in ch. 10 — open in glossary :

The answer is to move jobs — migration migration Moving a job between CPUs to rebalance load — sometimes once, sometimes continuously. defined in ch. 10 — open in glossary . For the idle-CPU case, one migration (move B or D over) fixes everything. The subtler A-alone case needs migration that never stops:

But when to migrate? The standard mechanism is work stealing work stealing A low-occupancy queue occasionally peeks at a fuller one and steals jobs; peek frequency trades overhead against imbalance. defined in ch. 10 — open in glossary :

10.6 Linux Multiprocessor Schedulers

Tellingly, the Linux community never converged on one answer:

Both multi-queue (O(1), CFS) and single-queue (BFS) approaches shipped and succeeded — architecture is a trade-off, not a theorem.

10.7 Summary

SQMS: easy to build and balances load naturally, but locks limit scaling and affinity suffers. MQMS: scales and preserves affinity, but must fight load imbalance with migration machinery. No simple answer exists — building a general-purpose scheduler remains daunting, where small code changes yield large behavioral differences. Undertake it only if you know exactly what you’re doing… or are being paid handsomely.

And with that, CPU virtualization’s mechanisms and policies are complete — from limited direct execution through single-CPU policies to multiprocessors. The Part I finale: two short dialogues, then on to memory.