Synchronization primitives (locks, barriers)

The fundamental problem: Race conditions

When multiple threads execute concurrently, their operations can interleave in unpredictable ways. Consider this simple increment:

// Thread 1 and Thread 2 both execute:
counter = counter + 1;

At the hardware level, this becomes:

LOAD counter from memory to register
ADD 1 to register
STORE register back to memory

If both threads execute simultaneously, we might see:

Thread 1 LOAD (reads 0)
Thread 2 LOAD (reads 0)
Thread 1 ADD (computes 1)
Thread 2 ADD (computes 1)
Thread 1 STORE (writes 1)
Thread 2 STORE (writes 1)

Result: counter = 1, not 2! This is the lost update problem.

Figure — Synchronization primitives (locks, barriers)

Locks (Mutual Exclusion)

Derivation: Building a lock from first principles

Requirements for a correct lock:

Mutual exclusion: Only one thread in critical section
Progress: If no thread holds the lock, a waiting thread must eventually acquire it
Bounded waiting: A thread waiting to acquire shouldn't wait forever (fairness)

Attempt 1: Simple flag (BROKEN)

bool lock = false;
 
acquire() {
    while (lock == true) { /* spin */ }
    lock = true;
}
 
release() {
    lock = false;
}

Why this fails: Two threads can both see lock == false, both pass the while loop, and both set lock = true. No mutual exclusion!

Attempt 2: Test-and-Set (Hardware atomic instruction)

Modern CPUs provide atomic read-modify-write instructions. Test-and-Set (TAS):

// Hardware provides this as ONE atomic instruction
int TestAndSet(int *ptr) {
    int old = *ptr;
    *ptr = 1;
    return old;
}

Why atomic? The CPU's cache coherence protocol ensures no other core can access this memory location during the TAS operation.

Now our lock:

typedef struct {
    int flag;  // 0 = free, 1 = held
} lock_t;
 
void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) {
        // Spin: keep trying
    }
}
 
void release(lock_t *lock) {
    lock->flag = 0;
}

Derivation of correctness:

Mutual exclusion: TAS returns 0 (old value) to exactly ONE thread when flag was 0. All others get 1 and spin.
Progress: When release() sets flag=0, next TAS will succeed.
Bounded waiting: Not guaranteed—a thread could spin forever if unlucky.

Formula Spin lock overhead

If $N$ threads contend for a lock held for time $T_c$ , average wait time per waiting thread: $W_{avg} = \frac{T_c}{2}$ Why? A waiting thread arrives at some random point during the current holder's critical section. On average it must wait for half of the remaining critical-section time, i.e. $T_c/2$ (assuming uniform random arrival within the hold interval). Total wait summed over all contenders: With $(N-1)$ threads queued behind the holder, and each having to wait for all the critical sections ahead of it complete in FIFO order, the last thread waits $\approx (N-1)\cdot T_c$ . So the average across the queue positions is: $W_{queue-avg} = \frac{(N-1)\cdot T_c}{2}$ Note these are two different quantities: $W_{avg}=T_c/2$ is per-arrival expected wait behind one holder; $W_{queue-avg}$ is the mean over an $N$ -deep FIFO queue. Energy cost: Spinning wastes CPU cycles. If each spin iteration takes $t_{spin}$ and lock is held for $T_c$ : $E_{waste} = \frac{T_c}{t_{spin}} \cdot (N-1) \cdot E_{instruction}$ This growth with contention motivates blocking locks.

Attempt 3: Compare-and-Swap (CAS) - More general

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

CAS is more powerful—can implement lock-free data structures. Lock implementation identical to TAS in behavior.

Blocking locks: Don't waste CPU

Spin locks are wasteful on single-core or oversubscribed systems. Solution: yield the CPU when lock unavailable.

void acquire(lock_t *lock) {
    while (TestAndSet(&lock->flag) == 1) {
        yield();  // OS call: give CPU to another thread
    }
}

