为什么解决问题的monitor解决方案没有死锁，只有饥饿？

Question

从操作系统概念

5.8.2使用显示器的餐饮哲学家解决方案

接下来，我们通过对用餐哲学家问题提出一个无死锁的解决方案来说明监控概念。这个解决方案施加了一个限制，即哲学家只有在筷子都可用的情况下才能拿起筷子。为了给这个解决方案编码，我们需要区分我们可能找到哲学家的三种状态。为此，我们引入以下数据结构：

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

哲学家只有当她的两个邻居不吃饭时，我才能设置变量state[i]=EATING:（state[（i4）%5]！=吃）和（州[（i 1）%5]！=吃）。

我们还需要申报

condition self[5];

这使得哲学家i在饥饿但无法获得所需筷子时可以拖延时间。

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;
    }

}

图5.18问题的监视器解决方案。

每个哲学家在开始进食之前，必须调用操作pickup（）。这一行为可能导致程序暂停。手术成功后，哲学家可以吃东西。接下来，哲学家调用putdown（）操作。

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

很容易证明这个解决方案确保没有两个邻居同时吃饭，也不会发生死锁。

然而，我们注意到，哲学家有可能饿死。我们不提供这个问题的解决方案，而是将其留给您作为练习。

为什么显示器解决方案没有死锁？

为什么哲学家可能饿死？

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

谢谢




Answer 1

要理解为什么两个邻居不能同时吃饭，请看一下test（inti）方法。这是唯一一个哲学家的状态设置为吃的地方：

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

前面的if条件确保，对于任何哲学家来说，其邻居（i4）%5和（i1）%5都没有进食。

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