Synchronization

When threads touch a shared resource, some interleavings of their steps are fine and some corrupt your data. Synchronisation is the toolbox for allowing only the safe ones.

The tools

• Critical section: the bit of code that touches shared state and must not be run by two threads at once.
• Mutex (mutual exclusion lock): one holder at a time; everyone else waits.
• Semaphore (Dijkstra): a counter that allows up to n holders. A mutex is the n = 1 case.
• Monitor: a lock bundled with the data it protects and condition variables for waiting (Java’s synchronized).

Too little, too much

• Too little synchronisation gives you race conditions: lost updates and impossible states.
• Too much, or locks taken in inconsistent orders, gives you Deadlock and Starvation.
• The craft is holding locks for as short a time as possible, always in the same order.

Beyond one machine

The same problem reappears across machines as distributed locks and leases (e.g. infrastructure state locking, so two deploys can’t change the same state at once), and at its hardest as The Consensus Problem.

A front-end echo

I hit this in a graph visualisation library: user mutations were stacking up faster than the graph could apply them, and applying them out of order broke the layout. The fix was the classic one. Serialise mutations through a single queue and replay them in order, which is effectively a lock with a waiting line.

Related: Threads and Processes · Deadlock and Starvation · Message Passing