POSIX Threads and Linux Synchronization: The Magic of Futex

In previous chapters of the Systems I/O series, we explored how a process is loaded into memory, how it executes instructions, and how it is fundamentally isolated from other processes by the operating system.

But what if we want to share memory? What if we need multiple streams of execution working simultaneously on the same data? This is where threads come in.

A thread is the smallest unit of execution managed by the operating system scheduler. Unlike separate processes, multiple threads belonging to the same process share the same virtual address space. They can read and write to the same global variables and the same heap.

In this guide, I will walk you through how we create threads using the POSIX Threads (pthreads) API, and more importantly, how Linux efficiently synchronizes their access to shared memory using one of its most brilliant inventions: the futex.

Creating a Thread

On Linux, the standard way to create threads in C is using the pthreads library. Let’s look at a basic example of spawning a thread.

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

// The function that our new thread will execute
void* worker_thread(void* arg) {
  int id = *((int*)arg);
  printf("Hello from worker thread %d!
", id);
  return NULL;
}

int main() {
  pthread_t thread;
  int thread_arg = 1;

  printf("Main thread: Creating worker...
");
  
  // Spawn the thread
  // Note: Passing a pointer to a local variable (&thread_arg) is safe here 
  // only because we immediately pthread_join(). If you were spawning multiple 
  // threads in a loop, this would be a classic dangling pointer bug!
  if (pthread_create(&thread, NULL, worker_thread, &thread_arg) != 0) {
      perror("Failed to create thread");
      return 1;
  }

  // Wait for the worker to finish
  pthread_join(thread, NULL);
  printf("Main thread: Worker finished.
");
  
  return 0;
}

When we call pthread_create, the library sets up a new stack for the thread and then invokes the clone system call under the hood. Unlike fork, which creates a completely independent process, clone with flags like CLONE_VM, CLONE_FILES, CLONE_THREAD, and CLONE_CHILD_CLEARTID tells the Linux kernel to create a new execution context that shares memory and file descriptors with the parent. In fact, CLONE_THREAD is what makes it a thread (putting it in the same thread group), and CLONE_CHILD_CLEARTID allows pthread_join to work by futex-waking the caller when the thread exits.

But shared memory introduces a massive problem: Data Races. If two threads try to modify the same variable at the same time, the result is undefined. To prevent this, we need synchronization primitives like a Mutex (Mutual Exclusion).

The Synchronization Dilemma

Before the invention of the futex, implementing a mutex was a trade-off between wasting CPU cycles and wasting time transitioning to the kernel.

Approach 1: Spinlocks (Wasting CPU)

We could use atomic instructions to check if a lock is available. If it isn’t, the thread just loops (while(locked) {}) until it is. This is called a spinlock. It’s incredibly fast to acquire, but if the lock is held for a long time by another thread, the spinning thread burns CPU cycles doing absolutely nothing.

Approach 2: Heavyweight Kernel Locks (Wasting Time)

To avoid burning CPU cycles, we could ask the kernel to put our thread to sleep if the lock is taken. The kernel would wake our thread up when the lock is released. The problem? This requires a system call (syscall) for every lock and unlock operation. System calls are slow. They require a mode switch (a privilege-level transition) from User Mode to Kernel Mode.

What if a lock is uncontested? What if a thread tries to grab a lock, and no one else is currently holding it? Making a system call in this scenario is a massive performance penalty for an operation that should have been instantaneous.

Enter the Futex

In 2002, Linux 2.5.7 introduced the Fast Userspace Mutex, or futex (though the interface was reworked several times before settling). The philosophy behind the futex is simple and elegant:

1. The Fast Path (Userspace): In the uncontested case, acquiring and releasing a lock should happen entirely in userspace using atomic CPU instructions. No system calls. No kernel transitions.
2. The Slow Path (Kernel): Only if the lock is currently held by someone else (contested), should we trap into the kernel to put the calling thread to sleep.

A futex is basically a 4-byte aligned 32-bit integer in userspace shared memory, paired with a wait queue managed by the kernel. The kernel keys on the physical page and offset, meaning the same futex can sit at different virtual addresses in different processes. Because there is no standard libc wrapper for futex operations, we must invoke syscall(SYS_futex, ...) directly. Additionally, for threads within the same process, we can use the FUTEX_PRIVATE_FLAG to tell the kernel it doesn’t need to support cross-process sharing, which is measurably faster.

Let’s implement a rudimentary mutex using atomics and the futex system call to see how this fast-path/slow-path logic actually works in C.

A Contested vs Uncontested Lock Implementation

To build our own mutex, we need an atomic integer to represent the lock state:

• 0: Unlocked
• 1: Locked (uncontested)
• 2: Locked (contested - threads are sleeping and need to be woken up)

#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <stdatomic.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <linux/futex.h>
#include <sys/time.h>
#include <pthread.h>

// A simple futex wrapper
// Note: futex_wait can return EAGAIN (if the value changed before the kernel could sleep) 
// or EINTR (spurious wake from a signal). The surrounding loop re-checks the state, 
// which is what makes ignoring those return values safe here.
static int futex_wait(atomic_int *uaddr, int val) {
  return syscall(SYS_futex, uaddr, FUTEX_WAIT | FUTEX_PRIVATE_FLAG, val, NULL, NULL, 0);
}

static int futex_wake(atomic_int *uaddr, int val) {
  return syscall(SYS_futex, uaddr, FUTEX_WAKE | FUTEX_PRIVATE_FLAG, val, NULL, NULL, 0);
}

// Our Custom Mutex
typedef struct {
  atomic_int state; // 0 = Unlocked, 1 = Locked, 2 = Contested
} my_mutex_t;

void my_mutex_init(my_mutex_t *m) {
  atomic_init(&m->state, 0);
}

void my_mutex_lock(my_mutex_t *m) {
  int expected = 0;
  
  // FAST PATH: Try to change state from 0 to 1 atomically.
  // If successful, the lock was uncontested. We own it now. No syscall!
  if (atomic_compare_exchange_strong(&m->state, &expected, 1)) {
      return; 
  }

  // SLOW PATH: The lock is contested.
  // If the state is 1 (Locked), we must mark it as 2 (Contested) so the 
  // owner knows to wake us up later.
  if (expected == 1) {
      expected = atomic_exchange(&m->state, 2);
  }

  // Now, wait in the kernel until the state changes.
  while (expected != 0) {
      // Sleep in the kernel only if state is still 2.
      futex_wait(&m->state, 2);
      
      // We woke up! Try to grab the lock and set it to contested again.
      expected = atomic_exchange(&m->state, 2);
  }
}

void my_mutex_unlock(my_mutex_t *m) {
  // FAST PATH: Try to release the lock by changing state from 1 to 0.
  // If it was 1, it was uncontested, and no one is waiting. No syscall!
  // Note: if state was 2, it briefly becomes 1 here. A new arrival will mark it 2 again,
  // and the futex_wake below still reaches it.
  if (atomic_fetch_sub(&m->state, 1) == 1) {
      return; 
  }

  // SLOW PATH: The state was 2 (Contested). 
  // We must release the lock and wake up one waiting thread.
  atomic_store(&m->state, 0);
  futex_wake(&m->state, 1); // Syscall to wake 1 sleeping thread
}

How the Magic Works

Let’s trace what happens when we use this custom mutex:

Scenario 1: Uncontested (The Fast Path)

Thread A calls my_mutex_lock. The state is 0. The atomic_compare_exchange_strong instantly swaps it to 1 with a single atomic instruction — on x86-64 a lock cmpxchg, on the order of tens of cycles when the cache line is already local, versus hundreds when it is contended between cores. Fast, but not free: the point is that it never leaves userspace. The function returns immediately.

When Thread A calls my_mutex_unlock, atomic_fetch_sub decrements the state from 1 to 0. It returns 1, so the function exits.

Total system calls: 0. Maximum performance.

Scenario 2: Contested (The Slow Path)

Thread A holds the lock (state is 1).

Thread B calls my_mutex_lock. The fast path fails because the state isn’t 0. Thread B executes the slow path, atomically setting the state to 2 (contested) and then calls futex_wait. Now, Thread B traps into the Linux kernel and is put to sleep.

Later, Thread A calls my_mutex_unlock. It decrements the state, but since the state was 2, atomic_fetch_sub returns 2. The fast path fails. Thread A realizes there are sleeping threads, sets the state to 0, and calls futex_wake. The kernel wakes up Thread B, which then grabs the lock.

Summary

This is the core of how glibc implements the default pthread_mutex_t you use every day in C under the hood.

By optimizing for the common case (uncontested locks) entirely in userspace using atomic instructions, and falling back to the kernel only when absolutely necessary, Linux ensures that multi-threaded programs run as fast as the hardware allows. This represents a fundamental systems programming principle: optimize the fast path, gracefully handle the slow path.

[!CAUTION] As an educational warning: this hand-rolled mutex is textbook-correct, but the optimizer can undermine the code around it. If you compile this mutex alongside a worker loop in the same translation unit, gcc 13 at -O2 can hoist the load of a shared non-atomic variable out of the loop, across the non-inlined lock and unlock calls, despite the memory barriers inside them. The lock still serializes the critical section correctly — what breaks is the data it protects: every iteration stores a value computed from a stale pre-loop load, so other threads’ updates are silently lost. The trap is that it is not universal — gcc -O3 and -Os, and clang at every level, are unaffected — so a quick “let me verify this” can easily come up clean. Moving the mutex into its own .c file, or declaring the protected data _Atomic, fixes it; note that pthread_mutex_t is safe partly because it lives in a separately compiled library. That is a concrete illustration of why you should always reach for pthread_mutex_t or std::mutex in production instead of rolling your own.