concurrency - 为什么 dining-philosopher 的监控解决方案没有死锁而是饥饿？

Question

来自操作系统概念

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.

为什么monitor方案没有死锁？

为什么哲学家有可能饿死？

这个问题的解决方案是什么？

谢谢。

Answer 1

要了解为什么两个邻居永远不能同时进食，请查看 test(int i) 方法。这是哲学家状态设置为 EATING 的唯一地方:

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

前面的 if 条件确保对于任何哲学家 i 它的邻居 (i + 4) % 5 和 (i + 1) % 5 正在吃东西。

饥饿是可能的，因为signal()这是不公平的:它随机唤醒任何等待的线程，因此可能在任意长的时间内都不会唤醒某个线程。