Worked examples — Synchronization primitives (locks, barriers)

This page is the practice arena for the parent topic. The parent built the machinery: locks, Test-and-Set / Compare-and-Swap, spin-lock cost formulas, and reusable barriers. Here we run those machines through every case they can face, so you never meet a scenario cold.

Before we start, a one-line refresher on the symbols we will reuse, so nothing is used before it's earned:

Recall Symbols we inherit from the parent (click to expand)

• $N$ ::: total number of threads contending for a lock or arriving at a barrier.
• $T_c$ ::: the critical-section hold time — how long one thread keeps the lock (seconds).
• $W_{avg}=T_c/2$ ::: expected wait for one arrival landing at a random moment behind a single holder.
• $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}$ ::: mean wait averaged over the positions of an $N$-deep FIFO queue.
• $t_{spin}$ ::: time for one spin-loop iteration (one failed Test-and-Set attempt).
• $E_{instruction}$ ::: energy cost of executing one instruction.
• TAS ::: Test-and-Set — atomically reads a flag and sets it to 1, returning the old value.
• CAS ::: Compare-and-Swap — writes new only if the location still equals expected.

---

The scenario matrix

Every problem this topic throws at you falls into one of these cells. Each cell is a distinct kind of trap. The examples below are labelled with the cell they hit — together they cover the whole grid.

#	Cell class	What varies	Example
A	Race baseline — no lock	interleaving order	Ex 1
B	Lock cost, low contention	small $N$	Ex 2
C	Lock cost, high contention	large $N$, queue wait	Ex 3
D	Degenerate: $N=1$	zero contention	Ex 4
E	Spin energy waste	$T_c/t_{spin}$ ratio	Ex 5
F	CAS success vs failure	expected matches or not	Ex 6
G	Barrier reuse race	generation counter	Ex 7
H	Barrier limiting case: one slow thread	straggler dominates	Ex 8
I	Real-world word problem	translate to formula	Ex 9
J	Exam twist: deadlock ordering	two locks, two threads	Ex 10

---

Cell A — the race with no lock

Forecast: guess before reading — is the final value always 2? Always 1? Or does it depend?

