CPU Scheduling II: Multicore, Real-Time and Linux

Multiprocessor scheduling

• Asymmetric multiprocessing: one master core runs all scheduling decisions and OS code; others run user code. Simple, but the master becomes a bottleneck.
• Symmetric multiprocessing (SMP): every core schedules itself — the design of all modern OSs.

With SMP there are two organizations:

Load balancing. With per-core queues the OS periodically evens out the load:

• Push migration: a periodic task checks loads and pushes tasks from busy to idle cores.
• Pull migration: an idle core pulls a waiting task from a busy core. Linux does both.

Example — loads per core (arbitrary units): core0 = 80 (A 30, B 20, C 10, D 20), core1 = 10, core2 = 30 (F 20 is pinned to core2, G 10), core3 = 0. Rule: repeatedly move the largest movable task from the busiest to the least-loaded core if it reduces their gap. Moves: A (30) → core3, then B (20) → core1. Result: 30 / 30 / 30 / 30 — balanced in two moves.

Processor affinity. A task that ran on a core has its data in that core's caches (a warm cache). Migrating it makes it start with cold caches. So schedulers prefer to keep tasks on the same core (soft affinity), and programs can demand specific cores (hard affinity, e.g., taskset or sched_setaffinity on Linux). Load balancing and affinity pull in opposite directions.

NUMA (non-uniform memory access). In multi-socket servers, each processor has its own memory bank; accessing a remote bank is slower. NUMA-aware schedulers keep a task near its memory.

SMT (simultaneous multithreading, e.g., Intel Hyper-Threading): one physical core runs two hardware threads that share execution units. Two logical CPUs ≠ two cores: two busy threads on the same core may each run noticeably slower than on separate cores.

Heterogeneous cores. Phones (ARM big.LITTLE) and recent PCs (Intel/AMD performance and efficiency cores) combine fast, power-hungry cores with slow, efficient ones. The scheduler must put demanding foreground work on big cores and background work on little cores — a small version of the heterogeneous scheduling problem of Chapter 6.

Gang scheduling. Threads of a parallel program that communicate frequently should run at the same time on different cores; otherwise one thread waits for another that is not running. Gang (co-)scheduling schedules them together — important for parallel scientific jobs and GPU workloads.

Scheduling in Linux

Linux has scheduling classes, checked in priority order:

1. SCHED_DEADLINE — tasks with explicit runtime/period/deadline (EDF-based).
2. SCHED_FIFO and SCHED_RR — real-time priorities 1–99 (FIFO: run until block; RR: with a quantum).
3. SCHED_NORMAL (also called SCHED_OTHER) and SCHED_BATCH — ordinary tasks, shared fairly using nice values −20 … 19.
4. SCHED_IDLE — only when nothing else runs.

CFS — the Completely Fair Scheduler (2007–2023). CFS gives each task a virtual runtime (vruntime) and always runs the task with the smallest vruntime, keeping tasks in a red–black tree ordered by it. When a task runs for Δt, its vruntime grows by:

Δvruntime = Δt × 1024 / weight

where the weight comes from the nice value: nice 0 → 1024, nice 5 → 335, nice 10 → 110, nice −5 → 3121 (each nice step ≈ 1.25×). A high-weight task's vruntime grows slowly, so it is chosen more often. The resulting CPU share is weight ÷ sum of weights:

• nice 0 vs nice 5: 1024 / (1024 + 335) = 75.3% vs 24.7%.
• Two nice-0 tasks and one nice-10 task: 47.5%, 47.5%, 5.1%.

Simulating 100 ms (1 ms slices) for video (nice 0) and backup (nice 5) gives 75 ms and 25 ms — the first 10 ms are video backup video video video backup video video video backup. In Linux 6.6 (2023), CFS was replaced by EEVDF (Earliest Eligible Virtual Deadline First), which keeps the fairness idea but also gives latency-sensitive tasks earlier "virtual deadlines". Groups of tasks (cgroups) receive shares the same way — the basis of CPU limits for containers.

Real-time scheduling

A periodic real-time task τᵢ is released every Tᵢ time units (its period), needs Cᵢ units of CPU per release, and must finish each job before its deadline (here, the end of its period, Dᵢ = Tᵢ). Examples: read a sensor every 10 ms, render a video frame every 33 ms.

