python - 哲学家就餐的非阻塞解决方案

Question

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

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

Answer 1

这是非阻塞算法的定义：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)

此解决方案使用比较和交换习语。

Answer 2

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

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

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

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

Answer 3

哲学家就餐问题是这样一个场景，你有 N 个哲学家围坐在一张圆桌旁，每个哲学家之间都有一个叉子。如果哲学家想咬一口，那么他或她必须拿起旁边的两个叉子中的一个，然后再拿起另一个叉子。哲学家取一个字节后，他或她放下两个叉子。

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