Race Conditions & the Critical Section

Picture a bank account with a balance of 1000, stored in shared memory. One thread handles a deposit of 100; another, at the same instant, handles a withdrawal of 100. Each does the obvious thing: read the balance, compute the new value, write it back. If they take turns, the answer is 1000 — deposit then withdraw, order does not matter. The trouble is that they do not have to take turns, and nothing you have written so far forces them to.

Suppose both threads read 1000 before either has written anything back. The deposit thread computes 1100 and stores it. The withdrawal thread, still holding its stale copy of 1000, computes 900 and stores that, overwriting the deposit entirely. The 100 that was deposited has simply evaporated. Run the same program a thousand times and it might be correct 999 times and wrong once — because correctness now depends on who reached the store instruction first.

Shared data

Any memory more than one thread can read and write — a global, a heap object, a field both threads hold a reference to.

Race condition

A bug where the result depends on the relative timing (interleaving) of concurrent threads, not just on the code.

Interleaving

The specific order in which the scheduler happens to run instructions from different threads on this particular execution.

Nondeterminism

The property that the same program with the same input can produce different results on different runs.

The heart of the problem is that count++ is not one operation. The CPU cannot add to a memory location in a single indivisible move; it must load the value from memory into a register, add one in the register, and store the register back to memory. Three steps. And between any two of them, the scheduler is free to pause this thread and run another one — including another thread executing the very same three steps on the very same variable.

count++;   // one line of C ...

// ... is really three machine steps:
   load   reg, [count]   // 1. copy count from memory into a register
   add    reg, 1         // 2. increment the register
   store  [count], reg   // 3. copy the register back to memory

Now interleave two threads, T1 and T2, that each run count++ when count is 5. If the three steps of T1 finish before T2 starts, we get 7, as expected. But watch the bad schedule: T1 loads 5, then the scheduler switches to T2, which also loads 5. T1 adds and stores 6. T2, still holding its own 5, adds and stores 6 too. Two increments ran; count went from 5 to 6. One update was lost, and no rule was broken — every instruction did exactly what it was told.

• ▸T1: load count → reg1 = 5
• ▸T2: load count → reg2 = 5 (switched in before T1 could store)
• ▸T1: reg1 = 6, store count = 6
• ▸T2: reg2 = 6, store count = 6 (overwrites T1 with a stale value)
• ▸Result: count = 6, not 7 — a lost update.

Once you see the problem clearly, the fix has an obvious shape: never let two threads execute their read-modify-write on the same data at the same time. The stretch of code that touches shared data — the load, add, and store on count — is called the critical section. The whole game of concurrency control is making sure that at most one thread is inside a given critical section at any moment. That guarantee has a name: mutual exclusion.

It helps to divide each thread’s code into four regions. The critical section is the sensitive part. Wrapped around it are an entry section, where a thread asks permission to go in, and an exit section, where it signals that it has left so someone else may enter. Everything else — the work that touches only a thread’s own local data — is the remainder section, and it never needs protecting.

Critical section

The region of code that accesses shared data and must not run concurrently with another thread’s access to the same data.

Mutual exclusion

The guarantee that at most one thread is executing inside a given critical section at a time.

Entry section

The code just before the critical section where a thread requests and waits for permission to enter.

Exit section

The code just after the critical section that releases the section so another waiting thread can proceed.

Mutual exclusion alone is not enough to call a solution correct. A gate that keeps everyone out forever technically prevents two threads from being inside at once, but it is useless. So a correct critical-section solution must satisfy three properties together, and it is worth stating each one precisely, because real bugs come from quietly dropping one of them.

Mutual exclusion

If one thread is executing in its critical section, no other thread may be executing in its critical section at the same time.

Progress

If no thread is in the critical section and one or more want in, the choice of who enters cannot be postponed indefinitely, and threads doing only their remainder work cannot block that choice.

Bounded waiting

There is a limit on how many times other threads can enter the critical section after a thread has requested entry and before that request is granted — so no thread is starved forever.

Read them as three different failures you are ruling out. Break mutual exclusion and you get the lost-update race we just dissected. Break progress and threads that could safely proceed are needlessly blocked, or the whole system stalls with the section empty and everyone waiting. Break bounded waiting and one unlucky thread is repeatedly overtaken, waiting forever while others cut ahead — starvation. A solution is only trustworthy when it holds all three at once.

