Synchronization &
Concurrency Control

edits_logged++ looks atomic — one statement, done in an instant. It isn't. Every real CPU turns it into at least three separate steps: load the current value into a register, add one, write the register back. Chapter 1 already told you why this matters: the scheduler can switch threads between any two instructions, not just between statements.

Two people editing the same tally

Imagine two people sharing one running tally on a whiteboard, each walking up independently to add one to it. Each reads the current number, does the addition in their head, then writes the new number down. If both read before either writes, both compute "old value plus one" — and the second person to write erases the first person's update entirely, even though both genuinely did their job. Nobody made a mistake. The timing did.

Formal definitions

A race condition is exactly this: a situation where the final result of concurrent operations on shared data depends on the precise timing of their execution, rather than being determined by the logic of the program alone. The critical section is the specific piece of code that touches the shared data — for T_ui and T_save, the single line edits_logged++, each time either of them executes it.

Any correct solution to the critical section problem — any scheme for deciding who may be inside their critical section at a given moment — must guarantee three things:

Figure 1 · watching the update get lost

Before there was a proper tool: three attempts using only shared variables

It's worth seeing, briefly, what people tried before reaching for the toolkit in Section 3.2 — because every one of those tools exists specifically to make this next part unnecessary.

Hardware eventually offered a cleaner way out: an atomic TestAndSet instruction that reads and sets a lock variable in one indivisible step, closing the lock variable's race directly rather than working around it with a proof. But TestAndSet alone still leaves a thread spinning — burning a full CPU core — for as long as it waits. None of these three give a programmer a reusable, safe, efficient building block. That's precisely the gap Section 3.2 fills.

Practice 3.1

