用并发浏览器解决哲学家进餐问题

引言

在计算机科学中，哲学家就餐问题是一个常用于并发算法设计中的示例问题，用以说明同步问题及其解决方法。哲学家就餐问题最初由 Edsger Dijkstra 在1965年作为一个学生考试练习题提出，不久后由 Tony Hoare 完善为现在的形式。维基百科对该问题的描述如下：

“五位沉默的哲学家坐在一张圆桌旁，面前都有一碗意大利面。在每两位相邻的哲学家之间都放着一把叉子。

每位哲学家必须交替进行思考和吃饭。然而，一位哲学家只有在同时拿到左右两边的叉子时才能吃意大利面。每把叉子一次只能被一位哲学家持有，因此一位哲学家只有在叉子未被他人使用时才能使用它。当一位哲学家吃完饭后，他们需要放下两把叉子，以便其他人可以使用。哲学家可以在左边或右边的叉子可用时拿起它，但在拿到两把叉子之前不能开始吃饭。

吃饭不受限于剩余的意大利面数量或胃容量；假设供应和需求都是无限的。

问题在于如何设计一种行为准则（一种并发算法），使得没有哲学家会饿死；也就是说，每位哲学家都可以永远在吃饭和思考之间交替，前提是任何哲学家都无法知道其他人何时想要吃饭或思考。”

在急于编写自己的解决方案之前，不妨考虑使用 Concurrency Explorer (ConcX) 来解决哲学家就餐问题。ConcX 是 Avian Computing Project 推出的一个免费、开源的工具。ConcX 是一个交互式工具，旨在帮助我们思考并行问题；ConcX 鼓励我们将并行问题/程序想象成一群鸟，每只鸟都独立行动和操作，但同时也与鸟群中的其他鸟合作。ConcX 将各种线程状态映射到鸟类的自然行为中，例如孵化 (thread.start)、小睡 (thread.sleep)、死亡 (thread.stop) 等，以便更容易地思考和描述每个线程的动作。将程序的任务分解为一组可以独立执行的原子操作（每只鸟执行一个）的思维过程，可以产生一个可扩展的并行解决方案。

设置 ConcX 运行哲学家就餐问题

以下截图显示了用于选择鸟类类型以及如何配置它们的 ConcX GUI。该 GUI 还允许在实时查看每只鸟在其进度条上的活动时，启动或停止整个鸟群或单个鸟。

为了解决哲学家就餐问题，我们添加了五只“鸟”（选项卡 #2 - #6）来创建一个新的鸟群。每只鸟都有自己的选项卡，因此可以独立配置。在这种情况下，每只鸟都被配置为“吃”两种食物，分别称为 Fork1Pod 到 Fork5Pod。为了布置餐桌，还添加了一只“服务员”鸟（它在布置好餐桌后就消失了，这似乎是世界各地服务员的常态）。

请注意，ConcX 下载包中包含了解决哲学家就餐问题以及其他各种并行问题所需的所有鸟类和食物对象，例如生产者-消费者问题、并行计算 Pi、睡眠理发师问题等。

解决哲学家就餐问题

点击“全部启动”按钮（左下角），将为鸟群中的每只鸟启动一个 SwingWorker 线程。哲学家们（鸟/线程）将全部开始吃饭，这可以通过它们各自不断增长的活动进度条来体现。30秒后（它们的默认生命周期），所有哲学家都将因达到其（可配置的）生命周期终点而死亡，它们的线程也将全部终止。如果你没有耐心，也可以点击“全部停止”按钮，它们将全部停止吃饭，并终止各自的线程。

好了，就是这样。问题解决了。ConcX 提供了解决哲学家就餐问题所需的所有工具和必要框架。所有哲学家都共享了他们的叉子，并且吃饭的次数大致相等，没有一个饿死。

“等等！！”我几乎能听到你在说，“不可能这么简单。给我看看它是如何工作的。”

哲学家就餐解决方案详解

