If a system uses LRU page replacement but the reference string exhibits a cyclic pattern larger than the number of frames, what is the expected impact on page faults compared to FIFO?
hard🎤 Interviewer Follow-up Q15 of Q15
Operating Systems - Page Replacement - FIFO, LRU, Optimal Algorithm
If a system uses LRU page replacement but the reference string exhibits a cyclic pattern larger than the number of frames, what is the expected impact on page faults compared to FIFO?
ALRU will have fewer page faults because it always evicts the least recently used page
BLRU will perform optimally and minimize page faults in cyclic patterns
CLRU will have more page faults than FIFO because it keeps evicting pages that will be needed soon
DLRU and FIFO will have similar page fault rates due to cyclic references exceeding frame count
Step-by-Step Solution
Step 1: Understand cyclic reference pattern larger than frames
Pages are referenced in a cycle longer than available frames, causing repeated evictions.
Step 2: Analyze LRU vs FIFO behavior
Both algorithms will evict pages that will be needed soon because the working set exceeds frame count. LRU's advantage diminishes as no page stays long enough to be reused before eviction.
Step 3: Evaluate options
LRU will have fewer page faults because it always evicts the least recently used page is false; LRU advantage is lost in cyclic patterns larger than frames. LRU will perform optimally and minimize page faults in cyclic patterns is false; both have similar fault rates in this scenario. LRU will have more page faults than FIFO because it keeps evicting pages that will be needed soon is false; LRU does not necessarily have more faults than FIFO here. LRU and FIFO will have similar page fault rates due to cyclic references exceeding frame count is true; LRU and FIFO have similar fault rates due to cyclic references exceeding frame count.
Final Answer:
Option D -> Option D
Quick Check:
When working set > frames, LRU and FIFO fault rates converge.
Quick Trick:LRU loses advantage when working set exceeds frames [OK]
Common Mistakes:
MISTAKES
Assuming LRU always outperforms FIFO
Believing cyclic patterns favor LRU
Thinking LRU is optimal in all cases
Trap Explanation:
PITFALL
Option A and B are tempting due to overgeneralizing LRU's superiority; C misinterprets eviction behavior.
Interviewer Note:
CONTEXT
Tests deep understanding of algorithm behavior under edge-case workloads and limits of LRU.
Master "Page Replacement - FIFO, LRU, Optimal Algorithm" in Operating Systems
2 interactive learning modes - each teaches the same concept differently
