vault

Mutex vs Semaphore vs Condition Variable

23 min read

Mutex vs Semaphore vs Condition Variable

Three primitives form the alphabet of classical concurrency: a mutex (mutual exclusion lock) protects a critical section so only one thread enters at a time; a semaphore is a counting gate that admits up to N threads concurrently and was historically the first general-purpose primitive (Dijkstra, 1965); a condition variable lets a thread wait until some predicate over shared state becomes true, always paired with a mutex. A monitor packages a mutex with one or more condition variables into a language-level construct (Hoare, 1974). Choosing the wrong primitive — using a semaphore where a condition variable is needed, treating a mutex as a signaling channel, or replacing a while-loop wait with if — is the source of most concurrency bugs that aren’t outright races. This note is the reference card: what each primitive guarantees, what it does not, the per-language API map (Python threading, Java synchronized and java.util.concurrent, C++ <mutex>/<condition_variable>), and the safety vs liveness trade-offs that govern choice.

1. Intuition — Three Different Kinds of Door

Imagine three different doors in a building, each enforcing a different rule.

The mutex is a single-occupant restroom. There is one key, hanging on a hook by the door. To enter, you take the key (lock); when you leave, you return the key (unlock). If someone else has the key, you wait. Exactly one person inside at any time. Crucially, the same person who took the key must return it — there is an owner. Try to return a key you never took, and the system rejects you (in a well-implemented mutex).

The semaphore is a parking lot with a counter at the gate displaying “spaces available.” When you drive in, the counter decrements (acquire/P); when you drive out, it increments (release/V). If the counter is 0, you wait at the gate. The counter can start at any value N — a parking lot with 50 spaces lets up to 50 cars in concurrently. Crucially, anyone can increment the counter — the car that enters does not have to be the one that leaves. There is no ownership; the semaphore is a pure counter.

The condition variable is a waiting-room buzzer. You sit in a doctor’s waiting room because some condition is not yet true (“the doctor is ready for me”). You hand your buzzer to the receptionist (release the mutex) and sit down (block on wait). When the receptionist sees the doctor is free, she presses the buzzer (notify/signal); you wake up, take back your buzzer (re-acquire the mutex), check that it really is your turn (the predicate), and proceed. The waiting-room buzzer is paired with the receptionist — without the desk and clipboard (the mutex protecting the patient list), buzzing is meaningless. And critically: sometimes the buzzer goes off spuriously (electrical interference, false alarms) or for the wrong patient — you must always re-check the predicate before proceeding (the famous while not predicate: wait() pattern).

The monitor is the entire doctor’s office. The receptionist desk and the waiting-room buzzer come together as one structure. In a programming language with monitor support — Java’s synchronized, C# lock, certain Pascal dialects — you don’t construct the mutex and condvar separately; they’re built into every object.

These analogies map cleanly onto the formal semantics, which we develop below.

2. Tiny Worked Example — Three Threads, Three Primitives

We have three concurrent tasks and a shared counter. Compare how each primitive coordinates them.

2.1 Mutex Example

Two threads each increment a shared counter 1000 times. Without a mutex, the counter ends up somewhere between 1000 and 2000 because counter = counter + 1 is three machine instructions: read, add, write. With interleaving, two reads can both see the same old value, both write the same new value — an update is lost. With a mutex, only one thread is in the critical section at a time, so each increment is atomic with respect to other threads:

T1 acquires mutex → reads counter (47) → writes 48 → releases mutex
T2 acquires mutex → reads counter (48) → writes 49 → releases mutex

Final value: 2000. Safety property satisfied (no lost updates). The critical section serializes access.

2.2 Semaphore Example — Resource Pool

A connection pool of 3 database connections, accessed by 10 worker threads. A semaphore initialized to 3 allows up to 3 workers to hold a connection simultaneously:

sem = Semaphore(3)
T1 acquire → counter 3→2, gets conn #1
T2 acquire → counter 2→1, gets conn #2
T3 acquire → counter 1→0, gets conn #3
T4 acquire → counter is 0, BLOCKS
T1 release → counter 0→1, T4 wakes up, gets conn #1

The semaphore is not protecting a critical section — it is gating count of in-flight users. This is the use case where semaphores genuinely beat mutexes: they generalize from “one at a time” (binary semaphore, count = 1) to “up to N at a time” (counting semaphore).

