Locks and Mutexes, in depth: exclusion and visibility, futexes, fairness, lock design and contention

What a mutex promises: exclusion and visibility

A mutex makes two promises, and people usually remember only the first. The first is exclusion: between a successful lock() and the matching unlock(), no other thread can hold the same mutex, so the code in between (the critical section) runs as if it were alone. The second is visibility: compilers and CPUs reorder and buffer writes. Unlocking a mutex is a release operation and locking it is an acquire operation, so everything a thread wrote before unlocking is guaranteed visible to the next thread that locks the same mutex. In Java's memory model this is the happens-before edge from an unlock to every subsequent lock of that monitor.

So a lock must protect reads as well as writes: a reader that skips it can see a half-updated object or a stale value. Every access to shared mutable state holds the one lock that guards it. Document which lock guards which fields; Java's @GuardedBy annotation and Clang's thread-safety analysis can check it for you.

The bug a lock fixes

The classic demonstration is a shared counter. count += 1 looks atomic but is three steps: load, add, store. Two threads can both load 41, both add one and both store 42, losing an increment. Run four threads doing a million increments each and the total is usually well short of four million.

// Java: broken, then fixed with a mutex
class Counter {
    private long count;                 // guarded by lock
    private final Object lock = new Object();

    void brokenIncrement() { count++; } // load, add, store: lost updates

    void increment() {
        synchronized (lock) {           // acquire: see all earlier writes
            count++;
        }                               // release: publish this write
    }

    long get() {
        synchronized (lock) { return count; }  // reads need the lock too
    }
}

For a single counter, an atomic increment is the better tool (see atomics). A mutex earns its keep when an invariant spans several fields, such as a map and its size: no single atomic can update both, but a critical section can, and nobody sees the halfway state.

Inside a mutex: atomics plus a futex

A mutex is built from two ingredients: an atomic read-modify-write instruction (compare-and-swap or exchange) to claim the lock, and a way to put a thread to sleep when it cannot. Pure spinning wastes a core, and a system call on every lock wastes hundreds of nanoseconds even when nobody else wants the lock. Linux resolves this with the futex (fast user-space mutex): the lock is an ordinary integer in user memory, and the kernel provides FUTEX_WAIT (sleep if the integer still holds the expected value) and FUTEX_WAKE (wake up to N sleepers on this address). glibc's pthread_mutex_t, Go's runtime and Rust's standard library on Linux all build on this idea; Windows has the comparable WaitOnAddress.

The best-known design, from Ulrich Drepper's paper Futexes Are Tricky, uses three states so that an uncontended unlock never makes a system call:

# state: 0 = unlocked, 1 = locked, no waiters, 2 = locked, maybe waiters
def lock(m):
    c = cas(m.state, 0, 1)          # returns the old value
    if c == 0:
        return                      # fast path: no kernel involved
    if c != 2:
        c = exchange(m.state, 2)    # announce: someone is about to wait
    while c != 0:
        futex_wait(m.state, 2)      # sleep only if state is still 2
        c = exchange(m.state, 2)    # woke up: try to take it, keep "2"

def unlock(m):
    if exchange(m.state, 0) == 2:   # were there (possibly) sleepers?
        futex_wake(m.state, 1)      # wake exactly one

The kernel's futex_wait re-checks the value inside the kernel, so a wake between the user-space check and the sleep is never lost. A woken thread sets the state to 2, not 1, because it cannot know whether others still sleep; an occasional spurious wake is the price of never missing one.

Spin or sleep

Parking and unparking a thread costs system calls and a context switch, typically several microseconds, plus cold caches on resume. If the critical section takes tens of nanoseconds, the owner will release before the waiter has finished falling asleep. So production mutexes are adaptive: spin briefly, betting the owner is running on another core, then wait on the futex. HotSpot does this for synchronized, Go's sync.Mutex spins a few iterations only on multicore machines with another processor busy, and glibc offers an adaptive mutex type.

Spinning only helps while the owner runs. If it has been preempted, spinning burns the CPU it needs to finish. Pure spinlocks belong in kernels and tiny non-preemptible sections; see the spinlock article. In application code, use the platform mutex and let it decide.

Fairness versus throughput

When a lock is released and there are waiters, who gets it next? A fair lock hands it to the longest waiter, in FIFO order. An unfair lock lets any thread that arrives at the right moment take it, including the thread that just released it: barging. Barging usually wins on throughput, because the releaser runs with hot caches while a woken waiter needs microseconds to be scheduled; strict handoff forces a context switch per contended release and can form lock convoys.

The cost of unfairness is tail latency and possible starvation, so implementations compromise. Java's ReentrantLock is unfair by default; new ReentrantLock(true) grants it in arrival order, at a large throughput cost under contention, and note that the untimed tryLock() barges even on a fair lock. Go's sync.Mutex runs in normal (barging) mode but switches to starvation mode when a waiter has waited more than one millisecond: ownership is then handed directly to the head waiter, and newcomers queue behind it, until a waiter gets the lock quickly or is the last in line. Fairness also interacts with thread priorities; if a low-priority owner can block a high-priority waiter indefinitely, read priority inversion.

The same lock in five languages

Each language's spelling encodes a different safety net:

Rust's design is worth copying in spirit: the mutex owns the data, so the compiler will not let you reach it without the guard. Whatever the language, use the scoped form (synchronized, with, RAII guards, defer mu.Unlock(), try/finally around ReentrantLock) so every exit path, including exceptions and early returns, releases the lock.

Reentrancy, ownership and robustness

