CMSC 412


March 17, 1999

Dining Philosophers Problem

1. Problem statement

This problem is related to the mutual exclusion problem, and we use the notions of thinking, hungry, and eating from there.

There are five philosopher processes, numbered 0, 1, 2, 3, 4. There are five fork variables also numbered 0, 1, 2, 3, 4. ["placed" between the philosophers such that forks i and (i+1 mod 5) are next to philosopher i.] Each philosopher cycles through thinking, hungry, and eating states. To eat, philosopher i needs forks i and (i+1 mod 5). We want to ensure that

  1. Neighboring philosophers do not eat at the same time.

  2. A hungry philosopher eventually eats provided no philosopher stays eating forever.

  3. No busy waiting.

2. Solution attempt 1

Guard each fork i with a lock semaphore f[i] initialized to 1. To eat, philosopher i does a P on each of its forks.
Semaphore fLock[0..4] initially 1;  // fLock[i] controls access to fork i

Phil( i: 0..4 ) {  // code executed by philosopher i
  do forever {
    // become hungry
    P( fLock[i] );          // grab "right" fork
    P( fLock[i+1 mod 5] );  // grab "left" fork
    V( fLock[i] );          // release "right" fork
    V( fLock[i+1 mod 5] );  // release "left" fork

3. Solution approaches

Here are some approaches to solving the problem: