Eric Campbell 6 min read Engineering

Mutex: Mutual Exclusion Lock Implementation

Concurrent programming is hard because shared mutable state creates race conditions. When two threads read-modify-write the same variable simultaneously, the result depends on timing—and timing is...

Key Insights

  • A mutex is fundamentally a state machine with two states (locked/unlocked), but production implementations require careful handling of wait queues, memory ordering, and OS integration to avoid burning CPU cycles or causing priority inversion.
  • Spinlocks work well for short critical sections on multicore systems, but blocking mutexes with futex support are essential when contention is high or critical sections are long.
  • Most mutex bugs stem from forgetting to unlock, recursive locking without reentrant support, or holding locks across blocking operations—design your API to prevent these mistakes.

Introduction to Mutual Exclusion

Concurrent programming is hard because shared mutable state creates race conditions. When two threads read-modify-write the same variable simultaneously, the result depends on timing—and timing is non-deterministic.

A mutex (mutual exclusion lock) solves this by ensuring only one thread can access a critical section at a time. Thread A acquires the lock, does its work, and releases the lock. Thread B waits until the lock is available. Simple in concept, tricky in implementation.

The mutex is the most fundamental synchronization primitive. Semaphores, condition variables, and read-write locks all build on the same core idea. Understanding how mutexes work at the implementation level makes you a better systems programmer and helps you debug the inevitable concurrency issues in production.

Anatomy of a Mutex

A mutex needs three components:

  1. Lock state: Is the mutex currently held?
  2. Owner tracking: Which thread holds the lock? (Optional but useful for debugging and reentrant locks)
  3. Wait queue: Which threads are waiting to acquire the lock?

Here’s a minimal mutex structure in C:

#include <stdatomic.h>
#include <stdint.h>

typedef struct {
    atomic_int state;        // 0 = unlocked, 1 = locked
    atomic_int owner;        // Thread ID of current owner (0 if none)
    // Wait queue handled by OS in real implementations
} mutex_t;

#define MUTEX_INITIALIZER { .state = 0, .owner = 0 }

void mutex_init(mutex_t *m) {
    atomic_store(&m->state, 0);
    atomic_store(&m->owner, 0);
}

The invariants a mutex must maintain:

  • If state == 0, no thread holds the lock
  • If state == 1, exactly one thread holds the lock
  • A thread that didn’t acquire the lock cannot release it
  • After unlock, at least one waiting thread must be able to acquire the lock

The tricky part is implementing lock() and unlock() without race conditions—using atomic operations to coordinate the very thing that’s supposed to provide coordination.

Spinlock Implementation

The simplest mutex is a spinlock: try to acquire the lock in a loop until you succeed. No OS involvement, no sleeping—just atomic operations and patience.

#include <stdatomic.h>
#include <sched.h>

typedef struct {
    atomic_int locked;
} spinlock_t;

void spinlock_init(spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
}

void spinlock_lock(spinlock_t *lock) {
    while (1) {
        // Try to change state from 0 to 1
        int expected = 0;
        if (atomic_compare_exchange_weak(&lock->locked, &expected, 1)) {
            return; // Successfully acquired
        }
        
        // Spin-wait hint for CPU (reduces power, improves performance)
        #if defined(__x86_64__) || defined(__i386__)
            __asm__ volatile("pause" ::: "memory");
        #elif defined(__aarch64__)
            __asm__ volatile("yield" ::: "memory");
        #endif
    }
}

void spinlock_unlock(spinlock_t *lock) {
    atomic_store(&lock->locked, 0);
}

The atomic_compare_exchange_weak operation is the heart of the spinlock. It atomically checks if the value equals expected and, if so, replaces it with the new value. This is the classic test-and-set pattern.

When to use spinlocks:

  • Critical sections are very short (< 1 microsecond)
  • You’re on a multicore system (spinning on a single core is pointless)
  • You can’t afford the overhead of OS context switches
  • Kernel code where sleeping isn’t allowed

When to avoid spinlocks:

  • Critical sections might block (I/O, memory allocation)
  • High contention scenarios
  • Single-core systems
  • User-space code with unpredictable scheduling

Blocking Mutex with OS Support

Spinning wastes CPU cycles. For longer critical sections or high contention, you want the waiting thread to sleep and let other threads run. This requires OS support.

On Linux, the futex (fast userspace mutex) system call provides this. The key insight: only call into the kernel when there’s actual contention.

#include <linux/futex.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <stdatomic.h>

typedef struct {
    atomic_int state;  // 0 = unlocked, 1 = locked no waiters, 2 = locked with waiters
} futex_mutex_t;

static int futex_wait(atomic_int *addr, int expected) {
    return syscall(SYS_futex, addr, FUTEX_WAIT_PRIVATE, expected, NULL, NULL, 0);
}

static int futex_wake(atomic_int *addr, int count) {
    return syscall(SYS_futex, addr, FUTEX_WAKE_PRIVATE, count, NULL, NULL, 0);
}

void futex_mutex_lock(futex_mutex_t *m) {
    int state = atomic_exchange(&m->state, 1);
    
    if (state != 0) {
        // Lock was held, need to wait
        do {
            // Mark that there are waiters
            if (state == 2 || atomic_compare_exchange_strong(&m->state, &state, 2)) {
                // Sleep until woken (state might change, that's okay)
                futex_wait(&m->state, 2);
            }
            // Try to acquire again
            state = atomic_exchange(&m->state, 2);
        } while (state != 0);
    }
    // Lock acquired
}

