CSS Optional — Paper-II, Section-A · P-II.III.VI · Second-highest-yield numerical subtopic after Deadlocks — expect page-replacement, TLB, or multi-level page-table arithmetic almost every year.
Virtual memory gives each process the illusion of a large, private, contiguous address space independent of installed RAM, by using disk (the swap area) as an extension of memory. Under demand paging, a page is loaded into a physical frame only when actually referenced; if a process accesses a page not currently resident, a page fault occurs: the OS traps, locates the page on disk, loads it into a free (or newly-evicted) frame, updates the page table, and resumes the process.
When memory is full and a new page must be brought in, a victim page must be evicted.
| Algorithm | Rule | Note |
|---|---|---|
| FIFO | Evict the page that has been in memory longest | Simple but can suffer <b>Belady's Anomaly</b> — more frames can paradoxically cause MORE faults |
| Optimal (OPT/MIN) | Evict the page that will not be used for the longest time in the FUTURE | Theoretical benchmark only — needs knowledge of the future, impossible in a live system; gives the fewest possible faults |
| LRU | Evict the page not used for the longest time in the PAST | Practical approximation of Optimal (temporal-locality heuristic); never suffers Belady's Anomaly; needs timestamps/a stack to implement exactly, so the Clock/Second-Chance algorithm approximates it cheaply |
📐 FIFO/Optimal/LRU compared on one reference string, plus Belady's Anomaly, Clock, and frame-allocation numericals:
Page Replacement Algorithms — Deep Dive & Solved Numericals
If the degree of multiprogramming is pushed too high, each process gets too few frames, so it page-faults almost continuously — the CPU spends nearly all its time swapping pages in/out and almost none executing real instructions. This collapse in useful throughput is thrashing, and it is precisely why "job size very low" or "page size very small" scenarios need careful trade-off analysis: smaller time slices/pages increase overhead relative to useful work.
The TLB is a small, fast associative cache inside the MMU holding recently used virtual-page → physical-frame translations, avoiding a full page-table walk on every memory access. On a TLB hit, translation is near-instant; on a TLB miss, the full (slower) page-table lookup happens, and the TLB is updated.
A single flat page table for a 32-bit address space with 4 KB pages needs 2^20 entries — wastefully large if most of a process's address space is unused. Multi-level (hierarchical) paging splits the VPN into multiple index fields, each indexing into a smaller table, and unused branches simply never get a second-level table allocated — trading one extra memory access per additional level for large space savings (a TLB is what makes this overhead acceptable in practice).