Even better: Use a wait queue. When lock unavailable, thread calls park() (sleeps), and the releasing thread calls unpark() on a waiting thread.

Worked example Lock usage pattern

lock_t mutex;
int shared_counter = 0;
// Thread function
void increment() {
    acquire(&mutex);
    // Critical section
    shared_counter = shared_counter + 1;
    release(&mutex);
}

Why this step?

acquire: Ensures we're the ONLY thread modifying shared_counter
Critical section: The dangerous code that accesses shared state
release: Let other threads proceed

Common mistake: Forgetting release in error paths → deadlock!

Barriers (Synchronization points)

Derivation: Building a barrier

Requirements:

All $N$ threads must reach the barrier
No thread proceeds until all have arrived
Reusable for multiple phases (must survive back-to-back barriers safely)

Naive barrier (BROKEN for reuse)

// DANGER: resetting count and using one CV is not enough
void barrier_wait(barrier_t *b) {
    lock(&b->lock);
    b->count++;
    if (b->count == b->threshold) {
        b->count = 0;          // reset
        broadcast(&b->cv);
    } else {
        wait(&b->cv, &b->lock); // wait for others
    }
    unlock(&b->lock);
}

Common mistake Why "reset count = 0" alone breaks barrier reuse

The intuition: "The last thread resets the counter and wakes everyone, so it's ready for next time." Feels complete. The reality: A fast thread that was just woken can loop around and call barrier_wait again for the next phase before some slow thread from the previous phase has even been scheduled to run. The fast thread increments count, and now the slow thread's wakeup and the new phase's count are tangled — some threads get stuck, or a thread slips through the barrier without everyone arriving. This is the classic barrier reuse race. The fix: Add a generation (phase) counter. Each thread records the current generation before waiting, and only proceeds when the generation actually advances — not merely when the CV is signalled. This makes each barrier episode logically distinct.

Correct reusable barrier (with generation counter)

typedef struct {
    int count;          // How many have arrived in THIS generation
    int threshold;      // Total number of threads (N)
    int generation;     // Phase / episode counter
    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);   // MUST initialize the internal lock
    cond_init(&b->cv);     // MUST initialize the condition variable
}
 
void barrier_wait(barrier_t *b) {
    lock(&b->lock);
    int my_gen = b->generation;   // remember which episode I belong to
 
    b->count++;
    if (b->count == b->threshold) {
        // Last thread in: open the barrier and start a NEW generation
        b->generation++;   // advance phase -> distinguishes old vs new
        b->count = 0;      // reset for next use
        broadcast(&b->cv);
    } else {
        // Wait until the generation actually changes.
        // Looping guards against spurious wakeups AND the reuse race.
        while (my_gen == b->generation) {
            wait(&b->cv, &b->lock);
        }
    }
    unlock(&b->lock);
}

Why this works:

Lock protects count/generation: Atomic increment and comparison.
Generation counter: A newly-woken fast thread that re-enters for the next phase sees a different my_gen, so it cannot accidentally satisfy or interfere with the previous episode's wait.
while loop (not if): A thread only leaves when generation truly advanced, so spurious wakeups and reuse races are both handled.
Init function: lock_init and cond_init are required — an uninitialized mutex/CV is undefined behavior.

Barrier types

Blocking barrier: Threads sleep (above example)
Spinning barrier: Threads spin-wait (useful for very short phases)
Tree barrier: Hierarchical wake-up for $N \gg 1$ (reduces $t_{notify}$ from $O(N)$ to $O(\log N)$ )

Worked example Barrier in matrix computation

double A[N][N], B[N][N];
barrier_t sync;
 
void compute_phase() {
    int tid = get_thread_id();
    // Phase 1: Compute on A, write to B
    for (int i = tid * CHUNK; i < (tid+1) * CHUNK; i++) {
        for (int j = 0; j < N; j++) {
            B[i][j] = some_function(A[i][j]);
        }
    }
    
    barrier_wait(&sync);  // ALL threads must finish Phase 1
    
    // Phase 2: Now safe to read B, write to A
    for (int i = tid * CHUNK; i < (tid+1) * CHUNK; i++) {
        for (int j = 0; j < N; j++) {
            A[i][j] = another_function(B[i][j]);
        }
    }
}

