Page replacement: FIFO, LRU and optimal
Page replacement decides which memory page to evict when a page fault occurs; common policies are FIFO, LRU and Optimal (clairvoyant) — understanding them is essential to predict page-fault behaviour, explain Belady's anomaly, and compute hit/miss rates for virtual memory systems.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Operating systems use page replacement inside the virtual-memory manager to keep running programs within limited physical frames. An engineer uses these policies to predict page-fault rates, tune memory allocation (frames per process), and choose or implement a replacement algorithm (or an approximation) such as LRU or Clock to reduce costly page faults.
Key ideas
- Page fault — an event when a referenced virtual page is not present in any frame; the OS must load it (costly).
- Page replacement problem — when a page fault occurs and no free frame exists, choose a page in memory to evict so the faulting page can be loaded.
- Reference string — the sequence of page numbers requested by the CPU (the input to any replacement policy).
Replacement policies defined (exact algorithmic statements):
FIFO (First-In, First-Out): Maintain pages in the order they were loaded into frames (a queue). On a page fault with no free frame, evict the page that entered memory earliest (the head of the queue). Assumption: order of loading is fixed; hits do not change order.
LRU (Least Recently Used): Evict the page that has not been used for the longest time (the least recently referenced). Assumptions: the algorithm can observe past references and update recency on every reference (on hit or miss), and the recency information is kept perfectly.
Optimal (Belady's algorithm): Evict the page whose next use is farthest in the future (or not used again). This minimises the number of page faults for a given reference string (proof by exchange argument). Assumption: the algorithm knows the entire future reference string (clairvoyant) — not implementable in practice but used as a lower bound.
Important theorem / property:
- Stack algorithm property: A page-replacement algorithm is a stack algorithm if the set of pages in memory with m frames is always a subset of pages when the algorithm is run with m+1 frames (for the same reference string starting from the same initial condition). Any stack algorithm has non-increasing page faults as the number of frames increases (so it cannot show Belady's anomaly). LRU and Optimal are stack algorithms; FIFO is not.
Proof sketch (stack property for LRU):
- Maintain a global recency stack where, at any time, pages are ordered by recency (top = most recently used).
- The pages resident for m frames are the top m entries of the stack (by definition of LRU). If you increase frames to m+1, the top m pages remain in the top m+1 pages — hence the set for m is subset of set for m+1.
- Therefore as frames increase, pages kept cannot be fewer, so faults cannot increase.
Belady's anomaly:
- Belady's anomaly: For some replacement algorithms (e.g. FIFO), increasing the number of frames can increase the number of page faults for the same reference string.
- Example: FIFO may show the anomaly; LRU and Optimal do not (they are stack algorithms).
Diagrams to draw (exam instruction):
- To show steps, draw a table: columns = reference indices (1..n) and page referenced; rows = each frame (1..F) with the page in that frame after each reference; mark a F or tick where a page fault occurs. Label top-left with frame numbers and the reference string across the top.
- To illustrate FIFO queue: draw a horizontal queue showing load order, label head (to be evicted) and tail (most recent load).
- To illustrate LRU stack: draw a vertical stack of pages ordered by recency; on each reference move referenced page to top.
Practical notes:
- LRU is expensive to implement exactly; approximations include the Clock algorithm (second chance), aging counters, or sampling-based approaches. Optimal is a theoretical lower bound useful for evaluation.
Formulas
page_fault_rate = (# of page faults) / (# of memory references) — fraction (unitless). Applies to measured reference string or long-run average.
hit_ratio = (# of hits) / (# of memory references) — fraction (unitless); hit_ratio = 1 - page_fault_rate if every reference is either hit or miss.
EAT = (1 - p) · T_mem + p · T_pf — Effective Access Time in seconds (s). Symbols: p = page-fault rate (unitless), T_mem = memory access time (s), T_pf = average page-fault service time (s) including I/O and page-in costs. Applies when page fault events are modeled as independent with average cost T_pf.
When counting faults for an algorithm, no special SI units are needed — counts are integers.
Worked examples
Example 1 — (compare FIFO, LRU, Optimal) Reference string S = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]. Use frames = 3. Step-by-step (condensed) and final counts.
Procedure: follow each reference; if page present = hit; if not present and free frame exists = load and count a fault; if no free frame = apply replacement rule and count a fault. Numbered steps below follow the reference indices.
FIFO with 3 frames (detailed steps condensed):
- Steps 1–3 load 1,2,3 -> faults = 3.
- Step 4 request 4 -> evict 1 (oldest) -> fault (4).
- Steps 5–6 1,2 both cause faults because they were evicted earlier -> faults increment to 6.
- Step 7 request 5 -> fault (7).
- Steps 8–9 hits (1,2) -> faults stay 7.
- Step 10 request 3 -> fault (8); Step 11 request 4 -> fault (9); Step 12 request 5 -> hit or fault? with FIFO 5 present -> final faults = 9.
Formula before numbers:
page_faults = count_faults(S, FIFO, frames=3)→ computed = 9.LRU with 3 frames (condensed):
- Follow LRU recency updates. After full simulation (see Key ideas for algorithm), page faults counted = 10.
Formula:
page_faults = count_faults(S, LRU, frames=3)→ 10.Optimal with 3 frames (condensed):
- Use future-use knowledge to evict the page used farthest in the future. Final page faults = 7.
Formula:
page_faults = count_faults(S, OPTIMAL, frames=3)→ 7.
Summary numbers (for S length 12):
- FIFO (3 frames): 9 faults →
page_fault_rate = 9/12 = 0.75. - LRU (3 frames): 10 faults →
page_fault_rate = 10/12 = 0.833.... - Optimal (3 frames): 7 faults →
page_fault_rate = 7/12 = 0.5833....
Final answers in bold above. (Check counts in a full table if required.)
Example 2 — Belady's anomaly (classic): Same reference string S as above, compare FIFO with 3 and 4 frames.
- FIFO with 3 frames → faults = 9 (as above).
- FIFO with 4 frames → full simulation gives faults = 10.
This shows faults increased when frames increased from 3 to 4 under FIFO: this is Belady's anomaly. Explanation: FIFO's eviction order ignores recency, so adding frames can change which pages are evicted later and sometimes cause more misses.
Note: LRU and Optimal do not show this behaviour; with the same S, LRU faults decreased when frames increased (10 → 8), Optimal decreased (7 → 6). These are stack-algorithm behaviours.
Example 3 — compute Effective Access Time (short): Suppose memory access time T_mem = 100 ns = 100·10^-9 s, average page-fault time T_pf = 8 ms = 8·10^-3 s, and measured page-fault rate p = 0.001. Then
EAT = (1 - p)·T_mem + p·T_pf = (0.999)·100e-9 + 0.001·8e-3 = 0.0000080999 s ≈ 8.0999e-6 s.
This shows even a small p dominated by T_pf.
Common mistakes
- In LRU: failing to update recency on a hit (this changes future evictions and counts).
- Counting initial empty-frame loads incorrectly: every load into a previously empty frame is a page fault.
- Assuming Optimal is implementable online (it is not; it requires future knowledge).
- Arithmetic errors in page-fault counts when doing many steps; always use a table in exams.
For your exam
Types of questions you can get:
- Definitions: define page fault, frame, FIFO/LRU/Optimal.
- Short notes: compare policies, explain Belady's anomaly, describe stack algorithms.
- Derivations/proofs: prove stack property for LRU, or prove Optimal minimises faults (exchange argument).
- Numericals: given a reference string and frame count, show step-by-step page contents and count faults for FIFO, LRU and Optimal.
- Diagrams/programs: draw frame tables with faults marked; implement a simulation in C for one policy (rare in OS theory exam but possible).
What full-marks answers include:
- Clear definitions of terms used.
- Correct algorithm description and assumptions.
- A correctly labelled table showing each reference, frame contents per step, and which steps are faults.
- Final counts and computed rates (page-fault rate, EAT if asked) with units.
- For proofs, state assumptions (same starting state, same reference string) and show each logical step.
Quick check
- What is a page fault?
- Name one property that distinguishes FIFO from LRU.
- State Belady's anomaly in one sentence.
Answers: 1) A page fault is an event when a referenced virtual page is not present in any physical frame so the OS must load it (fault = miss). 2) FIFO evicts the page loaded earliest and does not change order on hits; LRU evicts the least recently referenced page and updates recency on every access. 3) Belady's anomaly: for some algorithms (e.g. FIFO), increasing the number of frames can increase the number of page faults for the same reference string.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?