1226. The Dining Philosophers

MediumConcurrency

Problem Description

The Dining Philosophers problem is a classic synchronization problem involving five philosophers who do two things: think and eat. However, to eat, each philosopher needs to have both the fork to their left and the fork to their right. Since each philosopher shares a fork with their neighbor, they must coordinate fork usage to prevent deadlock, where everyone holds one fork and is waiting for the other, or starvation, where a philosopher is perpetually denied the opportunity to eat.

The philosophers are sitting at a round table, which creates a circular dependency in resource (fork) acquisition. The challenge is to implement a system that allows philosophers to pick up and put down forks in such a way that they can all continue eating and thinking indefinitely without any of them starving due to being unable to acquire the necessary forks.

The problem is to design a wantsToEat function conforming to the given method signature, which allows a philosopher to:

Pick up the left fork.
Pick up the right fork.
Eat spaghetti.
Put down the left fork.
Put down the right fork.

This function will be called multiple times in parallel, simulating each philosopher's attempt to eat.

Intuition

To tackle this problem, the key is to implement a protocol that ensures philosophers can alternately think and eat without causing a deadlock or starvation. By using mutual exclusion (mutex), we can avoid the situation where multiple philosophers can hold the same fork simultaneously, leading to a deadlock. The scoped_lock used in the solution automatically acquires locks for both the philosopher's left and right forks upon entering the wantsToEat method and releases them when the method completes. This ensures that the philosopher holds both forks while they eat and that the resources are properly released afterward.

In the given C++ solution, a std::scoped_lock is introduced for the mutex objects that represent the forks. A scoped_lock is a lock that manages multiple mutexes while maintaining a simplified lock interface. The implementation uses the scope of the lock to handle the acquisition and release of the mutexes. This lock ensures that both or neither of the forks are acquired, preventing deadlock since a philosopher will only begin eating when both forks are available.

To prevent neighboring philosophers from picking up the same fork at the same time, an array of five mutexes is used (mutexes_). Each index in the mutexes_ array corresponds to a philosopher and their right fork. The philosopher parameter determines which mutexes to lock. Since the philosophers are in a circle, we need to handle the case where the last philosopher (index 4) must lock the mutex at index 0 and index 4.

The solution elegantly ensures that each wantsToEat function call locks and releases the correct pair of forks atomically. The eat function will only be called when the philosopher has successfully picked up both the left and the right forks. The std::scoped_lock will automatically release the locks when it goes out of scope, which occurs when the philosopher finishes eating and the wantsToEat function exits. This ensures the forks are released in all scenarios, preventing a situation where a fork is left locked indefinitely, which would lead to starvation of a philosopher.

Solution Approach

The implementation of the solution primarily revolves around the concept of mutual exclusion, ensuring that only one thread (philosopher) can access a particular resource (fork) at any given time. The algorithm relies on the following elements:

Mutexes: Mutexes are used to represent the forks. A mutex is a synchronization primitive that can be used to protect shared data from being simultaneously accessed by multiple threads.
Scoped Locks: std::scoped_lock is a C++17 feature that simplifies the management of locking multiple mutexes. It locks the provided mutexes at the start of a block and automatically unlocks them when the block is exited. This is particularly useful to avoid common problems with locking such as deadlocks.
Vector of Mutexes: A vector with five mutexes represents the five forks on the table, corresponding to the five philosophers. Each index in this vector represents a philosopher's right fork (and the left fork of the philosopher to their right).
Locking Logic: For any given philosopher attempting to eat, they need to lock the mutexes corresponding to the forks on their left and right. To do this, we pass the current philosopher's mutex and the next philosopher's mutex (wrapping around using the conditional operator for the last philosopher) to the scoped_lock constructor. This ensures that both forks are locked simultaneously in a deadlock-free manner because scoped_lock uses a deadlock avoidance algorithm when acquiring multiple mutexes.

Here is a step-by-step breakdown of how the wantsToEat function works:

