当 BPF 邂逅 CPU 调度器

本文地址：https://www.ebpf.top/post/cfs_scheduler_bpf

1. 前言

BPF 从最早局限于过滤网络数据包开始，现在已经在系统观测、网络优化和安全等诸多领域得到了广泛的应用；在内核 5.6 和 5.13 版本中针对 TCP 拥塞算法的场景，分别引入了 STRUCT_OPS 和调用内核函数的能力，（详情可参见 深入浅出 BPF TCP 拥塞算法实现原理 ），同时 io_uring 机制也可运行 BPF 程序 ，也为 BPF 在更多场景中的应用提供了更多的想象力。

截止到目前内核中对于 BPF 程序类型支持大概 30 多种，但是 BPF 在调度器方面还未有太大的进展，这个状况在今年的 9 月取得了进展，来自 Facebook 的 Roman Gushchin 提交的一个内核 patch 将 BPF 程序引入到了内核调度器模块，根据 Facebook 内部的测试表明主要网络负载的延迟得到了改善且 RPS 有 1% 左右的提升，虽然这个机制还在早期，而且还存在一些争议，但是这个 patch 的确打开了 Linux 内核调度器与 BPF 的对话窗口。

在内核上游代码演进缓慢和大量存量生产环境不能够及时跟进内核版本演进的困境下，通过 BPF 程序来定制内核调度器的核心逻辑，配合 BPF 用户空间程序的灵活调整和控制，会给更多的场景带来更多方案的可能，例如在离线混部中的离线与在线的抢占控制，当然这只是一家之言，还有待时间验证。关于 Linux 调度器和在离线混部的相关资料可参考 Linux 进程管理 和 混部之殇 - 论云原生资源隔离技术之 CPU 隔离 。

Linux 进程调度器大致经历了 O(N)/O(1)/CFS 等阶段，2.6.23 内核版本后，CFS 作为默认调度器使用。在没有实时进程的系统中，几乎所有的调度都是由 CFS 完成的，以至于大多数人可能只是把它当作 " 调度器 “。CFS 是一个复杂的实现，通过一套努力学习的启发式方法，试图使各种工作负载的性能最大化，并有一些参数调整来调整启发式方法需要帮助的情况。主流的 CFS 调度器，基于进程优先级、红黑树数据结构和虚拟运行时间（vruntme），通过选取 vruntime 最下的进行调度，兼顾了效率和公平性，可适应大多数通用场景，但是 CPU 调度也是一项复杂的任务，在特定场景下，CFS 的结果并不总是被所有用户认为是最佳的。

CFS 调度器为了调度吞吐量和公平性考虑，会通过进程最小运行保护（sched_min_granularity_ns）、唤醒抢占时间（sched_wakeup_granularity_ns）、新进程加入保护等手段进行优化，但这对于我们想实现完全的进程调度控制可能会带来一定的麻烦；最佳的调度策略应基于工作负载而变化，所以能够根据需要通过 BPF 程序调整调度策略是非常具有价值的。

2. SCHED 类型 BPF 程序

这种灵活控制的场景，这正是 BPF 在其他内核模块得到快速发展的主要原因。BPF 程序在保证安全和速度的前提下为用户提供了改变策略的灵活性，这也适用于像 CPU 调度器这样的性能关键子系统。

Roman Gushchin 通过对 CFS 各种参数调整的效果进行了广泛的研究，发现它们中的大多数对工作负载的性能没有什么影响。最后，将其归结简单的决定：

换句话说，我们的部分工作负载通过让长期运行的任务被短期运行请求的任务抢占而受益，而一些只运行短期请求的工作负载则通过从不被抢占而受益。

Roman Gushchin 的补丁集为影响 CPU 调度器决策的程序创建了一个新的 BPF 程序类型（BPF_PROG_TYPE_SCHED）。该类型程序定义了 3 个挂载点：

