抢占式调度：内存重排序的垃圾回收

背景

在多线程编程中，内存重排序是一个核心问题。现代处理器和编译器为了性能，可能会对内存操作进行重排，导致在并发环境中观测到不一致的顺序。传统上，开发者通过显式的内存屏障（memory barrier）来强制排序，但这种方法会带来性能开销。与此同时，抢占（preemption）——即任务被操作系统中断并切换——通常被视为一个需要避免的干扰因素，因为它会破坏锁自由（lock-free）代码的确定性。

然而，作者在2019年的这篇文章中提出了一个逆向思维：抢占已经发生了，我们已经在为它付出性能代价（上下文切换、缓存影响等），既然如此，不如像对待垃圾回收（GC）一样，把它当作一种“沉没成本”来利用。在x86架构上，中断处理（从中断处理程序返回）是完全串行化的：任何用户空间指令要么在中断前完整执行，要么在返回用户空间后从头重新执行。这一特性可以被“滥用”来保证内存访问的顺序，而无需显式屏障。这一观察与Bounded TSO技术互补：Bounded TSO通过硬件限制在途存储指令的数量来保证活性，但需要将指令计数映射到实时时间；而跟踪中断则可以让我们明确知道“足够多的时间已经过去，先前的写入已确定退休”。

作者在开发两个锁自由同步原语——事件计数（event counts）和不对称标志翻转（asymmetric flag flips，用于隐患指针和时代回收）——时得出了这一结论。这两个原语都涉及慢路径等待快路径的“生命迹象”，但处理“卡住”的快路径的方式不同。文章聚焦于Linux/x86-64上的实现，借由中断来保证排序。

核心内容

抢占作为“预付费的屏障”

在用户空间，锁自由编程通常使用内存屏障或原子操作来保证操作顺序。但抢占实际上提供了一种天然的序列化点：当发生中断（例如定时器中断、系统调用返回、或硬件中断）时，CPU会确保中断发生前的所有指令都已完全执行，或者被完全回滚。从中断处理程序返回后，任何用户空间指令都会从头开始。因此，两次用户空间指令之间的中断保证了这两条指令不会被重排序跨越中断。

这意味着：如果我们在某次写入之后、读取之前，确保至少发生了一次中断（例如通过系统调用、或者等待调度时间片用完），那么读取就一定能看到写入的结果（或看到写入完全未发生）。这可以替代显式的内存屏障，代价只是等待一个中断发生（通常已经存在，无需额外开销）。作者称之为“滥用中断”，但这一“滥用”是有用的：它让我们可以用几乎零开销的方式保证排序，只要接受一个保守的延迟（比如等待一个定时器嘀嗒）。

Bounded TSO 与中断的互补

Bounded TSO（有界总存储顺序）是一种已知技术：通过测量硬件在途存储指令的最大数量（例如某些x86处理器允许同时最多有约64条存储指令在写缓冲中），并结合指令按序退休的特性，可以保证在没有显式屏障的情况下，经过一定数量的指令后，之前的写入一定已经提交。它的优点是零开销且通常延迟很低。但缺点是需要知道最坏情况执行时间（WCET）才能将指令计数映射为实时时间，而WCET在用户空间很难精确获得。

中断跟踪则解决了这个映射问题：通过观察实际发生的中断时间（例如用户空间代码运行了多少时间片），我们可以确定是否已过去了足够长的实时时间，使得之前的写入必定已退休。尽管延迟比Bounded TSO的典型情况更保守，但更可靠、更易于实现。

事件计数（Event Counts）与 futex 的结合

事件计数是一个版本计数器，它允许线程等待直到当前版本不同于之前记录的某个版本。典型用法：等待者记录当前版本 v₀，处理数据，然后等待版本变化（即新数据到达）。它避免了条件变量中常见的“丢失唤醒”问题。

