Operating Systems - Thrashing - Working Set Model & Prevention
Considering memory overhead, what is the space complexity trade-off when maintaining working set information for \( p \) processes each with window size \( \tau \)?
Considering memory overhead, what is the space complexity trade-off when maintaining working set information for \( p \) processes each with window size \( \tau \)?
medium🪤 Complexity Trap Q6 of Q15
Step-by-Step Solution
Solution:
Step 1: Identify what is stored
Each process maintains a window of size \( \tau \) tracking page references.Step 2: Analyze space complexity
For \( p \) processes, total space is proportional to \( p \times \tau \).
B: O(p + \tau) underestimates by summing instead of multiplying.
C: O(\tau) assumes shared windows, which is incorrect.
D: O(p \times n) overestimates by involving total pages unnecessarily.Final Answer:
Option A -> Option AQuick Check:
Space grows linearly with processes and window size [OK]
Quick Trick: Space = number of processes x window size [OK]
Common Mistakes:
MISTAKES- Assuming windows are shared globally
- Adding instead of multiplying process count and window size
- Confusing page table size with working set tracking space
Trap Explanation:
PITFALL- Candidates often confuse per-process data with global data, underestimating space needs.
Interviewer Note:
CONTEXT- Evaluates understanding of space trade-offs in working set tracking across multiple processes.
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