Paging, Page Faults and Replacement Policies

Address translation can fault when a valid page is not resident in RAM. The OS may load its contents or supply a zero-filled page, then retry. Invalid accesses and permission violations need different handling. In our replacement model, each frame holds one page. An absent-page reference counts as a fault; if all frames are full, evict a resident victim before loading.

Least recently used, or LRU, evicts the resident page whose last reference was earliest. Every access, including a hit, refreshes recency. With two empty frames and references 4, 5, 4, 6, 4, the first two loads fault. The next 4 hits. Loading 6 evicts 5; the final 4 hits. Total: three faults.

First in first out, or FIFO, evicts the earliest-loaded resident page. A hit does not change arrival order. With two empty frames and references 4, 5, 4, 6, 4, the first two loads fault and the next 4 hits. Loading 6 evicts 4. The final 4 faults and evicts 5. Total: four faults.

Thrashing means repeated faults and page transfers consume much of the time needed for useful execution. It often occurs when actively used pages do not fit in available RAM. Progress slows while paging activity is high. A busy storage device alone does not prove thrashing; other work also reads and writes storage.

For a known finite trace, optimal replacement evicts the resident page used farthest in the future. A page never used again is a suitable victim. An offline simulator can inspect the remaining trace. A running kernel generally lacks that future information; logging past references cannot guarantee the best victim for every possible continuation.

LRU does not have strictly fewer faults than FIFO on every trace. With two empty frames and references A, B, A, both load A and B with faults, then hit on A. Both have two faults. One tie disproves a claim of always fewer faults.