Mutexes, Condition Variables, Deadlocks & Happens-Before

Overview

Every production service that shares mutable state across threads — or across Node worker_threads / browser SharedArrayBuffer — hits the same questions: who may mutate this, when is my write visible to another core, and why is this process stuck with every thread blocked?

Mutexes and condition variables are the classical answers. Happens-before is the precise language that makes those answers correct under modern memory models (JMM, C++11, Rust Send/Sync). Interviewers still probe Dining Philosophers, Mesa vs Hoare, and lock ordering because they separate engineers who can ship concurrent code from those who only memorize synchronized.

After this lesson you should be able to:

• Say what a mutex buys you besides mutual exclusion (visibility / happens-before, a place to hang invariants).
• Write a Mesa-style CV wait loop and explain lost wakeups.
• Name the Coffman conditions and break circular wait with a global lock order.
• Contrast deadlock, livelock, and starvation.
• Explain why volatile / atomics are not compound atomicity, and when locks beat lock-free.

1. 1

   shared fields → lost wakeup / deadlock

   Scatter locks and if-wait

   Callbacks re-enter. Philosophers pick left then right. Waiters sleep on a predicate that already became true. This is the bug class the hub exists to kill.

2. 2

   critical section → unlock ≺ next lock

   Winner: one owned mutex, Mesa while, lock order

   Own shared state in one module. Wait in while (!pred). Acquire locks in a global order (prevention). RWLock only when reads dominate (mutex vs RWLock).

3. ?

   Visibility, then atomics if the profile says so

   Mutex unlock is a happens-before edge (visibility). Mesa notify is a hint (Mesa vs Hoare). Atomics for single-word counters after you can defend the memory order (atomics vs locks).

Mutex / lock — mutual exclusion

A mutex (mutual exclusion lock) guarantees that at most one thread holds the lock at a time. Critical sections protected by the same mutex appear to execute atomically with respect to each other.

What a mutex actually buys you:

1. Mutual exclusion — only one holder.
2. Memory visibility / happens-before — unlock synchronizes-with a later lock on the same mutex (JMM §17.4.5; C++11 [intro.multithread]). Everything the previous holder wrote before unlock becomes visible to the next acquirer.
3. A place to hang invariants — "while holding mu, queue.length == buffered_count."

Non-reentrant vs reentrant

Reentrancy hides design smells (lock held across callbacks). Prefer the simplest lock that fits.

RWLock (readers–writer)

Many concurrent readers or one exclusive writer. Great when reads dominate and the critical section is non-trivial.

Pitfalls:

• Writer starvation — endless readers never let a writer in.
• Upgrade deadlock — promoting read → write while still holding the read lock.
• Overhead — for tiny critical sections a plain mutex is often faster.

Full comparison (reader-count ping-pong, writer starvation, upgrade deadlock): mutex vs RWLock.

Architecture note — shared mutable state boundaries

Prefer message passing / ownership transfer (channels, actor mailboxes) at service boundaries. Use mutexes inside a carefully owned component when shared mutable state is unavoidable. Thread-pool workers should share one owned module that holds the mutex (or a channel/queue), not scatter locks across call sites.

Condition variables — wait / notify / notifyAll

A condition variable (CV) lets a thread sleep until another thread signals that a predicate may have become true. A CV is always paired with a mutex:

1. Lock the mutex.
2. while (!predicate): cv.wait() — atomically releases the mutex and blocks; on wakeup, re-acquires the mutex before returning.
3. Do work under the lock.
4. Unlock (or use with / RAII).

Why the mutex is mandatory: without atomic unlock+sleep, a producer can set the predicate and notify between your check and your sleep — you sleep forever (lost wakeup).

notify vs notifyAll

Spurious wakeups and Mesa semantics

Real systems (pthread_cond_wait, Java Condition.await, Rust Condvar::wait, C++ condition_variable::wait) may return without a corresponding notify. That is a spurious wakeup. Additionally, almost all production monitors use Mesa semantics (signal-and-continue), not Hoare:

Rule that never changes:

while (!predicate):
    cv.wait(lock)

Never if (!predicate): wait(...). Why Mesa (pthreads, Java, C++) forbids Hoare's if: condition variables, Mesa vs Hoare.

