用餐哲学家的非阻塞解决方案

Question

我被要求为 python 中的哲学家就餐问题编写一个简单的解决方案。这本身看起来很简单，但有些令人困惑，因为我被要求编写一个非阻塞解决方案。我不确定在这种情况下这是什么意思。

有没有人能给我任何提示或指出正确的方向？

Answer 1

哲学家就餐问题是这样一种场景，您有 N 位哲学家围坐在一个圆形 table 周围，并且每个哲学家之间都有一个叉子。如果哲学家想咬一口，那么他或她必须拿起旁边的两把叉子中的一把，然后再拿起另一把。哲学家吃了一个字节后，然后他或她放下两个叉子。

如果每个哲学家都拿起他们左边的叉子，这个场景就会阻塞。然后没人能拿起正确的叉子吃饭，他们都饿死了。一种解决方案是让每个哲学家都从拿起左边的叉子开始，除了一个将从拿起右边的叉子开始。

Answer 2

下面是非阻塞算法的定义：http://en.wikipedia.org/wiki/Non-blocking_algorithm.

这个问题的非阻塞解决方案的伪代码：

# The number of forks.
FORKS_COUNT = ... 

# Indicates if the i-th fork is taken or not.
taken = new bool[FORKS_COUNT] 

# The philosopherId is a position at the table.
def haveDinner(philosopherId):
    leftFork = philosopherId
    rightFork = (philosopherId + 1) % FORKS_COUNT
    if leftFork > rightFork:
        swap(leftFork, rightFork)
    while true:
        # Tries to take the left fork.
        while not compare_and_swap(taken[leftFork], false, true):
            # Do nothing.
        # Tries to take the right fork.
        while not compare_and_swap(taken[rightFork], false, true):
            # Do nothing.
        # Eats.
        ...
        # Returns the forks to the table.
        compare_and_swap(taken[leftFork], true, false)
        compare_and_swap(taken[rigthFork], true, false)

此解决方案使用 compare-and-swap 习语。

Answer 3

在问题的上下文中，非阻塞意味着没有死锁。也就是说，哲学家不会在已经拿着另一把叉子的情况下无限期地等待一把叉子。暂停意味着该线程出于调度目的而被禁用，并且在另一个线程专门恢复暂停的线程之前不会执行。解决方案必须避免无限期暂停或死锁（即 2 个或更多线程暂停等待彼此继续）。

该解决方案需要一个仲裁者，它可以自动授予两个分叉或拒绝请求。如果哲学家不能原子地拿走两个叉子，那么哲学家必须在随机的时间内思考生命、宇宙和其他一切。经过思考，哲学家再次请求仲裁员以原子方式获得两个叉子。在放弃两把叉子之前，进食也会随机延迟一段时间。所有的随机延迟都是有限的，有一个共同的上限，比如 10 秒或 10 分钟，随便什么。

此设计需要一种比较和交换机制来检查和有条件地更新位掩码，每个分叉一个位。该机制是原子的。两个位都更新或都不更新。

java 中的示例解决方案适用于任意数量的哲学家，它仅使用易失性字段并且没有 synchronized() 块或挂起锁，可在以下位置获得： sourceforge.net/projects/javamutex/

用餐哲学家的非阻塞解决方案

Non-blocking solution to the dining philosophers

python

algorithm

blocking

dining-philosopher