04. Real-Time & Multiprocessor Scheduling

In batch and interactive systems, scheduling algorithms optimize for statistical averages: mean turnaround time, maximum throughput, or average interactive response time. However, two specialized computing domains introduce physical and temporal constraints that break standard general-purpose queuing models:

Real-Time Systems: The correctness of a computation depends not only on its logical output, but on the exact physical instant that output is delivered. Missing a deadline can result in catastrophic physical failure.
Multiprocessor / Multicore Systems (SMP): Distributing runnable threads across multiple physical execution units creates hardware cache affinity bottlenecks, interconnect memory traffic (NUMA), and inter-core lock contention.

1. Real-Time Scheduling Foundations

Real-time systems are categorized by the operational consequence of missing a deadline:

Hard Real-Time: Absolute, deterministic timing constraints. Missing a single deadline by 1 microsecond represents a total system catastrophe (e.g., flight control fly-by-wire surfaces, automotive Anti-lock Braking Systems [ABS], cardiac pacemakers, nuclear reactor protection rods). Over-provisioning hardware and mathematical schedulability proofs are mandatory.
Soft Real-Time: Deadlines are critical for quality of service, but an occasional miss causes degraded user experience rather than destruction (e.g., 60 FPS video streaming, video game rendering, VoIP voice packet decoding). Missing a deadline drops a frame; the system continues operating.

The Periodic Task Formal Model

A classic real-time system executes a set of n periodic tasks, denoted Τ = {τ₁, τ₂, ..., τ_n}. Each task τ_i is characterized by three deterministic physical parameters:

Period (P_i): The time interval between successive releases or arrivals of the task.
Worst-Case Execution Time (C_i): The maximum continuous computation time required by the task on the target CPU core.
Deadline (D_i): The time relative to task arrival by which computation must complete. In standard synchronous models, the deadline equals the period: D_i = P_i.

Total CPU Utilization (Load Factor, U):
The fraction of CPU execution bandwidth demanded by the periodic task set is the sum of their individual utilization ratios:

U = ∑_i=1ⁿ (C_i / P_i)

Necessary Condition for Schedulability:
For any single-core hardware architecture, the task set cannot possibly be scheduled without missing deadlines if total utilization exceeds 100%:

U ≤ 1.0

If U > 1.0, the task set is mathematically unschedulable under any algorithm.

2. Rate-Monotonic Scheduling (RMS)

Developed by C. L. Liu and James Layland (1973), Rate-Monotonic Scheduling (RMS) is the canonical static-priority scheduling algorithm for periodic real-time tasks:

Static Assignment Rule: Priorities are assigned to tasks prior to system execution based strictly on their rate (frequency of occurrence, 1 / P_i).
The Monotonic Priority Principle: Tasks with shorter periods (higher rates) receive higher static priority. Tasks with longer periods receive lower priority.
Preemption: If a high-priority task with a short period arrives while a low-priority task is running, the running task is immediately preempted.

The Liu & Layland Schedulability Bound

Is a task set with U ≤ 1.0 guaranteed to meet all deadlines under RMS? No. Because priorities are fixed statically, a long-period task can be repeatedly preempted by short-period tasks, missing its deadline even when spare CPU capacity exists.

Liu and Layland proved that a set of n independent periodic tasks is guaranteed to be schedulable under Rate-Monotonic Scheduling if its total CPU utilization satisfies the following inequality:

U = ∑_i=1ⁿ (C_i / P_i) ≤ n(2^1/n − 1)

Evaluating the bound across increasing task counts:

n = 1: U ≤ 1(2¹ − 1) = 100%
n = 2: U ≤ 2(2^1/2 − 1) ≈ 2(1.414 − 1) = 82.8%
n = 3: U ≤ 3(2^1/3 − 1) ≈ 3(1.260 − 1) = 77.9%
As n → ∞: lim_n→∞ n(2^1/n − 1) = ln(2) ≈ 69.3%

The 69.3% Invariant: If total utilization of any arbitrary periodic task set is below 69.3%, Rate-Monotonic scheduling guarantees that no deadline will ever be missed. If utilization falls between 69.3% and 100%, the set may still be schedulable, but requires exact Response-Time Analysis (RTA) recurrence testing.

3. Earliest Deadline First (EDF)

To overcome the 69.3% static priority ceiling and achieve up to 100% CPU utilization, operating systems turn to Earliest Deadline First (EDF).

Dynamic Priority Assignment: Unlike RMS, priorities under EDF are not fixed at compile time. Priorities are assigned dynamically at runtime.
The Dynamic Selection Rule: Whenever the scheduler evaluates runnable tasks, it selects the task whose absolute deadline (d_i) is closest to the current physical clock.
Preemption: If task τ₂ arrives with a deadline at T = 14 ms while task τ₁ is executing with a deadline at T = 18 ms, τ₁ is immediately preempted because 14 < 18.

The Optimality of EDF

