01. Introduction to CPU Scheduling

In any multiprogrammed system, multiple processes and execution threads reside simultaneously in main memory. While modern hardware platforms provide multi-core processors, the number of active, runnable tasks almost always exceeds the number of physical execution units.

The operating system must decide: which process runs next, on which CPU core, for how long, and when it must be forced to yield? This critical allocation policy is governed by the CPU scheduler, while the low-level mechanism that enacts the switch is executed by the dispatcher.

1. Process Behavior: The CPU-I/O Burst Cycle

Nearly all processes alternate between two distinct execution phases in an unending cycle:

• CPU Burst: The processor actively executes machine instructions, arithmetic calculations, memory loads, and data transformations without waiting for external hardware.
• I/O Burst: The process issues a synchronous request to an external device (e.g., secondary storage, network socket, user keyboard, or system timer) and transitions into the Blocked/Waiting state until the hardware device completes the transfer.

The Empirical Burst Distribution

Decades of empirical measurements across production systems demonstrate that CPU burst durations follow a heavy-tailed, hyperexponential frequency distribution:

• The Vast Majority of Bursts are Extremely Short: Over 80% of all CPU bursts in general-purpose workloads last under 4 to 8 milliseconds. These correspond to interactive events, GUI updates, system call parameter validation, and short message passing.
• A Small Minority of Bursts are Very Long: A tiny fraction of CPU bursts last tens, hundreds, or thousands of milliseconds. These belong to compute-heavy workloads such as video rendering, scientific matrix inversion, data compression, or cryptographic hashing.

Compute-Bound vs. I/O-Bound Workloads

An operating system exploits this asymmetry to achieve balanced system utilization:

• I/O-Bound Processes: Spend the majority of their lifespan waiting for I/O operations. They run for mere fractions of a millisecond before issuing a system call and yielding the core. If the scheduler prioritizes I/O-bound tasks immediately upon unblocking, they can issue hardware disk/network requests rapidly and step aside, keeping peripheral hardware pipelines saturated while consuming minimal CPU time.
• Compute-Bound (CPU-Bound) Processes: Spend virtually all their time performing continuous calculations. If an unconstrained compute-bound process is allowed to run indefinitely, it will monopolize the physical CPU core, starving all interactive processes and causing severe system lag.

2. The Scheduler vs. The Dispatcher

In operating system architecture, execution scheduling is cleanly partitioned according to the fundamental computer science principle of separating policy from mechanism:

• Policy (The CPU Scheduler): Determines which task runs next and for how long. It is an algorithmic decision engine that balances competing performance goals (fairness, throughput, latency) by organizing processes across priority queues, computing dynamic decay factors, and maintaining run-time accounting data.
• Mechanism (The Dispatcher): Executes how the selected process is loaded onto the hardware execution pipeline. It is a highly optimized, hardware-dependent assembly-language routine invoked on every context switch to alter CPU register states, switch memory mappings, and drop processor privilege levels.

1. Low-Level Execution Sequence of a Dispatch Cycle

Whenever the scheduler decides to replace Outgoing Process A with Incoming Process B, the dispatcher executes an exacting, deterministic sequence of machine-level operations:

