Parallel computing shows up without computers in business.
Computer programming is the art of describing actions unambiguously. It is also the analysis of the effort involved in very complicated actions, since any action you can describe unambiguously, no matter how involved or tedious, computers can do execute very quickly. There are many additional studies that flow from these core elements.
One area of computing is called parallelism, parallel programming, concurrency, etc. It studies the intricacies of having multiple entities cooperating on the performance of a single task. In this post I will describe three problems and seven patterns used in parallelism with fairly ordinary day-to-day examples.
Parallel computation can suffer from three main problems: deadlock, livelock, and race conditions. Others, such as excessive duplication of work and handling fluid numbers of workers, are less commonly discussed.
Deadlock happens when two workers are each waiting for the other before they continue. Most deadlocks are petty-seeming arguments over sharing: “give me the scissors” “no, you give me the paper”. A more sane, if less canonical, example might be two people each waiting outside the other’s office.
Livelock occurs when each worker keeps trying to accommodate the other(s), but without success. The classic example is the failure-to-pass-in-the-hallway scenario where two people both dodge to one side, then the other, back and forth. For dumbly obedient, uncreative things like computers live lock can continue ad infinitum.
Race conditions occur when each worker takes action based on the same snapshot of some shared information. And example might be people with a shared chequing account who both check the balance in the morning, and both write cheques nearly draining the account during the day. Each action independently is legal, but the combined impact is incorrect.
There are a variety of tools and patterns used to avoid concurrency problems (though some create more problems of their own). Several common patterns are listed below.
The simplest method of parallelism splits work into many jobs and assigns each job to a different worker. A store with several independent checkout lines is an example.
When several clerks pull from the same checkout queue we have a shared work queue. If VIPs are allowed to cut it’s a priority work queue.
When some tasks depend on others you have a dependency graph. I experienced this once when building ten identical robots with two friends. There were lots of pieces made out of other pieces; when I was working on a larger part and ran out of completed smaller parts I’d switch to working on the smaller parts instead.
It takes two people to play on a teeter-totter. This is a simple kind of barrier or fence: workers can only pass these in set numbers (in this case two).
Sometimes you need to control access to some information so that only one worker has access to it at a time. Metal detectors, lavatories, and doorways are all natural mutual exclusion lock or mutexes. There’s also a social mutex in games like darts and golf where multiple players could go at once but society dictates the go one at a time.
Sometimes a mutex is overly restrictive: for some types of actions lots of workers can access a resource in parallel while for others workers need to get exclusive access. An example is the restroom in my office: usually people can come and go freely, but when the janitor is working the restroom is closed to everyone else. In computing we’d call the janitor a writer and the other people readers from the idea that it’s OK to have a lot of people read text in parallel but it’s best not to have anyone reading or writing while someone else is writing the text.
In a transaction, a worker checks some information, does some work, verifies that the original information has not changed, and then makes the results of its work visible to other workers. Transactions are kind of an optimistic version of a mutex or reader-writer lock. Some calls for proposals and some contests work like this, particularly those without a deadline that will accept the first suitable proposal/solution submitted: you read the call/contest notice, work to create the proposal/solution, and then submit it only if the call/contest hasn’t closed.
There are other patterns too, many of which build off of these in some way.
Describing processes unambiguously is necessary to communicate with computers, but it is also useful in many other fields. For example, corporate efficiency experts think about many of the same concurrency issues as do parallel programmers, seeking ways to remove locks, communicate dependency graphs, and simplify queues. The study of processes turns out to be fairly universal.
Looking for comments…