ITPEC FE Morning October 2022 Question 17

Page Replacement: FIFO vs LFU — count page faults for each algorithm with 3 memory blocks.

Page reference string: 1, 3, 2, 1, 4, 5, 2, 3, 4, 5

FIFO (First In, First Out):
- Evict the page that has been in memory the longest
- Faults at steps: 1, 3, 2, 4, 5, 3 → 6 page faults

LFU (Least Frequently Used):
- Evict the page with the lowest access count
- Tiebreaker: FIFO among pages with equal count
- Faults at steps: 1, 3, 2, 4, 5, 2, 3, 4, 5 → 9 page faults

Why not others:
- (a) FIFO=3, LFU=2 — only 3 faults would mean almost all hits; impossible with 5 distinct pages and 3 blocks
- (b) FIFO=4, LFU=6 — FIFO count is too low; 3 mandatory cold-start faults + at least 3 more
- (c) FIFO=5, LFU=3 — LFU=3 is impossibly low (minimum 5 cold-start faults for 5 distinct pages minus 3 blocks = at least 5)

Key rule: First 3 distinct pages always cause faults (cold start). LFU can perform worse than FIFO when frequency counts don't reflect future access patterns. Don't confuse LFU (frequency) with LRU (recency).

AI-generated — may contain errors