LWN：可扩展scheduler class！

关注了就能看到更多这么棒的文章哦～

The extensible scheduler class

By Jonathan Corbet
February 10, 2023
DeepL assisted translation
https://lwn.net/Articles/922405/

总是有人试图将 BPF 引入内核的 CPU 调度器领域，这只是一个时间问题。1月底，Tejun Heo 发布了一个由 30 个 patch 组成的改动的第二版，这个 patch set 是与 David Vernet、Josh Don 和 Barret Rhoden 共同编写的，实现了 CPU 调度方面采用 BPF。显然，通过将调度决策推迟到 BPF 程序就可以做一些有趣的事情，但要说服整个开发社区采用这个想法可能需要不少工作。

BPF 的核心理念是允许在运行时从用户空间加载程序到内核；使用 BPF 进行调度有可能会使调度行为跟现在的 Linux 系统非常不一样。"可插拔（pluggable）" 调度器的想法并不新鲜，比如在 2004 年 Con Kolivas 对另一组注定会失败的 patch 的讨论中就出现了。当时，可插拔调度器（pluggable scheduler）的想法被人们强烈反对。人们认为只有把精力集中在一个调度器上，开发社区才有可能找到可以适配所有工作场景的方案，也就是不需要用乱七八糟的各种特殊用途调度器来塞到内核里。

当然，内核只有一个 CPU 调度器的这个想法并不十分准确；实际上是存在几个调度器的，包括 realtime 调度器和 deadline 调度器等，应用程序可以从中选择。但是，几乎 Linux 系统上的所有工作都采用了默认的 "完全公平调度器， completely fair scheduler" 下运行的，从嵌入式系统到超级计算机的各种工作负载的管理方面它的工作确实很可靠。人们总是希望有更好的性能，但是多年来几乎没有人提出要求建立一个可插拔的调度器机制。

那么，为什么现在要提出 BPF 机制呢？很明显是预期到了会有长篇讨论，这组 patch 的封面邮件中以很大的篇幅描述了这项工作背后的动机。简而言之，主要观点是在 BPF 中编写调度策略的能力大大降低了试验新的调度方法的难度。自从 completely fair scheduler 引入以来，我们的工作场景和它们所运行的系统都变得更复杂了。人们需要通过实验来开发适合当前系统的调度算法。BPF scheduling class 就可以采用安全的方式进行实验，甚至不需要重新启动测试机。BPF 编写的调度器还可以提高小众的工作场景的性能毕竟这些工作场景可能不值得在 mainline kernel 中实现相关支持，而且还更容易部署到大型系统中。

scheduling with BPF

这个 patch set 增加了一个新的调度类（scheduling class），叫做 SCHED_EXT，可以像其他大多数调度类一样，通过 sched_setscheduler()调用来选择（选择 SCHED_DEADLINE 的步骤要复杂一点）。它是一个非特权类（unprivileged class），意味着任何进程都有权限把自己放入 SCHED_EXT 中。SCHED_EXT 在优先级堆栈中被置于 idle class（SCHED_IDLE）和 completely fair scheduler（SCHED_NORMAL）之间。这样就确保了 SCHED_EXT 调度器方式的进程都不可能阻塞采用 SCHED_NORMAL 运行的普通 shell 会话进而强制接管系统。这也表明，在使用 SCHED_EXT 的系统上，人们实际上是希望大部分 workload 都采用该 class 来运行。

BPF 编写的调度器对整个系统来说是全局的；没有规定不同的进程组可以加载它们自己的调度器。如果没有加载 BPF 调度器，那么任何被放入 SCHED_EXT 类中的进程将被当作 SCHED_NORMAL 类来运行。不过，一旦加载了一个 BPF 调度器，它将接管所有 SCHED_EXT 任务的责任。还有一个神奇的函数，BPF 调度器可以调用（scx_bpf_switch_all()），它将把所有运行在实时优先级以下的进程移到 SCHED_EXT 中。

实现调度程序的 BPF 程序通常会管理一组调度队列，每个队列可能包含等待 CPU 执行的可运行的任务。默认情况下，系统中每个 CPU 都有一个调度队列，还有一个全局队列。当一个 CPU 准备好运行一个新的任务时，调度器会从相关的调度队列中抽出一个任务并将其交给 CPU。调度器的 BPF 端主要实现为一组通过操作结构调用的回调，每个回调都会通知 BPF 代码一个事件或一个需要做出的决定。这个列表很长；完整的列表可以在 SCHED_EXT 代码分支的 include/sched/ext.h 中找到。这个列表包括：

• prep_enable()
  

• enable()
  第一个回调通知调度器有一个新的任务正在进入 SCHED_EXT；调度器可以在这里设置该任务相关的任何数据。prep_enable() 允许阻塞，也就可以进行内存分配。 enable()不能阻塞，就是实际上启用新任务的调度的动作。
  

• select_cpu()
  为一个刚刚被唤醒的任务选择一个 CPU；它应该返回将任务放在哪个 CPU 上的对应的 CPU 编号。这个设计可能会在任务真正运行之前再重新检查一下，这个 API 也会用来在调度器选择了当前空闲的 CPU 的时候唤醒所选的 CPU。
  

