Ticket Lock: FIFO Fairness with Two Counters

The Problem: Fair Mutual Exclusion

The simplest spinlock is test-and-set: a single flag that every thread hammers with an atomic swap until it wins. It works, but it has two ugly properties. First, it is unfair: which thread wins the next atomic op is decided by the cache-coherence hardware, so a thread can be passed over indefinitely while newcomers barge ahead — that is starvation. Second, under contention every release triggers a stampede: all spinning cores fire atomic writes at the same cache line, producing an O(n) storm of invalidations.

• Goal: mutual exclusion (one holder at a time).
• Plus: a hard fairness guarantee — threads acquire in the order they requested.
• Plus: bounded waiting — a thread at position k waits behind at most k others, never forever.

The ticket lock solves the fairness half elegantly. Modeled on Lamport's 1974 Bakery Algorithm (deli-counter tickets), it replaces the free-for-all with an ordered queue realized as arithmetic on two counters — no explicit list, no per-thread nodes, just add and compare.

How It Works, Step by Step

Two shared counters live in one cache line: next_ticket (next number to hand out) and now_serving (number currently allowed in). Both start at 0.

acquire(lock):
    my_ticket = fetch_and_add(&lock.next_ticket, 1)   // grab a unique number
    while (lock.now_serving != my_ticket):
        cpu_pause()                                    // spin (PAUSE / yield)
    // critical section

release(lock):
    lock.now_serving += 1        // plain store; hand off to next ticket
    // (a store, not an atomic — only the holder writes it)

Key points:

• The atomic fetch-and-add is the only expensive step in acquire and it runs exactly once — no retry loop on the atomic itself, unlike test-and-set.
• Uniqueness: because fetch_and_add is atomic, no two threads ever receive the same ticket, so exactly one thread's condition (now_serving == my_ticket) is true at any moment.
• Release is a single non-atomic increment — the current holder is the only writer of now_serving, so a plain store (with a release barrier) suffices. This is cheaper than a CAS-based unlock.

Complexity and a Worked Trace

Space: O(1) — two words per lock, regardless of thread count. Acquire: one atomic fetch-and-add (O(1) uncontended) plus a spin whose length equals the number of tickets ahead of you. Release: O(1), a single store. The invariant that makes it correct: at all times now_serving ≤ next_ticket, and the number of threads in-or-waiting-for the critical section equals next_ticket - now_serving.

Trace with threads A, B, C arriving in that order (counters start 0/0):

A: fetch_and_add -> ticket 0, next_ticket=1; now_serving=0 -> ENTERS
B: fetch_and_add -> ticket 1, next_ticket=2; spins (serving 0 != 1)
C: fetch_and_add -> ticket 2, next_ticket=3; spins (serving 0 != 2)
A: release -> now_serving=1  => B's condition true -> B ENTERS
B: release -> now_serving=2  => C's condition true -> C ENTERS
C: release -> now_serving=3  => lock idle

Note the strict order A -> B -> C, matching arrival order exactly. The gap next_ticket - now_serving was 3 at peak — three threads accounted for, none lost or duplicated. This bounded-waiting proof is why ticket locks are a standard textbook example of a fair lock.

Where It Is Used in Real Systems

The ticket lock's most famous deployment was the Linux kernel. Nick Piggin introduced ticket spinlocks in 2.6.25 (2008), replacing the old unfair test-and-set spinlock_t after fairness pathologies were observed on large SMP machines — some CPUs could be starved for milliseconds. The kernel cleverly packed both counters into one 32-bit word (two 16-bit halves), so a single atomic add advanced next_ticket.

• Operating-system kernels and RTOSes use ticket-style locks where predictable, bounded acquisition latency matters more than raw uncontended throughput.
• Teaching and research: it is the canonical fair spinlock in OS courses (MIT 6.S081, the Herlihy & Shavit textbook) and the baseline against which MCS and CLH locks are compared.
• Embedded / real-time systems value its determinism: worst-case wait is bounded by the number of waiters, which schedulability analysis can reason about.

Linux ultimately moved to queued spinlocks (qspinlock) in 2015 (Waiman Long) because ticket locks scale poorly past a few contending cores — but the ticket lock remains the conceptual bridge from naive spinlocks to scalable queue locks.

Comparison: Ticket Lock vs Its Cousins

All the alternatives trade fairness against cache behavior:

• vs test-and-set / TTAS: Ticket wins decisively on fairness (FIFO vs none) at essentially the same atomic cost. But both share a fatal scaling flaw: every waiter spins on the same now_serving line, so each release invalidates n caches — O(n) coherence traffic per handoff.
• vs MCS lock (Mellor-Crummey & Scott, 1991): MCS also guarantees FIFO, but each waiter spins on its own local queue node. A release touches exactly one remote line, giving O(1) traffic per handoff. The cost: MCS needs a per-thread node passed into acquire/release and a slightly heavier unlock (a CAS). Ticket locks are simpler and API-compatible with a plain lock/unlock.
• vs queued spinlock: Modern kernels use a hybrid — a fast fetch-and-add path when uncontended, falling back to a per-CPU MCS queue under contention, capturing ticket-lock simplicity and MCS scalability.

Rule of thumb: ticket lock for low core counts and simplicity; MCS/qspinlock when many cores contend the same lock.

Pitfalls, Failure Modes, and Significance

Cache-line bouncing (the big one). Because all spinners poll a single shared word, high contention degrades throughput super-linearly — Linux measured this as the reason to abandon ticket locks on large NUMA boxes. Each unlock's write to now_serving ping-pongs the line across every socket.

• Convoying / preemption: ticket locks are strictly FIFO, so if the thread holding ticket k is descheduled by the OS, everyone behind it stalls even if they could otherwise proceed. Never take a spinning ticket lock in code that can be preempted or sleep — this is why kernel spinlocks disable preemption.
• Counter overflow: with 16-bit halves the counters wrap; correctness relies on the number of simultaneous waiters staying below 2^16, which holds in practice.
• No backoff / no fast bail-out: a thread that took a ticket is committed to waiting its full turn — there is no clean try-lock timeout without extra machinery.

Significance: the ticket lock is the minimalist proof that fairness costs almost nothing algorithmically — two counters and one atomic add — and it defined the fairness baseline that every scalable lock since (MCS, CLH, qspinlock) has had to match while fixing its cache behavior.

Ticket lock versus other spinlock designs on fairness, atomic cost, and cache traffic under contention.

Lock	Fairness	Acquire atomics	Cache traffic under contention (n waiters)
Test-and-set (TAS)	None — starvation possible	1 (test-and-set), retried	O(n) invalidations per release; heavy bus contention
Test-and-test-and-set (TTAS)	None	1 on success	O(n) invalidations per release (all spinners re-read)
Ticket lock	Strict FIFO, starvation-free	1 (fetch-and-add)	O(n) invalidations per release — all spinners re-read now_serving
MCS lock	FIFO, starvation-free	1 (swap) + 1 (CAS on release)	O(1) — each waiter spins on its own local node
Queued spinlock (qspinlock)	FIFO under contention	1 (CAS) fast path	O(1) via per-CPU MCS queue when contended