Multi-Processor Scheduling

For decades, computer performance growth followed a simple trajectory: faster clock speeds meant faster programs. Engineers and programmers rode Moore's Law, confident that each generation of processors would automatically make their software run faster. Then, around 2004, the industry hit a wall—the power wall, the frequency wall, and the instruction-level parallelism wall simultaneously. Clock speeds stagnated, but the demand for computing power continued to accelerate.

The solution? Parallelism at the processor level. Instead of one faster core, modern systems deploy multiple cores working in harmony. But this architectural shift fundamentally changes how operating systems must approach CPU scheduling. A scheduler designed for a single processor becomes inadequate—even counterproductive—in a multi-processor environment.

Symmetric Multiprocessing (SMP) is a multiprocessor architecture where two or more identical processors are connected to a single, shared main memory and are controlled by a single operating system instance. The term "symmetric" is crucial—it defines the fundamental property that distinguishes SMP from other multiprocessor architectures.

The Symmetry Principle:

In an SMP system, all processors are functionally identical and equally privileged:

• Every processor can access all memory locations with uniform latency (within the physical constraints of the memory system)
• Every processor can execute any process or thread in the system
• Every processor can handle interrupts from any device
• Every processor runs the same operating system kernel image
• No processor has special status or exclusive access to resources

This symmetry creates an elegant abstraction: from the operating system's perspective, processors are interchangeable. A ready process can be dispatched to any available processor without architectural constraints. This property, while conceptually simple, enables sophisticated load balancing and failure tolerance.

Architectural Components of SMP:

An SMP system consists of several tightly integrated components that work together to present a coherent computing environment:

The shared memory characteristic of SMP is not merely a technical feature—it fundamentally shapes how software is written and how operating systems manage concurrent execution. Understanding its implications is essential for effective multi-processor scheduling.

Memory Access Model:

In an ideal SMP system, all processors have Uniform Memory Access (UMA)—the latency to access any memory location is the same for all processors. While true UMA is approximated in small-scale SMP systems, real hardware has nuanced access characteristics:

• Access to L1 cache: ~1-4 cycles
• Access to L2 cache: ~10-20 cycles
• Access to L3 cache (shared): ~30-50 cycles
• Access to main memory: ~100-300 cycles

These differences create implicit "locality" even in UMA systems—data in a processor's cache hierarchy is dramatically faster to access than data elsewhere.

Implications for Scheduling:

The memory hierarchy creates significant scheduling considerations:

1. Cache Affinity: When a process runs on a processor, its working set becomes cached in that processor's cache hierarchy. If the scheduler moves the process to a different processor, the cache must be repopulated—a "cold start" penalty that can cost millions of cycles for large working sets.

2. False Sharing: When two processors modify different variables that happen to reside on the same cache line, the coherence protocol forces cache invalidations even though no actual data sharing occurs. The scheduler can inadvertently exacerbate this by frequently moving processes.

3. Memory Bandwidth Contention: Even with shared memory access, the bus or interconnect has finite bandwidth. Too many processors accessing memory simultaneously creates contention, degrading overall system performance.

These factors mean that optimal SMP scheduling isn't simply about keeping all processors busy—it must also respect the memory system's physical reality.

Perhaps the most sophisticated aspect of SMP hardware is the cache coherence protocol—the mechanism that ensures all processors observe a consistent view of memory despite each maintaining local cached copies. Without coherence, processors could operate on stale data, leading to impossible-to-debug corruption.

The Coherence Problem:

Consider a simple scenario:

