Classical Synchronization Problems • Dining Philosophers ProblemHard⏱️ ~3 min
Solution 2: Breaking Symmetry with Asymmetric Fork Ordering
Solution 2
Asymmetric solution: Make one philosopher "left-handed" (picks up left fork first). This breaks the circular wait because not everyone reaches in the same direction.
Breaking Symmetry
Why It Works
Circular wait requires everyone to wait in the same direction. If P4 picks up left fork first while others pick up right fork first, the cycle breaks. P4 and P0 both reach for the same fork first. One wins, eats, releases, and the other can proceed.
Implementation
if (id == N-1) // last philosopher
left.wait(); right.wait();
else
right.wait(); left.wait();
left.wait(); right.wait();
else
right.wait(); left.wait();
Generalization: Resource Ordering
Number all resources globally. Always acquire in increasing order. This prevents circular wait because you cannot hold resource 5 while waiting for resource 3.
Pattern: Always acquire resources in a consistent global order. Breaks circular wait. The most practical real-world solution.
💡 Key Takeaways
✓Making at least one philosopher left-handed (acquires left fork first instead of right) breaks circular wait; deadlock requires all philosophers waiting in same circular direction
✓Proof by contradiction: if leftie is in deadlock holding left fork waiting for right, her right neighbor must hold that fork and also be waiting, implying neighbor is also leftie; repeating shows all must be lefties
✓Simplest implementation: P0 is leftie (left then right), P1-P4 are righties (right then left); requires no extra semaphores beyond fork array
✓Generalizes to resource ordering: acquiring resources in consistent global order prevents circular wait; equivalent to breaking symmetry in the dependency graph
✓More efficient than footman solution (no additional semaphore) and allows full concurrency (all 5 philosophers can attempt eating, 2 succeed)
📌 Examples
1Asymmetric prevents deadlock: P0 tries left(F1) then right(F0); P4 tries right(F0) then left(F4); if P4 holds F0, P0 blocks on F0 first, never holding F1 while waiting; no cycle forms
2Database lock ordering: transactions always acquire locks on rows in ascending row ID order; T1 needs rows 5,10; T2 needs rows 10,5; both acquire 5 first, one blocks, no deadlock
3Why one leftie suffices: the cycle P0→P1→P2→P3→P4→P0 requires each to wait for successor; if P0 waits for predecessor (leftie behavior), cycle is broken between P0 and P4