When a philosopher wants to eat, they call the wantsToEat function with their ID.
The function creates a scoped_lock, locking the mutexes corresponding to the philosopher's left and right forks. For the philosopher with ID 4, the locked mutexes are at index 4 and 0, as they will wrap around the table.
Once the locks are acquired, the philosopher can pick up both forks by calling the pickLeftFork and pickRightFork actions.
With both forks in hand, the philosopher then calls the eat action to simulate eating.
After eating, the philosopher puts down the forks by invoking putLeftFork and putRightFork actions.
The scoped_lock automatically releases the mutexes when the wantsToEat function exits the scope (at the end of the function), which allows other philosophers to then acquire these forks.

With this design, each philosopher can eat without causing deadlock or starvation, while also ensuring the concurrent access to the shared forks is properly managed.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach with just two philosophers for simplicity, even though the Dining Philosophers problem typically involves five. Imagine a table with two philosophers and two forks, one for each philosopher. When a philosopher wants to eat, they must follow the steps outlined in the solution approach.

Philosopher 0 decides they want to eat and calls wantsToEat(0).
The wantsToEat function for Philosopher 0 attempts to create a scoped_lock for the mutexes at indices 0 (Philosopher 0's right fork) and 1 (using modulus arithmetic, it's the left fork which is also Philosopher 1's right fork).
Because we're using the scoped_lock, it attempts to lock both mutexes at the same time. If successful, Philosopher 0 now has both forks, avoiding deadlock.
Philosopher 0 proceeds with the pickLeftFork and pickRightFork actions, simulating the action of picking up the forks.
After picking up the forks, Philosopher 0 calls the eat action to simulate eating the spaghetti.
Once done eating, in most implementations, Philosopher 0 would set down the forks with putLeftFork and putRightFork. However, in our automatic scope-based system, the forks are implicitly put down when the scoped_lock is released.
The scoped_lock reaches the end of its scope when the wantsToEat function for Philosopher 0 finishes. At this point, the lock is automatically released, and the forks are available again.

Now, let's say Philosopher 1 concurrently calls wantsToEat(1) while Philosopher 0 has not yet finished eating.

Philosopher 1 also tries to create a scoped_lock for their forks, which correspond to mutexes at indices 1 and 0 (indicating Philosopher 1’s right and Philosopher 0’s left fork, respectively).
However, since Philosopher 0 is already holding both forks, the scoped_lock for Philosopher 1 cannot immediately acquire the mutex at index 1; thus, Philosopher 1 must wait.
Once Philosopher 0's scoped_lock goes out of scope, the mutexes are released, and Philosopher 1 can now acquire the locks on both forks.
Philosopher 1 can now pick up both forks, eat, and once they're done, the scoped_lock will ensure that the forks are released.

This system ensures that no deadlock occurs because the forks are always picked up and put down in a controlled manner, and no philosopher can start eating without holding both forks. Moreover, starvation is avoided since each philosopher will get a chance to acquire both forks and eat as the scoped_lock ensures mutexes are eventually released for others to use.

Solution Implementation

1from threading import Lock
2
3class DiningPhilosophers:
4    """
5    Class representing the Dining Philosophers problem.
6    """
7
8    def __init__(self):
9        """
10        Initialize the DiningPhilosophers class with necessary locks for the forks.
11        """
12        # Initialize a list of 5 Locks, representing the 5 forks.
13        self.forks = [Lock() for _ in range(5)]
14
15    def wants_to_eat(self, philosopher, pick_left_fork, pick_right_fork, eat, put_left_fork, put_right_fork):
16        """
17        Method called when a philosopher wants to eat.
18
19        It ensures that no two philosophers can hold the same fork at the same time.
20        For the fifth philosopher, the right fork is considered to be the fork at index 0.
21
22        :param philosopher: The index of the philosopher who wants to eat [0-4].
23        :param pick_left_fork: Function to simulate picking up the left fork.
24        :param pick_right_fork: Function to simulate picking up the right fork.
25        :param eat: Function to simulate eating.
26        :param put_left_fork: Function to simulate putting down the left fork.
27        :param put_right_fork: Function to simulate putting down the right fork.
28        """
29
30        # Philosopher 4 (indexing from 0) has a different right fork compared to others.
31        right_fork_index = 0 if philosopher == 4 else philosopher + 1
32
33        # Acquire both forks using context management to ensure exception safety.
34        with self.forks[philosopher], self.forks[right_fork_index]:
35            # Simulate picking up left and right forks, eating, and putting down the forks.
36            pick_left_fork()
37            pick_right_fork()
38            eat()
39            put_left_fork()
40            put_right_fork()
41

1import java.util.concurrent.locks.Lock;
2import java.util.concurrent.locks.ReentrantLock;
3
4/**
5 * Class representing the Dining Philosophers problem.
6 */
7public class DiningPhilosophers {
8
9    // Alias for the action functions using Runnable, since Java does not have a std::function equivalent.
10    // Runnable is chosen as it represents an action that takes no arguments and returns no result.
11    public interface Action extends Runnable { }
12
13    // Array of ReentrantLocks representing the forks.
14    private final Lock[] forks = new ReentrantLock[5];
15
16    // Constructor initializes each lock representing a fork.
17    public DiningPhilosophers() {
18        for (int i = 0; i < forks.length; i++) {
19            forks[i] = new ReentrantLock();
20        }
21    }
22
23    /**
24     * Method called when a philosopher wants to eat.
25     * 
26     * @param philosopher The index of the philosopher [0-4].
27     * @param pickLeftFork Runnable action to pick up the left fork.
28     * @param pickRightFork Runnable action to pick up the right fork.
29     * @param eat Runnable action to perform the eating action.
30     * @param putLeftFork Runnable action to put down the left fork.
31     * @param putRightFork Runnable action to put down the right fork.
32     */
33    public void wantsToEat(int philosopher,
34                           Action pickLeftFork,
35                           Action pickRightFork,
36                           Action eat,
37                           Action putLeftFork,
38                           Action putRightFork) throws InterruptedException {
39        // The id of the left and right fork, taking into account the special case of the last philosopher
40        int leftFork = philosopher;
41        int rightFork = (philosopher + 1) % 5;
42
43        // Lock the forks to ensure that no two philosophers can hold the same fork at the same time.
44        // Locking is arranged to prevent deadlock.
45        forks[leftFork].lock();
46        forks[rightFork].lock();
47
48        try {
49            // Perform actions with the forks and eating in a critical section.
50            pickLeftFork.run(); // Pick up left fork
51            pickRightFork.run(); // Pick up right fork
52            eat.run(); // Eat
53            putLeftFork.run(); // Put down left fork
54            putRightFork.run(); // Put down right fork
55        } finally {
56            // Ensure that forks are always released to avoid deadlock.
57            forks[leftFork].unlock();
58            forks[rightFork].unlock();
59        }
60    }
61}
62

1#include <functional>
2#include <mutex>
3#include <vector>
4
5// Class representing the Dining Philosophers problem
6class DiningPhilosophers {
7public:
8    // Alias for the action functions
9    using Action = std::function<void()>;
10
11    // Method called when a philosopher wants to eat
12    void wantsToEat(int philosopher,
13                    Action pickLeftFork,
14                    Action pickRightFork,
15                    Action eat,
16                    Action putLeftFork,
17                    Action putRightFork) {
18        // Ensure no two philosophers hold the same fork at the same time
19        // For the fifth philosopher, we consider the fork to the right as the fork at position 0
20        std::scoped_lock lock(forks_[philosopher], forks_[philosopher == 4 ? 0 : philosopher + 1]);
21      
22        // Pick up left fork
23        pickLeftFork();
24      
25        // Pick up right fork
26        pickRightFork();
27      
28        // Eat
29        eat();
30      
31        // Put down left fork
32        putLeftFork();
33      
34        // Put down right fork
35        putRightFork();
36    }
37
38private:
39    // Mutexes representing the forks
40    std::vector<std::mutex> forks_ = std::vector<std::mutex>(5);
41};
42

1// TypeScript doesn't have mutexes, but we can simulate a lock using Promises and async/await.
2// Here's a simple lock implementation in TypeScript for educational purposes.
3class Lock {
4  private _isLocked: boolean = false;
5  private _waitingResolvers: Array<() => void> = [];
6
7  async acquire(): Promise<void> {
8    while (this._isLocked) {
9      // Wait until the lock becomes free
10      await new Promise(resolve => this._waitingResolvers.push(resolve));
11    }
12    this._isLocked = true;
13  }
14
15  release(): void {
16    if (!this._isLocked) {
17      throw new Error('Lock is already released');
18    }
19    this._isLocked = false;
20    const resolve = this._waitingResolvers.shift();
21    if (resolve) {
22      resolve();
23    }
24  }
25}
26
27// Alias for the action functions
28type Action = () => void;
29
30// Array representing the locks for the forks
31const forks = Array.from({ length: 5 }, () => new Lock());
32
33// Method called when a philosopher wants to eat
34async function wantsToEat(
35  philosopher: number,
36  pickLeftFork: Action,
37  pickRightFork: Action,
38  eat: Action,
39  putLeftFork: Action,
40  putRightFork: Action
41): Promise<void> {
42  // Calculate fork indices, ensuring the right fork index wraps for the fifth philosopher
43  const leftForkIndex = philosopher;
44  const rightForkIndex = (philosopher + 1) % 5;
45
46  // Acquire locks for the two forks asynchronously to simulate locking
47  await Promise.all([forks[leftForkIndex].acquire(), forks[rightForkIndex].acquire()]);
48
49  try {
50    // Once both forks are acquired, the philosopher can follow the eating procedure
51    pickLeftFork();   // Pick up left fork
52    pickRightFork();  // Pick up right fork
53    eat();            // Eat
54    putLeftFork();    // Put down left fork
55    putRightFork();   // Put down right fork
56  } finally {
57    // Always release the locks in the end, regardless of whether the actions succeeded or not
58    forks[leftForkIndex].release();
59    forks[rightForkIndex].release();
60  }
61}
62
63// Sample usage:
64// A philosopher would call the `wantsToEat` function with appropriate actions
65// In practice, proper synchronization primitives would be required to prevent race conditions
66

Time and Space Complexity

Time Complexity

The time complexity of the wantsToEat method in the DiningPhilosophers class isn't determined by a simple algorithmic analysis, because it's primarily dependent on the concurrency and synchronization primitives used (mutexes and locks). Each philosopher (in this case, a thread) attempts to pick up two forks (acquiring two mutexes) before eating. The std::scoped_lock is used to acquire both mutexes atomically, which prevents deadlock. The actual time complexity for each philosopher to eat depends on the order and time at which each thread is scheduled as well as contention for the mutexes.

However, assuming there is no contention and each operation (pickLeftFork, pickRightFork, eat, putLeftFork, and putRightFork) has a constant time complexity O(1), the wantsToEat function would have a time complexity of O(1) for each call in an ideal scenario. Acquiring and releasing a mutex can also be considered to have a time complexity of O(1).

Space Complexity

The space complexity of the DiningPhilosophers class is O(N) where N is the number of philosophers (which is 5 in this case). This is due to the vector<mutex> mutexes_ which contains a mutex for each philosopher's left fork. There are no additional data structures that scale with the number of operations or philosophers, so the space complexity is proportional to the number of philosophers.

In this code, since N is fixed at 5, you could argue that the space complexity can be considered as O(1) since it doesn't scale with input size and is fixed.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know