餐饮哲学家:Chandy-Misra方法:如何避免僵局

Question

我正在尝试一下，但是一个问题：在维基中，该算法的第3点说：

当一个拿着叉子的哲学家收到请求信息时，如果叉子干净，他会保留叉子，但如果它脏了，他会放弃它。如果他把叉子送过来，他会在这样做之前清洗叉子

我试图理解为什么这不会导致僵局？ 如果一个哲学家有一个干净的叉子，并等待从邻近的餐馆/哲学家那里得到另一个干净的叉子，而另一个餐馆/哲学家又在等待一个叉子

，这可能会累积成一个死锁，对吗？ 一个哲学家总是在等待另一个哲学家的分叉？

ps：我是线程和并发的新手，把它作为一个学习项目。

编辑：给出分叉的实际位置，发布此内容以询问分叉是否应该可变。pLeft，pRight是左右哲学家，fLeft和fRight是左右叉。

private Fork giveFork(Philosopher diner) {
        Fork forkToGive;
        if (this.pLeft.equals(diner)) {
            // give left fork to left philosopher
            if (this.fLeft.isClean)
                forkToGive = null; // don't give
            else {
                forkToGive = new Fork(this.fLeft.id, true); // give the fork
            }
        } else if (diner.pRight.equals(this)) {
            // give right fork to right philosopher
            if (this.fRight.isClean)
                forkToGive = null;
            else {
                forkToGive = new Fork(this.fRight.id, true);
            }
        } else {
            // default value , i'm not yet sure if this code
            // can be theoretically reached
            forkToGive = null;
        }
        return forkToGive;
    }

我还没想好在哪里同步，但是我确实觉得还是需要同步的。 就像两个食客，说第一个和第三个向第二个哲学家要叉子。

Answer 1

你引用的来源解释了它：

但是，如果系统初始化为完全对称状态， 像所有哲学家拿着左叉一样，那么图表是 一开始是循环的，他们的解决方案无法防止僵局。 初始化系统，使ID较低的哲学家脏了 forks 确保图形最初是非循环的。

因此，您需要将系统初始化为非对称状态，并且规则集旨在不离开所需的(非死锁状态(。