May 14, 2015

Concurrency and Painting

This metaphor comes from Herlihy's The Art of Multiprocessor Programming; maybe in the future I'll extend it.

Multiprocessor synchronization and Concurrency is painting a house. You have four workers, two brushes, one roller, one ladder, and one giant can of paint. The goal here is to paint the house as fast as possible.

But having four workers isn't four times as good as having a single one - they have to share brushes and paint trays and ladders. This is called Amdahl's Law which says that the theoretical speedup of multiple painters is equivalent to: 1/(B + 1/n(1 - B)), where B is the work that can not be done at the same time.

A deadlock occurs when two painters each are waiting on the other. One has a paintbrush and desires the paint can, while the other has the can and requires the brush. Often times this can be avoided by making sure resources are acquired in a particular order ie. Everyone acquires paint before picking up a brush.