Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 10 (Advanced), Arpaci-Dusseau & Arpaci-Dusseau

Multiprocessor Scheduling (Advanced)

Advanced chapter

This topic sits with CPU scheduling but makes more sense after concurrency. Multicore is everywhere — phones included — because architects hit power walls making one core ever faster.

A typical C program uses one CPU. More cores help only if the app is rewritten to run in parallel (e.g. threads). The OS faces a new question too:

Crux: how should the OS schedule jobs on multiple CPUs? Do old techniques still work?

Background: caches and coherence

Single CPU: a cache holds popular data from slow main memory. Works because of locality:

Kind	Idea
Temporal	Access `x` → likely access `x` again soon
Spatial	Access address `x` → likely nearby addresses too

Multiple CPUs + shared memory: each core has its own cache. Write D′ on CPU 0 (maybe write-back), migrate the process to CPU 1, read again — without help you might see old D. That is the cache coherence problem.

Hardware (e.g. bus snooping) invalidates or updates remote copies so shared memory still looks consistent. Correctness ≠ speed: migrating still flushes the warm cache/TLB.

Don’t forget synchronization

Coherence does not replace locks. Concurrent updates to a shared queue/list need mutual exclusion (or carefully designed lock-free structures). Two threads can both read the same head and corrupt the list even on coherent hardware.

As CPU count grows, a single global lock around the run queue becomes a scalability bottleneck.

Cache affinity

A process builds state in a CPU’s cache/TLB. Prefer running it again on the same CPU when possible — cache affinity. It still runs correctly elsewhere (coherence), just slower while state reloads.

Single-queue multiprocessor scheduling (SQMS)

One shared ready queue; pick the best N jobs for N CPUs.

Pros	Cons
Simple — reuse uniprocessor policy	Lock contention → poor scalability
Naturally balances load	Jobs bounce → cold caches

Affinity heuristics help (pin most jobs; migrate a few for balance) but add complexity.

Multi-queue multiprocessor scheduling (MQMS)

One queue per CPU. Place a new job on some queue (random / least loaded). Schedule mostly independently.

Pros	Cons
Scales with CPU count	Load imbalance (one core idle, another busy)
Intrinsic affinity	Need migration / work stealing

Work stealing: an underloaded queue occasionally peeks at a busier one and steals jobs. Peek too often → overhead; too rarely → imbalance. Another “voo-doo” threshold.

Linux landscape

Historically: O(1) (priority / MLFQ-like, multi-queue), CFS (proportional-share, multi-queue), BFS (single queue, EEVDF-style). Both SQMS and MQMS can work — details dominate.

Interactive: coherence · SQMS · MQMS

Check your understanding

Quiz