LRU Page Replacement: Step-by-Step 3-Frame Example and Exam Traps
Trace every reference through fixed frame slots, learn two reliable recency methods, compare LRU with FIFO and Optimal, and avoid mistakes that alter fault counts.
KnowledgeGate Team
Exam prep & CS education

The LRU rule sounds simple: replace the least recently used page. Errors begin when a hit changes recency, an empty frame is mistaken for a replacement, or the oldest loaded page is chosen. Virtual Memory in Operating Systems connects address translation, TLB timing, page faults, all three replacement policies and thrashing across CS Fundamentals for Exams & Placements. LRU's narrower calculation uses backward-looking recency, captured by last-used indices or an MRU-to-LRU stack.
What LRU replaces, and what recently used really means
A process has a fixed number of page frames. A reference to a resident page is a hit; one to a non-resident page is a fault. A fault fills an empty frame when possible. Only a fault with full frames needs a victim.
Least Recently Used, or LRU, selects the resident whose most recent reference lies farthest in the past. Load time, page number and total access count do not decide the victim.
Use this four-step rule:
Check whether the referenced page is resident.
On a hit, keep the frames unchanged but make that page the most recently used.
On a fault with space, load the page and mark it most recent.
On a fault with full frames, evict the current least recently used page, load the new page and mark it most recent.
Two reliable ways to track recency by hand
With the last-used-index method, number references from 1 and update the accessed page's index. On a full-frame fault, evict the resident with the smallest index. Before step 8, pages 2, 0, 3 were last used at steps 4, 7, 6, so page 2 leaves for page 4.
An equivalent recency stack puts MRU on the left and LRU on the right. A hit or new page moves to the left; a full-frame fault removes the rightmost page. Before step 8, the stack is [0, 3, 2]; after reference 4, it is [4, 0, 3]. Always label it MRU -> LRU.
Worked example: trace 13 references through three frames
Assume demand paging, 3 fixed frame slots and no preloaded pages. A dash is unused, F is a fault, and H is a hit. Slots stay fixed; page values are not sorted.
Step | Ref | F1 | F2 | F3 | Result | Victim | MRU -> LRU after access |
|---|---|---|---|---|---|---|---|
1 | 7 | 7 | - | - | F | none | 7 |
2 | 0 | 7 | 0 | - | F | none | 0, 7 |
3 | 1 | 7 | 0 | 1 | F | none | 1, 0, 7 |
4 | 2 | 2 | 0 | 1 | F | 7 | 2, 1, 0 |
5 | 0 | 2 | 0 | 1 | H | none | 0, 2, 1 |
6 | 3 | 2 | 0 | 3 | F | 1 | 3, 0, 2 |
7 | 0 | 2 | 0 | 3 | H | none | 0, 3, 2 |
8 | 4 | 4 | 0 | 3 | F | 2 | 4, 0, 3 |
9 | 2 | 4 | 0 | 2 | F | 3 | 2, 4, 0 |
10 | 3 | 4 | 3 | 2 | F | 0 | 3, 2, 4 |
11 | 0 | 0 | 3 | 2 | F | 4 | 0, 3, 2 |
12 | 3 | 0 | 3 | 2 | H | none | 3, 0, 2 |
13 | 2 | 0 | 3 | 2 | H | none | 2, 3, 0 |
Faults occur at steps 1, 2, 3, 4, 6, 8, 9, 10, 11, giving 9 faults. Hits occur at steps 5, 7, 12, 13, giving 4 hits. The checksum is 9 + 4 = 13, the number of references. Rounded to two decimal places, the fault rate is 9/13 = 69.23% and the hit rate is 4/13 = 30.77%.

Why each eviction is correct, and how LRU differs from FIFO and Optimal
The dense part starts after step 7. Residents 2, 0, 3 have last-use indices 4, 7, 6, so step 8 evicts 2. Next, 4:8, 0:7, 3:6 makes step 9 evict 3. Then 4:8, 0:7, 2:9 makes step 10 evict 0. Finally, 4:8, 3:10, 2:9 makes step 11 evict 4. Each victim has the oldest latest use at that moment.
For the same string and three empty frames, FIFO gives 10 faults and 3 hits, LRU gives 9 faults and 4 hits, and Optimal gives 7 faults and 6 hits. FIFO removes the earliest loaded resident; LRU looks farthest backward; Optimal removes the resident used farthest ahead or never again. This trace does not prove LRU always beats FIFO. Optimal remains theoretical because it needs future references.