2.3 Condition Variable Example — Wait Until Ready

A worker thread should sleep until some shared state (work_available) becomes true. The producer flips the state and wakes the worker:

Worker:
  acquire mutex
  while not work_available:
      cv.wait(mutex)         # atomically releases mutex, sleeps;
                             # on wake, re-acquires mutex
  process the work
  release mutex

Producer:
  acquire mutex
  work_available = True
  cv.notify()                # wake one waiter
  release mutex

The wait call has a precise three-step contract: (1) atomically release the mutex and block, (2) on receiving a signal, re-acquire the mutex, (3) return. Without atomicity in step 1, a notify between “release mutex” and “block” would be lost — the classic missed wakeup race. The while (not if) is essential: see §7.3 Spurious Wakeups.

3. Pseudocode — The Three Primitives

3.1 Mutex

struct Mutex:
    locked: bool = false
    owner: ThreadID = NONE
    waiters: Queue<ThreadID>

lock(m):
    atomically:
        if not m.locked:
            m.locked = true
            m.owner = current_thread()
            return
        else:
            m.waiters.enqueue(current_thread())
    block_current_thread()       # release CPU, scheduler picks another thread

unlock(m):
    assert m.owner == current_thread()    # only owner may unlock
    if m.waiters.empty():
        m.locked = false
        m.owner = NONE
    else:
        next = m.waiters.dequeue()
        m.owner = next
        wake(next)               # m.locked stays true (ownership transferred)

Properties. Mutual exclusion (only one thread in the protected section), ownership (only the locking thread may unlock), bounded waiting under fair queueing.

3.2 Counting Semaphore (Dijkstra’s P and V)

The names P (probeer = “try” in Dutch, sometimes glossed as passeren, “pass”) and V (verhogen = “increment”) come from Dijkstra 1965, EWD 123, “Cooperating Sequential Processes.” Modern names: acquire / release or wait / signal.

struct Semaphore:
    count: int        # nonnegative invariant
    waiters: Queue<ThreadID>

acquire(s):           # "P" or "wait"
    atomically:
        while s.count == 0:
            s.waiters.enqueue(current_thread())
            block_current_thread()    # released by some release()
        s.count -= 1

release(s):           # "V" or "signal"
    atomically:
        s.count += 1
        if s.waiters not empty:
            t = s.waiters.dequeue()
            wake(t)

Properties. No ownership — any thread can release. Any nonnegative initial count. Counting variant for resource pools; binary variant (count ∈ {0, 1}) gives mutual exclusion but without ownership, which makes it a worse mutex (can’t detect “double release” or “release without acquire” bugs).

3.3 Condition Variable

struct CondVar:
    waiters: Queue<ThreadID>

wait(cv, mutex):
    atomically:
        cv.waiters.enqueue(current_thread())
        unlock(mutex)
        block_current_thread()
    # ...later, when woken:
    lock(mutex)            # re-acquire before returning to caller

notify(cv):                # also called "signal"
    atomically:
        if cv.waiters not empty:
            t = cv.waiters.dequeue()
            wake(t)        # t will re-acquire the mutex when scheduled

notify_all(cv):            # also called "broadcast"
    atomically:
        for t in cv.waiters:
            wake(t)
        cv.waiters.clear()

Atomicity in wait. The “enqueue + unlock + block” must happen atomically with respect to other notify calls. Otherwise, a notify between unlock and block disappears (no waiter to wake), and the waiter sleeps forever. This is the missed-wakeup race; it is why wait takes the mutex as an argument and is implemented with kernel-level support (e.g., futex on Linux).

4. Python Implementation

The Python threading module provides all three primitives. We illustrate each.

4.1 Mutex — threading.Lock and threading.RLock

import threading
 
# Non-reentrant mutex
lock = threading.Lock()
 
counter = 0
 
def increment(n):
    global counter
    for _ in range(n):
        lock.acquire()
        try:
            counter += 1            # critical section
        finally:
            lock.release()
 
# Or, idiomatically, with a context manager:
def increment_pythonic(n):
    global counter
    for _ in range(n):
        with lock:                  # __enter__ acquires, __exit__ releases (even on exception)
            counter += 1
 