1. Is x = 5 (assigning a constant, not derived from x's old value) a critical section if two threads could execute it concurrently on the same x?
   Show solution

   No — whichever thread's write happens last simply wins, and x ends up 5 either way, since neither write depends on reading the old value first. A race condition specifically requires the result to depend on timing; here, every possible timing produces the same final value.

2. Variation. T_ui and T_save both execute edits_logged++ starting from 41, but this time T_ui's three instructions complete fully before T_save starts. What's the final value?
   Show solution

   43. With no interleaving, T_save's LOAD reads the value after T_ui's STORE, so it correctly starts from 42 and produces 43. Sequential execution of the exact same two increments is perfectly safe — the danger was always the interleaving, not the operation itself.

3. Interpretation. Why does strict alternation satisfy mutual exclusion but fail progress, in one sentence each?
   Show solution

   Satisfies mutual exclusion: turn holds one value at a time, so only one thread's wait loop can exit at once. Fails progress: a thread that doesn't want the critical section can still hold turn at its own value indefinitely, blocking the other thread out even when the critical section is free and wanted.

4. Synthesis. Peterson's solution and the naive lock variable both use a flag-like variable. What does Peterson's solution add that actually fixes the lock variable's race?
   Show solution

   The lock variable's race comes from "check, then set" not being atomic. Peterson's solution never has a thread check its own intent flag before setting it — each thread unconditionally sets flag[i] = true first, so that write can never race with itself. The turn variable then breaks the remaining tie deterministically: whichever thread's write to it happens last is the one the waiting condition actually reads.

Section 3.1 ended on a gap: no software trick using only ordinary variables gives you an easy, efficient, reusable way to protect a critical section. Edsger Dijkstra closed that gap in the early 1960s with a single idea that's still how most concurrent code is written today.

The semaphore

Think of a semaphore as a key rack with a counter on it. If the counter is positive, you take a key and the count drops by one. If it's zero, you wait — someone has to return a key first. A semaphore is exactly this, formalised as an integer S with two operations, and critically, both operations are atomic: the hardware or kernel guarantees each one runs as a single indivisible step, so the race from Section 3.1 can't recur inside the semaphore itself.

A binary semaphore is constrained to 0 or 1 and behaves like a lock: initialise it to 1, and wait/signal pairs enforce mutual exclusion directly.

Three lines, versus Peterson's eight, and this version works for any number of threads without a single change — not just two. A counting semaphore is the same construct initialised to any N, modelling a pool of N interchangeable resources rather than a single lock.

Worked example: the bounded buffer

T_save now has company: T_flush, a background thread that drains autosave snapshots out of a small 3-slot in-memory buffer and writes them to disk. This is the classic producer-consumer problem, and it needs three semaphores at once:

Figure 2 · two producers' worth of snapshots, one flush

Spin, or block? Revisited with a real mutex

A semaphore's wait has the same choice a hand-rolled TestAndSet lock did: when a thread can't proceed, does it spin, or give up the CPU? Reusing Chapter 1's measured context- switch cost settles it numerically.

Real semaphore implementations block by default (a thread that calls wait on an unavailable semaphore is put to sleep, not spun) — but the underlying mutex protecting the semaphore's own counter is almost always a short-held spinlock, precisely because that critical section is only a few instructions long, deep in spin territory on this chart.

Monitors: mutual exclusion you can't forget

A semaphore is powerful and easy to misuse — nothing stops you from calling wait twice, forgetting signal, or acquiring two semaphores in the wrong order. A monitor, introduced by C.A.R. Hoare and Per Brinch Hansen in the early 1970s, bundles shared data together with the only procedures allowed to touch it, and the language or runtime automatically ensures only one thread executes inside at a time — there's no explicit wait(mutex)/signal(mutex) to forget, because the compiler put it there for you.

Condition variables: waiting for something else to become true

Mutual exclusion alone isn't enough for the bounded buffer — T_flush needs to wait for a specific condition ("the buffer isn't empty"), not just for the lock. A condition variable gives a monitor exactly this: wait(cv) atomically releases the monitor's lock and blocks the thread; signal(cv) wakes (at most) one waiter.

Practice 3.2

1. A binary semaphore mutex is initialised to 1. Thread A calls wait(mutex) twice in a row without an intervening signal. What happens the second time?
   Show solution

   mutex drops to −1, which is negative, so Thread A blocks itself on its own second call — a self-deadlock. This is exactly the "forgot to structure the code carefully" bug the note above warns about: nothing prevents calling wait twice, and the semaphore has no notion of "who already holds it."

2. Variation. In the bounded buffer, what would go wrong if empty were initialised to 5 instead of 3, while the actual buffer array still only has 3 slots?
   Show solution

   T_save could be let through wait(empty) up to 5 times before any consumption happens, but the buffer only has room for 3 — the 4th and 5th snapshots would overwrite buffer memory that's already in use. The semaphore's initial value must always match the real physical capacity it's modelling; get that number wrong and the semaphore will happily authorise more concurrent access than the resource can actually support.

3. Interpretation. A monitor's condition-variable wait call is documented as releasing the monitor's lock before blocking. Why does it have to do both atomically, as one step?
   Show solution

   If releasing the lock and blocking were two separate steps, a signalling thread could acquire the lock and call signal in the gap between them — a signal sent before the waiter is actually registered as waiting is simply lost, and the waiter then sleeps forever waiting for a wake-up that already happened. Making release-and-block one atomic operation is exactly what closes that gap.

4. Synthesis. Connect Mesa semantics' "recheck in a while loop" requirement back to Chapter 2's scheduler: why can't a woken thread simply assume it will run immediately?
   Show solution

   Being moved from blocked to ready doesn't grant the CPU — Chapter 2 established that a ready thread still has to wait its turn under whatever scheduling algorithm is running. Any other thread that runs first, including another one just woken from the same condition variable, can change the shared state before the original waiter actually gets scheduled. Mesa semantics is really just being honest about a fact Chapter 2 already established: "ready" is not "running."

Sections 3.1 and 3.2 fixed who gets to run inside a critical section. This section is about a quieter, sneakier problem: even with no race at all on any single variable, two threads on two different CPU cores are not guaranteed to see each other's writes in the order those writes actually happened.

A note on the fridge, read from an old photo

If you write "dinner's ready" on a sticky note and put it on the fridge, your housemate reading it a minute later just works — you're both looking at the same physical note. Now imagine your housemate is looking at a photo of the fridge from their phone instead, one that syncs every so often. They might see the note appear before the food is actually finished cooking, or the food finished before the note appears, depending entirely on when the photo happened to sync. Multiple CPU cores, each with their own cache, are exactly this: each core has its own "photo" of memory, refreshed on its own schedule unless something forces a sync.

Sequential consistency, formally

The model every programmer intuitively assumes is sequential consistency, formalised by Leslie Lamport in 1979: the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in that sequence in the order specified by its own program. In plain terms: writes from any one thread stay in the order that thread issued them, and every other thread agrees on some single global ordering of everyone's operations.

Worked example: the flag that lied

T_save writes the actual autosave bytes to a buffer, then sets save_complete = true so T_ui can show a "Saved" indicator. T_ui's code checks the flag, and if it's true, reads the buffer to confirm. Both threads look correct in isolation. Running on two different cores with no synchronization between them, they aren't.

Figure 3 · the same two writes, two legal orders

The fix: the same tools from Section 3.2, used correctly

Wrapping both of T_save's writes — and T_ui's read — in the mutex from Section 3.2 fixes this, not incidentally but by design: real mutex and semaphore implementations include the necessary memory barriers as part of acquiring and releasing the lock. Get the mutual exclusion right, using the real primitives, and the visibility problem is solved as a side effect. Language-level tools work the same way: C++'s atomic types with an explicit memory_order, or the humble volatile keyword in some languages, exist specifically to tell the compiler and CPU "don't reorder across this point."

Practice 3.3

1. Two threads run on the same single CPU core (no real parallelism, just time-sliced). Does the reordering problem in Figure 3 still apply?
   Show solution

   Much less so. A single core executing instructions from multiple threads (via context switches) still sees its own writes in program order from its own perspective, and typically flushes its store buffer on a context switch. The dangerous reordering in Figure 3 is specifically a multi-core problem, where two cores have physically separate caches and no inherent reason to agree on ordering without explicit synchronization.

2. Variation. If T_save used a mutex around its two writes, but T_ui read save_complete and the buffer without acquiring any lock at all, is the visibility problem fixed?
   Show solution

   Not necessarily. A mutex's guarantees are strongest when both sides of a shared access go through it — the barrier on the writer's release doesn't help a reader that never synchronizes with it at all. Correct fixes require the reader to also go through a corresponding acquire (the same mutex, or a matching atomic load with the right memory order), not just the writer using one.

3. Interpretation. A developer says "this bug only happens on the ARM build, never on x86 in years of testing." What does that suggest about the bug?
   Show solution

   It's very likely a missing-synchronization / reordering bug of exactly the kind this section covers — x86's stronger TSO model happens to forbid the specific reordering the buggy code depends on not happening, while ARM's weaker model permits it. "Works on x86" is not evidence of correctness here; it's evidence the code was never actually safe, just running on hardware forgiving enough to hide it.

4. Synthesis. Explain why Section 3.2's monitors don't need a separate "memory consistency" discussion of their own.
   Show solution

   A correctly implemented monitor's automatic locking already includes the same memory barriers a manually-used mutex would need — entering and leaving the monitor's automatic critical section provides the acquire/release ordering for free. The visibility problem in this section is precisely what you get when someone tries to hand-roll synchronization with a plain flag instead of using one of Section 3.2's real primitives.

Every tool in Section 3.2 works the same way: if you can't proceed, you wait — spinning or blocked — for someone else to finish. That waiting is exactly where deadlock, priority inversion, and the convoy effect come from. A different family of designs asks: what if nothing ever waited?

What locks cost, beyond the wait itself

• Deadlock. Two threads each holding a lock the other wants, forever — Unit 4 gives this its own full treatment.
• Priority inversion. A low-priority thread holding a lock blocks a high-priority thread that needs it — directly undermining the real-time guarantees Chapter 2's EDF and RMS worked so hard to prove.
• The convoy effect, again. If the thread holding a lock is preempted mid-critical-section (Chapter 2), every other thread waiting on that lock is stuck too, no matter how ready they otherwise are.

Lock-free: retry instead of wait

A lock-free algorithm never blocks. Instead, it reads the current state, computes a new state, and tries to install it with a single atomic Compare-And-Swap (CAS) instruction: "update this memory location to the new value, but only if it still holds the value I originally read." If some other thread got there first, the CAS simply fails — harmlessly — and the thread tries again with a fresh read.

The guarantee is subtle and worth stating precisely: lock-free means the system as a whole always makes progress — some thread's CAS succeeds every time there's contention — not that any particular thread is guaranteed to succeed on any particular try.

Worked example: the exact interleaving that broke Section 3.1, revisited

Final value: 43, correct — both increments counted. This is the exact interleaving that produced a lost update in Section 3.1's Figure 1; CAS doesn't prevent the collision, it detects it and forces a retry instead of silently overwriting.

The ABA problem

CAS checks whether a value is unchanged, not whether it's been untouched. If a value leaves A, becomes something else, and returns to A before a delayed CAS checks it, the CAS sees "still A" and proceeds — even though the underlying structure changed meaningfully in between.

Thread 1's CAS never noticed anything was wrong — head really was A at the instant it checked. The stack now points at B, which Thread 2 already freed. The standard fixes: attach a version counter to the pointer that increments on every change, so CAS compares pointer and tag together (a stale match can't slip through); or hazard pointers, where threads publish which nodes they're currently touching so those nodes can't be freed out from under them.

