Mutexes

The problem it solves

A mutex gives you a region of code that only one thread can be inside at a time. That is the whole feature, and it is enough to fix most of what goes wrong when threads share memory.

What is worth understanding is not that it works but what it does to the set of possible executions. Everyone can say a lock makes the counter safe. Far fewer can say what happened to the eighteen interleavings that used to lose the update — and the answer is not that they became unlikely, or that they are now caught, or that the thread retries. They stopped existing. A thread whose next operation is a held lock is not a thread that runs and then blocks; it is a thread the scheduler cannot choose. The orderings that depended on it running are unreachable.

That distinction — removing orderings rather than surviving them — is what separates a fix from a mitigation, and it is the frame worth carrying into every question about locking.

The mechanism

lock(m) proceeds if the mutex is free and does not proceed otherwise. In the model on this page that is expressed directly: the enumerator asks which threads can take a step, and a thread waiting on a held mutex is not among them. The interleaving space is generated from that question, so exclusion falls out of it rather than being enforced on top.

The critical section is the region between acquiring and releasing, and its boundaries are the entire design decision. It has to span every operation that must appear indivisible to other threads. For a counter that means the read, the add and the write — not just the write, which is the mistake this page demonstrates.

Underneath, an uncontended acquisition is a single compare-and-swap on the lock word, which is why it costs tens of nanoseconds rather than microseconds. Blocking is the expensive part: a thread that actually has to wait is descheduled, and getting it running again costs a context switch. Most production mutexes therefore spin briefly before sleeping, on the theory that a short critical section will be over before a context switch would have completed.

What the enumeration shows

Put the lock around the whole increment and the space collapses from twenty interleavings to two, with a single outcome. The two are “T1’s whole critical section, then T2’s” and the reverse — which are exactly the two orderings that were correct before. Everything else has been removed from existence.

Now switch to mutex-too-late, where the lock is taken after the read. It is a real mutex, correctly acquired, correctly released, and it protects nothing: 8 of 12 interleavings still lose the update, because the race was between the read and the write and the critical section starts in the middle of it. This variant is the most useful thing on the page. The code looks synchronised. It reviews as synchronised. It is not.

Also worth reading is the bound line under the outcome panel: the multinomial says 252 orderings on paper, and 2 can actually happen. The gap is what the lock removed.

The numbers worth carrying

• Guarded increment: 2 interleavings, 1 outcome. Unguarded: 20 and 2. Guarded too late: 12 and 2 — no better than nothing.
• Uncontended lock/unlock: roughly 20–50ns. Contended, with an actual block and wake: 1–10µs, dominated by the context switch. Two orders of magnitude between the fast and slow path.
• Throughput ceiling: one critical section at a time means 1 / criticalSectionTime operations per second, no matter how many threads arrive. A 100ns critical section caps the system at 10M ops/s — see lock granularity, where that ceiling is plotted.

Where it breaks down

A lock protects data, not code. The invariant is that everybody who touches the data takes the same lock. One path that reads the field without locking — because it is “just a read”, or because it is in a different class, or because someone added a getter — and the protection is gone. See reader-writer locks for what an unlocked read actually costs.

Locks compose badly. Two correct critical sections, one taken inside the other, is how deadlock happens: deadlock is entirely a story about combining locks that are individually fine. Nothing about a lock’s interface tells you what it is safe to call while holding it, which is why “never call unknown code inside a critical section” is a real rule.

A lock is a throughput ceiling. It converts the critical section into a serial fraction, so Amdahl’s law applies with the lock in place of the sequential region. If you find yourself widening a critical section for correctness, you are lowering that ceiling.

Non-reentrant locks deadlock against themselves. One thread, one lock, no concurrency — see reentrancy, which is the cleanest counterexample to “deadlock needs two threads”.

Fairness is not free and not the default. A released mutex generally goes to whoever the scheduler runs next, which may be the thread that just released it — see starvation.

What people get wrong

“I added a lock, so it is thread-safe.” Where does the critical section start? The mutex-too-late variant is a working lock that fixes nothing.

“Locking the write is enough because reads are atomic.” An atomic read gives you a value that is accurate and immediately stale. This is check-then-act again.

“Bigger critical sections are safer.” They are safer against races and worse for throughput and much more likely to deadlock, because more of what you call happens while holding the lock. The goal is a critical section that is exactly as large as the invariant requires.

“Locks are slow.” Uncontended locks are tens of nanoseconds. Contention is slow, and contention is a property of your design rather than of the primitive.

In production

synchronized and ReentrantLock in Java, std::mutex with lock_guard/scoped_lock in C++, sync.Mutex in Go, Mutex<T> in Rust, threading.Lock in Python. Two idioms are worth adopting wherever the language allows them.

The first is scope-based release — defer mu.Unlock(), lock_guard, try/finally — so the lock is released on every path including the ones that throw. A lock leaked by an early return is a deadlock that appears only on the error path, which is the path least covered by tests.

The second is Rust’s arrangement, which is worth understanding even if you never write Rust: the mutex owns the data, so there is no way to name the protected value without holding the lock. The convention that everyone must take the same lock becomes a fact the compiler enforces, and the entire class of “somebody accessed it without locking” disappears.

For choosing where to lock: prefer one lock per invariant rather than one per object or one per module, keep critical sections short, never perform I/O or call user-supplied callbacks while holding one, and if you need two locks, read deadlock first.

The follow-up questions

“Where does the critical section start and end?” — The real question behind “did you add a lock”. It must span every operation the invariant depends on.

“What does the lock do to the possible interleavings?” — It removes them. Twenty to two. This is the answer that shows understanding rather than habit.

“What is the cost when uncontended, and when contended?” — Tens of nanoseconds against microseconds, and say why: the context switch.

“You need to take two locks. What now?” — A total ordering over locks, applied everywhere. And then the follow-up about a third thread in a ring.