Dining philosophers

• 下载源代码 - 539Kb 

问题所在

五位哲学家花费他们所有的时间来吃饭和思考。他们居住的学院有一张餐桌，桌子中间有一大碗意大利面。桌上有五个盘子，盘子之间放着五双叉子。

吃意大利面需要使用两双叉子（通常，这个问题会用筷子而不是叉子来解释，因为要求用两根筷子吃意大利面比要求用两根叉子更容易理解），哲学家们一次只能拿起一双。哲学家们从不互相交谈，这会产生一种危险的可能性，即死锁，即每个哲学家都拿着左边的叉子，永远都在等待右边的叉子（反之亦然）。

这个问题 verbatim 地摘自 en.wikipedia.org 网站。在这篇文章中，我将提出一个简单的多线程解决方案，介绍如何安排所有哲学家用餐而不会争抢勺子。一如既往，我会进行大量解释。

解决方案

我们将哲学家编号为哲学家 1、哲学家 2、哲学家 3、哲学家 4、哲学家 5。

设

1. 哲学家 1 使用勺子 1 和勺子 5。
2. 哲学家 2 使用勺子 1 和勺子 2。
3. 哲学家 3 使用勺子 2 和勺子 3。
4. 哲学家 4 使用勺子 3 和勺子 4。
5. 哲学家 5 使用勺子 4 和勺子 5。

吃完饭的哲学家可以释放其他正在等待用餐的哲学家。所以我们有以下情况：

1. 哲学家 1 只能释放哲学家 2 或哲学家 5。
2. 哲学家 2 只能释放哲学家 3 或哲学家 1。
3. 哲学家 3 只能释放哲学家 4 或哲学家 2。
4. 哲学家 4 只能释放哲学家 5 或哲学家 3。
5. 哲学家 5 只能释放哲学家 1 或哲学家 4。

代码非常简单。有 5 个线程，每个线程代表一个哲学家，模拟吃饭和思考。代码对于每个哲学家来说基本上是相同的，但我重复了代码只是为了提高可读性。

这是我提出的多线程架构，它试图解决这类问题。其中一些如下所列。

1. Dining philosophers problem (哲学家吃饭问题)
2. Readers and writers problems (读者-写者问题)。

在某种条件下运行的每个线程都必须有进入标准和退出标准。只有在这两个标准之间，线程安全的条件代码才能执行。我将在我即将发表的文章中利用这个架构深入探讨读者-写者问题。目前，我将用它来解释“哲学家吃饭问题”的解决方案。

有一个 CRITICAL_SECTION 变量，它同步所有线程必须执行的进入和退出标准。有五个事件句柄，每个线程一个，需要时在上面进行等待，还有一个五元素的整数数组，代表勺子。这些元素中的每一个要么是 1，要么是 0（布尔值），0 表示勺子未被任何哲学家使用，1 表示勺子正在被某个哲学家使用。除此之外，我还有其他数据成员，但它们仅用于动画，因此我不会深入讨论。

每个哲学家线程将持续在一个 while(1) 循环中旋转。在循环开始时，有一个局部变量 nSHouldWait，一个布尔值，用于确定是让线程进入等待状态还是执行。

以下步骤说明了进入标准。

1. 在此进入临界区，EnterCriticalSection(&cs);。请参见下面的说明。
2. 检查我的勺子是否准备好吃饭 if(!sp[1] && !sp[5])
3. 如果我的勺子准备好吃饭，则将勺子变量设置为占用状态，sp[1]=sp[5]=1;
4. 这样我就不必等待，nSHouldWait=0;
5. 否则，从（2）开始，我的勺子不可用，其他哲学家正在使用它们，所以我不能吃。因此我将等待，nSHouldWait=1;
6. LeaveCriticalSection(&cs);
7. if(nSHouldWait)
8. 在我的事件上等待，直到我收到信号可以运行，WaitForSingleObject(hndEvents[1],INFINITE);

这是进入标准结束的地方。

注意：所有进入标准都必须由一个共同的临界区保护，否则全局变量的状态将不一致。同样，所有退出标准都必须被保护，因此我将同一个临界区用于这两种目的。

当代码完成进入标准后，意味着它要么有完全合法的运行权，要么需要等待。让我们以它将要运行（模拟哲学家吃饭）并且最终经过一段时间后完成吃饭的情况为例。那么是时候深入研究退出标准了。

退出标准在以下步骤中进行说明。

1. 定义一个局部句柄并将其初始化为 NULL，HANDLE hndTmp = NULL;
2. 由于我已经吃完饭，首先放弃我的勺子，sp[1]=sp[5]=0;
3. 因为哲学家 1 只能释放给哲学家 2 或哲学家 5。检查我是否可以先释放哲学家 2，if(!sp[1] && !sp[2]) 如果为真。
4. 如果可以，则将他的勺子设置为占用状态，sp[1]=sp[2]=1;
5. 并设置他的事件句柄，他正在等待吃饭，hndTmp = hndEvents[2];
6. 如果不行，则检查我是否可以释放哲学家 5，并对哲学家 5 重复上述步骤。
7. 最后离开临界区，LeaveCriticalSection(&cs);
8. 允许哲学家 2 或哲学家 5 中的一个吃饭，if(hndTmp != NULL) SetEvent(hndTmp);

这是退出标准结束的地方，哲学家 1 可以循环回并再次开始执行进入标准。

代码对于所有其他哲学家来说基本相同，只是勺子使用编号和事件句柄设置不同。要测试代码，可以更改用餐间隔，观察一段时间运行后，没有哲学家会挨饿。