Spinlock Design from Test-and-Set to Ticket Locks

A spinlock is the simplest lock that can be built from atomics: a word that is 0 when free and 1 when held, acquired by an atomic exchange that returns the old value. If the old value was 0, the caller won; otherwise it spins and tries again. That construction is correct, and it is the worst reasonable implementation on a machine with more than a couple of cores. The reasons are worth working through because they apply to every primitive built on a contended word.

The acquire, and the release that is not optional

typedef struct { atomic_int state; } spinlock_t;

static inline void lock(spinlock_t *l)
{
    while (atomic_exchange_explicit(&l->state, 1, memory_order_acquire))
        ;                                    /* keep trying until the old value was 0 */
}

static inline void unlock(spinlock_t *l)
{
    atomic_store_explicit(&l->state, 0, memory_order_release);
}

The acquire ordering on the exchange is not decoration. Everything the critical section does must happen after the lock is obtained, and the acquire prevents those operations from being hoisted above the loop. The release ordering on the store is equally load-bearing: it guarantees that the critical section’s writes are visible before the lock appears free, so the next holder does not read a half-finished update. Removing either one leaves a lock that works on x86 in practice and fails on weakly ordered hardware, which is the worst kind of bug to own.

Using atomic_exchange rather than a compare-exchange is deliberate. The exchange writes unconditionally, so even a failed acquisition has modified the line and taken exclusive ownership of it. That is the source of the trouble.

Why test-and-set starves its waiters

With N threads spinning on the exchange, every iteration of every waiter’s loop is a write to the lock word. Each write needs exclusive ownership, so each iteration invalidates the copies held by all the other waiters. The line circulates continuously among the cores, and the lock is handed to whichever core happens to win the arbitration after the current holder releases it.

The consequences are worse than the raw traffic suggests. The holder that releases the lock immediately re-enters the loop for its next acquisition, and a core that has just released is well placed to win again: it has the line, it has the branch predicted, and the other cores are still waiting for their invalidations to complete. Under sustained contention a thread can lose the race repeatedly and make no progress for a long time, even though the lock is being acquired and released constantly by others. This is starvation by unfairness, and it is a property of the algorithm, not of the scheduler.

There is a second cost. The spinning writes are pure coherence traffic; none of them can succeed until the holder releases, so the waiters are burning interconnect bandwidth and power to accomplish nothing. On a machine with SMT the spinning also competes with the holder’s own sibling thread for issue slots.

Test-and-test-and-set

The standard repair is to make the spin read-only and attempt the write only when the read suggests the lock is free:

static inline void lock_ttas(spinlock_t *l)
{
    for (;;) {
        while (atomic_load_explicit(&l->state, memory_order_relaxed))
            ;                                 /* read-only spin: shared state, no invalidation */
        if (atomic_exchange_explicit(&l->state, 1, memory_order_acquire) == 0)
            return;
    }
}

The inner loop loads with relaxed ordering, which on a coherent machine leaves the line in the shared state across all waiters. Shared reads do not invalidate each other, so the traffic collapses to a single transfer when the lock is released, after which every waiter observes the change and attempts the exchange.

The trade is a window of extra latency. A waiter that observes the lock free and then loses the exchange must go back to the outer loop, and that path is longer than a single failed exchange. It also reintroduces a milder unfairness: all waiters see the free value at roughly the same moment and race for the exchange, so the winner is still decided by arbitration rather than by arrival order.

Test-and-test-and-set is a strict improvement over plain test-and-set on any machine where spinning reads are cheaper than spinning writes, which is every machine with a coherent cache. It is not the end of the line.

Backoff

Adding a delay after a failed acquisition reduces the frequency of the race. A common shape is to spin on a read a fixed number of times, then pause, and to increase the pause after repeated failures.

The delay should be a processor-specific hint rather than a busy loop, because a busy loop occupies an issue slot that the lock holder may need. x86 provides pause, which also serves as a hint to the SMT scheduler that the thread is spinning. Arm provides a yield hint instruction. Both are preferable to an empty loop on a core with a sibling thread.

