Scheduling on Many CPUs

The Process Management topic’s schedulers (FCFS, SJF, Round Robin, Priority) assume one CPU. Real machines have many cores — and each core has its own cache, possibly its own memory controller. Multiprocessor scheduling is not “run the same algorithm on each core”; it is a distribution problem: which thread runs on which CPU, when, and how the work stays balanced without destroying cache locality.

The two masters are fairness/latency (the uniprocessor goals) and locality/balance (new). Every scheduler below is a compromise between them.

CPU Affinity and Cache Locality

Switching a thread to a different CPU is costly: it has to refill that CPU’s caches (L1/L2) and possibly a TLB — the memory-hierarchy tax from Computer Architecture. The simplest and most powerful fix is CPU affinity: keep a thread on the same CPU it last ran on (soft affinity), or pin it explicitly (hard affinity, taskset/sched_setaffinity on Linux, SetThreadAffinityMask on Windows).

The result: a busy worker thread “warms” its core, and its hot data stays resident. Real schedulers default to soft affinity — a thread migrates only when the scheduler needs to rebalance. Explicit pinning is reserved for latency-critical or cache-sensitive workloads where migration jitter is unacceptable.

Load Balancing

If every thread stayed pinned forever, one core would saturate while others idled. So schedulers migrate threads between CPUs when the load skews — two complementary mechanisms:

• Pull — an idle CPU takes a runnable thread from a busy CPU’s queue (Linux’s idle_balance; the “work stealing” of Go’s runtime and other runtimes is the same idea).
• Push — a CPU that just got several new threads pushes some to underloaded CPUs.

The rebalance cadence matters: balance too often and you pay migration/cache costs; too rarely and cores idle. Linux’s CFS runs periodic load balancing and uses per-entity load tracking (PELT) to decide when a migration is actually worth it.

NUMA-Aware Scheduling

Not all memory is equal. On Non-Uniform Memory Access (NUMA) machines, each CPU has local memory and remote memory is slower — the memory-hierarchy ladder from Computer Architecture reappears between cores. A thread that allocates on node 0 and then runs on node 1 pays remote-memory latency on every miss.

NUMA-aware scheduling keeps threads on the node where their memory lives: first-touch placement (the node that touches a page owns it) plus affinity steering keeps a thread near its pages. This is invisible on small machines and dominant at server scale — which is why numactl and sched_affinity are the first knobs for large database and JVM workloads.

Scheduler Classes: Linux CFS, Windows

Modern OSes don’t run one scheduler — they run a family with priorities between them:

• Linux — a hierarchy: SCHED_DEADLINE (EDF, highest) → SCHED_FIFO/RR (real-time, static priorities) → SCHED_NORMAL (the CFS — Completely Fair Scheduler). CFS doesn’t use time slices; it tracks each runnable task’s virtual runtime (time weighted by priority) and always runs the task with the least virtual time — a weighted fair queueing model that guarantees fairness with no fixed quantum.
• Windows — priority classes (Idle, Below Normal, Normal, High, Realtime) × per-class levels, adjusted dynamically; threads at the same priority rotate in a round-robin style within a time slice.

The concept to keep: a modern scheduler is a prioritized composition — real-time and deadline classes preempt the fair CFS, and the fair class handles the bulk of work fairly.

Real-Time Scheduling

Real-time (RT) work has a deadline: audio must be mixed before the buffer underruns, a control loop must read the sensor before the sample is stale. RT scheduling is about guaranteeing the deadline, not maximizing throughput or fairness.

• Hard real-time — missing a deadline is a system failure (flight control, medical devices). Requires admission control and provable analysis.
• Soft real-time — missing deadlines degrades quality but isn’t fatal (audio, video, gaming). Most “RT” you deploy is soft.

Classic static-priority design: rate-monotonic (RM) — assign priority inversely proportional to the task’s period (the fastest task gets the highest priority). RM is optimal among static-priority schedulers and is what SCHED_FIFO/RR approximates when you set priorities by hand.

Earliest Deadline First (EDF)

EDF is the dynamic-priority answer: at every scheduling point, run the ready task with the earliest deadline. Unlike static-priority policies, EDF can achieve full utilization (it can schedule any set of tasks whose total utilization ≤ 1 on one CPU) — but it needs to know deadlines and it degrades unpredictably under overload. Linux exposes it as SCHED_DEADLINE, so a real kernel ships both: RM-style priorities for simple cases, EDF for high utilization with real deadline knowledge.

The decision table for a designer:

Worked Example: Rate-Monotonic Assignment

Three periodic tasks on one CPU: T1 every 10 ms (needs 2 ms), T2 every 20 ms (needs 4 ms), T3 every 40 ms (needs 6 ms). Utilization = 2/10 + 4/20 + 6/40 = 0.2 + 0.2 + 0.15 = 0.55 ≤ 1, schedulable. Rate-monotonic priority: T1 highest (shortest period), then T2, then T3.

A timeline sketch: T1 runs first 2 ms of every 10 ms period; T2 fits in the gaps; T3 runs in whatever remains. The schedulability condition for RM (Liu & Layland) is n(2^(1/n) − 1) — for 3 tasks ≈ 0.78 — so 0.55 is comfortably schedulable. Had T1 needed 6 ms (utilization 0.95), RM would miss deadlines even though total utilization < 1 — the moment you reach for EDF, which handles 0.95.

Hard vs Soft Real-Time in Practice

• Soft RT is what you usually get: the kernel’s RT class (SCHED_FIFO/RR, Windows Realtime priority) guarantees priority, not timing — a misbehaving RT thread can still starve everything (why you never put a buggy loop in SCHED_FIFO on a box you care about).
• Hard RT needs a dedicated RTOS (QNX, VxWorks, seL4) with provable worst-case execution times, not a general-purpose OS. The OS Architecture topic’s microkernel discussion applies here — determinism is why safety-critical systems use microkernels.

Practice Trajectory

1. On a multi-core Linux machine, run a CPU-bound thread, taskset it to one core, and compare its throughput pinned vs unpinned; observe the migration in top (P column).
2. Use chrt -f -p 99 <pid> (or Windows Realtime priority) to promote a task to the RT class; confirm it preempts CFS tasks and note the risks.
3. On a NUMA machine, use numactl --hardware to map nodes; run a memory-heavy benchmark local vs remote and measure the latency gap.
4. Enumerate the scheduler classes on your system (ps -eo pid,comm,pri,ni,cls on Linux) and identify which process sits in each.
5. Hand-build a rate-monotonic timeline for a three-task set and check the schedulability bound; then recompute under EDF and compare.

When It’s the Right Tool