Spinlock Contention: Ticket Ordering and MCS Queues

A spinlock’s cost is not the instruction that acquires it. It is the traffic that the waiters generate while they cannot. A lock held for a few hundred cycles on an idle machine is nearly free; the same lock with eight threads queued on it can dominate the runtime of the program, and the reason is the coherence protocol rather than the critical section.

The cache line is the unit of contention

The state of a spinlock lives in a cache line, 64 bytes on x86-64 and on most Arm implementations. A core may only write the line while holding it in the modified state, and obtaining that state requires invalidating every other copy. Each acquisition therefore transfers the line from the previous holder to the next, and each failed acquisition attempt by a spinning thread can also transfer it if the attempt writes.

A test-and-set loop writes on every iteration. With N waiters, each iteration by each waiter is a request for exclusive ownership of the line, and the requests serialize at the coherence point. The line moves from core to core continuously even though the lock is never released. This is the pathology that makes naive spinlocks scale badly: throughput falls as waiters are added, because the waiters compete for the line rather than for the critical section.

Two mitigations are standard and both are partial. The first is test-and-test-and-set: spin on a plain load, which can be served from a shared copy, and only attempt the atomic write when the line appears to have changed. Loads still require the line to be present, and every release invalidates the shared copies in all spinners at once, so all of them see the change simultaneously and all attempt the write together. The herd is smaller but not absent. The second is backoff: after a failed attempt, execute a delay loop whose length grows with the number of failures. Backoff reduces the frequency of requests, at the cost of latency when the lock becomes free during a delay.

Neither changes the fundamental structure. Every waiter is watching the same location, so the release is a broadcast and the acquisition is a race among all observers. The queue-based locks described below change the structure: each waiter watches a location that only it reads.

Ticket locks: fairness bought with a shared counter

A ticket lock replaces the flag with two counters in the same cache line. A thread that wants the lock performs an atomic fetch-and-increment on the first counter and receives its ticket. It then spins until the second counter, the now-serving number, equals its ticket, and increments the second counter on release.

/* Two 32-bit counters, adjacent so they share a cache line. */
struct ticket_lock {
    unsigned next_ticket;
    unsigned now_serving;
};

static void ticket_acquire(struct ticket_lock *l)
{
    unsigned my = __atomic_fetch_add(&l->next_ticket, 1, __ATOMIC_RELAXED);
    while (__atomic_load_n(&l->now_serving, __ATOMIC_ACQUIRE) != my)
        ;   /* each waiter spins on the same word */
}

static void ticket_release(struct ticket_lock *l)
{
    __atomic_fetch_add(&l->now_serving, 1, __ATOMIC_RELEASE);
}

The ordering property is worth being precise about. Tickets are handed out in the order the fetch-and-increment operations serialize at the coherence point, so acquisition order matches arrival order at that point. There is no starvation: a thread that has a ticket will acquire the lock after at most the number of threads that were ahead of it. The bound is finite even if it is not short.

A refinement that keeps the counting scheme but reduces the storm is to let a waiter stop spinning once it knows it is not next and instead park on a private flag, which is the queue-lock idea applied inside a counting lock. Another, used where the lock sits on a contended NUMA path, is to have a waiter that fails repeatedly back off for a bounded interval; this trades the latency of an immediately available lock for a lower request rate, and the interval has to be tuned per machine because it depends on how long a cache-line transfer takes across the interconnect.

The cost is that the spinning is still on a shared word. All waiters read now_serving, and every release writes it, invalidating all of their copies. The line moves to every waiter on every release, whether or not that waiter is next. With many waiters, the release is followed by a burst of line transfers as each core refetches the line to discover the new value. The traffic is proportional to the number of waiters per release, which is exactly the quantity a scalable lock must not depend on.

There is a subtler problem on machines with non-uniform memory access. A waiter on a remote node that spins on the shared counter pays a remote latency for every read of the line, and the line itself migrates to whichever node last read it. The lock’s location becomes a performance property of the machine’s topology rather than of the code.

The MCS queue: one word per waiter, watched by one waiter

The MCS lock, published by Mellor-Crummey and Scott in 1991, gives each waiter its own node and makes the queue a linked list threaded through those nodes. The tail of the list is a single pointer that is swapped atomically. A thread that arrives swaps its node into the tail and receives the previous tail, then links itself behind that node. It spins on a flag in its own node, which is in its own cache line and which no other thread writes until its turn comes.

struct mcs_node {
    struct mcs_node *next;      /* filled in by the thread ahead */
    int locked;                 /* this thread's own flag */
} __attribute__((aligned(64)));

