原子操作如何实现公平锁：从自旋锁到取号锁

在并发编程中，互斥锁是保证数据安全的基础工具，但并非所有锁都是公平的。Computerphile 的视频以熟食店取号系统为喻，深入浅出地讲解了原子操作如何构建更公平的锁机制，并探讨了性能与公平之间的权衡。

自旋锁的公平性困境

上一期介绍的互斥锁具体实现是自旋锁（spin lock）。它的工作方式很简单：线程不断尝试获取锁，直到成功为止。这种锁的问题在于不公平。视频中用了一个生动的比喻：20 个人同时试图打开一扇厕所门，每个人都不断转动门把手。如果其中一个人动作稍慢，或者运气不好，他可能永远抢不过那些“计数到 9”就尝试的人，最终导致饥饿（starvation）。

自旋锁的实现依赖于硬件提供的一个原子操作：比较并交换（compare-and-swap）。线程可以将一个值（比如 1）原子地写入内存单元，并取回旧值（比如 0），整个过程没有其他线程能插手。这足以构建一个基本的自旋锁，但无法保证等待的顺序。

饥饿（starvation）是指某个线程因长期无法获得所需资源而无法推进的状态，与死锁不同，系统整体仍在运行，只是个别线程被无限期搁置。在非公平锁中，新来的线程可能不断“插队”，导致早期等待的线程永远抢不到锁。除了饥饿，非公平锁还可能引发护航效应（convoy effect）：一个线程释放锁后，大量线程同时争抢，造成上下文切换和缓存失效的开销激增。公平锁通过强制排队缓解这些问题，但也会降低吞吐量，因为线程切换和唤醒需要额外开销，且新来的线程无法利用“锁刚好空闲”的窗口直接获得锁。

取号锁：用原子递增实现公平

为了实现公平，我们需要硬件提供稍多一点的能力：原子加法。视频解释说，与其只是替换内存中的值，不如对内存单元执行简单的算术运算，比如加一。这样，线程可以原子地递增一个内存位置，并知道递增前的值。

这个小小的扩展催生了取号锁（ticket lock）。其核心思想借鉴了熟食店的取号系统：顾客从取号机领取一个号码，然后等待叫号。在计算机中，有两个计数器：

• 下一个票号（next ticket）：新来的线程原子地递增此计数器，获得自己的票号。
• 正在服务（now serving）：当前持有锁的线程完成工作后，递增此计数器，通知下一个票号的线程可以进入。

视频中演示了具体过程：初始时两个计数器都为 0。第一个线程执行原子加一，得到旧值 0，因此它的票号是 0，同时下一个票号变为 1。它检查正在服务是否为 0，如果是，则获得锁。释放锁时，它将正在服务递增为 1，于是票号为 1 的线程可以继续。

这种机制保证了先到先得：每个线程都拥有一个唯一的票号，严格按照票号顺序获得锁，不会出现饥饿。视频强调，这仅仅通过增加一个原子加法操作就实现了公平性。

原子加法（atomic add，也称 fetch-and-add）是一种硬件原语，它在一条指令内完成“读取旧值、加上增量、写回新值”三个步骤，期间不会被其他线程打断。与比较并交换不同，原子加法天然适合实现排队：每个线程调用一次，就能获得一个全局唯一的递增序号，且调用顺序与序号顺序一致。在 x86 架构上，这通常由 LOCK XADD 指令实现；在 ARM 上则通过 LDXR/STXR 循环或 LDADD 等原子指令完成。正是这种“取号即排队”的语义，使得取号锁无需任何额外同步就能保证先到先得。

公平的代价：超时与复杂策略

取号锁并非完美。视频指出，如果一个线程取号后没有及时检查“正在服务”计数器（比如去“购物”了），整个队列都会阻塞。在现实中，熟食店会跳过缺席的顾客，但在计算机中处理超时却非常复杂：如果允许等待过久的线程强行获取锁，那么被跳过的线程回来时可能引发冲突，需要复杂的协调机制。

此外，取号锁假设所有任务耗时相近。视频提到，如果存在长任务和短任务混合，可能会引入优先级反转问题：低优先级的长时间任务持有锁，高优先级任务却只能等待。这属于策略层面的问题，而非原子操作原语本身的安全性问题。

优先级反转（priority inversion）是指高优先级任务因等待低优先级任务持有的锁而被阻塞，而低优先级任务又可能被中优先级任务抢占，导致高优先级任务实际等待时间远超预期。经典案例是 1997 年火星探路者号任务中，高优先级的信息总线任务被低优先级的通信任务阻塞，而后者又被中优先级的天气任务抢占，最终触发系统复位。常见的缓解手段包括优先级继承（持有锁的低优先级任务临时提升至高优先级）和优先级天花板（锁被获取时即提升至可能访问它的最高优先级）。这些机制属于调度策略层面，与锁的公平性正交，但在混合任务负载下必须与取号锁等公平机制协同考虑。

性能优化：快速路径与乐观检查

视频最后讨论了高性能场景下的优化技巧。一个常见的模式是快速路径检查：在真正加锁之前，先检查是否已经满足条件。例如，在初始化数据库连接时，如果连接已经建立，线程可以直接使用而不必获取锁；只有当连接不存在时，才走加锁的慢路径。

这种优化需要小心处理双重检查（double-checked locking）：线程在未加锁时检查到连接不存在，获取锁后必须再次检查，因为在此期间其他线程可能已经建立了连接。视频提醒，这种模式容易出错，但为了性能有时不得不采用。

另一个值得注意的点是自旋锁的 CPU 开销。线程在自旋时持续占用 CPU，进行无意义的检查，视频形容这就像不断敲门问“好了没”，既烦人又耗费资源。因此，自旋锁适用于临界区极短的场景，而较长的等待应使用阻塞式锁。

双重检查锁定（double-checked locking）在 Java 等语言中曾因内存可见性问题而广为人知：线程在未加锁时读取到的对象引用可能非空，但对象尚未完成初始化，从而使用到部分构造的对象。修复方案通常是将共享变量声明为 volatile（或使用 std::atomic 等具有 acquire/release 语义的类型），确保初始化写入先于引用发布。视频中提到的数据库连接场景正是这一模式的典型应用：第一次检查避免加锁开销，加锁后的第二次检查防止重复初始化，而正确的内存序保证则是该模式安全的前提。

总结

原子操作是构建并发原语的基石。从简单的比较交换到原子加法，硬件的微小增强就能实现从非公平自旋锁到公平取号锁的跨越。然而，公平性、性能和策略复杂性之间的权衡始终存在，理解这些底层机制有助于在实际开发中做出更合理的选择。