1. Interrupt Trapping & Mode Transition (Ring 3 → Ring 0): The CPU transitions from unprivileged User Mode to supervisor Kernel Mode via a hardware interrupt (e.g., local APIC timer tick) or an explicit software trap (e.g., synchronous syscall instruction). The CPU hardware automatically pushes the User Stack Pointer (RSP), Program Counter (RIP), and Flags register (RFLAGS) onto the process's private kernel stack.
2. Hardware Context Preservation: The kernel pushes all remaining general-purpose registers (RAX, RBX, RCX, RDX, RSI, RDI, RBP, R8–R15) onto the kernel stack, assembling a complete hardware trap frame (struct pt_regs in Linux, KTRAP_FRAME in Windows). The resulting stack pointer is written into Outgoing Task A's Thread Control Block.
3. Task State Accounting & Scheduler Invocation: The kernel dispatcher records the consumed CPU cycles in Task A's execution counter. If Task A blocked on I/O, its state is set to TASK_INTERRUPTIBLE and it is placed into a wait queue. If its quantum expired, its state remains TASK_RUNNING and it is enqueued at the tail of the Ready list. The scheduler then selects Incoming Task B.
4. Virtual Memory Context Switch (MMU CR3 Reloading): If Task B belongs to a different process than Task A, the dispatcher reloads the CPU's CR3 control register (or TTBR0 on ARM) with the physical base address of Task B's page table root:

   /* Low-level x86-64 assembly in kernel dispatcher: */
   movq  %rax, %cr3   /* Loads new page table directory; invalidates non-global TLB entries */

   Note on Thread Switching: If Task A and Task B are two threads within the same process, they share the identical memory descriptor (task->mm). The dispatcher detects this identity and completely bypasses reloading CR3, preserving warm Translation Lookaside Buffer entries.
5. Hardware TLS Segment Register Reconfiguration: The dispatcher updates the architecture-specific segment register base address pointing to the thread's user-mode Thread Control Block (writing to Model-Specific Register IA32_FS_BASE via WRMSR on Linux, or IA32_GS_BASE on Windows).
6. Kernel Stack Pointer Swap (TSS Update): The CPU's stack pointer register (RSP) is updated to point to Incoming Task B's saved kernel stack. Simultaneously, the kernel updates the privileged Task State Segment (TSS) so that future hardware interrupts while Task B runs in user mode will automatically vector to Task B's kernel stack rather than Task A's.
7. Hardware Context Restoration: The dispatcher executes a sequence of POPQ assembly instructions, loading Task B's saved general-purpose registers from its kernel stack back into the silicon register files.
8. Privilege Drop and Instruction Jump (Ring 0 → Ring 3): The dispatcher executes the IRETQ (interrupt return) or SYSRETQ instruction. This atomically restores the user instruction pointer (RIP), user stack pointer (RSP), user execution flags (RFLAGS), and drops the hardware privilege level back to Ring 3. Incoming Task B resumes execution at the exact instruction it was executing when previously suspended.

2. Deconstructing Dispatch Latency: Direct vs. Indirect Costs

The total computational penalty incurred by a dispatch cycle is split between direct hardware overhead and indirect memory hierarchy penalties:

• Direct Dispatch Latency (1 to 3 microseconds): The non-negotiable instruction execution cost of saving registers to the trap frame, updating internal scheduler linked lists, executing the context switch assembly, reloading segment descriptors, and executing the privilege return instruction.
• Indirect Dispatch Latency (The "Invisible Tax", 10 to 50 microseconds): The substantial hardware performance degradation that occurs immediately after Incoming Task B resumes execution:
  • TLB Invalidation: If the switch crossed process boundaries, clearing the Translation Lookaside Buffer forces subsequent memory references to execute expensive 4-level page table walks in main memory (adding ~200 CPU cycles per translation). Modern processors mitigate this using PCID (Process Context Identifiers) on x86 or ASID (Address Space Identifiers) on ARM, tagging TLB lines with process IDs to avoid full flushes.
  • Hardware Cache Eviction (Cache Pollution): As Task B runs, its memory footprints overwrite the L1 Instruction, L1 Data, and L2 caches previously warmed by Task A. Task B suffers a storm of cache misses until its active working set is fetched back from slower L3 cache or DRAM.
  • Branch Target Buffer (BTB) Disruption: The CPU hardware branch predictors must clear and retrain branch history patterns for the new code stream, causing repeated instruction pipeline flushes during the first several thousand instructions.

3. When to Schedule: Trigger Points & Preemption

CPU scheduling decisions arise under four distinct operational events:

