9

我正在寻找一种适用于“工作中的洗碗机”问题的算法。

虽然可以将脏咖啡杯等放入其中很棒，但您很快就会遇到“盘子的状态如何？” 困境。如果你走到厨房，你能从洗碗机里拿盘子，因为它们很干净，只是没有收起来吗？您可以将脏盘子放入洗碗机中，否则会使里面的干净盘子失效吗？

这似乎是一个必须具有编程等价物的问题。您有一个异步触发的共享进程，并将对象从一种状态移动到另一种状态。您需要能够在任何给定时间了解对象的状态。可以应用哪些算法？

我的开始选择是在“干净”和“脏”的洗碗机上创建一个翻转标志。当洗碗机清空时，必须切换到“脏”，运行时必须切换到“清洁”。该算法有问题吗？有没有更好/更不容易出错的？

注意：请不要使用轮询时间表的算法...

4

12 回答 12

6

User当线程想要将脏东西Dish放入其他干净的洗碗机中时，就会出现问题中的主要问题。

解决方案很简单。创建另一个Dishwasher对象。

一个Dishwasher拿着脏盘子，等着清洗，另一个拿着最近清洗过的盘子。

当Dishwasher盛着干净的盘子是空的，开始清洗另一个盘子里的脏盘子Dishwasher。

此时，User线程现在可以将脏盘子放入曾经是干净的Dishwasher（现在是空的）的地方。

Dishwashers继续无限期地交替两者的角色。User线程总是可以丢弃脏盘子，而无需KitchenCounterBuffer.

注意：此解决方案不能解决杯子饥饿问题。User线程仍然可能会阻塞等待洗碗机完成清洁。

注意 2：在单例的受限环境中Dishwasher，提供 aKitchenCounterBuffer和 aDishwasherOperator来收起盘子并将脏盘子从KitchenCounterBuffer到Dishwasher。然后在上面的算法KitchenCounterBuffer中扮演脏的角色。Dishwasher但是，这可能会导致User线程抛出异常或死亡。

于 2009-04-22T22:15:38.010 回答
2

与编程无关，但它可能有助于回答您的逻辑问题......我的洗碗机有一个“清洁”灯，当您运行洗衣机时会亮起。如果您只是打开门很短时间（即取出一个干净的杯子），灯会保持亮起，但如果您将门打开更长的时间（足够清空洗衣机的时间），灯就会熄灭。这并不完美，但它比必须由（有点健忘的）人翻转的前面的旗帜更可靠。

于 2009-04-23T00:58:29.023 回答
1

我假设洗碗机中的所有物品都必须干净或脏，但不能混搭。下面的解决方案强制执行该属性。如果不是，那你的比喻就不太对了。

只需几个互斥锁就可以解决问题。

你有四个州。

  • 洗碗机空了，你可以放脏盘子
  • 洗碗机脏了，可以放脏盘子
  • 洗碗机运行，您不能放置脏盘子或移除干净的盘子。
  • 洗碗机干净，你不能放脏盘子，可以取出干净的盘子。

您可以进一步将空和脏一起折叠，因为您不关心差异。

  • 当你想插入一些东西时，你等待 DirtyMutex
  • 当您想开始洗涤时，请等待 DirtyMutex 以免浪费水；）
  • 清洗结束时，您会发出 CleanMutex 信号
  • 当您想清空洗碗机时，您可以等待 CleanMutex
  • 当洗碗机空了时，您会发出 DirtyMutex 信号

这假设您可以知道洗碗机何时是空的，如果没有，您将需要 ElementsInDishwasher 的计数信号量，然后再发出 DirtyMutex 信号。

于 2009-04-22T22:04:11.827 回答
1

我喜欢你的比喻，但潜在的问题让我担心。以我的经验，一个设计良好的系统总是知道（通常是隐含地）你所指的那种状态。例如，共享资源队列中的资源可供其他进程使用——如果不是，它就不会在队列中。或者，工作线程正在修改的资源处于线程处理所说的任何状态——更重要的是，没有其他线程需要知道它是“干净”还是“脏”。

