logo标签列表

寻求“洗碗机在工作时”的解决方案

resource-management
10
我正在寻找一种算法来应用于“工作中的洗碗机”问题。
虽然它很棒，可以把脏咖啡杯等放进去，但你很快就会遇到“餐具的状态是什么？”的困境。如果你走到厨房，能否从洗碗机中取出干净的餐具而不需要放回原处？你能否将脏碗放入洗碗机，而不会使里面的干净餐具失效？
这似乎是必须有编程等价物解决的问题。您有一个共享进程，该进程被异步触发并将对象从一种状态移动到另一种状态。您需要能够在任何给定时间了解对象的状态。可以应用哪些算法？
我的起始选择是在洗碗机上创建“干净”和“脏”翻转标志。当洗碗机被清空时，必须将其切换为“脏”，当运行它时，必须将其切换为“干净”。那个算法有问题吗？有更好/更少错误的方式吗？
注意：请勿使用轮询计划的算法......
你应该尝试更轻松地对待生活 :-))) 不过这是个好观点..非常原创。 - Blerta
1
不仅这个有效，而且有人已经赚到了钱... http://www.amazon.com/Clean-Dirty-Dishwasher-Indicator-255/dp/B00004XSF9 - Liran Orevi
13个回答
6
在你的问题中，主要问题是当一个“用户”线程想把一个脏的“盘子”放到一个干净的洗碗机里时发生的。
解决方案很简单。创建另一个“洗碗机”对象。
一个“洗碗机”容纳脏盘子，等待清洗，另一个容纳最近清洗过的盘子。
当容纳干净盘子的“洗碗机”为空时，开始在另一个“洗碗机”中清洗脏盘子。
此时，“用户”线程现在可以把脏盘子放在原来是干净的“洗碗机”中（现在为空）。
无限交替两个“洗碗机”的角色。 “用户”线程始终可以放下脏盘子，而不需要“厨房柜台缓冲区”。
注意：这种解决方案并不能解决杯子匮乏问题。 “用户”线程仍然可能会阻塞等待洗碗机完成清洗。
注意2：在约束环境中，“洗碗机”是单例的情况下，除了提供“厨房柜台缓冲区”外，还要提供“洗碗机操作员”，将餐具放好，并将脏盘子从“厨房柜台缓冲区”放到“洗碗机”中。然后，“厨房柜台缓冲区”在上述算法中扮演脏“洗碗机”的角色。但是，这可能会导致“用户”线程抛出异常或死亡。
2

虽然与编程无关，但它可能有助于回答您的逻辑问题......我的洗碗机有一个“清洁”灯，当您运行洗碗机时会亮起。如果您只是短时间打开门（例如取出干净的杯子），则灯会保持亮着，但如果您长时间打开门（足够时间将洗碗机清空），则灯会熄灭。 虽然不完美，但比在前面翻转的旗帜更可靠，因为那需要一个（有些健忘的）人来完成。

1

只需制定一个规则，始终将干净的餐具从洗碗机中取出，这样里面的任何东西都是脏的，你可以添加更多。

问题在于onDoneWashing回调处理程序并不总是可靠地实现，因此您不能假设因为里面有盘子它们就是脏的。 - Nathan Voxland
1
看，这就是过程式思维的问题所在。它把所有事情都变成了批处理，而在异步、事件驱动的世界中，这样做并不好。你需要开始担心状态、线程、竞态条件、持久性等问题。
避免这些问题的解决方案是使所有餐具都是不可变的。如果你需要一个脏盘子，你只需创建一个新实例并加入污垢即可。
如果获取干净的盘子是一个常见操作（在你的情况下似乎是这样），你可以在你的Dish对象中添加一个.AsClean()方法，它会自动为你返回一个干净的克隆。如果性能成为瓶颈，这可以通过在实例已经干净时返回this来进行优化。
当然，这假定你处于一个有合理堆空间和自动垃圾收集的环境中。
1

我见过商用洗碗机，它们通过一个隧道将餐具送上传送带。你把脏盘子放在左边的架子上，从右边的架子上取出干净的盘子。每个盘子的清洁/脏污状态对应于其在机器内的物理位置。

这是完全不同的架构。使用标准洗碗机时，您会认为“清洁/脏污”是洗碗机的属性。“清洁”表示“不含有脏盘子”。但是，在传送带式洗碗机中，“清洁/脏污”不是洗碗机的属性。

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

1

我假设洗碗机中的所有物品都必须是干净或脏的，而不能混合使用。下面的解决方案强制执行该属性。如果不是这样，那么你的比喻就不太恰当。

只需要一些互斥锁就可以解决问题。

你有四种状态。

  • 洗碗机为空，你可以放脏碗
  • 洗碗机脏了，你可以放脏碗
  • 洗碗机正在运行，你不能放脏碗或取出干净的碗。
  • 洗碗机干净了，你不能放脏碗，可以取出干净的碗。

你可以进一步将空和脏合并在一起，因为你不关心它们之间的区别。

  • 当你想要插入东西时，你会等待DirtyMutex
  • 当你想要开始清洗时，你会等待DirtyMutex，以免浪费水 ;)
  • 清洗结束后，你会发出CleanMutex信号
  • 当你想要清空洗碗机时，你会等待CleanMutex
  • 当洗碗机为空时，你会发出DirtyMutex信号

这假设你可以知道洗碗机何时为空，如果不行，你需要一个ElementsInDishwasher的计数信号量，在发出DirtyMutex信号之前等待该信号。

让一群人排队等待洗碗机完成清洁工作并不是一个解决方案。 - Ben S
嗯，我不确定我从计算的角度理解这个。如果他们想要做其他事情，他们需要轮询，没有解决方案。每个“人可以旋转一个等待线程”，并在完成后设置一个值，如果他们想要的话，他们可以内部轮询。 - jfclavette
1
当然，“现实世界”的解决方案是拥有两个洗碗机。每个洗碗机都有互斥状态：一个洗碗机装着干净的餐具，另一个装着脏的餐具，并且它们交替使用。再也不用把餐具放回原位了。 - Mark Renouf
@tweakt：是的，详细信息请参见我的答案，:P - Ben S
或者更好的“现实世界”解决方案是一个带有两个独立抽屉的洗碗机！（http://www.fisherpaykel.co.nz/dishwashing/?productUid=29D789C0-BC96-E1AC-9D294AD0A3EBF38B） - rbrayb
显示剩余2条评论
1

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

我还没有遇到过（或发明出来的）大量有效的设计模式，但你所描述的具有设计上的瑕疵（或脏盘子）而不是有效的模式。

1
0

你能让洗碗机在洗完后自动弹出餐具吗？

这与Mark Lutton的想法类似，类比于将清洗过的餐具推入已知干净餐具的（可能是临时的）队列中，然后可以从中出队。

0

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

使用可食用的盘子？

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接