Problem Description

This is the classic Dining Philosophers Problem, a well-known concurrency challenge in computer science.

Setup:

• 5 philosophers sit around a circular table
• Each philosopher has a bowl of spaghetti in front of them
• Between each pair of adjacent philosophers, there is exactly one fork (so 5 forks total)
• Philosophers are numbered 0 to 4 in clockwise order

Rules:

• Each philosopher alternates between thinking and eating
• To eat, a philosopher needs both the left fork AND the right fork
• Each fork can only be held by one philosopher at a time
• After eating, the philosopher must put down both forks
• A philosopher can pick up forks in any order (left first or right first) as they become available
• A philosopher cannot start eating until they have both forks

The Challenge: Design a concurrent algorithm that prevents deadlock and starvation - ensuring every philosopher can continue alternating between eating and thinking forever, without any philosopher being permanently blocked from eating.

Implementation Requirements: You need to implement the function wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:

• philosopher: the ID (0-4) of the philosopher who wants to eat
• pickLeftFork, pickRightFork: callback functions to pick up the respective forks
• eat: callback function to let the philosopher eat (only call after both forks are picked)
• putLeftFork, putRightFork: callback functions to put down the respective forks

The system will run 5 threads simultaneously (one per philosopher), and the function may be called multiple times for the same philosopher, even before their previous eating session completes.

The Core Problem: The main challenge is avoiding deadlock (where all philosophers pick up their left fork and wait forever for the right fork) while ensuring fairness (no philosopher starves).

Intuition

The key insight to solving this problem is understanding what causes deadlock in the naive approach. If all philosophers simultaneously pick up their left fork, they'll all be waiting for their right fork forever - classic circular wait deadlock.

To prevent deadlock, we need to break the circular dependency. One elegant approach is to ensure that adjacent philosophers cannot attempt to eat at the same time. Think of it this way: if philosopher 0 is eating (holding forks 0 and 1), then philosophers 4 and 1 cannot eat because they need forks 0 and 1 respectively.

This naturally leads us to think about mutexes for each philosopher rather than for each fork. If we assign a mutex to each philosopher and require that when a philosopher wants to eat, they must lock both their own mutex AND their neighbor's mutex, we ensure:

1. No adjacent philosophers can eat simultaneously - if philosopher i is eating, they hold locks for positions i and i+1, preventing both neighbors from eating
2. Non-adjacent philosophers can still eat - philosophers 0 and 2 can eat at the same time, as can philosophers 1 and 3, maximizing concurrency
3. Deadlock is impossible - scoped_lock in C++17 acquires multiple locks in a deadlock-free manner by using a consistent ordering internally

The beauty of scoped_lock(mutex1, mutex2) is that it:

• Acquires both locks atomically using a deadlock avoidance algorithm
• Automatically releases both locks when the scope ends
• Handles the edge case where philosopher 4's "next" neighbor is philosopher 0 (circular table)

This approach is simpler than managing individual fork locks and naturally prevents the circular wait condition that leads to deadlock, while still allowing maximum possible concurrency (up to 2 philosophers can eat simultaneously).

Solution Approach

The solution uses a mutex-per-philosopher strategy with C++17's scoped_lock to elegantly handle the concurrency challenges.

Data Structure:

• vector<mutex> mutexes_ - An array of 5 mutexes, one for each philosopher position

Core Implementation:

1. Mutex Assignment Strategy:

   • Each philosopher i is associated with mutex at index i
   • When philosopher i wants to eat, they must acquire locks for both position i and position (i+1) % 5
   • This ensures adjacent philosophers cannot eat simultaneously

2. Lock Acquisition:

   std::scoped_lock lock(mutexes_[philosopher], 
                        mutexes_[philosopher >= 4 ? 0 : philosopher + 1]);

   • For philosophers 0-3: lock mutexes [i] and [i+1]
   • For philosopher 4: lock mutexes [4] and [0] (wrapping around the circular table)
   • scoped_lock acquires both mutexes atomically using deadlock avoidance algorithms

3. Eating Sequence: Once both locks are acquired, the philosopher performs actions in order:

   pickLeftFork();    // Pick up left fork
   pickRightFork();   // Pick up right fork
   eat();             // Eat with both forks
   putLeftFork();     // Put down left fork
   putRightFork();    // Put down right fork

4. Automatic Lock Release:

   • When the function scope ends, scoped_lock automatically releases both mutexes in reverse order
   • This makes the philosopher's position available for adjacent philosophers

Why This Works:

• Prevents Deadlock: scoped_lock internally orders lock acquisition consistently across all threads
• Prevents Starvation: Each philosopher gets fair access to attempt eating when their required mutexes are free
• Maximizes Concurrency: Non-adjacent philosophers (e.g., 0 and 2, or 1 and 3) can eat simultaneously since they don't share mutexes

The elegance lies in shifting from "locking forks" to "locking philosopher positions", which naturally prevents the circular dependency that causes deadlock in the traditional fork-based approach.

Example Walkthrough

Let's walk through a scenario with 5 philosophers (0-4) to see how the mutex-per-philosopher approach prevents deadlock and allows concurrent eating.

Initial Setup:

• Philosophers: 0, 1, 2, 3, 4 sitting in a circle
• Mutexes: M0, M1, M2, M3, M4 (one per philosopher)
• Each philosopher needs to lock their own mutex and their right neighbor's mutex

Scenario Timeline:

Time T1: Philosopher 0 wants to eat

