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

Updated 17 Nov 20266 min read
LRU Page Replacement: Step-by-Step 3-Frame Example and Exam Traps

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:

  1. Check whether the referenced page is resident.

  2. On a hit, keep the frames unchanged but make that page the most recently used.

  3. On a fault with space, load the page and mark it most recent.

  4. 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%.

LRU frame-trace table shows 13 references across frames F1 to F3, with 9 faults, 4 hits, and victims 7, 1, 2, 3, 0, and 4.

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.

Recency-decision strip shows MRU-to-LRU stacks for steps 8 through 11, evicting pages 2, 3, 0, and 4, with LRU totaling 9 faults.

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 5 references resident page 0. There is no fault or replacement, but 0 becomes MRU. Ignoring that change would wrongly evict 0 instead of 1 at step 6.

  • FIFO trap: At step 6, last uses are 2:4, 0:5, 1:3, so LRU evicts 1. FIFO would evict 0, 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.

Go deeper with the full courseOperating System

Keep learning

Discussion