Problem Explanation

Five philosophers are sitting around a circular table. Each philosopher spends his life alternately thinking and eating. In the center of the table there is a large bowl of spaghetti. A philosopher needs both forks to eat a helping of spaghetti. A fork is placed in between each pair of adjacent philosophers.

The problem is to design the wantsToEat method that each philosopher will call when they want to eat. This method should ensure that a philosopher only eats when they have both left and right forks. Each fork can only be held by one philosopher so a philosopher can only pick the fork up if it's currently not being used by another philosopher. After eating, a philosopher must put down both forks, making them available to others. A philosopher can pick up the right or left fork first but they cannot start eating until they have both forks.

No philosopher can know when others may want to eat or think, therefore, the solution needs to provide a way to prevent deadlock and starvation amongst philosophers. In the context of computer science, deadlock is a condition where a process cannot progress because each member is waiting for some event that can only be caused by another member in the same set. In this problem, if all philosophers pick up their left fork at the same time, they will wait forever for the right fork, leading to deadlock.

Example

Consider the case where each philosopher needs to eat once (n = 1). A possible sequence in which the philosophers perform actions could be:

1
2
3# Philosopher 0 picks up left fork (represented by [0, 1, 1]) 
4# Philosopher 0 picks up right fork (represented by [0, 2, 1]) 
5# Philosopher 0 eats (represented by [0, 0, 3]) 
6# Philosopher 0 puts down left fork (represented by [0, 1, 2])
7# Philosopher 0 puts down right fork (represented by [0, 2, 2])
8# Philosopher 1 picks up left fork (represented by [1, 1, 1]) 
9# Philosopher 1 picks up right fork (represented by [1, 2, 1]) 
10# Philosopher 1 eats (represented by [1, 0, 3]) 
11# Philosopher 1 puts down left fork (represented by [1, 1, 2])
12# Philosopher 1 puts down right fork (represented by [1, 2, 2])
13# .... repeat for philosophers 2, 3, 4

Here, each action in the sequence is represented by an array [a, b, c] where a is the philosopher number, b is the fork {1: left, 2:right} and c is the operation {1: pick, 2: put, 3: eat}.

Approach

The Dining Philosophers problem is a classic multi-process synchronization problem which is used to demonstrate the ability to reason about concurrent systems. The problem describes five philosophers sitting around a table who do nothing but think and eat. In the center of the table is a communal bowl of spaghetti and between each philosopher is a single fork. The problem is to design a discipline of behavior which will allow each philosopher to periodically eat the spaghetti without causing a deadlock.

To solve this problem, a possible approach is to use a mutex lock which will serve as the shared resource. A mutex is a program object that allows multiple program threads to share the same resource, such as file access, but not simultaneously.

In the context of the problem, when dining, a philosopher will first attempt to grab a fork, waits until it's available (the mutex lock ensures that the philosopher waits his turn when multiple philosopher threads are leeching off the left and right fork at the same time), next retrieves the other fork, and then dines. After he is finished dining, the philosopher puts down both of his forks and starts thinking.

Solution

C++

1
2cpp
3#include <mutex>
4
5class DiningPhilosophers {
6private:
7    std::mutex mutex;
8
9public:
10    DiningPhilosophers() {}
11
12    void wantsToEat(int philosopher, 
13                    function<void()> pickLeftFork, 
14                    function<void()> pickRightFork, 
15                    function<void()> eat, 
16                    function<void()> putLeftFork, 
17                    function<void()> putRightFork) 
18    {
19        mutex.lock(); // The philosopher picks up the fork on his left.
20        pickLeftFork();
21        pickRightFork(); // The philosopher picks up the fork on his right to become the critical section.
22        eat(); // The philosopher eat.
23        putLeftFork(); // The philosopher puts down the fork on his left.
24        putRightFork(); // The philosopher puts down the fork on his right.
25        mutex.unlock(); // The philosopher goes back to thinking.
26    }
27};

Python

1
2python
3from threading import Lock
4
5class DiningPhilosophers:
6    def __init__(self):
7        self.mutex = Lock()
8
9    def wantsToEat(self,
10                   philosopher: int,
11                   pickLeftFork: 'Callable[[], None]',
12                   pickRightFork: 'Callable[[], None]',
13                   eat: 'Callable[[], None]',
14                   putLeftFork: 'Callable[[], None]',
15                   putRightFork: 'Callable[[], None]') -> None:
16        with self.mutex:
17            pickLeftFork()
18            pickRightFork()
19            eat()
20            putLeftFork()
21            putRightFork()

