algorithm - 用餐哲学家 : Chandy-Misra approach : how does it avoid a deadlock?

Question

我正在尝试，但是有一个问题:在wiki ，该算法的第三点说:

When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so

我试图理解为什么这不会导致死锁？如果一位哲学家有一把干净的 fork ，并等待从邻近的用餐者/哲学家那里得到另一把干净的 fork ，而后者也在等待一把 fork ，这会累积成一个僵局吗？一位哲学家总是在等待另一位哲学家的 fork ？

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

编辑:给出 fork 的实际位置，张贴这个是为了询问 fork 是否应该是可变的。pLeft , pRight 是左右哲学家，fLeft 和 fRight 是左右 fork 。

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;

    }

还没想好在哪里同步，不过感觉还是需要同步的。就像两个用餐者一样，假设第一个和第三个向第二个哲学家要 fork 。

Answer 1

您引用的来源对此进行了解释:

However, if the system is initialized to a perfectly symmetric state, like all philosophers holding their left side forks, then the graph is cyclic at the outset, and their solution cannot prevent a deadlock. Initializing the system so that philosophers with lower IDs have dirty forks ensures the graph is initially acyclic.

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