翻译自Completing the EEVDF scheduler，大部分借助于ChatGPT翻译，仅作为我个人的参考，如果你想了解具体内容，建议查看原网页，因为我不确定我记录的中文翻译是否完整和正确。
作者：Jonathan Corbet 日期：2024年4月11日
最早虚拟截止时间优先（EEVDF）调度器已作为 6.6 内核的一个选项合并。这代表了 Linux 系统上 CPU 调度方式的重大变化，但自那时以来，EEVDF 的进展相对平静。不过，现在调度器开发者 Peter Zijlstra 在长时间缺席后回归，发布了一系列补丁，旨在完成 EEVDF 的工作。除了修复一些问题外，这些工作还包括一个重要的行为变化和一个新功能，旨在帮助延迟敏感的任务。
EEVDF 调度器的工作是将可用的 CPU 时间在系统中所有可运行的任务之间平均分配（假设所有任务的优先级相同）。如果四个具有相同优先级的任务在争夺 CPU，每个任务将获得 25% 的时间份额。每个任务被分配一个虚拟运行时间，代表其分配的 CPU 份额；在四个任务的例子中，虚拟运行时间可以被视为以实际时间的 25% 速度运行的时钟。当任务运行时，内核计算任务的虚拟运行时间与其实际运行时间之间的差异；这个差异称为“滞后”。正滞后值表示任务还应获得 CPU 时间，而负滞后值则表明任务已获得超过其份额的时间。
当滞后值为零或更大时，任务被视为“合格”；每当 CPU 调度器需要选择任务运行时，它会从合格任务集中进行选择。对于这些任务中的每一个，通过将时间片剩余时间加到任务变得合格的时间来计算虚拟截止时间。具有最早虚拟截止时间的任务将被选择运行。由于较长的时间片会导致较晚的虚拟截止时间，时间片较短的任务（通常是延迟敏感的任务）往往会优先运行。
以下是一个帮助可视化滞后如何工作的例子。假设有三个 CPU 密集型任务，称为 A、B 和 C，它们同时开始运行。在它们运行之前，它们的滞后都是零：
A B C
滞后： 0ms 0ms 0ms由于没有任务有负滞后，所有任务都是合格的。如果调度器选择 A 首先运行，时间片为 30ms（以此为例），如果 A 运行直到时间片耗尽，滞后情况将如下：
A B C
滞后： -20ms 10ms 10ms在这 30ms 中，每个任务应获得 10ms（总时间的三分之一）的 CPU 时间。A 实际获得了 30ms，因此其滞后为 -20ms；其他两个任务没有获得任何 CPU 时间，因此它们的滞后为 10ms，反映了它们应获得的 10ms 的 CPU 时间。
任务 A 不再合格，因此调度器将必须选择其他任务。如果 B 获得（并使用）一个 30ms 的时间片，情况变为：
A B C
滞后： -10ms -10ms 20ms同样地，每个任务的滞后对应于它应得的 CPU 时间，B 实际运行了 30ms。现在只有 C 是合格的，因此调度器的下一步决策就很简单了。
从上面的表格中可以看出，EEVDF 调度器的一个特性是系统中所有滞后值的总和始终为零。
滞后计算只对可运行的任务相关；一个睡眠一天的任务实际上并没有错过其虚拟运行时间（因为它没有），因此不会累积巨大的滞后值。然而，调度器在任务进入睡眠状态时会保留任务当前的滞后值，并在任务醒来时从该值开始计算。所以，如果一个任务在睡眠之前已经超出了其分配时间，它在醒来时会为此付出代价。
然而，有时保留任务的滞后可能没有意义。一个刚刚睡眠了一天的任务，是否真的应该因为昨天稍微超出了分配时间而受到惩罚呢？显然，迟早任务的滞后值应该恢复为零。但具体何时应该发生这种恢复并不完全明确。正如 Zijlstra 在这一系列补丁中的补丁中指出的那样，立即在任务睡眠时忘记滞后会使任务通过在时间片结束时短暂睡眠（当其滞后值可能为负时）来操控系统，从而获得超过其应得的 CPU 时间。他总结道，仅仅根据时间衰减滞后值也行不通，因为滞后与虚拟运行时间相关，虚拟运行时间的流逝速度不同且变化多端。
解决方案是根据虚拟运行时间来衰减睡眠任务的滞后值。这一思路在补丁集中有一定的实现趣味。当一个任务进入睡眠状态时，它通常会从运行队列中移除，以便调度器不再考虑它。在新补丁中，不合格的任务在睡眠时将被保留在队列中，但会标记为“延迟出队”。由于它不合格，它不会被选择执行，但其滞后值会根据虚拟运行时间的流逝而增加。一旦滞后值变为正值，调度器将注意到该任务并将其从运行队列中移除。
这种实现的结果是，短时间睡眠的任务将无法逃避负滞后值，但长期睡眠的任务最终会被免除滞后债务。有趣的是，正的滞后值将被无限期保留，直到任务再次运行。
如前所述，具有较短时间片的任务将拥有更早的虚拟截止时间，从而导致调度器更早地选择它们。然而，在当前内核中，这种隐式优先级只有在调度器寻找新的任务运行时才会生效。如果一个延迟敏感的任务带有短时间片醒来，它可能仍需等待当前任务耗尽其时间片（可能很长）之后才能运行。不过，Zijlstra 的补丁系列改变了这一点，允许一个任务在虚拟截止时间更早时抢占另一个任务。这一变化为短时间片任务提供了更一致的调度时间，同时可能会稍微降低长时间运行任务的运行速度。
不过，还有一个悬而未决的问题：如何指定某个任务应获得较短的时间片？在当前的内核中，非实时进程无法告知内核其时间片应为多少，因此这个补丁系列增加了这一功能。具体来说，任务可以使用 sched_setattr() 系统调用，在 sched_attr 结构体的 sched_runtime 字段中传递所需的时间片（以纳秒为单位）。在当前的内核中，这个字段仅用于截止时间调度。通过这一新增功能，任何任务都可以请求较短的时间片，这将导致它被更早运行，并且可能会更频繁地运行。然而，如果请求的时间片过短，任务将会频繁被抢占，从而整体运行速度变慢。
允许的时间片范围为 100µs 到 100ms。对于好奇的读者，Zijlstra 在该补丁的变更日志中展示了各种时间片选择的结果，使用了令人印象深刻的 ASCII 艺术图。
这些更改处于相对早期的状态，并且似乎可能需要修订才能考虑合并。除此之外，与控制组的交互尚未进行调查，可能会出现不正常的情况。但是，一旦细节得到处理，EEVDF 调度器应当会达到准备广泛使用的阶段。