Multiprocessor Scheduling

Everything so far — MLFQ, stride, CFS — answered "who runs next?" for a single CPU. Now there are dozens of them. A modern server has 64, 128, or more hardware threads, and the scheduler must decide not just when a task runs but where. Two facts, both from shared-memory architecture, dominate every decision: cores do not share caches all the way down, and a lock that every core must grab is a scalability disaster. Multiprocessor scheduling is the art of respecting both.

The first and most consequential choice is the shape of the run queue: one global queue shared by all cores, or one run queue per CPU. It sounds like a minor implementation detail. It is the whole ball game.

Single global queue versus per-CPU queues

A single global queue (SQMS — single-queue multiprocessor scheduling) is trivially fair and load-balanced: every idle core just grabs the next task off the one shared list. But that list is shared mutable state, so every scheduling decision on every core must take the same lock. With N cores hammering one lock, contention grows roughly with N and the scheduler stops scaling — the cores spend their time waiting for each other instead of running work. Worse, a task bounces from core to core on successive quanta, trashing cache affinity every time.

So real kernels — Linux, Windows, FreeBSD — use per-CPU run queues (MQMS). Each core has its own queue and its own lock, so scheduling decisions are almost entirely local and contention-free, and a task tends to stay on one core and keep its cache warm. The price is that the queues drift out of balance — one core piled high while another sits idle — which the kernel must actively correct by migrating tasks. The diagram shows the layout and the migration that rebalances it.

Per-CPU queues and migration

Balancing happens two ways. In push migration a periodic balancer notices CPU 0 is overloaded and shoves a task onto idle CPU 2. In pull migration — Linux calls it work stealing — an about-to-go-idle core reaches into a busier core's queue and takes work for itself. Both fix imbalance, but both pay the migration cost: the task arrives on its new core with a cold cache and must refetch its working set from a shared cache or memory. A migration can cost thousands of cycles of cache misses, so the balancer is deliberately reluctant — it migrates only when the imbalance is worth the reload, and it respects affinity by preferring to keep tasks where their data already is.

Global queue: perfect load balance, but one lock ⇒ contention that grows with core count, and poor cache affinity;
Per-CPU queues: local, scalable, cache-friendly, but must be rebalanced by migration (push, or pull/work-stealing);
Cache affinity: keep a task on the core whose cache holds its data — migration throws that away and pays a cold-cache reload;
NUMA: migrating across memory nodes is worse still — the task's memory is now remote — so the balancer prefers to move within a node;
Gang scheduling: co-schedule all threads of one parallel job at once, so they can communicate without waiting on a descheduled peer.

A load balancer in code

Here is the essence of work stealing: an idle core finds the busiest core and pulls half its backlog. Halving (rather than taking one task) is what real stealers do — it minimises how often you have to steal, amortising the migration cost.

// Per-CPU run queues; an idle core steals HALF of the busiest core's backlog. const queues: number[][] = [ [1, 2, 3, 4, 5, 6], // CPU 0: overloaded [7, 8], // CPU 1 [], // CPU 2: idle — will steal ]; const load = () => queues.map((q) => q.length); console.log("before: loads = [" + load().join(", ") + "]"); // CPU 2 is idle: find the busiest queue and take half of it. const idle = 2; let busiest = 0; for (let i = 0; i < queues.length; i++) if (queues[i].length > queues[busiest].length) busiest = i; const steal = Math.floor(queues[busiest].length / 2); const taken = queues[busiest].splice(0, steal); // migrate these tasks (their caches go cold) queues[idle].push(...taken); console.log(`CPU ${idle} stole ${steal} tasks from CPU ${busiest}: [${taken.join(", ")}]`); console.log("after steal: loads = [" + load().join(", ") + "]"); const avg = load().reduce((s, n) => s + n, 0) / queues.length; console.log("average load per CPU = " + avg.toFixed(2) + " (perfect balance would be this on every core)");

Why the lock decides scalability

Model it simply. With per-CPU queues, adding a core adds a core's worth of scheduling throughput — the line is straight, y = N. With a single global lock, each of the N contenders slows every decision, so useful throughput behaves like N/(1 + k(N-1)) and saturates — beyond some point, more cores make things worse, not better. Drag the lock-cost slider and watch the global-queue curve peel away from the ideal line. This is exactly why the industry moved from "big kernel lock" designs to fine-grained, per-CPU state.

Meet gang scheduling's reason for existing. A parallel job whose threads constantly communicate — barrier synchronisation, a producer/consumer pipeline, an MPI collective — grinds to a halt if even one of its threads is descheduled while the others try to talk to it. Thread A spins waiting on a message from thread B, but B is not currently on any core, so A wastes its entire quantum spinning. With hundreds of such micro-stalls a second the job crawls even though CPUs sit idle. Gang scheduling co-schedules all the job's threads in the same time slice across cores, so they are all present to talk to each other. HPC schedulers and hypervisors (which must avoid descheduling one vCPU of a guest that holds a spinlock — "lock-holder preemption") care about this intensely.

It is tempting to balance queues to exactly equal length at every tick. That is a trap. Each migration costs a cold-cache reload (and, across NUMA nodes, remote-memory penalties on every subsequent access until the pages migrate too). A scheduler that chases perfect balance migrates constantly and spends more on cache misses than it saves in idle time. Real balancers are hysteretic and lazy: they tolerate mild imbalance, migrate only when a core would otherwise idle or the imbalance crosses a threshold, and prefer moving a task that is not "cache-hot". The right objective is keep every core usefully busy at the least migration cost, not equal queue lengths.

The shape of the whole problem

Multiprocessor scheduling layers a placement problem on top of the single-core ordering problem, and every knob trades the same two currencies: locality (keep a task's data close and its cache warm) versus utilisation (keep every core busy). Linux's CFS/EEVDF runs a per-CPU red-black tree with a hierarchical, NUMA-aware balancer that walks scheduling domains (SMT siblings, then a socket, then across sockets), migrating reluctantly and locally first. The last scheduling frontier is tasks with deadlines rather than mere fairness — real-time scheduling — where being late is not just slow but wrong.