Skip to content

DA3. The Dining Philosophers’ Problem

Statement

Discuss The Dining Philosophers (Figure 31.14) in terms of how “A Solution: Breaking The Dependency” improves upon the “Broken Solution”.

Solution

This text will refer to the philosophers as P1 to P5 and the forks as F1 to F5.

The Dining Philosophers’ Problem abstracts the problem of concurrency in a way that is easy to understand and visualize. It illustrates the problems that can arise when multiple threads are trying to access the same resources (Arpaci-Dusseau, Arpaci-Dusseau, 2012, 31.6).

The problem is as follows: Five philosophers are sitting around a circular table, each with a bowl of spaghetti. There are five forks on the table, one between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.

The problem arises if all the philosophers pick up the fork on their right and then wait for the fork on their left to become available. This will result in a deadlock, as each philosopher is holding on to one fork, waiting for the other fork to become available, and no fork will ever become available as all forks are picked.

The solution to this problem is to introduce a priority to the philosophers (depending on the philosopher’s ID). The philosopher with the highest priority will pick the right fork first and then pick the left fork.

Switching the order in the philosopher with the highest priority will break the dependency, and the deadlock will be avoided.

In the first round, P5 acquired his right fork, while three other philosophers got their left forks; there will be one philosopher that needs to wait for the next round and one fork will always be available (the fork on the left of P5).

So in the first round, only P5 will be able to eat, and the other philosophers will be waiting for their turn (three of them got one fork, and one has no fork).

In the next round, When P5 releases his both forks, P4 will get its 2 forks, then P3, then P2, and finally P1 will get its 2 forks. then the cycle will repeat with only one philosopher eating at a time.

References