The Dining-Philosophers Problem

• The dining philosophers problem is useful for modeling processes that are competing for exclusive access to a limited number of resources, such as I/O devices.
• Consider five philosophers who spend their lives thinking and eating.
• The philosophers share a circular table surrounded by five chairs, each belonging to one philosopher. In the center of the table is a bowl of rice, and the table is laid with five single chopsticks (see Fig. 11).

  Figure 11: The situation of the dining philosophers.

  
  • When a philosopher thinks, she does not interact with her colleagues.
  • From time to time, a philosopher gets hungry and tries to pick up the two chopsticks that are closest to her (the chopsticks that are between her and her left and right neighbors).
  • A philosopher may pick up only one chopstick at a time. Obviously, she cannot pick up a chopstick that is already in the hand of a neighbor.
  • When a hungry philosopher has both her chopsticks at the same time, she eats without releasing her chopsticks.
  • When she is finished eating, she puts down both of her chopsticks and starts thinking again.
• The dining-philosophers problem is an example of a large class of concurrency-control problems. It is a simple representation of the need to allocate several resources among several processes in a deadlock-free and starvation-free manner.
• One simple solution is to represent each chopstick with a semaphore.
  • A philosopher tries to grab a chopstick by executing a $wait()$ operation on that semaphore; she releases her chopsticks by executing the $signal()$ operation on the appropriate semaphores.
  • Thus, the shared data are

    semaphore chopstick[5] ;
    

    where all the elements of chopstick are initialized to 1.
  • The structure of philosopher $i$ is shown in Fig. 12.

    Figure 12: The structure of philosopher $i$.

    
  • Although this solution guarantees that no two neighbors are eating simultaneously, it nevertheless must be rejected because it could create a deadlock.
  • Suppose that all five philosophers become hungry simultaneously and each grabs her left chopstick. All the elements of chopstick will now be equal to 0. When each philosopher tries to grab her right chopstick, she will be delayed forever.
• One improvement to Fig. 12 that has no deadlock and no starvation is to protect the five statements following the call to think by a binary semaphore.
  • Before starting to acquire forks, a philosopher would do a down on mutex
  • After replacing the forks, she would do an up on mutex
• It has a performance bug: only one philosopher can be eating at any instant. With five forks available, we should be able to allow two philosophers to eat at the same time.
• Any satisfactory solution to the dining-philosophers problem must guard against the possibility that one of the philosophers will starve to death. A deadlock-free solution does not necessarily eliminate the possibility of starvation.
• The solution presented in Fig. 13 is deadlock-free and allows the maximum parallelism for an arbitrary number of philosophers. It uses an array, state, to keep track of whether a philosopher is eating, thinking, or hungry (trying to acquire forks).
• A philosopher may move only into eating state if neither neighbor (LEFT and RIGHT) is eating .

  Figure 13: A solution to the dining philosophers problem.

  
• The solution is deadlock-free and allows the maximum parallelism for any number of philosophers