Exact LRU, practical tracking and the stack property
Exact LRU needs exact access order. One implementation stores each resident's timestamp and evicts the smallest. Another pairs an ordered recency list with a lookup map, moving accesses to the MRU end and evicting from the LRU end. Cost depends on the data structure.
A reference bit records whether a page was accessed during an interval, not exact order. Clock and second-chance use such bits to approximate recency, avoiding exact-order maintenance on every reference.
LRU has the stack property: for the same reference prefix, pages in an n-frame run are a subset of those in an (n+1)-frame run. Adding frames cannot increase LRU faults. This string gives 9 faults with 3 frames and 6 with 4. FIFO can show Belady's anomaly.
Traps that change the page-fault count
Hit trap: Step
5references resident page0. There is no fault or replacement, but0becomes MRU. Ignoring that change would wrongly evict0instead of1at step6.FIFO trap: At step
6, last uses are2:4, 0:5, 1:3, so LRU evicts1. FIFO would evict0, which arrived earlier. Never choose by scanning frame slots left to right.Initial-state trap: The first three faults fill empty frames and have no victims. Count each miss as one fault, including a cold-start fill. An eviction is not a second fault. Always state whether frames start empty.
Dirty-page trap: A dirty victim may need write-back, but its dirty bit does not change LRU's recency rule.
Future-knowledge trap: Looking ahead selects Optimal's victim, not LRU's.
Frequency trap: Least frequently used and least recently used are different. A page used many times long ago can still be LRU now.
How exams test LRU reasoning
Problems may ask you to compute hits and faults, identify a victim, reconstruct a table cell, compare policies, calculate a rate, recognise the stack property, or distinguish exact LRU from a reference-bit approximation.
Try a retrieval drill. Immediately before step 10, residents are 4, 0, 2, last used at 8, 7, 9. Pick the victim for incoming page 3 before reading on. It is 0, because 7 is the oldest latest use. At step 12, page 3 is resident, so the result is a hit and [0, 3, 2] becomes [3, 0, 2].
Continue with Page Replacement MCQs: 12 Solved (FIFO, LRU, Optimal). They test victim selection, fault counts and policy comparisons. For timed practice and error review, use the GATE Test Series.
Short version and next step
A hit updates recency.
A fault uses an empty frame if one exists.
A full-frame fault replaces the resident with the oldest latest use.
Faults plus hits equal references:
9 faults + 4 hits = 13.
Cover the result column and rebuild the MRU -> LRU list for all 13 references. Repeat with four frames and confirm 6 faults. Explain why more frames cannot increase LRU faults.
For a structured route through GATE subjects, use GATE Guidance by Sanchit Sir. Then use the linked MCQ article and GATE Test Series for practice. The goal is not memorising 9, but rebuilding every recency decision that produces it.
Keep learning
LRU Page Replacement MCQs: 12 Solved Questions with Page-Fault Traces
Solve 12 LRU questions with checked hit-fault traces, victim choices, policy comparisons, and one address-to-page conversion.
Page Replacement Algorithms for GATE: FIFO, LRU and Optimal with Belady's Anomaly Explained
One shared reference string traced fault by fault through FIFO, LRU and Optimal page replacement with 3 frames, then re-run under FIFO with 4 frames to demonstrate Belady's anomaly. Includes the counting rules GATE expects, why LRU beating FIFO is a tendency and not a theorem, and the stack-algorithm property that makes LRU and Optimal immune to the anomaly.
Page Replacement Algorithms MCQs: 12 solved questions (FIFO, LRU, Optimal)
Page replacement MCQs for GATE, UGC NET and DSSSB: FIFO and Belady's anomaly, LRU, Optimal, and page-fault counting numericals, each solved and explained.
Optimal Replacement MCQs: 10 Solved Questions with Step-by-Step Page-Fault Explanations
Solve 10 Optimal Replacement questions from GATE, ISRO, HTET, UPPSC and DSSSB papers, then check each answer against a full three-frame page-fault trace.





