Operating Systems - Thrashing - Working Set Model & Prevention
What is the time complexity trade-off when implementing the working set model with a sliding window of size \( \tau \) for page reference tracking in a system with \( n \) pages?
What is the time complexity trade-off when implementing the working set model with a sliding window of size \( \tau \) for page reference tracking in a system with \( n \) pages?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Understand working set tracking
The working set model tracks pages referenced within a recent window \( \tau \).Step 2: Analyze complexity
Naively scanning the window per reference is O(\tau), but efficient data structures (queues + hash maps) allow O(1) amortized updates.
A: O(n) per page reference due to scanning entire window is incorrect.
B: O(\tau) per page reference ignores data structure optimizations.
D: O(n \times \tau) overestimates complexity.Final Answer:
Option C -> Option CQuick Check:
Efficient data structures enable O(1) amortized updates [OK]
Quick Trick: Use queues and hash maps for O(1) amortized working set updates [OK]
Common Mistakes:
MISTAKES- Assuming scanning entire window per reference (O(\tau))
- Confusing total pages with window size in complexity
- Ignoring data structure optimizations
Trap Explanation:
PITFALL- Candidates often forget amortized cost improvements from data structures and assume naive scanning.
Interviewer Note:
CONTEXT- Tests understanding of complexity trade-offs in working set implementation.
Master "Thrashing - Working Set Model & Prevention" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes