哲学家用餐问题

哲学家用餐问题是一个经典的同步问题，它描述了五位哲学家围坐在一张圆桌旁，他们的任务是交替地思考和用餐。桌子中央放着一碗面条，以及五双筷子，每位哲学家一双。为了用餐，一位哲学家需要同时拥有他的右筷子和左筷子。只有当哲学家左右两侧的筷子都可用时，他才能用餐。如果左右两侧的筷子都不可用，哲学家就会放下他（左或右）的筷子，重新开始思考。

哲学家用餐问题演示了一大类并发控制问题，因此它是一个经典的同步问题。

五位哲学家围坐在桌子旁

哲学家用餐问题 - 让我们通过以下代码来理解哲学家用餐问题。我们参考图1来帮助您准确理解这个问题。五位哲学家表示为 P0、P1、P2、P3 和 P4，五双筷子表示为 C0、C1、C2、C3 和 C4。

让我们讨论上述代码

假设哲学家 P0 想用餐，他将进入 Philosopher() 函数，并执行 take_chopstick[i];。通过这样做，他持有 C0 筷子。然后他执行 take_chopstick[ (i+1) % 5];。通过这样做，他持有 C1 筷子（因为 i = 0，所以 (0 + 1) % 5 = 1）。

同样，假设现在哲学家 P1 想用餐，他将进入 Philosopher() 函数，并执行 take_chopstick[i];。通过这样做，他持有 C1 筷子。然后他执行 take_chopstick[ (i+1) % 5];。通过这样做，他持有 C2 筷子（因为 i = 1，所以 (1 + 1) % 5 = 2）。

但实际上，筷子 C1 不可用，因为它已经被哲学家 P0 拿走了，所以上述代码会产生问题并导致竞态条件。

哲学家用餐问题的解决方案

我们使用信号量来表示筷子，这确实是哲学家用餐问题的解决方案。Wait 和 Signal 操作将用于哲学家用餐问题的解决方案，拿起筷子时可以执行 wait 操作，而释放筷子时可以执行 signal 信号量。

信号量：信号量是 S 中的一个整数变量，除了初始化外，只能通过两个标准的原子操作——wait 和 signal 来访问，其定义如下：

从上面 wait 的定义可以清楚地看出，如果 S 的值 <= 0，它将进入无限循环（因为 while 循环后面有一个分号；）。而 signal 的作用是增加 S 的值。

筷子的结构是一个信号量数组，如下所示：

最初，信号量 C0、C1、C2、C3 和 C4 的每个元素都初始化为 1，因为筷子在桌子上，没有被任何哲学家拿起。

让我们修改上面哲学家用餐问题的代码，使用信号量操作 wait 和 signal，所需的代码如下：

在上面的代码中，首先对 take_chopstickC[i] 和 take_chopstickC [ (i+1) % 5] 执行 wait 操作。这表明哲学家 i 已经拿起了他的左手和右手的筷子。之后执行 eating 函数。

哲学家 i 吃完后，对 take_chopstickC[i] 和 take_chopstickC [ (i+1) % 5] 执行 signal 操作。这表明哲学家 i 已经吃完，并放下了左右两双筷子。最后，哲学家又开始思考。

让我们看看上述代码是如何为哲学家用餐问题提供解决方案的？

令 i = 0（初始值），假设哲学家 P0 想用餐，他将进入 Philosopher() 函数，并执行 Wait( take_chopstickC[i] );。通过这样做，他持有 C0 筷子，并将信号量 C0 减为 0，然后他执行 Wait( take_chopstickC[(i+1) % 5] );。通过这样做，他持有 C1 筷子（因为 i = 0，所以 (0 + 1) % 5 = 1），并将信号量 C1 减为 0。

同样，假设现在哲学家 P1 想用餐，他将进入 Philosopher() 函数，并执行 Wait( take_chopstickC[i] );。通过这样做，他将尝试持有 C1 筷子，但无法做到，因为信号量 C1 的值已经被哲学家 P0 设置为 0，所以他将进入无限循环，因此哲学家 P1 将无法拿起筷子 C1。而如果哲学家 P2 想用餐，他将进入 Philosopher() 函数，并执行 Wait( take_chopstickC[i] );。通过这样做，他持有 C2 筷子并将信号量 C2 减为 0，然后他执行 Wait( take_chopstickC[(i+1) % 5] );。通过这样做，他持有 C3 筷子（因为 i = 2，所以 (2 + 1) % 5 = 3），并将信号量 C3 减为 0。

因此，上述代码为哲学家用餐问题提供了一个解决方案。哲学家只有在左右两边的筷子都可用时才能用餐，否则哲学家需要等待。同时，同一时间可以有两位独立的哲学家同时用餐（即哲学家 P0 和 P2、P1 和 P3 以及 P2 和 P4 可以同时用餐，因为它们都是独立的进程，并且它们遵循哲学家用餐问题的上述约束）。

上述哲学家用餐问题解决方案的缺点

从上述哲学家用餐问题的解决方案中，我们证明了没有两位相邻的哲学家可以同时用餐。这个解决方案的缺点是它可能导致死锁。这种情况发生在我们所有的哲学家同时拿起他们的左手筷子时，这导致了死锁，任何哲学家都无法用餐。

为了避免死锁，一些解决方案如下：

• 桌子上哲学家最多不应超过四位，在这种情况下，筷子 C4 将可供哲学家 P3 使用，因此 P3 将开始用餐，并在用餐完成后放下他的两双筷子 C3 和 C4，即信号量 C3 和 C4 将增加到 1。现在，持有筷子 C2 的哲学家 P2 也将获得筷子 C3，因此同样，他将在用餐后放下他的筷子，让其他哲学家用餐。
• 偶数位置的哲学家应该先拿起右手筷子，然后是左手筷子，而奇数位置的哲学家应该先拿起左手筷子，然后是右手筷子。
• 只有当左右两双筷子同时可用时，才允许哲学家拿起筷子。
• 所有开始的四位哲学家（P0、P1、P2 和 P3）应该先拿起左手筷子，然后是右手筷子，而最后一位哲学家 P4 应该先拿起右手筷子，然后是左手筷子。这将迫使 P4 首先持有他的右手筷子，因为 P4 的右手筷子是 C0，已经被哲学家 P0 持有，并且其值设置为 0，即 C0 已经是 0，因此 P4 将陷入无限循环，筷子 C4 保持空闲。因此，哲学家 P3 同时拥有左手 C3 和右手 C4 筷子，因此他将开始用餐，并在完成后放下他的两双筷子，让其他人用餐，从而消除了死锁问题。

该问题的设计旨在说明避免死锁的挑战。系统中的死锁状态是指系统无法取得任何进展的状态。考虑一个建议，指示每位哲学家按以下方式行事：

• 指示哲学家思考，直到左边的叉子可用。当它可用时，拿起它。
• 指示哲学家思考，直到右边的叉子可用。当它可用时，拿起它。
• 指示哲学家在两支叉子都可用时用餐。
• 然后，先放下右手叉子
• 然后，接着放下左手叉子
• 从头开始重复。