1. Break each thread into 3 atomic steps. Thread 1 = $L_1,A_1,S_1$ (Load, Add, Store); Thread 2 = $L_2,A_2,S_2$. Why this step? The parent showed the hardware doesn't run counter = counter+1 as one action — it's three. Correctness lives at the step level.
2. A correct result (2) needs one thread's store to happen before the other thread's load. i.e. $S_1$ before $L_2$, or $S_2$ before $L_1$. Why this step? If a thread reads after the other has stored, it sees the updated value and adds on top of it.
3. A lost update (final = 1) happens whenever both loads precede the FIRST store, e.g. $L_1{L}_2{A}_1{A}_2{S}_1{S}_2$. Why this step? Both read 0, both compute 1, both write 1 → one increment vanished.
4. Count directly. Enumerate the 20 order-preserving interleavings and simulate each. The safe condition (a store precedes the other thread's load) holds for 16 interleavings; the remaining 4 are lossy (final = 1). Why this step? Rather than argue by symmetry (which is easy to miscount), we simulate every ordering — the mechanical check the =VERIFY= block reproduces.

Verify: The number of order-preserving interleavings of two 3-step sequences is $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$. Direct simulation gives 16 safe (final value 2) and 4 lossy (final value 1). So the answer is not always 2 — it goes wrong in 4 of 20 orderings (20% of the time).

---

Cells B, C, D — spin-lock waiting time

Forecast: 40? 20? 80?

1. Recognise this is "one arrival behind one holder". Use $W_{avg}=T_c/2$. Why this step? The parent's formula: a uniformly-random arrival waits on average for half the remaining hold interval.
2. Substitute: $W_{avg}=40/2=20\mu s$.

Verify: Units: $\mu s/2=\mu s$. ✓ Half of 40 is 20. ✓

Forecast: will the mean equal $T_c/2$ again, or scale with $N$?

1. The last thread waits for all 4 ahead of it. $W_{last}\approx (N-1)T_c=4\times 40=160\mu s$. Why this step? In FIFO, position $k$ waits for the $k-1$ full critical sections in front.
2. Average over positions $0,1,2,3,4$: $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{4\times 40}{2}=80\mu s$. Why this step? The mean of the arithmetic run $0,T_c,2T_c,\dots$ is $(N-1)T_c/2$. This is a different quantity from Ex 2's $T_c/2$ — see the parent's warning.

Verify: $W_{queue\text{-}avg}=80$, and $W_{last}=160=2\times 80$ (mean is half the max of a uniform run). ✓ Contrast with Ex 2's $20\mu s$: raising $N$ from 2 to 5 raised mean wait $4\times$. This is exactly why blocking locks matter (see Deadlock and livelock and Thread scheduling).

The figure below is this example drawn out. Each blue bar is the wait suffered by a thread sitting at that queue position: the holder (position 0) waits nothing, and every step further back adds one more full critical section ($+40\mu s$), so the bars climb $0,40,80,120,160$. The red bar is the worst-placed (last) thread waiting the full $160\mu s$. The yellow dashed line is the mean $80\mu s$ — and notice it lands exactly halfway up the tallest bar, which is the geometric reason the queue average equals $(N-1)T_c/2$: the mean of an evenly-spaced run is always half its maximum. Reading the bars left-to-right lets you see the linear growth that punishes high contention.

Forecast: zero wait? or still some cost?

1. Contention wait: with $N=1$ there is no other holder, so $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{0\cdot T_c}{2}=0$. Why this step? Plugging $N=1$ into the queue formula gives 0 — the degenerate boundary sanity-checks the formula.
2. But the lock is not free: the single TAS instruction still executes (one atomic read-modify-write) plus a store on release. Why this step? Even uncontended, an atomic op forces a coherence transaction (get the line in exclusive state). This is the "uncontended lock overhead."

Verify: $(1-1)\cdot 40/2=0$. ✓ Zero waiting, non-zero instruction cost — both statements consistent.

---

Cell E — energy wasted by spinning

Forecast: milli-joules? nano-joules? how does it scale with $N$?

1. Count spin iterations per waiting thread: $\frac{T_c}{t_{spin}}=\frac{40}{0.1}=400$ iterations during one hold. Why this step? A thread spinning for the whole hold burns one instruction every $t_{spin}$.
2. Multiply by the $(N-1)$ waiters: total iterations $=400\times (5-1)=1600$. Why this step? Each of the 4 waiters spins; the holder does not spin.
3. Multiply by energy per instruction: $E_{waste}=\frac{T_c}{t_{spin}}(N-1)E_{instruction}=1600\times 2\text{nJ}=3200\text{nJ}=3.2\mu J$.

Verify: $\frac{40}{0.1}\cdot 4\cdot 2=3200$. ✓ Units: $(\mu s/\mu s)\cdot 1\cdot \text{nJ}=\text{nJ}$. ✓ Grows linearly with $N-1$ — the parent's motivation for blocking locks over spinning.

---

Cell F — CAS success vs failure

Forecast: will B's swap succeed?

1. A's call: does actual (7) equal expected (7)? Yes → write new=9. CAS returns the old actual = 7. Memory is now 9. Why this step? CAS writes only on a match and always returns what it saw. A saw 7, so it swapped.
2. B's call: does actual (9) equal expected (7)? No → no write. CAS returns actual = 9. Memory stays 9. Why this step? B's expected is stale — the world changed under it. This is the CAS failure case; a real lock-free loop would re-read and retry with expected=9.

Verify: A returns 7, memory→9 (match branch). B returns 9, memory stays 9 (no-match branch). Both cells of the CAS matrix (match / no-match) covered. ✓ See Atomic operations for how retry loops build on this.

---

Cells G, H — barriers

Before the barrier examples, two symbols we will use inside the trace:

Recall Barrier symbols for Ex 7 (click to expand)

• threshold ::: the barrier trip count — the total number of threads $N$ that must arrive before the gate opens. Here $\text{threshold}=3$.
• my_gen ::: a per-thread local copy of the barrier's current generation, recorded the moment a thread arrives, so it can tell its episode apart from the next one.
• generation ::: the barrier's shared phase counter; the last-in thread increments it to open the gate for the current episode.
• count ::: how many threads have arrived in the current generation (reset to 0 when the gate opens).

Forecast: what is generation after two full phases?

1. Phase 0 start: generation=0, count=0. Threads arrive: each records my_gen=0, then count goes $1\to 2\to 3$. Why this step? Each barrier_wait increments count under the lock and records my_gen = the generation it belongs to.
2. 3rd thread trips the threshold: count == threshold (3) → set generation=1, reset count=0, broadcast. Why this step? The last-in thread opens the gate and advances the generation. Waiters wake and check: their my_gen(0) != generation(1) → they proceed.
3. Phase 1: a fast thread loops back, records my_gen=1, count goes $1\to 2\to 3$; last-in sets generation=2, resets count=0. Why this step? Because phase-1 threads recorded my_gen=1, a stale phase-0 wakeup can't accidentally satisfy them — the generation check separates episodes. This is the exact race the parent's "reset count = 0 alone" version failed.

Verify: After two phases, generation = 2 and count = 0. Each phase advanced generation by exactly 1 and left count at 0 ready for reuse. ✓

Forecast: is the release time the average arrival, or the max?

1. A barrier releases only when the LAST thread arrives. Release time $=\max (\text{arrival times})=100\mu s$. Why this step? The definition: no thread proceeds until all $N$ have arrived — the slowest dictates.
2. Idle time = sum over the early threads of (release − their arrival). Three threads each wait $100-0=100\mu s$: total $=3\times 100=300\mu s$. Why this step? Each early thread sits blocked from its arrival until release.

Verify: Release $=100\mu s$ (max, not the mean of 25). Idle $=300\mu s$. ✓ Lesson: barriers are only as fast as the slowest thread — the motivation behind load-balanced Parallel algorithms.

The figure below is this example laid on a timeline, one row per thread. The three green dots are the punctual arrivals at $t=0$; the red dot is the straggler landing at $t=100\mu s$. The yellow bars are the idle stretches — each punctual thread is blocked from the moment it arrives until the blue dashed release line at $100\mu s$, so each yellow bar is $100\mu s$ long. The pedagogical punch: add the three equal yellow bars ($100+100+100$) and you read off the $300\mu s$ total idle by eye, and you see that it is the single red straggler — not the average arrival — that sets the release line. That is the whole point of "a barrier runs at the speed of its slowest thread."

---

Cell I — real-world word problem

Forecast: microseconds? milliseconds? which formula — $T_c/2$ or the queue one?

1. Identify the cell: 50 contenders queueing = high-contention FIFO (cell C machinery). Why this step? This is Ex 3 dressed as a word problem — pick $W_{queue\text{-}avg}$, not the single-arrival $T_c/2$.
2. Average wait: $W_{queue\text{-}avg}=\frac{(N-1)T_c}{2}=\frac{49\times 2}{2}=49\mu s$. Why this step? With 50 requests in a FIFO line, a typical request sits at a middle position; the mean over all positions is $(N-1)T_c/2$ — the same queue formula proven in Ex 3, now with $N=50$.
3. Worst request: $W_{last}=(N-1)T_c=49\times 2=98\mu s$. Why this step? The unluckiest request is dead last, waiting for all $N-1=49$ critical sections ahead of it — the top of the arithmetic run, exactly twice the mean.

Verify: $49\times 2/2=49\mu s$ average, and $49\times 2=98\mu s$ worst case $=2\times 49$. ✓ Units in $\mu s$. ✓ Real lesson: at high $N$, a single global lock serialises everything — why real servers shard the account or use per-account locks (a consistency vs throughput trade-off).

---

Cell J — exam twist: deadlock by lock ordering

Forecast: can this always complete, or is there a hang?

1. Find the deadly interleaving: A gets L1, B gets L2. Now A waits for L2 (held by B), B waits for L1 (held by A). Why this step? Each holds one lock and blocks forever on the other — the classic circular-wait cycle.
2. Confirm all four Coffman conditions hold: mutual exclusion (locks), hold-and-wait (A holds L1, wants L2), no preemption (can't steal a held lock), circular wait (A→L2→B→L1→A). Why this step? Deadlock needs all four; here they all appear, so a hang is possible (not guaranteed on every run — only on the bad interleaving).
3. The fix — global lock ordering: make every thread acquire locks in the same order, e.g. always L1 before L2. Why this step? If both A and B do acquire(L1); acquire(L2), no circular wait can form — whoever gets L1 first will get L2 next. This breaks the cycle condition.

Verify: With ordered acquisition, the "hold-and-wait cycle" $A\to L2\to B\to L1\to A$ is impossible because both request L1 first. ✓ Deep-dive continues in Deadlock and livelock.

---

Recall Self-test (cover the right side)

Final value range with no lock on two increments from 0 ::: either 1 (lost update, in 4 of 20 orderings) or 2 (safe, in 16 of 20) $W_{queue\text{-}avg}$ for $N=5,T_c=40\mu s$ ::: $80\mu s$ Wait for the last of $N=5$ threads ::: $160\mu s$ Barrier release time = ? of arrival times ::: the max (slowest thread) CAS with stale expected ::: no write, returns current value, caller retries Fix for two-lock deadlock ::: global lock ordering (same order everywhere)