The Critical Section Problem & Atomicity

Language-specific mechanics: Concurrency Language Manual — Concurrent Collections, Shared State & Debugging Tools →

The critical section, formally defined

A critical section is a segment of code that accesses shared, mutable state such that allowing more than one thread to execute inside it at the same time could leave that state inconsistent or produce an incorrect result. The classic way to structure a thread's interaction with a critical section is in four parts:

Section	Purpose
Entry section	Request permission to proceed — the protocol a thread runs before touching the shared state
Critical section	The actual code that reads/writes the shared state
Exit section	Release permission, signaling that the shared state is available again
Remainder section	Everything else the thread does that never touches this particular shared state

The critical section problem is the problem of designing an entry/exit protocol every thread follows so the critical section is protected correctly — without assuming anything about relative thread speeds, and without knowing in advance how many threads there are or when they'll want in.

The three requirements a correct solution must satisfy

A protocol isn't "correct" just because it happens to prevent corruption in the cases you tried. The formal definition — going back to early operating systems theory — requires all three of the following simultaneously:

Requirement	Definition	What breaks without it
Mutual exclusion	If a thread is executing in its critical section, no other thread may be executing in its critical section for the same shared resource	The direct correctness property — two threads mutating the same state concurrently corrupts it
Progress	If no thread is currently in the critical section and one or more threads want to enter, the decision of who goes next cannot be postponed indefinitely — and only threads that actually want to enter get a say in that decision	A solution that "just never lets anyone in" trivially satisfies mutual exclusion but is useless: the system deadlocks or livelocks instead of making progress
Bounded waiting	There's a finite, known bound on how many times other threads can enter their critical section ahead of a thread that's already requested entry, before that thread's request is granted	Without this bound, a thread can be perpetually skipped in favor of others — starvation, which gets its own formal treatment in the Deadlock, Livelock & Starvation topic later on this roadmap

Two implicit assumptions sit underneath all three: threads execute at unpredictable, arbitrary relative speeds (you cannot design a solution that only works if thread A happens to be faster than thread B), and only threads that actually want to enter get to influence who enters next — a thread off in its remainder section can't block or delay anyone.

Worth noting explicitly: mutual exclusion alone is not a solution. A protocol that satisfies mutual exclusion by simply never admitting any thread is correct on that one axis and completely fails the other two. Interviewers listening for this topic are listening for all three properties, not just the first one people usually remember.

Why naive attempts fail — and why that failure looks familiar

A first instinct is to protect a critical section with a plain shared boolean:

// naive, BROKEN mutual-exclusion attempt using an ordinary flag
while (lock == true) { /* spin, waiting */ }
lock = true
    ... critical section ...
lock = false

This fails for a reason that should look familiar from the previous subtopic: the check (while lock == true) and the set (lock = true) are two separate, unsynchronized operations on lock. Two threads can both observe lock == false before either sets it true, and both proceed into the critical section together — mutual exclusion violated. The guard variable meant to prevent a race has a race of its own; the bug reproduces at whatever level you stop enforcing atomicity, business data or synchronization mechanism alike.

Historically, this is exactly what purely software-based algorithms like Dekker's and Peterson's were built to solve for two threads: carefully ordered reads and writes across two or three shared variables (not just one flag) satisfy all three requirements without special hardware support. They're worth knowing exist, but modern practice relies on hardware-provided atomic instructions instead — the next piece of the puzzle.

Atomicity: what it actually buys you

An operation is atomic if, from the perspective of every other thread, it appears to happen either completely or not at all — no other thread can ever observe a partially-completed intermediate state. It's useful to separate this into two levels:

Hardware/primitive atomicity. A single CPU instruction the hardware guarantees can't be torn or interrupted partway through — a compare-and-swap, or a properly aligned read/write of one machine word. This guarantee comes from the hardware directly, independent of any language or library.
Logical (compound) atomicity. A multi-step sequence — a read-modify-write, a check-then-act, an entire multi-statement transaction — that your program needs to behave as one indivisible unit, even though it compiles to many machine instructions. This never comes for free; it has to be constructed, either by wrapping the sequence in mutual exclusion, by using a hardware atomic instruction in a retry loop, or by redesigning to avoid the shared mutable state entirely.

