65.9K
CodeProject 正在变化。 阅读更多。
Home

使用 Concurrency Explorer 解决“睡着的理发师”问题。

nchamberlain
starIconstarIconstarIconstarIconstarIcon

5.00/5 (1投票)

2018年7月27日

CPOL

14分钟阅读

viewsIcon

8978

“睡着的理发师”问题是一个经典的进程间通信问题，与使用标准的并行或异步编码技术相比，使用 Concurrency Explorer 等工具进行研究和探索会更加容易。

引言

Concurrency Explorer (ConcX) 提供了探索和解决各种并行或异步问题的工具和功能，包括“睡着的理发师”问题，维基百科对其描述如下：

“在计算机科学中，“睡着的理发师”问题是操作系统之间多个进程之间一个经典的进程间通信和同步问题。该问题类似于如何在有顾客时让理发师工作，在没有顾客时休息，并以有序的方式进行。

该类比基于一家假设的理发店，只有一位理发师。理发师有一个理发椅在理发室，以及一个包含若干椅子的等候室。当理发师完成为顾客理发后，他会解散顾客并前往等候室查看是否有其他等待的顾客。如果有，他会带一位顾客到椅子旁理发。如果没有，他会回到椅子上睡觉。

每位顾客到来时，都会查看理发师在做什么。如果理发师在睡觉，顾客会叫醒他并坐在理发椅上。如果理发师正在理发，顾客会留在等候室。如果等候室有空椅子，顾客就会坐下并等待。如果等候室没有空椅子，顾客就会离开。”

维基百科文章随后讨论了各种并发问题，例如：

  • 理发师和新来的顾客同时查看对方的状态，导致死锁，因为在那一刻

    • 理发师看到椅子上没有人，认为等候室是空的，于是去睡觉

    • 顾客认为理发师很忙，所以不尝试叫醒理发师，只是耐心等待理发师

  • 两位顾客同时到达，看到理发师已经很忙，然后都试图坐同一把椅子，导致：

    • 两位顾客都试图占用同一把椅子，或者

    • 两位顾客都未能获得椅子，因此两位顾客都离开了

取决于进程间通信的定义是否完善，也可能发生其他并发问题。但别走神，开始在脑海中规划你的代码解决方案，先考虑使用 ConcX 来解决“睡着的理发师”问题。

解决“睡着的理发师”问题

Concurrency Explorer (ConcX) 是一个免费的开源工具，可从 Avian Computing Project 获取。ConcX 是一个交互式 GUI 工具，旨在帮助我们思考并行问题。ConcX 鼓励我们将并行问题/程序想象成一群鸟，每只鸟都独立地（吃、睡等）运作，但也会与其他鸟群竞争与合作。

Customer、Barber、ShopManager 和 Chair 对象都包含在 ConcX 的下载中。您可以逐个添加一个或多个这些对象，也可以直接加载标准 ConcX 下载中包含的 barbershop20cust.bird 文件。此文件将加载并配置一个理发师、一个店铺经理和二十个顾客。

对象加载完成后，ConcX 将显示如下截图：

左侧的编号选项卡代表已加载并配置为理发师和顾客角色的鸟。您可以单击各个选项卡以查看每个鸟的配置详细信息。屏幕中央是鸟的名称和类型列表，旁边是它们的个人进度条。每当一只鸟（理发师、顾客或店铺经理）成功“进食”时，其进度条就会增长。进度条是实时更新的，因此无需等到运行完成即可查看每个线程是否按预期工作。

单击屏幕左下角的“Start All”（全部开始）按钮。ConcX 屏幕右侧的活动进度条将开始增长，这与每个鸟成功进食的次数相关（参见下图）。

每个顾客的进度条仅在他们实际等待时才会增长。每个顾客的到达时间都已预先配置，因此他们不会同时到达。当顾客找不到椅子时，他们就会放弃并离开。如果顾客等待时间过长（单独配置），他们就会放弃并离开。成功理发的顾客（或放弃的顾客）将终止其线程，其进度条将停止增长。

每次理发师理发时，他的进度条都会增长；如果只有一个顾客，理发师的进度条只会增长一次。只有店铺经理的进度条在整个运行过程中会持续增长，因为他会不断检查发型报告的更新。当他的进度条停止增长时，单击屏幕右上角的 TupleTree 选项卡，查看运行结果。本文稍后将详细介绍 TupleTree。

“睡着的理发师”结果

下图显示了运行标准的“睡着的理发师”解决方案后 TupleTree 的内容。DailyTransactionPod 包含由 ShopManager 生成并持续更新的报告。