以下截图显示了所有哲学家在全部启动后不久的进度。每个进度条都根据其对应的哲学家吃饭的次数进行实时独立更新。在这种情况下，它们的进度条长度大致相同，表明它们在相当公平地分享，尽管培根（Bacon）在吃饭方面比其他人稍微逊色一些。

这个哲学家就餐问题的解决方案之所以有效，是因为每个哲学家在 ConcX 中都是一个 BasicBird，这使得它们都继承了标准的鸟类生命周期。如生命周期图所示，一旦一个 BasicBird 被孵化出来，它就会寻找其指定类型的食物，消化它找到的任何食物，储存相应类型的食物，然后小睡片刻。它会重复这个循环，直到老死、饿死，或者你按下停止按钮。

BasicBird 的生命周期恰好可以映射到哲学家就餐问题的描述中：每个哲学家试图拿起两把叉子，这映射到鸟的“寻找食物”阶段；吃意大利面是在“消化食物”阶段进行的；放下叉子发生在“储存食物”阶段；而思考则是在“小睡”阶段完成的（这也是我所有最佳思考的时刻）。

回到我们的示例运行，培根吃饭的频率不如其他哲学家。请注意，每个哲学家都可以通过其选项卡上的“启动我”按钮单独启动。如果你想看培根多吃点，可以点击他的选项卡（#3），然后点击他的“启动我”按钮；他将开始吃饭，并且将是唯一一个进度条在增长的哲学家。实际上，他的进度条会比以前增长得更快，因为他不必分享。

以下截图显示了在给培根一个大吃大喝的机会之后的结果；他的活动选项卡进度条现在比其他进度条更长。

“等等，”我几乎能听到你在说，“不断增长的进度条并不能证明任何事情。我想看到一些证据，证明确实发生了什么。”

要真正了解运行期间发生了什么，请在 GUI 屏幕上点击右上角的 TupleTree 选项卡。这将显示每个 ForkPod 的“历史记录”（见以下截图）。每个食物 Pod 的历史记录都会被记录下来，因此你随时可以回顾和分析在该食物 Pod 最近一次运行期间发生的事件。

在这部分放大的屏幕中，Fork2Pod 由亚里士多德（Aristotle）和培根（Bacon）共享；TupleTree 选项卡允许你查看每个食物 Pod 精确到毫秒的独立历史记录。请注意，在运行开始时，Fork2Pod 由亚里士多德和培根平均共享，但在屏幕中部左右，亚里士多德变得“贪婪”并独占了 Fork2Pod，然后在这部分屏幕的底部又开始更均匀地分享。如果你向下滚动 Fork2Pod 的历史记录，可以看到培根是唯一活跃的哲学家并且是唯一使用 Fork2Pod 的时间段，这与他更长的进度条相符。你还可以向下滚动并查看 TupleTree 中所有其他食物 Pod 的历史记录。

TupleTree 讨论

ConcX 中的 TupleTree 是 元组空间（tuplespace）的简化版本，这个概念最初是为 Linda 协调语言 开发的；元组空间 是一个用作数据元组仓库的共享关联内存。Linda 于1986年由 Sudhir Ahuja、David Gelernter、Nicholas Carriero 等人发起。Linda 成为多个主要产品的基础，包括 Sun 的 JavaSpaces、IBM 的 TSpaces，以及其他多种语言的许多产品。

在 ConcX 中，TupleTree 主动管理所有共享对象（食物 Pod）。在这个问题中，当一个哲学家试图拿起一把叉子时，他实际上是在向 TupleTree 请求一种特定类型的食物 Pod。如果 TupleTree 中不包含所请求类型的食物 Pod，哲学家将一无所获，这意味着他没能拿起叉子，于是回去思考（小睡）一段随机的时间。

然而，如果 TupleTree 确实包含所请求的食物 Pod（Fork1Pod、Fork4Pod 等），TupleTree 会移除所请求的 Pod 并将其交给请求它的哲学家，该哲学家现在就独占了那个食物 Pod（叉子）的唯一实例。在哲学家放下它（将其存回 TupleTree）之前，没有其他哲学家可以访问、更改或修改那把叉子。

