Bird
Raised Fist0

Comparing the resource hierarchy solution and the waiter solution for Dining Philosophers, which statement about space complexity is correct?

medium🪤 Complexity Trap Q6 of Q15
Operating Systems - Dining Philosophers - Problem, Deadlock & Solution
Comparing the resource hierarchy solution and the waiter solution for Dining Philosophers, which statement about space complexity is correct?
AResource hierarchy requires O(N) space for fork ordering, waiter requires O(1)
BBoth require O(N) space for semaphores or mutexes per fork
CWaiter requires O(N^2) space to track philosopher states, hierarchy requires O(N)
DResource hierarchy requires O(1) space, waiter requires O(N)
Step-by-Step Solution
Solution:

  1. Step 1: Analyze resource hierarchy

    Each fork needs a semaphore/mutex, so O(N) space.

  2. Step 2: Analyze waiter solution

    Waiter tracks availability of all forks and philosopher requests, also O(N) space.

  3. Step 3: Evaluate other options

    Waiter does not require O(1) or O(N^2) space; resource hierarchy is not O(1).

  4. Final Answer:

    Option B -> Option B

  5. Quick Check:

    Both solutions track forks with semaphores -> O(N) space [OK]
Quick Trick: Each fork requires a semaphore -> O(N) space [OK]
Common Mistakes:
MISTAKES
  • Assuming waiter uses constant space
  • Thinking waiter tracks all philosopher pairs (O(N^2))
  • Believing resource hierarchy is constant space
Trap Explanation:
PITFALL
  • Candidates confuse control logic with space usage, underestimating semaphore storage needs.
Interviewer Note:
CONTEXT
  • Assesses understanding of space complexity in synchronization solutions.
Master "Dining Philosophers - Problem, Deadlock & Solution" in Operating Systems

2 interactive learning modes - each teaches the same concept differently

SolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Operating Systems Quizzes
Context Switch - Cost & Causes - Context Switch - Cost & Causes - Quiz 3easy Critical Section Problem - Requirements & Peterson's Solution - Critical Section Problem - Requirements & Peterson's Solution - Quiz 14medium Process State Machine - Five-State Model - Process State Machine - Five-State Model - Quiz 1easy Producer-Consumer Problem Using Semaphores - Producer-Consumer Problem Using Semaphores - Quiz 15hard Producer-Consumer Problem Using Semaphores - Producer-Consumer Problem Using Semaphores - Quiz 3easy Round Robin Scheduling - Quantum & Turnaround Time - Round Robin Scheduling - Quantum & Turnaround Time - Quiz 2easy Semaphore vs Mutex - When to Use Which - Semaphore vs Mutex - When to Use Which - Quiz 6medium Starvation vs Deadlock vs Livelock - Differences & Examples - Starvation vs Deadlock vs Livelock - Differences & Examples - Quiz 9hard System Call - Mechanism & Modes (User vs Kernel) - System Call - Mechanism & Modes (User vs Kernel) - Quiz 6medium TLB - Translation Lookaside Buffer & Effective Access Time - TLB - Translation Lookaside Buffer & Effective Access Time - Quiz 1easy