寻找"洗碗机在工作"的解决方案

Question

我正在寻找一种适用于"洗碗机工作"问题的算法.

虽然能够将脏咖啡杯等放入其中是很棒的,但您很快就会遇到"菜肴状态如何？" 困境.如果你走到厨房,你可以从洗碗机中取出菜肴,因为它们很干净而且没有放好吗？你可以把一个肮脏的盘子放入洗碗机中,还是会使干净的盘子无效？

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

我的开始选择是在"干净"和"脏"的洗碗机上创建一个翻转标志.当洗碗机清空时,必须将其切换为"脏",当它运行时必须切换到"清洁".这个算法有问题吗？是否有更好/更少错误？

注意:没有使用轮询时间表的算法,请...

Answer 1

当一个User线程想要Dish在一个干净的洗碗机中放置一个脏时,就会出现问题的主要问题.

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

一个Dishwasher拿着脏盘子,等待清理它们,另一个拿着最近清洗过的菜肴.

当Dishwasher拿着干净的盘子是空的,开始清洗在其他的脏碗碟Dishwasher.

此时,User线程现在可以将脏盘子放在曾经是干净的Dishwasher(现在是空的)中.

继续Dishwashers无限期地交替两者的角色.User线程总是可以从脏盘中掉出来而不需要a KitchenCounterBuffer.

注意:此解决方案无法解决杯子饥饿问题.User线程仍然可能阻止等待洗碗机完成清洁.

注2:在受限的环境中Dishwasher是一个单身,提供KitchenCounterBuffer以及一DishwasherOperator放好餐具,并把脏盘子从KitchenCounterBuffer到Dishwasher.在KitchenCounterBuffer随后取脏的作用Dishwasher在上面的算法.但是,这可能会导致User线程抛出异常或死亡.

Answer 2

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

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

你有四个州。

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

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

• 当你想插入一些东西时，你需要等待 DirtyMutex
• 当你想开始清洗时，你可以等待 DirtyMutex，这样你就不会浪费水;)
• 洗涤结束后，您发出 CleanMutex 信号
• 当你想清空洗碗机时，你需要等待 CleanMutex
• 当洗碗机空了时，您发出 DirtyMutex 信号

这假设您可以知道洗碗机何时是空的，如果没有，您将需要 ElementsInDishwasher 的计数信号量，您在发出 DirtyMutex 信号之前等待它。