Operating Systems - Page Replacement - FIFO, LRU, Optimal Algorithm
Which of the following statements about the LRU page replacement algorithm's complexity and implementation is TRUE?
Which of the following statements about the LRU page replacement algorithm's complexity and implementation is TRUE?
medium🪤 Complexity Trap Q13 of Q15
Step-by-Step Solution
Step 1: Analyze LRU Implementation Complexity
LRU needs to track the order of page usage, which is costly without hardware or data structures.Step 2: Evaluate Each Option
LRU requires hardware support or additional data structures to track usage efficiently is true; LRU requires hardware support or additional data structures to track usage efficiently.
LRU can be implemented with O(1) time complexity per page reference using a stack is false; a stack alone cannot provide O(1) updates on every reference.
LRU always performs better than FIFO regardless of workload is false; LRU can perform worse than FIFO in some workloads (e.g., scan patterns).
LRU does not require any extra space beyond the page frames is false; LRU requires extra space for tracking usage metadata.Final Answer:
Option A -> Option AQuick Check:
Efficient LRU needs support beyond just frames.
Quick Trick: LRU needs extra tracking structures or hardware support [OK]
Common Mistakes:
MISTAKES- Assuming LRU is always better than FIFO
- Believing LRU can be done with no extra space
- Thinking a simple stack suffices for O(1) LRU
Trap Explanation:
PITFALL- Options A and D are tempting due to oversimplification; C is a common misconception about LRU's superiority.
Interviewer Note:
CONTEXT- Tests understanding of LRU's practical implementation challenges and trade-offs.
Master "Page Replacement - FIFO, LRU, Optimal Algorithm" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes