Timesharing versus spacesharing, cache affinity retention, two-dimensional gang scheduling, and Simultaneous Multithreading (SMT) core-scheduling security boundaries.
Timesharing, Spacesharing & Affinity Scheduling
On a uniprocessor system, scheduling is a single-dimensional problem: the kernel determines which thread runs next on the solitary CPU. On a multiprocessor, scheduling becomes a multidimensional optimization problem: the operating system must determine both which thread to execute and which physical CPU core should execute it.
1. Timesharing vs. Spacesharing
The operating system must balance resource utilization against inter-thread synchronization overhead:
Timesharing Across Cores: Threads share CPU cores over discrete time slices (quanta). Each core independently selects runnable threads from a per-core or shared run queue, preempting them when their time quantum expires. Timesharing maximizes overall system utilization and interactive responsiveness when running independent, compute-bound jobs.
Spacesharing Across Partitions: Physical cores are partitioned among parallel applications. If a parallel scientific job requests 4 cores, the kernel assigns 4 dedicated CPUs to that job until completion. No preemption or timesharing occurs on those cores. Spacesharing eliminates synchronization latency and context-switching overhead, but risks core starvation if threads block on external I/O.
Scheduling Dimension
Timesharing Across Cores
Spacesharing Partitions
Core Assignment
Dynamic; threads move between cores across quanta.
Static; dedicated cores bound for job duration.
Preemption Overhead
High; regular context switches and cache evictions.
Zero; applications run uninterrupted to completion.
Synchronization Penalty
High risk of spinlock stalls if lock holders are preempted.
Zero preemption stalls; spinlocks resolve in nanoseconds.
System Utilization
High; idle cores immediately pick up waiting threads.
Lower; cores sit idle if a thread blocks on I/O.
2. Cache Warmth & The Migration Penalty
When thread T executes on Core 0, it loads its working set (data structures, stack frames, loop variables) into Core 0's private L1 and L2 caches. This is called a warm cache.
If the operating system preempts T and subsequently dispatches it to Core 1 to balance run queues:
Cold Cache Misses: Core 1's L1/L2 caches contain none of T's data. Every instruction fetch and memory load incurs a cache miss, stalling the execution pipeline while data is fetched from shared L3 or physical DRAM (~40–80 ns vs. ~1 ns for L1).
Coherence Invalidation Traffic: If T mutates data on Core 1 that was left dirty in Core 0's cache, the hardware cache coherence protocol must broadcast invalidation messages, invalidating lines across the interconnect and adding bus contention.
3. Soft vs. Hard Affinity Scheduling
To preserve cache warmth without causing CPU starvation, kernels implement Affinity Scheduling:
Soft Affinity: The scheduler prefers to reschedule a thread on the physical core it last occupied. If that core is busy, the scheduler delays migration briefly (an affinity grace period). Only when another core becomes idle and load imbalance exceeds a threshold does work stealing migrate the thread.
Hard Affinity: The application or administrator explicitly binds a thread to a specific set of cores using system calls (e.g., Linux sched_setaffinity() or Windows SetThreadAffinityMask()). The scheduler is forbidden from migrating the thread, guaranteeing deterministic cache locality at the cost of potential core underutilization.
Guided Walkthrough: Cache Warmth & Affinity SchedulingStage 1 of 3
Concept Overview: When an operating system scheduler migrates a thread between cores, it discards the hardware benefits of cache locality. This walkthrough visually demonstrates the physical contents of private L1/L2 caches: observe how executing a thread on a warm core achieves near-instant memory hits, how thread migration induces a severe cold-cache penalty, and how affinity scheduling preserves execution throughput.
Action Required: Click 'Execute Stage 1: Thread A on Warm Core 0' below.
Watch Thread A execute on Core 0. Notice that its working set lines (X, Y, Z) reside inside Core 0's private L1/L2 cache, delivering 100% cache hits and optimal execution latency (~1.2 ns).
Thread Location: Core 0 (Warm)
Memory Hit Latency: ~1.2 ns (L1 Hit)
Interconnect Traffic: None (Local)
Affinity Mode: Soft Affinity
-- Stage 1 ready: Thread A running on warm Core 0 with optimal cache hit ratios --
Two-Dimensional Gang Scheduling
When parallel applications consist of multiple cooperating threads that synchronize frequently using spinlocks, barriers, or message passing, independent thread timesharing causes severe performance collapse due to desynchronization delays.
The Preemption Synchronization Hazard: Suppose Thread 0 sends a request to Thread 1 and spins waiting for an immediate acknowledgment. If Thread 1 is scheduled on another core, it replies in nanoseconds. However, if the scheduler independently preempted Thread 1 to run an unrelated task, Thread 0 spins wasted CPU cycles across its entire 10 ms time quantum waiting for Thread 1 to be rescheduled.
Pioneered by John Ousterhout (1982), Gang Scheduling eliminates this penalty through three invariants:
Groups of related, communicating threads form a single gang.
All members of a gang are allocated and scheduled simultaneously on distinct physical cores.
All members of a gang begin and terminate their time quanta synchronously in lockstep.
Guided Walkthrough: Timesharing Desynchronization vs. Gang SchedulingStage 1 of 3
Concept Overview: This walkthrough visually demonstrates the two-dimensional scheduling matrix (Cores × Time Quanta). Observe what happens when communicating threads are scheduled out of sync versus when they are dispatched synchronously as a coordinated gang.
Watch 4 CPUs independently schedule threads from Gang A (T0, T1, T2, T3). Notice that CPU 0 runs Gang A (T0) while CPU 1 runs an unrelated task. When T0 sends a message to T1, it wastes its quantum spinning because T1 is not running.
Scheduling Policy: Uncoordinated Timesharing
Inter-Thread Sync: Severe Spinlock Stalls
CPU Efficiency: Low (~35% Waste)
Lockstep Status: Out of Phase
-- Uncoordinated timesharing active. Notice that communicating threads are scheduled out of phase --
Scheduling for Security: SMT & Core Scheduling
Modern processors routinely employ Simultaneous Multithreading (SMT) (e.g., Intel Hyper-Threading, AMD SMT), where a single physical execution core presents two or more architectural execution contexts (hardware threads) to the operating system.
While SMT boosts throughput by allowing hardware threads to share execution units during memory stall cycles, sibling threads share critical microarchitectural resources:
L1 Data & Instruction Caches
Translation Lookaside Buffers (TLB)
Branch Target Buffers (BTB) & Branch Prediction Units
Microarchitectural Fill Buffers (MDS / RIDL / Fallout attacks)
If the kernel schedules an untrusted container or user process on Hardware Thread 0 while a sensitive cryptographic worker or kernel service executes on Hardware Thread 1 of the exact same physical core, the untrusted thread can measure cache eviction timings and transient execution side channels to reconstruct secret cryptographic keys.
2. Core Scheduling (Co-Scheduling) Mitigations
To prevent hyperthread side-channel leaks without completely disabling SMT in the BIOS (which sacrifices 20–30% compute capacity), modern operating systems (Linux and Windows) implement Core Scheduling:
The Co-Scheduling Invariant: Sibling hardware threads belonging to the same physical core must only execute tasks belonging to the exact same security domain (cookie/tag). If an isolated task is scheduled on Thread 0, and no sibling task from that same trust domain is runnable, Thread 1 is forced to execute an idle halt loop.
Guided Walkthrough: SMT Side-Channel Exposure vs. Core SchedulingStage 1 of 2
Concept Overview: This walkthrough visually demonstrates hardware thread pairing on a dual-thread SMT core. Observe how naive schedulers expose cryptographic secrets across shared L1 caches, and how Core Scheduling isolates sibling threads to maintain security.
Watch an untrusted guest container scheduled on Thread 1 of Physical Core 0 while an SSL/TLS cryptographic worker executes on Thread 0. Notice that both threads share the L1 cache, allowing MDS side-channel leaks.