Multithreading in the kitchen

David Stark / Zarkonnen
2013-10-29 12:33
We have a pretty small kitchen, but we like to do kitchen work together. A frequent scenario occurs where one of us is standing at the sink, washing up, while the other one is tidying and needs to throw something away. Unfortunately, person A is blocking access to the bin, which is below the sink. In other words, they hold a mutual exclusion lock on that bit of the kitchen.

Person B now has to wait for A to finish washing up at least the current dish before they can move in. This might take a while, and is not very efficient. Moreover, the dance of one person moving out of the way, letting the other open the bin and throw in the garbage, and then moving back in, is also pretty tedious. In other words, if you have two threads of execution (people cleaning the kitchen) who both need frequent access to a single resource, execution is slowed down a lot.

So what's the alternative? Well, if B notices that A is going to take a while to finish scrubbing that a big dirty pan, they might instead deposit the item to be thrown away next to the sink, letting A dispose of it at their leisure. Basically switching from a mutex-based multithreading system to one based on message passing - the "message" here being the piece of garbage to be thrown away. This comes with extra overhead for A, but it leaves B to continue doing stuff.

This becomes especially useful if B's other task is to dry and put away dishes. In this case, if the dish rack is full, the system can enter deadlock: B needs to throw away the garbage before they can take a dish out of the rack, but A needs to have a free space in the dish rack to put the plate before they can move out of the way of B.

Of course, in a kitchen, these kinds of deadlocks are just resolved with some awkward balancing of plates, or putting down the garbage somewhere, or putting the plate back into the sink - in other words, human beings can detect deadlock and back out of what they were doing to resolve it. Computers aren't so smart. If, on the other hand, we use messages - putting the garbage next to the sink for the other person to throw away and then moving to pick up a plate from the rack - these kinds of situation simply go away.