Backoff helps throughput under contention and hurts latency under light contention: an uncontended lock is acquired on the first attempt and never enters the backoff path, but a lightly contended one pays a delay that was not needed. The delay must also be bounded, since an unbounded doubling can push a thread’s wait far past the critical section length.

The ticket lock

A ticket lock removes the race rather than damping it. Two counters are used: next is incremented by each arriving thread and yields its ticket, and now is incremented by the releasing thread. A thread acquires when its ticket equals now.

typedef struct { atomic_int next; atomic_int now; } ticket_t;

static inline int ticket_acquire(ticket_t *t)
{
    int me = atomic_fetch_add_explicit(&t->next, 1, memory_order_relaxed);
    while (atomic_load_explicit(&t->now, memory_order_acquire) != me)
        ;                                     /* each waiter reads one shared value */
    return me;
}

static inline void ticket_release(ticket_t *t)
{
    atomic_fetch_add_explicit(&t->now, 1, memory_order_release);
}

Arrival order is now the acquisition order, so no thread can be starved by another arriving later. The waiters spin on a single shared read of now, which stays in the shared state and produces no invalidation traffic until the release changes it; at that moment the line is transferred once and every waiter observes the new value.

Fairness has a cost. A thread that arrives, acquires, and releases while no one else is waiting still performs two atomic read-modify-writes, where test-and-test-and-set needed one exchange plus a store. The uncontended fast path is measurably longer, which matters for locks that are mostly free.

The deeper problem is that tickets are handed out on arrival, not on scheduling. A thread that is preempted while holding a ticket, or that is descheduled while waiting, blocks every thread behind it. Under contention with more threads than cores, a ticket lock converts a scheduling delay into a convoy: the holder is not running, the queue does not advance, and every waiter spins on a core that could have been running the holder. Test-and-test-and-set degrades more gracefully here, because an absent holder eventually loses the lock to whoever is running.

Ticket counters also wrap. Both are plain integers, and the comparison is equality rather than magnitude, so wrapping at 2^32 is harmless as long as no thread waits through a full wrap of the counter. With a 32-bit ticket and a large queue that is not a practical risk, but a 64-bit ticket removes the question.

Queueing locks and the cache-line question

A ticket lock still has all waiters reading one word, which is one transfer per release. A queue-based lock, in which each waiter spins on its own predecessor’s flag, distributes the wait across distinct lines so that a release touches only the next waiter’s line. The cost is more memory per waiter and a more complex handoff, and the gain appears only at high core counts where the single-word broadcast becomes the bottleneck.

Where the two counters of a ticket lock are adjacent, they share a cache line, and the fetch_add on next invalidates the line the waiters are reading. Separating them by a line removes that interference. The same padding question applies here as to any counter described in Cache Line Transfer, False Sharing, and the Cost of Contention.

When not to spin at all

Spinning is only reasonable when the expected wait is shorter than the cost of a context switch, which is on the order of a few thousand cycles on a typical system. A lock held across a system call, a page fault, or an I/O operation violates that assumption, and every waiter burns a core that could be doing other work.

The standard resolution is a hybrid: spin for a bounded number of iterations, then block in the kernel. The spin phase handles the short critical sections that dominate, and the blocking phase prevents the pathological case where the holder is descheduled. The boundary between them is a tunable, and it is genuinely a property of the workload rather than of the lock.

A lock held in a context where blocking is illegal cannot use the hybrid. An interrupt handler on a uniprocessor that spins on a lock held by the interrupted code will never see it released, which is why interrupt-safe locking on a single core reduces to disabling interrupts rather than to spinning. That is a property of the execution context, not of the lock implementation, and no amount of backoff fixes it. The distinction between a waiter that spins and a waiter that may be descheduled is the same one that separates the guarantees in Progress Guarantees and the Lock-Free Hierarchy: a spinlock held by a preempted thread is blocking however the acquisition is written.