Race conditions, locks and deadlock

A web server counts page views with one line, count++, run by whichever thread handles the request. After a busy day the counter reads 9,970, yet the log shows 10,000 requests. No request failed and no line of code is wrong on its own.

Thirty updates vanished because two threads ran count++ at the same time, and the order their steps happened to interleave decided the result. That is a race condition. The cure is a lock, and locks bring a failure of their own: threads that wait for each other forever, a deadlock.

thread

An independent line of execution. Threads of one program share its memory, and the scheduler can pause any of them between any two instructions.

interleaving

One order in which the threads' instructions actually run. The scheduler picks it, so it can change from run to run.

race condition

The result depends on the interleaving, and some interleavings give a result that running the threads one at a time never would.

lock (mutex)

Only one thread can hold it. Code between lock and unlock, the critical section, never runs in two threads at once.

atomic instruction

An instruction the hardware does as one step that nothing can split, such as fetch-and-add or compare-and-swap.

deadlock

A set of threads each waiting for a lock that another of them holds, so none can ever move.

count++ looks like one step, but the machine does it in three: load count into a private register, add 1 to the register, store the register back. Here threads A and B each run count++ once, starting from count = 0, and the scheduler runs them in the order A B A A B B.

Most of the interleavings go wrong here, so why do real programs usually seem to work? Because the threads rarely hit those three steps at the same moment: a scheduler lets a thread run thousands of instructions before switching, and on separate cores the two updates must overlap within a few nanoseconds. With three threads there are 1,680 interleavings: 1,404 end at 1, 270 at 2, and only the 6 that run one thread at a time reach 3.

An account holds 100. Two threads each try to withdraw 80: load the balance, stop if it is under 80, otherwise subtract 80 with one atomic instruction. Only one withdrawal should succeed. Predict each step.

Wrap count++ in a lock and only the thread holding the lock can run the three steps. A thread that reaches lock m while another holds it has to wait.

For a single number there is a cheaper fix: an atomic instruction such as fetch-and-add does the load, the add and the store as one step that nothing can split, so no lock is needed. Compare-and-swap is the general version: store the new value only if memory still holds the value you read, and otherwise read again and retry.

The withdrawals went wrong even though the subtraction was atomic.

Locks have a cost. A waiting thread does no useful work, and a lock held across slow code makes the threads take turns, so adding threads stops helping. Programs therefore use several smaller locks, and that opens the door to a new failure. P1 takes R1 then R2; P2 takes R2 then R1.

With both processes taking R1 before R2, P2 may wait, but it waits for a lock whose holder needs nothing P2 holds, so the circle can't close.

Dijkstra's dining philosophers is the classic case: five philosophers round a table with a fork between each pair. Each picks up the fork on one side, then the other. If all five lift their first fork together, the waits close a circle.

• count++ is load, add, store. Threads can be paused between steps, so unlocked updates get lost, and only some interleavings show it, which is why tests miss races.
• A lock makes a critical section run in one thread at a time; atomic instructions (fetch-and-add, compare-and-swap) make a single update indivisible.
• Check-then-act needs the check and the act in one critical section: atomic steps alone aren't enough.
• Locks make threads wait. A cycle of waits is a deadlock; it needs all four Coffman conditions, and one global lock order rules it out.