Looking for a solution to "Dishwasher At Work"

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

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 2

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 3

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 4

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.