COP4610: Operating Systems & Concurrent Programming up ↑

The Dining Philosophers Problem

 

Topics

What is the Dining Philosophers Problem?

*

A Java applet animation of the execution of the Dining Philosophers is given at http://www-ec.njit.edu/%7Emmr3411/Diners.html. (For links to some others, and a note about Java plugins, click here.)

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.

Significance of this Problem

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

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

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

How good is this solution?

  1. Is this solution subject to deadlock? If not, why not?
  2. 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.

Dining Philosopher Solution with Binary Semaphores, for Processes

void chopsticks_take (int i) {
  if (i == (NTHREADS - 1)) { lock (0); lock (NTHREADS - 1); }
  else { lock (i); lock ((i + 1) % NTHREADS); }
}
void chopsticks_put (int i) {
  unlock (i);
  unlock ((i + 1) % NTHREADS);
}

This example is for processes. It uses what are usually called "lockfiles" as conceptual binary semaphores. This is not to be confused with Unix file record locking locking (e.g., flock()) or the two kinds of Unix semaphores (e.g. sem_init and semget).

It is instructional in several ways:

Unix Mutual Exclusion Mechanisms

Of the list above, in this course we will only go into detail on lockfiles. That is because we have limited time. We chose lockfiles because they were the first interprocess mutual exclusion mechanism provided by Unix. Each of the other mechanisms either less general, less portable, or less simple. (This is not meant to imply they are not better, or should never be used on systems that support them.)

Lockfile Implementation of Binary Semaphore

void lock (int i) {
  int fildes;
  while ((fildes = open (lockfilename[i],
         O_RDWR | O_CREAT | O_EXCL, S_IRUSR | S_IWUSR)) == -1) {
    if (errno != EEXIST) chopsticks_emergency_stop();
    CHECK (usleep (100));
  }
  close (fildes);
}     
void unlock (int i) {
  CHECK (unlink (lockfilename[i]) == -1);
}     

Weaknesses of this Solution

Lockfiles are far from perfect binary semaphores. Stallings mentions six requirements for mutual exclusion:

How does this lockfile solution rate do on these requirements?

Regarding the recovery from process death: Why are the two solutions suggested only partial remedies? What is wrong with each of them?

How good is this solution?

  1. Is this solution subject to deadlock? If not, why not?
  2. Is this solution subject to starvation? Why or why not?
  3. Which of the defects of this solution, if any, is due to the lockfile implementation, versus the way the binary semaphores are used in the solution?

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

Dining Philosopher Lockfile Solution Complete Code

The complete code is in the directory examples/philos

Variant Solution, using sigsuspend()

In the directory examples/philos

This example differs from the previous one by using a signal to wake up waiting philosophers, instead of having them just sleep and recheck periodically.

Why is the word "maybe" in the name of the array variable "maybe_waiting[NTHREADS]"? That is, why can we not be certain whether a process is waiting or not?

Counting Semaphores

See the separate notes on semaphores.

T. P. Baker. ($Id)