Problem description
Five philosophers are sitting around a dining table. Each has a plate in front of them, and five chopsticks are placed between them.
The philosophers have two statuses, which are thinking and eating. Before they begin to eat, they need to pick up both chopsticks one by one on their right and left sides, and they can pick up the chopstick only if it is not occupied. After they finish eating, they will put down both chopsticks. We need to ensure that each chopstick is only used by one philosopher at any time.
Imagine a scenario, for example, every philosopher is holding the right chopstick in their hand. There are no available chopsticks on the table, but none of the philosophers can eat, which results in starvation because of the deadlock. Here comes the problem of designing an algorithm to keep philosophers from starvation. In other words, the algorithm is expected to make the status of each philosopher alternate between thinking and eating forever.
In conclusion, there are two requirements for solving this problem, which are:
- Each chopstick can only be occupied by at most one philosopher at any time.
- None of the philosophers will starve, and everyone alternates between thinking and eating forever.
Importance
The scenario of the Dining Philosophers Problem is the epitome of concurrent threading and multi-processing in real-world computer systems. Philosophers refer to processes or threads, and chopsticks refer to resources that need to be shared. The Dining Philosophers Problem illustrates the need for synchronization mechanisms when multiple tasks ask for the same resources simultaneously to avoid problems like race conditions and deadlock, which may result in severe consequences. Moreover, as a simplified version of the concurrency problem for computer systems, it can be used as a platform for testing and verifying synchronization algorithms.
Solutions
To fulfill the first requirement stated above, we can use a mutex or binary semaphore for each chopstick. When the philosopher tries to pick up a chopstick, the lock() or wait() method will be called, and when the philosopher puts down a chopstick, unlock() or signal() method will be called. This mechanism ensures that each chopstick can be used by at most one philosopher at any time, but it fails to prevent deadlock.
To address the deadlock issue, the followings are some of the approaches.
The Waiter Solution
The waiter solution provides a simple way to solve the Dining Philosophers problem, assuming an external entity called the waiter (St Olaf College, 2018). Before eating, the philosophers will first ask for the left chopstick and then the right. The waiter is responsible for granting access to chopsticks. If only one chopstick is left idle, only the request for the right chopstick will be approved. Imagine a case of four philosophers, each holding their left chopstick. The request is denied when the fifth one asks for the left chopstick. Thus the first philosopher can pick up the right chopstick and eat. After the first philosopher puts down the chopsticks, the third can eat. Everyone will be able to eat in this mechanism.
William Stallings' Solution
A solution presented by William Stallings is to allow a maximum of n-1 philosophers to sit down at any time (Wikipedia, 2023). In the scenario of 5 philosophers, four are allowed to try to eat at a time. Imagine a case of four philosophers, each holding their left chopstick. The fourth philosopher still has access to the right chopstick and can eat. After finishing eating, the philosopher puts down both chopsticks, and the third philosopher can eat. In this way, everyone will not starve.
Symmetrical solution
The symmetrical solution is that an even philosopher should pick the right chopstick and then the left chopstick, while an odd philosopher should pick the left chopstick and the right chopstick (Kristi Castro, 2020). The mechanism ensures that between every adjacent philosopher if one is holding one chopstick but not able to acquire another one, the adjacent philosopher who is using that chopstick can be proved eating. The adjacent philosophers can eat when the eating philosopher puts down the chopsticks.
Applicability
As stated above, the solutions to this problem are epitomes of concurrency control mechanisms, as philosophers refer to threads or processes, and chopsticks refer to shared resources.
Solutions to the Dining Philosopher problem. (2018, October 3). In St Olaf College. https://www.stolaf.edu/people/rab/pdc/text/dpsolns.htm
Dining philosophers problem. (2023, February 4). In Wikipedia. https://en.wikipedia.org/wiki/Dining_philosophers_problem
Dining Philosophers Problem (DPP). (2020, June 24). By Kristi Castro. https://www.tutorialspoint.com/dining-philosophers-problem-dpp
