Locks and waiting

3.6 Waiting your turn: what a lock is and what it costs

A lock is the oldest answer to sharing. It lets one thread at a time into the code that touches the shared data, the critical section, and makes every other thread wait. A mutex, short for mutual exclusion, is that lock. It is simple and it is correct, and all of its costs lie in when it is used. This section is how a mutex is built, why it needs the kernel, and what each way of getting it costs.

What a mutex is made of

A mutex has two parts: an atomic word that says whether the lock is held, and somewhere for a thread to wait. Rust’s std::sync::Mutex on Linux uses one AtomicU32 with three states: 0 for unlocked, 1 for locked, 2 for locked with threads possibly asleep. The Mutex<T> keeps the protected T right beside that word, so a small T shares a cache line with it.

The fast path touches only the word. Locking is a compare_exchange from 0 to 1 with Acquire ordering: one lock cmpxchg. Unlocking is a swap to 0 with Release ordering: one xchg. If the swap returns 2, someone may be asleep, and the unlocker wakes one. When nobody waits, neither side makes a system call. The Acquire on lock and the Release on unlock are what make the writes inside one critical section visible inside the next: a mutex is a Release/Acquire pair with a waiting room attached.

The waiting room: futex

A thread that finds the lock held could spin, reading the word until it changes. If the holder is about to release, a few hundred nanoseconds of spinning is the fastest possible wait. If the holder has been preempted, the spinner burns its own core for the whole of the holder’s absence, milliseconds, and its spinning may even be what keeps the holder off a core. Waiting longer than a moment needs the kernel, which can park a thread and wake it later.

The kernel’s mechanism is the futex, for fast user-space mutex: one system call with two main operations. FUTEX_WAIT(addr, expected) checks that the word at addr still equals expected and, if it does, puts the thread to sleep on a wait queue keyed by that address. The check and the sleep are atomic with respect to wakes, so a wake that lands between the thread’s last look at the word and its going to sleep is never lost. FUTEX_WAKE(addr, n) wakes up to n threads asleep on addr. The kernel keeps nothing at all for a futex that nobody waits on, which is why the uncontended path needs no system call, and is the fast in the name.

The standard mutex first tries the acquire CAS, spins briefly on failure, then marks the word contended and waits while it remains locked. Unlocking releases the word and wakes a waiter when the old state said one might be asleep. The Rust implementation shows the complete lost-wake handling.

A thread that wakes from futex_wait does not own the lock. It tries again, and it can lose again.

What it costs

Uncontended, a lock and an unlock are two locked instructions: about 10 ns back to back on one core, and 20–40 ns in real code, where each must first drain the stores ahead of it. If the last thread to hold the lock ran on another core, add the line’s transfer, 50–100 ns, plus a transfer for each line the critical section touches that the other thread wrote. Two cores that share a mutex pay those transfers even if they never collide in time.

Contended, the cost depends on how long the holder keeps the lock. If it releases during the spin, the wait is a few hundred nanoseconds to a microsecond. If it does not, the waiter sleeps. The unlocker then pays a futex_wake system call, about 1 µs, on its own critical path, and the waiter runs again 5–20 µs later if its core is awake and 100–200 µs later if its core went into a deep sleep state. If the holder was preempted, every waiter waits out its time slice: 1–4 ms.

Once threads start to sleep, a lock can form a convoy. Every hand-over to a sleeper costs a wake-up, during which the lock does no useful work. If acquisitions arrive faster than one per wake-up, the queue never drains. Throughput falls to one acquisition per wake-up, 50,000–200,000 a second, for a critical section that takes 50 ns, and stays there until arrivals slow down. Rust’s standard mutex is not fair. A thread that is already running can take a just-released lock before the woken sleeper gets to it, which is called barging. Barging keeps throughput up and leaves a waiter’s wait unbounded: the woken thread finds the lock taken, sleeps again, and can lose again. A fair lock forms convoys; an unfair one grows a tail.

Priorities add a further failure. A scheduler’s real-time classes rank threads so that a higher-priority thread always runs ahead of a lower one on the same core. Suppose a low-priority thread L holds the lock, a high-priority thread H blocks on it, and a medium-priority thread M, which wants no lock at all, becomes runnable on L’s core. M preempts L, and H now waits for M, a thread it outranks, for as long as M runs. This is priority inversion; it repeatedly reset the Mars Pathfinder lander in 1997. The kernel’s mechanism for it is priority inheritance: FUTEX_LOCK_PI futexes, which pthread uses for mutexes created with PTHREAD_PRIO_INHERIT, lend H’s priority to L for as long as H waits. Rust’s standard Mutex does not use them. Without real-time classes, the same shape appears whenever anything preempts the holder.

A reader-writer lock, RwLock, lets many readers hold it at once, or one writer alone. Read-mostly data looks like its ideal case. But taking a read lock is an RMW on the shared state word, which is a write. Readers on different cores therefore bounce that line between them, each read lock paying 50–100 ns when the last reader ran elsewhere, even though no reader ever waits for another.

Worked example: a Mutex<VecDeque> between two threads

A feed thread on core 2 decodes messages and pushes each into a Mutex<VecDeque<Msg>>. A strategy thread on core 4 runs a loop that locks it, pops whatever is there, and unlocks. A burst brings 500,000 messages a second, one every 2 µs.

In the quiet case, each push finds the lock word and the deque’s header in the strategy’s cache, because the strategy has just polled: a transfer for the lock line, a transfer for the slot the message goes into, and the pop pays the same in the other direction. From push to pop that is about 150–300 ns, and it is the histogram’s p50.

The strategy polls without pause, so it holds the lock for a good part of every microsecond, and many pushes find it held. Nearly all of those resolve in the spin, within a few hundred nanoseconds, and set the p99 at about 1 µs. A few times a second a timer tick or an interrupt lands on core 4 while the strategy holds the lock, for 1–5 µs. The feed thread spins its hundred rounds and goes to sleep. The strategy then pays a futex_wake on unlock, and the feed thread wakes 5–20 µs later, while the next 3–10 messages wait in the socket behind it: the p99.9 is tens of microseconds. If the strategy is preempted while holding the lock, the feed waits out the slice, and the max is milliseconds. So: p50 about 0.2 µs, p99 about 1 µs, p99.9 in the tens of microseconds, max in milliseconds. The p50 says the lock is cheap. The tail is a queue that nobody designed. Its order is the kernel’s wait queue plus whoever barges in, its service time is the wake-up latency, and its length is however many messages arrive while a thread sleeps.

Seeing it

A mutex’s spinning slow path may still avoid the kernel. Visits that park or wake a waiter make futex calls, so strace -f -e trace=futex -c ./binary, or perf trace -s -e futex with far less overhead, counts them: a lock nobody contends shows none, and the Mutex<VecDeque> above shows a wait and a wake for every time the feed thread slept. perf lock contention -b observes instrumented kernel locks, not arbitrary Rust user-space mutexes. For the latter, trace futex calls and measure waits around the lock; correlate those with scheduling events. voluntary_ctxt_switches in /proc/<pid>/task/<tid>/status counts the times a thread gave up its core, and on a thread whose only reason to sleep is a lock, each one is a wake-up paid, 5–200 µs on the ladder. The tail is the wait queue, and its length is set by whoever else wants the lock.