threads = [threading.Thread(target=increment_pythonic, args=(10000,)) for _ in range(10)]
for t in threads: t.start()
for t in threads: t.join()
print(counter)                      # 100000, deterministically

threading.Lock() is a non-reentrant mutex: if the same thread calls acquire() twice in a row without an intervening release(), it deadlocks against itself. threading.RLock() (reentrant lock) allows the owning thread to re-acquire arbitrarily many times, requiring an equal number of releases. RLock is what you need when a method holding the lock calls another method that also locks. The cost of RLock is tracking owner identity and recursion depth, so prefer Lock when you can.

The Python GIL is not your mutex

CPython’s Global Interpreter Lock (GIL) makes individual bytecodes atomic — x += 1 might look atomic, but x = x + 1 compiles to LOAD_GLOBAL, LOAD_CONST, BINARY_ADD, STORE_GLOBAL, and the GIL can be released between any pair. So counter += 1 is a race in pure-Python multithreaded code. Use a Lock. The free-threaded Python (PEP 703, optional in 3.13+) removes the GIL entirely, making this even more important.

4.2 Semaphore — threading.Semaphore

import threading
import time
import random
 
# Up to 3 concurrent connections allowed
pool_sem = threading.Semaphore(3)
 
def use_connection(worker_id):
    print(f"worker {worker_id} waiting for connection")
    with pool_sem:                         # acquire on enter, release on exit
        print(f"worker {worker_id} got connection")
        time.sleep(random.uniform(0.1, 0.3))
        print(f"worker {worker_id} releasing connection")
 
threads = [threading.Thread(target=use_connection, args=(i,)) for i in range(10)]
for t in threads: t.start()
for t in threads: t.join()

At any instant, at most 3 workers print “got connection” before any prints “releasing.” The semaphore caps concurrency at the resource limit. Note: threading.Semaphore does not check that releases match acquires — pool_sem.release() called too many times silently raises the count beyond the initial value, breaking the invariant. For that defensive check, use threading.BoundedSemaphore, which raises ValueError on over-release.

4.3 Condition Variable — threading.Condition

The producer-consumer pattern, the canonical condvar example (see Producer-Consumer for the full deep-dive):

import threading
from collections import deque
 
buffer = deque()
MAX_SIZE = 5
not_empty = threading.Condition()       # condvar, also creates an RLock internally
not_full  = threading.Condition(not_empty)  # share the lock so both predicates serialize
 
def producer():
    for i in range(20):
        with not_full:                  # acquire lock
            while len(buffer) == MAX_SIZE:
                not_full.wait()         # release lock, sleep; on wake, re-acquire
            buffer.append(i)
            not_empty.notify()          # wake one consumer
 
def consumer():
    while True:
        with not_empty:
            while not buffer:
                not_empty.wait()
            item = buffer.popleft()
            not_full.notify()
        process(item)

The two condition variables share the same underlying lock so that len(buffer) is consistent across both predicates. The while (not if) on each predicate guards against §7.3 spurious wakeups and against the Mesa (not Hoare) signaling discipline that Python and most modern languages use — under Mesa semantics, between a notify() and the woken thread re-acquiring the lock, another thread can sneak in and invalidate the predicate.

5. Per-Language API Map

ConceptPython threadingJava java.util.concurrentC++ <mutex> / <condition_variable>
Non-reentrant mutexLock()(no direct equivalent; synchronized is reentrant)std::mutex
Reentrant mutexRLock()synchronized block; ReentrantLockstd::recursive_mutex
Counting semaphoreSemaphore(N)Semaphore(N)std::counting_semaphore<N> (C++20)
Binary semaphoreSemaphore(1)Semaphore(1)std::binary_semaphore (C++20)
Bounded semaphoreBoundedSemaphore(N)(manual)(manual)
Condition variableCondition()Condition (from Lock.newCondition()); Object.wait/notify/notifyAllstd::condition_variable
Read-write lock(none in stdlib; readerwriterlock lib)ReentrantReadWriteLock, StampedLockstd::shared_mutex
Atomic integerthreading doesn’t expose; use multiprocessing.Value or atomic libAtomicIntegerstd::atomic<int>
Once / one-shot init(none built-in)synchronized + flag, or AtomicReferencestd::call_once / std::once_flag

5.1 Java Specifics — synchronized and Object Monitors

