Chapter 10 puts several CPUs, each with its own cache, in front of the scheduler built in Chapters 7–9. This tool follows the three issues a single-CPU scheduler never had to face — cache coherence, synchronization and cache affinity — then compares the two classic ways to organize run queues across CPUs: one shared queue (SQMS) and one queue per CPU (MQMS), including what MQMS has to do about the load imbalance it creates.
Why one CPU's assumptions break with several
Every CPU on a multicore chip has its own private cache to avoid hitting main memory on every access.
Caching keeps single-CPU scheduling cheap — but now the same memory location can have multiple, disagreeing copies, one per CPU cache.
This is the cache coherence problem: hardware has to make sure every CPU eventually sees the same value for the same address.
Watch a stale read happen
CPU 1 caches a value, then CPU 2 changes it. Step through with and without a coherence protocol.
Scenario
CPU 1
cache: empty
CPU 2
cache: empty
Memory: D = 50
Press Next to start, or Play to animate.
Coherence is solved in hardware, not by the scheduler: protocols like bus snooping watch every write and invalidate or update stale copies so all CPUs agree on one value per address.
Shared data now means shared across CPUs
The OS keeps shared data structures — run queues, free lists — that code on any CPU might touch at the same time.
Without protection, two CPUs interleaving on the same structure race each other and can corrupt it.
Locks fix correctness, but every CPU that wants the lock has to wait its turn — a single lock becomes a bottleneck as the CPU count grows.
Two CPUs pop the same free list
T1 runs on CPU 0, T2 on CPU 1. Both call pop() on a 3-node free list, A → B → C, at almost the same time.
Scenario
Press Next to start, or Play to animate.
A shared structure touched by several CPUs needs a lock to stay correct — the cost is CPUs piling up waiting for it, exactly the scalability problem a single shared run queue runs into (Tab 4).
A warm cache is worth keeping
Whichever CPU a process last ran on has its data sitting in that CPU's cache — a warm cache.
Move the process to a different CPU and that cache starts empty for it — a cold start, paid for in extra memory stalls until it warms back up.
A scheduler with cache affinity tries to keep a process on the same CPU run after run.
Same six time slices for process P, two policies
Click any round on either row to see why it was warm or cold.
Ignore affinity — whichever CPU happens to be free
Respect affinity — prefer P's last CPU
Click a round above on either row.
Same process, same six rounds — respecting affinity turns most of them warm instead of cold.
One queue, shared by every CPU
Single-Queue Multiprocessor Scheduling (SQMS) puts every runnable job in one global queue and lets any single-CPU policy (RR, SJF, …) pick from it.
Simple to build — it reuses single-CPU scheduling almost unchanged, and naturally keeps CPUs load-balanced.
Cons
(1) Lack of scalability — some form of locking needs to be inserted around the shared queue so CPUs popping from it at the same time don't race each other (Tab 2). More CPUs means more contention for that one lock.
(2) Cache affinity issue — nothing ties a job to the CPU it last ran on, so it can land on a different CPU almost every time it's rescheduled (Tab 3).
Con (1) and (2) together: five jobs, one queue, two CPUs
Shared queue (front → back)
CPU 0
idle
CPU 1
idle
Press Next to start, or Play to animate.
Every pop above happens under the queue's lock — that's Con (1). Watch job A: it starts on CPU 0, but later gets pulled back off the queue by CPU 1 — that's Con (2).
Con (2) in detail: 4 CPUs, 1 shared queue
Five processes, A–E, cycle through a single queue feeding four CPUs — only four can run at once, so one process always waits. Pick an option, then step through the rounds and watch the schedule table fill in.
Option
Press Next round to populate round 1, or Play to animate through all five rounds.
SQMS scales poorly as CPUs are added (Con 1), and by default has no cache affinity at all (Con 2) — Option 1 above. Real single-queue schedulers add explicit affinity mechanisms, like Option 2, accepting a little load imbalance to keep most processes warm.
One queue per CPU
Multi-Queue Multiprocessor Scheduling (MQMS) gives each CPU its own queue and its own lock.
No shared lock to fight over, and a job that stays in one queue keeps running on the same CPU — good affinity, for free.
The catch: queues fill and drain independently, so nothing keeps their lengths in balance.
Two independent queues can drift apart
CPU 0's queue
CPU 1's queue
CPU 0
idle
CPU 1
idle
Press Next to start, or Play to animate.
MQMS scales and preserves affinity, but with no coordination between queues it can leave one CPU idle while another stays backed up — the load-imbalance problem.
Two ways to move work across queues
Migration: the OS notices the imbalance itself and explicitly moves a waiting job from a long queue to a short one.
Work stealing: instead of waiting for the OS to notice, a CPU whose own queue is (nearly) empty periodically peeks at another queue and steals a job off its tail. It's the same move as migration — just decided locally, by the idle side, instead of centrally.
The tuning problem for stealing is how often to check: too often and you pay constant overhead and throw away the affinity MQMS was giving you for free; too rarely and CPUs sit idle while work piles up elsewhere.
Approach 1 · Migration: the OS moves a specific job
Q0 (CPU 0) is empty; Q1 (CPU 1) holds B and D. The OS decides to move one of them over — either choice fixes the imbalance equally well.
Q0 (CPU 0)
Q1 (CPU 1)
Q0 is empty while Q1 has two jobs waiting. Move either B or D over to balance them.
Approach 2 · Work stealing: the idle CPU helps itself
Picking up where Tab 5 left off: CPU 0's queue is backed up, CPU 1's is empty. This time nobody tells CPU 1 what to do — it checks for itself.
CPU 0's queue
CPU 1's queue
CPU 1's queue is empty while CPU 0 still has jobs waiting. Click Steal a job to have CPU 1 check CPU 0's queue and take one off the tail.
Whether the OS pushes a job (migration) or an idle CPU pulls one for itself (work stealing), the fix is the same move — spread the queues back out before a CPU sits idle for too long.