Spin or Sleep: That is the question

This post surveys the locking primitives available to systems programmers, using the Linux kernel as the reference implementation and noting where userspace (POSIX threads, C11/C++ standard library) provides equivalents or diverges. Every primitive discussed here is an answer to a single design question: when a thread fails to acquire a contended lock, should it spin (busy-wait, retaining the CPU) or sleep (block, yielding the CPU to other work)?

The trade-off is quantitative. A context switch costs on the order of 1–10 µs once cache and TLB pollution are accounted for; blocking therefore pays that cost twice — once to sleep, once to wake. If the expected wait is shorter than that round trip, spinning wastes fewer cycles than sleeping. If the expected wait is longer, or unbounded, spinning burns a CPU that could run other work. A second, non-negotiable constraint compounds the trade-off: certain execution contexts — interrupt handlers, or any region with preemption disabled — are forbidden from sleeping at all, and must spin regardless of cost.

flowchart TB
    A["Lock acquisition fails<br/>(contended)"] --> B{"Can this<br/>context sleep?"}
    B -->|"no: IRQ handler,<br/>preemption disabled"| S["<b>Spin</b><br/>busy-wait, retain the CPU"]
    B -->|"yes"| C{"Expected wait vs.<br/>2× context switch"}
    C -->|"shorter<br/>(ns–µs)"| S
    C -->|"longer or<br/>unbounded"| Z["<b>Sleep</b><br/>block, yield the CPU"]
    S --> R["Retry until the owner releases"]
    Z --> W["Enter wait queue;<br/>woken at release"]

    classDef q fill:#dae8fc,stroke:#6c8ebf,stroke-width:1.5px,color:#1a1a1a
    classDef spin fill:#d5e8d4,stroke:#82b366,stroke-width:1.5px,color:#1a1a1a
    classDef sleep fill:#ffe6cc,stroke:#d79b00,stroke-width:1.5px,color:#1a1a1a
    class A,B,C q
    class S,R spin
    class Z,W sleep

Each primitive below occupies a different point in this design space. For each we state what it is, why it exists, and show its canonical use.

Spinlocks

A spinlock is the minimal mutual-exclusion primitive: a single word, acquired with an atomic read-modify-write instruction, released with a store. A thread that fails to acquire it retries in a tight loop.

Why it exists. Spinlocks are the only primitive usable in contexts that cannot sleep — interrupt handlers and preemption-disabled regions — and they are the cheapest option when critical sections are short (tens to hundreds of nanoseconds). In the Linux kernel, spin_lock() additionally disables preemption, guaranteeing that the lock holder is not descheduled while other CPUs spin on it.

static DEFINE_SPINLOCK(stats_lock);

void stats_update(struct stats *s, u64 delta)
{
	unsigned long flags;

	spin_lock_irqsave(&stats_lock, flags);   /* also masks local IRQs */
	s->bytes += delta;
	s->packets++;
	spin_unlock_irqrestore(&stats_lock, flags);
}

Interrupt handlers and self-deadlock. The _irqsave suffix above is not decorative. Consider a CPU that acquires a spinlock in process context with interrupts enabled, and a device interrupt that arrives on that same CPU while the lock is held. If the interrupt handler attempts to acquire the same lock, the CPU deadlocks against itself: the handler spins waiting for the lock, but the lock holder — the interrupted process-context code — cannot execute another instruction until the handler returns. No second CPU is required; a single interrupt at the wrong instruction boundary is sufficient, which makes the bug both inevitable at scale and nearly impossible to reproduce on demand.

sequenceDiagram
    participant P as CPU 0 (process context)
    participant H as CPU 0 (IRQ handler)

    P->>P: spin_lock(&l) — interrupts left enabled
    Note over P,H: device raises an interrupt on CPU 0
    P-)H: control transfers to the handler
    H->>H: spin_lock(&l) → spins forever
    Note over P,H: the handler waits for the lock.<br/>The holder cannot run until the handler returns.<br/>CPU 0 is deadlocked against itself.

The rule that follows: any spinlock that an interrupt handler can take must be acquired with local interrupts masked everywhere else — spin_lock_irqsave() in process context, so that the fatal interleaving cannot occur on the holding CPU. Interrupts on other CPUs are unaffected; their handlers simply spin until the holder releases, which is the normal, bounded case. The same discipline extends down the kernel’s softer deferred contexts (spin_lock_bh() for locks shared with softirqs), and the kernel’s runtime lock validator, lockdep, checks it mechanically: a lock ever taken in interrupt context that is elsewhere held with interrupts enabled is reported as a potential deadlock even if the fatal interleaving never occurred in the observed run.

This constraint is also why the sleeping primitives in the remainder of this survey are confined to process context: an interrupt handler has no task to put on a wait queue and no scheduler to return to, so for it, spinning is not merely the cheaper option — it is the only one.

The naive implementation — test-and-set on a shared byte — is instructive but performs poorly under contention, because every spinning CPU repeatedly writes the same cache line, generating coherence traffic that slows the eventual release:

typedef struct { atomic_flag locked; } tas_lock_t;