Every Java object has an associated intrinsic lock and single condition variable (the object monitor). The keyword synchronized is sugar for acquire/release of the intrinsic lock; wait(), notify(), notifyAll() operate on the object’s single condvar:

class BoundedBuffer {
    private final Queue<Integer> q = new LinkedList<>();
    private final int capacity = 5;
 
    public synchronized void put(int x) throws InterruptedException {
        while (q.size() == capacity) wait();    // Object.wait() — releases intrinsic lock
        q.offer(x);
        notifyAll();                            // wake all waiters; not-empty waiters proceed
    }
 
    public synchronized int take() throws InterruptedException {
        while (q.isEmpty()) wait();
        int x = q.poll();
        notifyAll();
        return x;
    }
}

The single intrinsic-lock-and-single-condvar design is limiting — you can’t have separate “not full” and “not empty” condvars per the canonical producer-consumer textbook construction, so you broadcast (notifyAll) and tolerate the wasted wakeups. For finer control, use java.util.concurrent.locks.ReentrantLock and lock.newCondition() to get multiple condvars per lock. See the java.util.concurrent.locks package.

5.2 C++ Specifics — RAII and unique_lock

C++ std::condition_variable::wait requires std::unique_lock<std::mutex> (not bare std::lock_guard) because wait must be able to release-and-reacquire:

#include <mutex>
#include <condition_variable>
#include <queue>
 
std::queue<int> q;
std::mutex m;
std::condition_variable cv_not_empty;
 
void producer(int x) {
    {
        std::lock_guard<std::mutex> lk(m);    // scoped lock, no release-reacquire needed
        q.push(x);
    }
    cv_not_empty.notify_one();
}
 
int consumer() {
    std::unique_lock<std::mutex> lk(m);       // unique_lock supports manual release
    cv_not_empty.wait(lk, [&]{ return !q.empty(); });   // predicate form: while not pred, wait
    int x = q.front(); q.pop();
    return x;
}

The lambda form of wait (wait(lk, predicate)) is sugar for the while (!predicate()) cv.wait(lk); loop. Use it; it is harder to misuse than the bare form.

6. Correctness — Safety vs Liveness

A concurrent algorithm is correct only if it satisfies both safety and liveness properties. The two are independent, and a primitive choice that delivers one can break the other.

Safety: “nothing bad happens.” Mutual exclusion (no two threads simultaneously inside a critical section, no lost updates, no torn reads of multi-word values), data-race freedom, well-formed states (the buffer length stays in [0, MAX_SIZE]).

Liveness: “something good eventually happens.” Deadlock freedom (the system as a whole makes progress), starvation freedom (every individual thread eventually makes progress), bounded waiting (a thread is overtaken at most k times for some finite k).

The trade-off is real:

  • A strictly fair mutex (FIFO acquisition) maximizes liveness/fairness but harms throughput because cache-warm threads can be forced to wait for cold threads.
  • An unfair / barging mutex (e.g., the default Java ReentrantLock, the default pthread_mutex) maximizes throughput but allows starvation: a thread releasing the lock might immediately re-acquire it before a queued waiter.
  • A lock-free algorithm guarantees system-wide progress (no deadlock, ever) but a specific thread can still spin forever if other threads keep racing past it. Wait-free is the strongest form: every thread completes its operation in a bounded number of steps, regardless of what others do.

Each primitive admits different bugs:

  • Mutex: deadlock if multiple locks are acquired in inconsistent orders (see Deadlock Detection and Avoidance).
  • Semaphore: semantic confusion — using a semaphore as a signaling primitive (initial count 0, one thread acquires waiting, another releases as signal) works but is harder to reason about than a condvar.
  • Condition variable: missed wakeup if mutex/condvar pairing is wrong; using if instead of while violates the Mesa semantics; using a condvar without holding its mutex is undefined behavior.

7. Pitfalls

7.1 Releasing a Mutex You Don’t Own

In a non-reentrant mutex with ownership semantics, releasing a mutex held by another thread is undefined behavior or an outright runtime error. In Python’s threading.Lock, calling release() from a non-owner thread raises RuntimeError. The bug typically appears when locks are passed across threads as a “ticket.” Don’t do that — the thread that locks, unlocks.

7.2 Forgetting to Release on Exception

