philos.html

The Dining Philosophers Problem

Topics

The Dining Philosophers problem
Example of how to code a monitor using the POSIX thread synchronization objects, mutexes and condition variables
Example of the danger of deadlock, and one way to prevent it

What is the Dining Philosophers Problem?

This is a classic example of a synchronization problem, described in terms of philosophers sitting around a table, eating noodles with chopsticks. Each philosopher needs two chopsticks to eat, but there are not enough chopsticks to go around. Each must share a chopstick with each of his neighbors, as shown in the figure.

The dining philosophers are a popular theme for people learning to write Java applets. Over the years, I have found several such applets, but when I put links to them in course notes the applets disappeared from the linked locations. However, if you search for keywords "dining philosophers applet" or "dining philosophers animation" you can probably find one.

Significance of this Problem

Potential for deadlock and starvation
Academic benchmark for evaluation and comparison of synchronization and mutual exclusion mechanisms
An example for demonstrating various process and thread synchronization mechanisms
A good solution has no deadlock or starvation

Possibility of Deadlock

If philosophers take one chopstick at a time, taking a stick from the left and then one from the right, there is danger of deadlock, as shown in the figure.

For example, if you run the applet using the link above, you will see that if it runs fast enough it will deadlock.

This possibility of deadlock means that any solution to the problem must include some provision for preventing or otherwise dealing with deadlocks.

Possibility of Starvation

If philosophers take two chopsticks at a time, there is a possibility of starvation, as shown in the figure. Philosophers B & E, and A & C can alternate in a way that starves out philosopher D.

This possibility of starvation means that any solution to the problem must include some provision for preventing starvation.

Review of Monitor Concept

Encapsulated data objects and procedures
(a.k.a. methods or functions)
Per-monitor lock enforces mutual exclusion
Only one thread may be executing in the monitor at a time
Thread inside the monitor may reliquish the monitor lock to wait for a condition
POSIX mutex and CVs designed to implement monitors

Dining Philosophers Solution as Monitor

int 
update_state (int i) {
  if (state[i] == HUNGRY
   && state[LEFT] != EATING
   && state[RIGHT] != EATING) {
     state[i] = EATING;
     pthread_cond_signal (&CV[i]);
  }
  return 0;
}
void
chopsticks_take (int i) {
   pthread_mutex_lock (&M);
   state[i] = HUNGRY
   update_state(i);
   while (state[i] == HUNGRY)
     pthread_cond_wait (&CV[i],&M);
   pthread_mutex_unlock (&M);
}

void
chopsticks_put (int i) {
  pthread_mutex_lock (&M);
  state[i] = THINKING;
  update_state (LEFT);
  update_state (RIGHT);
  pthread_mutex_unlock (&M);
}

This problem admits to a very simple solution using a monitor, as shown in the figure. The monitor's mutual exclusion is implemented using a POSIX mutex, M. There is a POSIX condition variable, CV for each philosopher. The other monitor data consists of an array of integers, representing the states of the philosophers, which are one of { HUNGRY, EATING, THINKING }. Besides the four entry functions (i.e., those that are callable from outside the monitor and go through the mutex, there is an internal function (which cannot be called from outside the monitor) that is called by the other functions to update the state.

Pay special attention to the update_state procedure. This design encapsulates the code for state updates in a form that can be shared by both entry procedures. If you adopt this style in your solution to the ferry problem, it will be simpler and more likely to work correctly.

The Complete Code

In directory examples/philos

chopsticks.h, the monitor interface
chopsticks0.c, the monitor implementation
philosophers_t.c, the main program

The full code for this solution is in the indicated files.

How good is this solution?

Is this solution subject to deadlock? If not, why not?
Is this solution subject to starvation? Why or why not?

After you have finished reading about deadlock, you should be able to answer these questions about the solution.