TupleTree 的一个有趣且极其方便的副产品是，BasicBird 的代码不包含并行编程逻辑，如互斥锁、信号量、锁等。所有并行编程代码/逻辑都已从 BasicBird（数据使用者）中分离出来，并且只存在于 TupleTree 代码（数据仓库）中。TupleTree 拥有对数据仓库的独占访问权，并管理所有的锁定代码，所以你无需操心。

在 ConcX 中防止死锁

回到最初的问题描述：当一个哲学家成功拿起他的第一把叉子后，他会尝试拿起他的第二把叉子。这正是通常可能发生死锁的地方，因为可能会出现这样的情况：每个哲学家都拿着他们的第一把叉子，却无法拿到第二把，因为第二把叉子正被他们邻座的哲学家拿着。

ConcX 默认避免了死锁情况，因为 BasicBird 在尝试获取第二份食物（叉子）失败达到可配置的次数后会放弃，并放下第一把叉子，使其对邻座可用。BasicBird 之所以能表现得如此得体，是因为它们从不阻塞等待它们的叉子。相反，它们只需等待一毫秒左右，直到 TupleTree 返回所请求的食物 Pod 或一个空的食物 Pod，后者意味着所请求的食物 Pod 不在 TupleTree 中。在 ConcX 中，收到一个空的食物 Pod 是一种正常情况；就像现实生活中的鸟儿一样，没有找到食物的 BasicBird 只会继续它们的生命周期，并在下一次生命周期循环中再次寻找食物。

为了演示死锁预防的工作原理，可以通过点击特定鸟的编号选项卡，然后点击其独立的“历史”选项卡来查看其生命周期事件。在 ConcX 中，每只鸟总会记录其最近一次运行期间发生的事件。以下截图显示了亚里士多德最近一次运行的部分历史记录。所显示的历史记录部分始于他寻找食物但一无所获，于是他小睡了160毫秒。当他醒来后，他寻找食物，拿到了 Fork1Pod，然后尝试了三次才拿到 Fork2Pod（他的第二把叉子）。接着他吃饭、消化并放下他的叉子（将它们存回 TupleTree），以便其他哲学家可以使用。经过一番劳累后，他小睡了50毫秒（注意这次小睡的随机持续时间），然后再次寻找食物。每个事件都有时间戳，因此你可以与 TupleTree 选项卡上的食物 Pod 事件进行交叉核对。

ConcX 专门设计为一个用于实验的交互式环境：至此，你已拥有足够的信息来下载 ConcX 并开始对哲学家就餐问题进行实验。例如，你可以轻松地进行以下实验：

• 将一只或多只鸟的生命周期更改为100秒、10分钟或任何期望的时长。
• 降低一位哲学家的“耐心”（一个可配置的值），让他只尝试一次获取第二把叉子，然后就放弃并放下第一把叉子。
• 增加一位哲学家的耐心，看看如果他尝试10次而不是默认的5次来获取第二把叉子，结果会如何改变。
• 缩短一位哲学家的小睡时间，看看如果他更频繁地检查可用叉子会发生什么。他的渴望（贪婪）会导致更频繁地吃饭吗？一个更贪婪的哲学家将如何影响他的邻居？如果邻居们也变得贪婪会怎样？

这些实验以及更多实验都可以通过简单地更改哲学家的配置、清除之前的活动/结果并重新启动哲学家来运行。通过增加更多哲学家，还可以进行更多的实验。例如：

• 增加第六位哲学家，但不增加叉子。只需点击“添加新鸟”按钮，给它一个名字，选择一种鸟的类型，然后选择要吃和储存的叉子，并重新启动模拟。
• 再增加五位哲学家（总共10位），但不增加叉子，这样餐桌上的每个位置都有两位哲学家共享相同的两把叉子。
• 如果是一个更大的桌子，有10位哲学家和10把叉子呢？
• 在不增加叉子数量的情况下，最多可以喂饱多少位哲学家而没有任何一个饿死？