void futex_mutex_unlock(futex_mutex_t *m) {
    if (atomic_fetch_sub(&m->state, 1) != 1) {
        // There were waiters (state was 2)
        atomic_store(&m->state, 0);
        futex_wake(&m->state, 1);  // Wake one waiter
    }
}

The three-state design is crucial for performance:

  • State 0: Unlocked. Lock acquisition is a single atomic operation.
  • State 1: Locked, no waiters. Unlock is a single atomic operation.
  • State 2: Locked with waiters. Unlock must wake a sleeping thread.

This means uncontended lock/unlock never touches the kernel—just fast userspace atomics.

Handling Edge Cases

Reentrant Mutexes

A reentrant (recursive) mutex allows the same thread to acquire the lock multiple times. This prevents deadlock when a function that holds a lock calls another function that needs the same lock.

#include <stdatomic.h>
#include <pthread.h>

typedef struct {
    atomic_int state;
    atomic_ulong owner;      // Thread ID of owner
    int recursion_count;     // How many times owner has locked
} reentrant_mutex_t;

void reentrant_mutex_lock(reentrant_mutex_t *m) {
    unsigned long self = (unsigned long)pthread_self();
    
    // Check if we already own the lock
    if (atomic_load(&m->owner) == self) {
        m->recursion_count++;
        return;
    }
    
    // Standard lock acquisition (simplified, use futex in practice)
    while (1) {
        int expected = 0;
        if (atomic_compare_exchange_weak(&m->state, &expected, 1)) {
            atomic_store(&m->owner, self);
            m->recursion_count = 1;
            return;
        }
        // Spin or sleep here
    }
}

void reentrant_mutex_unlock(reentrant_mutex_t *m) {
    unsigned long self = (unsigned long)pthread_self();
    
    if (atomic_load(&m->owner) != self) {
        // Error: unlocking mutex we don't own
        return;
    }
    
    if (--m->recursion_count == 0) {
        atomic_store(&m->owner, 0);
        atomic_store(&m->state, 0);
        // Wake waiters if using futex
    }
}

Opinion: Avoid reentrant mutexes when possible. They often mask design problems—if you need reentrant locking, consider whether your function should be split into a locked and unlocked version.

Timeout Acquisition

Sometimes you can’t wait forever. A try_lock with timeout prevents deadlocks and enables responsive systems:

#include <time.h>
#include <errno.h>

int futex_mutex_trylock_timeout(futex_mutex_t *m, int timeout_ms) {
    struct timespec ts = {
        .tv_sec = timeout_ms / 1000,
        .tv_nsec = (timeout_ms % 1000) * 1000000
    };
    
    int state = atomic_exchange(&m->state, 1);
    if (state == 0) return 0;  // Got it immediately
    
    struct timespec deadline;
    clock_gettime(CLOCK_MONOTONIC, &deadline);
    deadline.tv_sec += ts.tv_sec;
    deadline.tv_nsec += ts.tv_nsec;
    
    do {
        if (state == 2 || atomic_compare_exchange_strong(&m->state, &state, 2)) {
            int ret = syscall(SYS_futex, &m->state, 
                            FUTEX_WAIT_PRIVATE, 2, &ts, NULL, 0);
            if (ret == -1 && errno == ETIMEDOUT) {
                return -1;  // Timeout
            }
        }
        state = atomic_exchange(&m->state, 2);
    } while (state != 0);
    
    return 0;  // Acquired
}

Performance Considerations

Cache Line Contention

When multiple cores spin on the same memory location, they fight over the cache line. Each write invalidates other cores’ caches, causing a “cache line ping-pong” that destroys performance.

Mitigation strategies:

  • Backoff: After a failed acquisition, wait before retrying
  • MCS locks: Each thread spins on its own cache line
  • Padding: Ensure the mutex doesn’t share a cache line with other data

Adaptive Spinning

Modern mutex implementations combine spinning and sleeping. Spin briefly in case the lock holder is about to release, then sleep if contention persists.

#define SPIN_COUNT 100

void adaptive_mutex_lock(futex_mutex_t *m) {
    // Try spinning first
    for (int i = 0; i < SPIN_COUNT; i++) {
        int expected = 0;
        if (atomic_compare_exchange_weak(&m->state, &expected, 1)) {
            return;  // Got it while spinning
        }
        __asm__ volatile("pause" ::: "memory");
    }
    
    // Fall back to blocking
    futex_mutex_lock(m);
}

Conclusion

Mutexes are the workhorse of concurrent programming. Use them when:

  • You need exclusive access to shared mutable state
  • The critical section is short and well-defined
  • You can guarantee lock/unlock pairing

Consider alternatives when:

  • Multiple readers, rare writers → use read-write locks
  • Producer-consumer patterns → use channels or queues
  • Simple counters → use atomics directly
  • No shared state needed → restructure to avoid sharing

Best practices for production code:

  1. Always use RAII or defer patterns to ensure unlock happens
  2. Keep critical sections short—don’t do I/O while holding a lock
  3. Document lock ordering to prevent deadlocks
  4. Use lock-free data structures for hot paths when profiling shows contention
  5. Prefer standard library implementations (pthread_mutex_t, std::mutex) over rolling your own

Understanding mutex internals helps you debug contention issues, choose the right synchronization primitive, and appreciate why your language’s standard mutex works the way it does. But in production, use the battle-tested implementations—they handle edge cases you haven’t thought of yet.

Liked this? There's more.

Every week: one practical technique, explained simply, with code you can use immediately.