The Dining Philosophers Problem

Topics

• The Dining Philosophers problem
• Introduction to deadlock
• Example of monitor solution using POSIX threads

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

• 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?

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:

• it illustrates the use of individual binary semaphores, in contrast to the monitor solution
• it illustrates the use of processes, in contrast to threads
• it illustrates a contrasting approach to dealing with deadlock
• it illustrates the use of lockfiles, the most traditional and most portable Unix mutual exclusion mechanism

Unix Mutual Exclusion Mechanisms

• lockfiles (e.g., see open(...O_CREAT | O_EXCL...))
• System V semaphores (e.g., see sema_wait)
• POSIX semaphores (e.g., see sem_wait)
• File record locking (e.g., see flock(), lockf, and fcntl(...F_SETFL...))
• POSIX mutexes, with attribute PTHREAD_PROCESS_SHARED

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);
}     

• The lock object is a file, with an agreed-upon pathname
• To obtain the lock:
  • try to create the file, using open ( ... O_CREAT | O_EXCL ... )
  • if this fails, sleep a while and then retry
  • when the file is eventually created, this process has the lock
• To release the lock:
  • unlink the file
• e.g., the Netscape browser uses .netscape/lock as a lockfile, and the printer spooling daemon in Linux uses /var/spool/lp/SCHEDLOCK as a lockfile

Weaknesses of this Solution

• How do we choose the length of time to sleep?
• What happens if it is too long?
• What happens if it is too short?
• What happens if the process dies while holding a lock?
  • Keep all maskable signals masked while holding a lockfile
    (see explanation of signals later)
  • Time out when waiting for a lockfile, and then steal the lock

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

• mutual exclusion must be enforced
• a process can halts in a noncritical section without interfering with other processes
• no indefinite delays (implies no deadlock or starvation)
• if no process is in a critical section, entry must be permitted without delay
• no assumptions about relative process speeds or number of processors
• a process remains inside its critical section for a bounded time

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

• chopsticks.h defines the interface
• chopsticks1.c is the implementation
• philosophers.c is a test driver main program

Variant Solution, using sigsuspend()

In the directory examples/philos

• chopsticks2.c is the alternate implementation

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.

• it illustrates the use of signals for process synchronization

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.