• Attempts to acquire: scoped_lock(M0, M1)
• Success! Locks both M0 and M1
• Executes: pickLeftFork() → pickRightFork() → eat() → putLeftFork() → putRightFork()
• Status: P0 eating, P1 and P4 blocked (need M0 and M1 respectively)

Time T2: Philosopher 2 wants to eat (while P0 is still eating)

• Attempts to acquire: scoped_lock(M2, M3)
• Success! M2 and M3 are free since P0 only holds M0 and M1
• Both P0 and P2 are now eating simultaneously
• Status: P0 and P2 eating, P1, P3, P4 blocked

Time T3: Philosopher 1 wants to eat

• Attempts to acquire: scoped_lock(M1, M2)
• Blocked! M1 is held by P0, M2 is held by P2
• P1 waits...

Time T4: Philosopher 0 finishes eating

• Releases M0 and M1
• Now P1 can attempt again, but still needs M2 (held by P2)
• P4 could now eat (needs M4 and M0, both free)

Time T5: Philosopher 4 wants to eat

• Attempts to acquire: scoped_lock(M4, M0) (wraps around)
• Success! Both M4 and M0 are free
• P4 starts eating

Time T6: Philosopher 2 finishes eating

• Releases M2 and M3
• Now P1 can finally acquire scoped_lock(M1, M2) and start eating

Key Observations:

1. No Deadlock: Unlike the naive approach where all philosophers grab their left fork simultaneously, here scoped_lock prevents circular waiting
2. Maximum Concurrency: P0 and P2 ate simultaneously (non-adjacent), as did P4 and P1 later
3. Fair Access: P1 waited but eventually got to eat once required mutexes became available
4. Circular Table Handling: P4's wrap-around case (locking M4 and M0) worked seamlessly

This approach ensures at most 2 philosophers can eat at any given time (any more would require adjacent philosophers to eat, which is prevented by the shared mutex requirement).

Solution Implementation

Time and Space Complexity

Time Complexity: O(1) per philosopher's eating action. Each call to wantsToEat performs a constant number of operations: acquiring two locks, executing five function calls (pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork), and releasing the locks. The scoped_lock constructor uses deadlock avoidance algorithms internally but still completes in constant time for a fixed number of mutexes (2 in this case).

Space Complexity: O(1) overall. The class maintains a fixed-size vector of 5 mutexes regardless of how many times philosophers eat. Each mutex has constant space overhead, and the total space used is O(5) = O(1). The scoped_lock object created in each function call uses O(1) stack space temporarily, which is released when the function returns.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Circular Wait Deadlock (Without Ordered Locking)

The Pitfall: The most common mistake is having each philosopher always pick up their left fork first, then their right fork:

# WRONG - This causes deadlock!
def wantsToEat(self, philosopher, ...):
    left_fork = philosopher
    right_fork = (philosopher + 1) % 5
  
    with self.fork_mutexes[left_fork]:    # Everyone grabs left fork
        with self.fork_mutexes[right_fork]: # Everyone waits for right fork forever!
            # Eating logic...

Why it fails: If all 5 philosophers execute simultaneously, they all grab their left fork (philosophers 0-4 grab forks 0-4). Now each philosopher waits for their right fork, but those are held by their neighbors. Classic circular dependency → deadlock!

The Solution: Always acquire locks in a consistent global order:

first_fork = min(left_fork_index, right_fork_index)
second_fork = max(left_fork_index, right_fork_index)
with self.fork_mutexes[first_fork]:
    with self.fork_mutexes[second_fork]:
        # Safe to eat

2. Incorrect Fork-to-Philosopher Mapping

The Pitfall: Misunderstanding which forks a philosopher needs:

# WRONG - Incorrect fork assignment
left_fork = (philosopher - 1) % 5  # Wrong calculation!
right_fork = philosopher

Why it fails: This creates gaps where some forks are never used while others are over-contended, breaking the problem's constraints.

The Solution: Remember the circular arrangement:

• Philosopher i sits between fork i (left) and fork (i+1) % 5 (right)
• Fork 0 is shared by philosophers 0 and 4

3. Lock Acquisition Without Deadlock Prevention

The Pitfall: Using separate lock acquisitions without ordering:

# WRONG - Race condition in acquiring locks
if self.fork_mutexes[left_fork].acquire(blocking=False):
    if self.fork_mutexes[right_fork].acquire(blocking=False):
        # eat...
        self.fork_mutexes[right_fork].release()
    self.fork_mutexes[left_fork].release()

Why it fails: This tries to avoid deadlock through non-blocking acquisition, but it can lead to livelock (philosophers repeatedly picking up and putting down forks) or starvation (some philosophers never getting both forks).

The Solution: Use ordered locking or atomic multi-lock acquisition mechanisms like Python's nested with statements or C++'s scoped_lock.

4. Forgetting to Release Resources

The Pitfall: Not properly releasing forks after eating:

# WRONG - Missing proper cleanup
def wantsToEat(self, philosopher, ...):
    self.fork_mutexes[first_fork].acquire()
    self.fork_mutexes[second_fork].acquire()
  
    pickLeftFork()
    pickRightFork()
    eat()
    # Oops! Forgot to call putLeftFork() and putRightFork()
    # Oops! Forgot to release the mutexes!

Why it fails: Forks remain permanently locked, preventing other philosophers from eating.

The Solution: Always use context managers (with statements) for automatic cleanup, and ensure all callback functions are called in the correct sequence.