Foundations — Synchronization primitives (locks, barriers)

Before you can read the parent note on Synchronization primitives, you must own every word it throws at you without warning. Below, each idea is built from nothing, drawn as a picture, and justified. Read top to bottom — nothing uses a term defined lower down.

1. Thread — the "worker" that runs your code

The picture: a worker with a finger tracing down a list of steps. When there are two workers, two fingers move down two (possibly identical) lists at the same time.

Why the topic needs it: if there were only ever one thread, there would be no race, no lock, no barrier — nothing to synchronize. The whole chapter exists because two or more threads share something. See also Thread scheduling for who decides which worker runs when.

2. Shared memory & shared variable — the paper both workers write on

The picture: a single box labelled counter sitting on a table, with arrows from both workers pointing into it. There is exactly one box, not one per worker.

Why the topic needs it: the danger only exists when the box is shared. If each worker had their own private box, edits could never collide. "Shared" is the precondition for everything that follows.

3. Concurrent, interleave, and the timeline

The picture: two horizontal timelines, one per thread, with little step-blocks. Slide one timeline left or right and the blocks fall into a different combined order. Every legal slide is a possible run of the program.

Why the topic needs it: the parent's "lost update" is one specific bad interleaving. You cannot understand why a lock is needed until you can see the timeline sliding.

4. LOAD / ADD / STORE — one line of C is really three machine steps

The picture: the worker photocopies the box's number onto their own private sticky note (LOAD), scribbles +1 on the sticky note (ADD), then walks back and overwrites the box (STORE). While they hold the sticky note, the shared box is stale — anyone else who LOADs now reads the old value.

Why the topic needs it: the gap between LOAD and STORE is exactly where a second worker can sneak in and read a value that is about to become wrong. This three-step split is the mechanism of the race.

5. Atomic — the indivisible step

The picture: contrast two boxes. The left "non-atomic" LOAD-ADD-STORE has a dashed danger-zone in the middle where an intruder arrow can enter. The right "atomic" operation is a solid sealed block — the intruder arrow bounces off.

Why the topic needs it: the broken flag lock fails because check-then-set is not atomic. The fix (TestAndSet, CompareAndSwap) is a hardware atomic operation. Atomicity is what makes those instructions trustworthy. Deep dive: Atomic operations.

6. Critical section & mutual exclusion

The picture: a small room with a single doorway. The room is the critical section; the rule "only one person in the room" is mutual exclusion. The lock is the door.

Why the topic needs it: a lock's entire job is to enforce mutual exclusion around a critical section. These two words are the goal that every lock design is measured against.

7. The lock lifecycle: acquire, release, block, spin

The picture: a queue outside the single doorway. A spinning waiter keeps rattling the handle every microsecond (busy, hot). A blocking waiter sits on a bench and asks to be tapped on the shoulder when it's their turn (idle, cool).

Why the topic needs it: the parent contrasts spin locks vs. blocking locks. Their trade-off (CPU wasted vs. wake-up delay) only makes sense once "spin" and "block" are concrete pictures.

8. Condition variable, wait, broadcast

The picture: sleepers on benches under a bell. broadcast rings it; everyone wakes, glances at a sign on the wall, and either walks through or sits back down.

Why the topic needs it: the correct barrier is built from a lock plus a condition variable. Without wait/broadcast you cannot make threads sleep and wake as a group.

9. The counting symbols: $N$, count, threshold, generation

The picture: a turnstile with a mechanical tally. Each arrival clicks the tally up by one; when the tally hits $N$ the gate springs open, resets to $0$, and a small "round" dial advances by one.

Why the topic needs it: the parent's barrier code manipulates exactly these four values. generation is the star fix for the reuse race — you must know what each symbol counts to follow that argument.

10. Cache coherence & memory ordering (the ground under everything)

The picture: several cores each holding a small private photocopy of the shared box, with an invisible referee (the coherence protocol) making sure that when one core writes, everyone else's photocopy is either updated or torn up.

Why the topic needs it: TestAndSet is "atomic" only because coherence forbids another core from touching that line mid-operation. Locks sit on top of these guarantees.

How the foundations feed the topic

Related destinations once you have the foundations: Deadlock and livelock, Parallel algorithms.

Equipment checklist

Cover the right side and answer aloud. If any answer is fuzzy, re-read that section before the parent note.