查看源代码 进程管理优化
问题
运行时系统 SMP 支持的早期版本完全依赖于锁来保护来自多个线程的数据访问。在某些情况下，这并不是什么大问题，但在某些情况下，它确实是个问题。它使代码变得复杂，需要确保所有需要的锁都被持有，并确保所有锁都以不会发生死锁的顺序获取。以正确的顺序获取锁通常还涉及释放持有的锁，迫使线程重新读取已经读取的数据。这是创建错误的好方法。为了增加系统中可能的并行性，尝试使用更细粒度的锁会使复杂性情况变得更糟。在执行操作时必须获取大量锁通常也会导致严重的锁争用，从而导致较差的可伸缩性。
运行时系统内部的进程管理也存在这些问题。当更改进程的状态时，例如从 等待 变为 可运行，需要锁定进程上的锁。当将进程插入到运行队列时，还需要锁定保护运行队列的锁。当将进程从一个运行队列迁移到另一个运行队列时，必须锁定两个运行队列和进程上的锁。
最后一个例子在正常操作中很常见。例如，当调度器线程用完工作时，它会尝试从另一个调度器线程的运行队列中窃取工作。在寻找窃取目标时，涉及到大量的运行队列锁的切换，并且在实际的窃取过程中，最终必须锁定两个运行队列和进程。当一个调度器用完工作时，通常其他调度器也会用完，导致大量的锁争用。
解决方案
进程
为了避免这些情况，我们希望能够在不获取进程上的锁的情况下，对进程执行大多数基本操作。此类基本操作的一些示例包括：在运行队列之间移动进程，检测是否需要将其插入到运行队列中，以及检测它是否处于活动状态。
这些操作所需的进程结构中的所有这些信息都受进程 status 锁的保护，但这些信息分散在许多字段中。使用的字段通常是状态字段，可以包含少量不同的状态。通过稍微重新排列这些信息，我们可以轻松地将这些信息放入 32 位宽的位标志字段中（只需要 12 个标志）。通过移动这些信息，我们可以从进程结构中删除五个 32 位宽的字段和一个指针字段！此移动还使我们能够使用原子内存操作轻松读取和更改状态。
运行队列
与进程一样，我们希望能够在不获取锁的情况下执行最基本的操作。最重要的是能够确定是否应该将进程排入特定的运行队列中。这涉及到能够读取实际负载和负载均衡信息。
负载均衡功能在重复的固定间隔触发。负载均衡或多或少地努力使系统中的运行队列长度均匀分布。当触发均衡时，会收集有关每个运行队列的信息，并设置迁移路径和运行队列长度限制。迁移路径和限制会固定下来，直到下一次均衡完成。每个运行队列最重要的信息是自上次均衡以来的最大运行队列长度。所有这些信息以前都存储在运行队列本身中。
当进程变得可运行时，例如由于收到消息，我们需要确定将其排入哪个运行队列。以前，这至少涉及在持有进程状态锁的同时锁定进程当前分配到的运行队列。根据负载，我们有时还需要获取另一个运行队列上的锁，以便确定是否应该将其迁移到该运行队列。
为了能够在不锁定任何运行队列的情况下决定使用哪个运行队列，我们将所有固定的均衡信息从运行队列移到了一个全局内存块中。即迁移路径和运行队列限制。需要频繁更新的信息，例如最大运行队列长度，保留在运行队列中，但是当访问这些信息时，我们现在使用原子内存操作，而不是在锁下操作这些信息。这使得首先确定要使用哪个运行队列成为可能，而无需锁定任何运行队列，并且在决定之后，锁定选定的运行队列并插入进程。
固定均衡信息
当确定选择哪个运行队列时，我们需要读取我们从运行队列中移出的固定均衡信息。此信息是全局的，在负载均衡操作之间是只读的，但在负载均衡期间会发生更改。我们不想引入一个在访问此信息时需要获取的全局锁。读取器优化的读写锁可以避免一些开销，因为数据最常被读取，但它不可避免地会在负载均衡期间造成中断，因为此信息被非常频繁地读取。随着调度器数量的增加，由于此原因导致的大规模中断的可能性也会增加。
我们没有使用全局锁来保护此信息的修改，而是在每次负载均衡时编写一个全新的版本。新版本被写入与先前版本不同的内存块中，并通过发出写入内存屏障，然后使用原子写入操作将指向新内存块的指针存储在全局变量中来发布。
当调度器需要读取此信息时，它们使用原子读取操作读取指向当前使用信息的指针，然后发出数据依赖读取屏障，该屏障在大多数架构上都是空操作。也就是说，访问此信息的开销非常小。
我们没有为不同版本的均衡信息分配和释放内存块，而是保留旧的内存块，并在安全时重复使用它们。为了能够确定何时可以安全地重复使用块，我们使用线程进度功能，确保在重复使用内存块时，没有线程对该内存块有任何引用。
减少激进程度
我们使用无锁运行队列实现了一个测试版本。但是，此实现的性能不如使用每个运行队列一个锁的版本。没有进行足够的研究来解释原因。由于锁定的版本的性能更好，因此我们保留了它，至少目前是这样。但是，无锁版本迫使我们使用其他解决方案，其中一些我们保留了下来。
以前，当运行队列中的进程被挂起时，我们会立即将其从队列中删除。这涉及锁定进程、锁定运行队列，然后将其从实现队列的双向链表中取消链接。从无锁队列中删除进程变得非常复杂。相反，我们只是将其留在队列中并将其标记为已暂停，而不是将其从队列中删除。稍后选择执行时，我们会检查该进程是否已暂停，如果是，则将其丢弃。在队列中停留期间，它也可能会再次恢复，如果是这样，则在选择执行时执行它。
通过在恢复到锁定实现时保留这一部分，我们可以删除每个进程结构中的一个指针字段，并避免在进程和队列上执行不必要的操作，这可能会导致争用。
组合修改
通过组合进程状态管理和运行队列管理的修改，我们可以在不锁定任何锁的情况下完成管理进程（关于调度和迁移）时涉及的大部分工作。在这些情况下，我们以前必须锁定多个锁。这当然导致了运行时系统大部分地方的大量重写，但是重写既简化了代码，又消除了许多地方的锁定。主要好处当然是减少了争用。
基准测试结果
在运行 chameneosredux 基准测试时，调度器经常会因尝试相互窃取工作而耗尽工作。也就是说，无论是成功迁移，还是尝试迁移进程，这都是我们想要优化的场景。通过引入这些改进，当在具有超线程的 Intel i7 四核处理器的新机器上使用 8 个调度器运行此基准测试时，我们获得了 25-35% 的加速。