Why barrier here? Phase 2 reads from B, which Phase 1 writes. Without barrier, Thread 1 might start Phase 2 while Thread 2 is still in Phase 1, reading old/partial B values. And because the SAME barrier object is reused across many iterations of an outer loop, the generation counter is essential.

Hardware support for synchronization

Modern CPUs provide:

Atomic instructions: TAS, CAS, Fetch-and-Add, Load-Linked/Store-Conditional
Memory barriers: Enforce ordering of loads/stores across cores
Cache coherence: Keeps lock variables consistent (MESI protocol)

Common mistake Forgetting memory ordering

The trap: On modern CPUs, stores can be reordered. Without memory barriers, another thread might observe:

data = 42;      // Store 1
flag = true;    // Store 2 (release lock)

as flag=true but data still uninitialized!

The fix: Release operations include a store barrier (ensures all prior stores complete first). Acquire operations include a load barrier (ensures subsequent loads see all prior stores).

Advanced: Lock-free algorithms

Can we avoid locks entirely using only atomic CAS?

void lock_free_increment(int *counter) {
    int old, new;
    do {
        old = *counter;
        new = old + 1;
    } while (CompareAndSwap(counter, old, new) != old);
}

How it works:

Read current value
Compute new value
CAS: if *counter still equals old, update to new
If CAS fails (another thread changed it), retry

Advantage: No blocking, always progress
Disadvantage: High contention → many retries → wasted work

Recall Explain to a 12-year-old

Imagine a bathroom with one toilet. If there's no lock, two people could walk in at the same time—awkward! A lock is like a simple system: "If the door is unlocked, I lock it and go in. When I'm done, I unlock it." The Test-and-Set is like a magic door handle that, in one instant, both checks if it's unlocked AND locks it if it is. No one can sneak in between those two actions.

A barrier is like a field trip where the teacher says, "We all meet at the bus at 3pm—nobody gets on until everyone's here." If you arrive early, you wait. Once the last person shows up, the teacher yells "All aboard!" and everyone gets on together. And to run the trip again the next day, the teacher keeps a "Day number" so a fast kid who already got off doesn't accidentally get counted for today's roll call.

Connections

Cache coherence protocols – MESI ensures lock variables stay consistent across cores
Memory consistency models – Define legal orderings of loads/stores; synchronization enforces order
Thread scheduling – Blocking locks require OS scheduler to park/unpark threads
Deadlock and livelock – Incorrect lock ordering causes deadlock; lock-free algorithms can livelock
Parallel algorithms – Barriers enable bulk-synchronous parallel (BSP) model
Atomic operations – Hardware primitives that make lock implementation possible

#flashcards/hardware

What is a race condition?

When multiple threads access shared data concurrently and the result depends on the unpredictable interleaving of their operations, leading to incorrect results.

What three guarantees must a correct lock provide?

1) Mutual exclusion (only one thread in critical section), 2) Progress (if lock free, a waiting thread eventually acquires it), 3) Bounded waiting (no thread waits forever).

Why does a simple flag (check-then-set) fail as a lock?

The check and set are separate operations. Two threads can both see "free", both pass the check, and both set the flag, violating mutual exclusion. Need atomic read-modify-write.

What does Test-and-Set (TAS) do atomically?

Reads the old value of a memory location, sets it to 1, and returns the old value—all as one indivisible hardware operation.

What is a spin lock and when is it wasteful?

A lock where threads repeatedly check (spin) in a loop until the lock is free. Wasteful when the wait time is long, or on single-core systems where the spinning thread prevents the lock holder from running.

For a spin lock, what is the expected wait for a thread arriving behind ONE holder, assuming uniform arrival?

About T_c/2 — half the critical-section hold time. (The (N-1)·T_c/2 figure is instead the average over an N-deep FIFO queue.)

