ITPEC FE Morning April 2019 Question 19

FIFO vs LRU Page Replacement — count replacements for a given reference string.

Reference string: 1, 3, 2, 1, 4, 5, 2, 3, 4, 5 with 3 frames (initially empty). Filling an empty frame ≠ replacement.

FIFO (evict the page loaded earliest — hit does NOT update queue position):

• •1, 3, 2 → load into empty frames (0 replacements)
• •1 → hit
• •4 → evict 1 (oldest loaded) → replace #1
• •5 → evict 3 → replace #2
• •2 → hit
• •3 → evict 2 → replace #3
• •4 → hit
• •5 → hit

FIFO total = 3

LRU (evict the page least recently used — hit DOES update recency):

• •1, 3, 2 → load (0 replacements)
• •1 → hit (recency updates: 3, 2, 1)
• •4 → evict 3 (LRU) → replace #1
• •5 → evict 2 (LRU) → replace #2
• •2 → evict 1 (LRU) → replace #3
• •3 → evict 4 (LRU) → replace #4
• •4 → evict 5 (LRU) → replace #5
• •5 → evict 2 (LRU) → replace #6

LRU total = 6

Answer: (b) FIFO = 3, LRU = 6

Why not others:
- (a) FIFO=3, LRU=2 — LRU=2 is far too low; the access pattern causes frequent misses under LRU
- (c) FIFO=4, LRU=3 — FIFO=4 overcounts; page 1 is a hit at step 4, not a replacement
- (d) FIFO=5, LRU=4 — both values too high

Key rules:
- FIFO: evict the page that was loaded earliest; a hit does NOT change queue order
- LRU: evict the page that was accessed least recently; a hit DOES move the page to "most recent"
- Empty frame fills are NOT counted as replacements

AI-generated — may contain errors