我还没有遇到（或发明:-）的有效设计模式数量之多令人难以置信，但是您所描述的内容暗示着设计气味（或脏盘子）而不是有效模式。

于 2009-04-22T22:06:24.847 回答
1

也许有限状态机适合您要解决的问题？

于 2009-04-22T22:13:51.493 回答
1

只是制定一个规则，总是从洗碗机中取出干净的盘子，所以任何东西=脏，你可以添加更多

于 2009-06-20T22:13:30.533 回答
1

看，这就是程序性思维的问题。它将一切都变成了一个批处理过程，这在异步、事件驱动的世界中表现不佳。你需要开始担心状态、线程、竞争条件、持久性等。

避免这些问题的解决方案是使所有菜肴不可变。如果您需要一个脏盘子，您只需创建一个带有污垢的新实例。

如果获取菜的干净副本是一种常见操作（听起来像您的情况），您可以向您的 Dish 对象添加一个 .AsClean() 方法，它会自动为您返回一个干净的克隆。如果性能成为瓶颈，可以通过this在实例已经干净的情况下返回来优化。

当然，这假设您处于具有合理堆空间和自动垃圾收集的环境中。

于 2009-06-20T22:39:02.417 回答
1

我见过商业洗碗机通过隧道在传送带上传送盘子。你把脏盘子放在左边的架子上。你从右边的架子上拿干净的盘子。单个盘子的清洁/脏污状态与其在机器内的物理位置相对应。

这是一个完全不同的架构。对于标准洗碗机，您认为“干净/脏”是洗碗机的一个属性。“干净”的意思是“没有脏盘子”。对于传送式洗碗机，“干净/脏”不是洗碗机的属性。

您可能不想切换到此架构，但如果您这样做，请考虑通过并发阻塞队列连接的一系列处理对象。一个盘子进入预冲洗器，出来，进入洗衣机，出来，进入烘干机，最后出来。

于 2009-06-20T22:42:36.917 回答
0

正如您所指出的（干净/脏），您只需要一个标志。洗碗机通常已经提供了这种机制：（物理）锁。

  • 洗碗机开始清空，解锁
  • 洗碗机已解锁，因此可能会将脏盘子放入其中
  • 在运行洗碗机之前，它被锁定
  • 运行后还是被锁住，说明里面的东西都是脏的
  • 如果您从中删除某些东西，并且它不是最后一个项目，则重新锁定它

在软件意义上，锁只在于能够将盘子放入洗碗机——你会根据它是否被锁定来知道被移除的盘子是干净还是脏，但只有在它被锁定时才能将盘子放进去。解锁。如果你拿走最后一道菜，你就会解锁它。

于 2009-04-22T22:15:11.130 回答
0

一个简单的解决方案是保持始终为真的不变量。这样一组不变量的示例可以是：

  • 如果洗碗机是空的/没有完全装满 - 所有的盘子都是脏的
  • 如果洗碗机满了 - 那么所有的盘子都是干净的。

与洗碗机交互的对象的工作是保持这些不变量的顺序。如果有人在洗碗机里加了一个杯子，它就满了，他也必须打开它，这样下一个过来的人会发现洗碗机已经满了，所有的杯子都是干净的。

于 2009-04-22T22:20:40.803 回答
0

你能让洗碗机在洗涤周期结束时自动弹出它的碗碟吗？

这类似于 Mark Lutton 的想法，类似于将清洗过的盘子推到（可能是临时的）已知干净盘子的队列中，然后可以将它们从队列中取出。

于 2009-06-20T23:01:55.710 回答
0

这是由于使用衰变技术而导致的设计问题 - 通过将设计的一部分更新为更高级的形式，您可以摆脱整个问题并节省时间、水和能源。

使用可食用的盘子？

于 2009-06-20T23:15:05.417 回答