CPU Virtualization
Processes, the API to create them, context switching, and the scheduling policies that decide who runs next.
CPU virtualization is how one CPU pretends to be many. The OS gives each process the illusion of a private CPU by time-multiplexing real CPUs across processes — interrupting the running one, saving its state, picking the next one, restoring its state. The cleverness is in the policy (scheduling algorithms) and the speed (context-switch cost).
Most OS interview questions live here. Know the four classic schedulers (FIFO, SJF, STCF, RR) and their metrics (turnaround vs response time), know why MLFQ exists, and know that Linux CFS is a weighted-fair-queue with red-black-tree bookkeeping.
Key concepts
- The process is the unit of virtualization for the CPU
- fork+exec separates 'create' from 'become' — that's the whole UNIX process API
- Context switching costs hundreds of nanoseconds to low microseconds; design code around that
- Scheduling is a policy choice; there is no optimal scheduler across all workloads
- MLFQ approximates SJF without future knowledge — that's the trick
Reference template
// Evaluating a scheduling policy
1. What's the metric? (turnaround? response? fairness? deadline-hit?)
2. What's the workload? (mix of CPU- vs I/O-bound? interactive vs batch?)
3. Does it know job lengths? (SJF needs lengths; MLFQ doesn't)
4. How does it handle I/O? (let I/O-bound jobs keep priority?)
5. Does it scale to N CPUs? (per-CPU queues? load balancing? cache affinity?)Adapt to your problem; the structure is the load-bearing part.
Common pitfalls
- Reaching for SJF when job lengths aren't known — that's the whole reason MLFQ exists
- Treating Round Robin as 'always fair' — time-slice choice is the entire design
- Ignoring I/O — a scheduler that handles only CPU-bound jobs misses the common case
- Underweighting context-switch cost — preempting too often beats no preemption only sometimes
Related topics
Items (7)
- The Process Abstraction
Process state (running / ready / blocked), address space, PCB, and the kernel's view of a running program.
Concept Foundational - Process API — fork, exec, wait
The UNIX trio that creates and controls processes. Why fork+exec is the standard idiom and what dup/pipe add on top.
Building Block Foundational - Context Switching
Saving and restoring CPU state across processes — register sets, kernel stack, the cost paid every preemption.
Building Block Intermediate - CPU Scheduling — FIFO, SJF, STCF, RR
Four classic scheduling disciplines, their turnaround / response-time trade-offs, and where each breaks down.
Building Block Foundational - Multi-Level Feedback Queue (MLFQ)
Adaptive priority queues, priority boosts to prevent starvation, accounting tricks to defeat gaming.
Building Block Intermediate - Lottery Scheduling and Linux CFS
Probabilistic fair-share scheduling, ticket mechanisms, and how CFS uses red-black trees for O(log n) operations.
Building Block Intermediate - Multi-CPU Scheduling
Cache affinity, single-queue vs per-CPU queues, load balancing, and why scaling beyond one core is hard.
Concept Advanced