Utilization: U = Σ Cᵢ / Tᵢ. If U > 1, no algorithm can schedule the tasks on one CPU.

Rate-monotonic scheduling (RM): static priorities — shorter period = higher priority, preemptive. RM is the optimal fixed-priority policy. Liu and Layland (1973) proved that n tasks are schedulable by RM if:

U ≤ n (2^(1/n) − 1)

The bound is sufficient, not necessary: above it, the task set may still be schedulable. Then use the exact response-time analysis: for task i (priorities sorted), iterate

Rᵢ = Cᵢ + Σ_(j higher priority) ⌈Rᵢ / Tⱼ⌉ · Cⱼ

starting from Rᵢ = Cᵢ until it stops changing; the task meets its deadline if Rᵢ ≤ Tᵢ.

Example 1: T1 (C = 1, T = 4), T2 (2, 6), T3 (3, 12). U = 0.25 + 0.333 + 0.25 = 0.8333 > 0.7798 → the bound is inconclusive. Response times: R1 = 1; R2: 2 → 3 (OK ≤ 6); R3: 3 → 6 → 7 → 9 → 10 ≤ 12. All deadlines are met: schedulable.

Example 2: T1 (2, 5), T2 (4, 7). U = 0.4 + 0.571 = 0.9714. R2: 4 → 6 → 8 > 7 → T2 misses its deadline under RM (at t = 7 it still has 1 unit left).

Earliest deadline first (EDF): dynamic priorities — always run the job whose deadline is nearest. On one CPU with preemption and deadlines equal to periods, EDF is optimal: the tasks are schedulable if and only if U ≤ 1. Example 2 (U = 0.97) runs with zero misses under EDF over its hyperperiod of 35 time units. RM is still popular because static priorities are simpler, predictable under overload, and supported by every RTOS.

Priority inversion: the Mars Pathfinder story

In 1997 NASA's Mars Pathfinder lander kept resetting itself on Mars. The cause: priority inversion. A low-priority task held a lock (a mutex on a shared bus); a high-priority task needed that lock and waited; meanwhile a medium-priority task, which did not need the lock, preempted the low-priority task — so the high-priority task waited for the medium one. A watchdog timer noticed the high-priority task was late and reset the computer.

The fix, uploaded from Earth, was to enable priority inheritance: while a low-priority task holds a lock needed by a high-priority task, it temporarily inherits that high priority, so medium tasks cannot preempt it. (Priority ceiling protocols are a related solution.) Locks and priorities interact — Chapter 7 continues this story.

Energy-aware scheduling

A CPU's dynamic power grows roughly with C · V² · f, and because voltage must rise with frequency, power grows about with f³. For a task of W cycles, time = W / f, so dynamic energy ≈ k · f³ · W / f = k · W · f²: running at half the frequency takes twice as long but uses about one quarter of the dynamic energy. This is DVFS (dynamic voltage and frequency scaling), done by the OS's CPU-frequency governor.

But static (leakage) power is paid as long as the chip is on, so sometimes it is better to run fast and sleep ("race to idle"). And on heterogeneous chips, a little core may finish a light task with far less energy than a big one. Linux's energy-aware scheduling on phones uses an energy model of each core type to place tasks — while still meeting deadlines.

Key takeaways

• SMP with per-core run queues + load balancing (push/pull) vs. affinity (warm caches); NUMA and SMT change the cost of placement; heterogeneous cores need task–core matching; gang scheduling for communicating threads.
• Linux classes: DEADLINE > FIFO/RR (real-time) > NORMAL (fair) > IDLE. CFS: run the smallest vruntime; Δvruntime = Δt × 1024 / weight; share = weight / Σ weights. EEVDF since Linux 6.6.
• Real time: U = Σ C/T. RM: fixed priorities by period; schedulable if U ≤ n(2^(1/n) − 1) (sufficient); otherwise use response-time analysis. EDF: optimal on one CPU, schedulable iff U ≤ 1.
• Priority inversion (Mars Pathfinder) → priority inheritance / ceiling.
• DVFS: dynamic energy ∝ W·f²; but static power and heterogeneous cores make "slow is greener" not always true.