Context Switching

The context of a running process is everything the CPU needs to resume it later exactly where it left off. This includes the program counter (next instruction to execute), the CPU registers (general purpose, stack pointer, status/flags register), and, for a full process (as opposed to a thread), the memory-management state — page table base register, segment registers, and open file descriptor tables. A context switch is the operation of saving this entire bundle for the currently running execution unit and loading the previously saved bundle of another one, so the CPU can resume it. It is essential to separate two things that are often conflated. A thread switch changes only the CPU-register context (registers, program counter, stack pointer) because threads of the same process share an address space. A process switch additionally changes the memory context — it must reload the page table base register (and, on architectures without tagged TLBs, flush the Translation Lookaside Buffer). This is why switching between two threads of the same process is meaningfully cheaper than switching between two unrelated processes: the address-space-related cost is the dominant, and avoidable, part of the bill. Context switches are always mediated by the kernel and occur only at well-defined trigger points: a hardware interrupt (timer, I/O completion), an internal trap/exception (page fault, illegal instruction), or a system call that blocks (e.g., a `read()` waiting on disk) or explicitly yields the CPU. A process cannot switch itself out of the CPU; it can only request the kernel to do so, directly or indirectly, because the save/restore machinery touches privileged CPU state that user code is not permitted to manipulate. This is the essential link to the Threads and Concurrency model: preemption is what makes concurrent scheduling possible even for CPU-bound code that never voluntarily yields.

A context switch is not a single instruction — it is a sequence of operations spanning hardware and kernel software, executed with interrupts disabled to guarantee atomicity. We can decompose it into five stages.

Stage 1 — Trap into kernel mode. A hardware interrupt or software trap forces the CPU to switch to kernel/supervisor mode and jump to a fixed interrupt-handler address. The hardware itself typically saves a minimal frame (program counter, status register, sometimes the stack pointer) onto the kernel stack, because this much must happen before any software runs.

Stage 2 — Save the full context of the current process. The interrupt handler (or a scheduler routine it calls) saves the remaining general-purpose registers into the outgoing process's PCB, extending the minimal hardware-saved frame into a complete snapshot.

Stage 3 — Kernel-mode bookkeeping and scheduling decision. The kernel updates the process state field in the PCB (e.g., `RUNNING → READY` or `RUNNING → WAITING`), inserts the PCB into the appropriate scheduler queue, and invokes the scheduler to pick the next process to run. (Which policy it uses is the subject of CPU Scheduling Fundamentals; the switch mechanism itself is policy-agnostic.)

Stage 4 — Restore the context of the chosen process. The kernel loads the general-purpose registers from the incoming process's PCB, and — if it is a different address space — reloads the page-table base register (e.g., `CR3` on x86, or the ASID/page-table pointer on ARM), invalidating stale TLB entries as required.

Stage 5 — Return from trap. A special return-from-interrupt instruction restores the program counter and status register from the (now newly loaded) saved frame and drops back to user mode, resuming execution of the new process exactly at its saved instruction. ``` // Executed with interrupts disabled — must be atomic w.r.t. further interrupts function CONTEXT_SWITCH(old_pcb, new_pcb): // --- Stage 2: save outgoing context --- old_pcb.pc <- CPU.program_counter old_pcb.regs <- CPU.general_registers old_pcb.sp <- CPU.stack_pointer old_pcb.status_reg <- CPU.flags // --- Stage 3: bookkeeping --- old_pcb.state <- READY or WAITING // caller decides which enqueue(old_pcb, ready_queue_or_wait_queue) new_pcb <- scheduler_pick_next() // policy defined elsewhere new_pcb.state <- RUNNING // --- Stage 4: restore incoming context --- if old_pcb.address_space != new_pcb.address_space: CPU.page_table_base <- new_pcb.page_table_ptr flush_or_tag_TLB(new_pcb.asid) CPU.general_registers <- new_pcb.regs CPU.stack_pointer <- new_pcb.sp CPU.flags <- new_pcb.status_reg CPU.program_counter <- new_pcb.pc // committed on IRET/ERET return // hardware "return-from-interrupt" resumes new_pcb in user mode ``` The pseudocode makes explicit the invariant that a correct implementation must preserve: every bit of mutable CPU state that a running program can observe must be saved before it is overwritten, and restored before control returns to user mode. Miss one register, and the resumed process silently corrupts its own computation — a bug class that is notoriously hard to reproduce because it depends on exactly which process happened to run next.