The critical section is precisely the technique for manufacturing level-2 atomicity out of level-1 primitives: wrap a compound operation in a correctly-synchronized entry/exit protocol, and the whole block behaves as atomic to every other thread — even though, mechanically, it's still several separate instructions running one after another.

The classic time-of-check-to-time-of-use trap

Time-of-check-to-time-of-use (TOCTOU) is the general name for a logical-atomicity violation: a thread checks some condition, then acts based on that check, with a gap between the two where the world can change out from under it.

if balance >= amount:      # time of check
    ... other thread changes balance here ...
    balance -= amount      # time of use — decision is now stale

Notice that protecting the check and the act individually — locking only around the read and locking only around the write, as two separate critical sections — does not fix this. Each access is safe in isolation, but the pair together is not; the fix requires treating "check and act" as a single critical section held for the entire duration of both steps. This same shape reappears constantly outside of counters and balances — file-existence checks followed by file access, cache-then-populate patterns, and "get-or-create" logic are all instances of the identical bug.

Pitfalls and interview gotchas

Reciting only "mutual exclusion" when asked for the critical section requirements. A complete answer names all three — mutual exclusion, progress, bounded waiting — and can explain why a solution satisfying only the first is still wrong (it can trivially deadlock or livelock).
Assuming a lock around each individual access makes a multi-step sequence safe. Atomicity has to cover the entire logical operation, not each access separately — exactly the TOCTOU trap above, and one of the most common real-world concurrency bugs (see the "atomicity violation" category in empirical bug studies like OSTEP's).
Treating "atomic" as a fixed, all-or-nothing feature. Atomicity is always relative to a specific operation. An atomic counter is atomic for increments — it says nothing about a compound "read, then reset if over threshold" sequence built on top of it.
Forgetting that guard/lock variables themselves must be manipulated atomically. You cannot build synchronization out of ordinary, unsynchronized reads and writes on the lock variable — this is why real locks are built on hardware primitives like compare-and-swap, not plain booleans.
Conflating "critical section" with "lock." A lock is one common mechanism for implementing the entry/exit protocol, but semaphores, monitors, and lock-free compare-and-swap loops all solve the exact same underlying problem — knowing the distinction signals you understand the problem, not just one tool for it.

Where this leads

At this point you have precise language for both halves of the problem: the disease (data races, and the race conditions they can cause) and the specification for a cure (the critical section problem's three formal requirements, and what atomicity actually means). Locks & Mutual Exclusion, the next topic on this roadmap, is the first — and most common — concrete mechanism for satisfying all three requirements in real, production code.

Wrapping the entire check-then-act pair — not just the write — is what makes the compound operation behave atomically.

type BankAccount struct {
    mu      sync.Mutex
    balance int
}

func (a *BankAccount) Withdraw(amount int) bool {
    a.mu.Lock()         // entry section
    defer a.mu.Unlock() // exit section, even on panic
    if a.balance < amount { // check
        return false
    }
    a.balance -= amount     // act
    return true
}

Wrapping both the check and the act under the same Mutex is what makes the pair atomic. Locking only around the decrement still lets two goroutines both pass the check. sync.Mutex is not reentrant and must not be copied after first use — embed it in the struct and never pass that struct by value afterwards.

An alternative to a lock: push the read-modify-write down into a single hardware-guaranteed atomic step instead of protecting it with entry/exit sections.

var counter atomic.Int64 // Go 1.19+ typed atomic

var wg sync.WaitGroup
wg.Add(2)
for i := 0; i < 2; i++ {
    go func() {
        defer wg.Done()
        for j := 0; j < 100_000; j++ {
            counter.Add(1) // one atomic RMW, not load+add+store
        }
    }()
}
wg.Wait()
fmt.Println(counter.Load()) // reliably 200000

atomic.Int64.Add is a hardware-backed read-modify-write with the same happens-before guarantees as a mutex unlock/lock. Prefer the typed wrappers (Go 1.19+) over the older atomic.AddInt64(&n, 1) form. This is the lock-free fix for the lost-update race above; go run -race is clean.