Futex: fast locks in the Linux kernel

In short: A futex (“fast userspace mutex”) is the Linux building block that lets locks work mostly without any kernel call and involves the kernel only on contention.

In more detail: A lock is a number in memory. If it is free, a thread takes it with an atomic operation without asking the kernel. Only when it is taken does the thread go to sleep via the futex() system call.

In Depth

• Fast path: Atomic compare-and-swap in user space, a few nanoseconds.
• Slow path: FUTEX_WAIT sleeps until the value changes, FUTEX_WAKE wakes waiters.
• Users: pthread mutexes, semaphores and condition variables in glibc build on it.
• Advantage: Uncontended locks (the normal case) cost almost nothing.
• Pitfalls: Spurious wake-ups, priority inversion (priority inheritance addresses it) and fairness.
• Observing: strace shows many futex calls when a program suffers from lock contention. See strace.

See also: Semaphore