Solaris Turnstiles

# Solaris 门卫机制 — RDMSR 来源：https://rdmsr.github.io/writing/turnstiles/ ## 简介 Sun Microsystems 的 Solaris 曾一度被广泛认为在其时代操作系统中拥有最佳的对称多处理（SMP）支持之一。这种技术优势很大程度上源于项目内部开发的诸多创新。 尽管 Solaris 现已基本停止发展[\[1\]](https://rdmsr.github.io/writing/turnstiles/#fn-1)，但其影响依然深远；Solaris 开创的技术仍可在范围广泛的（https://en.wikipedia.org/wiki/ZFS）各类（https://en.wikipedia.org/wiki/Slab_allocation）软件（https://en.wikipedia.org/wiki/Solaris_Containers）中找到踪迹（https://en.wikipedia.org/wiki/DTrace）。 Solaris 的许多发明已被反复详述和讨论*至令人厌烦*（例如 Slab 分配器），但我很少见到讨论其**门卫机制**的。 尽管相对小众，这个思想已悄然传播，远远超出了 Solaris 的范畴。其变体现在可见于主要的操作系统、网络浏览器和语言运行时。事实上，你此刻可能就在使用多个该基本概念的实现！ ## 门卫机制为何存在 在深入探讨门卫机制之前，让我们先退一步，弄清楚 Sun 工程师当时试图解决哪些问题。 Solaris 的关键设计特点之一是重度使用阻塞互斥锁（或锁），部分原因是它们能为高优先级任务提供更低的延迟，这对于追求接近软实时行为的应用很重要。 但阻塞互斥锁自身也存在问题，而门卫机制的设计正是为了应对其中两个。 ### 互斥锁开销大 一个阻塞互斥锁不仅需要一个比特位来指示是否被锁定。内核还需要在其他地方跟踪诸如： - 当前谁持有该锁； - 哪些线程在等待它；以及 - 协调阻塞和唤醒这些线程所需的状态。 你可以将这些信息直接存储在每个互斥锁中，但这很快就会变得代价高昂。 高度可扩展的软件往往依赖于细粒度锁，即使用大量锁来保护相对较小的状态块。问题在于，大多数锁在大部分时间里都不会发生争用，因此为每个锁都分配大量的簿记信息大多是浪费空间。 保持互斥锁的小型化使得细粒度锁的成本更低。如果增加一个锁只花费几字节，开发者就能负担得起使用更多锁，而不是将不相关的状态合并到少数几个粗粒度锁后面。 ### 优先级反转 重度使用阻塞锁带来的另一个显著问题是*优先级反转*。 通常，当线程获取自旋锁时，它会禁用抢占（通过类似 `spl`、`Irql` 或 `preempt_disable` 的机制）。禁用抢占实际上将该线程置于系统最高优先级，阻止任何可能想要中断其工作的其他任务，直到自旋锁被释放。 这对吞吐量很有利，但如果禁用抢占时间过长，延迟可能会受损。 另一方面，阻塞锁不会禁用抢占，这提供了更好的延迟行为；高优先级任务可以中断其他低优先级任务。但这也会降低吞吐量，因此没有单一的最佳解决方案（尽管部分问题可以通过使用*自适应自旋*来解决）。 由于线程在持锁期间保持其优先级，一种特别棘手的情况可能发生：如果高优先级任务 A 试图获取当前被低优先级任务 B 持有的锁会怎样？ A 会阻塞，等待 B 释放锁。到目前为止一切正常。问题是 B 仍然是一个低优先级任务。任何变为可运行状态的中优先级任务都可以抢占 B，阻止其取得进展并释放锁。 实际上，我们的高优先级任务现在卡住了，需要等待本不该延迟它的任务。这被称为*优先级反转*，在最坏情况下，它可能使 A 被延迟不确定的时间。 那么，所谓的延迟保证也就化为乌有了！ ### 优先级继承 幸运的是，一群聪明人找到了一个巧妙的解决方案：**优先级继承**。 在相同情况下，B 会临时*继承* A 的优先级，直到它完成其临界区，使其能够在任何可能挡路的中优先级任务之前运行。 乍一看，这似乎很简单：当一个高优先级线程在锁上阻塞时，提升锁持有者的优先级。然而，一旦锁开始依赖其他锁，事情就变得更有趣了。 考虑以下场景：A 等待 B，而 B 本身又在等待 C。A 可以将它的优先级传播给 B，但它仍然必须等待可能优先级较低的 C 释放锁。为了纠正这一点，A 的优先级需要通过*所有者链*传播，直到到达 C。这被称为*多跳*优先级继承。 棘手之处在于内核中如何高效地跟踪这些链。 不同的操作系统发明了不同的机制来跟踪这些依赖链。门卫机制正是 Solaris 以及一些从 UNIX 衍生的操作系统用来实现此目的的机制。 其他一些值得注意的方法包括： - Windows 上的 AutoBoost；以及 - Linux 的 rt-mutex 优先级继承机制。 ## 门卫机制 ``` ⠀⠀⠀⠀⠀⢀⣀⣀⣀⣀⣀⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⢀⣴⣿⣿⣿⣿⣿⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢀⣴⣿⣧⣤⣤⣤⣤⣼⣿⠟⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⣿⡿⢋⣴⣿⠀⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⣶⡄⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠋⠰⠿⠟⠃⣀⣉⡉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠉⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠰⣦⡄⠉⠻⢿⣷⣦⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⢻⣿⡄⠀⠀⠈⠙⠻⣿⣶⣤⣀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⢿⣷⡀⠀⠀⠀⠀⠀⠙⠻⢿⣷⣦⣄⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠈⣿⣷⠀⠀⠀⠀⠀⠀⠀⠀⠈⠙⠛⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠘⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠸⣿⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠹⡿⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⢸⣿⣿⣿⣿⣿⣿⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠈⠉⠉⠉⠉⠉⠉⠀⠀ ``` 从高层次来看，门卫是一个与争用锁相关联的数据结构。它跟踪等待该锁的线程，以及通过锁的所有者链传播优先级所需的信息。 巧妙之处在于，这些状态不必存储在锁本身内部。 相反，每个线程在创建时都会获得自己的门卫，以防它可能在阻塞锁上发生争用。这基于一个事实：一个线程同一时间只能在一个锁上阻塞。 当一个线程确实阻塞时，它实际上将其门卫“捐赠”给它正在等待的锁。该门卫随后成为内核存储该锁的等待者和优先级继承状态的地方。 这就引出了一个明显的问题：如果门卫不存储在锁内部，内核如何找到它？ 答案是一个哈希表。锁的地址被哈希处理，用于定位当前与该锁关联的门卫。请注意，下面的图表逻辑上显示哈希表中每个哈希桶有一个门卫，但实践中每个桶包含一个链表；找到合适的门卫需要遍历该桶的链表，以找到指向所需锁的门卫。 当一个线程在一个已争用的锁上阻塞时，它将其门卫捐赠到一个按门卫管理的空闲链表上。当锁最终被释放时，每个线程只需从空闲链表中获取一个门卫，是哪个都无关紧要；门卫并不绑定到特定线程。 每个线程跟踪它当前阻塞在其上的门卫，每个门卫知道锁的当前所有者。 门卫图示### 所有者链 为了实现*多跳*优先级继承，优先级提升代码需要跟踪每个连续的锁依赖。概念上，这相当于遍历一条看起来像 `turnstile->owner->turnstile->owner...` 的链，直到到达一个未在同步对象上阻塞的所有者（这可以通过线程结构中的 `waiting_on` 字段来跟踪）。 执行此操作所需的锁实际上变得相当复杂，因此我建议你在渴望更多细节时阅读 Illumos 实现 (https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/os/turnstile.c) 中的注释[\[2\]](https://rdmsr.github.io/writing/turnstiles/#fn-2)。其要点是存在一个 `桶锁 -> 线程锁` 的锁层次结构，并且连续的桶锁使用 trylock 尝试获取。如果获取失败，则释放所有已持有的锁并重试，以避免当前正在执行优先级继承遍历的两个 CPU 之间发生活锁。 ### 局限性 敏锐的观察者可能已经注意到此方案的一个明显局限性：一个门卫只有一个继承者。那么，对于拥有多个所有者的锁，例如读写锁，该怎么办呢？ 这正是情况变得棘手的地方。如果一个写线程在多个读线程之后阻塞，它无法将优先级捐赠给单一的所有者。 相反，使用门卫的内核依赖启发式或“足够好”的解决方案，例如选择第一个获取锁的线程作为继承者，或者干脆放弃对多所有者锁的优先级继承。另一个可能的解决方案是在获取共享锁之前简单地将线程优先级提升到某个给定上限。 我相信，唯一支持多继承者的优先级继承方案是 NT 的 AutoBoost，但其内部细节并未广泛公开。 ## 影响 许多从 UNIX 衍生的操作系统在开始支持 SMP 时，开始借鉴（复制）Solaris 的想法。因此，门卫机制现在可见于同一家族的许多内核中。 门卫机制目前被用于： - Solaris（其发源地）； - Illumos (https://github.com/illumos/illumos-gate/blob/master/usr/src/uts/common/os/turnstile.c)； - macOS 的内核 XNU (https://github.com/apple-oss-distributions/xnu/blob/main/osfmk/kern/turnstile.c)； - FreeBSD (https://github.com/freebsd/freebsd-src/blob/main/sys/kern/subr_turnstile.c)；以及 - NetBSD (https://github.com/NetBSD/src/blob/trunk/sys/kern/kern_turnstile.c)。 此外，一些个人操作系统也采纳了它们： - 我自己的 zag (https://github.com/rdmsr/zag/blob/master/src/kern/turnstile.zig)[\[3\]](https://rdmsr.github.io/writing/turnstiles/#fn-3)； - MINTIA (https://github.com/xrarch/mintia2/blob/main/OS/Executive/Ke/KeTurnstile.jkl)； - Keyronex (https://github.com/Keyronex/Keyronex/blob/master/kernel/common/kern/turnstil.c)。 ### 操作系统之外 有趣的是，同样的基本思想也出现在操作系统内核之外。几个值得注意的例子包括： - Go 的运行时信号量 (https://github.com/golang/go/blob/master/src/runtime/sema.go)； - WTF::ParkingLot (https://webkit.org/blog/6161/locking-in-webkit/)。 `WTF::ParkingLot` 特别有趣，因为它被广泛使用，并且与门卫机制中节省空间的那一半功能看起来惊人地相似。 就像门卫一样，ParkingLot 将开销较大的等待器机制保持在锁本身之外。当线程需要阻塞时，锁的地址被用于在全局表中找到相应的等待队列。 重要的区别在于，ParkingLot 主要关注将线程置为睡眠状态并将其唤醒；它不提供使 Solaris 门卫机制变得特殊的优先级继承机制，因为用户空间不需要自己管理优先级继承，而是让内核通过诸如 Linux 上的 PI-futex 等机制来完成。 ## 资源 门卫机制在以下书籍中有很好的描述： - *The Design and Implementation of the FreeBSD Operating System*；以及 - *Solaris Internals*。 此外，它们曾在 Solaris 杂志中的一篇这里 (http://sunsite.uakom.sk/sunworldonline/swol-08-1999/swol-08-insidesolaris.html) 中有所描述。 1. 它在某种程度上通过 Illumos (https://en.wikipedia.org/wiki/Illumos) 得以延续↩ (https://rdmsr.github.io/writing/turnstiles/#fr-1-1) 2. 参见 `turnstile_interlock()`。↩ (https://rdmsr.github.io/writing/turnstiles/#fr-2-1) 3. 我实际上确实为 SMR 读取部分的某个特定情况成功实现了多所有者优先级继承，据我所知这是创新之举↩