Looking for a solution to the "Dishwasher At Work" problem

Question

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...

Answer 1

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.

• Dishwasher empty, you can put dirty dishes
• Dishwasher dirty, you can put dirty dishes
• Dishwasher running, you cannot put dirty dishes or remove clean ones.
• Dishwasher clean, you cannot put dirty dishes and can remove clean ones.

You can further collapse empty and dirty together, since you do not care about the difference.

• When a you want to insert something, you wait on DirtyMutex
• When you want to start washing, you wait on DirtyMutex so that you don't waste water ;)
• When washing is over, you signal CleanMutex
• When you want to empty the dishwasher, you wait on CleanMutex
• When the dishwasher is empty, you signal DirtyMutex

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.

Answer 2

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.

Answer 3

Maybe Finite State Machine fits the problem you want to solve?

Answer 4

You only need a single flag, as you indicated (clean/dirty). Dishwashers generally provide this mechanism already: a (physical) lock.

• Dishwasher starts empty, unlocked
• Dishwasher is unlocked, so dirty dishes may be put into it
• Before running the dishwasher, it is locked
• After running, it is still locked, indicating everything inside is dirty
• If you remove something from it, and it's not the last item, you relock it

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.

Answer 5

The main issue in your problem occurs when a User thread wants to place a dirty Dish in an otherwise clean dishwasher.

The solution is simple. Create another Dishwasher object.

One Dishwasher holds the dirty dishes, awaiting to clean them, the other holds the recently cleaned dishes.

When the Dishwasher holding the clean dishes is empty, start cleaning the dirty dishes in the other Dishwasher.

At this point, User threads can now put dirty dishes in what used to be the clean Dishwasher (which is now empty).

Continue alternating the roles of the two Dishwashers indefinitely. User threads can always drop off a dirty dish without the need for a KitchenCounterBuffer.

Note: This solution does not solve the cup-starvation problem. User threads still might block awaiting for a dishwasher to finish cleaning.

Note2: In constrained environments where Dishwasher is a singleton, provide a KitchenCounterBuffer as well as a DishwasherOperator to put away dishes and place dirty dishes from the KitchenCounterBuffer to the Dishwasher. The KitchenCounterBuffer then takes the role of the dirty Dishwasher in the algorithm above. However, this might cause User threads to throw exceptions or die.

Answer 6

A 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.

Answer 7

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.

Answer 8

just make a rule to always remove the clean dishes from the dishwasher, so anything that is in = dirty and you can add more

Answer 9

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 this if the instance was already clean.

Of course, this assumes that you're in an environment with reasonable heap space and automatic garbage collection.

Answer 10

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.

Answer 11

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.

Answer 12

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?