--- title: "Paging, Page Faults and Replacement Policies" description: "Accessing a valid nonresident page can cause a recoverable fault. The OS supplies the page and may reclaim a frame. FIFO and LRU choose different victims. Repeated faults and page transfers can leave " canonical: https://lightmysky.com/learn/computing/paging-page-faults-and-replacement-policies-mt_nEEuGL89Ze source: https://lightmysky.com/learn/computing/paging-page-faults-and-replacement-policies-mt_nEEuGL89Ze.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Paging, Page Faults and Replacement Policies Accessing a valid nonresident page can cause a recoverable fault. The OS supplies the page and may reclaim a frame. FIFO and LRU choose different victims. Repeated faults and page transfers can leave little time for execution when actively used pages do not fit in available RAM. Subject: Computing · Area: Computer Systems · Ages 20 to 21 Page: https://lightmysky.com/learn/computing/paging-page-faults-and-replacement-policies-mt_nEEuGL89Ze ## Ready when they can - Count LRU and FIFO faults from a stated reference string, frame count and initial contents - Explain how frequent faults and page transfers can limit progress during thrashing - Explain optimal replacement for a known trace and why past references alone cannot guarantee optimal online choices ## Lesson: Faults, victims, and thrashing 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. *(drawing: Process references in order. Count loads into empty frames as faults too.)* 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. **Recap.** LRU refreshes recency on hits; FIFO keeps arrival order. Count from stated initial frames. Thrashing limits progress; optimal replacement uses future references. *Lesson, worked questions and flashcards about page faults and replacement policies were written for this dataset.* ## Practice 8 questions on this page, each with its working shown. ## Needs first - [Virtual Memory and Address Translation](https://lightmysky.com/learn/computing/virtual-memory-and-address-translation-mt_B-PiAyderj) ## Optional connections - [The Memory Hierarchy and Why Caching Works](https://lightmysky.com/learn/computing/the-memory-hierarchy-and-why-caching-works-mt_0f5ArFPlxP) ## Opens up - [File Systems: Names, Blocks and Metadata](https://lightmysky.com/learn/computing/file-systems-names-blocks-and-metadata-mt_jN4u3idvF3) - [Serving a Model: Batching, the Key-Value Cache and Quantisation](https://lightmysky.com/learn/computing/serving-a-model-batching-the-key-value-cache-and-quantisation-mt_Nv1-WLGIO4)