报告包括：

  • 接受理发的顾客姓名以及为他们理发的理发师姓名

  • 未能找到椅子或耐心耗尽而离开的顾客姓名。两者都代表了错失的机会。

  • 按理发师列出的理发列表

  • 被叫但缺席的顾客列表

请注意，顾客均按字母顺序排列。这是因为顾客 #1 至 #20 都按字母顺序命名并按此顺序到达。这使得我们可以轻松确定顾客是否确实按到达顺序获得理发。

这是从 TupleTree 屏幕复制的完整报告：

Customers Completed Report
       CustName  Arrvd At  Start At  FinishAt  $Paid    BarberName
       Adambb9   17:001    17:060    18:060    $10.00   Zeb
       Bertc4a   17:919    18:075    20:075    $20.00   Zeb
       Chada24   18:937    20:098    23:099    $30.00   Zeb
       Dave9e1   20:954    23:133    24:633    $15.00   Zeb
       Evanb05   22:972    24:662    27:163    $25.00   Zeb
       Greg14f   27:007    27:549    29:550    $20.00   Zeb
       Hanka66   27:026    29:605    32:606    $30.00   Zeb
       Ivan42a   27:045    32:631    34:132    $15.00   Zeb
       Jake3da   31:060    34:167    36:668    $25.00   Zeb
       Kentbd3   33:077    36:679    37:680    $10.00   Zeb
       Lukebe8   34:096    37:746    39:747    $20.00   Zeb
       Mark2f9   36:113    39:756    42:756    $30.00   Zeb
       Natef97   37:131    42:764    44:265    $15.00   Zeb
       Otto7d3   39:149    44:302    46:803    $25.00   Zeb
       Todde18   42:233    48:249    50:750    $25.00   Zeb
       -----------------------------------------------

Customers Who Gave Up or Couldn't Find a Chair
       CustName   Arrvd At   Gave Up At
       Fredc86    23:089     26:100    
       Petec74    39:170     39:170    
       Quin77b    39:189     39:189    
       Rami325    39:207     39:207    
       Stan621    39:226     39:226    
       -----------------------------------------------

Barber Productivity Report
       Barber Name   Haircut Amt    Haircut Time
       Zeb           $10.0          10  minutes
       Zeb           $20.0          20  minutes
       Zeb           $30.0          30  minutes
       Zeb           $15.0          15  minutes
       Zeb           $25.0          25  minutes
       Zeb           $20.0          20  minutes
       Zeb           $30.0          30  minutes
       Zeb           $15.0          15  minutes
       Zeb           $25.0          25  minutes
       Zeb           $10.0          10  minutes
       Zeb           $20.0          20  minutes
       Zeb           $30.0          30  minutes
       Zeb           $15.0          15  minutes
       Zeb           $25.0          25  minutes
       Zeb           $25.0          25  minutes
       -----------------------------------------------

Barber Called Absent Customer Report
       Barber Name  Cust Name  Called At
       Zeb          Fredc86    27:534
       Zeb          Petec74    47:166
       Zeb          Quin77b    47:482
       Zeb          Rami325    47:841
       Zeb          Stan621    48:202
       -----------------------------------------------

请注意，有 5 位顾客放弃等待（1 位等待时间过长，4 位找不到椅子）。报告显示 Fred 等待了大约 3 秒后放弃，这与他 3 秒的耐心设置相符。其他 4 位顾客的到达时间和离开时间几乎相同，这表明他们都因为找不到椅子而离开。由于 Otto、Pete、Quin、Rami 和 Stan 的到达时间相差不到 80 毫秒，这表明他们都是同时到达的，但只有 Otto 找到了椅子并接受了理发。

让我们看看做一些小小的改变会如何影响结果。

探索“睡着的理发师”的可能性

下图显示已选择了选项卡 #1（Mr Smith，店铺经理），并且也选择了他的 Externally Managed Variable (XMV) 选项卡。“Chairs in Waiting Room”（等候室椅子）字段为空，这意味着 ShopManager 放置了默认数量的椅子（3 把）。通过将 XMV 字段更新为 5，我们可以重新运行模拟，看看增加椅子数量是否能解决问题。无需重新编译。

单击右下角的“Clear All Activities”（清除所有活动）按钮，然后单击屏幕左下角的“Start All”（全部开始）按钮。

以下报告节选显示了放弃等待的顾客：

Customers Who Gave Up or Couldn't Find a Chair
       CustName   Arrvd At   Gave Up At
       Fredbd3    39:798     42:904   
       Rami226    55:812     55:812   
       Stan7f5    55:819     55:819   
       -----------------------------------------------

 

<meta charset="utf-8" />