1. Running → Waiting (Blocked): The process initiates a blocking operation (e.g., synchronous file I/O, network packet wait, sleep(), or waiting on a semaphore/mutex).
2. Running → Ready: The process is forcibly interrupted while actively executing instructions (e.g., an APIC hardware timer interrupt indicates its time slice has expired, or an external device interrupt unblocks a higher-priority task).
3. Waiting → Ready: An asynchronous hardware event occurs (e.g., disk controller finishes DMA transfer, network packet arrives at the NIC), moving a previously blocked process into the Ready queue.
4. Terminated: The running process completes execution by calling exit() or is aborted by the kernel due to an unhandled exception (e.g., segmentation fault SIGSEGV).

Preemptive vs. Non-Preemptive (Cooperative) Scheduling

• Non-Preemptive (Cooperative) Multitasking: Scheduling occurs only under conditions 1 and 4. Once a process is allocated the CPU, it retains exclusive ownership of the core until it voluntarily yields control—either by blocking on an I/O request or terminating.
  The Fatal Vulnerability: If an application enters a buggy infinite loop (while(1);) or a developer refuses to call cooperative yield routines, the entire operating system and all other applications freeze permanently. Early personal computer operating systems (such as Windows 3.1 and classic Mac OS System 7) relied on cooperative multitasking, leading to frequent system-wide lockups.
• Preemptive Multitasking: Scheduling occurs across all four conditions (1, 2, 3, and 4). The operating system programs a hardware timer interrupt (e.g., the local APIC timer on x86-64) to fire periodically at a fixed frequency (e.g., every 1 ms to 10 ms).
  When the timer interrupt fires, the CPU hardware forcefully suspends user execution, vectors into the kernel interrupt handler in Ring 0, saves the interrupted task's state, and invokes the scheduler. If a task has exhausted its allocated quantum, it is preempted immediately and moved back to the Ready queue. Preemption prevents any single process from monopolizing the hardware.

4. Conflicting Optimization Goals & Metrics

An operating system scheduler operates in an environment of inherent physical constraints and mutually incompatible performance objectives. No single scheduling algorithm can simultaneously maximize raw hardware throughput, eliminate user latency, guarantee absolute fairness, and maintain zero scheduling overhead. Designing or selecting a scheduler requires understanding the formal mathematical metrics that quantify performance and the trade-offs that govern their optimization.

1. Formal Mathematical Scheduling Metrics

To evaluate and compare scheduling algorithms rigorously, operating system architects define precise timing invariants across the lifecycle of a process:

• Turnaround Time (T_turnaround): The total elapsed wall-clock duration from the instant a job is submitted or arrives in the Ready queue (T_arrival) to the exact instant it finishes execution (T_completion):

  Tturnaround = Tcompletion − Tarrival

  Turnaround time represents the user's total elapsed waiting experience in batch environments. It comprises four distinct sub-components:

  Tturnaround = Texec + Twait + Tio + Tdispatch

  where T_exec is total CPU burst time, T_wait is cumulative time spent in the Ready queue, T_io is time spent blocked on peripheral devices, and T_dispatch is cumulative context-switch latency.
• Normalized Turnaround Time / Penalty Ratio (W): Absolute turnaround time is often deceptive because a 10-second turnaround is catastrophic for a job requiring only 1 millisecond of computation, but stellar for a batch simulation requiring 9 seconds. The normalized turnaround time (also called the slowdown or penalty ratio) measures the relative delay imposed by the operating system:

  W = Tturnaround / Texec

  The minimum possible value is 1.0 (indicating the process ran with zero queue delays or context switches). Higher values indicate severe queuing congestion or scheduler starvation.
• Waiting Time (T_wait): The cumulative duration a process spends in the Ready queue waiting to be granted a CPU core. Unlike turnaround time, waiting time explicitly discounts time spent actively executing instructions or waiting for hardware I/O completion:

  Twait = Tturnaround − Texec − Tio

  In purely compute-bound workloads with zero I/O, this simplifies directly to:

  Twait = Tturnaround − Texec

  A scheduler has no control over how long a program must calculate (T_exec) or how long a disk takes to spin (T_io); its sole mathematical objective when optimizing turnaround time is minimizing T_wait.
