Virtual Memory: Policies and Summary
Fetch policy
Demand paging (the default): a page is brought into memory only when the CPU references it. The alternative is prepaging: the OS guesses which pages will be needed and brings them in proactively. Prepaging is useful at programme start (load the first few pages of code and the initial stack) but risks wasting I/O on pages never used.
Placement policy
With paging, placement is trivial: any free frame can hold any page. There is no decision to make — unlike segmentation, where the OS must find a contiguous hole large enough. This is one of the fundamental advantages of paging.
Replacement policy
The choice of victim when the free-frame list is empty. Covered in detail:
- OPT (gold standard, unimplementable)
- LRU (good, expensive to implement exactly, approximated by Clock)
- FIFO (simple, can exhibit Belady’s anomaly)
- Clock / Enhanced Clock (practical LRU approximations using A and D bits)
Allocation policy
How many frames should each process get?
Fixed allocation: each process gets a fixed number of frames (e.g., proportional to its size). Simple but inflexible — a process’s working set may change over time; its allocation should adapt.
Variable allocation: the OS adjusts frame counts based on page-fault frequency (PFF) or working-set size. Processes that fault heavily get more frames (if available); processes with excess frames have them reclaimed.
Global vs local replacement:
- Local: a process can only evict its own pages. It cannot steal frames from other processes. Its fault rate depends only on its own access pattern.
- Global: a process can evict any page, including those belonging to other processes. More flexible (an idle process’s frames can be used by a busy process), but a thrashing process can steal frames from others, spreading the thrashing.
Linux uses a global LRU-based scheme with background reclaim (kswapd) that monitors watermarks and evicts cold pages before the free list empties.
The page daemon
Many systems run a background page daemon (Linux’s kswapd, Windows’ modified page writer) that periodically:
- Scans pages, clearing A bits and collecting statistics.
- Evicts or writes back dirty pages proactively.
- Maintains a pool of free (and clean) frames so that the page-fault handler rarely needs to do synchronous disk writes.
This transforms page-fault handling from a disk-I/O-bound operation (slow) to a frame-reassignment operation (fast), dramatically improving the experience of page-fault handling from the perspective of the faulting process.
Summary of the virtual memory subsystem
| Component | Responsibility |
|---|---|
| Fetch policy | When to bring pages in (demand vs prepaging) |
| Placement policy | Where to put pages (trivial for paging) |
| Replacement policy | Which page to evict (OPT/LRU/FIFO/Clock) |
| Allocation policy | How many frames per process (fixed vs variable) |
| Page daemon | Background reclaim and free-pool maintenance |
Past Paper Questions
2023 Paper 2 Question 3(c): Discuss system-wide performance implications of swapping out two frames instead of one on each page fault where a frame must be reclaimed. [4 marks]