Problem Statement
The Dining Philosophers Problem is a classic resource-sharing synchronization problem. It is particularly used for situations, where multiple resources need to be allocated.
There are five philosophers sitting around a circular dining table. The table has a bowl of spaghetti and five chopsticks.
At any given time, a philosopher will either think or eat. For eating, he uses two chopsticks- one from his left and another from his right. When a philosopher thinks, he keeps down both the chopsticks at their place.
A fork can be held by only one philosopher at any given time i.e. no two philosophers can use the same fork. After a philosopher finishes eating, they put the forks back to their original places. A philosopher can only eat when both the forks are available to him, i.e. forks on his left and right should not be used by any other philosopher at the same time.
The problem is to design an effective algorithm, such that no philosopher has to starve, i.e. he can continue thinking and eating alternately for an indefinite amount of time.
Approach
This problem was structured to tackle the issue of deadlocks which occurs during multiple resource sharing on an operating system.
A deadlock is a situation in which two computer programs sharing the same resource are effectively preventing each other from accessing the resource, resulting in both programs ceasing to function.
Now let us understand how to effectively solve the Dining Philosophers Problem.
Let us consider the philosophers to be processed in an OS and the chopsticks to be shared resources. Now if we observe clearly, each process needs two resources, out of which, one of the resources it has already acquired, but another resource is in use for another process. Due to this, till the time the other process does not release its resource, the current process cannot proceed further.
In turn, the other processes are dependent on another process for its resources and this goes on and on.
Image Source – Google images
Therefore, every process is waiting for some other process, hence they are in a circular wait. This leads the system to a deadlock.
Let us consider the philosophers as P0, P1, P2, P3, P4, and chopsticks as C0, C1, C2, C3, C4
Algorithm
- P0 enters the process and since the system contains no other processes at the current moment, it acquires the resource C0 and C1.
- Now, process P1 enters the system. Since P0 is already acquiring the resource C0 and C1, P1 cannot acquire the process C1. Therefore, P1 keeps waiting until C1 gets freed, and after that, it can acquire the resources C1 and C2.
- Now, process P2 enters the system. Since resources C2 and C3 are both free, P2 acquires both.
- Now, process P3 enters the system. Since resource C3 has been acquired, it keeps waiting.
- Now, process P4 enters the system. Since resource C0 has been acquired, it keeps waiting.
- Now, let’s consider a situation, that process P0 completed eating. Hence, resource C0 and C1 gets freed. Therefore, process P4 starts acquires resources C0 and C4, since both are free.
Note: Process P1 cannot start executing, since C2 isn’t available.
- Now, if P2 completes executing, resource C2 and C3 becomes free, hence process P1 starts executing.
- Now, if P4 completes executing, resource C0 and C4 becomes free, hence process P3 starts executing.
Hence, by this design, every philosopher does not need to wait for an infinite amount of time, hence avoiding circular wait and no deadlock.
C++ Implementation
class DiningPhilosophers {
private:
// one mutex per fork
std::array<std::mutex, 5> mutexes;
public:
DiningPhilosophers() {
}
void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int left = philosopher;
int right = (philosopher + 1) % 5;
// ordered lock to avoid deadlock: fork with min number goes first
std::lock_guard<std::mutex> first(mutexes[std::min(left, right)]);
std::lock_guard<std::mutex> second(mutexes[std::max(left, right)]);
// do the work - fork order does not actualy matter here
pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork();
}
};
Java Implementation
class DiningPhilosophers {
private Semaphore[] leftForks, rightForks;
public DiningPhilosophers() {
leftForks = new Semaphore[5];
rightForks = new Semaphore[5];
for (int i = 0; i < 5; i++) {
leftForks[i] = new Semaphore(1, true);
rightForks[(i + 1) % 5] = leftForks[i]; // left fork of a philosopher is the right fork of the next philosopher, hence use the "same" semaphore (reference of the semaphore)
}
}
// call the run() method of any runnable to execute its code
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) throws InterruptedException {
leftForks[philosopher].acquire();
pickLeftFork.run();
rightForks[philosopher].acquire();
pickRightFork.run();
eat.run();
putLeftFork.run();
leftForks[philosopher].release();
putRightFork.run();
rightForks[philosopher].release();
}
}
Python Implementation
import threading
class DiningPhilosophers:
def __init__(self):
# List of semaphores, one for each fork
self.forks = [threading.Semaphore(1) for _ in range(5)]
# call the functions directly to execute, for example, eat()
def wantsToEat(self,
philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]') -> None:
# Take the right fork, then left fork
self.forks[philosopher].acquire()
self.forks[(philosopher + 1) % 5].acquire()
# Eat!
pickRightFork()
pickLeftFork()
eat()
putRightFork()
putLeftFork()
# Release right fork, then left fork
self.forks[philosopher].release()
self.forks[(philosopher + 1) % 5].release()
Time Complexity: O(N), where N is the number of processes or philosophers.
Frequently Asked Questions
What are the necessary conditions for deadlock?
There are four necessary conditions for deadlock-
- Mutual exclusion
- Hold and Wait
- No preemption
- Circular Wait
Does the above solution always guarantee no deadlock for the Dining Philosopher problem?
Dining the philosopher problem is a classic problem, The above approach is a solution that holds true for most of the situations, but there can still arise some situations when the system can get into a deadlock.
