Locks and Mutual Exclusion
Two threads increment a shared bank balance at the same instant. One update vanishes without a trace. This is the canonical symptom of a race condition. The fix that every operating system, language runtime, and database provides is the lock. A lock is a simple promise: only one thread may hold it at a time. Every thread that wants to touch shared state must hold the lock first. That promise is deceptively hard to deliver correctly and efficiently. It must survive interrupts, preemption, multiple CPU cores, and compiler or hardware reordering. Locks matter because almost nothing in a real system is single-threaded. Kernels update process tables from multiple CPUs. Web servers share connection pools across worker threads. Databases serialize concurrent transactions touching the same row. Without a correct locking discipline, "it worked in testing" becomes "it corrupted data in production." Races are timing-dependent and often invisible until load, core count, or scheduling noise changes. The entire discipline of Race Conditions and the Critical Section Problem exists to name this danger precisely. Locks are the most widely used tool for taming it. The big picture: a lock turns a critical section — a block of code that touches shared state — into something that behaves, from the outside, like it executed atomically. Underneath, the lock itself must be built from something atomic. If acquiring the lock were itself racy, we would have solved nothing. That something is the hardware's atomic read-modify-write instructions, covered in Hardware Support: Test-and-Set and Atomic Instructions. This article builds the lock abstraction on top of those instructions. It covers what `acquire`/`release` must guarantee, how to implement them correctly, why naive implementations fail, and how to reason rigorously about correctness and cost. By the end, you will be able to state the lock interface precisely. You will implement a working spinlock from test-and-set, and prove it satisfies mutual exclusion. You will also diagnose the classic pitfalls (deadlock, missing memory barriers, priority inversion) that break naive locking code. This sets up the natural next questions — should a thread that cannot get the lock spin or sleep, and what happens when we need more than one permit — which are the subjects of Spinlocks versus Blocking Locks and Semaphores.
- A lock provides `acquire()`/`release()` and guarantees mutual exclusion, progress, and (ideally) bounded waiting.
- Locks must themselves be built from atomic hardware instructions (test-and-set, compare-and-swap), not from
plain loads and stores, or the lock's own state becomes racy.
- A naive "check-then-set" lock using ordinary variables is broken: the check and the set are not atomic together.
- The Test-and-Set spinlock is the canonical correct-but-costly baseline; Test-and-Test-and-Set reduces bus traffic.
- Correctness is proved via an invariant: at most one thread ever observes the lock transition from free to held.
- Locks foreshadow deeper questions: whether to spin or block while waiting, and how to generalize to counting
resources, which lead to spinlocks-vs-blocking-locks and semaphores.
A lock converts an atomic hardware instruction into a software guarantee that only one thread executes a critical section at a time.
The idea
A lock (also called a mutex, for mutual exclusion) is an abstract data type with two operations, `acquire()` and `release()`, and one implicit state: held or free. The contract is simple to state and hard to get right: a call to `acquire()` returns only when the calling thread has exclusive ownership of the lock, and no other thread may believe it also owns the lock until the owner calls `release()`. Code between a matching `acquire`/`release` pair is the critical section. A correct lock implementation must satisfy three properties, the same ones required of any critical-section solution: 1. Mutual exclusion. At most one thread is inside the critical section at any time. 2. Progress. If no thread is in the critical section and some threads want to enter, one of them eventually does — the decision of who goes next cannot be postponed forever by threads that are not even trying to enter. 3. Bounded waiting. There is a limit on how many times other threads may enter the critical section after a thread has requested entry and before that thread is granted entry. Without this, a thread can starve forever. The crucial subtlety is that the lock's own internal state — typically a single flag or integer — is itself shared data. If two threads read that flag, both see it "free," and both then set it "held," the lock has failed at the exact problem it was meant to solve. This is why a lock cannot be built purely from ordinary loads and stores; it needs an atomic read-modify-write primitive from the hardware, such as `test-and-set`, `compare-and-swap`, or `fetch-and-add`, so that "check the flag" and "set the flag" happen as one indivisible step. This is the same insight developed in Hardware Support: Test-and-Set and Atomic Instructions: mutual exclusion for the lock's own metadata is bootstrapped from a hardware guarantee, and everything built on top inherits that guarantee.
How it works
The naive (broken) approach
Before building a correct lock, it is worth seeing precisely why the obvious approach fails, because the failure mode is the whole reason atomic instructions are needed. ``` // BROKEN — do not use shared boolean lock_held = false acquire(): while lock_held == true: // busy-wait pass lock_held = true // <-- separate instruction from the check! release(): lock_held = false ``` The bug: `while lock_held == true` and `lock_held = true` are two separate machine instructions with no atomicity between them. Suppose the lock is free and threads A and B both call `acquire()` at nearly the same time: 1. A reads `lock_held`, sees `false`. 2. Context switch or second core — B reads `lock_held`, also sees `false`. 3. A sets `lock_held = true` and enters the critical section. 4. B sets `lock_held = true` (redundantly) and also enters the critical section. Both threads believe they hold the lock. Mutual exclusion is violated. The check-then-act sequence needed to be one atomic step, and it was not.
Building a correct lock: Test-and-Set
The hardware instruction `test-and-set(addr)` atomically reads the old value at `addr`, writes `true` (or `1`) to `addr`, and returns the old value — all as one indivisible operation, even on a multi-core machine with a coherent memory bus. Using this single primitive, a correct spinlock is short: ``` struct Lock { boolean flag = false // false = free, true = held } acquire(Lock L): while test_and_set(&L.flag) == true: // someone else holds it; keep trying pass // test_and_set returned false: WE set it from false to true. // We now own the lock. release(Lock L): L.flag = false ``` `test_and_set` guarantees that exactly one caller, among any number racing at the same instant, will see the return value `false` (meaning "the flag was free, and I am the one who just claimed it"). Every other simultaneous caller sees `true`, because the hardware serializes the read-modify-write at the memory-controller/cache-coherence level — this is the atomic guarantee inherited from the hardware layer.
Reducing contention: Test-and-Test-and-Set
Plain Test-and-Set spins by repeatedly issuing an atomic write, which on multi-core machines forces cache-line invalidation traffic on every iteration even while the lock is held by someone else. Test-and-Test-and-Set (TTAS) first spins on an ordinary read (cheap, hits in local cache) and only attempts the atomic instruction when the read suggests the lock might be free: ``` acquire(Lock L): while true: while L.flag == true: pass // spin on a cached read, no bus traffic if test_and_set(&L.flag) == false: return // success, we own the lock // else: someone beat us to it, loop and try again release(Lock L): L.flag = false ``` This does not change the asymptotic worst case but dramatically reduces memory-bus contention in practice, which is why real spinlock implementations use TTAS or its descendants (ticket locks, MCS queue locks) rather than raw Test-and-Set. That refinement — whether waiting threads should spin at all versus yield the CPU — is developed fully in Spinlocks versus Blocking Locks.
State machine view
A single lock instance, viewed as a state machine, has exactly two states and one guarded transition:
Complexity & correctness
Time complexity of `acquire`/`release`. `release()` is O(1): a single store. `acquire()` under Test-and-Set is O(1) in the uncontended case (the very first atomic instruction succeeds). Under contention with threads competing, the worst case is unbounded in the strict sense — pure Test-and-Set gives no bound on how long a particular thread might keep losing the race, so it fails bounded waiting in the strong theoretical sense, though in practice the probability of losing forever is effectively zero on real hardware with a fair bus arbiter. Ticket locks (a refinement not detailed here) fix this by handing out FIFO tickets, giving each thread an O(n) worst case wait but a hard guarantee of eventual entry. Space complexity is O(1) per lock: one flag (or one machine word).
Correctness argument (mutual exclusion). The proof rests entirely on the hardware's atomicity guarantee for `test_and_set`. Define the invariant: > I: At any point in time, at most one thread has, in its lifetime, received the return value `false` from a > `test_and_set` call on this lock since the most recent `release()` (or since lock creation). Because `test_and_set` executes as a single indivisible read-modify-write — the hardware guarantees no other core's memory operation can be interleaved inside it — every call to `test_and_set` on the same memory location is totally ordered by the memory system. Consider the sequence of `test_and_set` calls on a given lock in that total order. The first call after a `release()` (or after initialization) reads `flag = false` and writes `true`; it returns `false`. Every subsequent call, until the next `release()`, reads `flag = true` (because no one has reset it) and returns `true`. Hence exactly one call returns `false` per free-to-held transition, establishing I. A thread only exits its `acquire()` loop when it receives `false`, so exactly one thread exits the loop per transition — that thread, and only that thread, proceeds into the critical section. This is mutual exclusion.
Progress. As long as at least one thread is spinning and the lock is free, the very next `test_and_set` call by any spinning thread will see `false` and succeed (by the invariant argument above, since no one holds it). So the system as a whole always makes progress; it is only the individual thread's bound on waiting that TTAS/basic TAS cannot guarantee.
Bounded waiting. Basic Test-and-Set does not guarantee bounded waiting — an unlucky thread can, in a pathological schedule, lose every race indefinitely. This is an honest limitation, not a detail to gloss over; it is precisely why ticket locks and queue-based locks (MCS, CLH) exist, trading a little more state for a fairness guarantee. TTAS has identical correctness and fairness properties to TAS — it changes constant factors in the contended case, not the asymptotic guarantees.
Tradeoff to be explicit about: this whole family are spinlocks — waiting means burning CPU cycles in a busy loop. That is efficient only when the expected wait is shorter than the cost of a context switch (roughly the cost of two thread scheduling operations). When waits are long, blocking locks that put the thread to sleep are strictly better — the comparison is developed in Spinlocks versus Blocking Locks.
Worked example
Trace two threads, T1 and T2, both running `increment_balance()` protected by a Test-and-Set lock, on a shared integer `balance = 100`. Assume a single core with preemptive context switches (the same argument holds unchanged across multiple cores, since `test_and_set` is atomic bus-wide). ``` acquire(L): while test_and_set(&L.flag) == true: pass critical section: balance = balance + 10 release(L): L.flag = false ```
| Step | Thread | Action | `L.flag` before → after | Result |
|---|---|---|---|---|
| 1 | T1 | calls `acquire()`, executes `test_and_set` | `false → true` | returns `false`; T1 owns lock |
| 2 | (preempt) | scheduler switches to T2 | `true` | — |
| 3 | T2 | calls `acquire()`, executes `test_and_set` | `true → true` | returns `true`; T2 spins |
| 4 | T2 | loop condition true, spins again | `true` | still spinning (no CPU released — this is a spinlock) |
| 5 | (preempt) | scheduler switches back to T1 | `true` | — |
| 6 | T1 | executes `balance = balance + 10` (reads 100, computes 110) | `true` | `balance` now 110 |
| 7 | T1 | calls `release()`: `L.flag = false` | `true → false` | lock now free |
| 8 | (preempt) | scheduler switches to T2 | `false` | — |
| 9 | T2 | still inside its spin loop, next `test_and_set` call | `false → true` | returns `false`; T2 now owns lock |
| 10 | T2 | executes `balance = balance + 10` (reads 110, computes 120) | `true` | `balance` now 120 |
| 11 | T2 | calls `release()`: `L.flag = false` | `true → false` | lock now free |
Final `balance = 120`, the correct result of two increments of 10 starting from 100. Note step 3-4: even though T2's first `test_and_set` attempt happens while T1 is inside the critical section, T2 correctly fails to enter — this is mutual exclusion working exactly as the invariant predicts. Contrast this with the broken naive lock: if steps 1 and 3 had instead been "read flag, see false" for both threads before either wrote `true` (possible with separate load/store instructions), both would have entered and the final balance could have been 110, silently losing an update. The atomicity of `test_and_set` is precisely what step 3 relies on to correctly return `true` instead of being fooled by a stale read.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Check-then-set with plain variables | Load and store are separate instructions; a preemption or second core can interleave between them | Use an atomic read-modify-write instruction (test-and-set, compare-and-swap) for the lock's own state |
| Forgetting to `release()` on an exception/early return | Control flow exits the critical section without hitting the release line | Use RAII/`finally`/scoped-lock patterns so release is guaranteed on every exit path |
| Recursive acquire by the same thread | A thread that already holds a non-reentrant lock calls `acquire()` again and deadlocks itself | Use a reentrant (recursive) lock if re-entry is needed, or restructure to avoid nested acquisition |
| Acquiring locks in inconsistent order across threads | Thread A takes lock 1 then wants lock 2; Thread B takes lock 2 then wants lock 1 → deadlock | Impose and follow a global lock ordering everywhere in the codebase |
| Treating a spinlock as free even after seeing a stale cached "false" | Compiler or CPU reordering can let a thread believe it acquired the lock when it did not, absent a memory barrier | Ensure the atomic instruction implies the required memory barrier/fence (real hardware `test-and-set`/`CAS` instructions do this) |
| Long critical sections under a spinlock | Other cores burn cycles spinning the whole time, wasting throughput | Keep critical sections short, or switch to a blocking lock for long waits |
Pioneers & history
The lock abstraction sits at the intersection of two lines of work: the theoretical critical-section problem, and the hardware instructions that made a practical solution possible. Early software-only solutions (Dekker's and Peterson's algorithms) proved mutual exclusion was achievable with only ordinary reads and writes, but they were fragile, did not scale past two threads without complication, and offered no efficient path on real multiprocessors. The shift to hardware atomic instructions — test-and-set, compare-and-swap — is what made locks practical at scale, and it is the direct ancestor of every mutex in every modern operating system and runtime.
Origins · 1 minEdsger W. Dijkstra and how this was discovered
Dijkstra's 1965 paper on cooperating sequential processes posed the mutual exclusion problem in its modern form and proposed one of the first general algorithmic solutions for arbitrarily many processes. His subsequent invention of the semaphore gave concurrent programming its first portable, composable synchronization primitive, directly foreshadowing the lock-based reasoning used throughout modern operating systems.
Where this matters
Every general-purpose operating system kernel — Linux, Windows, the BSDs, macOS's XNU — uses spinlocks internally to protect data structures accessed by interrupt handlers and by code running on multiple CPUs simultaneously, precisely because interrupt context often cannot block. User-space thread libraries (POSIX threads' `pthread_mutex_t`, Java's `synchronized` blocks and `ReentrantLock`, C++'s `std::mutex`) present the same acquire/release contract to application programmers, built underneath from exactly the atomic instructions and reasoning shown here, usually layered with a fallback to OS-level blocking when contention is high (foreshadowing Spinlocks versus Blocking Locks). Database engines use row-level and page-level locks to serialize concurrent transactions; distributed systems generalize the same idea into distributed locks built on consensus (etcd, ZooKeeper) when "shared memory" spans machines instead of cores. Any place where multiple threads, processes, or machines touch the same mutable state, some descendant of the lock described here is doing the work of preventing a race.
Ask the tutor: How do ticket locks and MCS queue locks guarantee bounded waiting where plain Test-and-Set cannot?
What is the difference between a lock and a critical section?
A critical section is a region of code that touches shared state and must not be executed by more than one thread at once. A lock is the mechanism used to protect that region. You do not synchronize "on" a critical section directly; you wrap it with `acquire()` before entering and `release()` after leaving, and the lock's internal state is what actually enforces the mutual-exclusion guarantee. Confusing the two leads to bugs like protecting a critical section with one lock in one part of the code and a different lock elsewhere — which provides no real protection at all, since the two locks do not coordinate with each other.
Why can't Peterson's algorithm (a software-only two-thread solution) replace hardware atomic instructions everywhere?
Peterson's algorithm achieves mutual exclusion using only ordinary reads and writes, but it relies on sequential consistency — the assumption that memory operations from different threads appear in some global, per-thread-order interleaving. Modern compilers and CPUs reorder instructions and use per-core caches for performance, breaking this assumption unless explicit memory barriers are inserted. It also does not generalize efficiently past small, fixed numbers of threads. Hardware atomic instructions like test-and-set or compare-and-swap solve both problems: they carry an implicit memory barrier and work uniformly for any number of contending threads.
Is a spinlock ever a good idea, given that it wastes CPU cycles while waiting?
Yes, specifically when the expected wait time is very short — shorter than the cost of two context switches (putting the waiter to sleep and later waking it up). This is common inside operating system kernels, where a lock might be held for only a handful of instructions to update a short shared data structure. It is a bad idea when critical sections are long or contention is high, since every waiting thread burns a full CPU core doing nothing productive. This exact tradeoff — spin versus block — is the central question addressed in Spinlocks versus Blocking Locks.
What is a reentrant (recursive) lock, and why does it matter?
A reentrant lock allows the thread that currently holds it to call `acquire()` again without deadlocking itself; the lock tracks an owner and a hold count, only becoming free again once `release()` has been called as many times as `acquire()` was. This matters because recursive functions or layered APIs may legitimately need to re-enter code protected by the same lock. A plain (non-reentrant) lock, described in this article, deadlocks a thread that tries to acquire a lock it already holds, since it has no notion of "owner" — it only tracks free-or-held.
How does compare-and-swap (CAS) relate to test-and-set for building locks?
Compare-and-swap is a more general atomic primitive: `CAS(addr, expected, new)` atomically replaces the value at `addr` with `new` only if it currently equals `expected`, returning whether the swap happened. A lock can be built with CAS by treating "expected = free, new = held" exactly as test-and-set does, but CAS also supports building lock-free data structures (queues, stacks, counters) that never block at all — a strictly more powerful building block than test-and-set alone, which is why most modern hardware and languages expose CAS as the primary atomic primitive.
Does using a lock guarantee that shared memory updates become instantly visible to other cores?
Only if the lock implementation includes the appropriate memory barriers/fences, which correct hardware atomic instructions do provide as part of their semantics. `acquire()` must act as an "acquire barrier" (nothing after it in program order can be reordered before it) and `release()` must act as a "release barrier" (nothing before it can be reordered after it). This is what guarantees that a thread which successfully acquires the lock actually sees all writes made by the previous holder before that holder released it — without this, mutual exclusion on the flag alone would not protect the data the lock is meant to guard.
What happens if two locks are always acquired in different orders by different threads?
This produces a classic deadlock: Thread A holds lock 1 and waits for lock 2, while Thread B holds lock 2 and waits for lock 1, and neither can ever proceed. This is not a failure of the lock implementation itself — each individual lock still correctly provides mutual exclusion — but a failure of the program's locking protocol. The standard fix is to impose a single global ordering on all locks in the system and require every thread to acquire locks only in that increasing order, which provably eliminates this cyclic-wait pattern.