Theorem: Earliest Deadline First is an optimal dynamic uniprocessor scheduling algorithm. A set of periodic tasks with deadlines equal to periods is schedulable under EDF if and only if:

U = ∑_i=1ⁿ (C_i / P_i) ≤ 1.0 (100%)

EDF can fully saturate a processor execution core up to 100% capacity without missing a single deadline.

The Fatal Flaw of EDF: Domino Effect under Overload

Despite its theoretical optimality, EDF exhibits a dangerous vulnerability in mission-critical environments: the cascading domino effect during transient overloads.

RMS Under Overload: Under static Rate-Monotonic priorities, if a system experiences a spike where U = 1.20, high-priority tasks (short periods) continue running perfectly without missing deadlines. Only the lowest-priority background tasks miss deadlines. System failure is contained predictably.
EDF Under Overload: If U > 1.0, EDF constantly prioritizes the task closest to failing its deadline. That task executes, misses its deadline anyway, and by doing so, delays the next upcoming task, causing it to miss its deadline as well. A single transient spike can cause every task in the entire system to miss its deadline consecutively.

Interactive Stepper: Static RMS vs. Dynamic EDF under High Utilization

Timeline Clock T = 0 ms

Active Core Task Task 1 (C=2, P=5)

Next Urgent Deadline Task 1 (d = 5 ms)

Schedulability Status Nominal (Zero Misses)

Current Step Summary At T=0, both Task 1 and Task 2 release instances. Under RMS, Task 1 (period 5) has shorter period than Task 2 (period 7), so Task 1 takes top static priority.

What Is Happening

Task 1 runs on Core 0 from T=0 to T=2 ms. Task 2 waits in the Ready list.

Why The System Does This

RMS assigns highest priority to the shortest period task (P1=5 < P2=7) to ensure high-frequency events complete ahead of longer deadlines.

4. Multiprocessor Scheduling (SMP Architectures)

Modern processors do not scale through raw clock frequency increases; they scale horizontally through multiple physical CPU cores. Symmetric Multiprocessing (SMP) architectures share a unified physical address space across all cores, but introduce complex hardware topology and memory latency bottlenecks.

Single-Queue vs. Multi-Queue Topologies

Operating system architects face a foundational design fork when structuring multiprocessor runqueues:

Figure 4.1: Single-Queue (SQMS) vs. Multi-Queue (MQMS) Topologies

Comparing global lock contention against per-core cache affinity and work-stealing load balancing.

Work Stealing to balance idle cores.

Hardware Cache Affinity & Invalidation Overhead

When a process runs on Core 0, its instructions and working data are fetched into Core 0's private L1 and L2 silicon caches. The task runs at peak hardware speed.

If the scheduler preempts the task and subsequently dispatches it onto Core 1:

Cold Cache Penalties: Core 1's L1/L2 caches contain none of the process's working set. The CPU stalls on memory read requests, waiting tens of nanoseconds for data from shared L3 cache or DRAM.
Cache Invalidation Traffic: Hardware cache coherence protocols (such as MESI or MOESI) must broadcast bus invalidation signals across the interconnect fabric to invalidate the stale dirty lines sitting in Core 0's cache, creating cross-core bandwidth saturation.

To prevent this, production schedulers enforce Processor Affinity:

Soft Affinity: The scheduler attempts to re-dispatch a process on the exact CPU core where it previously executed, but will migrate it to an idle core if queue imbalances become severe.
Hard Affinity (sched_setaffinity(2)): The application explicitly pins a thread to a specified bitmask of physical CPU cores, strictly prohibiting inter-core migration.

NUMA-Aware Scheduling (Non-Uniform Memory Access)

On modern multi-socket enterprise servers and high-core-count processors (such as AMD EPYC and Intel Xeon), memory controllers are partitioned across distinct physical silicon dies called NUMA Nodes.

Accessing local memory directly wired to the core's own node takes ≈ 60–80 ns.
Accessing remote memory attached to another socket via high-speed interconnects (Ultra Path Interconnect [UPI] or Infinity Fabric) takes ≈ 130–180 ns (a 2× to 3× latency penalty).
NUMA Scheduling Invariant: Schedulers must be NUMA-aware. A thread must be scheduled on the CPU node where its memory pages physically reside (following the operating system's first-touch memory allocation policy). Migration between NUMA sockets is treated as an expensive last resort.

Work Stealing Algorithms

To maintain near-perfect load balance in MQMS without global lock contention, modern schedulers implement Work Stealing:

Each CPU core maintains its own double-ended queue (deque) of runnable tasks.
A core pushes and pops tasks from the head of its own deque in LIFO order, maximizing hardware L1 cache locality for recently paused sub-tasks.
When a core exhausts its own runqueue and becomes idle, it randomly chooses a peer core (the "victim") and attempts to steal work from the tail of the victim's deque in FIFO order.
Stealing from the tail minimizes lock conflicts with the victim core (which accesses the head), while simultaneously grabbing the oldest queued task—the task whose cache footprint on the victim core is already cold, making cross-core migration practically free.