7.1 Demand Paging
Virtual Memory decouples the logical address space seen by user programs from physical RAM. In Demand Paging, pages are only loaded into memory when they are explicitly referenced during execution ("lazy swapper"), reducing memory pressure and start-up latencies.
Figure 7.1: Complete sequence of events in handling a page fault, from the initial trap through disk read to instruction restart.
Effective Access Time (EAT)
Let $p$ be the page fault rate ($0 le p le 1$), $ma$ be memory access time (e.g. 100ns), and $PFT$ be page fault service time (e.g. 8ms = 8,000,000ns):
EAT = (1 − p) × ma + p × PFT
Even if $p$ is just 0.1% ($0.001$), memory access slows down by an enormous factor of 80×!
7.2 Page Replacement Algorithms
When a page fault occurs and no physical memory frame is free, the operating system must choose a resident page to evict to secondary storage ā this is page replacement. The objective is to achieve the lowest page fault rate possible.
Figure 7.2: FIFO replaces the oldest resident page; Optimal replaces the page unreferenced for the longest future duration; LRU approximates Optimal using the recent past.
Algorithm Comparisons
- FIFO (First-In, First-Out): Evicts the page that has been in memory the longest. Susceptible to Belady's Anomaly.
- Optimal (OPT / MIN): Replace the page that will not be used for the longest period of time in the future. Provably produces the lowest possible page fault count, but cannot be implemented in general-purpose OSs because future references cannot be known in advance.
- LRU (Least Recently Used): Evicts the page that has not been referenced for the longest period of time. Uses the recent past as an approximation of the near future. Immune to Belady's Anomaly (it belongs to the class of stack algorithms).
- Clock (Second-Chance) Algorithm: Practical hardware-assisted approximation of LRU. Operates on a circular list of frames using a 1-bit reference flag per frame.
7.3 Thrashing
If a process does not have enough physical memory frames to hold all pages in its active locality (its Working Set), it will trigger continuous page faults. Each fault evicts a page that is immediately needed again, causing the CPU to spend nearly 100% of its cycles servicing page-in and page-out I/O rather than executing instructions. This pathological condition is called Thrashing.
Figure 7.3: As multiprogramming increases, CPU utilization rises until the available frames are exhausted. Beyond this threshold, thrashing sets in and utilization collapses.
Remedies for Thrashing
- Working-Set Model: Proposed by Peter Denning. Tracks the set of pages referenced by a process in the most recent $Delta$ page references. A process is only admitted if all pages in its working set fit in available free frames.
- Page-Fault Frequency (PFF): Directly measures each process's page fault rate. If the fault rate exceeds an upper threshold, allocate more frames to the process; if it drops below a lower threshold, reclaim unused frames.
