Exercises — Synchronization primitives (locks, barriers)

The fix is a lock (mutex) built on a hardware atomic such as Test-and-Set or Compare-and-Swap. A plain bool flag fails because "check then set" is two instructions — between the check and the set, the other thread slips in. Only an atomic read-modify-write reads the old value AND writes the new value in one indivisible step, so exactly one thread can win. See Atomic operations.

• (a) Lock — protects one shared variable from simultaneous writes (mutual exclusion).
• (b) Barrier — a meeting point where all $N$ threads wait until everyone has arrived, then all proceed together. The tell: "one resource, many writers" → lock. "one wall everyone waits at" → barrier.

acquire spins while TAS returns 1.

• T2 runs first: reads old value 0, sets flag to 1, returns 0 → 0 != 1, so T2 enters.
• T1: reads old value 1, returns 1 → spins.
• T3: reads old value 1, returns 1 → spins. Exactly one winner (T2). The returned values are [0, 1, 1] in the order (T2, T1, T3).

$W_{avg}=\frac{T_c}{2}=\frac{40}{2}=20\mu s.$

See Figure s01 below: the four queued threads wait $1T_c,2T_c,3T_c,4T_c$ (the bars), and the dashed line marks their mean. Sum $=(1+2+3+4)T_c=10T_c$. Average over 4 threads: $\bar{W}=\frac{10T_c}{4}=2.5T_c=\frac{N}{2}{T}_c=\frac{5}{2}\times 40=100\mu s.$ So the exact answer is $\frac{N}{2}{T}_c=100\mu s$. The parent's shorthand $\frac{(N-1)}{2}{T}_c=\frac{4}{2}\times 40=80\mu s$ is a slightly lower approximation — good to recognize the difference, but $100\mu s$ is correct for this discrete FIFO queue.

Spins per thread $=\frac{T_c}{t_{spin}}=\frac{40000ns}{50ns}=800$ iterations. $E_{waste}=800\cdot 4\cdot 2\text{nJ}=6400\text{nJ}=6.4\mu J.$ This growth with contention ($N-1$) is exactly why blocking locks exist: a sleeping thread burns ~0 energy. See Thread scheduling.

Without generation:

1. Phase 1: A, B, C all arrive, count hits 3, C resets count=0 and broadcasts on the CV.
2. A wakes, exits, races into phase 2, does count++ → count = 1.
3. B (from phase 1) was slow to wake; it re-checks the condition. But the condition ("has the barrier opened?") looks the same as a fresh phase-2 arrival — B and A's states are tangled. B may either slip through without all of phase-2 arriving, or get permanently stuck waiting for a count == 3 that already got reset. With generation:

• Each thread records my_gen = b->generation before waiting on the CV.
• The last thread does generation++, so old and new episodes have different numbers.
• A woken thread proceeds only when b->generation != my_gen — i.e. when its episode truly ended, not merely when the CV was signalled. This makes each barrier crossing logically distinct, killing the reuse race. Related idea: spurious wakeups in Memory consistency models require the same "loop and re-check a real condition" discipline.

Yes, on a weak model both can read 0: each core may reorder its own store after its load, so both loads see the old 0 before either store is visible. This is the classic "store buffering" outcome. The fix is a memory fence (a full barrier instruction) placed between the store and the load in each thread. It forces the store to become globally visible before the load executes, making r1 == 0 && r2 == 0 impossible. This is exactly the territory of Memory consistency models and is enforced under the hood by Cache coherence protocols.

typedef struct { int S; lock_t lock; cond_t cv; } sem_t;
 
void sem_init(sem_t *s, int val) {
    s->S = val; lock_init(&s->lock); cond_init(&s->cv);
}
 
void sem_wait(sem_t *s) {
    lock(&s->lock);
    while (s->S <= 0)          // LOOP, not if: guards spurious wakeups
        cond_wait(&s->cv, &s->lock);
    s->S--;                    // now safe to take a slot
    unlock(&s->lock);
}
 
void sem_signal(sem_t *s) {
    lock(&s->lock);
    s->S++;
    cond_signal(&s->cv);       // wake one waiter
    unlock(&s->lock);
}

Correctness:

• The lock gives mutual exclusion on S, so no lost updates on the counter.
• The while (not if) re-checks S > 0 after waking — essential against spurious wakeups AND against another thread grabbing the freed slot first.
• Setting val = 1 gives a plain mutex; larger val admits multiple threads (a resource pool of size $S$).

Deadlock interleaving:

1. T1 acquires A. 2. T2 acquires B. 3. T1 waits for B (held by T2). 4. T2 waits for A (held by T1). Circular wait → nobody proceeds. The universal fix: impose a global lock ordering — every thread must acquire locks in the same fixed order (say, always A before B). Then a cycle is impossible: no thread ever holds a "higher" lock while waiting for a "lower" one, so one of Coffman's four conditions (circular wait) is broken. See Deadlock and livelock.

A lock built on a plain bool fails because check-and-set is not ::: atomic (two separate steps let another thread interleave) The expected per-arrival spin wait for a hold of $T_c$ is ::: $T_c/2$ A barrier needs a generation counter to survive ::: reuse across back-to-back phases (the reuse race) The four-condition deadlock is broken by a global ::: lock ordering (prevents circular wait)