ITPEC FE Morning April 2020 Question 18

LRU Page Replacement — count page faults (replacements only) using LRU with a fixed number of frames.

Given 3 frames (initially empty) and page reference string 2, 4, 1, 1, 2, 7, 3, 4, 6, 5, 5, 1, 2:

Initial loads (not counted as page faults per problem statement):
- Load 2 → {2}
- Load 4 → {2, 4}
- Load 1 → {2, 4, 1}

Hits and faults (only replacements count):
- 1 → hit
- 2 → hit
- 7 → fault (evict 4, LRU)
- 3 → fault (evict 1)
- 4 → fault (evict 2)
- 6 → fault (evict 7)
- 5 → fault (evict 3)
- 5 → hit
- 1 → fault (evict 4)
- 2 → fault (evict 6)

Total page faults = 7

LRU rule: Evict the page not accessed for the longest time. Hits update the page's "last used" position.

Trap: "Filling an empty page is not considered a page replacement operation" means initial loads into empty frames do NOT count as page faults. Only eviction-based faults are counted.

Why not others:
- (a) 4 — significant undercount
- (b) 5 — likely stopped counting before the last two faults
- (c) 6 — missed one replacement (possibly step 12 or 13)

AI-generated — may contain errors