Concurrency: race conditions, locks and deadlocks

Concurrency bugs have a cruel property: they depend on timing. On two things happening in the wrong order, which is rare. But at a million requests a day, rare is every day.

It does not reproduce on your machine. It does not show up in tests. It shows up in production, disappears, and comes back in two weeks.

The good news is that the variety is small. Practically every concurrency bug falls into a handful of patterns, and you can recognise them by reading code.

Concurrency is not parallelism#

Rob Pike's distinction, and it is a useful one:

Concurrency is dealing with several things at once: program structure. You organise the code into tasks that can progress independently. It makes sense even on a single core: while one waits on disk, the other works.

Parallelism is doing several things at once: genuinely simultaneous execution, which requires more than one core.

Why it matters: a concurrent program on a single core already solves the I/O problem, which is the case for most web applications. And the reverse holds too: throwing more cores at a badly structured program speeds up nothing.

Race condition: the canonical example#

counter++

It looks like one operation. It is three: read the value from memory, add one, write it back.

Two threads, value at 10:

A reads 10. B reads 10. A adds → 11. B adds → 11. A writes 11. B writes 11.

Two increments, and the counter went from 10 to 11. One vanished. No error, no exception, no log.

The critical section is the stretch that touches shared state and needs to run uninterrupted. The solution is mutual exclusion: one at a time in there.

And the point that separates people who understand from people who memorised: the problem is not the shared variable. It is the shared mutable variable.

Immutable data never has a race. That is why functional languages suffer less, and why, in many cases, the best solution is not to add a lock but to stop sharing. Pass messages instead of sharing memory.

Before you go adding mutexes, ask: does this state really need to be shared?

The primitives, and when to use each#

Mutex: one at a time. It is what you use in ninety per cent of cases.

Semaphore: at most N at a time. It is for limiting a resource: at most ten simultaneous calls to that API.

Read-write lock: several readers at once, or one writer alone. Worth it when reads genuinely dominate; if writes are frequent, the extra cost does not pay off.

Spinlock: instead of sleeping, the thread spins and checks. It only makes sense when the wait is nanoseconds, like inside a kernel. In application code, a spinlock is almost always a mistake.

Atomic operations: the processor offers instructions that do read-modify-write without interruption. The most important is compare-and-swap (CAS): "if the value is still X, swap it for Y; otherwise tell me it changed".

With CAS you build lock-free algorithms: read, compute, try to swap, and if it failed, try again.

Upside: no thread blocks another. Downside: under heavy contention, everybody repeats work, and performance can end up worse than a simple mutex.

And there is the ABA problem: the value changed from A to B and back to A. CAS thinks nothing happened. It is solved with a version counter alongside the value.

The practical rule: use the simplest thing that works. Mutex first. Atomics when the mutex becomes a bottleneck proven by measurement. Lock-free only if you are certain you need it, and you probably do not.

Deadlock and the rule that solves it#

Thread A holds lock 1 and wants 2. Thread B holds lock 2 and wants 1. Nobody lets go, nobody moves.

Coffman showed that a deadlock needs four simultaneous conditions: mutual exclusion, hold and wait, no preemption, and circular wait. Break any one of them and there is no deadlock.

In practice you break the fourth, and the rule fits in one sentence:

Always acquire locks in the same global order.

If everybody takes lock 1 before lock 2, there is never a cycle. Define the order (by memory address, by name, by id) and document it. It is a convention that eliminates an entire class of bugs.

Second line of defence: timeouts. Instead of waiting forever, wait at most N and fail. You trade an eternal hang for a handleable error.

And this applies to databases too. Two transactions updating the same rows in reversed order deadlock; the database detects it, picks a victim and aborts. Same fix: a consistent order of access to rows, including adding an ORDER BY to the select that precedes the UPDATE.

Livelock is the cousin: nobody hangs, but nobody progresses. Two people in a corridor each trying to let the other pass.

Starvation: one thread never gets its turn because others always arrive first. It happens with badly configured priorities and with unfair locks.

The memory model#

This is the level almost nobody knows, and it explains impossible bugs.

The compiler and the processor reorder instructions to optimise. Within one thread, the result is always what you expect. Across threads, it is not.

One thread can see another's writes in a different order from the one they were made in. You initialise an object and then publish the reference; another thread sees the reference and a half built object.

The tools: volatile in Java and C# guarantees visibility: the read goes to memory instead of using a value in a register. Memory barriers prevent reordering. And the happens-before relationship is the formal vocabulary for reasoning about it.

The honest recommendation: if you are thinking about the memory model, you should probably be using a higher level abstraction instead: a concurrent queue from the standard library, an actor, a channel.

The code review checklist#

This is the one that catches the most bugs in practice:

→ Is this state shared? If so, is it protected?

→ Are all the paths that touch it protected, including the error path?

→ Is the lock acquisition order the same everywhere?

→ Is there an I/O operation inside the critical section? If so, you are holding a lock while waiting on the network, which is almost always wrong.

→ What happens if this operation runs twice? If the answer is bad, idempotency is missing.

→ Is there a timeout on every wait?

→ Is the resource closed on the error path too?

→ Is there a test that runs this with real concurrency?

The tool that changes everything#

The race detector. -race in Go, ThreadSanitizer in C and C++, equivalent tools in Java and Rust.

They instrument the program and detect unsynchronised concurrent accesses even when the bug does not manifest in that run. They find in seconds what would take you weeks to reproduce.

If you do one thing after reading this: run the race detector over your project's test suite. If something shows up, you have just found a bug that was waiting for the right moment.