What is a barrier in parallel programming?

A synchronization point where N threads must all arrive before any can proceed, ensuring phase completion before moving to the next phase.

What is the key difference between a lock and a barrier?

Lock ensures mutual exclusion (one thread at a time in critical section). Barrier ensures all threads reach a synchronization point before any proceed (ordering/phasing).

Why must a reusable barrier use a generation/phase counter?

Without it, a fast thread woken from one barrier can loop into the next phase and increment count before a slow thread from the previous phase runs, tangling the two episodes and breaking correctness. The generation counter makes each barrier episode distinct and lets waiters loop until the generation actually advances.

Why must barrier_init call lock_init and cond_init?

Using an uninitialized mutex or condition variable is undefined behavior; the internal synchronization objects must be initialized before the barrier is used.

What is Compare-and-Swap (CAS)?

An atomic instruction that compares a memory location to an expected value and, if they match, updates it to a new value. Returns the actual value found, allowing retry loops for lock-free algorithms.

What advantage do lock-free algorithms have over locks?

They guarantee system-wide progress even if individual threads are delayed or preempted, avoiding deadlock and priority inversion. However, they can suffer from high retry overhead under contention.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, jab do ya zyada threads ek saath ek hi shared resource ko access karte hain — jaise bank account balance ya ek simple counter — tab ek badi problem aa sakti hai jise hum race condition kehte hain. Socho, do log ek hi account mein paise add kar rahe hain: dono $100 padhte hain, apna apna amount add karte hain, aur waapas likhte hain. Result galat aata hai kyunki dono ke operations beech mein interleave ho gaye. Yeh isliye hota hai kyunki ek simple counter = counter + 1 bhi hardware level pe teen steps mein tootta hai — LOAD, ADD, STORE — aur inke beech mein doosra thread ghus sakta hai. Isko lost update problem kehte hain.

Isko solve karne ke liye humein synchronization primitives chahiye, jaise locks (mutex). Lock ka simple idea yeh hai ki critical section mein ek time pe sirf ek hi thread jaaye — baaki wait karein. Lekin yahan ek trap hai: agar aap sirf ek bool flag se check-then-set karoge, toh woh kaam nahi karega, kyunki check aur set ke beech mein doosra thread ghus jaata hai. Isiliye modern CPUs atomic instructions dete hain jaise Test-and-Set (TAS) — yeh check aur set dono ko ek hi indivisible step mein karta hai, aur cache coherence protocol ensure karta hai ki us waqt koi aur core us memory location ko chhu na sake. Isse mutual exclusion guarantee ho jaata hai.

Yeh concept isliye important hai kyunki aaj kal har processor multicore hai, aur real-world software mein multiple threads har jagah parallel chalte hain. Bina proper synchronization ke aapka program kabhi kabhi sahi answer dega aur kabhi galat — aur yeh bugs debug karna bahut mushkil hote hain kyunki woh randomly aate hain. Ek cheez yaad rakhna: spin locks mein overhead hota hai — agar bahut saare threads ek lock ke liye ladh rahe hain, toh average wait time badhta hai (roughly $T_c/2$ per thread). Isliye locks powerful hain, par inhe soch-samajh ke use karna padta hai taaki performance na girey.

Synchronization primitives (locks, barriers)

The fundamental problem: Race conditions

Locks (Mutual Exclusion)

Derivation: Building a lock from first principles

Attempt 1: Simple flag (BROKEN)

Attempt 2: Test-and-Set (Hardware atomic instruction)

Attempt 3: Compare-and-Swap (CAS) - More general

Blocking locks: Don't waste CPU

Barriers (Synchronization points)

Derivation: Building a barrier

Naive barrier (BROKEN for reuse)

Correct reusable barrier (with generation counter)

Barrier types

Hardware support for synchronization

Advanced: Lock-free algorithms

Connections

Concept Map

Hinglish (regional understanding)

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Parallelism & Multicore

Connections