The natural first idea is a shared boolean flag: if it is false the section is free, so set it to true, do your work, then set it back to false. It reads like a lock. It even works most of the time, which is exactly what makes it dangerous. But the flag protecting the critical section is itself shared data touched by a read-modify-write — and we already know what happens to those.

int locked = 0;                 /* shared flag: 0 = free, 1 = held */

void enter(void) {
    while (locked == 1) { }     /* 1. wait while someone holds it */
    locked = 1;                 /* 2. claim it ... but AFTER the check */
}

void leave(void) {
    locked = 0;                 /* release */
}

The gap sits between line 1 and line 2. Thread T1 reads locked as 0 and breaks out of the while loop. Before T1 can execute locked = 1, the scheduler switches to T2, which also reads locked as 0, also breaks out, and also proceeds. Now both threads set locked = 1 and both walk into the critical section together. Mutual exclusion is broken by the very code meant to enforce it — because "check if free" and "claim it" were two instructions with a window in between.

You cannot patch this by being cleverer with ordinary reads and writes alone; strict two-thread schemes exist (Peterson’s algorithm is the classic) but they are intricate, do not scale past a couple of threads, and modern CPUs reorder memory operations in ways that break their assumptions. The lesson is not "try harder". It is that we need a primitive the hardware guarantees to be indivisible — check-and-set as one unbreakable step.

The word underneath everything so far is atomicity. An operation is atomic if it happens all at once, indivisibly: no other thread can observe it half-finished, and it cannot be interrupted partway through. count++ is not atomic because its three steps can be split apart. If the hardware gave us an atomic increment — load, add, and store fused into one uninterruptible instruction — the race in section two simply could not occur, because there would be no gap to slip into.

This is why "just be careful" is not a strategy. Carefulness cannot make a three-step sequence into one step. The scheduler can preempt your thread between any two machine instructions, on any run, and it will eventually pick the one schedule that breaks you — usually in production, under load, months after the code shipped. Correctness here has to be a guarantee provided by a mechanism, not a hope resting on good intentions.

And the ground is even less solid than it looks, because the interleaving of threads is not the only reordering in play. To go faster, both the compiler and the CPU may reorder memory reads and writes as long as a single thread cannot tell the difference — but another thread can tell, and sees operations happen in an order your source code never wrote. Taming this needs atomic instructions and memory barriers, hardware features we take on directly in the next chapter.

Atomic operation

One that completes indivisibly — no other thread ever sees an intermediate, half-applied state.

Non-atomic (composite)

An operation made of several steps (load-modify-store) that a thread can be interrupted between.

Memory reordering

The compiler and CPU may execute reads/writes out of program order for speed; other threads can observe the reordered order.

Memory barrier

A special instruction that forbids reordering across it, restoring an order other threads can rely on (covered next chapter).

This is not a museum piece for exams. The bank balance is any counter under concurrency: two web requests incrementing a "likes" or "views" total, two workers decrementing an inventory count, two threads bumping a metrics gauge. Each request reads the current value, adds one, and writes it back — the exact lost-update race — and the symptom is a total that drifts steadily below the truth, worse the more traffic you get. Plenty of production counters are quietly wrong for precisely this reason.

The second classic is check-then-act, also called TOCTOU — time-of-check to time-of-use. You check a condition and then act on it, but the world can change in the gap between the two. "If no user with this email exists, create one": two concurrent signups both pass the check, both insert, and now you have duplicates or a crash. "If the file does not exist, create it"; "if balance ≥ amount, withdraw" — same shape, same gap. The check and the act must be one atomic step, or the check means nothing.

• ▸Lost updates: concurrent read-modify-write on a shared counter silently drops increments.
• ▸Check-then-act / TOCTOU: a condition verified, then acted on, is invalidated in the window between.
• ▸Non-atomic ++: a plain counter shared across threads or requests is never safe without synchronization.
• ▸Fix pattern: shrink the critical section, then guard it — a lock, an atomic instruction, or a single atomic DB statement.

The cleanest place to see the whole idea scaled up is a database. Two transactions selling the last item both read stock = 1, both write stock = 0, and you have oversold — a lost update at the row level. This is why databases are built around exactly the tools of this chapter: row locks that enforce mutual exclusion, and MVCC (multi-version concurrency control), which lets readers see a consistent snapshot while a writer works. The critical section did not disappear when we moved from threads to transactions; it just moved into the database engine.