Time complexity. A context switch is O(1) in the number of processes: it saves and restores a fixed-size register set (independent of how many other processes exist), so the direct save/restore work does not grow with system load. The scheduling decision that picks the next process, however, may cost more depending on the scheduler's data structure — O(1) for a simple ready queue, O(log n) for a priority heap, O(1) amortized for a red-black-tree-based scheduler with cached leftmost pointer (as in CFS-style designs). The switch mechanism itself is therefore cheap and constant; what varies is the policy layer riding on top of it, which is the concern of CPU Scheduling Fundamentals. The real cost, though, is not the register save/restore — it is indirect cost, and this is where honesty about "complexity" must go beyond asymptotic notation: 1. Mode-switch overhead: trapping into the kernel and back, typically hundreds of cycles. 2. TLB flush / reload: if the new process has a different address space and the hardware lacks tagged TLBs (ASIDs), every TLB entry must be invalidated, and the first memory accesses of the new process all take TLB-miss penalties — page-table walks costing tens to hundreds of cycles each. 3. Cache pollution: the outgoing process's working set in L1/L2/L3 cache is evicted by the incoming process's accesses, so the new process runs at "cold cache" speed for a while — this can dominate total cost, often being larger than the raw register-save time by an order of magnitude. 4. Pipeline/branch-predictor state loss: modern superscalar CPUs lose speculative state and branch history across a switch, incurring further stalls. A widely used empirical figure: raw register save/restore takes on the order of 1–5 microseconds on commodity hardware, but the effective cost including cache/TLB re-warming can be several times higher, and grows with the memory footprint of the processes involved. This is why the space complexity matters too: the PCB itself is O(1) additional space per process (a fixed-size record), but the transient cost of "cold" caches is proportional to the working set size being displaced — not a fixed constant.

Correctness argument. The invariant that must hold before and after any switch is: > State-preservation invariant. For any process P, the CPU-visible state (registers, PC, flags, and — for process switches — address mapping) recorded in P's PCB at the moment it is switched out is exactly sufficient to resume P's execution as if it had never stopped. The proof sketch is by construction: the hardware trap mechanism guarantees the PC and flags at the exact instruction boundary are captured atomically (this is a hardware contract — traps occur only at instruction boundaries, never mid-instruction), and the kernel save routine is written to touch every remaining architecturally-visible register exactly once, with interrupts disabled so no nested interrupt can corrupt the save in progress. Because the save is total (covers the full visible state) and atomic (no partial overwrite is observable), replaying it exactly reverses it: restoring the saved values before returning to user mode is bit-for-bit equivalent to never having left. The only way this invariant breaks is an implementation bug — e.g., forgetting a callee-saved register, or a race where an interrupt is re-enabled before the restore completes — both are classic sources of real kernel bugs, not flaws in the concept itself.

Tradeoffs. Faster switching (smaller saved context, e.g., switching only among threads of one process) buys responsiveness but the OS must still eventually pay full process-switch cost when scheduling across security/address-space boundaries. Reducing switch frequency (longer time slices) amortizes overhead but increases response latency for interactive workloads — a tension that CPU Scheduling Fundamentals resolves differently for throughput-oriented versus latency-oriented policies.

Consider two processes, P1 (a text editor waiting on keyboard input) and P2 (a CPU-bound compiler), both runnable on a single-core machine with a 10 ms timer tick. Trace the events:

Two things this trace makes concrete. First, at t=3ms, the switch is triggered by a blocking system call, not a timer — context switches are not solely a scheduling-tick phenomenon. Second, at t=23ms, P1 resumes at exactly `0x4018`, the instruction right after the trapping `read()` call, with its stack pointer and registers bit-identical to what they were at t=3ms — this is the state-preservation invariant holding in practice, twenty milliseconds and one full compiler run later. If P1 and P2 shared the same address space (i.e., were threads, not processes), the switch at t=23ms would skip the page-table-base reload and TLB invalidation entirely — the same register save/restore logic runs, but stage 4's address-space branch is skipped, saving the TLB-refill penalty. This is precisely why thread-based concurrency inside one process is cheaper than process-based concurrency, even though the trap-and-restore skeleton is identical.

Context switching as a concept emerged directly from the shift away from single-program batch computing toward multiprogramming, where the whole point was to keep the CPU busy while one job waited on slow I/O.

Every general-purpose operating system kernel — Linux, Windows NT, macOS/XNU, the BSDs — implements a context-switch routine as one of its most performance-scrutinized pieces of assembly and C code, because it runs millions of times per second across a datacenter fleet. Real-time operating systems (FreeRTOS, VxWorks) are judged partly on their worst-case context-switch latency, a headline number in embedded and aerospace systems where missing a deadline is a safety failure. Hypervisors (KVM, Xen, Hyper-V) perform an even heavier-weight version — the VM exit/entry — which saves and restores not just process context but entire virtual-CPU state, making context-switch cost a first-order concern in cloud infrastructure billing and density planning. Modern language runtimes with user-level "green threads" or coroutines (Go's goroutines, Erlang processes) exist specifically to dodge kernel context-switch overhead by implementing cheap, user-space stack switches — a direct engineering response to the cost analyzed in this article. Understanding this mechanism is the necessary foundation for CPU Scheduling Fundamentals, where scheduling policies must be designed around the fact that every decision to switch costs real, non-negotiable time.

Ask the tutor: How does hardware support like tagged TLBs (ASIDs) actually change the steps of the context-switch pseudocode above?