Java

1
2java
3import java.util.concurrent.locks.ReentrantLock;
4
5class DiningPhilosophers {
6
7    private ReentrantLock lock = new ReentrantLock();
8
9    public DiningPhilosophers() {
10        
11    }
12    
13    public void wantsToEat(int philosopher,
14                    Runnable pickLeftFork,
15                    Runnable pickRightFork,
16                    Runnable eat,
17                    Runnable putLeftFork,
18                    Runnable putRightFork) throws InterruptedException 
19    {
20        lock.lock();
21        pickLeftFork.run();
22        pickRightFork.run();
23        eat.run();
24        putLeftFork.run();
25        putRightFork.run();
26        lock.unlock();
27    }
28}

JavaScript

1
2javascript
3class DiningPhilosophers {
4    constructor() {
5        this.lock = false; // represent mutex lock
6    }
7
8    async wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) {
9        while (this.lock) {
10            await new Promise(resolve => setTimeout(resolve, 1)); // while waiting, do nothing
11        }
12        this.lock = true;
13        pickLeftFork();
14        pickRightFork();
15        eat();
16        putLeftFork();
17        putRightFork();
18        this.lock = false;
19    }
20}

C#

1
2csharp
3using System.Threading;
4
5public class DiningPhilosophers {
6    private Mutex mutex = new Mutex();
7
8    public DiningPhilosophers() {
9
10    }
11
12    // call the functions directly to execute, for example, eat()
13    public void WantsToEat(int philosopher, 
14                           Action pickLeftFork, 
15                           Action pickRightFork, 
16                           Action eat, 
17                           Action putLeftFork, 
18                           Action putRightFork) {
19
20        mutex.WaitOne();
21        pickLeftFork();
22        pickRightFork();
23        eat();
24        putLeftFork();
25        putRightFork();
26        mutex.ReleaseMutex();
27    }
28}

In all the above code snippets, we lock the mutex first, then pick up the left and right fork, eat, put down the left and right fork and finally unlock the mutex. The access to the critical section (picking up forks and eating) is synchronized using the mutex. Only one philosopher can execute the critical section at a time. The mutex ensures that when one philosopher is eating, no other philosopher can pick up their forks. After a philosopher is done eating, they put down both their forks and unlock the mutex, allowing other philosophers to pick up their forks and eat.This solution is decent as it prevents deadlock. However, in terms of fairness it does not ensure that all philosophers get their chance to eat. One philosopher can continually eat if they keep acquiring the mutex before other philosophers have a chance to.

To improve upon this solution, we can assign a Condition (monitor in Java) to each philosopher representing whether or not they are able to eat. The condition for a philosopher to be able to eat is that neither of their neighbours are currently eating. In the solution proposed below, we use an array to keep track of which philosophers are eating. When a philosopher wants to eat, they check if neither of their neighbours are eating. If they are, then the philosopher waits. When a philosopher is done eating, they signal their neighbours that they can eat.

Python

1
2python
3from threading import Lock, Condition
4
5class DiningPhilosophers:
6    def __init__(self):
7        self.lock = Lock()
8        self.eating = [False] * 5
9        self.cv = [Condition(self.lock) for _ in range(5)]
10
11    def wantsToEat(self,
12                   philosopher: int,
13                   pickLeftFork: 'Callable[[], None]',
14                   pickRightFork: 'Callable[[], None]',
15                   eat: 'Callable[[], None]',
16                   putLeftFork: 'Callable[[], None]',
17                   putRightFork: 'Callable[[], None]') -> None:
18        with self.lock:
19            self.cv[philosopher].wait_for(self.canEat, philosopher)
20            self.eating[philosopher] = True
21
22            pickLeftFork()
23            pickRightFork()
24            eat()
25            putLeftFork()
26            putRightFork()
27
28            self.eating[philosopher] = False
29            self.cv[(philosopher + 1) % 5].notify()
30            self.cv[(philosopher - 1) % 5].notify()
31
32    def canEat(self, philosopher: int) -> bool:
33        return not (self.eating[(philosopher - 1) % 5] or self.eating[(philosopher + 1) % 5])

The canEat method checks if any adjacent philosopher of the current philosopher is eating. If an adjacent philosopher is not eating then it returns True indicating success else it returns False.

Please note these solutions do not prevent philosopher starvation (where a philosopher never gets to eat). Sophisticated dining philosophers solutions do exist which prevent both deadlocks and starvation, however these solutions involve relatively advanced synchronisation primitives which are off topic for now.