struct mcs_lock { struct mcs_node *tail; };

static void mcs_acquire(struct mcs_lock *l, struct mcs_node *me)
{
    me->next = NULL;
    me->locked = 1;
    struct mcs_node *prev =
        __atomic_exchange_n(&l->tail, me, __ATOMIC_ACQ_REL);
    if (prev != NULL) {
        prev->next = me;                       /* ordered before prev's release */
        while (__atomic_load_n(&me->locked, __ATOMIC_ACQUIRE))
            ;                                  /* spin on a private line */
    }
}

static void mcs_release(struct mcs_lock *l, struct mcs_node *me)
{
    if (me->next == NULL) {
        /* No successor yet: try to clear the tail, or wait for one to appear. */
        if (__atomic_compare_exchange_n(&l->tail, &me, NULL, 0,
                                        __ATOMIC_ACQ_REL, __ATOMIC_RELAXED))
            return;
        while ((me->next = __atomic_load_n(&l->tail, __ATOMIC_ACQUIRE)) == NULL)
            ;
    }
    __atomic_store_n(&me->next->locked, 0, __ATOMIC_RELEASE);
}

The traffic per release is one write to one line, the successor’s flag, plus the read that the successor was already doing on that same line. No waiter observes a line that any other waiter writes, so the number of waiters does not increase coherence traffic. On a NUMA machine each waiter spins on memory local to itself, which is the property a shared counter cannot have.

The trade is space and complexity. Every acquisition needs a node, so the lock cannot be embedded in a structure and forgotten: the caller must own storage for the node, which usually means the node lives on the waiter’s stack and therefore has the lifetime of the wait. That is fine for a kernel spinlock held across a short critical section but awkward for a lock acquired inside a function that may return early. The release path also has a race: if the tail still points at the releasing node, there is no successor to hand the lock to, and the releasing thread must either clear the tail or wait for a newcomer to link itself in. The compare-and-swap plus the spin in the code above is the standard resolution; a version that simply cleared the tail unconditionally would lose a concurrent arrival.

What real kernels do with the two designs

Linux uses both shapes and a hybrid. Its historical spinlock on x86 was a ticket lock, and its current implementation is a queue lock that encodes the queue inside the single 32-bit lock word rather than in per-waiter nodes. The encoding lets an uncontended acquisition be a single compare-and-swap on one word, while a contended acquisition still gives each waiter a distinct position and a distinct byte to spin on, so the traffic does not grow with the number of waiters. The hybrid avoids the per-waiter node allocation at the cost of a more intricate state machine and a small fixed number of queue slots.

Whatever the encoding, the kernel-level rules are the same. A spinlock disables preemption for its duration, because a holder that is descheduled cannot release the lock and a waiter that spins on a uniprocessor would spin forever. spin_lock_irqsave additionally disables interrupts on the local processor, which is required when the same lock can be taken from an interrupt handler: an interrupt that preempts a holder and tries to take the lock deadlocks the processor against itself. The rule is not stylistic. It is the only way to keep the wait bounded on a machine with one runnable thread.

The kernel also distinguishes spinlocks from sleeping locks by context. A spinlock may be taken in interrupt context, where sleeping is impossible; a mutex may not. The distinction is documented in the lock types reference and enforced, imperfectly, by runtime checks.

Choosing between them

The decision comes down to which quantity must not grow with contention.

A ticket lock has bounded waiting, minimal state, and no allocation, and it is the right choice when the number of waiters is small or the critical section is long enough that the spinning traffic is a small fraction of the cost. Its weakness is that traffic scales with waiters.

An MCS lock has traffic independent of the number of waiters and is the right choice for large machines and hot locks. Its weaknesses are the per-acquisition node and the more delicate release path. It also has a property that matters for real-time code: it is strictly FIFO, so a thread cannot be starved, but a thread that has been preempted while holding the lock blocks the entire queue behind it, and a thread that is slow to be scheduled after being handed the lock leaves the queue idle.

Both designs are spinlocks and both are wrong when the critical section can be long or can block. The scheduler-based alternative, where a waiter is put to sleep and woken by the release, is the futex path described in futex wait and wake. Most production mutexes combine the two: spin for a bounded interval in the hope that the holder is running on another core, then sleep. The number of spins is a tunable that trades wasted cycles against the several-thousand-cycle cost of a context switch.

Readers that do not modify the protected state need not serialize against each other at all, which is a different design problem with its own pathologies, covered in reader-writer locks and their scaling limits.