A reentrant mutex lets its owner lock it again, releasing when the count returns to zero. It is convenient, but if a method re-enters while an invariant is half-updated, the inner call sees broken state and the lock cannot help, because you already hold it. A non-reentrant mutex deadlocks on re-entry instead: loud, but honest. In debug builds of C code, an error-checking mutex (PTHREAD_MUTEX_ERRORCHECK) reports relocking and unlocking by a non-owner. Rust's poisoning answers a related question, what happens if the holder crashes: a panic inside the critical section makes the next lock() return an error, so callers must decide whether the data is still trustworthy.

Granularity and striping, with a worked example

Lock granularity decides how much state one lock guards. A single global lock is easy to reason about and serializes everything. Finer locks allow more parallelism and multiply the ways to deadlock. A common middle ground is lock striping: split the data into N shards, each with its own lock, and choose the shard by hash.

class StripedCounterMap<K> {
    private static final int STRIPES = 64;           // power of two
    private final Object[] locks = new Object[STRIPES];
    private final Map<K, Long>[] shards = new HashMap[STRIPES];

    StripedCounterMap() {
        for (int i = 0; i < STRIPES; i++) { locks[i] = new Object(); shards[i] = new HashMap<>(); }
    }
    private int stripe(K key) { return (key.hashCode() * 0x9E3779B9) >>> 26; } // top 6 bits

    void add(K key, long delta) {
        int s = stripe(key);
        synchronized (locks[s]) { shards[s].merge(key, delta, Long::sum); }
    }
}

Worked example: a request handler spends 2 microseconds updating a shared statistics map under one lock, and the service handles 300,000 requests per second. The lock must be held 0.6 seconds out of every second, so it is 60% utilized; by basic queueing, waits grow sharply as utilization approaches 100%, and adding cores cannot raise throughput past 500,000 requests per second. With 64 stripes and evenly spread keys, each lock is under 1% utilized and the bottleneck disappears; a whole-map snapshot now needs all 64 locks, taken in index order. Often better first moves: shrink the critical section (compute outside, publish inside), or, when reads dominate, a read-write lock.

Lock ordering and deadlock avoidance

Deadlock needs four conditions at once: mutual exclusion, hold-and-wait, no preemption and a circular wait. You cannot drop the first three with ordinary mutexes, so break the cycle with a global lock order. The textbook case is a transfer between two accounts: thread A transfers from X to Y and locks X then Y, while thread B transfers from Y to X and locks Y then X. Each holds one lock and waits forever for the other. Ordering by a stable key fixes it:

void transfer(Account from, Account to, long amount) {
    Account first  = from.id < to.id ? from : to;   // global order by id
    Account second = from.id < to.id ? to : from;
    synchronized (first) {
        synchronized (second) {
            if (from.balance < amount) throw new InsufficientFunds();
            from.balance -= amount;
            to.balance   += amount;
        }
    }
}

When no natural order exists, acquire with tryLock(timeout), release everything on failure and retry after a random backoff. Never call unknown code such as callbacks while holding a lock; you cannot know what it locks. For finding deadlocks that already exist, see deadlock detection.

Failure modes

• Unguarded read. Writers lock, a reader does not, and sees torn or stale state. Fix: one lock per invariant, used on every access; run a race detector (go test -race, ThreadSanitizer) in CI.
• Lock held across I/O. A database call or RPC inside a critical section turns a microsecond lock into a 50 ms one and serializes the service. Fix: copy what you need, release, do the I/O, then re-lock and re-validate.
• Forgotten unlock on an error path. Manual lock()/unlock() with an early return leaks the lock; the next caller hangs forever. Fix: scoped release only.
• Check-then-act across two critical sections. if (!map.containsKey(k)) map.put(k, v) with each call individually locked is still a race. Fix: hold one lock across the compound action or use an atomic operation such as computeIfAbsent.
• Virtual-thread pinning. Before JDK 24, a virtual thread blocking inside synchronized pinned its carrier thread; JEP 491 removed that in JDK 24. On older JDKs, prefer ReentrantLock around blocking code.

Measuring contention

Contention is invisible in CPU profiles: blocked threads use no CPU, so a lock-bound service shows low utilization and high latency at the same time. Measure waiting directly. In Java, thread dumps (jcmd <pid> Thread.print) show BLOCKED threads and which monitor they wait on, and JDK Flight Recorder records jdk.JavaMonitorEnter and jdk.ThreadPark events with durations and stack traces. Go has a mutex profile: set runtime.SetMutexProfileFraction(5) and read /debug/pprof/mutex. On Linux, perf lock and off-CPU flame graphs show time asleep on futexes. (Biased locking was disabled in JDK 15 and removed in JDK 18; do not tune for it.) For your hottest locks, record wait-time and hold-time histograms: wait time shows contention, hold time shows why.

When a mutex is the wrong tool

Reach past the mutex when the problem's shape says so: one word of state wants an atomic, a producer feeding a consumer wants a queue, read-mostly data wants copy-on-write behind one atomic reference, and state owned by a single thread needs no lock at all.

What to do next

1. List every shared mutable field in one service and write down which lock guards it; mark it with @GuardedBy or a comment.
2. Turn on a race detector in your test suite: go test -race, ThreadSanitizer for C and C++, or stress tests with jcstress for Java.
3. Replace manual lock/unlock pairs with scoped forms; move I/O and callbacks out of critical sections.
4. Document a global order for code that takes more than one lock.
5. Profile your busiest locks under peak load (mutex profile or JFR); if one is hot, shrink it, then stripe or shard, re-measuring after each change.