Classical Synchronization Problems • Dining Philosophers ProblemMedium⏱️ ~3 min
Solution 1: Limiting Concurrency with a Footman
Solution 1
Footman solution: Limit to 4 philosophers at the table. With 4 philosophers and 5 forks, at least one fork is always free. Someone can always eat.
Footman Pattern
Why It Works
With 4 philosophers and 5 forks, by pigeonhole principle at least one fork is untouched. That fork has two neighbors, each holding one fork. At least one neighbor can grab the free fork and eat. No circular wait possible.
Implementation
Use a counting semaphore initialized to 4 (the "footman"). Before picking up any fork, philosopher waits on footman. After eating and releasing forks, signals footman. Simple and effective.
Trade-offs
Pros: Simple to implement. Guarantees progress. No starvation with fair semaphore.
Cons: Limits concurrency. At most 2 philosophers can eat simultaneously (with 4 at table). A 5th philosopher waits outside even if forks are available.
Pattern: footman = Semaphore(N-1) for N philosophers. Breaks "hold and wait" by limiting who can hold.
💡 Key Takeaways
✓Limiting to 4 philosophers at table prevents deadlock: with 5 forks and 4 philosophers, at least one fork is free, so at least one philosopher can acquire both forks and eat
✓Footman semaphore initialized to 4 acts as entry ticket; philosopher calls footman.wait() before acquiring forks, footman.signal() after releasing forks
✓Deadlock-free by pigeonhole principle; starvation-free because waiting on footman is bounded and waiting on specific fork is bounded by neighbor eating duration
✓Generalizes to resource allocation: n threads needing k resources from m total, limit concurrent attempts to floor(m/k) threads to prevent deadlock
✓Tradeoff is reduced maximum concurrency during contention; pattern appears in connection pooling, file handle limits, and rate limiting systems
📌 Examples
1Footman in action: P0, P1, P2, P3 enter (footman = 0), P4 blocks on footman; P0 and P2 eat while P1 and P3 wait for forks; P0 finishes, exits, footman.signal() allows P4 to enter
2Connection pool analogy: database has 10 connections, each transaction needs 2 connections (query + logging); limit to 5 concurrent transactions prevents connection deadlock
3Why 4 not 3: limiting to 3 is safe but wastes resources; with 4 philosophers and 5 forks, 2 can still eat simultaneously (max possible); limiting to 3 would allow only 1 eating