lock.acquire()
risky_operation()              # raises
lock.release()                 # never reached → permanent lock-hold → deadlock

The fix is try/finally or, more idiomatically, the context manager: with lock: risky_operation(). The context manager’s __exit__ runs even on exception, releasing the lock. Same with C++ RAII (std::lock_guard is destroyed on stack unwind).

7.3 Spurious Wakeups — the while-Loop Rule

Modern condvar implementations (Python, Java, C++, POSIX) operate under Mesa semantics, named after the Xerox Mesa language (Lampson & Redell, 1980). When a thread is notifyed, it does not immediately resume — it must first re-acquire the mutex, and between notify and re-acquisition, other threads can change the shared state. Additionally, the OS may spuriously wake a thread without any notify at all (this is allowed by POSIX and Java specifications to simplify kernel implementation).

Therefore, always check the predicate in a while loop, never if:

# WRONG (Mesa semantics violation):
with cond:
    if not buffer:
        cond.wait()
    item = buffer.popleft()    # buffer may be empty here!
 
# RIGHT:
with cond:
    while not buffer:
        cond.wait()            # wake → re-check predicate → maybe wait again
    item = buffer.popleft()

Hoare’s original 1974 paper specified Hoare semantics — the signaler immediately gives up the lock to the waiter, who then has the predicate guaranteed true. No while needed. But Hoare semantics are hard to implement efficiently and almost no modern system uses them. Always assume Mesa.

7.4 Notify Without Holding the Mutex

In some implementations (Python, POSIX), calling notify() without holding the mutex is technically allowed but creates a race window: the signaler can change the predicate, then notify, then a waiter can wake before the change becomes visible. Best practice: hold the mutex around both the predicate change and the notify. (Java’s Object.notify() requires holding the monitor; calling without raises IllegalMonitorStateException.)

7.5 notify vs notify_all — When Choice Matters

notify() wakes one waiter; notify_all() wakes all. With one condvar serving multiple distinct predicates (a common design when the language gives you only one condvar per object, like Java’s intrinsic monitor), you must notify_all because notify might wake the wrong waiter (one whose predicate is still false, who then re-sleeps — and your predicate-true waiter never gets woken). With separate condvars per predicate (Python, ReentrantLock.newCondition(), C++), notify is correct and more efficient. The cost of notify_all when you could have used notify is the thundering herd: all waiters wake, contend for the mutex, all but one re-sleep, wasting CPU.

7.6 Binary Semaphore vs Mutex

A binary semaphore (count ∈ {0, 1}) provides mutual exclusion but lacks ownership. Symptoms when used as a mutex:

  • Any thread can release even if it never acquired (silent over-count, breaks invariants).
  • No detection of double-release.
  • No detection of forgetting to release.
  • Cannot be made reentrant.

Use a real mutex when you want mutual exclusion. Use a semaphore when you want to count.

7.7 Semaphores for Signaling — Subtler Than They Look

A common idiom: “one thread waits for an event, another signals it”:

event = threading.Semaphore(0)       # init to 0
 
def waiter():
    event.acquire()                  # blocks until release
    do_work()
 
def signaler():
    setup_done = True
    event.release()                  # wake the waiter

This works for one-to-one signaling but breaks subtly with multiple waiters or repeated signals. For event signaling, prefer threading.Event (a built-in flag with set(), clear(), wait() semantics) or a condvar. Semaphores conflate “count of available resources” with “this thing happened” awkwardly.

7.8 Deadlock From Inconsistent Lock Order

Two locks A and B. Thread 1 acquires A then B; Thread 2 acquires B then A. Possible execution: T1 holds A, T2 holds B; T1 waits for B, T2 waits for A — classic deadlock. The fix is a canonical lock-acquisition order — pick a total order (by address, by id, by name) and always lock in that order. This is the “resource hierarchy” solution to Dining Philosophers and the standard prevention recipe in Deadlock Detection and Avoidance.

7.9 Lock Granularity — Coarse vs Fine

A coarse lock (one big mutex protecting everything) is easy to reason about but kills concurrency — only one thread at a time. A fine-grained scheme (one mutex per data structure, or per bucket in a hash table — see Hash Table for ConcurrentHashMap’s segmented locking) increases concurrency but exposes you to deadlock and ordering bugs. The right answer is workload-dependent; profile before refactoring.

