Virtual memory lets a process use an address space larger than physical RAM by keeping only the actively used pages in memory and the rest on disk. It is what lets you run a 4 GB program on a 2 GB machine. This article covers demand paging, the page-fault path, the TLB that makes translation fast, and the thrashing failure mode.
Demand paging
Rather than loading an entire program at start, demand paging loads a page only when it is first referenced. Pages begin marked not present in the page table; the first touch triggers a page fault that pulls the page from disk (the executable or the swap area). This makes startup fast and memory usage proportional to what the program actually touches — the basis for lazy loading and memory-mapped files.
The page-fault path
When the CPU accesses a page whose PTE has the present bit clear, the MMU raises a fault trap and the OS handles it:
- Trap to the kernel; save the faulting instruction's state.
- Validate the address against the process's memory regions. An access outside any valid region is a genuine fault (segmentation fault / SIGSEGV). A valid-but-not-resident page continues.
- Find a free frame. If none is free, run the page-replacement algorithm to evict a victim (writing it back first if dirty).
- Schedule the disk read to load the page into the frame; the process blocks and the CPU runs someone else.
- Update the PTE (present bit, frame number) when the read completes.
- Restart the faulting instruction — now it succeeds transparently.
A minor (soft) fault is satisfied without disk I/O (the page is already in memory, e.g., in the free list or shared by another process); a major (hard) fault requires a disk read and is far slower.
The TLB: making translation fast
Every memory access needs a virtual-to-physical translation, and the page table lives in memory. Walking a multilevel page table would add several memory accesses to every load and store. The Translation Lookaside Buffer (TLB) is a small, fast, fully-associative cache (typically 64–1024 entries) inside the MMU that caches recent page-number → frame-number translations.
- TLB hit: translation comes straight from the TLB — a fraction of a nanosecond.
- TLB miss: the hardware (or OS) walks the page table, then loads the result into the TLB.
Effective access time (worked example)
Let TLB lookup add negligible time, main-memory access = 100 ns, and the TLB hit ratio = 90%. On a hit, the access costs one memory reference (100 ns, translation already known). On a miss, you pay one reference to walk the table plus one to fetch the data (200 ns):
EAT = 0.90 * 100 + 0.10 * 200 = 90 + 20 = 110 ns
A 90% hit ratio costs only 10% overhead versus ideal — which is why even a small TLB is transformative. Raise the hit ratio to 99% and EAT drops to 0.99*100 + 0.01*200 = 101 ns.
TLB and context switches
TLB entries belong to a specific address space, so a naive context switch must flush the TLB, causing a burst of misses in the new process. Modern CPUs tag entries with an address-space identifier (ASID/PCID) so entries from multiple processes coexist and no flush is needed — one reason process switches got cheaper.
Thrashing
Thrashing is the pathological state where a system spends more time paging than computing. It happens when the combined working sets of running processes exceed physical memory: every process constantly faults, evicting a page another process is about to need, which faults in turn.
The signature is brutal: as the multiprogramming degree rises, CPU utilization climbs, then collapses sharply once thrashing begins — the CPU sits idle waiting on disk while the paging device saturates.
The working-set model
The working set W(t, Δ) is the set of pages a process referenced in the last Δ time units — its current locality. The OS estimates each process's working-set size and ensures the sum fits in RAM. If demand exceeds supply, it suspends (swaps out) a whole process rather than letting everyone thrash. This is load control.
Page-fault frequency (PFF)
A more direct control: monitor each process's page-fault rate. If it exceeds an upper threshold, give the process more frames; if it drops below a lower threshold, reclaim frames. Keeping every process's fault rate in a target band prevents thrashing without computing working sets explicitly.
Related mechanisms
- Copy-on-write: after
fork(), parent and child share pages read-only; a write triggers a fault that duplicates just that page — pairs naturally with demand paging. - Memory-mapped files (
mmap): map a file into the address space and let the page-fault mechanism load file blocks on demand, so file I/O becomes ordinary memory access. - Swapping vs paging: classic swapping moves an entire process between memory and disk; paging moves individual pages. Modern systems page and reserve full-process swap-out for load control.
- Prepaging: load several pages you expect to need soon (spatial locality) to amortize disk latency instead of faulting one page at a time.
Common follow-ups and gotchas
- "What is the difference between a page fault and a segmentation fault?" A page fault is normal — the page is valid but not resident, and the OS loads it. A segmentation fault is an access to an address with no valid mapping; the process is signaled and usually killed.
- "Why is the TLB so important?" Without it, every logical access would require extra memory accesses to walk the page table, roughly doubling or worse the cost of every load/store.
- Thrashing is a memory problem, not a CPU problem — adding CPU makes it worse by admitting more processes. The fixes are reducing multiprogramming, adding RAM, or better locality.
- Gotcha: a high fault rate right after startup is expected (cold cache / demand loading); sustained high fault rate with low CPU utilization is thrashing.