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

Question

我正在尝试,但是一个问题:在wiki中,该算法的第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的哲学家具有脏叉,确保图形最初是非循环的.

因此,您需要将系统初始化为非对称状态,并且该组规则的设计不会留下所需的(非死锁状态).