Spinlocks versus Blocking Locks

A lock (or mutex) enforces mutual exclusion: at most one thread executes a designated critical section at a time. Every lock implementation must answer one question precisely — what does a thread do while the lock is held by someone else? The two canonical answers define this article's subject. A spinlock answers "keep trying." The waiting thread executes a loop that repeatedly attempts to acquire the lock via an atomic instruction (test-and-set, or compare-and-swap), never relinquishing the CPU. This is called busy-waiting. The thread is technically "running" the entire time from the scheduler's point of view, even though it makes no forward progress on real work. A blocking lock answers "let someone else use the CPU; wake me later." The waiting thread invokes a system call that removes it from the run queue and places it on a wait queue associated with the lock. When the holder releases the lock, it (or the kernel) moves one waiting thread back onto the run queue, where the scheduler will eventually dispatch it. The mechanism connecting release to wakeup is often a futex (fast userspace mutex) on Linux, which lets the fast, uncontended path stay entirely in user space and only traps into the kernel when there is actual contention. Both approaches rest on the same foundation: an atomic read-modify-write instruction that makes the "check and claim" step indivisible. The difference is entirely in what happens after a failed acquisition attempt — spin again immediately, or descend into the scheduler and give up the processor. This distinction cascades into different requirements: spinlocks must sometimes disable interrupts (to prevent the CPU itself from being ceded to a handler while holding a short lock on a single core), while blocking locks must integrate with the scheduler's wait-queue and priority machinery.

Spinlock acquire/release. The canonical implementation uses an atomic test-and-set (TAS) instruction, which sets a memory location to 1 and returns its previous value, atomically: ``` // shared: lock (initially 0 = free, 1 = held) function acquire_spinlock(lock): while atomic_test_and_set(lock) == 1: // busy-wait: keep polling pass // now lock == 1 and we own it function release_spinlock(lock): atomic_store(lock, 0) ``` A refinement, test-and-test-and-set (TTAS), avoids hammering the shared cache line with atomic writes while the lock is held by someone else: ``` function acquire_spinlock_ttas(lock): while true: while atomic_read(lock) == 1: pass // spin on a local cached read if atomic_test_and_set(lock) == 0: return // acquired // else someone beat us to it; keep spinning ``` TTAS matters on real hardware: cache-coherence protocols (MESI/MOESI) turn every `test_and_set` on a contended lock into a bus transaction that invalidates every other core's cached copy. Plain spinning on a read only requires a shared (read-only) cache line, dramatically reducing bus traffic under contention. A further refinement, the ticket lock, gives strict FIFO fairness: ``` // shared: next_ticket = 0, now_serving = 0 function acquire_ticket_lock(): my_ticket = atomic_fetch_and_increment(next_ticket) while now_serving != my_ticket: pass function release_ticket_lock(): atomic_increment(now_serving) ```

Blocking lock acquire/release. The waiting thread is parked on a wait queue rather than spinning: ``` // shared: lock_state (0 = free, 1 = held), wait_queue = empty function acquire_blocking_lock(): disable_interrupts() // atomic section begins if lock_state == 0: lock_state = 1 enable_interrupts() return // fast path, uncontended else: add_current_thread_to(wait_queue) block_current_thread() // yields CPU; scheduler picks another thread enable_interrupts() // resumes here after being woken by release() // (implementation re-checks lock_state to guard against // spurious wakeups, then retries acquisition) function release_blocking_lock(): disable_interrupts() if wait_queue is not empty: t = remove_one_thread_from(wait_queue) lock_state = 1 // ownership passed directly to t wake_up(t) // moves t to run queue else: lock_state = 0 enable_interrupts() ``` The interrupt-disable/enable pair (or an internal spinlock protecting the queue, in a multiprocessor kernel) makes the check-and-enqueue step atomic, exactly analogous to the atomic instruction in the spinlock. This is the essential insight: a blocking lock is built out of a small spinlock (or interrupt masking) plus a wait queue — you cannot escape busy-waiting entirely, you only shrink it to a few instructions of internal bookkeeping instead of the whole critical section.

Adaptive/hybrid locking. Most production mutexes spin for a short bounded time first, then fall back to blocking if the lock is still not free: ``` function acquire_adaptive_lock(lock, SPIN_LIMIT): for i in 1 .. SPIN_LIMIT: if atomic_test_and_set(lock) == 0: return // got it while spinning pause_instruction() // hint to CPU, saves power/pipeline // spin budget exhausted — park acquire_blocking_lock(lock) ``` The `pause_instruction()` (e.g., x86 `PAUSE`) tells the CPU this is a spin-wait loop, reducing pipeline speculation misprediction penalties and power draw without giving up the core.

