Introduction

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.

Try the Lock

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.

<!-- Futex simulator — shows fast (userspace) vs slow (kernel) lock acquisition paths -->
<div class="controls">
  <label for="thread-count">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">Run simulation</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<div class="stats-row">
  <div class="stat-box">
    <div class="stat-label">Kernel calls</div>
    <div class="stat-value" id="kernel-calls">0</div>
  </div>
  <div class="stat-box">
    <div class="stat-label">Userspace acquires</div>
    <div class="stat-value" id="userspace-acquires">0</div>
  </div>
  <div class="stat-box">
    <div class="stat-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>

/* Styles for the futex demo — lane bars, stat boxes, log */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Futex simulation: models the two acquisition paths of a fast userspace mutex.
// Fast path: atomic CAS in userspace — no syscall needed when lock is free.
// Slow path: FUTEX_WAIT syscall parks the thread when lock is held by another.

const LOCK_FREE = 0;
const LOCK_HELD = 1;
const LOCK_CONTENDED = 2; // lock held with waiters queued

const ITERATIONS = 12; // lock acquisitions per thread in this simulation

let kernelCalls = 0;
let userAcquires = 0;
let totalAcquires = 0;
let running = false;

function updateStats() {
  document.getElementById('kernel-calls').textContent = kernelCalls;
  document.getElementById('userspace-acquires').textContent = userAcquires;
  document.getElementById('total-acquires').textContent = totalAcquires;
}

function addLog(msg, cls) {
  const log = document.getElementById('log');
  const d = document.createElement('div');
  d.className = cls || '';
  d.textContent = msg;
  log.appendChild(d);
  log.scrollTop = log.scrollHeight;
}

function resetUI() {
  kernelCalls = 0; userAcquires = 0; totalAcquires = 0;
  running = false;
  updateStats();
  document.getElementById('log').innerHTML = '';
  document.getElementById('lane-area').innerHTML = '';
  document.getElementById('btn-run').disabled = false;
}

// Run a step-by-step simulation of nThreads competing for one futex lock.
function simulateFutex(nThreads) {
  if (running) return;
  running = true;
  kernelCalls = 0; userAcquires = 0; totalAcquires = 0;
  updateStats();
  document.getElementById('log').innerHTML = '';
  document.getElementById('btn-run').disabled = true;

  const laneArea = document.getElementById('lane-area');
  laneArea.innerHTML = '';

  // Shared 32-bit lock word: 0=free, 1=held, 2=contended.
  let lockWord = LOCK_FREE;
  const lanes = [];

  for (let i = 0; i < nThreads; i++) {
    const lane = document.createElement('div');
    lane.className = 'lane';
    lane.innerHTML = `<div class="lane-label">Thread ${i + 1}</div>
      <div class="track"><div class="fill" id="fill-${i}"></div></div>
      <span class="badge" id="badge-${i}"></span>`;
    laneArea.appendChild(lane);
    lanes.push({ fill: document.getElementById('fill-' + i), badge: document.getElementById('badge-' + i) });
  }

  // Simulated kernel wait queue (parked thread IDs)
  let waitQueue = [];
  let step = 0;
  const totalSteps = nThreads * ITERATIONS;

  // Advance one acquisition step; alternate between threads round-robin.
  function tick() {
    if (step >= totalSteps) {
      running = false;
      document.getElementById('btn-run').disabled = false;
      addLog('Simulation complete.');
      return;
    }

    const tid = step % nThreads;
    const progress = Math.round(((step + 1) / totalSteps) * 100);
    const fill = lanes[tid].fill;
    const badge = lanes[tid].badge;
    fill.style.width = progress + '%';

    // Simulate CAS: if lock is free, acquire in userspace (fast path).
    if (lockWord === LOCK_FREE) {
      // Fast path acquired — no kernel call needed.
      lockWord = LOCK_HELD;
      userAcquires++;
      totalAcquires++;
      fill.className = 'fill fast';
      badge.className = 'badge user';
      badge.textContent = 'USER';
      addLog(i18nFmt('Thread %tid%: CAS succeeded → acquired in userspace (no syscall).', { tid: tid + 1 }), 'uline');

      // Release: if waiters exist, call FUTEX_WAKE (kernel); otherwise just write 0 back.
      if (waitQueue.length === 0) {
        lockWord = LOCK_FREE;
      } else {
        lockWord = LOCK_CONTENDED;
        kernelCalls++;
        updateStats();
        addLog(i18nFmt('Thread %tid%: released → FUTEX_WAKE woke thread %woken%.', { tid: tid + 1, woken: waitQueue.shift() + 1 }), 'kline');
        lockWord = LOCK_FREE;
      }
    } else {
      // Lock is held — slow path: call FUTEX_WAIT to park this thread in the kernel.
      lockWord = LOCK_CONTENDED;
      kernelCalls++;
      totalAcquires++;
      fill.className = 'fill slow';
      badge.className = 'badge kernel';
      badge.textContent = 'KERNEL';
      waitQueue.push(tid);
      addLog(i18nFmt('Thread %tid%: CAS failed → FUTEX_WAIT (kernel parked thread).', { tid: tid + 1 }), 'kline');
    }

    updateStats();
    step++;
    setTimeout(tick, 280);
  }
  tick();
}

document.getElementById('thread-count').addEventListener('input', function () {
  document.getElementById('thread-val').textContent = this.value;
});
document.getElementById('btn-run').addEventListener('click', function () {
  const n = parseInt(document.getElementById('thread-count').value, 10);
  simulateFutex(n);
});
document.getElementById('btn-reset').addEventListener('click', resetUI);
Result
Console

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.

The Real Complexity

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 nn 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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/futexes/Content licensed under CC BY-NC 4.0.