Press Run. Snippets must be self-contained — no network, files, or native modules.

Producer–consumer with a CV

The producer holds the mutex, pushes, notifies "not empty," then unlocks. The consumer re-checks while the queue is empty, pops, notifies "not full."

flowchart TB
  p["Producer"]
  m["Mutex"]
  q["Bounded Queue"]
  c["Consumer"]
  p -->|lock()| m
  p -->|push(item)| q
  p -->|unlock()| m
  c -->|lock()| m
  c -->|pop()| q
  c -->|unlock()| m

Deadlock, livelock, starvation

Coffman conditions (all four required)

1. Mutual exclusion — resources are non-shareable.
2. Hold and wait — hold one resource while waiting for another.
3. No preemption — resources cannot be forcibly taken.
4. Circular wait — a cycle in the wait-for graph.

Break any one and deadlock is impossible. In practice we almost always break circular wait via global lock ordering. Prevention vs avoidance vs detection, try-lock backoff, and actor redesign: deadlock prevention & avoidance.

Deadlock wait-for graph

Classic cycle: A holds L1 wants L2; B holds L2 wants L1.

Lock ordering

Assign every lock a total order (by address, by name, by hierarchy: dbConn < cache < metrics). Always acquire in ascending order. For N locks whose set is dynamic, sort the lock identities then acquire (David Beazley's dining-philosophers pattern).

Press Run. Snippets must be self-contained — no network, files, or native modules.

Livelock vs starvation

Dining Philosophers

Five philosophers, five forks; each needs left + right. Naive "pick left then right" → circular wait.

Fixes:

• Asymmetric ordering — last philosopher picks right first (breaks the cycle).
• Arbitrator — a waiter / butler hands out forks.
• Take-both-or-none under a monitor (or the sorted acquire_ordered pattern above).

Happens-before and memory visibility

Happens-before (hb) is a partial order. If action A happens-before action B, then A's effects are visible to B and A is ordered before B. It is not "earlier on a wall clock." Edges, data races, and why wall-clock order is not visibility: happens-before & memory visibility. When a single-word CAS beats a lock — and when it does not: atomics vs locks.

Key edges (JMM / C++11-style):

• Program order within a thread.
• Unlock → later lock on the same monitor/mutex.
• Volatile / atomic write → later read of the same variable (with the appropriate memory order).
• Thread start / join edges.
• Transitivity.

Without an hb edge, the compiler and CPU may reorder, and another thread may see stale or torn views.

volatile vs atomic vs locks

When locks beat lock-free

• Multi-field invariants (balance + ledger published together).
• Blocking waits for a condition (CV + mutex is clearer than spinning CAS).
• Contended updates where a short critical section + OS futex sleep beats CAS livelock.
• Clarity — lock-free is for measured hot paths, not default style.

Lock-free is a progress guarantee, not "we used atomics."

Python examples

Pyodide can run threads sometimes, but the sandboxes above stay in-process: predicate re-check and lock-id sort. The full buffer below is the production shape — Mesa while, notify_all, RAII with.

Bounded buffer (Mesa Condition)

threading.Condition owns an RLock by default (reentrant if helpers re-enter). Always re-check the predicate after wait().

"""Producer-consumer with Mesa-style Condition (always wait in a while loop)."""
from __future__ import annotations

import threading
import time
from collections import deque
from typing import Deque


class BoundedBuffer:
    def __init__(self, capacity: int) -> None:
        self._capacity = capacity
        self._q: Deque[str] = deque()
        self._cv = threading.Condition()

    def put(self, item: str) -> None:
        with self._cv:
            while len(self._q) >= self._capacity:
                self._cv.wait()  # atomically releases lock, sleeps, reacquires
            self._q.append(item)
            self._cv.notify_all()  # waiters blocked on "not empty"

    def get(self) -> str:
        with self._cv:
            while not self._q:
                self._cv.wait()
            item = self._q.popleft()
            self._cv.notify_all()  # waiters blocked on "not full"
            return item


def demo_buffer() -> None:
    buf = BoundedBuffer(2)

    def producer() -> None:
        for i in range(5):
            buf.put(f"msg-{i}")
            print("produced", i)

    def consumer() -> None:
        for _ in range(5):
            print("consumed", buf.get())
            time.sleep(0.01)

    threads = [
        threading.Thread(target=producer),
        threading.Thread(target=consumer),
    ]
    for t in threads:
        t.start()
    for t in threads:
        t.join()

Deadlock via lock-order inversion, and the fix

Naive "left then right" around a circle inverts order. Sort by id so every thread agrees.

"""Dining-philosophers style deadlock vs ordered acquire."""
import threading
from contextlib import contextmanager
from typing import Iterator, List


def bad_philosopher(left: threading.Lock, right: threading.Lock) -> None:
    # Classic inversion: each grabs left then right around a circle.
    with left:
        with right:
            pass  # "eating"


@contextmanager
def acquire_ordered(*locks: threading.Lock) -> Iterator[None]:
    ordered: List[threading.Lock] = sorted(locks, key=id)
    for lk in ordered:
        lk.acquire()
    try:
        yield
    finally:
        for lk in reversed(ordered):
            lk.release()


def good_philosopher(left: threading.Lock, right: threading.Lock) -> None:
    with acquire_ordered(left, right):
        pass  # eating under consistent lock order

Happens-before via unlock/lock (visibility)

Without sync, readers may see a torn / stale view of multi-field state. Publish both fields under one critical section; unlock happens-before the next lock, so the reader sees both or neither.

"""Without sync, readers may see a torn / stale view of multi-field state."""
import threading


class Config:
    def __init__(self) -> None:
        self._mu = threading.Lock()
        self.host = ""
        self.port = 0

    def publish(self, host: str, port: int) -> None:
        with self._mu:
            self.host = host
            self.port = port

    def snapshot(self) -> tuple[str, int]:
        with self._mu:
            return self.host, self.port

TypeScript examples

Node's main thread is single-threaded. The patterns below teach the same Mesa mutex/CV rules using cooperative async locks (event-loop safe). For true OS threads, use worker_threads with Atomics / SharedArrayBuffer, or a native addon.

Async mutex + condition (Mesa teaching form)

Handoff on unlock so a waiter is granted the lock without racing locked = false. wait enqueues, unlocks, then re-locks on wake. The buffer always uses while.

/** Cooperative async mutex — one critical section at a time on the event loop. */
class Mutex {
  private locked = false;
  private waiters: Array<() => void> = [];

  async lock(): Promise<void> {
    if (!this.locked) {
      this.locked = true;
      return;
    }
    await new Promise<void>((resolve) => this.waiters.push(resolve));
    this.locked = true;
  }

  unlock(): void {
    const next = this.waiters.shift();
    if (next) next();
    else this.locked = false;
  }
}

/** Condition variable analog: wait releases the mutex; notify is only a hint. */
class Condition {
  constructor(private mu: Mutex) {}
  private waiters: Array<() => void> = [];

  async wait(): Promise<void> {
    await new Promise<void>((resolve) => {
      this.waiters.push(resolve);
      this.mu.unlock();
    });
    await this.mu.lock();
  }

  notify(): void {
    this.waiters.shift()?.();
  }

  notifyAll(): void {
    for (const w of this.waiters.splice(0, this.waiters.length)) w();
  }
}

/** Bounded buffer — always while (!pred) await cv.wait() (Mesa + spurious). */
class Buffer<T> {
  private q: T[] = [];
  private mu = new Mutex();
  private cv = new Condition(this.mu);
  constructor(private cap: number) {}

  async put(x: T): Promise<void> {
    await this.mu.lock();
    try {
      while (this.q.length >= this.cap) {
        await this.cv.wait();
      }
      this.q.push(x);
      this.cv.notifyAll();
    } finally {
      this.mu.unlock();
    }
  }

  async take(): Promise<T> {
    await this.mu.lock();
    try {
      while (this.q.length === 0) {
        await this.cv.wait();
      }
      const v = this.q.shift() as T;
      this.cv.notifyAll();
      return v;
    } finally {
      this.mu.unlock();
    }
  }
}

async function demo(): Promise<void> {
  const buf = new Buffer<string>(2);
  const producer = (async () => {
    for (let i = 0; i < 5; i++) {
      await buf.put(`msg-${i}`);
      console.log("produced", i);
    }
  })();
  const consumer = (async () => {
    for (let i = 0; i < 5; i++) {
      console.log("consumed", await buf.take());
    }
  })();
  await Promise.all([producer, consumer]);
}

Lock ordering in TypeScript

/** Acquire multiple async mutexes in a stable global order (by id). */
let nextId = 1;

class OrderedMutex extends Mutex {
  readonly id = nextId++;
}

async function withOrdered(
  locks: OrderedMutex[],
  fn: () => Promise<void>
): Promise<void> {
  const ordered = [...locks].sort((a, b) => a.id - b.id);
  for (const lk of ordered) await lk.lock();
  try {
    await fn();
  } finally {
    for (const lk of [...ordered].reverse()) lk.unlock();
  }
}

True shared-memory mutex sketch (Atomics + SharedArrayBuffer)

Educational spin-then-wait. Prefer battle-tested libs in production.

/**
 * Cross-worker mutual exclusion on SharedArrayBuffer.
 * Educational spin-then-wait; prefer battle-tested libs in production.
 */
function lockSab(i32: Int32Array, idx: number): void {
  for (;;) {
    // CAS free(0) -> held(1)
    if (Atomics.compareExchange(i32, idx, 0, 1) === 0) return;
    Atomics.wait(i32, idx, 1); // sleep while value stays 1
  }
}

function unlockSab(i32: Int32Array, idx: number): void {
  Atomics.store(i32, idx, 0);
  Atomics.notify(i32, idx, 1);
}

// const sab = new SharedArrayBuffer(4);
// const i32 = new Int32Array(sab);
// lockSab(i32, 0); try { /* critical */ } finally { unlockSab(i32, 0); }

Architecture patterns

1. Own shared state in one module — export methods that take the lock internally; never expose the raw mutex.
2. Thread pools — workers pull tasks from a blocking queue (CV or channel); do not spawn unbounded threads per request.
3. Lock ranking / hierarchy — document acquire order in code review checklists.
4. Prefer immutability + channels across process/service boundaries; mutexes inside.
5. Timeouts on lock acquisition where the platform allows — fail fast into remediation rather than silent deadlock.

Interview Q&A

Pitfalls

1. Waiting with if instead of while.
2. Forgetting to hold the mutex when calling wait/notify (undefined / race).
3. Lock-order inversion across code paths (library A then B vs B then A).
4. Holding locks across I/O or slow RPCs → convoys and cascading latency.
5. Using volatile / atomics for multi-field invariants.
6. Nested lock acquisition without reentrancy when callbacks re-enter.
7. RWLock upgrade deadlock (read → write without releasing).
8. Assuming wall-clock order implies visibility (no happens-before).
9. Spawning unbounded threads instead of a bounded pool + queue.
10. Ignoring cancellation/interrupt — wait forever on a CV after shutdown.

Go Deeper

Docs / specs:

• Java Language Spec — Threads and Locks (happens-before)
• JSR-133 FAQ (Pugh)
• Python threading (Lock / Condition)
• C++ std::condition_variable
• Rust std::sync::Mutex
• Rust std::sync::Condvar
• Mesa monitors paper (Lampson & Redell)
• Java Condition API (spurious wakeups)
• Oracle JLS threads (JDK 26 draft)

Articles / talks:

• Real Python — thread locks
• Herb Sutter — search "atomic Weapons" / lock-free
• CppCon 2014: Herb Sutter — Lock-Free Programming (or, Juggling Razor Blades) (search the title; video IDs rotate)
• University/conference deep dives on the Java Memory Model referencing JSR-133

One-page cheat sheet

• Lock = exclusion + happens-before on unlock→lock.
• CV wait = unlock+sleep+relock; always while (!pred).
• Mesa ⇒ notify is a hint.
• Deadlock ⇒ break circular wait (order locks).
• volatile/atomics ≠ multi-field atomicity.
• Prefer channels at boundaries; mutexes inside owned modules.
• Measure before lock-free; clarity wins until profiles say otherwise.

Cluster: mutex vs RWLock · Mesa vs Hoare · deadlock · happens-before · atomics