How a Mutex Works: the Futex

The idea: a word in user memory, a wait list in the kernel

A Linux mutex (pthread_mutex_t, std::mutex) is built on a futex, a "fast user-space mutex". The futex is nothing but an ordinary int in the program's memory, here called m. Locking and unlocking are atomic instructions on that int. The kernel is only asked for help when a thread must sleep or wake someone, and then it is handed the address of the int, nothing else.

The canvas shows exactly these parts: three threads, the lock word m at 0x7f3a1c40, the code line each thread is running, the kernel's futex hash table with its four buckets, and a counter of futex system calls. Pick a thread, press lock() or unlock(), or run a demo. Mutex with a Futex shows the same lock tick by tick with CPU timelines; this page looks at what the lock word means and what the kernel does with the address.

Three values, not two

The algorithm is the second mutex in Ulrich Drepper's paper Futexes Are Tricky; glibc's mutex works the same way. The word has three values:

m	Meaning	Unlock must…
0	unlocked	—
1	locked, nobody waits	just write 0
2	locked, someone may be asleep	write 0 and call FUTEX_WAKE

lock():   if (cmpxchg(&m, 0, 1) == 0) return;          // fast path
          while (xchg(&m, 2) != 0)
              futex(&m, FUTEX_WAIT, 2);               // sleep only if m is still 2
unlock(): if (xchg(&m, 0) == 2)
              futex(&m, FUTEX_WAKE, 1);               // wake one waiter

cmpxchg(&m, 0, 1) is a compare-and-swap: it writes 1 only if m is 0 and returns the old value. xchg writes and returns the old value in one step. When nobody else wants the mutex, lock is one cmpxchg and unlock is one xchg that returns 1: 0 system calls (Demo: uncontended lock and unlock).

Why not just 0 and 1? Then the unlocker cannot tell whether anyone is asleep, so it has to call FUTEX_WAKE every time, just in case. In Demo: 2-state word, every unlock is a syscall T1 and T2 lock and unlock one after the other with no contention at all, and still make 2 system calls that wake nobody; the 3-state word makes 0. A system call costs hundreds of nanoseconds, an uncontended xchg a few, so this is the whole point of the third state.

A waiter writes 2 with xchg before it sleeps, so the owner will see 2 when it unlocks. The thread that is woken also takes the lock with xchg(&m, 2), not with 1: it cannot know whether other threads are still asleep, so it must assume they are. The price is one extra FUTEX_WAKE that may find nobody (Demo: two threads contend: 1 FUTEX_WAIT, 2 FUTEX_WAKE, the second one wakes nobody).

What FUTEX_WAIT does in the kernel

The kernel keeps no object per mutex; a mutex nobody waits on costs it nothing. When a thread calls futex(&m, FUTEX_WAIT, 2):

1. It turns the address into a key. For a private futex (one process, the glibc default) the key is the process's memory map (mm) plus the virtual address; for a futex in shared memory it is the underlying page plus the offset, so two processes find the same queue.
2. It hashes the key into one bucket of a global futex hash table (the canvas has 4 buckets; Linux sizes it at 256 per CPU, and recent kernels can give a process its own table). Unrelated futexes can land in the same bucket: on the canvas T7 already waits in bucket 2 for another futex at 0x7f3a2080.
3. It takes the bucket's spinlock and reads m again. If m is still 2, it adds a futex_q for the thread (holding the key) to the end of the bucket's list, releases the lock and puts the thread to sleep. If m is not 2, it returns at once with EAGAIN.

The lost wake-up, and why the value check stops it

There is a gap between a waiter's xchg(&m, 2) in user space and its arrival in the kernel. If the owner unlocks in that gap, its FUTEX_WAKE finds an empty list (the waiter is not queued yet) and returns 0. If the waiter then went to sleep anyway, nobody would ever wake it: the mutex is free, but the thread sleeps forever.

The value argument closes that gap. FUTEX_WAIT(&m, 2) means "sleep, but only if m is still 2", and the kernel checks it while holding the bucket's spinlock, the same lock that FUTEX_WAKE takes. So either the check happens first (the waiter is queued and the wake finds it) or the unlock happens first (the check sees 0 and returns EAGAIN). In Demo: lost wake-up race, EAGAIN T2 never sleeps: 1 FUTEX_WAIT that returns EAGAIN, and 2 FUTEX_WAKE calls that find nobody.

FUTEX_WAKE: wake one, not all

futex(&m, FUTEX_WAKE, 1) hashes the same key to the same bucket, takes its lock and walks the list. Entries with another key (T7) are skipped. The first match is unlinked and its thread made runnable; the call returns how many it woke (0 or 1). The list keeps arrival order among threads of the same priority, so the oldest waiter goes first.

The woken thread is not handed the mutex. It returns from FUTEX_WAIT, goes round the loop and runs xchg(&m, 2) again; if a newcomer got there first, it sleeps again. In Demo: three threads, wake one T2 and T3 both sleep in bucket 2. T1's unlock wakes only T2, and T3 keeps sleeping until T2 unlocks: 2 FUTEX_WAIT, 3 FUTEX_WAKE, 5 system calls for three critical sections.

Waking every waiter (FUTEX_WAKE with INT_MAX) would be a thundering herd: all of them wake, one wins the xchg, and the rest pay a context switch only to call FUTEX_WAIT again. Condition variables, which really do have to release many waiters at once, avoid the herd with FUTEX_REQUEUE, which moves waiters from the condition variable's futex to the mutex's futex without waking them.

Demo	FUTEX_WAIT (EAGAIN)	FUTEX_WAKE (woke nobody)	System calls
Uncontended lock and unlock	0	0	0
Two threads contend	1 (0)	2 (1)	3
Three threads, wake one	2 (0)	3 (1)	5
Lost wake-up race	1 (1)	2 (2)	3
2-state word, no contention	0	2 (2)	2

Where you meet it

• C and C++ on Linux: pthread_mutex_lock, std::mutex, condition variables, semaphores and pthread_join all end in futex() when they have to wait.
• Java: a contended synchronized block or ReentrantLock parks the thread, and on Linux the JVM parks it on a futex. Go parks goroutines in its own runtime and uses futexes only to put idle OS threads to sleep.
• strace -f -e futex ./program shows each FUTEX_WAIT_PRIVATE and FUTEX_WAKE_PRIVATE call, including the EAGAIN results.

See also Mutex vs Spinlock for what a sleep and a wake cost against spinning, and A Linux System Call, Step by Step for what crossing the boundary involves.

What the page leaves out

• Barging: a woken thread competes with newcomers. The page runs the woken thread at once, so it always wins.
• Spurious wake-ups and signals: FUTEX_WAIT can also return early (EINTR, a timeout), which is why it always sits in a loop.
• Adaptive spinning before the system call (PTHREAD_MUTEX_ADAPTIVE_NP), shown on Mutex vs Spinlock.
• Priority-inheritance futexes (FUTEX_LOCK_PI, the owner's thread id in the word), robust futexes for owners that die, and the newer futex_waitv that waits on several futexes.
• The real hash function (jhash), the table size, and the bucket's waiter count that lets FUTEX_WAKE skip the lock when a bucket is empty.

References

Ulrich Drepper, Futexes Are Tricky

futex(2), Linux manual page

Linux kernel source: kernel/futex/waitwake.c

LWN: A futex overview and update