7.10 Priority Inversion

Low-priority thread holds a mutex; high-priority thread blocks waiting on it; medium-priority thread (not contending for the mutex) preempts the low-priority thread. Now the high-priority thread is effectively waiting on the medium-priority thread’s progress — priority inversion. The famous case: NASA’s Mars Pathfinder (1997) suffered repeated resets because of priority inversion in its VxWorks scheduler (writeup). Fix: priority inheritance (the low-priority holder temporarily inherits the high priority of the waiting thread). Real-time mutex variants enable this; default mutexes typically don’t.

7.11 Forgetting the Atomicity in wait

Beginners who try to “implement their own condvar” using only mutexes and a flag invariably hit the missed-wakeup race:

# DON'T — broken hand-rolled condvar
def wait(mutex, flag):
    mutex.release()
    while not flag:
        sleep(0.001)              # busy-wait + race
    mutex.acquire()

There’s a window between mutex.release() and the while check where a notifier can set flag, and the woken thread enters its sleep loop, missing the signal. Real condvars rely on kernel atomic primitives (Linux futex, Windows WaitOnAddress) to make the “release + sleep” pair atomic with respect to wake operations. Don’t roll your own.

7.12 Assuming volatile (Java) or _Atomic (C) Is Enough

volatile in Java enforces ordering and visibility but is not atomic for compound operations. volatile int counter; counter++; is still a race because counter++ reads, adds, writes — three steps. Use AtomicInteger for that. C++ std::atomic<T> and Java java.util.concurrent.atomic.* are the right primitive for lock-free counters and flags. See Mutability and Aliasing Bugs for the language-level memory-model details.

8. Variants and Sub-Patterns

8.1 Reentrant vs Non-Reentrant

A reentrant (recursive) mutex tracks ownership and a recursion count: the owning thread can lock() again without blocking, incrementing the count; each unlock() decrements it; the lock is released when the count reaches 0. Useful when method A (which locks) calls method B (which also locks the same mutex). Cost: per-acquire overhead to track owner identity. Java synchronized is always reentrant; C++ std::mutex is not (use std::recursive_mutex); Python has both Lock (non-reentrant) and RLock (reentrant).

8.2 Spinlocks vs Blocking Locks

A spinlock busy-waits in a tight loop instead of blocking. Worth it when expected wait time is less than the cost of a context switch (~1-10 μs typically). Used in OS kernels for very short critical sections. Catastrophic in user-space if held longer than expected, because you waste an entire CPU on busy-waiting. Modern adaptive mutexes (e.g., pthread_mutex on Linux with PTHREAD_MUTEX_ADAPTIVE_NP, Java’s biased locking before deprecation) spin briefly then fall through to blocking — best of both worlds.

8.3 Read-Write Lock

Allows multiple concurrent readers OR a single writer. Optimization for read-heavy workloads. Java ReentrantReadWriteLock, C++ std::shared_mutex. The full design is covered in Reader-Writer Problem.

8.4 Counting Semaphore vs Binary Semaphore

Counting: arbitrary nonnegative initial count, used for resource pools (connection pools, thread pools). Binary: count ∈ {0, 1}, semantically a mutex without ownership; can be used for signaling in a pinch but a real condvar or Event is clearer.

8.5 Monitor — Mutex + Condvar Bundled

A monitor is a language-level construct that bundles a mutex and one or more condition variables, automatically locking on method entry. Java’s intrinsic locks (synchronized methods) approximate this; the Pascal language family had explicit monitor keywords. Monitors prevent the most common mistake (forgetting to lock) by making lock-on-entry the default. The trade-off is reduced flexibility — you can’t acquire the lock without entering a method, and many monitor designs allow only one condvar.

8.6 Lock-Free and Wait-Free Algorithms

When per-operation latency must be bounded, lock-free algorithms use atomic compare-and-swap (CAS) to make progress without blocking. A classic example is Michael-Scott’s lock-free queue (1996). The trade-off: lock-free code is dramatically harder to write correctly (memory ordering, ABA problem) and the throughput advantage often disappears under contention. Wait-free is even stronger and even harder. See Producer-Consumer for lock-free queue notes.

8.7 Hand-Over-Hand Locking (“Lock Coupling”)

