翻译自An EEVDF CPU scheduler for Linux，大部分借助于ChatGPT翻译，仅作为我个人的参考，如果你想了解具体内容，建议查看原网页，因为我不确定我记录的中文翻译是否完整和正确。
作者：Jonathan Corbet 日期：2023年3月9日
内核的完全公平调度器（CFS）负责管理大多数Linux系统上运行的进程的CPU时间分配。CFS在2007年2.6.23版本中合并，自那时起，经过不断调整，它一直表现得相当不错。然而，CFS并不完美，有一些情况它处理得不如预期。Peter Zijlstra发布的EEVDF调度器提供了改进CFS的可能性，同时减少对那些常常脆弱的启发式方法的依赖。
CFS 的一个关键设计目标是公平性——确保系统中的每个进程都能获得公平的 CPU 时间。这个目标通过跟踪每个进程获得的时间来实现，将那些获得 CPU 时间较少的进程优先运行，每个进程的运行时间会根据其“nice”优先级进行调整。换句话说，CFS 从本质上讲是一个加权公平排队调度器。
事实证明，公平性足以解决许多 CPU 调度问题。然而，调度器面临的约束远远超出了公平分配 CPU 时间。例如，调度器应该最大化系统内存缓存的效益，这要求尽量减少进程在 CPU 之间的移动。同时，它还应该保持所有 CPU 忙碌，如果有工作要做的话。电源管理也是一个复杂因素；有时，系统吞吐量的最佳决策必须让位于电池寿命的保护。混合系统（即并非所有 CPU 都相同）则增加了更多复杂性。等等。
一个希望改进的地方是对延迟要求的处理。一些进程可能不需要大量的 CPU 时间，但当它们需要时间时，必须迅速获得。其他进程可能需要更多的 CPU 时间，但如果有必要，可以等待。CFS 并没有提供一种方式来表达进程的延迟要求；nice 值（优先级）可以用来给予进程更多的 CPU 时间，但这不是同一回事。实时调度类可以用于延迟敏感的工作，但在实时类中运行是一个特权操作，实时进程可能会严重影响系统的其他部分。
目前缺乏的是一种确保某些进程能够快速访问 CPU，而不必让这些进程获得超过公平份额的 CPU 时间的方式。延迟 nice 补丁已经流传了一段时间，作为解决这个问题的尝试；它们允许具有严格延迟要求的 CFS 进程在需要运行时跳过 CPU 队列。这些补丁似乎有效，但 Zijlstra 认为可能有更好的方法来解决这个问题。
“最早合格虚拟截止时间优先”（EEVDF）调度算法并不新鲜；它在 Ion Stoica 和 Hussein Abdel-Wahab 1995 年的论文中已有描述。其名称暗示了类似于内核截止时间调度器使用的最早截止时间优先算法，但与该调度器不同，EEVDF 并不是实时调度器，因此它的工作方式不同。理解 EEVDF 需要掌握一些（相对）简单的概念。
与 CFS 类似，EEVDF 尝试公平地分配可用的 CPU 时间给那些争夺 CPU 时间的进程。例如，如果有五个进程在争夺一个 CPU，那么每个进程应该获得 20% 的可用时间。给定进程的 nice 值可以用来调整其公平时间的计算；较低的 nice 值（即较高的优先级）使得进程获得更多的 CPU 时间，而牺牲掉其他具有较高 nice 值的进程。到此为止，没有什么新意。
假设有一个一秒钟的时间段；在这个时间段内，在我们的五进程场景中，每个进程应该获得 200 毫秒的 CPU 时间。由于各种原因，实际情况往往不会完全如此；有些进程可能获得了过多的时间，而另一些进程则被剥夺了时间。对于每个进程，EEVDF 计算该进程应该获得的时间和实际获得的时间之间的差异；这个差异称为“滞后”。具有正滞后值的进程没有获得其公平份额，因此应比滞后值为负的进程更早被调度。
实际上，一个进程只有当其计算出的滞后值大于或等于零时，才被视为“合格”；任何具有负滞后值的进程都不会被认为是合格的。对于任何不合格的进程，未来某个时间点，它应得的时间会赶上实际获得的时间，它将再次变得合格；这个时间被称为“合格时间”。
因此，滞后的计算是 EEVDF 调度器的关键部分，大部分补丁集专注于正确找到这个值。即使没有完整的 EEVDF 算法，进程的滞后也可以用于公平地将其放置在运行队列中；滞后值较高的进程应该优先运行，以尝试平衡系统中的滞后值。
另一个因素是“虚拟截止时间”，即一个进程应在何时获得其应得的 CPU 时间。这个截止时间是通过将进程的分配时间片加到其合格时间上来计算的。一个时间片为 10 毫秒、合格时间为 20 毫秒的进程，其虚拟截止时间将是 30 毫秒。
正如其名称所示，EEVDF 的核心在于，它会优先运行虚拟截止时间最早的进程。因此，调度选择是由公平性（用于计算合格时间的滞后值）和每个进程当前应得的时间量的组合驱动的。
在这个框架下，为延迟敏感进程提供更快访问自然会实现。当调度器计算每个进程的时间片时，会考虑该进程的延迟优先级设置；延迟优先级设置较低（即延迟要求较紧）的进程将获得更短的时间片。对延迟相对不敏感的进程将获得较长的时间片。需要注意的是，任何两个具有相同 nice 值的进程（即优先级相同）的 CPU 时间量是相同的，但低延迟进程会在更多的较短时间片中获得这些时间。
虚拟截止时间是通过将时间片加到合格时间上来计算的。这将导致具有较短时间片的进程拥有更接近的虚拟截止时间，从而优先执行。通常不需要大量 CPU 时间的延迟敏感进程将能够快速响应事件，而没有延迟要求的进程将获得较长的时间片，这有助于提高吞吐量。无需复杂的调度启发式方法即可实现这一结果。
然而，从学术论文到在 Linux 内核中表现良好的实现之间还有很大差距。Zijlstra 刚刚开始对他的 EEVDF 调度器进行基准测试；他初步得出的结论是，“有一些优势和劣势，但没有什么表明完全失败的迹象”。他说，“一些结果似乎表明 EEVDF 的调度一致性比 CFS 高，且在延迟方面有不少优势”。
虽然这显然是一个合理的起点，但 Zijlstra 也承认仍然需要做很多工作。不过，他表示，“如果我们能够实现这一点，我们就可以删除一大堆复杂的启发式代码”，用更明确定义的策略取而代之。他补充说，这不是一个小的变化：“它完全重构了基本调度器、位置、抢占、选择——所有的东西。唯一的共同点是它们都是基于虚拟时间的调度器。”
不言而喻，这样一个根本性的变化不可能迅速进入内核。值得注意的是，目前的补丁将 EEVDF 作为 CFS 的一个选项实现，这将允许在不实际替换当前调度器的情况下进行更广泛的测试。CPU 调度器必须为内核支持的各种系统上的几乎所有可想象的工作负载做出正确的响应；这为即使是小的变化引发的不良回归留出了很大的空间——这不是一个小变化。因此，在考虑用 EEVDF 替换 CFS 之前，还需要进行大量测试；关于何时可能发生这种替换，没有明确的截止时间，无论是虚拟的还是其他的。