1. Processors P0 and P1 both read variable X (value = 0) into their L1 caches
2. P0 modifies X to 1, updating its L1 cache
3. P1 reads X—should it see 0 (its cached copy) or 1 (P0's updated value)?

Without coherence, P1 sees 0, creating an inconsistent view of memory that violates the shared memory abstraction. Cache coherence protocols solve this by tracking cache line states and propagating updates.

The MESI Protocol:

The most widely implemented coherence protocol is MESI, named for its four cache line states:

Coherence Traffic and Scalability:

Cache coherence is not free. Every state transition generates traffic on the interconnect:

• Invalidation broadcasts: When a processor writes to a Shared line, invalidation messages must reach all other caches
• Data sharing: When a processor reads data that another has Modified, the data must be transferred
• Snooping overhead: In bus-based systems, every cache must monitor (snoop) all bus transactions

As processor count increases, coherence traffic grows—potentially quadratically in pathological cases. This is why traditional bus-based SMP systems rarely scale beyond 8-16 processors. Modern systems use directory-based coherence and hierarchical interconnects to manage this complexity.

Running an operating system on an SMP platform introduces fundamental challenges that don't exist in uniprocessor systems. The OS must now handle true concurrency—multiple processors executing kernel code simultaneously—while maintaining correctness and performance.

The Single-Kernel Image:

In SMP, all processors run the same operating system kernel. This is a crucial simplification compared to alternatives, but it creates coordination requirements:

• Multiple processors may simultaneously attempt to modify kernel data structures
• Interrupt handlers can execute on any processor, potentially concurrent with system calls
• The scheduler itself may run on multiple processors simultaneously, racing to grab ready processes

Without careful design, an SMP kernel can exhibit race conditions, deadlocks, or worse—silent data corruption.

Evolution of Kernel Locking:

OS kernels have evolved through several approaches to handle SMP concurrency:

1. Giant Kernel Lock (GKL) / Big Kernel Lock (BKL):

The simplest approach—a single lock protecting the entire kernel. Only one processor can execute kernel code at a time.

• Advantage: Simple to implement; existing uniprocessor code works without modification
• Disadvantage: Severe bottleneck; kernel serialization eliminates most parallelism benefits

2. Coarse-Grained Locking:

Divide the kernel into subsystems, each with its own lock. Processors can execute in different subsystems simultaneously.

• Advantage: Better parallelism for workloads spanning subsystems
• Disadvantage: Lock contention for hot subsystems; complex to reason about lock ordering

3. Fine-Grained Locking:

Every data structure has its own lock. Maximum parallelism at the cost of complexity.

• Advantage: Minimal contention for well-designed workloads
• Disadvantage: Risk of deadlock; significant code complexity; lock overhead for every operation

4. Lock-Free and Wait-Free Structures:

Modern kernels use atomic operations and carefully designed algorithms to avoid locks entirely for some operations.

• Advantage: No lock contention or deadlock risk
• Disadvantage: Extremely difficult to implement correctly; limited applicability

The scheduler in an SMP system faces challenges that fundamentally differ from uniprocessor scheduling. It must not only decide which process runs, but also where (on which processor) and when to migrate processes between processors.

Key Architectural Decisions:

1. Run Queue Organization:

There are two fundamental approaches to organizing ready processes:

Global Run Queue: A single queue of ready processes, shared by all processors.

• Processors compete to dequeue the next process
• Natural load balancing—processors always grab work from the same pool
• Severe contention at the queue lock as processor count increases
• Poor cache affinity—processes bounce between processors

Per-Processor Run Queues: Each processor maintains its own queue of ready processes.

• No contention for queue access (each processor accesses only its own)
• Excellent cache affinity—processes tend to stay on their assigned processor
• Load imbalance risk—some processors may be idle while others are overloaded
• Requires explicit load balancing mechanism

Modern SMP schedulers universally use per-processor run queues. The scalability benefits are decisive—global queue lock contention limits practical scalability to perhaps 8-16 processors, while per-processor queues scale to hundreds of cores.

2. Load Balancing Strategy:

With per-processor queues, load balancing becomes an explicit scheduler responsibility. The scheduler must periodically:

• Detect imbalance (some processors overloaded, others idle)
• Select processes to migrate based on priority, cache affinity, and other factors
• Execute the migration without disrupting running processes

Linux, for example, implements both push and pull migration:

• Push: Overloaded processors push tasks to less loaded ones
• Pull: Idle processors pull tasks from loaded ones

The frequency and aggressiveness of load balancing creates tradeoffs. Too frequent rebalancing disrupts cache affinity; too infrequent allows persistent imbalance.

SMP systems require mechanisms for processors to communicate with each other. While shared memory provides one form of communication, the operating system often needs immediate, targeted signaling between processors.

Inter-Processor Interrupts (IPIs):

IPIs are hardware-level signals that one processor sends to another, forcing the target processor to respond immediately:

• Scheduler IPIs: Wake an idle processor to run a newly-ready high-priority task
• TLB Shootdown IPIs: Force all processors to invalidate TLB entries after page table changes
• Cache Flush IPIs: Request cache synchronization before DMA operations
• Function Call IPIs: Execute a function on another processor (used for debugging, profiling)

IPIs are powerful but expensive—they force the target processor to interrupt its current work, save context, handle the IPI, and restore context. Overuse of IPIs can significantly impact performance.

Memory Barriers and Synchronization:

Modern processors execute instructions out of order and cache writes for efficiency. In SMP systems, this can cause one processor to observe memory operations in a different order than another processor executed them—a phenomenon that violates intuitive expectations about program behavior.

Memory barriers (fences) are special instructions that enforce ordering:

• Read barrier (rmb): Ensures all reads before the barrier complete before any reads after
• Write barrier (wmb): Ensures all writes before the barrier are visible before writes after
• Full barrier (mb): Orders both reads and writes

Without proper barriers, SMP code can exhibit bugs that:

• Only appear under heavy load
• Only occur on certain processor architectures
• Disappear when debugging code is added (timing changes)

These are among the most difficult bugs to diagnose in systems programming.

Contemporary SMP systems have evolved far beyond the simple "multiple processors on a bus" model. Understanding modern implementations is essential for effective scheduling decisions.

Multi-Core Processors:

Today's SMP systems are dominated by multi-core processors—multiple CPU cores integrated onto a single chip (die). This integration provides several advantages:

• Shared Last-Level Cache (LLC): Cores share L3 cache, enabling efficient data sharing without main memory access
• On-chip Interconnect: Core-to-core communication is faster than crossing chip boundaries
• Power Efficiency: Shared infrastructure (memory controller, I/O) reduces total power consumption
• Thermal Management: Unified thermal envelope allows dynamic power distribution

Simultaneous Multithreading (SMT) / Hyper-Threading:

SMT allows a single physical core to present as multiple logical processors (typically 2) to the operating system. While logical processors share execution resources, they have independent architectural state (registers, instruction pointers).

SMT Scheduling Considerations:

• Logical CPUs on the same core contend for execution units, caches, and memory bandwidth
• Running two compute-intensive threads on SMT siblings provides less than 2x speedup (typically 1.2-1.3x)
• SMT provides significant benefit when one thread frequently stalls (memory access, I/O wait)
• Security considerations: speculative execution vulnerabilities may require SMT disabling

Schedulers must understand the SMT topology to make intelligent decisions—scheduling related threads onto SMT siblings can improve cache utilization, while scheduling competing threads may waste resources.

We have explored Symmetric Multiprocessing from its architectural foundations to its modern implementations. This knowledge provides the essential context for understanding all multi-processor scheduling strategies that follow.

Consolidating Our Understanding:

What's Next:

With SMP fundamentals established, we'll contrast this architecture with Asymmetric Multiprocessing (AMP)—an alternative model where processors have differentiated roles. Understanding both models illuminates why SMP dominates general-purpose computing while AMP persists in specialized domains.