• Response Time (T_response): In interactive systems, the user does not wait for an entire program to complete before assessing responsiveness. Response time is the duration between a process entering the Ready queue (e.g., when a key is pressed or a packet arrives) and its very first dispatch onto a CPU core:

  Tresponse = Tfirst_dispatch − Tarrival

  While turnaround time governs background batch efficiency, response time dictates the perceptible latency and tactile fluidity of user interfaces.
• System Throughput (X): The number of complete processes or tasks executed per unit time (e.g., jobs per second):

  X = N / Δt

  Throughput depends heavily on average job length and context-switch frequency. If a scheduler spends too much time executing context switches, useful computational throughput drops.
• CPU Utilization (U): The fraction of total time the physical CPU execution units spend executing non-idle user instructions or productive kernel system calls:

  U = (Tbusy / Ttotal) × 100%

  In multi-programmed systems, CPU utilization increases with the degree of multiprogramming n. If the probability that any single process is waiting for I/O is p, the probability that all n processes are simultaneously idle is pⁿ, yielding theoretical processor utilization of:

  U = 1 − pn

• Fairness & Predictability (Variance & Jitter): A scheduler must guarantee comparable treatment for comparable workloads. Beyond average response time, interactive and real-time systems require minimal variance (σ²). A system where response time fluctuates unpredictably between 10 ms and 2,000 ms feels broken to a human user and violates strict deadlines in a real-time system, even if the statistical average is acceptable.

2. Fundamental Architectural Dilemmas & Trade-Offs

Optimizing an operating system scheduler is an exercise in managing engineering tensions along Pareto optimal frontiers:

A. Turnaround Time vs. Response Time

Algorithms that mathematically optimize average turnaround time (such as Shortest Job First / Shortest Remaining Time Next) do so by letting short jobs run to completion while ignoring long jobs. However, if an interactive process arrives while a compute job is underway, non-preemptive turnaround optimizers force the interactive task to wait, severely degrading response time.

Conversely, algorithms designed to minimize response time (such as Round-Robin with tiny time slices) frequently interrupt long jobs to service incoming interactive events. Because every context switch incurs dispatch latency and invalidates CPU cache hierarchies, the total turnaround time for all jobs degrades.

B. System Throughput vs. Latency (The Quantum Sizing Dilemma)

Consider a system where every context switch requires dispatch latency δ. If the scheduler assigns a time quantum of length q, the fraction of CPU time wasted purely on dispatch overhead (α) is:

α = δ / (q + δ)

• Maximizing Throughput (Large q, e.g., q = 200 ms, δ = 1 ms): Overhead α ≈ 0.5%. Almost 99.5% of CPU cycles perform useful application computation. However, interactive response latency degrades to hundreds of milliseconds, causing unacceptable UI stutter.
• Minimizing Latency (Small q, e.g., q = 4 ms, δ = 1 ms): Response time drops to near-imperceptible levels, but overhead α surges to 20%. One-fifth of the entire processor's silicon capacity is lost to context switches, MMU reloading, and cache thrashing.

C. Fairness vs. Prioritization & Starvation

Strict fairness implies that every ready task receives an equal share of CPU cycles (e.g., pure Round-Robin or Generalized Processor Sharing). However, operating systems must enforce real-world urgency:

• A background disk-indexing service should not receive the same execution priority as the interactive display server rendering user keystrokes at 120 frames per second.
• However, introducing strict priority hierarchies immediately creates the risk of starvation: low-priority tasks may sit in the Ready queue indefinitely if higher-priority tasks arrive continuously. Schedulers must compromise strict prioritization through dynamic mechanisms such as aging.

3. Operational Environments & Optimization Target Matrix