Solaris Turnstiles

Introduction Sun Microsystems’ Solaris was once widely regarded as having some of the best symmetric multiprocessing (SMP) support among the operating systems of its time. Much of this technical strength came from innovations developed within the project. Although Solaris is now mostly defunct, its influence remains substantial; technologies pioneered by Solaris can still be found across a wide range of software. A lot of Solaris’ inventions have been described and talked about ad nauseam (such as the Slab Allocator), but one I rarely see discussed is its use of turnstiles. Despite being relatively obscure, the idea has quietly spread far beyond Solaris. Variations of it can now be found in major operating systems, web browsers, and language runtimes. In fact, you’re probably using several implementations of the same basic concept right now!

引言 Sun Microsystems 的 Solaris 操作系统曾被广泛认为拥有当时操作系统中最好的对称多处理（SMP）支持。这种技术实力很大程度上源于该项目内部开发的创新。尽管 Solaris 如今已基本停用，但其影响力依然深远；Solaris 首创的技术至今仍广泛存在于各类软件中。Solaris 的许多发明（如 Slab 分配器）已被反复讨论，但我很少看到有人讨论它对“旋转门”（Turnstiles）的使用。尽管这一概念相对冷门，但它已悄然传播到 Solaris 之外。如今，在主流操作系统、网页浏览器和语言运行时中都能找到它的变体。事实上，你现在可能就在使用这一基本概念的多种实现！

Why turnstiles exist Before going in depth on turnstiles, let’s take a step back and figure out what problems Sun engineers were trying to solve. One of the key design hallmarks of Solaris was that it made heavy use of blocking mutexes (or locks), in part because they could provide much better latency for high-priority tasks, which is important if you wanted something approaching soft real-time behavior. The catch was that blocking mutexes came with problems of their own, two of which turnstiles were designed to address.

为什么需要旋转门 在深入探讨旋转门之前，让我们先退一步，看看 Sun 的工程师们试图解决什么问题。Solaris 的关键设计标志之一是大量使用阻塞互斥锁（Mutexes），部分原因是它们能为高优先级任务提供更好的延迟表现，这对于实现接近软实时行为的需求至关重要。问题在于，阻塞互斥锁自身也带来了一些麻烦，而旋转门正是为了解决其中的两个问题而设计的。

Mutexes are big A blocking mutex needs more than just a single bit saying whether it’s locked. Somewhere, the kernel also needs to keep track of things like: Who currently owns the lock; which threads are waiting for it; and the state needed to coordinate blocking and waking those threads. You could store all of this directly in every mutex, but that gets expensive pretty quickly. Highly scalable software tends to rely on fine-grained locking, i.e., having lots of locks protecting relatively small pieces of state. The problem is that most of those locks will be uncontended most of the time, so dedicating a large amount of bookkeeping to every single one is mostly wasted space. Keeping mutexes small makes fine-grained locking much cheaper. If adding another lock only costs a handful of bytes, developers can afford to use more of them instead of combining unrelated state behind a smaller number of coarse-grained locks.

互斥锁的体积问题 一个阻塞互斥锁需要的不仅仅是一个表示“是否已锁定”的位。内核还需要在某处跟踪以下信息：谁当前拥有该锁；哪些线程正在等待它；以及协调这些线程阻塞与唤醒所需的状态。你可以将所有这些信息直接存储在每个互斥锁中，但这很快就会变得非常昂贵。高可扩展性软件倾向于依赖细粒度锁，即拥有大量锁来保护相对较小的状态片段。问题在于，大多数锁在绝大多数时间内都不会发生竞争，因此为每一个锁分配大量的簿记空间纯属浪费。保持互斥锁的小巧能使细粒度锁的成本大幅降低。如果增加一个锁仅需消耗几个字节，开发者就可以负担得起使用更多的锁，而不是将不相关的状态合并在少数几个粗粒度锁之后。

Priority Inversion Another significant problem that arises with the heavy use of blocking locks is priority inversion. Typically, when a thread acquires a spinlock, it disables preemption (via mechanisms like spl, Irql or preempt_disable). Disabling preemption effectively puts the thread at the highest priority on the system, blocking any other task that might want to interrupt its work from doing so until the spinlock is released. This is great for throughput, but latency can suffer if preemption stays disabled for too long. Blocking locks, on the other hand, do not disable preemption, which allows for better latency behavior; high priority tasks can interrupt other lower priority tasks. This can also reduce throughput however, so there is no single best solution (though this can partly be worked around through the use of adaptive spinning). Since threads keep their priority when holding a lock, an especially ugly situation can occur: What if high priority task A tries to acquire a lock currently held by low priority task B? A blocks, waiting for B to release the lock. So far, so good. The problem is that B is still a low-priority task. Any medium-priority task that becomes runnable can preempt B, preventing it from making progress and releasing the lock. In effect, our high-priority task is now stuck waiting behind work that should never have been able to delay it in the first place. This is called priority inversion, and in the worst case it can delay A for an unbounded amount of time. So much for those latency guarantees!

