Why does the monitor solution to dining-philosopher have no deadlock but starvation?

Question

From Operating System Concepts

5.8.2 Dining-Philosophers Solution Using Monitors

Next, we illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available. To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure:

enum {THINKING, HUNGRY, EATING} state[5];

Philosopher i can set the variable state[i] = EATING only if her two neighbors are not eating: (state[(i+4) % 5] != EATING) and (state[(i+1) % 5] != EATING).

We also need to declare

condition self[5];

This allows philosopher i to delay herself when she is hungry but is unable to obtain the chopsticks she needs.

monitor DiningPhilosophers
{

    enum {THINKING, HUNGRY, EATING} state[5];
    condition self[5];
    void pickup(int i) {

        state[i] = HUNGRY;
        test(i);
        if (state[i] != EATING)
            self[i].wait();

    }
    void putdown(int i) {

        state[i] = THINKING;
        test((i + 4) % 5);
        test((i + 1) % 5);

    }
    void test(int i) {

        if ((state[(i + 4) % 5] != EATING) &&
        (state[i] == HUNGRY) &&
        (state[(i + 1) % 5] != EATING)) {
            state[i] = EATING;
            self[i].signal();
        }

    }
    initialization code() {

        for (int i = 0; i < 5; i++)
            state[i] = THINKING;
    }

}

Figure 5.18 A monitor solution to the dining-philosopher problem.

Each philosopher, before starting to eat, must invoke the operation pickup(). This act may result in the suspension of the philosopher process. After the successful completion of the operation, the philosopher may eat. Following this, the philosopher invokes the putdown() operation.

DiningPhilosophers.pickup(i);
...
eat
...
DiningPhilosophers.putdown(i);

It is easy to show that this solution ensures that no two neighbors are eating simultaneously and that no deadlocks will occur.

We note, however, that it is possible for a philosopher to starve to death. We do not present a solution to this problem but rather leave it as an exercise for you.

Why does the monitor solution have no deadlock?

Why is it possible for a philosopher to starve to death?

What is a solution to this problem?

Thanks.

Answer 1

To understand why two neighbours can never be eating at the same time have a look at the test(int i) method. This is the only place where a philosopher's state is set to EATING:

if ((state[(i + 4) % 5] != EATING) &&
    (state[i] == HUNGRY) &&
    (state[(i + 1) % 5] != EATING)) {
        state[i] = EATING;
        self[i].signal();
}

The preceding if condition ensures that for any philosopher i neither of its neighbours (i + 4) % 5 nor (i + 1) % 5 is eating.

Starvation is possible because signal() is not fair: it wakes up any of the waiting threads at random and might thus not wake up a certain thread for an arbitrary long time.