• enqueue()
  将一个任务排入调度器来进行执行。通常这个 callback 会调用 scx_bpf_dispatch()，将任务放入选定的调度队列中，最终从那里运行。此外，该调用提供了 task 运行后应给予它的时间片的长度。如果时间片长度是 SCX_SLICE_INF，那么当该任务运行时，CPU 将进入 tickless mode。
  

  值得注意的是，enqueue() 并不一定会把任务放到任何调度队列中；如果任务不应该立即运行的话，它可以暂时把这个任务放在某个地方。不过内核会持续跟踪它，确保没有 task 会被遗忘掉；如果一个 task 搁置太久（默认为 30 秒，不过可以缩短这个超时时间），BPF 调度器就会被 unload 掉。
  

• dispatch()
  在 CPU 的调度队列为空时会被调用；它应该将任务调度到该队列中从而保持 CPU 繁忙。如果调度队列仍然是空的，调度器就会尝试从全局队列中抓取 task。
  

• update_idle()
  当 CPU 进入或离开 idle 状态时，这个 callback 会通知调度器。
  

• runnable()
  

• running()
  

• stopping()
  

• quiescent()
  这些都是用来通知调度器一个 task 的状态变化；当一个 task 变成 runnable 状态、或者开始在 CPU 上运行、从 CPU 上退下来、不再 runnable 时，就会分别被调用。
  

• cpu_acquire()
  

• cpu_release()
  通知调度器这个系统中 CPU 的状态。当一个 CPU 变得可供 BPF 调度器管理时，对 cpu_acquire()的调用就会通知到它。当一个 CPU 不再可用时（比如可能有一个 realtime scheduling class 的 task 占用了这个 CPU）就会通过 cpu_release()来通知。
  

还有许多其他的回调函数，用来管理 cgroup、CPU affinity、core scheduling （CPU 核心管理）等等。还有一组函数供调度器使用来影响调度决策。例如 scx_bpf_kick_cpu()可以用来抢占一个运行在指定 CPU 上的 task，并回调到调度器中挑选一个新的 task 在那里运行。

Examples

最终得到的是一个 framework，可以在 BPF 代码中实现各种各样的调度策略。为了证明这一点，这组 patch 也包括一些调度器的例子。有一个 patch 提供了一个最小的 "dummy" 调度器，对所有的 callback 都使用默认值；它还实现了一个基本的调度器，实现了五个优先级，并展示了如何将 task 放到 BPF map 里。"虽然不是很实用，但这作为一个简单的例子是很有用的，可以演示不同的功能"。

除此之外，还有一个 "central" 调度器，它将一个 CPU 专用于调度决策，让所有其他的 CPU 都自由地运行 workload。后来的一个 patch 就给该调度器增加了 tickless 支持，并得出结论：

虽然 scx_example_central 本身太简陋以至于不能作为生产环境中的调度器来用，但可以用同样的方法建立一个功能更强的 central scheduler。谷歌的经验表明，这样的方法对某些应用（如 VM hosting）来说有很大的好处。

如果觉得这还不够的话，scx_example_pair 实现了一种使用 control groups 的 core scheduling 功能。scx_example_userland 调度器 "在用户空间实现了一个相当简单直接的排序列表 vruntime 调度器，以证明大多数调度决策可以委托给用户空间来做"。这组 patch 最终实现了 Atropos 调度器，它有一部分是用 Rust 编写的很复杂的用户空间的组件。封面邮件中还描述了一个 scx_example_cgfifo，但是没有包含在这组 patch 中，因为它还是依赖一些尚未合入的 BPF rbtree 补丁。它 "为单个 workload 提供了 FIFO 策略，并为 cgroups 提供了一个扁平化的分层的 vtree"，而且显然在 Apache 网络服务 benchmark 中测得了比 SCHED_NORMAL 更好的性能。

Prospects

这组 patch set 已经是第二次发布了，到目前为止，还没有引来大量的评论；也许是它太大了的原因。不过，Scheduler 维护者 Peter Zijlstra 对第一个版本做出过回应，他说："我讨厌这一切。Linus 在过去多次对 loadable scheduler 进行过拒绝（NAK），而这又是一个这样的工作，并且还是基于 BPF 的，这是一个新增的缺点”。不过，他接着 review 了许多部分的 patch，这表明他可能不打算直接拒绝这项工作。

即便如此，BPF scheduler class 对于 core kernel 社区来说影响显然很大。它增加了超过 1 万行的核心代码，并暴露了许多迄今为止一直被隐藏在内核深处的调度细节。这相当于是承认通用调度器不能让所有的 workload 都满意；一些人可能会担心，这将标志着为实现这一目标而进行的 completely fair scheduler 工作就此结束，以及在 Linux 系统中增加碎片化的实现。BPF 调度的开发者的观点恰恰相反，自由试验调度模型的能力反而会加速对 completely fair scheduler 的改进。

后续会如何发展还是很难预测，只能说到目前为止，这个 BPF 巨无霸已经成功地克服了它所遇到的几乎所有反对意见。将核心内核功能局限在内核本身的日子似乎就要结束了。很期待能看到这个子系统启用哪些新的调度方法。

全文完
LWN 文章遵循 CC BY-SA 4.0 许可协议。

长按下面二维码关注，关注 LWN 深度文章以及开源社区的各种新近言论～