# The Dining Philosophers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/the-dining-philosophers)
Canonical: https://scaleengineer.com/dsa/problems/the-dining-philosophers
---
## Problem
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

Design a discipline of behaviour (a concurrent algorithm) such that no philosopher will starve; _i.e._, each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.

![](https://assets.glich.co/dsa/the-dining-philosophers/image0.png)

_The problem statement and the image above are taken from [wikipedia.org](https://en.wikipedia.org/wiki/Dining%5Fphilosophers%5Fproblem)_

The philosophers' ids are numbered from **0** to **4** in a **clockwise** order. Implement the function `void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)` where:

* `philosopher` is the id of the philosopher who wants to eat.
* `pickLeftFork` and `pickRightFork` are functions you can call to pick the corresponding forks of that philosopher.
* `eat` is a function you can call to let the philosopher eat once he has picked both forks.
* `putLeftFork` and `putRightFork` are functions you can call to put down the corresponding forks of that philosopher.
* The philosophers are assumed to be thinking as long as they are not asking to eat (the function is not being called with their number).

Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. The function may be called for the same philosopher more than once, even before the last call ends.

**Example 1:**

**Input:** n = 1
**Output:** [[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
**Explanation:**
n is the number of times each philosopher will call the function.
The output array describes the calls you made to the functions controlling the forks and the eat function, its format is:
output[i] = [a, b, c] (three integers)
- a is the id of a philosopher.
- b specifies the fork: {1 : left, 2 : right}.
- c specifies the operation: {1 : pick, 2 : put, 3 : eat}.

**Constraints:**

* `1 <= n <= 60`

# Approaches
## Naive Approach (Prone to Deadlock)
This is the most intuitive but incorrect approach where each philosopher tries to pick up their left fork and then their right fork. While simple to conceptualize, this symmetrical behavior leads to a classic deadlock scenario where the system can come to a complete halt.
**Time:** Potentially infinite. Due to the high probability of deadlock, the philosophers may wait forever and never get to eat. · **Space:** O(1), as the number of forks (and thus locks) is fixed at 5.
**Pros:** Very simple to understand and implement.
**Cons:** This approach is fundamentally flawed as it leads to deadlock.; It does not solve the dining philosophers problem correctly.
### Explanation
In this approach, we model each of the five forks as a separate lock. A philosopher is programmed to first attempt to acquire their left fork. If successful, they then attempt to acquire their right fork. Only when both forks are held can the philosopher proceed to eat. After eating, they release both forks.

The critical issue arises from the possibility of a circular wait. If all five philosophers decide to eat at roughly the same time, it's possible for every philosopher to successfully pick up their left fork. At this point, every philosopher is holding one fork and waiting for the fork on their right. Since the right fork of any philosopher is the left fork of their neighbor, and all left forks are already held, no one can acquire their second fork. All philosophers will wait indefinitely, leading to a deadlock.

```java
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    // One lock for each fork
    private final ReentrantLock[] forks = new ReentrantLock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    // This implementation is prone to deadlock!
    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;

        // Symmetrical acquisition order
        forks[leftFork].lock();
        pickLeftFork.run();
        
        forks[rightFork].lock();
        pickRightFork.run();

        eat.run();

        putLeftFork.run();
        forks[leftFork].unlock();
        
        putRightFork.run();
        forks[rightFork].unlock();
    }
}
```
### Algorithm
- Create an array of 5 `ReentrantLock` objects, one for each fork.
- When philosopher `i` wants to eat, they attempt to lock their left fork (`i`) first.
- Then, they attempt to lock their right fork (`(i + 1) % 5`).
- Once both forks are acquired, the philosopher eats.
- After eating, the philosopher releases both the left and right forks.

## Waiter/Host Solution (Limiting Concurrency)
This approach prevents deadlock by introducing a constraint on the number of philosophers that can compete for forks at the same time. By allowing at most four philosophers to attempt to eat, we ensure that there is always at least one philosopher who can successfully acquire both forks, thus breaking the circular wait condition.
**Time:** The time is variable and depends on contention. A philosopher might have to wait for the semaphore and then for the individual fork locks. · **Space:** O(1), as it requires a fixed number of locks and one semaphore.
**Pros:** Effectively prevents deadlock.; The logic is relatively straightforward to implement and reason about.
**Cons:** Reduces the maximum possible concurrency, as at most 4 philosophers can even attempt to eat at once.; A philosopher might be blocked by the semaphore even if both of their required forks are currently available.
### Explanation
The core idea is to have a coordinator, often called a 'waiter' or 'host', that limits access to the table. We can implement this using a `java.util.concurrent.Semaphore` initialized with `N-1` permits (where N=5 is the number of philosophers). 

A philosopher who wants to eat must first ask the waiter for permission, which corresponds to acquiring a permit from the semaphore. If the semaphore has permits available (i.e., fewer than 4 philosophers are currently at the table), the philosopher gets a permit and proceeds to pick up their forks. If all 4 permits are in use, the philosopher waits until one is released.

This strategy guarantees that a deadlock cannot occur. In the worst-case scenario, four philosophers are at the table, and each picks up one fork. Since there are five forks in total, at least one fork must remain free on the table. The philosopher who needs this free fork as their second fork can acquire it, eat, and then release their forks, allowing the system to make progress.

```java
import java.util.concurrent.Semaphore;
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    private final ReentrantLock[] forks = new ReentrantLock[5];
    // A semaphore to allow at most 4 philosophers to pick up forks simultaneously.
    private final Semaphore waiter = new Semaphore(4);

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;

        // Wait for permission to sit at the table
        waiter.acquire();

        forks[leftFork].lock();
        pickLeftFork.run();
        forks[rightFork].lock();
        pickRightFork.run();

        eat.run();

        putLeftFork.run();
        forks[leftFork].unlock();
        putRightFork.run();
        forks[rightFork].unlock();

        // Release the permit
        waiter.release();
    }
}
```
### Algorithm
- Create 5 `ReentrantLock` objects for the forks.
- Create a `Semaphore` initialized with 4 permits. This acts as a 'waiter' or 'host'.
- Before attempting to pick up forks, a philosopher must first `acquire()` a permit from the semaphore.
- If a permit is granted, the philosopher proceeds to lock their left and right forks.
- After eating and putting down the forks, the philosopher must `release()` the permit back to the semaphore.

## Resource Hierarchy (Ordered Fork Acquisition)
This is a classic, efficient, and widely-used solution that prevents deadlock by breaking the circular wait condition. Instead of all philosophers following the same 'left-then-right' fork picking strategy, they follow a globally ordered resource allocation strategy. This ensures that a circular dependency among philosophers waiting for forks can never form.
**Time:** Highly efficient. The waiting time depends only on the contention for the two specific forks a philosopher needs, not on a global lock or semaphore. · **Space:** O(1), as it only requires a fixed number of locks (5).
**Pros:** Effectively and efficiently prevents deadlock.; Allows for a high degree of concurrency as there is no central bottleneck; contention is localized to the forks.; Elegant and simple to implement.
**Cons:** While deadlock is prevented, starvation is still theoretically possible. A philosopher could be perpetually unlucky, always finding one of their required forks locked by a neighbor.
### Explanation
The resource hierarchy solution assigns a unique order to all resources (the forks). For example, we can order the forks by their indices from 0 to 4. The rule is simple: any philosopher must acquire the lock for the lower-indexed fork before acquiring the lock for the higher-indexed fork.

Let's see how this works. For philosophers 0, 1, 2, and 3, their left fork `i` has a lower index than their right fork `(i+1)%5`. So they will all try to pick up their left fork first. However, for philosopher 4, their left fork is index 4 and their right fork is index 0. According to the rule, philosopher 4 must try to acquire fork 0 (lower index) before fork 4 (higher index). 

This breaks the cycle. If all philosophers try to eat at once, philosophers 0 through 3 will try to grab their left forks, while philosopher 4 will try to grab their right fork (fork 0). This means philosopher 0 and philosopher 4 will compete for fork 0. One will get it, and the other will wait. The circular wait condition is broken, and deadlock is prevented.

```java
import java.util.concurrent.locks.ReentrantLock;

class DiningPhilosophers {
    private final ReentrantLock[] forks = new ReentrantLock[5];

    public DiningPhilosophers() {
        for (int i = 0; i < 5; i++) {
            forks[i] = new ReentrantLock();
        }
    }

    public void wantsToEat(int philosopher,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        
        int leftForkIndex = philosopher;
        int rightForkIndex = (philosopher + 1) % 5;

        // To prevent deadlock, acquire locks in a fixed global order based on their index.
        int firstForkIndex = Math.min(leftForkIndex, rightForkIndex);
        int secondForkIndex = Math.max(leftForkIndex, rightForkIndex);

        forks[firstForkIndex].lock();
        forks[secondForkIndex].lock();

        // The problem statement implies the runnables are for logging/simulation.
        // Once both locks are acquired, the philosopher can 'pick up' both forks.
        pickLeftFork.run();
        pickRightFork.run();
        
        eat.run();

        // The order of putting down forks doesn't matter for correctness,
        // but it's good practice to release in reverse order of acquisition.
        putLeftFork.run();
        putRightFork.run();
        
        forks[secondForkIndex].unlock();
        forks[firstForkIndex].unlock();
    }
}
```
### Algorithm
- Create 5 `ReentrantLock` objects for the forks, indexed 0 to 4.
- To avoid deadlock, impose a strict ordering on fork acquisition.
- A philosopher must always lock the fork with the lower index before locking the fork with the higher index.
- For philosopher `i`, their forks are `i` and `(i + 1) % 5`. They must lock `fork[min(i, (i+1)%5)]` first, then `fork[max(i, (i+1)%5)]`.
- After eating, the forks are unlocked.

# Solutions
### CPP

```cpp
class DiningPhilosophers { public: using Act = function < void () > ; void wantsToEat ( int philosopher , Act pickLeftFork , Act pickRightFork , Act eat , Act putLeftFork , Act putRightFork ) { /* 这一题实际上是用到了C++17中的scoped_lock知识。 作用是传入scoped_lock(mtx1, mtx2)两个锁，然后在作用范围内，依次顺序上锁mtx1和mtx2；然后在作用范围结束时，再反续解锁mtx2和mtx1。 从而保证了philosopher1有动作的时候，philosopher2无法操作；但是philosopher3和philosopher4不受影响 */ std :: scoped_lock lock ( mutexes_ [ philosopher ], mutexes_ [ philosopher >= 4 ? 0 : philosopher + 1 ]); pickLeftFork (); pickRightFork (); eat (); putLeftFork (); putRightFork (); } private: vector < mutex > mutexes_ = vector < mutex > ( 5 ); };
```