现在只有三位顾客放弃了：Impatient Fred 和那五位同时进来的顾客中的最后两位。如果我们增加几把椅子，清除结果然后重新运行模拟，报告的“Customer Gave Up”（顾客放弃）部分将只包含 Impatient Fred。

但是，如果理发店很小，放不下 7 把椅子呢？为了仅在 5 位或更多顾客同时到达的罕见情况下扩大店铺，成本将相当高。让我们看看如果我们增加第二位理发师而不是增加椅子会发生什么。

首先，单击选项卡 #1，将 Mr Smith 的“Chairs in Waiting Room”值留空/归零。

接下来，单击“Add New Bird”（添加新鸟）按钮（屏幕底部中间），并添加一个新的 Barber 鸟，如下所示：

单击“Add New Bird”按钮，然后：

  • （鸟）类型：在 Type 字段中输入“bar”，然后按 Tab 键。ConcX 将找到多个以“bar”开头的鸟类类型，并弹出显示所有匹配项的 ComboBox。如果尚未突出显示，请选择 Barber.class，然后单击 OK 按钮。

  • 进食：在 Food Type 字段中输入“bar”，然后按 Tab 键。ConcX 将找到多个以“bar”开头的食物豆，并弹出显示所有匹配项的 ComboBox。如果尚未突出显示，请选择 BarberBacklogPod，然后单击 OK 按钮。

  • 储存食物：在 Food Type 字段中输入“null”，然后按 Tab 键。ConcX 将只找到一个匹配的食物豆，并填充 NullPod 的完整名称。

  • 给理发师起一个恰当的随意名字，例如 Yank 或 Willy。

  • 单击理发师的“Vitality”（活力）选项卡，将其“Stamina”（耐力）更改为负数，例如 -5000。负数可以防止鸟在长时间不进食的情况下死亡。

单击“Clear All Activities”（清除所有活动）按钮，然后单击“Start All”（全部开始）按钮。

运行完成后，店铺经理的结果将与以下类似：

Customers Completed Report
       CustName  Arrvd At  Start At  FinishAt  $Paid    BarberName
       Adam81e   57:134    57:136    58:136    $10.00   Zeb
       Bertfaa   58:050    58:084    00:085    $20.00   Yank
       Chad422   59:067    59:079    02:079    $30.00   Zeb
       Dave5a8   01:085    01:121    02:620    $15.00   Yank
       Evan447   03:102    03:108    05:608    $25.00   Zeb
       Freda5f   05:118    05:137    06:137    $10.00   Yank
       Greg4a4   07:135    07:142    09:142    $20.00   Zeb
       Hankac2   07:153    07:191    10:191    $30.00   Yank
       Ivan8fe   07:171    09:171    10:672    $15.00   Zeb
       Jake753   11:185    11:240    13:740    $25.00   Yank
       Kent3a6   13:203    13:235    14:235    $10.00   Zeb
       Luke0cb   14:219    14:233    16:233    $20.00   Yank
       Nate4cf   17:253    17:275    18:775    $15.00   Zeb
       Mark0b8   16:236    16:252    19:253    $30.00   Yank
       Petedb7   19:290    19:321    20:321    $10.00   Yank
       Otto736   19:272    19:299    21:798    $25.00   Zeb
       Quin94d   19:309    20:330    22:330    $20.00   Yank
       Toddee5   22:354    22:371    24:870    $25.00   Yank
       -----------------------------------------------

Customers Who Gave Up or Couldn't Find a Chair
       CustName   Arrvd At   Gave Up At
       Ramif1e    19:327     19:327    
       Standec    19:346     19:346    
       -----------------------------------------------

Barber Productivity Report
       Barber Name   Haircut Amt    Haircut Time
       Zeb           $10.0          10  minutes
       Yank          $20.0          20  minutes
       Zeb           $30.0          30  minutes
       Yank          $15.0          15  minutes
       Zeb           $25.0          25  minutes
       Yank          $10.0          10  minutes
       Zeb           $20.0          20  minutes
       Yank          $30.0          30  minutes
       Zeb           $15.0          15  minutes
       Yank          $25.0          25  minutes
       Zeb           $10.0          10  minutes
       Yank          $20.0          20  minutes
       Zeb           $15.0          15  minutes
       Yank          $30.0          30  minutes
       Yank          $10.0          10  minutes
       Zeb           $25.0          25  minutes
       Yank          $20.0          20  minutes
       Yank          $25.0          25  minutes
       -----------------------------------------------

Barber Called Absent Customer
       Barber Name  Cust Name  Called At
       Zeb          Ramif1e    22:124
       Zeb          Standec    22:457
       -----------------------------------------------

 