ConcX 使探索这些可能性以及更多可能性变得容易，所有这些都无需编码。如果你喜欢某个模拟或结果，可以将其保存为一个新的鸟群文件，以便以后重新加载和运行。

如果你愿意进行一些编码，可能性是无穷的。例如，一个机会主义的哲学家会怎么样？他会使用任何可用的叉子，只要能找到两把未被使用的叉子就会吃饭。如果一把或多把叉子是弯曲或扭曲的，哲学家们是否会尝试交换叉子以获得更好的叉子？

背景

并行程序的开发时间太长。近十年来，多核机器已成为大多数现代计算机的标准CPU，但大多数软件仍在努力充分、均衡地利用这些核心。如果软件能够跟上硬件的步伐，那么16核或128核的CPU可能早已成为常态。

Avian Computing Project 的初衷是，如果我们能更好地可视化和描述并行程序应如何运行，我们就能缩短开发并行程序所需的时间。这一洞见促使我们寻找一个能够自然且内在地展现并行行为的模型；我们选择了鸟群作为该项目的模型，尽管鱼群、蜂群或犬群也可以同样被选择。

这些模型使我们能够轻松地思考单个个体的所需行为，然后同样轻松地思考整个群体，以及对一个个体所做的改变如何影响整个群体。此外，使用来自自然的模型可以更容易地创建单个线程操作的心理图像，因为线程生命周期中的各个阶段可以映射到动物生命周期中易于理解的阶段。想要证据吗？试着向一个5岁的孩子解释一个多线程程序是如何工作的。现在，试着向同一个5岁的孩子解释一群鸟如何做一些有用的事情，孩子就会理解了。

将鸟类模型与编写并行代码的标准方式进行对比，后者通常是在我们怀疑多个线程可能访问某个共享资源的任何地方，在代码中散布互斥锁和锁。通常，我们无法预测各个线程何时会访问共享资源，也无法预测系统何时会中断一个线程，所以我们所能做的就是尽力想象所有可能导致问题的情况，然后进行测试，并希望我们能找到任何我们未曾预料到的实际故障情况。

ConcX 的开发旨在提供一个交互式环境，让开发者能够利用鸟类模型（鸟群）轻松地表示群体中的单个成员，然后实验这些个体如何协同工作以并行方式完成程序的目标。ConcX 提供了各种预构建的对象，可以轻松定制以满足几乎任何程序要求，从而为开发者简化和加速工作。ConcX 还将所有锁定和同步操作结构化并限制在共享的 TupleTree 对象中，从而将任何不当访问对象的问题仅限于 TupleTree。

Using the Code

以下代码演示了如何创建一种新型的鸟，这通常通过扩展 BasicBird 然后重写适当的方法来完成。在哲学家就餐问题中，Waiter 是一种特殊用途的鸟，其唯一的工作就是将五把叉子放到桌子上（放入 TupleTree）。完整的代码如下所示，只需要47行（包括注释和空行），去掉空行后只有38行，去掉注释和空行并将独立的 curly braces 移到其他行上后只有24行。

public class Waiter extends BasicBird {

   /**
    * The waiter sets the table for the philosophers by putting forks
    * into the TupleTree
    */
   @Override
   public void findFood() { //overridden so will store the forks in TupleTree
       Fork1Pod f1 = new Fork1Pod(); //creates a new instance of a Fork1Pod
       f1.setEmpty(false);           //The ForkxPods are all predefined food
       mEatBeak1.storeItem(f1, this);//pods that are used as forks

       Fork2Pod f2 = new Fork2Pod();
       f2.setEmpty(false);
       mEatBeak1.storeItem(f2, this);

       Fork3Pod f3 = new Fork3Pod();
       f3.setEmpty(false);
       mEatBeak1.storeItem(f3, this);

       Fork4Pod f4 = new Fork4Pod();
       f4.setEmpty(false);
       mEatBeak1.storeItem(f4, this);

       Fork5Pod f5 = new Fork5Pod();
       f5.setEmpty(false);
       mEatBeak1.storeItem(f5, this);

       addToBirdHistory("Table is Set - Ready to Terminate", Level.INFO);
       setStopNow(true); //this thread can now be terminated
   }