Correctness of the spinlock. Mutual exclusion follows directly from the atomicity of `test_and_set`: the hardware guarantees that if two threads execute TAS on the same word "simultaneously," one observes the prior value 0 (and proceeds) and the other observes 1 (and spins), never both observing 0. This is the invariant: at most one thread transitions the lock from 0 to 1 at any instant. Progress (no deadlock) holds because the lock is released unconditionally by whoever holds it, so some spinning thread's next TAS attempt eventually observes 0 — assuming the holder is not preempted forever and the scheduler is fair. Plain TAS spinlocks provide no fairness guarantee (a thread can starve if unlucky), which the ticket lock fixes by handing out FIFO sequence numbers; its correctness invariant is that `now_serving` increases by exactly one per release and a thread proceeds only when its ticket matches, so waiters are served in arrival order.

Correctness of the blocking lock. The invariant is enforced identically at the moment of state transition — the `disable_interrupts()` / internal-spinlock region makes "check `lock_state`, then either take it or enqueue" atomic, so no two threads can both read `lock_state == 0` and both proceed. The wait queue provides liveness: `release()` explicitly hands ownership to a dequeued waiter (rather than merely setting `lock_state = 0` and hoping someone notices), which avoids a missed-wakeup race where a thread parks after the release already happened and would otherwise sleep forever. This handoff discipline is why real implementations pass ownership directly rather than waking all waiters to race for a freshly-cleared flag (the latter is simpler but reintroduces a stampede and possible starvation).

Time complexity. Under contention, a spinlock's acquire cost is $O(1)$ in the best case (uncontended TAS succeeds immediately) but its wait time is unbounded in the worst case, bounded above by (number of contenders) × (critical section length) under a fair scheduler — since every other spinning thread wastes full CPU quanta doing nothing but polling. A blocking lock's acquire cost is $O(1)$ atomic operations plus a context-switch cost $C$ (typically hundreds to a few thousand nanoseconds, including scheduler overhead and cache/TLB effects) whenever contention occurs; its wait time is bounded by the time until the lock is released plus one scheduling latency, but it does not burn CPU cycles while waiting.

The core tradeoff, quantified. Let $T_{cs}$ be the average critical-section hold time, $C$ the cost of a context switch (park + wake + reschedule), and $n$ the number of runnable threads waiting for the lock. Expected wasted work:

A spinlock is the better choice when $T_{cs} < 2C$ per waiter — i.e., the critical section is shorter than the round-trip cost of sleeping and waking. This is why kernels use spinlocks almost exclusively for very short critical sections (updating a run-queue pointer, a few instructions) and blocking locks for anything that might touch disk I/O, allocate memory, or otherwise run for microseconds or longer. On a single-processor system, a spinlock is almost always wrong for anything but disabling interrupts briefly: if the lock holder cannot run (because the only CPU is busy spinning in the waiter), the lock will never be released — a genuine liveness bug, not just an inefficiency.

Space complexity. A spinlock needs $O(1)$ words of shared state (just the lock flag, or two counters for a ticket lock). A blocking lock needs $O(1)$ words plus $O(w)$ space for the wait queue, where $w$ is the number of currently blocked threads — each entry typically reuses the thread's existing control block, so the marginal cost is a queue-link pointer per waiter.

Consider four threads (T1–T4) on a 4-core machine contending for a lock protecting a critical section that takes 50 ns. Assume a context switch (park, later wake, reschedule) costs 1000 ns round trip.

Reading the trace. T2 (spinning) wasted exactly 50 ns of CPU time but acquired the lock the instant it was free — negligible latency. T3 (blocking) wasted zero CPU time while parked, freeing its core for other work, but paid roughly 1000 ns of wakeup latency before it could even begin its 50 ns critical section — a 20× latency penalty relative to the work being protected. This single trace is the entire tradeoff in miniature: with four cores and short critical sections, spinning is clearly better for this lock's latency, though it costs CPU cycles that could otherwise run T3 or T4's non-critical work. If instead the critical section were 10,000 ns (e.g., it performs disk I/O), the spinning thread would waste 10,000 ns of a whole core versus the blocker's fixed ~1000 ns overhead — now blocking wins decisively. This crossover is exactly the $T_{cs}$ vs. $2C$ comparison derived above, and it is precisely why adaptive locks spin only up to a bounded threshold (often tuned near $C$) before parking.

Operating system kernels use spinlocks pervasively for data structures accessed from interrupt handlers, where blocking is impossible or unsafe — Linux's `spin_lock_irqsave`, protecting run queues and device driver state, is a textbook example. Database engines and in-memory key-value stores use short spinlocks for latch-protected page headers but blocking locks (or condition variables built atop them) for anything touching disk. Language runtimes hedge their bets: Java's intrinsic locks, glibc's `pthread_mutex`, and Rust's `parking_lot` all implement adaptive spin-then-park strategies, because application code cannot know in advance whether a given critical section will be nanoseconds or milliseconds. Hardware transactional memory and lock-free data structures are attempts to sidestep the tradeoff entirely, but they still fall back to one of these two waiting disciplines whenever a conflict is detected. Understanding this tradeoff is also the on-ramp to Semaphores, which extend blocking locks from a binary "held/free" flag to a counted resource with a wait queue, and to Condition Variables, which layer richer waiting conditions on top of a blocking lock's queue machinery.

Ask the tutor: How does a ticket lock's fairness guarantee change the worst-case waiting time compared to a plain test-and-set spinlock?