寻找“洗碗机工作时”的解决方案
我正在寻找一种算法来解决“工作中的洗碗机”问题。
虽然能够将脏咖啡杯等放入其中固然很棒，但您很快就会遇到“碗碟状况如何？”的问题。 困境。 如果您走到厨房，您可以从洗碗机中取出餐具吗？因为它们很干净，只是没有收起来？ 您可以将脏盘子放入洗碗机中吗？否则干净的盘子会失效吗？
这似乎是一个必须有一个等价的编程问题。 您有一个异步触发的共享进程，并将对象从一种状态移动到另一种状态。 您需要能够在任何给定时间了解对象的状态。 可以应用哪些算法？
我的起始选择是在洗碗机上创建一个“干净”和“脏”的翻转标志。 当洗碗机清空时，必须切换到“脏”状态，运行时必须切换到“干净”状态。 该算法有问题吗？ 有没有更好/更不易出错的方法？
注意：没有使用轮询时间表的算法，请...
I am looking for an algorithm to apply to the "dishwasher at work" problem.
While it is great to be able to put dirty coffee cups etc. in it, you quickly run into the "what is the state of the dishes?" dilemma. If you walk up to the kitchen, can you take dishes from the dishwasher because they are clean and just not put away? Can you put a dirty dish in the dishwasher or will that invalidate the clean dishes in it?
It seems like a problem that must have a programming equivalent. You have a shared process that is triggered asynchronously and moves objects from one state to another. You need to be able to know the state of the objects at any given time. What algorithms can be applied?
My starting option is to create a flip flag on the dishwasher of "clean" and "dirty". When the dishwasher is emptied, it must be switched to "dirty", when it is run it must be switched to "clean". Are there problems with that algorithm? Is there a better/less error prone one?
Note: No algorithms that utilizes a polling schedule, please...
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（13）
当
User线程想要将脏的Dish放入原本干净的洗碗机中时，问题中的主要问题就会发生。解决方案很简单。 创建另一个
洗碗机对象。一台
洗碗机存放脏盘子，等待清洗，另一台则存放最近清洗过的盘子。当装有干净餐具的
洗碗机空了时，开始清洗另一个洗碗机中的脏盘子。此时，
User线程现在可以将脏盘子放入原来干净的洗碗机（现在是空的）中。继续无限期地交替两个
洗碗机的角色。用户线程总是可以放下脏盘子，而不需要KitchenCounterBuffer。注意：此解决方案不能解决杯子饥饿问题。 用户线程仍然可能会阻塞等待洗碗机完成清洁。
注 2：在
Dishwasher是单例的受限环境中，请提供一个KitchenCounterBuffer以及一个DishwasherOperator来收起餐具并放置脏盘子。KitchenCounterBuffer到洗碗机。 然后，KitchenCounterBuffer 就扮演了上述算法中肮脏的洗碗机的角色。 但是，这可能会导致User线程抛出异常或终止。The main issue in your problem occurs when a
Userthread wants to place a dirtyDishin an otherwise clean dishwasher.The solution is simple. Create another
Dishwasherobject.One
Dishwasherholds the dirty dishes, awaiting to clean them, the other holds the recently cleaned dishes.When the
Dishwasherholding the clean dishes is empty, start cleaning the dirty dishes in the otherDishwasher.At this point,
Userthreads can now put dirty dishes in what used to be the cleanDishwasher(which is now empty).Continue alternating the roles of the two
Dishwashersindefinitely.Userthreads can always drop off a dirty dish without the need for aKitchenCounterBuffer.Note: This solution does not solve the cup-starvation problem.
Userthreads still might block awaiting for a dishwasher to finish cleaning.Note2: In constrained environments where
Dishwasheris a singleton, provide aKitchenCounterBufferas well as aDishwasherOperatorto put away dishes and place dirty dishes from theKitchenCounterBufferto theDishwasher. TheKitchenCounterBufferthen takes the role of the dirtyDishwasherin the algorithm above. However, this might causeUserthreads to throw exceptions or die.与编程无关，但它可能有助于回答您的逻辑问题...我的洗碗机有一个“清洁”灯，当您运行洗衣机时该灯会亮起。 如果您只是短时间打开门（即取出干净的杯子），则该灯会保持亮起状态，但如果您将门打开较长时间（有足够的时间清空洗衣机），则该灯会熄灭。
它并不完美，但它比前面必须由（有点健忘的）人类翻转的旗帜可靠得多。
Not programming related but it may help answer your logic question... My dishwasher has a "Clean" light that comes on when you run the washer. The light stays on if you just open the door for a short time (i.e. to take out a clean cup) but goes off if you keep the door open for a longer time (enough time to empty the washer.)
It's not perfect, but it's much more reliable than a flag on the front that must be flipped by a (somewhat forgetful) human.
我假设洗碗机中的所有物品都必须是干净的或脏的，但不能混合搭配。 下面的解决方案强制执行该属性。 如果不是，那么你的类比不太正确。
只需几个互斥体就可以解决问题。
你有四个州。
您可以进一步将空和脏一起折叠起来，因为您不关心其中的差异。
这假设您可以知道洗碗机何时空，如果没有，您需要为 ElementsInDishwasher 提供一个计数信号量，在发出 DirtyMutex 信号之前等待它。
I am assuming that all the objects in the dishwasher must be clean or dirty, but not mix and match. The solution below enforces that property. If not, you analogy wasn't quite right.
Just a few mutexes should do the trick.
You have four states.
You can further collapse empty and dirty together, since you do not care about the difference.
This assumes you can know when the dishwasher is empty, if not, you'll need a counting semaphore for ElementsInDishwasher that you wait on before signaling DirtyMutex.
我喜欢你的类比，但潜在的问题让我担心。 根据我的经验，一个设计良好的系统总是知道（通常是隐式的）您所指的状态类型。 例如，共享资源队列中的资源可供其他进程使用，否则它就不会在队列中。 或者，工作线程正在修改的资源处于该线程的处理表明其所处的任何状态 - 更重要的是，其他线程不需要知道它是“干净”还是“脏”。
有大量我还没有遇到（或发明过：-）的有效设计模式，但是您所描述的有设计气味（或脏盘子）的暗示，而不是有效的模式。
I like your analogy, but the underlying problem worries me. In my experience, a well-designed system always knows (usually implicitly) the kind of state that you're referring to. For example, a resource in a shared resource queue is available for use by other processes -- if it weren't, it wouldn't be in the queue. Or, a resource being modified by a worker thread is in whatever state the thread's processing says it's in -- more importantly, no other thread needs to know whether it's "clean" or "dirty".
There's a mind-boggling number of valid design patterns that I haven't encountered (or invented :-) yet, but what you're describing has the hint of a design smell (or dirty dishes) rather than a valid pattern.
也许有限状态机适合您想要解决的问题？
Maybe Finite State Machine fits the problem you want to solve?
只需制定一条规则，始终将干净的餐具从洗碗机中取出，这样任何东西都脏了，您可以添加更多
just make a rule to always remove the clean dishes from the dishwasher, so anything that is in = dirty and you can add more
你看，这就是程序思维的问题。 它将一切都变成了批处理过程，这在异步、事件驱动的世界中表现不佳。 您需要开始担心状态、线程、竞争条件、持久性等。
避免这些问题的解决方案是使所有菜肴不可变。 如果您需要一个脏盘子，您只需创建一个包含污垢的新实例即可。
如果获取菜肴的干净副本是一种常见操作（听起来像您的情况），您可以向您的 Dish 对象添加 .AsClean() 方法，该方法会自动为您返回一个干净的克隆。 如果性能成为瓶颈，如果实例已经干净，则可以通过返回
this来优化。当然，这假设您处于具有合理堆空间和自动垃圾收集的环境中。
See, this is the problem with procedural thinking. It turns everything into a batch process, and that doesn't play well in an asynchronous, event-driven world. You need to start worrying about state, threading, race conditions, persistence, etc.
A solution that avoids these issues would be to make all dishes immutable. If you need a dirty dish, you would simply create a new instance with dirt in it.
If getting a clean copy of a dish was a common operation (which sounds like the case in your situation), you could add an .AsClean() method to your Dish object, which would automatically return a clean clone for you. If performance became a bottleneck, this could be optimized by returning
thisif the instance was already clean.Of course, this assumes that you're in an environment with reasonable heap space and automatic garbage collection.
我见过商用洗碗机将餐具通过隧道传送到传送带上。 你把脏盘子放到左边的架子上。 您从右侧的架子上取出干净的盘子。 单个盘子的干净/脏状态与其在机器内的物理位置相对应。
这是一个完全不同的架构。 对于标准洗碗机，您会将“干净/脏”视为洗碗机的一个属性。 “干净”的意思是“没有脏盘子”。 对于传送式洗碗机，“干净/肮脏”不是洗碗机的属性。
您可能不想切换到这种架构，但如果您愿意，请考虑通过并发阻塞队列连接的一系列处理对象。 一个盘子进入预冲洗器，出来，进入洗衣机，出来，进入烘干机，最后出来。
I've seen commercial dishwashers that send dishes on a conveyor through a tunnel. You put dirty dishes into the racks on the left. You take clean dishes from the racks on the right. The clean / dirty state of an individual dish corresponds to its physical location within the machine.
This is a completely different architecture. With a standard dishwasher you think of "clean / dirty" as an attribute of the dishwasher. "Clean" means "contains no dirty dishes." With the conveyor dishwasher, "clean / dirty" is not an attribute of the dishwasher.
You may not want to switch to this architecture, but if you do, consider a series of processing objects connected by concurrent blocking queues. A dish goes into the pre-rinser, comes out, goes into the washer, comes out, goes into the dryer, and comes out the end.
正如您所指出的，您只需要一个标志（干净/脏）。 洗碗机通常已经提供了这种机制：（物理）锁。
从软件意义上来说，锁只能将餐具放入洗碗机中——你可以根据它是否被锁定来知道被取出的餐具是干净的还是脏的，但只能将其放入洗碗机中 如果未锁定，则可以放入一盘菜。 如果你拿走了最后一道菜，你就解锁了它。
You only need a single flag, as you indicated (clean/dirty). Dishwashers generally provide this mechanism already: a (physical) lock.
In a software sense, the lock is only on being able to put dishes into the dishwasher -- you'd know if a dish being removed is clean or dirty based on whether it's locked or not, but can only put a dish in if it's unlocked. If you take the last dish, you unlock it.
一个简单的解决方案是保持不变量始终为真。 这样一组不变量的示例可以是：
与洗碗机交互的对象的工作是保持这些不变量的有序性。 如果有人在洗碗机中添加了一个杯子，使其满了，他还必须将其打开，以便下一个过来的人会发现洗碗机已满并且所有杯子都是干净的。
A simple solution to this is maintaining invariants that are always true. An example of such a set of invariants can be:
It is the job of the object which interact with the dishwasher to keep these invariants in order. If someone adds a cup to the dishwasher and that makes it full, he must also turn it on so that the next person who comes around will find that the dishwasher is full and all the cups are clean.
您可以让洗碗机在洗涤周期结束时自动弹出餐具吗？
这与 Mark Lutton 的想法类似，也类似于将已清洁的菜肴推入已知干净的菜肴的（可能是暂时的）队列中，然后可以将其从队列中取出。
Can you have the dishwasher eject its dishes automatically, at the end of its wash-cycle?
This is similar to Mark Lutton's idea, amd analogous to pushing cleaned dishes onto a (perhaps temporary) queue of known-clean dishes, from which they can be dequeued.
这是由于使用衰退技术而导致的设计问题 - 通过将设计的一部分更新为更先进的形式，您可以摆脱整个问题并节省时间、水和能源。
使用可食用的盘子吗？
It's a design problem resulted from the use of a decaying technology - By updating a part of your design, to a more advanced form, you can get rid of the entire problem and save time, water and energy.
Use eatable plates?
解决这个问题的简单方法是保持不变量始终为真。 此类不变量集的一个示例可以是：
如果洗碗机是空的/未完全满 - 所有盘子都脏了
如果洗碗机已满，则所有餐具都是干净的。
与洗碗机交互的对象的工作是保持这些不变量的有序性。 如果有人在洗碗机中添加了一个杯子，使其满了，他还必须将其打开，以便下一个过来的人会发现洗碗机已满并且所有杯子都是干净的。
Simple solution to this is maintaining invariants that are always true. An example of such a set of invariants can be:
If the dishwasher is empty/not completely full - all the dishes are dirty
If the dishwasher is full - then all the dishes are clean.
It is the job of the object which interact with the dishwasher to keep these invariants in order. If someone adds a cup to the dishwasher and that makes it full, he must also turn it on so that the next person who comes around will find that the dishwasher is full and all the cups are clean.