• cfs_check_preempt_tick 在处理调度器的周期性定时器 tick 时被调用；然后附加在此处的 BPF 程序可以查看哪个进程正在运行。基于 BPF 程序返回值进行不同的行为：

  • < 0 表示防止抢占，该进程应该被允许继续运行；
  • > 0 会通知调度器应该进行进程切换，从而迫使抢占发生；
  • == 0，则由调度器决定，就像钩子没有被运行一样；

• cfs_check_preempt_wakeup 在进程被内核唤醒时被调用；基于 BPF 程序返回值进行不同的行为：

  • < 0 将阻止该进程抢占当前运行的进程；
  • > 0 将强制抢占；
  • == 0 则由调度器决定；

• cfs_wakeup_preempt_entity 与 cfs_check_preempt_wakeup 类似，但是当一个新的进程被选择执行时，被调用，并能影响决定。基于 BPF 程序返回值进行不同的行为：

  • < 0 的表示不进行抢占；
  • > 0 强迫抢占；
  • == 0 则由调度器来决定；

作者也提供了一个 BPF 调度器程序样例，我们可以在 rgushchin/atc 进行查看。

代码框架如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

SEC("sched/cfs_check_preempt_tick")
int BPF_PROG(tick, struct sched_entity *curr, unsigned long delta_exec)
{
	// ...
}

SEC("sched/cfs_check_preempt_wakeup")
int BPF_PROG(wakeup, struct task_struct *curr, struct task_struct *p)
{
	// ...
}

SEC("sched/cfs_wakeup_preempt_entity")
int BPF_PROG(preempt_entity, struct sched_entity *curr, struct sched_entity *se)
{
	// ...
}

在 Facebook 内部，Roman Gushchin 表示通过使用这些 hook 点的测试效果 " 看起来很有希望 “。

3. 总结

通过该补丁集，Roman Gushchin 希望能引发一场关于如何在调度器中使用 BPF 的对话，但是也有部分调度器专家也表达了顾虑，认为补丁提供的机制可能会导致大家针对各自的场景以特定方式的进行微优化，而对推动社区在调度器上进行更大力度的优化造成障碍。自然这是一个众口难调的话题，存在共性就会存在个性化，能够提供个性化定制的手段大多数场景下都会是一个不错的方案。尽管目前围绕调度器和 BPF 的讨论还很平淡，而且反馈还偏少，但是相信这将是一个崭新的开始，BPF 程序控制调度器更长期应该会是调度器的良好补充，而不是调度器发展的一个障碍。

不管是好是坏，Linux 内核为各种各样的用户服务；为每一个用户提供最好的解决方案总是一个挑战，为每个用户提供更个性化的需求也是未来发展的一个方向，毕竟内核的代码开发不可能一直走在做加法的路上，将更多的能力提升至用户空间，或许会是稳定和效率两者共同作用的结果。

其实 Roman Gushchin 并不是唯一的尝试者，Google 也在进行类似的工作，只是他们更加激进，希望将调度器的代码在用户空间实现，其核心目的也类似，是的调度器的变化和调整更统一开发、验证和部署，这多少有些 DPDK 在用户态处理网络数据包的思路。如果对于只是对于某些热点路径优化，本次的 patch 提交则可以满足，相关议题参见 Google ghost CPU Scheduler 中的 eBPF。除了使用 BPF 程序加速调度外，Google 还使用其进行调度延时统计和调度算法空闲时间统计。

ghOSt 是一个由 Google 开源的框架，用于在 Linux 环境中实现通用的调度策略委托给用户空间进程。通过用户空间的程序可以控制将哪些任务运行在哪个 CPU。ghOSt 使用 BPF 加速需要发生在调度边缘的策略行动。BPF 程序被用来最大化 CPU 利用率（pick_next_task），最小化抖动（task_tick elision）和控制尾部延迟（select_task_rq on wakeup）。

最后，我们也期待更多 BPF 在内核模块中场景化的落地！

4. 参考

• Controlling the CPU scheduler with BPF

• Early Patches Bring BPF To The Linux Scheduler

• eBPF in CPU Scheduler Google

• ghOSt: Fast & Flexible User Space Delegation of Linux Scheduling schedghostidle.c

• patch

• bpf-next google addr