1. Problem statement

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

Semaphore fLock[0..4] initially 1;  // fLock[i] controls access to fork i

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

• Prove that this satisfies all the requirements except for starvation freedom.

• Provide a counter-example for the starvation-freedom requirement (it can deadlock).

3. Solution approaches

• Allow at most four philosophers to contend for eating. This can be done as follows: introduce a semaphore, say table, that is initialized to 4; do P(table) before attempting to grab a fork; do V(table) after releasing the last fork.

• Allow philosophers to pick up both forks at once or none. This can be done as follows: let the forks be boolean variables (indicating whether free or not); all access to the forks are in a critical section enforce by a semaphore; if a philosopher finds that the two forks needed are not free, it waits on a semaphore until the forks are free.

• Introduce asymetry: make odd numbered philosophers grab the left fork first and then the right fork; make even numbered philosophers grab the right fork first and then the left fork.

• Introduce asymetry: make one philosopher grab the left fork first and then the right fork; all others grab the right fork first and then the left fork.

• Associate timestamps with hungry philosophers and use them to break contention.