Ticket Locks: Bringing Order to Chaos

In the world of concurrent programming, fairness is often a luxury we trade for raw throughput.

Most standard mutexes or spinlocks make no guarantees about who gets the lock next. When a lock is released, the operating system or hardware scheduler decides the winner, often based on luck (who happens to be scheduled) or proximity (which core is closest). This non-determinism can lead to starvation, where an unlucky thread waits indefinitely while newer threads jump the queue.

The Ticket Lock is an elegant solution to this problem, inspired directly by the "take a number" systems found in delis and bank tellers.

The Mechanism: Take a Number

The logic behind a Ticket Lock is beautifully simple. It maintains two atomic counters:

1. Ticket Counter (Next Ticket): The number to be handed out to the next arriving thread.
2. Service Counter (Now Serving): The number currently allowed to hold the lock.

When a thread wants the lock, it performs an atomic fetch_add on the Ticket Counter to get its unique number. It then spins, waiting for the Service Counter to match its ticket.

When the lock holder is done, it increments the Service Counter, waking up the specific thread holding the next number.

This mechanism strictly enforces FIFO (First-In, First-Out) ordering. Threads are served in the exact order they arrived.

Implementation (C++20)

We can demonstrate this mechanism cleanly using modern C++20 atomics. Here is a simplified implementation focusing on the core concept.

#include <atomic>
#include <thread>

class TicketLock {
    // The next ticket to be issued
    std::atomic<size_t> next_ticket_{0};
    // The ticket currently being served
    std::atomic<size_t> now_serving_{0};

public:
    void lock() {
        // 1. Atomically grab a ticket
        // memory_order_relaxed is sufficient here because the fetch_add is atomic,
        // and the subsequent acquire load provides the necessary barrier.
        size_t my_ticket = next_ticket_.fetch_add(1, std::memory_order_relaxed);

        // 2. Wait for our number to be called
        while (now_serving_.load(std::memory_order_acquire) != my_ticket) {
            // Hint to the CPU that we are spinning to save power/pipeline resources
            #if defined(__x86_64__) || defined(_M_X64)
                __builtin_ia32_pause();
            #elif defined(__aarch64__)
                asm volatile("yield");
            #endif
        }
    }

    void unlock() {
        // 3. Call the next number
        // Use release semantics to ensure writes in the critical section are visible
        size_t current = now_serving_.load(std::memory_order_relaxed);
        now_serving_.store(current + 1, std::memory_order_release);
    }
};

Beauty and The Beast

The beauty of the Ticket Lock lies in its minimalism. No complex wait queues, no linked lists—just two integers delivering strong fairness.

The Good

• Determinism: It completely eliminates starvation. Every thread gets a turn.
• Low Overhead: In uncontended or lightly contended scenarios, it involves a single atomic increment and a comparison.

The Bad

However, everything has a cost. Ticket Locks suffer from a well-known scalability issue under high contention.

Because every waiting thread is spinning on the exact same variable (now_serving_), the cache line containing that variable bounces between cores constantly. When the lock holder updates now_serving_, it invalidates that cache line across all waiting cores, triggering a burst of bus traffic (a "thundering herd" of cache coherency traffic), even though only one thread will succeed.

To solve this, more advanced locks like MCS Locks or CLH Locks distribute the spinning variables to local nodes, but that adds significant complexity.

For moderate contention, or when strict ordering is a requirement, the Ticket Lock remains an excellent tool. It reminds us that sometimes, simple queue theory is the most effective computer science.