31. Virtual Memory & Paging

Why it exists: without it, two programs using the same address would corrupt each other, a program larger than RAM couldn't run, and every program would need to know exact physical addresses. Virtual memory gives every process its own private address space, translated behind the scenes.

Address translation:

Virtual Address = [ Page Number | Offset ]
1. Extract page number
2. Look up page table → frame number
3. Physical Address = Frame Number + Offset

Page fault sequence: CPU accesses a virtual address not in RAM → page fault (hardware interrupt) → OS finds the page on disk (swap) → loads it into a free frame → updates the page table (valid bit = true) → restarts the instruction → process continues, unaware anything happened.

Virtual address space layout (low → high): text segment → data segment (initialized globals) → BSS (uninitialized globals) → heap (grows up) → ... → stack (grows down) → kernel space.

Page Replacement Algorithms:

• FIFO: evict the oldest page. Simple but can evict a heavily used page.
• LRU: evict the page unused for longest. Smart, approximates optimal, expensive to implement perfectly.
• Optimal: evict the page not needed for the longest time in the future. Impossible in practice — used only as a theoretical benchmark.
• Clock: a practical LRU approximation — each page has a reference bit; sweep a "clock hand," clearing bits, evicting the first page found with bit = 0. Used in Linux.

Belady's Anomaly (interview gotcha): you'd expect that giving a process more physical frames always reduces or holds steady its page-fault count. FIFO can violate this — for certain reference strings, adding more frames actually increases the number of page faults. LRU and Optimal do not exhibit this anomaly (they belong to the class of "stack algorithms," which are provably free of it). This is the classic follow-up question after "explain page replacement algorithms."

Thrashing: when the OS spends more time swapping pages than running processes — too many processes, too little RAM each, constant page faults, CPU barely does real work. Fixed by reducing the degree of multiprogramming, adding RAM, or using the working-set model.

Key numbers: page size ~4KB; TLB entries 64–1024; TLB hit rate ~99%; RAM access ~100ns; page fault costs milliseconds — roughly 10,000× slower than a normal memory access.

---