void tas_lock(tas_lock_t *l)
{
	while (atomic_flag_test_and_set_explicit(&l->locked,
						 memory_order_acquire))
		cpu_relax();          /* PAUSE on x86 */
}

void tas_unlock(tas_lock_t *l)
{
	atomic_flag_clear_explicit(&l->locked, memory_order_release);
}

The kernel’s production implementation has evolved precisely to eliminate these pathologies: ticket locks (2008) added FIFO fairness, and the current qspinlock (2015) is MCS-based — each waiter spins on its own per-CPU cache line rather than on the shared lock word, so the coherence traffic at release is O(1) rather than O(waiters). The API is unchanged; only the contention behavior improved.

Constraint. The critical section must not sleep — no memory allocation with GFP_KERNEL, no blocking I/O — and should be short, since every waiting CPU is burning cycles for its entire duration.

Sleeping locks: the mutex

A mutex provides the same exclusive-ownership semantics as a spinlock, but a contending thread blocks: it is placed on a wait queue and the scheduler runs other work until the owner releases.

Why it exists. For critical sections that are long, of unbounded duration, or that must sleep internally (allocation, I/O, waiting on other events), spinning is either wasteful or outright forbidden. The mutex converts wasted spin cycles into useful work at the price of two context switches.

static DEFINE_MUTEX(cfg_mutex);

int cfg_update(struct cfg *c, const struct cfg_delta *d)
{
	mutex_lock(&cfg_mutex);          /* may sleep: process context only */
	apply_delta(c, d);               /* may allocate, may block */
	mutex_unlock(&cfg_mutex);
	return 0;
}

The kernel mutex is not a pure sleeping lock: it implements optimistic spinning. A contending thread first spins — on its own MCS queue node — as long as the lock owner is actively running on another CPU, on the reasoning that a running owner will release soon. Only when the owner is preempted, or the spin budget is exhausted, does the waiter block. Measured under moderate contention with short hold times, this hybrid recovers most of the spinlock’s throughput while retaining the mutex’s ability to sleep. Userspace adaptive mutexes (PTHREAD_MUTEX_ADAPTIVE_NP) apply the same policy with less information: they cannot observe whether the owner is running, so they spin for a fixed budget and then block.

Semaphores

A counting semaphore generalizes the mutex from one permitted holder to N: down() decrements the count, blocking when it reaches zero; up() increments it and wakes a waiter.

Why it exists. Semaphores govern access to a pool of identical resources — DMA channels, command slots, bounded queues — where mutual exclusion is the wrong abstraction because concurrency up to N is precisely the intent. Semaphores also permit release by a thread other than the acquirer, which mutexes prohibit; this makes them usable for signaling, though dedicated completion APIs (struct completion) are now preferred for that role.

static struct semaphore slot_sem = __SEMAPHORE_INITIALIZER(slot_sem, 8);

int submit_cmd(struct cmd *c)
{
	if (down_interruptible(&slot_sem))   /* wait for one of 8 slots */
		return -EINTR;
	issue(c);
	return 0;                            /* completion IRQ calls up() */
}

Historically the semaphore (with N = 1) was the kernel’s general sleeping lock; the dedicated mutex replaced it in 2006 because the stricter single-owner semantics enable optimistic spinning, priority inheritance (in the real-time tree), and debugging assertions that a counting primitive cannot support. New code should treat the semaphore as a special-purpose tool, not a default.

Reader–writer locks

Reader–writer locks split acquisition into a shared mode, admitting any number of concurrent readers, and an exclusive mode for writers. The kernel provides a spinning variant (rwlock_t) and a sleeping variant (rw_semaphore); POSIX provides pthread_rwlock_t, and C++17 provides std::shared_mutex.

Why it exists. Many shared structures are read frequently and modified rarely. Forcing readers to serialize behind a mutex discards reader-side parallelism that the workload inherently offers. The canonical kernel example is mmap_lock, the rw_semaphore protecting each process’s address-space layout: page faults take it for read and can proceed concurrently; mmap() and munmap() take it for write.

static DECLARE_RWSEM(map_sem);

u64 map_lookup(struct map *m, u32 key)
{
	u64 v;

	down_read(&map_sem);      /* concurrent with other readers */
	v = __lookup(m, key);
	up_read(&map_sem);
	return v;
}

void map_insert(struct map *m, u32 key, u64 val)
{
	down_write(&map_sem);     /* excludes readers and writers */
	__insert(m, key, val);
	up_write(&map_sem);
}

The caveat. Reader parallelism is not free. Every down_read() performs an atomic update on the lock word, so all readers still contend for exclusive ownership of one cache line; at high core counts this coherence traffic can erase the benefit of shared mode entirely. Writer starvation is the second hazard: a continuous stream of readers can hold writers off indefinitely unless the implementation queues fairly (the kernel’s does; POSIX leaves the policy unspecified).

Seqlocks

A sequence lock protects readers optimistically: a writer increments a sequence counter before and after its update (so the count is odd while a write is in progress), and a reader retries its read if the counter changed — or was odd — during the read.

