Dining philosophers problem and solution

The problem

Five philosophers sit around a circular table. Between each pair of philosophers there is one fork (five forks in all), and in front of each is a plate of spaghetti. A philosopher alternately thinks and eats; to eat, he needs both the fork on his left and the fork on his right. After eating he puts both forks down and thinks again.

        P0
    f4      f0
  P4          P1
    f3      f1
       P3 f2 P2

The problem models processes competing for exclusive access to a limited set of resources. Care is needed to avoid:

• Deadlock: if every philosopher picks up the left fork at the same time, each waits forever for the right fork.
• Starvation: a philosopher may never get both forks, while neighbours eat repeatedly.

A simple solution, where each philosopher does down(fork[i]) then down(fork[(i+1)%5]), is wrong because of the deadlock above. Waiting a random time before retrying avoids deadlock but is not guaranteed.

Solution using semaphores (Tanenbaum)

A philosopher may start eating only if neither neighbour is eating. An array state[] records THINKING, HUNGRY or EATING; a mutex protects state, and each philosopher has a semaphore s[i] on which he blocks if the forks are not available.

#define N        5                 /* number of philosophers */
#define LEFT     (i+N-1)%N         /* left neighbour of i */
#define RIGHT    (i+1)%N           /* right neighbour of i */
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                      /* state of each philosopher */
semaphore mutex = 1;               /* protects critical regions */
semaphore s[N];                    /* one semaphore per philosopher, all 0 */

void philosopher(int i) {
    while (TRUE) {
        think();
        take_forks(i);             /* get both forks or block */
        eat();
        put_forks(i);              /* release forks */
    }
}
void take_forks(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);                       /* try to acquire both forks */
    up(&mutex);
    down(&s[i]);                   /* block if forks were not acquired */
}
void put_forks(int i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);                    /* can left neighbour eat now? */
    test(RIGHT);                   /* can right neighbour eat now? */
    up(&mutex);
}
void test(int i) {
    if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

How it works: take_forks marks the philosopher HUNGRY and calls test; if both neighbours are not eating, he becomes EATING and up(s[i]) allows down(s[i]) to pass at once; otherwise he blocks. When he finishes, put_forks tests his left and right neighbours and wakes them if they are hungry and can now eat. This gives no deadlock and the maximum parallelism (two philosophers may eat together).