CHEATSHEETSTOOLSBOOKSHELFABOUT中文

Process Scheduling & CPU Virtualization

CPU virtualization is the operating system abstraction that enables hundreds of threads and processes to share physical processing cores seamlessly. The kernel scheduler determines which thread executes on which CPU core, for how long, and under what conditions it yields control, directly governing system responsiveness, throughput, energy efficiency, and deterministic latency.

+-------------------------------------------------------------+
|                      Ready Threads                          |
|   [ Thread A (QoS: Interactive) ]  [ Thread B (Batch) ]     |
+-------------------------------------------------------------+
                               |
                       OS CPU Scheduler
           (CFS / EEVDF / MLFQ / QoS / Fixed-Priority)
                               |
                               v
+-------------------------------------------------------------+
|                     Physical CPU Cores                      |
|  [ Core 0: Thread A ]    [ Core 1: Idle ]    [ Core 2: ... ]|
+-------------------------------------------------------------+

The Multitasking Spectrum: Preemptive vs Cooperative

Operating system scheduling models fall into two fundamental paradigms:

  1. Cooperative Multitasking:

    • Running threads retain CPU ownership until they voluntarily yield execution (yield(), sched_yield()) or block on synchronous I/O.
    • Historical context: Classic Mac OS (System 7–9), Windows 3.1, and Go goroutine runtimes (prior to asynchronous preemption in Go 1.14).
    • Vulnerability: A single uncooperative loop (while (1) {}) starves all other tasks and freezes the entire OS.

  2. Preemptive Multitasking:

    • The operating system interrupts running threads asynchronously using hardware timer interrupts (e.g. Local APIC timer, ARM Generic Timer) without requiring application cooperation.
    • All modern general-purpose kernels (Linux, Windows NT, macOS XNU) and commercial RTOSes enforce preemptive scheduling.

The Anatomy of a Hardware Context Switch

A context switch is the operation of halting the currently executing thread, preserving its architectural CPU state, and restoring the state of a previously halted thread.

Executing Thread A (User Mode)
        |
   Timer Interrupt (Local APIC) / Syscall / Blocking I/O
        |
        v
Privilege Transition to Ring 0 (Kernel Mode)
        |
1. Save Architectural Registers on Kernel Stack (RAX, RBX, RCX, RDX, RSI, RDI, R8-R15)
2. Save Program Counter (RIP), Stack Pointer (RSP), and Processor Flags (RFLAGS)
3. Save Extended State (FPU, AVX-512, SSE via XSAVEOPT / XRSTOR)
4. Update Thread Control Block (task_struct / _ETHREAD / thread_t)
        |
        v
Scheduler Decision (Pick next runnable Thread B)
        |
        v
