Synchronization primitives (locks, barriers): Question bank

Definition Symbols used on this page (defined once, up front)

Before any trap uses these, here is what each stands for — all measured on a single lock or barrier episode:

$N$ = the number of contending threads (for a barrier, the number of participants that must all arrive).
$T_{c}$ = the critical-section hold time: how long the winning thread keeps the lock before releasing.
$t_{s p in}$ = the time for one spin iteration (one Test-and-Set attempt that fails and loops).
$E_{in s t r u c t i o n}$ = the energy cost of executing one instruction (roughly, one spin attempt).
$W_{a v g}$ = expected wait for a thread arriving at a random moment behind one current holder.
$W_{q u e u e - a v g}$ = the mean wait averaged over all positions in an $N$ -deep FIFO queue.
$E_{w a s t e}$ = total energy burned by spinning threads while waiting.

Look at the picture of the three concepts this bank tests before you start — it names where each trap lives.

Figure — Synchronization primitives (locks, barriers)

The atomic read-modify-write, visually

True or false — justify

The simple flag lock (check lock == true, then set lock = true) guarantees mutual exclusion.

False — two threads can both read false in the gap between the check and the set (the red gap in the figure above), both pass the loop, and both write true. The check-and-set is not one indivisible step.

Test-and-Set (TAS) works because the compiler reorders the read and write together.

False — it works because the hardware makes the read-modify-write one atomic instruction, enforced by the cache coherence protocol, not because of any compiler trick.

An atomic Test-and-Set alone is enough to protect shared data across the critical section.

False — atomicity stops the acquire itself from racing, but without a memory fence the CPU may reorder the protected loads/stores outside the lock. You need acquire/release ordering too (see Memory consistency models).

A spinlock always wastes fewer CPU cycles than a blocking lock.

False — spinning is cheap only when the hold time is very short and cores are idle. On a single core or an oversubscribed system, spinning burns the very CPU the lock-holder needs to finish, making things worse.

Compare-and-Swap (CAS) can do everything Test-and-Set can, plus more.

True — CAS carries an expected value, so it can conditionally update based on the current state, enabling lock-free structures; TAS always blindly writes 1, so it can only build a plain lock.

A correct lock guarantees bounded waiting (no thread waits forever).

False — the TAS spinlock gives mutual exclusion and progress but not bounded waiting; an unlucky thread can lose every race and spin indefinitely. Fairness needs extra machinery like a ticket or queue.

Once the last thread in a barrier calls broadcast, resetting count = 0 is enough to make the barrier reusable.

False — a woken fast thread can loop into the next phase and increment count before a slow thread from the previous phase runs, tangling the two episodes. You need a generation counter to keep phases distinct.

A barrier and a lock solve the same problem.

False — a lock enforces mutual exclusion (one thread inside at a time); a barrier enforces rendezvous (all

N

threads must arrive before any leaves). Different goals entirely.

If a lock is released but no thread is waiting, the release is wasted work.

False — releasing simply sets the flag to free (or unparks nobody); it is cheap and necessary so the next acquirer succeeds. There is no waste, just no one to wake.

park() / unpark() blocking locks eliminate all busy-waiting.

Mostly true, but there is a small window where a thread decides to sleep just as unpark arrives (the lost-wakeup problem). The guard is to loop on a wake-up predicate — see the pattern below.

The lost-wakeup guard and barrier generations, in code

Definition Generation counter (how a reusable barrier is actually built)

A generation (or phase) is just an integer that counts how many times the barrier has fully opened. Each thread snapshots it before sleeping and only leaves when the snapshot no longer matches — proof that a whole new episode has begun, not a stray wakeup.

typedef struct {
    int   count;       // arrived in THIS generation
    int   threshold;   // = N, total participants
    int   generation;  // phase counter, starts at 0
    lock_t lock; cond_t cv;
} barrier_t;
 
void barrier_init(barrier_t *b, int n){
    b->count = 0; b->threshold = n; b->generation = 0;
    lock_init(&b->lock); cond_init(&b->cv);
}
 
void barrier_wait(barrier_t *b){
    lock(&b->lock);
    int my_gen = b->generation;      // snapshot MY episode
    if (++b->count == b->threshold){ // I am the last to arrive
        b->generation++;             // open a NEW episode
        b->count = 0;                // reset for reuse
        broadcast(&b->cv);
    } else {
        // loop on a PREDICATE, not a bare wait -> guards lost/spurious wakeups
        while (my_gen == b->generation)
            wait(&b->cv, &b->lock);
    }
    unlock(&b->lock);
}

The while (my_gen == b->generation) loop is the same shape as the lost-wakeup guard for park: always re-test a condition after waking, never trust the wakeup itself.

Spot the error

acquire(&mutex);
if (error) return;        // <-- what's wrong?
shared_counter++;
release(&mutex);

Find the bug.

The early return skips release, so the lock is held forever → deadlock. Every error path inside a critical section must release the lock first.

void acquire(lock_t *l){ while(l->flag==1){} l->flag=1; }

