Operating Systems - Semaphore vs Mutex - When to Use Which
What is the time complexity of acquiring and releasing a mutex compared to a counting semaphore in a typical OS implementation?
What is the time complexity of acquiring and releasing a mutex compared to a counting semaphore in a typical OS implementation?
medium🪤 Complexity Trap Q5 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze mutex operations
Mutex acquire/release typically use atomic instructions and simple queue updates, O(1).Step 2: Analyze semaphore operations
Counting semaphore also uses atomic decrement/increment and queue management, O(1).Step 3: Evaluate other options
Mutex ownership checks are constant time, not O(n). Priority inheritance is a protocol but does not affect base complexity. Queue management is usually O(1) with linked lists, not O(log n).Final Answer:
Option B -> Option BQuick Check:
Both use atomic ops and queues with O(1) complexity [OK]
Quick Trick: Mutex and semaphore ops are O(1) with atomic instructions [OK]
Common Mistakes:
MISTAKES- Assuming semaphore queue management is O(n) or O(log n)
- Confusing priority inheritance with base mutex complexity
- Thinking ownership checks add complexity
Trap Explanation:
PITFALL- Candidates often overestimate complexity due to queue management or priority protocols.
Interviewer Note:
CONTEXT- Tests understanding of synchronization primitive operation costs and OS implementation details.
Master "Semaphore vs Mutex - When to Use Which" in Operating Systems
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Operating Systems Quizzes