Practice 3.4

1. A thread's CAS fails three times in a row before succeeding on the fourth attempt. Has the algorithm violated the lock-free guarantee?
   Show solution

   No. Lock-free only promises the system makes progress on every contended attempt — some thread succeeds each time — not that any specific thread succeeds quickly. Three failed retries followed by a fourth success is exactly what "lock-free, not wait-free" looks like in practice.

2. Variation. If edits_logged's CAS-based increment were used instead by five threads simultaneously rather than two, does the correctness argument in the worked example still hold?
   Show solution

   Yes, unchanged. Each thread's CAS still only succeeds if the value it read hasn't changed since; with five threads instead of two, more retries will typically be needed under contention, but the same detect-and-retry logic handles any number of colliding threads without modification — unlike Peterson's solution, which was explicitly limited to two.

3. Interpretation. A lock-free stack implementation using tagged pointers is reported to "waste" a few bits of every pointer on a version counter. Why is this considered an acceptable trade-off?
   Show solution

   Those bits are the entire fix for the ABA problem: without them, a CAS genuinely cannot distinguish "unchanged" from "changed and changed back," which can silently corrupt the structure. A few bits of overhead per pointer is cheap compared to a data structure that is occasionally, unpredictably wrong.

4. Synthesis. Explain why a lock-free algorithm still needs the memory-consistency guarantees from Section 3.3, even though it never uses a mutex.
   Show solution

   CAS is atomic with respect to the single memory location it operates on, but a thread's read of the "old" value and its use of any other related data still needs proper ordering guarantees to avoid the reordering hazard in Figure 3. Atomicity of one operation and consistent visibility of everything around it are separate problems — lock-free code solves the first without automatically solving the second.