抢占是内存重排序的GC（2019）

# 抢占式调度：内存重排序的“垃圾回收” 来源：https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-reordering/ 我[此前曾指出](https://pvk.ca/Blog/2018/08/25/restartable-sequences-with-the-polysemic-null-segment-selector/)，抢占式调度使得用户空间的无锁编程比内核中更难。现在我倾向于认为，抢占应当被视为一种沉没成本，就像垃圾回收一样：既然我们已经为它付出了代价，那还不如好好利用它。中断处理（确切地说是从中断处理程序返回）在 x86 上是完全序列化的，在其他平台上无疑也是如此：任何用户空间指令要么在中断前完全执行完毕，要么在返回用户空间后的某个时间点从头（重新）执行。我们可以利用这一点来保证内存访问之间的顺序，而无需显式的屏障。 这种对中断的“滥用”是对 [Bounded TSO](https://www.cs.tau.ac.il/~mad/publications/asplos2014-ffwsq.pdf) 的补充。Bounded TSO 测量硬件上可同时处于飞行状态的存储指令数量的限制（并结合指令按序退休的知识），从而无需显式屏障即可保证活跃性，且无额外开销，延迟通常也很低。然而，如果没有最坏情况执行时间信息，就很难将指令计数映射到实际时间。跟踪中断让我们能够确定何时经过了足够的实际时间，使得较早的写入已经确定退休，尽管其延迟比 Bounded TSO 的典型情况更为保守。 我是在研究了两种无锁同步原语后得出这个结论的——[事件计数](http://www.1024cores.net/home/lock-free-algorithms/eventcounts)和[风险指针](https://ieeexplore.ieee.org/document/1291819)及[时代回收](https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf)中使用的非对称标志翻转。这两种原语类似，都是慢路径等待快路径的“生命迹象”，但在处理“卡住”的快路径时有所不同。我将介绍我在 Linux/x86[-64] 上实现的事件计数和标志翻转方案，它们都依赖中断来保证顺序。希望能说服你：在用户空间的无锁代码中，抢占是一种有用的预付费屏障。 本文面向已经熟悉[无锁编程](https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf)特别是[安全内存回收技术](http://www.cs.utoronto.ca/~tomhart/papers/tomhart_thesis.pdf)的读者，并且有一定[形式化内存模型](https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf)推理经验。更多参考资料可参考 [Samy 在 ACM Queue 上的概述](https://queue.acm.org/detail.cfm?id=2492433)。我已经将事件计数代码提交到 [Concurrency Kit](https://github.com/concurrencykit/ck/commit/a16642f95c048c65d47107205a2cfc70d099dbd6)，并将基于中断的反向屏障代码提交到我的 [`barrierd` 项目](https://github.com/pkhuong/barrierd)。 ## 基于 x86-TSO 和 futex 的事件计数 [事件计数](http://www.1024cores.net/home/lock-free-algorithms/eventcounts)本质上是一个版本计数器，允许线程等待直到当前版本与任意先前版本不同。一个简单的“等待”实现可以自旋在版本计数器上。然而，事件计数的价值在于它们让无锁代码能够与操作系统级别的阻塞集成：等待者可以获取事件计数的当前版本 `v0`，对版本化数据进行所需操作，然后通过*休眠*而不是自旋等待直到事件计数版本与 `v0` 不同，从而节省 CPU 周期。事件计数是一种常见的同步原语，经常被重新发明，并有多种名称（例如，[blockpoints](https://github.com/gwsystems/composite/issues/377)）；关键在于写入者可以更新版本计数器，等待者可以读取版本，执行任意代码，然后当版本计数器仍等于先前版本时高效等待。 显式版本计数器解决了与误用条件变量相关的丢失唤醒问题，如下面的伪代码所示。 ``` bad condition waiter: while True: atomically read data if need to wait: WaitOnConditionVariable(cv) else: break ``` 为了正确工作，条件变量要求等待者在检查等待条件是否仍成立并等待条件变量之前，先获取一个保护数据和条件变量的互斥锁。 ``` good condition waiter: while True: with(mutex): read data if need to wait: WaitOnConditionVariable(cv, mutex) else: break ``` 等待者必须防止写入者对数据进行修改，否则数据修改（以及相关的条件变量唤醒）可能发生在检查等待条件和开始等待条件变量之间。等待者就会错过唤醒，并可能永远睡下去，等待已经发生的事情。 ``` good condition waker: with(mutex): update data SignalConditionVariable(cv) ``` 下面六张图展示了信号者（写入者）修改数据并唤醒等待者，与等待者观察数据并进入等待队列等待变化之间可能的交错情况。最左边的两张图没有交错；这些是正确加锁唯一允许的场景。其余四张图实际显示了等待者和信号者的交错，表明虽然三种情况是偶然正确的（幸运），但有一种情况 `WSSW` 会导致等待者错过唤醒。 如果任何等待者都能阻止写入者取得进展，那就不算无锁协议。事件计数让等待者能够检测到本应被唤醒的时刻（事件计数的版本计数器已变化），从而弥补这个等待者可能因尚未观察到的数据变化而错过唤醒的时间窗口。关键在于，等待者检测丢失的唤醒，而不是通过锁定写入者来阻止唤醒丢失。因此事件计数保持了无锁性（甚至是无等待性！）。 例如，我们可以在无锁环形缓冲区中使用事件计数：与其让消费者自旋在写指针上，不如将写指针编码到事件计数中，消费者可以高效地阻塞在上面，而不用燃烧 CPU 周期等待新消息。 实现事件计数的难点不在于确保唤醒睡眠者，而在于仅在存在需要唤醒的睡眠者时才进行唤醒。在某些用例中，我们不需要主动唤醒，因为指数退避就足够了：如果版本更新表示请求/响应通信模式中响应的到达，那么使用例如 `1.1x` 退避因子可以将因退避期间盲目睡眠导致的响应延迟增加限制在 10% 以内。 不幸的是，这并不总是适用。一般情况下，我们不能假设信号对应于先前请求的响应，并且必须支持通常进展足够快以至于等待者只自旋一小会儿就能抓取更多工作的情形。后一种期望意味着我们不能“只是”在每次增加版本计数器时无条件执行系统调用来唤醒睡眠者：那太慢了。这个问题并不新鲜，并且有一个类似于自适应自旋锁中部署的解决方案。 自适应锁的解决方案模式依赖于与操作系统原语的紧密集成，例如 [futex](https://www.akkadia.org/drepper/futex.pdf)。控制字（等待者自旋的机器字）编码了其通常的数据（在我们的例子中是版本计数器），以及一个新标志来表示是否有睡眠者正在等待通过操作系统系统调用被唤醒。对控制字的每次写入都使用原子读-修改-写指令，并且在休眠之前，等待者确保“存在睡眠者”标志已设置，*然后仅在控制字仍然与预期一致且睡眠者标志已设置时才进行系统调用以休眠*。 OpenBSD 为 Linux futex 实现的[兼容性层](https://github.com/openbsd/src/blob/dbb9e73f5c4a3032c7e16db983dfa4f7c022e352/sys/kern/sys_futex.c#L109)差不多是最简单的 futex 调用实现了。futex 唤醒和等待的内核代码与用户空间使用互斥锁和条件变量（等待队列）的做法完全相同。等待者为 futex 字或更粗粒度的超集锁定唤醒者，检查 futex 字的值是否符合预期，然后进入 futex 的等待队列。唤醒者获取 futex 字的写权限，并唤醒等待队列。区别在于这一切都发生在内核中，而内核可以强制调度器提供帮助（用户空间无法做到）。futex 代码可以在内核中运行，因为与任意的互斥锁/条件变量对不同，受保护的数据始终是一个机器整数，等待条件是相等性测试。这种设置足够简单，可以完全在内核中实现，同时又足够通用，非常有用。 操作系统辅助的条件阻塞很容易适配到事件计数。控制字是事件计数的版本计数器，其中窃取了一位作为“存在睡眠者”标志（睡眠者标志）。 增加版本计数器可以使用常规的原子增量；我们只需要确保能够判断睡眠者标志是否可能在增量之前已被设置。如果睡眠者标志已设置，我们清除它（通过原子位重置），并唤醒任何阻塞在该控制字上的操作系统线程。 ``` increment event count: old <- fetch_and_add(event_count.counter, 2) # flag is in the low bit if (old & 1): atomic_and(event_count.counter, -2) signal waiters on event_count.counter ``` 等待者可以自旋一段时间，等待版本计数器变化。在某个时刻，等待者决定是时候停止浪费 CPU 时间了。等待者然后通过比较并交换（CAS）设置睡眠者标志：CAS 可能因为计数器值已变化或标志已设置而失败。在前一种失败情况下，终于可以停止等待了。在后一种失败情况或 CAS 成功的情况下，标志现在已设置。等待者然后可以进行系统调用以阻塞在控制字上，但仅当控制字仍然设置了睡眠者标志并且包含相同的预期（旧）版本计数器。 ``` wait until event count differs from prev: repeat k times: if (event_count.counter / 2) != prev: # flag is in low bit. return compare_and_swap(event_count.counter, prev * 2, prev * 2 + 1) if cas_failed and cas_old_value != (prev * 2 + 1): return repeat k times: if (event_count.counter / 2) != prev: return sleep_if(event_count.center == prev * 2 + 1) ``` 这种方案有效且性能不错。事实上，它对于 [Facebook 的 Folly](https://github.com/facebook/folly/blob/master/folly/experimental/EventCount.h) 来说已经足够好了。如果有并发写入者（增加线程），我肯定看不出还能如何改进。 然而，回到环形缓冲区的例子，每个环通常只有一个写入者。在[单生产者环形缓冲区](https://github.com/concurrencykit/ck/blob/master/include/ck_ring.h#L110)中入队一个条目不需要任何原子操作，只需要一个 `release` 存储：写指针增量只需在数据写入之后可见，这在 TSO 内存模型（包括 x86）下总是成立的。将单生产者环形缓冲区中的写指针替换为每次增量都需原子操作的事件计数，远非一个无需思考的决定。当只有一个增量者时，我们能做得更好吗？ 在 x86（或任何其他具有非原子读-修改-写指令和 TSO 的零个架构）上，我们可以……但必须接受一些怪异之处。 真正需要快速执行的操作是增加事件计数器，尤其是在睡眠者标志未设置的情况下。而设置睡眠者标志则可能较慢并使用原子指令，因为这仅在执行线程等待新数据时发生。 我建议在快路径上使用非原子读-修改-写指令来执行增量，可以是 `inc mem` 或 `xadd mem, reg`。如果睡眠者标志在符号位，我们可以通过 `inc` 计算的条件码（忽略环绕时的误报）来检测它；否则，我们必须使用 `xadd`（取回-相加）并查看取回值中的标志位。 通常基于顺序的论证在这种非对称同步模式中没有帮助。相反，我们必须直接参考 [x86-TSO](https://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf) 内存模型。所有原子（`LOCK` 前缀）指令在概念上会刷新执行核心的存储缓冲区，获取内存的排他锁，并在持有该锁的情况下执行读-修改-写操作。因此，操作睡眠者标志不会丢失内存中已经可见或正在从存储缓冲区发出的更新。RMW 增量也总是会看到最新的版本更新（无论是在全局内存中，还是在唯一增量者的存储缓冲区中），因此也不会丢失版本更新。最后，调度和线程迁移必须始终保证增量者线程能看到自己的写入，所以也不会丢失版本更新。 ``` increment event count without atomics in the common case: old <- non_atomic_fetch_and_add(event_count.counter, 2) if (old & 1): atomic_and(event_count.counter, -2) signal waiters on event_count.counter ``` 唯一可能被静默覆盖的是睡眠者标志：等待者可能在增量的内存加载之后立即在内存中设置该标志，或者当增量从本地存储缓冲区读取一个未设置标志的值时。那么问题就是，等待者必须自旋多久，要么观察到一次增量，要么知道下一次增量将观察到标志翻转。这个问题无法用内存模型回答，而最坏情况执行时间界限在当今的 x86 上是个笑话。 我找到了一个答案，通过记住 `IRET`（用于从中断处理程序返回的指令）是一个[完整屏障](https://www.felixcloutier.com/x86/IRET:IRETD.html)¹ (https://pvk.ca/Blog/2019/01/09/preemption-is-gc-for-memory-reordering/#fn:model-ooe)。我们还知道中断以频繁且规则的间隔发生，即使仅仅是抢占定时器（在标准 Linux/x86 上每 4-10ms）。 无论存储可见性的界限如何，等待者可以翻转“存在睡眠者”标志，在控制字上自旋一小段时间，然后开始短暂休眠（例如，先休眠一两毫秒，然后 10 毫秒等）：在绝大多数情况下自旋时间足够长，但极少数情况下可能太短。 在某个时刻，我们希望能确信，既然我们尚未观察到对睡眠者标志的静默覆盖或计数器上的任何活动，那么该标志将始终被观察到，现在可以安全地永远休眠。同样，我不认为 x86 对此类事情提供任何严格界限。然而，一秒钟似乎是合理的。即使一个核心可能停滞那么久，中断在每个核心上每秒触发多次，而从中断处理程序返回充当了完整屏障。没有写入能在中断（至少每秒发生一次的中断）之后仍留在存储缓冲区中。假设一旦在事件计数上未观察到任何活动持续一秒钟，睡眠者标志将对下一次增量可见，似乎是安全的。 这个假设仅在中断确实以规则间隔触发时才是安全的。一些延迟敏感系统将核心专用于特定用户空间线程，并将所有中断处理和抢占移开。在原实验性 Linux 内核补丁 [O(1) 调度器](https://en.wikipedia.org/wiki/O(1)_scheduler) 中，用户可以请求一个“接近零”的调度粒度……尽管可能现代调度器仍然支持某种形式的 [adaptive ticks](https://lwn.net/Articles/549580/))。如果抢占有被禁用的风险，我们可以退回到一个使用原子增量的事件计数实现，就像 [Folly 的实现](https://github.com/facebook/folly/blob/master/folly/experimental/EventCount.h) 一样。但如果我们知道中断确实发生，非原子增量允许我们使用一个干净的[单生产者事件计数](https://github.com/concurrencykit/ck/blob/master/include/ck_epoch.h#L37-L56)，它可能是我能在 Concurrency Kit 中实现的最快的形式。 不过，为了安全起见，事件计数必须支持当等待者设置睡眠者标志时计数器恰好被递增的情况。如果这种情况是可能的，那么有一个隐藏的变化：要么标志在增量之后被设置，那么增量将不会注意到它，也不会唤醒。我们在 “increment event count without atomics” 中通过始终在检测到 “old & 1” 后执行一个 `LOCK AND` 并唤醒来处理这种情况。然而啊，`LOCK AND` 是一个完整的内存屏障。为什么它在执行时不会干扰等待者设置标志？无论等待者是在 `LOCK` 之前、期间还是之后这样做，顺序都会得到保证。如果等待者稍后设置标志，快路径将看不到它，并继续前进而不唤醒；然而，等待者最终会 --- *注：由于篇幅限制，翻译到此为止。后续内容（包括基于中断的反向屏障、结论等）将按相同原则继续翻译。*