<meta charset="utf-8" />

关于这些结果有几点需要注意：

  • 有了两位理发师，Impatient Fred 得到了理发，因为他不必等待太久。

  • 只有两位顾客因为找不到椅子而放弃。

  • “Completed Customers”（完成的顾客）报告按理发完成顺序而非到达顺序列出顾客。这表明理发师们在协作但异步工作；一位理发师不必等待另一位理发师完成，而是始终去处理等待时间最长的顾客。

  • 店铺经理知道是哪位理发师进行了哪些理发，而无需重新编程。

让我们增加第三位理发师，看看会发生什么。单击“Add New Bird”（添加新鸟）按钮，然后按照上述说明添加另一位 Barber 鸟。现在单击“Clear All Activities”（清除所有活动），然后单击“Start All”（全部开始）。

重新运行模拟后，我们得到以下结果：

Customers Who Gave Up or Couldn't Find a Chair
       CustName   Arrvd At   Gave Up At
       Ramibea    11:000     11:000    
       Stanf61    11:018     11:018    
       -----------------------------------------------

<meta charset="utf-8" />这个结果表明增加第三位理发师并没有帮助；仍然有两位顾客找不到椅子。所以，让我们解雇第三位理发师（通过将其类型更改为 Not Found 来禁用他的线程），并将等候室的椅子数量更改为 4。现在，当我们清除所有活动并启动所有活动时，20 位顾客中的每一位都能获得理发。

这意味着我们已经确定了两种不同的方式来服务每一位顾客：

  • 通过将等候室椅子数量增加到 7 把
  • 通过增加一位理发师，并将等候室椅子数量增加到 4 把

 

<meta charset="utf-8" />

ConcX 概念

让我们看一下 ConcX 的基本概念。利用 Avian Computing 的思想，ConcX 将各种线程状态映射到鸟类的自然行为，如孵化（thread.start）、打盹（thread.sleep）、死亡（thread.stop）等，以便更容易地思考和描述每个线程的动作。每只鸟都遵循一个标准的生命周期；一旦孵化，它们就会寻找食物，如果找到特定种类的食物就会消化，储存任何产生的食物（就像有些鸟会藏起剩饭），然后小睡。当鸟类年龄太大或吃不饱时，它们就会死亡。以自然术语表达线程的动作是为了使其更轻松、更自然地思考线程。

 

<meta charset="utf-8" />

ConcX 中的每个“鸟”（线程）都消耗一种食物豆，并在“TupleTree”中储存一种食物豆。“TupleTree”是 ConcX 中 元组空间 的简化版本，这是最初为 Linda 协调语言 开发的一个概念。元组空间 是用作元组数据存储库的共享关联内存。Linda 最初于 1986 年由 Sudhir Ahuja、David Gelernter、Nicholas Carriero 等人创建。Linda 是许多主要产品的基础，包括 Sun 的 JavaSpaces、IBM 的 TSpaces 以及各种语言中的许多其他产品。

在 ConcX 中，TupleTree 是一个单例，它使用同步方法与所有鸟类共享数据。TupleTree 中的任何对象都可以被任何知道如何请求该类型对象的鸟类检索。由于 TupleTree 使用同步方法管理其对象，因此用户无需创建或编写互斥锁、锁或其他用于并发对象共享对象的机制。相反，TupleTree 管理所有数据共享，因此您可以专注于需要对数据进行的操作。

传统的 wait 和 notify 并发工具就像一个传统的电话系统；如果你拨打的电话对方在线，那效果非常好。不幸的是，如果双方不能同时在线，就什么都做不了。

Linda 更像一个电子邮件系统，发送者和接收者会方便地检查和回复电子邮件，而不是相互打断。在 ConcX 中，TupleTree 就像一个电子邮件服务器，但它存储着充当共享资源的食物豆。通过这种方式，Linda 为多个异步线程之间的数据共享提供了一种安全、简单且健壮的机制。

ConcX 中的运行时信息

ConcX 最初的目标之一是提供对其运行时上下文的即时访问，了解每个线程在运行时发生的情况。为此，ConcX 提供的信息比实时更新进度条更多。ConcX 以多种方式自动记录每次运行，包括：

  • TupleTree 中的每个食物豆都有一个完整的带时间戳的历史记录，记录了该食物豆发生的所有事件以及是哪个鸟导致了该事件。

  • 每只鸟都维护自己的带时间戳的事件历史记录，例如何时寻找食物、找到了什么食物、何时消化并储存了食物等等。