Why is this broken even though it "checks then sets"?

The check and the set are two separate operations; a second thread can slip into the gap. It must be a single atomic Test-and-Set / CAS, not two plain memory accesses.

if (b->count == b->threshold) { broadcast(&b->cv); }
else { wait(&b->cv, &b->lock); }   // no loop

What's the danger of wait without a surrounding loop?

A spurious wakeup (or a stale broadcast from a previous generation) can wake the thread while the condition is still false. Without a while loop re-checking the generation, the thread proceeds too early.

barrier_t b;
b.count = 0; b.threshold = 4;   // then straight to barrier_wait

What was forgotten?

The internal lock and condition variable were never initialized (lock_init / cond_init), and generation wasn't set to 0. Using an uninitialized lock is undefined behaviour.

// mutex with NO ownership tracking:
release(lock_t *l){ l->flag = 0; }   // any thread may call this

Thread B calls release on a lock held by thread A. What breaks, and how do real mutexes stop it?

Setting flag = 0 frees the lock while A is still inside its critical section, so a third thread can enter — mutual exclusion is silently broken. Real mutexes store an owner id and reject a release (or double-release) from a non-owner, turning this into an error instead of corruption.

Is E_waste = (T_c / t_spin) · (N−1) · E_instruction an error?

No — it is a correct estimate. Count the spins: a lock held for

T_{c}

with each spin costing

t_{s p in}

gives

T_{c} / t_{s p in}

spins per waiter, times

(N - 1)

waiters, times

E_{in s t r u c t i o n}

per spin. It is here to show energy waste grows with contention

(N - 1)

, which is the real reason to prefer blocking locks.

Why questions

Why must Test-and-Set return the old value rather than just set the flag?

The old value is how a thread knows whether it was the one that acquired the lock (old was 0) or arrived too late (old was 1). Without the return value there's no way to distinguish winner from loser atomically.

Why does the barrier need to remember my_gen = b->generation before waiting?

So the waiter can tell "the barrier actually advanced to my next phase" apart from "someone signalled the CV." It only proceeds when generation truly changes, not merely when woken.

Why does cache coherence matter for atomic instructions?

The atomic read-modify-write must appear indivisible across cores; the coherence protocol gives one core exclusive ownership of the cache line for the duration, so no other core can observe or alter the value mid-operation.

Why do we need a fence and an atomic instruction — isn't atomicity enough?

Atomicity makes the acquire indivisible, but says nothing about ordering of the surrounding loads/stores. A fence stops the compiler/CPU from moving protected accesses outside the lock (see Memory consistency models).

Why is

W_{a v g} = T_{c} /2

(per arrival) different from

W_{q u e u e - a v g} = (N - 1) T_{c} /2

W_{a v g}

is the expected wait behind one current holder for a randomly-timed arrival (on average, halfway through its hold).

W_{q u e u e - a v g}

averages the wait across all

N

FIFO queue positions, where later positions wait for every critical section ahead of them.

Why can spinning ever be better than blocking?

If the lock is held for less time than a context switch costs, spinning briefly avoids the expensive sleep/wake round-trip. This is exactly why some systems use adaptive/spin-then-block locks.

Why does forgetting to advance generation (only resetting count) still sometimes "work" in testing?

Under low contention threads rarely loop back fast enough to trigger the reuse race, so the bug hides. It surfaces only when a fast thread reaches the next barrier before a slow thread from the previous one — timing that stress tests expose but casual runs miss.

Edge cases

What does a barrier with threshold = 1 do?

The single thread arrives, immediately hits count == threshold, advances the generation, and passes straight through — a no-op barrier, which is correct behaviour.

What does a barrier with threshold = 0 do?

No thread can ever make count equal 0 by incrementing (the first arrival sets count = 1 > 0), so with the == test the barrier never fires and any arrival hangs — a degenerate input that a robust barrier_init should reject (or treat as "fires immediately, letting everyone through").

What happens if you release a lock that was never acquired?

The flag is forced to 0 (free), so a thread currently inside the critical section is no longer protected — another thread can now enter. This silently breaks mutual exclusion unless the mutex tracks ownership.

Two threads call acquire at the exact same instant on two cores. Who wins?

The coherence protocol serializes the two atomic operations onto the cache line, so exactly one TAS reads the old 0 and the other reads 1. Ties are impossible at the hardware level.

Zero threads ever call barrier_wait. What state is the barrier in?

It stays at count = 0, generation = 0, waiting forever — harmless. The barrier only "fires" when the

N

-th thread arrives; with no arrivals nothing blocks and nothing leaks.

A thread calls barrier_wait for a phase, but one of the

N

threads crashed and never arrives.

The barrier never reaches threshold, so every arrived thread waits forever → a permanent stall. Barriers assume all

N

participants are alive; missing participants cause a hang (a liveness failure, see Deadlock and livelock).

Recall Self-check before moving on

One-line trap I still can't justify ::: Re-read that item's answer and trace it against the code in the parent note, then re-test yourself in an hour.