票据锁：给等待一个公平的号码

在多线程并发的世界里，“公平”往往是一个被奢侈对待的属性。

大多数常见的互斥锁（Mutex）或自旋锁（Spinlock）并不保证公平性。当锁被释放时，操作系统或硬件调度器决定哪个等待线程胜出，这通常取决于谁运气好（刚好在 CPU 上）或者谁反应快。这种非确定性可能导致“线程饥饿”——某个倒霉的线程可能一直抢不到锁，即便它已经等了很久。

票据锁（Ticket Lock）是解决这个问题的一种优雅方案。它的灵感来源于我们在银行或办事大厅见过的排队叫号系统。

原理：取号与叫号

Ticket Lock 的核心逻辑非常直观，它维护两个原子计数器：

排队号（Ticket/In）：表示下一个可领取的号码。
服务号（Service/Out）：表示当前持有锁（正在被服务）的号码。

当一个线程想要获取锁时，它执行 fetch_add 原子操作拿到一个排队号（Ticket），然后检查这个号码是否等于当前的服务号（Service）。如果不等，它就自旋等待；如果相等，说明轮到它了。

当线程释放锁时，它只需将服务号加 1，唤醒持有下一个号码的线程。

这种机制严格保证了 FIFO（先进先出） 的顺序。先来的线程拿到更小的号码，必然先获得锁。

代码实现 (C++20)

我们可以使用 C++20 的 std::atomic 来演示这一机制。为了避免原始代码的依赖，这里展示一个纯净的现代 C++ 实现。

#include <atomic>
#include <thread>

class TicketLock {
    // 排队号：下一个进入等待的线程领取的号码
    std::atomic<size_t> next_ticket_{0};
    // 服务号：当前允许进入临界区的号码
    std::atomic<size_t> now_serving_{0};

public:
    void lock() {
        // 1. 原子地获取一个号码，并将排队号加1
        // memory_order_relaxed 足够，因为 fetch_add 本身保证原子性，
        // 且后续的加载会有同步屏障
        size_t my_ticket = next_ticket_.fetch_add(1, std::memory_order_relaxed);

        // 2. 自旋等待，直到叫到我的号
        while (now_serving_.load(std::memory_order_acquire) != my_ticket) {
            // 提示 CPU 我们在自旋，避免过度消耗流水线资源
            #if defined(__x86_64__) || defined(_M_X64)
                __builtin_ia32_pause();
            #elif defined(__aarch64__)
                asm volatile("yield");
            #endif
        }
    }

    void unlock() {
        // 3. 叫下一个号
        // 使用 release 语义，确保临界区的写入对下一个线程可见
        size_t current = now_serving_.load(std::memory_order_relaxed);
        now_serving_.store(current + 1, std::memory_order_release);
    }
};

优势与代价

Ticket Lock 的美感在于简洁。它没有复杂的等待队列结构，仅仅依靠两个整数就实现了强公平性。

优势

确定性：彻底消除了线程饥饿。
低开销：在无竞争或低竞争场景下，它只需要一次原子加法和一次比较，非常高效。

代价

然而，凡事皆有代价。Ticket Lock 在高竞争场景下存在著名的可扩展性问题。

由于所有等待的线程都在自旋检查同一个变量 now_serving_，这个变量所在的缓存行（Cache Line）会在多个 CPU 核心之间频繁颠簸（Bouncing）。每当持有锁的线程更新 now_serving_ 时，所有等待线程的缓存行都会失效，引发一次总线风暴，尽管最终只有一个线程能成功获取锁。

为了解决这个问题，更复杂的锁（如 MCS Lock 或 CLH Lock）将等待状态分散到每个线程独立的节点上，但这又是另一个故事了。

对于中等程度的竞争，或者当你必须保证处理顺序时，Ticket Lock 是一个极佳的工具。它提醒我们，有时候最简单的排队论原理，就是最高效的计算机科学。