优先级反转 大量使用阻塞锁带来的另一个重大问题是优先级反转。通常，当线程获取自旋锁（Spinlock）时，它会禁用抢占（通过 spl、Irql 或 preempt_disable 等机制）。禁用抢占实际上使该线程处于系统最高优先级，阻止任何其他任务在自旋锁释放前中断其工作。这对吞吐量很有利，但如果抢占被禁用太久，延迟就会受到影响。另一方面，阻塞锁不会禁用抢占，这允许更好的延迟表现；高优先级任务可以中断其他低优先级任务。然而，这也会降低吞吐量，因此没有唯一的最佳解决方案（尽管可以通过使用自适应自旋来部分缓解）。由于线程在持有锁时保持其优先级，可能会出现一种特别糟糕的情况：如果高优先级任务 A 试图获取当前由低优先级任务 B 持有的锁会怎样？A 会阻塞，等待 B 释放锁。到目前为止，一切正常。问题在于 B 仍然是一个低优先级任务。任何变为可运行状态的中等优先级任务都可以抢占 B，阻止其继续执行并释放锁。实际上，我们的高优先级任务现在被困在等待那些本不应延迟它的工作之后。这被称为优先级反转，在最坏的情况下，它可能会导致 A 无限期地延迟。那些延迟保证也就无从谈起了！

Priority inheritance Luckily, a bunch of smart people figured out a neat solution to this: priority inheritance. In the same situation, B would temporarily inherit A’s priority until it finishes its critical section, allowing it to run ahead of any medium-priority task that might otherwise get into its way. At first glance, this seems pretty simple: when a high-priority thread blocks on a lock, boost the priority of whoever owns it. Things get more interesting, though, once locks start depending on other locks. Consider the following scenario: A waits on B, but B itself is waiting on C. A could propagate its priority to B, but it would still have to wait for a potentially lower-priority C to release the lock. To correct this, A’s priority needs to be propagated through the owner chain until it reaches C. This is called multi-hop priority inheritance. What gets tricky is keeping track of these chains efficiently in the kernel. Different operating systems have come up with different machinery for keeping track of these dependency chains. Turnstiles are the mechanism Solaris and a bunch of UNIX-derived operating systems use to do exactly that. A few other notable approaches are: AutoBoost on Windows; and Linux’s rt-mutex priority-inheritance machinery.

优先级继承 幸运的是，一群聪明人想出了一个巧妙的解决方案：优先级继承。在同样的情况下，B 将暂时继承 A 的优先级，直到它完成临界区代码，从而允许它优先于任何可能阻碍它的中等优先级任务运行。乍一看，这似乎很简单：当高优先级线程在锁上阻塞时，提升锁持有者的优先级。然而，一旦锁开始依赖于其他锁，情况就变得有趣了。考虑以下场景：A 等待 B，但 B 本身正在等待 C。A 可以将其优先级传播给 B，但它仍然必须等待可能优先级更低的 C 释放锁。为了纠正这一点，A 的优先级需要通过所有者链传播，直到到达 C。这被称为多跳优先级继承。棘手之处在于如何在内核中高效地跟踪这些链。不同的操作系统提出了不同的机制来跟踪这些依赖链。旋转门正是 Solaris 和许多 UNIX 衍生操作系统用来实现这一点的机制。其他一些值得注意的方法包括：Windows 上的 AutoBoost，以及 Linux 的 rt-mutex 优先级继承机制。

Turnstiles At a high level, a turnstile is a data structure associated with a contended lock. It keeps track of the threads waiting on that lock, along with the information needed to propagate priority through the lock’s owner chain. The clever part is that this state doesn’t have to live inside the lock itself. Instead, each thread gets its own turnstile when it is created, in case it might contend on a blocking lock. This hinges on the fact that…

旋转门 从宏观层面来看，旋转门是一个与竞争锁相关联的数据结构。它跟踪在该锁上等待的线程，以及通过锁的所有者链传播优先级所需的信息。巧妙之处在于，这种状态不必驻留在锁本身内部。相反，每个线程在创建时都会获得自己的旋转门，以防它在阻塞锁上发生竞争。这取决于这样一个事实：……