Monitor; dining philosophers with semaphore

Monitor

A monitor is a high-level synchronization construct: a package of procedures, variables and data structures, with the rule that only one process may be active in the monitor at any instant. The compiler adds the mutual exclusion automatically, so the programmer does not code locks. Inside it, condition variables with the operations wait(c) (block and release the monitor) and signal(c) (wake one waiting process) are used to synchronize processes. Example: producer-consumer with insert() and remove() procedures.

Dining philosophers using semaphores

Five philosophers alternate between thinking and eating; each needs the two forks beside him. A philosopher may eat only if neither neighbour is eating. The solution below uses an array state[], a mutex for the critical regions, and one semaphore per philosopher on which he blocks when forks are not available. It avoids deadlock; neighbours are tested whenever forks are put down.

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

Explanation

1. take_forks(i): inside the mutex, the philosopher sets HUNGRY and calls test(i). If left and right neighbours are not eating, he sets EATING and does up(s[i]). Then he leaves the mutex and does down(s[i]); this passes immediately if he got the forks, otherwise he blocks.
2. put_forks(i): sets THINKING and tests the left and right neighbours. A hungry neighbour who can now eat is woken by up(s[neighbour]).
3. Two non-adjacent philosophers can eat together, so concurrency is maximum, and the forks are never held while waiting, so deadlock cannot occur.