For linked data structures (linked list, tree), acquire the next node’s lock before releasing the current node’s. Allows multiple threads to traverse concurrently while ensuring that a node is never modified by two threads at once. Used in concurrent linked lists, concurrent skip lists (Skip List), and concurrent B-trees.

9. Mermaid Diagram — State Transitions for Each Primitive

stateDiagram-v2
    [*] --> Unlocked : Mutex created
    Unlocked --> Locked : T1 lock()
    Locked --> Unlocked : T1 unlock()
    Locked --> Locked : T1 lock() (RLock; recursion++)
    Locked --> Waiting : T2 lock() while T1 holds
    Waiting --> Locked : T1 unlock(); T2 acquires
    note left of Waiting
      Mutex: blocks waiter
      until owner releases
    end note

    state Semaphore {
        [*] --> CountN : Sem(N)
        CountN --> CountN_minus_1 : acquire()
        CountN_minus_1 --> Count0 : ...more acquires...
        Count0 --> Blocked : acquire() while count=0
        Blocked --> Count0 : release() wakes waiter
        Count0 --> CountN : release() N times
    }

    state CondVar {
        [*] --> NoWaiters
        NoWaiters --> WaitersQueue : T1 wait(mutex)
        WaitersQueue --> WaitersQueue : T2,T3 wait(mutex)
        WaitersQueue --> NoWaiters : notify_all()
        WaitersQueue --> WaitersQueueMinus1 : notify() (wakes one)
        note right of WaitersQueue
          Each waiter, on wake,
          re-acquires mutex,
          re-checks predicate
          (Mesa semantics)
        end note
    }

What this diagram shows. Three independent state machines, one per primitive. The Mutex has just two main states (Unlocked, Locked) plus a transient Waiting state for blocked threads; ownership transfers serialize state transitions. The Semaphore is a counter machine: each acquire() decrements the count, each release() increments; threads block only when count = 0. The Condition Variable is a waiter queue with no state of its own — it lives entirely in the queue of blocked threads, and notify / notify_all are the only transitions. The right-side note emphasizes the Mesa semantics: a notified waiter must re-acquire the mutex and re-check the predicate before it can proceed, which is why the loop must be while, never if. The visual takeaway: the three primitives serve fundamentally different purposes (mutual exclusion, counting, waiting-on-predicate) and are not interchangeable, despite the surface similarity that they all “block threads.”

10. Common Interview Problems

ProblemPrimitive(s) UsedNote
Implement thread-safe counterMutexOne-line critical section
Bounded buffer / Producer-ConsumerMutex + 2 condvars (or semaphores)Canonical use of condvar
Connection poolCounting semaphoreInit to pool size
One-time initializationMutex + flag, or std::call_once”Double-checked locking” if mutex is too expensive (still tricky)
Print numbers in sequence with N threadsCondvars or semaphoresLeetCode 1114 (“Print in Order”)
FizzBuzz MultithreadedMultiple condvars, or rotating semaphoreLeetCode 1195
Build H2O molecule from H, O threadsCounting semaphore + barrierLeetCode 1117
Reader-Writer ProblemRead-write lock OR mutex + counter + cvMultiple readers OR single writer
Dining PhilosophersPer-fork mutex; deadlock-prevention strategyClassic teaching problem
Implement a lock from atomicsCAS, memory barriersReal interview at OS-level companies
Implement a semaphore from a mutex + condvarMutex protects count, condvar waits when count = 0Build-from-primitives exercise
Implement a condvar from a semaphore + mutexSubtle — see Andrew Birrell’s “Implementing Condition Variables with Semaphores”Reverse direction is hard

11. Open Questions

  • Is the Mesa-vs-Hoare semantics distinction still pedagogically important, given that essentially no modern system uses Hoare semantics? (Answer: yes, because it explains why the while-loop rule exists.)
  • How much does spurious wakeup actually happen on Linux futex? The kernel doesn’t prefer spurious wakeups, but the spec allows them, and one root cause is signal delivery interrupting futex_wait. Order of magnitude: rare under normal load, noticeable under signal-heavy workloads.
  • Are RCU (Read-Copy-Update) and hazard pointers — used in the Linux kernel for read-mostly data — better described as primitives or as patterns? They blur the line between synchronization and memory management.

12. See Also

Graph View

Backlinks