Futexes

Every shared-memory program eventually needs a mutex — a way to ensure that only one thread touches a critical section at a time. For decades the obvious tool was a kernel object: you called the OS to lock, and called it again to unlock. Every lock acquisition paid a round-trip through the kernel, even when no other thread was competing.

In 2002, Hubertus Franke, Matthew Kirkwood, Ingo Molnar and Rusty Russell introduced futexes (Fast Userspace muTEXes) in Linux. The key insight: when a lock is uncontended, you don't need the kernel at all. A single atomic compare-and-swap in userspace is enough to acquire it. The kernel only enters the picture when a thread must actually wait for a lock held by someone else.

That asymmetry — a handful of nanoseconds in the common case versus a syscall only when there is genuine contention — is why every modern threading library (pthreads, Java, Go, Rust's std::sync) is built on futexes under the hood.

The demo below simulates the two paths a futex takes. Add threads and watch what happens: an uncontended acquire completes in userspace with one atomic op; only when threads collide does the simulation show a kernel WAIT syscall parking the loser.

<!-- {{c_html_comment}} -->
<div class="controls">
  <label for="thread-count">{{label_threads}}</label>
  <input id="thread-count" type="range" min="1" max="8" value="1" />
  <span id="thread-val">1</span>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div class="stats-row">
  <div class="stat-box">
    <div class="stat-label">{{label_kernel_calls}}</div>
    <div class="stat-value" id="kernel-calls">0</div>
  </div>
  <div class="stat-box">
    <div class="stat-label">{{label_userspace_acquires}}</div>
    <div class="stat-value" id="userspace-acquires">0</div>
  </div>
  <div class="stat-box">
    <div class="stat-label">{{label_total_acquires}}</div>
    <div class="stat-value" id="total-acquires">0</div>
  </div>
</div>
<div class="lane-area" id="lane-area"></div>
<div class="log" id="log"></div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .8rem; }
label { font-size: .85rem; font-weight: 600; }
input[type=range] { width: 120px; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats-row { display: flex; gap: .7rem; margin-bottom: .8rem; flex-wrap: wrap; }
.stat-box { background: #f0f4f8; border-radius: 8px; padding: .4rem .8rem; min-width: 100px; }
.stat-label { font-size: .72rem; color: #556; text-transform: uppercase; letter-spacing: .03em; }
.stat-value { font-size: 1.5rem; font-weight: 700; color: #1d3557; }
.lane-area { display: flex; flex-direction: column; gap: 6px; margin-bottom: .8rem; }
.lane { display: flex; align-items: center; gap: 8px; font-size: .82rem; }
.lane-label { width: 64px; font-weight: 600; color: #334; }
.track { flex: 1; height: 20px; background: #e2e8f0; border-radius: 10px; position: relative; overflow: hidden; }
.fill { height: 100%; border-radius: 10px; width: 0; transition: width .3s; }
.fill.fast { background: #2ecc71; }
.fill.slow { background: #e67e22; }
.badge { font-size: .7rem; font-weight: 700; color: #fff; padding: 1px 6px; border-radius: 8px; margin-left: 4px; }
.badge.kernel { background: #e74c3c; }
.badge.user { background: #27ae60; }
.log { font: .78rem ui-monospace, monospace; color: #334; max-height: 110px; overflow-y: auto;
       background: #f8f9fa; border-radius: 6px; padding: .4rem .6rem; line-height: 1.6; }
.log .kline { color: #c0392b; }
.log .uline { color: #27ae60; }

// Code not found

Notice the kernel calls counter. In the uncontended case it stays at zero — the lock is acquired and released entirely in userspace. Add more threads and contention rises: the kernel must now park waiting threads and wake them up, at a cost visible in the call count. The fast path is the whole point of the design.

A futex is surprisingly simple at the protocol level:

• A shared 32-bit word lives in memory accessible to all threads (or processes). Its value encodes lock state — typically 0 = free, non-zero = held.
• Fast path (uncontended): lock() executes an atomic compare-and-swap (CAS): if the word is 0, swap it to 1 and return. No syscall. Cost: a single memory barrier, a few nanoseconds. unlock() atomically writes 0 back; if no waiters are recorded, it also returns without a syscall.
• Slow path (contended): if the CAS fails (someone else holds the lock), the thread calls FUTEX_WAIT(addr, expected). The kernel checks the word at addr — if it still matches expected, the thread is parked in a per-address queue; otherwise the syscall returns immediately (the lock became free in the race). Cost: one kernel round-trip.
• Wake path: when the lock is released and waiters exist, the holder calls FUTEX_WAKE(addr, n) to wake up to $n$ parked threads. The kernel dequeues them and schedules them.

The elegance is in the double check inside the kernel: the word is re-read after the thread enters kernel mode, preventing the race where the lock is released between the failed CAS and the kernel park. This is why Drepper and Molnar's paper (2011) is titled Futexes Are Tricky — the corner cases around this window are subtle but the core protocol is correct.

Compared to a pure kernel mutex the saving is enormous: on a lightly loaded server a futex lock/unlock pair costs roughly 20–40 ns; a traditional kernel mutex costs 500–2000 ns per acquisition. Because most production locks are uncontended most of the time, that difference multiplies across every synchronization point in the program.

See also: P vs NP to understand why some problems have no equally clever shortcut, and halting problem for another boundary between what can be decided quickly and what cannot.

Futexes are the invisible foundation of concurrency on Linux and Android:

• pthreads (pthread_mutex_t): the GNU C Library's mutex, rwlock and condition variable are all futex-based. Every C and C++ program using POSIX threads benefits automatically.
• Java monitors: the JVM maps synchronized and java.util.concurrent locks to futexes on Linux via park/unpark.
• Go runtime: goroutine scheduling uses futexes for the sync.Mutex fast path and for parking goroutines on channel operations.
• Rust std::sync::Mutex: on Linux/Android delegates to parking_lot, which uses futexes directly for sub-microsecond uncontended acquisition.
• Databases and servers: high-throughput databases (PostgreSQL, MySQL, Redis) rely on futex-based latches protecting buffer pool pages. A futex outperforms a spinlock under load without burning a CPU core while waiting.
• Android: the Android Bionic libc ships its own futex wrappers and uses them for the pthread and ART runtime locks throughout the OS.

Anywhere latency matters and locks are mostly uncontended — which is most of the time — futexes quietly keep the kernel out of the critical path.

A futex is one of the cleanest examples of algorithm-meets-systems thinking: by recognizing that uncontended locking is the common case, the designers pushed it entirely into userspace. The kernel's power is reserved for the rare moment when a thread truly has no choice but to wait.

The result is a primitive so efficient that every major language runtime on Linux quietly wraps it. The lock you write in Java, Go, Rust, or C++ almost certainly touches a futex word before anything else — and in the happy path it never goes further. One atomic operation, zero syscalls, millions of times per second.

The lesson generalizes: when the slow path is rare, optimizing the fast path to near zero can transform a bottleneck into a rounding error. That instinct — find the common case and make it free — is the same one behind P vs NP research: understanding why some paths are hard helps us build systems that almost always take the easy one.