   /**
    * This method does nothing and prevents the regular digestFood method
    * from making any changes to any of the forks.
    */
   @Override
   public void digestFood() { }

   /**
    * This method does nothing and prevents the regular storeFood method from
    * storing any additional forks.
    */
   @Override
   public void storeFood () { }
}

创建新的食物 Pod (ForkxPod) 同样简单，因为它扩展了 BasicPod 并为其分配了唯一的标识符。以下是创建 Fork9Pod 的完整代码。

package com.avian.foods.philos;
import com.avian.foods.basefoods.BasicPod;

public class Fork9Pod extends BasicPod {

   /**
    * Default (and only) constructor for this food, it calls the BasicPod
    * constructor with reasonable values for its variables
    */
   public Fork9Pod()
       super("phl09","Fork9Pod"); //constructor params = treeID, desc
       this.setPodType("Fork9Pod");
   }
}

BasicBird 代码包含许多存根方法，为定制任何继承自 BasicBird 的鸟的行为提供了方便的方式。例如，可以重写诸如 beforeDigesting 和 afterStoring 等方法，以获得确切期望的行为，而无需修改 BasicBird 代码。

要了解更多关于 Avian Computing 和为 ConcX 编程的信息，请下载《Avian Computing 入门 - 使用 ConcX 探索并行编程》，该文档可在 aviancomputing.net 或 SourceForge 上的 Avian Computing 页面获取。

关注点

也许 ConcX 最有趣的方面之一是它没有像大多数并行程序那样，有一个设置和/或控制线程的 main() 函数。这带来了一些有趣的 ramifications：

• ConcX 程序的线程可以随意独立启动和停止，因为它们不是在 main() 函数或某个设置方法中预定义或编译的。它们作为独立的线程运行，只要满足它们自身的继续运行标准，就会一直运行下去。
• ConcX 线程是松散耦合的。它们不知道其他线程的存在，也从不直接与其他线程通信；相反，数据块（食物 Pod）通过 TupleTree 进行异步共享。这意味着代码永远不需要为增加或删除线程而修改。
• 松散耦合的线程还允许通过简单地改变鸟类吃和储存的食物来改变或重新安排鸟群的行为。例如，在哲学家就餐问题中，哲学家们可以不与邻居共享叉子，而与对面坐的哲学家共享，只需改变哲学家们吃的食物即可。
• 松散耦合的半自治线程提出了一个可能性，即可能会出现一个特殊用途鸟类对象的市场。例如，有人可以开发和销售一种地址格式化鸟，它以客户信息为输入，并产生一个格式正确的地址作为输出。

结论

希望本文已经证明，使用 ConcX 的对象、工具和功能来解决哲学家就餐问题是相对简单的。与大多数哲学家就餐问题的解决方案不同，ConcX 还提供以下功能：

• 关于每位哲学家吃饭成功率的实时视觉反馈，因此很容易验证他们中没有一个在挨饿，并且他们在共享叉子。
• 一个真正的异步解决方案，其中每个线程都可以独立启动/停止，而不会中断（或使程序崩溃）。
• 事件记录工具，可自动捕获运行时信息，以便进行详细的事后分析。
• 能够重新配置各个哲学家并立即重新运行哲学家就餐问题，以测试配置更改的影响。

ConcX 是一个通用解决方案，旨在为开发人员提供一个环境，帮助他们思考并行程序。ConcX 的设计允许开发人员专注于他们的程序需要做什么，而不是专注于如何编写安全共享数据和资源的代码。

历史

• 2018年5月7日：初次提交