Synchronization primitives (locks, barriers): Visual walkthrough

Throughout, a thread is just "one worker following a list of instructions". A shared variable is a number in memory that more than one worker can read and write. That's all the vocabulary we need to begin.

Step 1 — Two workers, one number

WHAT. Picture two workers, T1 and T2. Both want to run the same tiny job: take the shared number counter and make it one bigger. In C this is the innocent line counter = counter + 1.

WHY. Before we can see a bug, we need the simplest possible situation where a bug can exist: the smallest shared thing (one number) touched by the smallest crowd (two workers).

PICTURE.

Figure — Synchronization primitives (locks, barriers)

Look at the red box in the middle — that is counter, currently holding the value $0$ . Both arrows (T1 from the left, T2 from the right) point at it. Nothing is wrong yet, because we have not looked at what "add one" really costs.

Step 2 — "Add one" is secretly three steps

WHAT. The CPU cannot add one to a memory location in a single motion. It must:

LOAD — copy counter from memory into a private scratch space (a register).
ADD — add $1$ to that private copy.
STORE — write the private copy back to memory.

WHY. This is the crux of the entire lesson. A bug can only sneak in between sub-steps. If "add one" were truly one indivisible act, there would be no gap to sneak into. So we must expose the gaps.

Each worker has its own register, drawn as its own little box. The word "register" just means "the worker's private notepad — nobody else can read it."

PICTURE.

The three stacked bars are the three sub-steps. Notice the shared counter (red) sits in the middle, but each worker's register (black boxes on the sides) is private. The dashed lines are the gaps — the dangerous moments where the CPU could pause one worker and run the other.

Step 3 — The bad interleaving, frame by frame

WHAT. Let us run the worst-case ordering. Time flows downward. I mark the value each worker holds at each instant.

$r_{1} = 0 T1 LOAD \to r_{2} = 0 T2 LOAD \to r_{1} = 1 T1 ADD \to r_{2} = 1 T2 ADD \to counter = 1 T1 STORE \to counter = 1 T2 STORE$

Reading the terms left to right: $r_{1}$ is T1's private register, $r_{2}$ is T2's private register. Both LOAD while counter still shows $0$ , so both copy the stale value $0$ . Both then ADD to reach $1$ on their own notepad. Both STORE $1$ . Two increments happened, but counter ended at $1$ , not $2$ .

WHY. This is the lost update: one worker's write silently overwrites the other's. The parent note names this exact failure — here we see the timeline that produces it.

PICTURE.

Follow the red STORE arrows: T2's store lands on top of T1's store. T1's whole increment vanished. The value we expected ( $2$ , dashed) is never reached.

Step 4 — The naive fix, and why it also breaks

WHAT. Obvious idea: guard the number with a flag. "If the flag says free, set it to held, then do your work." In code:

while (lock == true) { /* spin */ }   // wait while held
lock = true;                          // claim it

WHY. We are trying to enforce mutual exclusion — a fancy phrase meaning only one worker inside the danger zone at a time. The danger zone (the LOAD-ADD-STORE) is called the critical section.

But the check-then-set is itself two steps — read the flag, then write the flag — with a gap between them. So the very same disease reappears one level up.

$"it’s free!" T1 reads flag = f a l se \to "it’s free!" T2 reads flag = f a l se \to enters T1 sets t r u e \to enters T2 sets t r u e$

Both saw false, both walked in. Mutual exclusion is destroyed.

PICTURE.

The red gap between "read flag" and "set flag" is the same crack from Step 2, just wearing a different costume. You cannot fix a gap by adding another gap.

Step 5 — Test-and-Set: gluing read and write together

WHAT. The hardware gives us one instruction that reads the old value and writes the new value with no gap in between — indivisible. It is called Test-and-Set (TAS):

int TestAndSet(int *ptr) {
    int old = *ptr;   // read the old value
    *ptr = 1;         // write 1 (claim it)
    return old;       // hand back what was there before
}

Term by term: ptr is the address of the flag; old is what the flag held before we touched it; we unconditionally slam a 1 in; we return old so the caller learns whether they were the one who flipped it.

WHY THIS TOOL. We need an operation that cannot be split by the scheduler. TAS is the smallest such tool: it collapses read-then-write into one atomic beat. "Atomic" literally means uncuttable — no other worker can slip in mid-instruction, because the cache coherence protocol grants exactly one core exclusive ownership of that memory line for the duration.

The lock, using TAS:

void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) { /* spin */ }
}
void release(lock_t *lock) { lock->flag = 0; }

Why does this give mutual exclusion? When the flag is $0$ (free) and several workers race, TAS runs one at a time by definition of atomic. The first worker's TAS sees old = 0 (the door was open) — it gets in. Every later worker's TAS now sees old = 1 (someone already slammed a $1$ there) — they get $1$ back and keep spinning.

PICTURE.

The red block is the single unbreakable beat. Exactly one arrow (T1) emerges with old = 0 and enters; T2's TAS returns $1$ and loops. Compare this to Step 4 — the gap is gone.

Step 6 — The degenerate cases (never leave a gap unshown)

WHAT & WHY. A derivation is only trustworthy if it survives the corners. Four corners:

One worker, no contention ( $N = 1$ ): TAS reads $0$ , returns $0$ , enters instantly. No spinning. Cost is one atomic instruction. Correct and cheap.
Lock already held when you arrive: TAS reads $1$ , returns $1$ , you spin. When the holder calls release (writes $0$ ), your next TAS reads $0$ and you enter. This is the progress guarantee.
Two workers release/acquire at the exact same instant: Impossible to overlap — TAS and the store in release both act on the same memory line, and coherence serialises them. One ordering wins; the other simply sees the updated value.
Forgotten release: flag stays $1$ forever, every future acquirer spins forever. That is a self-inflicted deadlock — the lock is correct, the program is buggy.

PICTURE.

Four mini-timelines, one per corner. The red element flags what makes each corner distinct: the lone entry, the successful retry after release, the serialised clash, and the never-ending spin of the forgotten release.

The one-picture summary

The whole journey on one canvas: the gap is the villain (Steps 2–4), and the atomic beat (red) is the hero that removes it (Step 5). Naive flag = gap moved, not removed. TAS = gap glued shut → exactly one winner.

Recall Feynman retelling — tell it back in plain words

Adding one to a shared number is really fetch, bump, put back — three moves. Two workers can both fetch the old value before either puts it back, so one of the two "+1"s just disappears. That's the lost update. The tempting fix — "check a flag, then grab it" — is also fetch-then-put-back on the flag, so it has the very same crack. You cannot patch a gap with another gap. The real fix is one hardware instruction, Test-and-Set, that reads the flag and writes it in a single uncuttable beat: whoever's beat runs first sees the door open and walks in; everyone else's beat sees the door already shut and waits. Exactly one winner, guaranteed. It still wastes energy while others spin, and it deadlocks if you forget to unlock — but it is correct, and it is the foundation the fancier locks are built on.

Related: Atomic operations · Cache coherence protocols · Memory consistency models · Deadlock and livelock · Thread scheduling · Parallel algorithms