If a requested page is not in physical memory, a page fault occurs and the system must make it available. In this model it is fetched from disk. When every frame is occupied, a replacement policy chooses which page to evict, affecting the total fault count.
A simulator showing pages entering and leaving frames along a reference string
1. Choose a page reference string and frame count
2. Choose a replacement policy
3. Process requests one at a time
Page faults for the same reference string
Each Next request advances one column. A column shows memory immediately after processing that request.
Three replacement policies
FIFO evicts the page loaded earliest. It is simple, but even a frequently used page may be removed just because it arrived long ago.
LRU evicts the page unused for the longest time. It relies on temporal locality; practical systems often approximate it.
OPT evicts the page whose next use is furthest in the future. It minimizes faults for a known reference string, but is a benchmark rather than an implementable online policy because future requests are unknown.
Belady's anomaly
More frames usually reduce page faults, but FIFO can produce more faults with additional frames. Load the Belady example and change from three frames to four: faults increase from 9 to 10. LRU and OPT do not exhibit this anomaly.