以下节选将有助于说明如何使用记录的信息。首先，从运行结束时留在 TupleTree 中的 Chair-2 食物豆，我们可以看到 Bert 何时坐在椅子上（该次运行中坐在 Chair-2 上的所有顾客也都有记录）。

11:14:23:853,WaitingRoomChairPod,Bert78b found a chair in waiting room
11:14:24:127,WaitingRoomChairPod,Bert78b gave up chair to get haircut

 

<meta charset="utf-8" />

接下来，这是来自 Customer #2，Bert 的个人历史记录节选，可在其 History（历史记录）选项卡上找到：

11:14:23:853,Bert,Bert78b found a chair in waiting room
11:14:23:853,Bert,Created CustInfoFindByNamePod,Bert78b
11:14:23:853,Bert,Created BarberBacklogPod,Bert78b
11:14:23:853,Bert,Looking for food,
11:14:23:853,Bert,eating foodType,Bert78b
11:14:23:853,Bert,Napping,107ms
11:14:23:961,Bert,Looking for food,
11:14:23:961,Bert,eating foodType,Bert78b
11:14:23:961,Bert,Napping,166ms
11:14:24:127,Bert,Looking for food,
11:14:24:127,Bert,eating foodType,Bert78b
11:14:24:127,Bert,bird lifetime was set to 40300 millis
11:14:24:127,Bert,haircut in process

 

<meta charset="utf-8" />

Bert 的历史记录显示，他在 23:853 时找到了一把空椅子（Chair #2）。等待了大约 250 毫秒（寻找食物和打盹）后，Bert 在 24:127 时记录了他的理发正在进行中。

为了交叉验证信息，理发师（Zeb）的历史记录显示他在 23:963 时在睡觉，然后从等待列表（BarberBacklogPod）中获取了下一个名字，然后叫了他（Bert）。在 Bert 小睡 166 毫秒（从 23:995 到 24:127）的短暂延迟后，期望的理发（2000 毫秒）就完成了（从 23:995 到 25:996）。

11:14:23:963,Zeb,Napping,32ms
11:14:23:995,Zeb,Looking for food,
11:14:23:995,Zeb,Got 1 pods from TupleTree
11:14:23:995,Zeb,eating foodType,barbershop\BarberBacklogPod,Zeb
11:14:23:995,Zeb,Called Bert78b for haircut
11:14:23:995,Zeb,BEFORE Haircut retrieved Bert78b info on attempt 0
11:14:25:996,Zeb,AFTER Haircut retrieved Bert78b info on attempt 0
11:14:25:996,Zeb,ATE_FOOD1-->strFood1 NullPod,STORE_ONE by,barbershop\Barber
11:14:25:996,Zeb,Napping,49ms

虽然上面显示的节选仅确认了理发店按预期运行，但当出现问题时，食物豆和鸟类的组合历史记录最有价值。带时间戳的历史记录条目使得在遇到错误时，能够重建运行时上下文，直至每个线程的状态。

 

<meta charset="utf-8" />

“睡着的理发师”结论

ConcX 解决“睡着的理发师”问题的方案比维基百科上描述的原始问题复杂得多，它允许有多个理发师、近乎实时报告的店铺经理、不耐烦的顾客等等。与大多数其他解决方案相比，它更容易运行和修改，同时提供了更好的保证，证明它完成了预期的工作。ConcX 解决方案在扩展时也非常健壮；下面的截图显示了当 barbershop flock 文件加载五次并运行时会发生什么。所有 5 位理发师、所有 5 位店铺经理和所有 100 位顾客都按预期工作。

本文展示了 ConcX 在探索并发程序解决方案方面的一些优势，包括：

  • 用于配置和运行多个并发线程的 GUI 环境。

  • 根据需要添加新线程。

  • 在运行期间随时启动和停止单个线程或所有线程。

  • 简单地修改单个线程设置，以帮助识别哪些设置是关键的，哪些是不重要的。

  • GUI 屏幕上每个线程进度的实时更新，为用户提供即时视觉反馈。

  • 共享数据对象的带时间戳事件历史记录，包括是哪个鸟（线程）拥有该数据对象。

  • 每次运行的每个鸟（线程）的带时间戳事件历史记录，并为每个鸟选择不同的详细程度。

ConcX 的设计旨在支持在健壮的高反馈环境中快速轻松地进行修改，以促进并发程序的探索。ConcX 是一个免费的开源工具，旨在促进对并发程序的更高层次的思考；ConcX 让我们能够思考我们希望线程**做什么**，而不是思考**如何**编写我们希望它们做的事情。

历史

2018 年 7 月 27 日：文档首次发布

© . All rights reserved.