标准条件变量的缺陷在于：如果检查等待条件和进入等待队列之间发生了数据更新，且信号者已经发出了唤醒，等待者就会永远睡眠。事件计数通过让等待者检测版本号是否已变化来解决这个问题——即使错过了唤醒，等待者也会发现版本号变了，从而不会进入睡眠或重新检查。

实现事件计数的挑战在于：只在有睡眠者需要唤醒时才执行唤醒操作（而不是每次更新版本都执行系统调用）。解决方案类似于自适应自旋锁，紧密集成操作系统原语（如Linux的futex）。控制字（一个机器字）同时编码版本号和一个“有睡眠者”标志。写入者使用原子的读-修改-写指令更新控制字；等待者在睡眠前确保“有睡眠者”标志已设置，然后调用futex wait仅当控制字仍符合预期且标志置位时。通过这种方式，写者可以避免无谓的系统调用开销。

中断在事件计数中的应用

作者在Concurrency Kit中实现了一个基于中断的事件计数版本。当慢路径需要等待时，它不会仅仅自旋，而是利用中断来保证排序。具体来说，在x86-TSO（x86的总存储排序模型）下，结合futex和中断，可以实现高效的阻塞等待，同时保持锁自由（甚至等待自由）的属性。

不对称标志翻转（Asymmetric Flag Flips）

对于隐患指针（hazard pointers）和时代回收（epoch reclamation），使用不对称标志翻转。快路径（通常是无锁数据结构的读者）设置一个标志；慢路径（回收者）需要等待快路径离开临界区。如果快路径被抢占（卡住），慢路径可能无限等待。利用中断，慢路径可以确定快路径的指令已经完成或已回滚，从而安全地认为标志已稳定。

关键要点

• 抢占是沉没成本：中断已经发生，我们可以用它来保证内存顺序，无需额外屏障。这类似于垃圾回收——虽然带来开销，但可以加以利用。
• 中断处理是天然序列化点：在x86上，从中断返回后，任何用户空间指令要么完全在中断前执行，要么从零开始。因此，跨中断的访存不会重排序。
• Bounded TSO 与中断互补：Bounded TSO提供零开销的指令计数保证，但需要WCET；中断提供实时时间保证，但延迟更保守。
• 事件计数解决了丢失唤醒：通过版本计数器检测缺失的唤醒，而非阻止竞态；保持锁自由（甚至等待自由）。
• 高效实现依赖futex：控制字内嵌“有睡眠者”标志，避免无谓系统调用；写入者使用原子RMW，等待者只在使用futex时会陷入内核。
• 中断用于“反向屏障”：在不对称标志翻转中，慢路径利用中断来保证快路径的指令已退休，从而安全回收内存。
• 代码已开源：事件计数在Concurrency Kit中，基于中断的反向屏障在barrierd项目中可用。

意义与影响

该观点首次将抢占从“问题”转变为“机会”，为锁自由编程提供了一种近乎零额外开销的排序保证手段。传统上，开发者需要仔细插入屏障，或者依赖昂贵的内存序原子操作；而利用已有的中断（操作系统调度、硬件定时器中断）来保证顺序，不仅能简化代码，还能提高性能（因为避免了屏障带来的流水线停顿）。

这一思路对于实时嵌入式系统、高吞吐量网络服务器、以及内核级锁自由数据结构的用户空间实现都有启示。例如，在用户空间实现无锁队列时，可以利用定时器中断来避免自旋等待，同时保证正确的可见性。

不过，该方法依赖于中断的发生频率，在无中断的长时间用户空间执行中（例如一个持续计算而没触发任何系统调用的循环）可能无法保证及时顺序。因此，它更适用于混合模型：大多数情况依赖Bounded TSO的低延迟，在极端情况（如慢路径长时间等待）时才依赖中断。

总体而言，文章提供了一种新颖的权衡视角：既然我们无法避免操作系统调度的干扰（抢占），不如将它纳入同步原语的设计中，从而开发出更简单、更高效的锁自由算法。