3

从操作系统概念

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

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

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

state[i] = EATING只有当她的两个邻居不吃饭时，哲学家 i 才能设置变量：(state[(i+4) % 5] != EATING)并且 (state[(i+1) % 5] != EATING).

我们还需要声明

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

很容易证明，该解决方案确保没有两个邻居同时进食，并且不会发生死锁。

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

为什么监控解决方案没有死锁？

为什么哲学家会饿死？

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

谢谢。

4

1 回答 1

3

要了解为什么两个邻居永远不能同时吃饭，请查看该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()是不公平的：它随机唤醒任何等待的线程，因此可能不会在任意长时间内唤醒某个线程。

于 2017-10-23T11:46:07.270 回答