Where the last guide left us stranded
In guide 2 you met the critical section — the short stretch of code that touches shared data — and the three rules any solution must obey: mutual exclusion (at most one thread inside at a time), progress (if nobody is inside, somebody who wants in gets in), and bounded waiting (no one waits forever). You also met Peterson's solution, which satisfies all three using nothing but ordinary reads and writes of two shared variables. So the problem is solved — why do we need a whole guide about hardware?
Two honest reasons. First, Peterson's solution is built for exactly two threads; generalizing it to N threads is awkward and rarely worth it. Second, and far more unsettling, it can quietly stop working on a real CPU. Peterson's whole correctness argument assumes that when one thread writes a flag and then reads the other thread's flag, those operations actually happen in that order, and that the other thread sees the write. On a modern processor neither assumption is safe by default — and that crack is where this guide begins.
The crack: the CPU reorders your memory
Here is the surprise that bites everyone once. To run fast, a CPU core does not necessarily perform your memory reads and writes in the order you wrote them. A write may sit in a per-core buffer for a while before it becomes visible to other cores, and the compiler and processor may reorder independent reads and writes when they look harmless on a single thread. On one thread this is invisible — the core preserves the illusion that everything ran in order. Across two threads sharing memory, the illusion shatters: thread A's write to its flag may still be hiding in a buffer when thread B reads it, so B sees the old value and both threads waltz into the critical section together. This collection of rules about what one core may see of another's writes is the machine's memory consistency model.
The fix is to tell the hardware, at exactly the right spots, do not reorder across here. That instruction is a memory barrier (also called a fence): it forces every memory operation issued before it to complete and become visible before any operation after it may proceed. Picture a turnstile at a concert that empties one section completely before letting the next group through — nothing slips past out of order. Correct lock-free code is peppered with barriers, and so is a correct Peterson's solution, which needs a barrier between writing your own flag and reading your neighbor's. The general principle of which reorderings are allowed and which are forbidden is memory ordering, and getting it wrong gives bugs that vanish the instant you try to look at them.
One instruction that does two things at once
Recall from guide 1 why count++ races: it is three separate steps (read, add, write) that another thread can interleave between. The root cure is to make the read-and-write happen as one indivisible step — an atomic operation, where atomicity means it either fully happens or not at all, with no halfway point any other core can observe. You cannot build that from ordinary instructions, so every modern CPU offers at least one special instruction that the hardware itself promises to perform atomically. Two are famous. The first is test-and-set: in one unbreakable step it reads a memory word, returns its old value, and stores 1 into it. Think of a single-occupancy restroom with a sign that flips to OCCUPIED the very instant you check whether it was free — you both learn the old state and claim it in the same motion, so two people can never both think it was empty.
The second, and the workhorse of modern systems, is compare-and-swap (CAS). It atomically does this: look at a memory location; if it still holds the value I expected, replace it with my new value; either way, tell me what was actually there. The conditional twist is what makes it so powerful. You read a value, compute a new one, and ask CAS to install your update only if nobody changed the value meanwhile — if someone did, CAS fails and you simply retry. This optimistic loop is the foundation of lock-free data structures, where threads make progress with no lock at all. Both of these are kinds of atomic operation, and crucially each comes with the memory ordering guarantees that plain reads and writes lacked, so the barrier worry from the last section is handled for you.
// build a lock from test-and-set (locked = 0 means free)
acquire(lock):
while test_and_set(lock) == 1: // was it already 1?
; do nothing, just loop // yes -> someone holds it, spin
// test_and_set returned 0 -> it WAS free, and we just set it to 1.
// we now hold the lock; fall through into the critical section.
release(lock):
lock = 0 // put the sign back to FREEFrom a raw instruction to a mutex you can use
Wrap an atomic instruction in the acquire/release pair above and you have invented the mutex lock — short for mutual exclusion. The contract is simple and is the everyday tool you will actually reach for: before the critical section you call acquire (often named lock), and after it you call release (unlock); the lock guarantees only one thread holds it at a time. Notice this finally satisfies all three critical-section rules cleanly, for any number of threads, and the ugly memory-ordering details are sealed inside the lock implementation where an expert handled them once. This is the payoff of the whole rung: you stop reasoning about flags and barriers and just bracket your critical section between lock and unlock.
But how should a thread that finds the lock taken actually wait? Two strategies, and the difference matters enormously. The version we wrote above just loops, re-checking the lock over and over — that is a spinlock, and the looping is busy waiting. The waiter is awake the whole time, burning a CPU core to do nothing but ask are we there yet, are we there yet. That sounds wasteful, and on a single core it is disastrous: the spinner cannot make progress, and it hogs the very core the lock-holder might need to finish and release. A spinlock only makes sense when the wait is expected to be shorter than the cost of going to sleep and waking up — which is precisely the situation inside the kernel on a multiprocessor, where the lock-holder is running on another core and will release in nanoseconds.
The alternative is a blocking lock. When a thread cannot get the lock, instead of spinning it asks the OS to put it to sleep — moved off the CPU, out of the run queue — and the scheduler runs something useful instead. When the lock is released, the OS wakes a waiter and makes it ready again. This is the right choice when the wait might be long, because a sleeping thread costs nothing but memory. Its price is the context switch to sleep and wake — overhead you only want to pay if the wait would otherwise be longer than that switch. General-purpose mutexes often blend both: spin briefly in hope of a quick win, then fall back to blocking if the wait drags on.
An honest hazard: priority inversion
Locks solve mutual exclusion, but they introduce a subtle trap worth knowing before you trust one in anything time-critical: priority inversion. It happens when a high-priority thread is forced to wait on a lock held by a low-priority thread — and a medium-priority thread, which has nothing to do with the lock, keeps preempting the low one and stops it from ever finishing and releasing. The result is upside-down: the important thread is effectively blocked by a thread it should be able to push aside, simply because that thread sits in the middle. This is not a hypothetical; it famously froze NASA's Mars Pathfinder rover until engineers patched it from millions of kilometres away.
The standard cure is priority inheritance: while a low-priority thread holds a lock that a high-priority thread is waiting for, the holder temporarily inherits the high priority, so no medium thread can preempt it — it sprints through its critical section and releases. The lesson to carry forward is broader than the fix: a lock is not a free, side-effect-free black box. It interacts with the scheduler, and using it well means thinking about who waits, for how long, and at what priority. With that caution noted, the mutex is now your reliable building block — and in the next guide we generalize it into the semaphore, a counter that can let in not just one thread but a fixed number, and that can signal as well as guard.