Why it exists. For small, frequently read data — timestamps, counters, coordinates — even the rwlock’s single atomic per reader is too expensive. A seqlock reader performs no writes to shared memory at all: it reads the counter, reads the data, and re-reads the counter. Readers therefore never impede writers or each other. The kernel’s timekeeping code is the canonical user; gettimeofday() reaches a seqlock via the vDSO on every call.

static seqlock_t clk_lock = __SEQLOCK_UNLOCKED(clk_lock);
static u64 clk_ns;

u64 clk_read(void)
{
	unsigned int seq;
	u64 t;

	do {
		seq = read_seqbegin(&clk_lock);
		t   = clk_ns;
	} while (read_seqretry(&clk_lock, seq));   /* retry if a write intervened */

	return t;
}

void clk_tick(u64 now)
{
	write_seqlock(&clk_lock);    /* counter becomes odd */
	clk_ns = now;
	write_sequnlock(&clk_lock);  /* counter becomes even */
}

Constraints. The protected data must be small enough that a torn read is merely discarded, never dereferenced (a reader may observe a half-written update before retrying — pointers require care); readers must be side-effect-free, since they can execute any number of times; and read-heavy workloads are assumed, since a reader can in principle starve under a sustained write stream.

Userspace: the futex

Everything above the spinlock ultimately needs the scheduler’s help to sleep, and in userspace the scheduler sits behind a syscall boundary. Crossing that boundary on every acquisition — as pre-2002 SysV semaphores did — costs hundreds of nanoseconds even without contention. The futex (fast userspace mutex) removes that cost: the lock word lives in ordinary user memory and is manipulated with atomics; the kernel is invoked only to sleep (FUTEX_WAIT) and to wake (FUTEX_WAKE). An uncontended acquisition and release execute zero syscalls.

sequenceDiagram
    participant T as Thread
    participant W as Lock word (user memory)
    participant K as Kernel (futex)

    rect rgb(213, 232, 212)
    Note over T,W: Fast path — uncontended, no syscall
    T->>W: CAS 0 → 1
    W-->>T: success: lock held
    end

    rect rgb(255, 230, 204)
    Note over T,K: Slow path — contended
    T->>W: CAS fails (word = 1)
    T->>W: exchange → 2 (waiters present)
    T->>K: futex(FUTEX_WAIT, expect 2)
    K-->>T: sleep until owner calls FUTEX_WAKE
    end

The canonical three-state implementation (0 = unlocked, 1 = locked, 2 = locked with waiters) is due to Drepper’s Futexes Are Tricky:

void futex_mutex_lock(atomic_int *f)
{
	int c = 0;

	if (atomic_compare_exchange_strong(f, &c, 1))
		return;                          /* fast path: no syscall */

	if (c != 2)
		c = atomic_exchange(f, 2);
	while (c != 0) {
		syscall(SYS_futex, f, FUTEX_WAIT, 2, NULL, NULL, 0);
		c = atomic_exchange(f, 2);
	}
}

void futex_mutex_unlock(atomic_int *f)
{
	if (atomic_exchange(f, 0) == 2)          /* waiters were present */
		syscall(SYS_futex, f, FUTEX_WAKE, 1, NULL, NULL, 0);
}

Every modern userspace synchronization primitive — pthread_mutex_t, pthread_rwlock_t, std::mutex, std::shared_mutex, language runtimes’ monitors — is built on this mechanism. The futex is thus not a kernel locking primitive but the kernel service that makes efficient userspace locking possible.

Why userspace cannot simply spin. Pure spinlocks are far more hazardous in userspace than in the kernel, because userspace cannot disable preemption. If the lock holder is descheduled mid-critical-section, every spinner burns its entire timeslice waiting for a thread that is not running — the lock-holder preemption problem — and with fixed priorities the spinner can prevent the holder from ever running at all (priority inversion). Userspace spinning is defensible only as a bounded prelude to sleeping, which is exactly the adaptive-mutex policy.

For completeness, the C++17 reader–writer equivalent:

std::shared_mutex m;
std::unordered_map<Key, uint64_t> table;

uint64_t lookup(const Key& k)
{
	std::shared_lock r(m);        // concurrent readers
	return table.at(k);
}

void update(const Key& k, uint64_t v)
{
	std::unique_lock w(m);        // exclusive
	table[k] = v;
}

Summary

Toward zero-cost readers

Observe the trajectory across this survey. The rwlock admitted concurrent readers but charged each one an atomic operation on a shared cache line. The seqlock eliminated reader-side writes entirely but still forces readers to retry when a writer intervenes, and cannot safely protect pointer-linked structures. The logical endpoint of this progression is a primitive whose readers execute no atomic operations, no shared-memory writes, and no retries — readers that cost nothing beyond an ordinary function call, even while writers concurrently modify the structure they are traversing.

That primitive exists, and the Linux kernel invokes it billions of times per second: Read-Copy-Update (RCU). How it reconciles zero-cost readers with concurrent writers — by making writers copy, publish, and defer reclamation until all pre-existing readers have finished — is the subject of the next post in this series.