5. Switch Virtual Address Space (load CR3 with Thread B's page table, if different process)
6. Switch Kernel Stack Pointer (load RSP0 in Task State Segment TSS)
7. Restore Thread B Extended State (XRSTOR)
8. Restore Architectural General-Purpose Registers
        |
        v
IRETQ / SYSRET -> Resume Thread B in User Mode (Ring 3)

Context Switch Overhead Costs

The direct execution cost of executing instructions to swap register sets is relatively small (~1–2 microseconds). The primary performance penalty is indirect hardware cache pollution:

  • L1/L2 Instruction & Data Cache Eviction: The new thread's instructions and working set overwrite the previous thread's cached data.
  • Branch Target Buffer (BTB) & Branch Predictor Invalidation: Cold branch prediction state leads to misprediction pipeline bubbles.
  • TLB Invalidation: If switching across processes without hardware PCID/ASID support, reloading CR3 flushes all non-global page translations, forcing hundreds of memory accesses on subsequent instruction fetches.

Production Scheduling Paradigms Across Kernels

Different operating systems deploy radically different scheduling algorithms optimized for their primary workload domains.

1. Linux: CFS and EEVDF

Linux 2.6.23 introduced the Completely Fair Scheduler (CFS), designed by Ingo Molnar to model an "ideal multi-tasking CPU" on real hardware:

  • Virtual Runtime (vruntime): Every task tracks the exact amount of CPU execution time it has consumed, scaled inversely by its nice level (-20 to +19): $$\text{vruntime} \mathrel{+}= \Delta \text{exec_time} \times \frac{\text{NICE_0_LOAD}}{\text{task_weight}}$$
  • Red-Black Tree Hierarchy: CFS maintained runnable tasks ordered by vruntime in a self-balancing red-black tree (rb_node). The scheduler picked the leftmost node (the task that had received the least virtual CPU time).

Transition to EEVDF (Linux 6.6+): Peter Zijlstra replaced CFS with EEVDF (Earliest Eligible Virtual Deadline First), based on Peter Hoon's 1995 scheduling theory:

  • CFS struggled with audio/gaming latency because vruntime prioritized long-term throughput over short-term response deadlines.
  • EEVDF introduces two parameters for each task: Eligibility Time (when a task is allowed to run without cheating fair share) and Virtual Deadline (the time by which its allocated time slice must complete).
  • EEVDF schedules the task with the earliest deadline among eligible tasks, dramatically improving real-time desktop responsiveness while preserving strict fairness.

2. Windows NT: Multilevel Feedback Queue (MLFQ)

The Windows NT Executive scheduler employs a priority-driven, preemptive Multilevel Feedback Queue with 32 priority levels (0 to 31):

  • Levels 16–31 (Real-Time Priorities): Fixed priorities. The highest-priority thread runs uninterrupted until it yields or blocks. No automatic adjustment occurs.
  • Levels 1–15 (Dynamic Priorities): Priorities fluctuate dynamically based on thread behavior and user interaction:
    • I/O Completion Boost: When a thread completes a blocking I/O operation (e.g. disk or network read), the kernel grants a temporary priority boost (e.g. +1 for disk, +6 for network/audio) to process data promptly.
    • Foreground Window Boost: The active GUI process window currently focused by the user receives priority boosts to ensure zero perceptual interface lag.
    • Anti-Starvation Balance Set Manager: Scans thread runqueues every second; if a low-priority thread has been ready but starved of CPU time for over 4 seconds, the kernel temporarily boosts it to priority 15 with double quantum before letting it decay back to its baseline.

3. macOS & Darwin (XNU): QoS and Asymmetric Core Scheduling

Apple's XNU kernel pairs BSD POSIX scheduling with Mach thread abstractions, integrated with Grand Central Dispatch (GCD) and hardware topology:

  • Quality of Service (QoS) Classes:
    1. UserInteractive: Highest priority; main event loop, UI rendering, animations (allocates 100% CPU capacity without throttling).
    2. UserInitiated: Asynchronous tasks directly requested by the user requiring immediate results (e.g. opening a document).
    3. Default: Standard application logic when no explicit QoS is set.
    4. Utility: Progress-based tasks (downloading files, data exports) where completion is user-visible but not blocking.
    5. Background: Maintenance, indexing, and backups (runs with heavy power and thermal throttling).
  • Asymmetric BIG.little Scheduling (Apple Silicon):
    • The XNU scheduler is tightly coupled with hardware Performance (P) and Efficiency (E) core clusters.
    • Threads classified as Background or Utility are pinned exclusively to E-cores, keeping P-cores powered down to preserve battery life.
    • As soon as a user touches the trackpad or types, the window server and compositor threads run instantly on P-cores with maximum frequency scaling.

4. Real-Time Operating Systems (RTOS): Deterministic Bounded Latency

Real-time kernels (FreeRTOS, QNX Neutrino, VxWorks, Zephyr) discard fairness entirely in favor of guaranteed upper bounds on response latency (deadlines):

  • Fixed Priority Preemptive Scheduling (FPPS): The scheduler always selects the runnable task with the highest numeric priority.
  • Rate Monotonic Scheduling (RMS): Static priority assignment where tasks with the shortest recurring period receive the highest priority.
  • Earliest Deadline First (EDF): Dynamic priority assignment where tasks whose absolute completion deadline is closest in time run first.
  • Priority Inversion & Priority Inheritance Protocol (PIP): When a low-priority task holds a shared resource (mutex) needed by a high-priority task, an intermediate task can preempt the low-priority task, causing the high-priority task to miss its deadline (the infamous Mars Pathfinder bug). Real-time kernels resolve this by temporarily elevating the priority of the lock-holding task to match the highest waiting task until the lock is released.

Multiprocessor & Multicore Scheduling

Scheduling on modern 32-core to 128-core symmetrical multiprocessor (SMP) systems introduces hardware topology constraints:

+--------------------------- NUMA Node 0 ---------------------------+
|  [ Core 0 (L1/L2) ]  [ Core 1 (L1/L2) ] ... Shared L3 Cache (32MB) |
|  Local Memory Controller -> Fast Local DRAM Access (~60 ns)       |
+-------------------------------------------------------------------+
                                ^
                                | Interconnect (UPI / Infinity Fabric)
                                v
+--------------------------- NUMA Node 1 ---------------------------+
|  [ Core 8 (L1/L2) ]  [ Core 9 (L1/L2) ] ... Shared L3 Cache (32MB) |
|  Remote Memory Access -> Latency Penalty (~120 ns)                |
+-------------------------------------------------------------------+

1. Per-CPU Runqueues vs Global Runqueue

Early SMP operating systems maintained a single global runqueue guarded by a single kernel spinlock. As core counts climbed, lock contention crippled performance.

Modern kernels allocate independent per-CPU runqueues:

  • Each physical core locks only its own local runqueue.
  • Work Stealing / Load Balancing: If a core's runqueue becomes empty, it enters an idle state or scans neighboring cores' runqueues, "stealing" runnable tasks to balance workloads across CPUs.

2. NUMA-Aware Scheduling (Non-Uniform Memory Access)

In multi-socket servers and chiplet architectures (AMD EPYC, Intel Xeon, Apple M-Max/Ultra), access latency to local memory is significantly faster than to memory attached to another socket:

  • Processor Affinity (sched_setaffinity): Schedulers prefer to keep a thread running on the same CPU core or the same NUMA node where its memory pages are physically allocated.
  • Migrating a thread across NUMA nodes forces cache-invalidation penalties and remote DRAM access latency bottlenecks.

Comparative Overview: Scheduling Across Operating Systems

Metric / Feature Linux (EEVDF) Windows NT (MLFQ) macOS (XNU / QoS) RTOS (FreeRTOS / QNX)
Primary Goal Proportional fairness + low-latency deadline matching Desktop UI responsiveness & interactive boosting Energy efficiency & user perception QoS Deterministic hard deadline guarantees
Data Structure Per-CPU Red-black tree / priority min-heap Per-CPU 32-level priority array / bitmap Multi-tier Mach runqueues per QoS bucket Priority-indexed linked lists / bitmapped ready-list
Preemption Granularity Timer tick + dynamic tickless (NO_HZ_FULL) Dynamic timer resolution (1 ms–15.6 ms) Tickless dynamic deadline timer Configurable tick rate (typically 1 ms or microsecond)
Priority Inversion Defense Priority Inheritance Mutexes (rt_mutex) Priority boosting via Balance Set Manager Priority donation across Mach ports / GCD queues Strict Priority Inheritance Protocol (PIP) / PCP
Hardware Topology NUMA domain balancing, Energy-Aware Scheduling (EAS) Processor groups (64+ cores), NUMA nodes Asymmetric BIG.little (P-core vs E-core) pinning Homogeneous or single-core optimized
UNIX ClassicSponsored
The Design of the UNIX Operating System
Kernel Architecture
The Design of the UNIX Operating System
By Maurice J. BachView on Amazon
Operating Systems
OS Case Studies