使用 sched_ext 定制 Linux 调度器¶
标题:Designing Custom Linux Schedulers with sched_ext
日期:2025/01/23
作者:Andrea Righi
链接:https://www.youtube.com/watch?v=jsLjg9tGuVI
注意:此为 AI 翻译生成 的中文转录稿,详细说明请参阅仓库中的 README 文件。
好的,谢谢 Candace。大家好,非常高兴来到这里。我叫 Andrea Righi,是 NVIDIA 的内核工程师。让我切换到幻灯片。希望每个人都能看到幻灯片。我们今天将讨论调度。
本次网络研讨会的范围是引导大家了解一项名为 sched_ext
的技术。我会从一些调度理论开始,以便大家能更熟悉这个话题。我想提一下,大约两年前,David Vernet 在 Kernel Recipes 上有一个介绍 sched_ext
和如何设计调度器的演讲。但自那以后,很多事情都发生了变化。因此,我借此机会做一个关于调度的一般性更新演讲,特别是关于 sched_ext
,以及如何使用这项技术进行自己的实验。
这是议程:我们将从一些调度通用概念开始。然后我们将转向 sched_ext
API,以及如何使用它进行实验和一些动手操作。就像 Candace 说的,请随时提问。我会尽量留意聊天。看到了一些熟悉的名字。我们将在幻灯片和演示之间切换,所以一切都应该是互动的,希望不要太无聊。我们也会看到一些演示。
期望是,我希望大家通过观看本次网络研讨会就能熟悉 sched_ext
,但我明白这是一个非常雄心勃勃的目标。所以,至少我希望我能激发大家的一些好奇心,或者让大家看到一些概念,你们可以使用它并做自己的调度实验,甚至有可能设计自己的调度器。
好的,让我们开始。但这次我想做些不同的事情。通常我先做整个介绍,然后转向演示。这次我想从演示开始,然后看看发生了什么,再尝试理解为什么会发生以及如何解决。让我切换到这里。希望你们能看到。让我把自己移下来一点,这样你们能看到 CPU 利用率。
我希望大家能看到。如果你们好奇,我正在使用一个名为 CachyOS 的发行版,它基本上是一个 Arch 发行版。但现在 sched_ext
已经上游了,所以所有发行版都在慢慢支持它。我想特别感谢 CachyOS,因为他们帮了我们很多忙,他们一直在通过测试调度器帮助我们。所以我使用这个发行版,它也非常好,sched_ext
在这个发行版中集成得非常好。
好的,让我们从一个例子开始。这是 Terraria,一个很酷的游戏,你走来走去,建造东西,杀死怪物。你们能看到下面的帧率吗?希望如此。如果你们看到了帧率,请在聊天里说“是”。好的,没有,那只是为了让大家互动一下。是的,它以 60 fps 运行,这很好,因为如果一个游戏以 60 fps 运行,意味着… 人类眼睛… 这并不完全正确,但我们可以将人类眼睛建模为一个以 60 fps 采样的设备。所以我感知到游戏是流畅的,玩起来很好。
现在,如果我开始一个内核编译会发生什么?我现在在后台构建内核,同时玩游戏。你们可以看到这里的 CPU 利用率达到了 100%,所有核心都很忙。如果我回到游戏,是的,你们看到它相当卡顿,这就是玩家所说的“lag”(延迟)。这是非常强的延迟,因为我从 60 fps 跳到了 25、20 fps,甚至更糟,因为它不是稳定在 20 fps,而是很低且非常不可预测。这带来了非常糟糕的游戏体验,因为你们看到我的角色在加速然后减速。
那么,如果我加载一个不同的调度器会怎样?这就是 sched_ext
允许你做的事情。你可以在系统运行时加载一个作为 BPF 程序实现的调度器。我现在正在运行另一个调度器。现在有另一个调度器在运行,我的游戏现在运行得相当流畅,又是 60 fps 了。我可以玩游戏。CPU 利用率仍然到处是 100%,内核仍在编译,游戏也在运行,我似乎可以同时做这两件事。这好多了。
如果我停止这个调度器,一切就会回退到默认的 Linux 调度器,我们又回到了大约 17、20、20 fps 的状态。所以,让我们停止这个,回到幻灯片。
好的,我们有一个调度问题,对吧?显然。为什么会发生?我们如何解决?为了做到这一点… 到目前为止你们有任何问题吗?我的意思是,肯定有很多问题,因为我还没说什么,只是展示了演示。但我想问题很清楚。这是一种极端问题,因为玩家通常不会在玩游戏的同时编译内核。但这只是为了突显某些用例可以大幅改进。
Mario: 这个工具在任何发行版上都有效吗?
Andrea: 它已经在 6.12 版本中合并到上游了。所以任何提供 6.12 内核的发行版都应该启用了 sched_ext
,这意味着你有允许编写和加载调度器的内核组件。当然,你需要用户空间的调度器,可以是预编译的,也可以自己编译。所有东西都是开源的。像我现在使用的 CachyOS 发行版从 6.8 版本左右就已经支持了。Ubuntu 将在 25.04(Plucky)中拥有它。Ubuntu SUSE Tumbleweed 已经有了带 sched_ext
的内核。Red Hat 我不确定时间,但他们显然会在发行版拥有 6.12 内核时跟进。一旦发行版拥有 6.12 内核,你们就会有这个工具。
Piotr: 这个问题以前没有发现吗?如果是,之前有没有尝试解决它?
Andrea: 我们会讲到这个,我会解释为什么我们看到这个问题。Piotr,正如你在我们的对话中提到的,你无法制作一个让每个人都满意的调度器。这正是关键点,也是我要讲的。
让我们定义一下调度器。调度器是一个内核组件,它决定每个任务在哪里运行、何时运行以及运行多长时间。这意味着… 哦,视频模糊了吗?你们能看到幻灯片吗?… 基本上,你们可以把调度器看作一个进行 CPU 分配和时间分配的组件。你需要决定每个任务在哪里运行、运行多长时间以及以什么顺序运行。概念上看起来简单,但在实践中可能变得非常复杂。调度是一个非常不简单的问题,有很多很多极端情况。
调度器的目标是公平:所有任务在某个时刻都应该获得一些时间、一些 CPU 时间。你不希望任务永远或无限期地停滞,所以每个人都应该有机会运行。你们还需要做优化决策。例如,通常你们希望尽可能将任务保持在同一个 CPU 上运行,因为缓存局部性(cache locality)。或者至少希望将它们保持在共享一些缓存的核心上,或者在同一个 NUMA 节点上(如果你们有更复杂的拓扑结构)。在设计调度器时需要考虑这些优化决策。否则,你们就没有以最佳性能使用系统。
在这样做的同时,调度器还需要反应快速,即低开销。这并不意味着调度器本身在计算上是密集型的。实际上恰恰相反,调度器应该在小的 CPU 突发中运行,并尽可能快地决定下一个谁运行。原因是,如果你们查看 CPU 负载,应该看到如果 100% 的 CPU 时间都很忙,这是一个好迹象。如果这 100% 的 CPU 时间主要是用户空间时间,而不是调度器本身,那就很好。如果你们的调度器占用了一个 CPU,那它运行得就不太好,你们增加了太多开销。
最后一点,通用性,基本上是本次演讲的主题。问题是调度器应该适用于所有架构和每种工作负载。一个好的调度器需要让每个人都满意,而设计一个在任何地方、为每个人工作的调度器模型是非常困难的。
Mario(在问答区): 这个程序类似于 cron 吗?还是我们在讨论不同的东西?我不确定指的是哪个程序。
Andrea: 我猜是类似于 cron 的… cron?哦,cron!好的,让我打开问答区… “程序类似于 cron”… 我得说我并不熟悉你指的是什么?我只知道 cron job,那个在特定时间启动任务的东西。希望你会回来… 哦,是的,我指的是那个。所以 cron 是… 使用 cron 你们可以在特定时间启动作业或任务,但它们实际上并不对某些工作负载进行优先或降级处理。这有点不同… 我的意思是,cron 更像是一个管理工具,当你们需要自动化运行一些命令等等时使用。cron 做不到的是:当你们有一堆任务在系统中竞争获取 CPU 时,如何将它们分配给 CPU?如何决定它们运行的顺序?以及为每个任务分配多少时间?所以,你们可以把 cron 看作一个调度器,但 cron 要简单得多。Cron 更像是一系列你们想在特定时间执行的任务,然后自动启动它们,设置它们。也许你们想在某个时间点开灯之类的事情。
聊天区有几个问题。看起来… 是的,我错过了那个。在视频模糊之后,Devender 问:sched_ext
会取代我们默认的调度器吗?
Andrea: 不,我认为我们仍然需要默认调度器。就像我说的,通用性是这里的关键词。默认调度器需要尽可能通用。我们需要一个默认的调度器,它做出所有可能的折衷,让每个人… 我不会说让每个人都开心,但至少让每个人不至于太不开心。
事实上,让我转到下一张幻灯片。这就是关于 Linux 中的调度。所以 Linux 的策略是拥有一个调度器,一个统治所有任务的调度器。过去几年,我们有许多提案,比如拥有可插拔的调度器,或者拥有多个调度器。这个想法总是被拒绝,有充分的理由。其中之一是性能问题,你们不想在调度器代码中添加额外的抽象层,调度器代码应该被视为内核中完全的热路径(hot path),在那里放置的逻辑越少越好。但我认为更重要的原因是,如果我们只有一个调度器,所有内核开发人员就被迫联合起来,尽可能做出最好的调度器。然而,这是很久以前的事了。
例如,如果你们看这张幻灯片,在 6.6 之前我们使用 CFS(完全公平调度器)。在 6.6 之后,调度器变成了 EEVDF(基于截止时间的调度器)。CFS 工作了大约 15 年,而且运行良好。但那时候系统要简单得多。我们没有像现在这样多样化的异构工作负载池,特别是考虑到现在 Linux 运行在桌面、手机上(我现在用的手机就在运行 Linux)、HPC 系统上。过去 Linux 更像是服务器系统,现在它更多地进入我们的日常生活,也用于终端用户设备。Linux 游戏也正在兴起。
一方面,我们有更多的需求来区分 Linux 中典型的工作负载和使用方式。另一方面,我们有更复杂的架构,比如现在的复杂芯片(dies)在同一个封装中有异构核心(例如 big.LITTLE 或 E-core 和 P-core)。在同一系统、同一个封装中,你们有优化性能的核心和优化能效的核心。所以如果你们决定一个任务在这里运行,可能会影响性能和功耗。调度器需要处理的逻辑要复杂得多。
这就是 sched_ext
最终被提出的主要动机之一,也正如我在幻灯片中提到的,进行实验非常困难,上游化更改也非常困难。实验部分:是的,因为如果你们更改了调度器中的某些东西,需要重新编译内核,需要重启。这在生产环境中通常无法做到,因为它有风险,而且有时在大型云环境中重启系统需要重新预热所有缓存,这是一个非常昂贵的操作。第二部分,上游化更改困难,意味着再次强调通用性。调度器需要尽可能通用。如果你们发现某些东西对你们自己工作得非常好,但对其他人不起作用,它就不会被合并。
这些是非常严格的约束。这两件事使得调度开发非常困难,相当难以接近,除非你们有很多年经验。而且你们在能做的事情上受到限制。这就是为什么提出了 sched_ext
,并最终在 6.12 版本合并。
现在,我们可以将调度策略实现为 BPF 程序。关键特性是:
你们可以设计自定义调度器,就像我一开始展示的那个。回答之前的问题:它并不比默认的 EEVDF 调度器“更好”。它在一般情况下并不更好,它在那个特定用例下更好。所以关键是专业化,这是
sched_ext
带来的一个重要特性。另一个(我个人最喜欢的)是快速实验。因为有可能在内核中重新编程(如果你们熟悉 BPF 的话)。BPF 本质上是内核中的一个 JIT(即时编译器)。你们可以把 BPF 程序看作一个不会使内核崩溃的内核模块,它在一个安全的沙箱中运行,对内核中的一切拥有读取访问权限(基本上)。在
sched_ext
中,你们可以在 BPF 程序中做出调度决策。这意味着你们可以加载程序并观察运行情况。它不会使系统崩溃,因为如果你们访问了不该访问的内存区域,或者做错了什么,验证器(verifier)会阻止加载程序。或者如果你们导致任务停滞、引入某种饥饿或死锁等运行时问题,sched_ext
核心实现了一个看门狗(watchdog)。如果任何任务在可配置的一段时间内没有被调度,sched_ext
内核核心部分将踢出你们的调度器,并将所有任务透明地迁移回默认调度器。我认为这非常强大,因为你们实际上可以进行测试。通常在内核开发中,一次测试到下一次测试的周转时间非常长:编辑、编译、测试。在用户空间,你们有编辑、编译、测试的快速工作流。在内核中你们没有这个。但有了sched_ext
,你们可以有这种快速工作流。我认为这可能是这项技术带来的最有用的特性。
这是一个很长的问题回答,但我们继续前进。让我看看是否有其他问题。
问答区问题: 将调度器作为 BPF 程序运行是否会产生相对于没有 BPF 的开销?
Andrea: 直觉上我们倾向于说“是”,BPF 当然有一个额外的层,所以会增加开销。但再次强调,正如我之前提到的,首先,调度器本身并不是 CPU 密集型工作,它只需要快速反应,这是唯一的要求。此外,BPF 代码实际上是内核代码。即使它是编译成 BPF 字节码,当它被加载时,有一个 JIT(即时编译器),字节码会被翻译成机器指令。所以它就像运行内核代码一样。因此,基本上没有开销。我们做了很多测试和测量,即使是像 FIFO 调度器这样简单的东西,与内核中的 SCHED_FIFO
相比,也基本没有区别。实际上有时 BPF 版本运行得更快,但那只是因为分配 CPU 的策略略有不同,并且它比内核中的那个更简单。所以是的,没有开销。
另一个问题: 你会比较 sched_ext
与当前内核默认调度器的优缺点吗?
Andrea: 比较 sched_ext
与当前内核默认调度器的优缺点?嗯,我们已经有很多 sched_ext
调度器,我们经常运行一些比较和基准测试。当然,有些用例下,像专门化的调度器完全超越(beat)了默认调度器,只是因为我们能放宽某些约束。像我之前展示的游戏演示,后台负载下视频游戏的表现,sched_ext
调度器碾压了 EEVDF 调度器。所以一般来说,最好的通用调度器是 EEVDF。但有很多很多用例,通过使用自定义调度器,可以大幅提升性能。因为默认调度器需要是通用的,如果你们有非常特定的工作负载或非常特定的架构,并且只关心自己的用例,有很多低垂的果实(low-hanging fruits)可以轻易超越默认调度器。因为你们可以更少防御性,可以放宽约束,你们不关心公平性,你们就自动赢了。设计一个超越默认调度器的调度器真的很容易。
另一个问题: 是否有客观的方法来评估我们的自定义调度策略是否有效地达到了其目标?
Andrea: 是的,这是一个有趣的问题。我们目前正在努力,我们缺乏的是更多追踪正在发生的事情的工具。在某个时候,我们需要定义一组基准测试的子集,来衡量一个调度器整体的“好坏”。我们在 sched_ext
中有一些针对特定工作负载的相当专门的调度器。例如,我们有 scx_lavd
(由 Igalia 的 Changmin Min 设计),该调度器专门为 Steam Deck 设计。在某些时候,当 Valve 升级到 6.12 内核时,Steam Deck 将会使用一个 sched_ext
调度器来代替默认调度器,因为为游戏设计的专门化调度器在那个特定场景下工作得更好。我们也有通用调度器,比如 bpf_land
(我维护的一个调度器),它足够通用,旨在用于桌面使用。实际上,我现在就是用这个调度器在做这个视频,因为它更好地优先处理延迟敏感的工作负载,比如直播,它工作得很好。同样地,这取决于情况。如果能做一个通用的比较会很好。我做了一些通用的比较,同样,有些用例下默认调度器击败 bpf_land
,其他情况下 bpf_land
击败默认调度器。所以这取决于具体情况。
Q&A 里有三个问题,聊天里还有一个问题。你们是想延迟回答还是现在回答?… 没关系,现在可以。那我们看聊天吧。
Chat 问题: sched_ext
BPF 程序可以访问所有指标吗?
Andrea: 是的,这确实是个好问题。我实际上有一张关于这个的幻灯片… 让我跳过去,我们就讲那张幻灯片,因为没问题,我们不必按顺序来。sched_ext
能做的一件有趣的事情是:你们有一个加载 BPF 字节码的用户空间程序,它使用 BPF 系统调用将字节码注入内核。但用户空间程序保持活动状态,是它保持 BPF 程序活动的。一个非常酷的特性是 BPF 程序与用户空间程序共享内存空间。你们知道有 BPF map 可以高效地在内核空间(或 BPF 空间)和用户空间之间通信。也有 BPF ring buffers(环形缓冲区),它们也是无锁的(lockless),所以你们没有使用系统调用,更像是直接访问,非常高效。你们可以用它们在 BPF 和用户空间之间传递信息。
这意味着你们可以做两件事:
你们可以将一些复杂性从 BPF 卸载到用户空间。例如,我们有一个叫
scx_rusty
的调度器(由 David Vernet 编写)。这个调度器在 BPF 中实现了所有热路径(hot paths)和调度逻辑,但它实现了负载均衡器(load balancer)… 负载均衡器是决定“这个调度域(scheduling domain)负载过重,让我们迁移一些任务到另一个调度域”的组件。scx_rusty
在用户空间实现负载均衡器,并且是用 Rust 编写的。它使用 BPF map 进行通信。我们看到这种方法是最成功的:热路径在 BPF 中实现,将复杂性移到用户空间,并使用 map 进行通信。因为首先,你们可以使用所有用户空间库,访问许多在内核或 BPF 中无法使用的库。你们也解锁了使用任何语言的可能性。另一个很酷的项目是
scx_rustland
(基于sched_ext
的框架)。它实现了一个最小的 BPF 调度器(更像是一个小框架),将所有东西传递给libbpf
。libbpf-rs
是libbpf
的 Rust 绑定。它的作用是:在 BPF 中拦截所有调度事件,通过 BPF ring buffers 将所有内容传递给用户空间守护进程(daemon)。它在用户空间做出 100% 的调度决策,并将调度结果发送回 BPF,然后 BPF 将结果发送给sched_ext
。
所以发生的是:你们有一个用户空间进程在调度系统中所有其他任务,包括它自己(它调度自己)。这对于入门来说是一个很好的起点。如果你们没有太多经验,想开始做调度实验,这是一个非常好的起点。因为你们可以只通过 cargo init
创建一个调度器,导入 rustland
crate,就完成了。你们实现几个 API… 我也做了一个视频展示用 rustland
实现一个调度器有多容易。视频里我实际上是让 ChatGPT 来做,我给它 Rust crate 的文档,让 ChatGPT 实现一个调度器,然后我下载 ChatGPT 的回复并编译,然后运行调度器。真的非常容易。这工作得非常好,你们可以这样做,并且解锁其他更复杂的功能,这些功能在内核中,特别是在 BPF 中不容易实现。BPF 更糟,因为你们的编程模型也受到限制:不能有分配(allocations),不能有无限的周期(cycles),还有所有常见的内核限制:栈大小(stack size)、不能使用浮点指针等等。
Piotr: 我记得测试过那个 ChatGPT 生成的调度器,它运行得相当不错。
Andrea: 是的,我的意思是,当然,结果不如自己写的那么好。我们离让 AI 设计一个好的调度器还很远,还没到那一步。但令人惊讶的是,像编写 Linux 内核调度器这样被认为完全难以接近的事情,居然可以通过简单地询问就能实现。我当时只是说“请使用这个 API 设计一个基于截止时间的调度器”,仅此而已。但谁知道未来呢,我们可能会有 AI 设计的调度器,但现在还没有。我认为值得探索的一件事是收集跟踪数据(traces),分析(profile)系统,然后基于跟踪尝试生成一个调度器图表。尝试猜测你们拥有哪种工作负载,并基于此自动生成一个调度器,使用 sched_ext
在运行时加载它,观察运行情况。或者,也许可以迭代测试更多调度器,做更多更改,持续收集跟踪数据。这在某些情况下可能有效。
好的,让我们回到我们之前讲到的地方。我这里有一些数学,恐怕需要解释一下,因为这是演讲的一部分。关于公平性… 或者除非你们有关于这个的问题?也许… Q&A 里有几个问题… 让我先讲完这个。好的,完美。我们讲完这个,就涵盖了所有理论,然后我们可以做问答,甚至测试。
我想提一下公平性。这个方程驱动了大多数调度器,至少在 Linux 中是这样。这是我之前几张幻灯片提到的公平性概念。CFS(完全公平调度器),它的“完全公平”是什么意思?公平性基本上是你们如何进行带宽分配,按比例权重的 CPU 分配逻辑。看起来复杂,但其实很直观。本质上,你们想做什么:每个任务都有一个权重(weight),这当然是从优先级(priority)派生的。每个任务都有一个权重,你们希望根据其权重相对于其他运行任务的权重,按比例分配运行时间(runtime)。
这里有一个积分(integral),但假设权重是常数,那么这就变成了任务 i 的权重 Wi。假设我们有一个时间区间 T1 - T0,任务 i 的权重是 Wi。你们用它的权重除以正在运行的、竞争 CPU 的其他任务的权重之和,然后乘以时间区间。所以本质上,我们做的事情是:将时间分配给竞争 CPU 的任务,比例与它们的权重成正比。
例如,你们有两个任务,权重都是 1。如果你们把这些值代入公式,一个任务获得时间区间的 50%,另一个也获得 50%。很直观,对吧?我想要两个权重相同的任务,它们应该各获得一半的 CPU。现在假设又有两个任务,一个权重是 3,另一个是 1。再做一次数学计算:一个任务获得 75%,另一个获得 25%,因为它的权重是另一个的三倍(相对权重)。
当然,你们不希望权重更大的任务总是覆盖另一个,否则另一个就会饿死(starve)并永远停滞。但这是提供公平性最优雅、最通用的解决方案。这样,每个人都会有机会运行,他们获得的时间量将与他们的权重成正比。
你们如何实现这个?你们用虚拟运行时间(virtual run time, vrun time)来实现。我想提到这个是因为,如果你们阅读 sched_ext
文档,它被多次提到,人们有时会纠结:什么是虚拟运行时间?就是上面这个。它是这个公式的一个实现。你们通过定义一个传统上为 100 的基准权重(baseline weight)来实现虚拟运行时间。你们用基准权重除以任务权重,再乘以任务的实际运行时间(runtime),并将这个时间计入任务。每个调度滴答(tick),你们选择虚拟运行时间最小的任务运行。
所以,如果一个任务大部分时间在睡眠,它的虚拟运行时间会很小,就会有更多机会运行。一个一直运行的任务,它的虚拟运行时间会很高,所以它获得运行的机会就较少。但这正是我们在这里做的,对吧?按比例优先分配时间区间给任务,也考虑了权重。这个虚拟运行时间公式是 CFS(我们用了 15 年的 Linux 调度器)实现的基础。
那么,问题是什么?问题是它超级通用,在大多数情况下都有效。但缺点是它对延迟(latency)不太好。例如,你们有很多任务在睡眠,有一个任务在运行,但它是周期性的,比如一个接口(interface)或一个视频游戏。现在所有那些睡眠的任务,假设有 100 个,它们的虚拟运行时间很小,它们决定同时运行。那么它们会在那个之前运行的任务之前获得 CPU,因为我们关心公平性。但这会影响延迟敏感的任务,因为它们会在延迟敏感任务之前获得运行机会。
所以我们不得不提出一些临时解决方案(ad hoc solutions)、变通方法(workarounds)和特殊逻辑(special logic)来防止延迟敏感任务被这种逻辑降级。你们可以调整权重和优先级,但要找到非常通用的东西总是很困难。这就是为什么后来我们有了 EEVDF。EEVDF 仍然是公平的,因为它使用了一个截止时间(deadline),就是这里的公式。
EEVDF 给每个任务分配一个截止时间,该时间基于虚拟运行时间(和 CFS 一样)加上任务请求的时间(按比例缩放其权重)。这意味着,假设我是一个延迟敏感任务,通常我会请求一小段 CPU 时间,然后立即释放 CPU。这意味着我的 Δt 非常小,所以我的截止时间会比那些请求更多时间的任务小,因此我有更多机会运行。这允许按截止时间而不是按虚拟运行时间来排序任务(尽管仍然有虚拟运行时间分量来保证公平)。
此外… 但再次强调,这对于优先处理延迟敏感任务很有效,但同时我还想保证公平,因为这是唯一的调度器(在那个时候)。我还想能够提供公平性。所以 EEVDF(Earliest Eligible Virtual Deadline First,最早合格虚拟截止时间优先)引入了资格(eligibility)的概念,以减轻仅使用截止时间可能导致的公平性破坏。
你们如何减轻?基本上,你们从合格任务中获取最早截止时间的任务。合格任务是那些具有 lag(滞后)… 然后我们定义 lag(在实现中,不是论文中的定义),但你们可以把 lag 看作是一个任务应该获得的理想时间减去它实际获得的时间。所以,如果我得到的时间少于我应该得到的,我的 lag 会大于零,我就有资格运行。如果我的截止时间是最小的,我将最先运行。但如果我的 lag 是负的,意味着我使用的时间比根据完全公平逻辑我应该使用的时间多,我基本上被延迟了,我将没有资格被调度。
好吧,你们不必理解所有这些细节。但想法是:EEVDF 仍然是公平的,仍然是完全公平的,但它也允许延迟敏感任务在短时间内获胜。随着时间的推移,如果某个任务滥用截止时间逻辑,它们仍然会因为 lag 而变慢。所以它很公平,但同时也给了延迟敏感任务更好的运行机会。这很酷,因为我们试图解决的问题就是延迟问题,使 Linux 更具响应性。它解决了问题。同时它仍然提供公平性,这作为通用方法非常好。
但再次强调,有时你们不关心公平性。你们可以放宽公平性约束以获得更好的延迟性能。这就是我在演示的调度器中所做的。之前的调度器(演示中的)只使用截止时间,没有实现 lag。它更像是某种没有资格检查的 EEVDF,它使用不同的截止时间公式。如果有时间我们可以看看。但核心思想是:我完全放宽了公平性约束,这样即使在更长的时间段内,我也能为延迟敏感任务获得更好的性能。这是默认调度器无法做到的,因为它还需要在服务器等许多其他场景下工作良好。像我这样在 sched_ext
调度器中所做的更改如果应用到上游,将是不可接受的,因为它会在某些情况下失效,会对其他工作负载造成性能回退(regress)。但使用 sched_ext
是可能的。
这就是理论部分。我们可以处理其他问题了。让我看看 Q&A… 哇,有很多问题… 好吧,至少我讲完了理论部分… 很好,时间刚好。好,我们按顺序来吧?
John Wyatt: 对于网络密集型多人游戏(如 Marvel Rivals、CS:GO、Dota 2),你会推荐哪个社区调度器?
Andrea: 所以 CS:GO 实际上是一个很好的基准测试游戏,因为它对后台工作负载非常敏感。一旦启动后台任务,FPS 会显著下降。在 sched_ext
仓库(sched_ext
有内核部分,我们还有一个 scx
仓库实现实际的 BPF 调度器)中,可能有三个调度器适合游戏。
最明显的是
lavd
(由 Igalia 的 Changmin Min 编写)。这个调度器是为 Steam Deck 设计的,但它在其他架构上也运行得很好,它对架构没有严格要求。简而言之,这个调度器做的是:检测流水线(pipelines),比如唤醒者(wakers)和被唤醒者(wakie)的关系。它跟踪频率,比如任务被阻塞的频率和被唤醒的频率等等。因为游戏是一个大的流水线:有一个主循环等待一帧,然后场景管理器更新场景,新帧传递给合成器(compositor),可能还有 Wayland 在视频中渲染帧,然后一切回到起点。这是非常周期性的:如果你们以 60 fps 玩游戏,你们需要每 16 毫秒(1/60 秒)完成一次。如果错过了截止时间,你们就会感知到延迟。通过检测这个流水线链,似乎能非常有效地优先处理游戏工作负载。我开头演示的极端例子(玩 Terraria 同时编译内核)中,那些调度器… 我们关心的是 P99 FPS。特别是在电子竞技或有竞争的情况下,你们可能希望保证良好的性能水平,即使后台启动了更新或者像之前提到的 cron 决定运行某些东西。不仅如此,想想 VR 头显或复杂的可穿戴设备,这些设备有许多线程/任务,理论上都是实时(real-time)的。使用优先级或 cgroups 可能非常棘手。所以能够实现一个自动理解并在每次都能找出谁最需要优先级的调度策略非常强大。在游戏领域潜力巨大,我认为sched_ext
可以显著促进 Linux 游戏。所以回答你的问题:对于网络密集型多人游戏,我会说lavd
或bpf_land
。也许rusty
也可以,但bpf_land
和lavd
可能是最好的两个,因为它们以不同方式优先处理延迟工作负载。网络密集型也是延迟问题,你们关心 ping 值、响应时间,特别是在竞技游戏中。
Christina: sched_ext
支持时钟驱动(clock driven)/时间驱动(time driven)的调度实现吗?
Andrea: 是的,可以。sched_ext
很酷的一点是调度器是一个 BPF 程序,所以你们可以做通常在 BPF 中做的任何事情,加上你们可以实现调度回调(callbacks)来实际实现调度器。所以你们可以使用 BPF 定时器(timers)在基于时间的逻辑上触发某些事件。你们也可以… 例如,一个非常有效的做法是添加 kprobes。lavd
或 bpf_land
… 哦,我们还有一个叫 flash
的调度器。flash
和 lavd
实际上都在关键的 futex 内核调用(kernel calls)上添加 kprobes,以确定用户空间任务何时持有用户空间锁,并提升其优先级(boost the priority),即使它的时间片(time slice)到期了,也允许它继续运行。这非常强大,因为你们可以防止用户空间锁的优先级反转(priority inversion)。而且你们不需要引入任何新的内核接口,因为一切都可以通过 BPF 完成。BPF 是纯粹的内核到内核接口,没有用户空间 API(UAPI)限制。通常引入新的内核接口很复杂,因为需要永远维护它们(UAPI 限制)。在这种情况下,就像内核模块一样。是的,你们有高效的方式在内核和用户空间之间通信。但回答你的问题:是的,你们可以通过 BPF 定时器实现时钟驱动/时间驱动的调度实现。
For those less familiar: 对于我们这些不太熟悉调度器的人,是否有预构建的选项可用于 sched_ext
测试,而不必自己编写?
Andrea: 是的,当然。就像我提到的 CachyOS 发行版。也许我可以展示一下。这是 CachyOS… 让我到这里… 抱歉。CachyOS 有一个叫 cachyos-kernel-manager
的工具。如果你们想重新编译自己的内核等等,可以用它。但还有这个 sched_ext scheduler config
。如果你们点这里,会看到一个调度器池。这些是我们在上游 scx
仓库中的调度器,不是全部。你们可以直接选择任何一个,比如 lavd
,我点击应用… 是的,需要输入密码… 现在我在运行 lavd
。所以现在我运行的是不同的调度器,这个也对游戏不错。或者运行 bpf_land
。你们看到还有一组配置文件(profiles)。比如我想要游戏(gaming)配置,我运行 bpf_land
并带游戏配置文件。这里显示需要传递给 bpf_land
的选项。然后点击应用… 再次输入密码… 现在我在运行 bpf_land
。如果我点禁用(disable),就回到了默认调度器。所以如果你们想做实验,这真的很容易。你们基本上不需要做任何事,不需要自己写调度器。或者,你们也可以手动编译并运行它们,就像我之前做的那样。
另一个问题: 运行 scx
?systemctl
?sdx-loader
?啊,是的。sdx-loader
是 CachyOS 等用来加载不同调度器的用户空间组件。所以这是一种调度器管理器,挺酷的。
另一个问题: 你是在建议为特定领域和已知的高级应用程序使用自定义调度器吗?
Andrea: 是的,我的意思是… 是的,这就是重点。调度专业化(scheduling specialization)是 sched_ext
的重点之一。另一个当然是实验。有时我们可能发现一些在一般情况下工作得非常好的东西,如果它确实在一般情况下更好,我们可以将其上游化。所以 sched_ext
的另一个重要用例当然也是实验,能够将其作为改进内核内调度器的新工具。就像加入力量做更多实验,向更广泛的程序员和开发者开放调度开发。同时,让人们能够为不同的应用领域使用不同的调度器。
另一个问题: sched_ext
支持实时调度吗?
Andrea: 嗯,这是个好问题。你们可以将 sched_ext
与 PREEMPT_RT
(抢占式实时)一起使用。实时是一回事,调度是另一回事。实时更多是关于可预测性(predictability),涉及很多关于锁、更改锁语义的代码,因为你们总是应该能够睡眠(sleep)。此外,当然我们可能有保证可预测性的调度要求。例如,内核中有 SCHED_DEADLINE
,它不是 sched_ext
。sched_ext
类(class)实际上… 我有一张关于这个的幻灯片。
当我之前说 Linux 只有一个调度器时,这并不完全正确。我们有一个用于非实时任务的调度器(这样说更准确),因为我们在 Linux 中已经有实时调度器,在 sched_ext
之外。这里是调度类(scheduling classes)的排名。问题是:较高优先级的调度类可以完全覆盖较低优先级的调度类。所以假设你们有一个 SCHED_FIFO
任务在一个 CPU 上运行,如果它在那 CPU 上自旋(spinning),它将完全占用那个 CPU。正常的 sched_ext
调度任务当然不能在那个 CPU 上运行,如果有一个 SCHED_FIFO
任务在运行的话。所以有这个调度类的排名是有道理的,因为目标是提供实时性(real-time),它应该总是优先。
正如你们在这张幻灯片看到的,sched_ext
运行在 SCHED_NORMAL
和 SCHED_BATCH
之下(在 SCHED_IDLE
之上)。这很重要。通常,如果你们加载 sched_ext
调度器,所有 SCHED_NORMAL
和 SCHED_BATCH
任务都会被移到 sched_ext
类。但有一种可能性是使用部分模式(partial mode),在这种模式下,除非你们显式地将它们移到 sched_ext
,否则不会自动移动任何任务。所以你们也可以拥有一个系统,其中只有一部分任务由你们的 BPF 程序(sched_ext
调度器)调度,所有其他任务仍然由默认的 Linux 调度器(公平类,即 EEVDF)调度。
然而,我们从不建议这样做,除非你们确切知道自己在做什么。因为这张幻灯片意味着:如果你们在部分模式下运行,任何在 SCHED_NORMAL
这里的任务都可以完全占用一个 CPU,而 sched_ext
调度器永远没有机会运行。这有点… 我不想说危险,因为最坏情况是 sched_ext
的任务会被停滞。内核中的看门狗会检测到任务在一定时间内没有机会运行,它会踢出你们的 sched_ext
调度器。所以你们不会破坏系统。最坏情况是你们会感知到停滞,直到看门狗踢出你们的调度器,然后一切恢复正常。但要知道,如果你们选择部分模式,可能会遇到这个问题。CachyOS 社区的人熟悉 kthread stall(内核线程停滞),我们遇到过很多关于 kthread 的问题,这通常不是 sched_ext
的问题。例如,如果有一个 SCHED_FIFO
任务在一个 CPU 上运行,当然 sched_ext
会被完全饿死(starved)并被那个 SCHED_FIFO
任务停滞。
哦,抱歉。发生的是:看门狗会检测到“哦,嘿,你们在这个 CPU 上有一段时间没有调度任务了”,但那是因为有一个实时任务在运行。所以看门狗为了安全起见,会踢出你们的调度器,触发一次停滞(stall)。你们会看到停滞。我幻灯片里有一个停滞的例子… 让我翻到那里… 就是这个。如果你们看到这个,当你们的调度器退出时,它会 dump 一个跟踪(trace),你们可以检查它看发生了什么。在这个例子中,有一个 kworker/6
内核线程。这个内核线程的属性是它只能在 CPU 6 上运行。如果你们尝试将它分派(dispatch)到其他 CPU 上,是不行的(由于内核要求)。然而,在 CPU 6 上,有一个叫 yes
的任务(你们知道 yes
是做什么的,它只是打印 yes 等等)。我故意创建了一个 CPU 占用者(CPU hog),作为 SCHED_FIFO
实时调度类运行,占用了 CPU。所以这个由 sched_ext
管理的任务在长达 7 秒甚至更长时间内没有机会运行。因此 sched_ext
检测到这一点并踢出你们的调度器,即使在这种情况下它没有解决任何问题,因为实时任务还在那里。你们对此无能为力,因为它是更高优先级的调度类。
所以实时性再次变得棘手。在玩 sched_ext
时也要记住这些。
我想提到的另外两点,然后我们留时间给其他问题:
调度队列(Dispatch Queue)的概念:这是
sched_ext
的设计方式,即如何通过调度队列(本质上是运行队列)将任务分配给 CPU。你们将任务插入一个队列,sched_ext
核心会负责将任务分派到 CPU 上。SCX_DSQ_LOCAL
是一个关键字,代表每个 CPU 上的一个 DSQ(调度队列)。如果你们使用scx_bpf_dispatch()
到SCX_DSQ_LOCAL
,任务将被添加到分配给该任务的 CPU 的运行队列中。但你们也可以通过发送到
scx_bpf_dispatch()
到SCX_DSQ_LOCAL_ON(cpu)
来迁移任务(指定 CPU 号)。还有一个全局 DSQ
SCX_DSQ_GLOBAL
。 这些都是内置队列。全局队列会被所有 CPU 以 FIFO 模式消耗(consume),而这些本地队列只能由特定 CPU 消耗。所以我们有本地队列和全局队列的概念。此外,你们可以创建用户定义的 DSQ(user-defined DSQs)。如果你们创建自己的 DSQ,可以决定哪些 CPU 可以从中消耗任务。你们可以使用用户定义的 DSQ 来实现例如每 LLC(最后一级缓存)队列、每 NUMA 节点队列或每调度域(scheduler domain)队列等等。
工作流程是:一旦你们将任务插入本地 DSQ(
SCX_DSQ_LOCAL
或SCX_DSQ_LOCAL_ON(cpu)
),它会被内核核心逻辑自动消耗,并将任务分派到目标 CPU。如果本地 DSQ 为空,内核核心将检查全局 DSQ (SCX_DSQ_GLOBAL
) 中是否有任务,并将第一个任务移到本地 DSQ(更准确地说,第一个可用的 CPU 会从全局 DSQ 取任务放到自己的本地队列),然后再次触发相同的逻辑:DSQ 中的第一个任务被消耗并移到 CPU 上运行。如果本地 DSQ 和全局 DSQ 中都没有任务,一个名为
dispatch
的回调将被调用。如果你们在调度器中实现这个回调,可以决定在dispatch
操作中使用什么逻辑。在dispatch
操作中,你们通常从用户 DSQs 消耗任务,可以使用scx_bpf_dispatch()
将第一个任务移到当前 CPU 的本地 DSQ(SCX_DSQ_LOCAL
)。这样,你们就可以将任务分配给 CPU。DSQs:内置的(全局 DSQ、本地 DSQ)只能以 FIFO 模式工作。而用户 DSQ 可以以 FIFO 模式或优先级模式(priority mode) 工作。优先级模式称为
SCX_BPF_DSQ_FLAG_BUILTIN
?… 如果你们使用scx_bpf_dispatch()
插入任务到一个 DSQ,它会以 FIFO 模式消耗。而insert_vtime
(插入虚拟时间)是优先级模式。在后台,它使用一个红黑树(rbtree)按你们指定的值(value)对任务进行排序,该值代表任务在队列中的位置。如果你们传递虚拟运行时间(vrun time),基本上就可以使用这个和一个全局 DSQ 来实现 CFS(完全公平共享调度器)。你们不能同时对一个用户 DSQ 使用 FIFO 和虚拟时间模式,它们是互斥的。但这是一个重要的概念,我想提一下,万一你们想开始用它做实验,因为它有文档,但有点难理解。调度器回调(Scheduler Callbacks):例如,在
enqueue
(任务想要运行时)、dispatch
(CPU 可用时)、runnable
(任务准备好运行时)、running
(任务实际开始运行时)、stopping
(任务停止运行时,因为它要么用完了时间片,要么阻塞在事件上)、wakeup
(当它阻塞在事件上并收到唤醒事件时,我们可以选择一个新的 CPU)等等。这是完整的任务工作流回调。这张图没有文档化,如果我们能把它上传到某处就好了,但我们会把它文档化。这展示了所有与任务工作流相关的回调。
Evans: 权重是如何衡量的?
Andrea: 权重是从 nice 值派生的。内核中有一个逻辑将 nice 级别(-20 到 19)转换为权重,范围从 1 到 10000(这是比例)。默认值是 100,这是传统。同样的逻辑也用于 cgroup。如果你们进入 cgroup cpu.weight
,会找到相同的逻辑。在 sched_ext
中,优先级或权重也是同样的逻辑。你们可以通过… 我没提到,但例如,在调度器中,你们实现所有这些回调。在 enqueue
是任务想要运行时,dispatch
是 CPU 可用时,runnable
是任务准备好运行时,running
是它实际开始运行时,stopping
是它停止运行时(因为它要么用完了时间片,要么阻塞在事件上),wakeup
是当它阻塞在事件上并收到唤醒事件时(我们可以选择一个新的 CPU)等等。还有 exit
。这是完整的任务工作流回调图。这没有文档化,如果我们能把它上传到某处就好了,但我们会把它文档化。
另一个问题: 在默认调度器中,任务是否被分配相同的优先级和时间片?
Andrea: 你们可以使用 nice
和 sched_setscheduler
来调整优先级。我认为时间片是相同的,不能调整。所以是的,这是我已经回答过的一个问题。需要注意的一点是,EEVDF 使用的截止时间是基于时间片的。所以这是关于 EEVDF 的另一个注意事项。有时我们发现更好的方法是使用虚拟运行时间来评估截止时间,而不是添加按比例缩放的请求时间片。像我展示的 vader
调度器,它使用从任务变为可运行(runnable)到释放 CPU 的时间来测量时间片。所以,如果一个 CPU 密集型任务的部分运行时间会越来越大,那么它的截止时间会大大延迟。如果一个任务经常睡眠并不断释放 CPU,它的部分虚拟运行时间会很小(那个值被加到虚拟运行时间上)。结果是延迟敏感的任务会自动获得更短的截止时间,因此它们有更多机会运行。
在 sched_ext
中可以做的另一件很酷的事情是:当你们分派任务或将任务移入 DSQ 时,可以显式地为每个任务分配时间片。这意味着你们可以做一些有趣的技巧。例如,如果你们有一个全局队列变得太长(任务堆积),你们可以分配时间片,比如与睡眠任务数量成反比。这是另一个对某些情况非常有效的技巧,因为这样任务会有更多的上下文切换(context switches),但任务获得运行的机会更多,因为它们的时间片更短。你们基本上减少了平均等待时间(average wait time)。用这种逻辑,一个 FIFO 调度器有时比 EEVDF 表现更好。
另一个问题: 时间片是静态的还是动态的?
Andrea: 你们可以… 让我展示代码以便理解。比如 vader
调度器。这是一个很好的学习 sched_ext
的调度器(注释很多,在 scx
仓库里)。例如,在 enqueue
函数里… 这里,你们看到我是这样将一个任务入队到一个共享 DSQ 的。我分配一个切片(slice),我定义为 task_slice
,它基本上是默认切片 20 毫秒,然后我除以全局 DSQ 中等待的任务数量。所以当任务开始运行时,它拥有这个时间片预算。但在任何滴答(tick)或任何其他回调中,你们可以改变切片。例如,在这里,我可以将切片重置为零,任务基本上就会被抢占(preempted)。这就是如何实现抢占。所以时间片是动态的。你们可以分配预定义的值,或者有默认值,但你们可以在调度器中不断改变和调整时间片,只需在插入任务到 DSQ 时操作,或者例如在这里(dispatch
回调中)… 这是一个任务结构指针 p
,我可以做 p->scx.slice = time_slice
。例如,在这里我说如果在这个 CPU 上有其他任务准备好运行,就从共享 DSQ 消耗任务并运行。但如果没有其他人想运行,并且这个 CPU 上之前的任务还想运行,就重新填充(refill)它的时间片。这是一个优化(如注释所说:如果当前任务用完时间片,且没有其他任务想在这个 CPU 上运行,就重新填充它的时间片,让它再运行一轮)。这样做可以节省一些回调。希望这回答了你的问题。
另一个问题: 我经常一次运行六个编译任务。这种工作负载适合 sched_ext
吗?我能用它减少编译时间吗?
Andrea: 是的,简短回答:是的,可以。你们可以做两件事。如果你们运行 vader
调度器,它实际上… 如果你们在系统中运行这些和其他东西(比如我在编译内核的同时在 YouTube 上看视频或做直播),你们的编译会被减慢,因为它给延迟敏感任务更多优先级。但假设你们在一个构建服务器上,只运行内核编译。我发现使用共享 DSQ(就像 vader
做的那样)可以帮助加快构建速度。实际上我在 NVIDIA 内部为构建服务器做过一些实验。在一个带有 NUMA 节点的英特尔机器上,我们也能为拓扑结构做一些技巧,我们能够将内核编译速度提高 10-15%,这非常显著。但那是针对那个特定架构的,因为它是一个对缓存一致性(cache coherency)非常敏感的老旧英特尔机器。所以如果你们将任务打包到 NUMA 节点或… 在一个没有 NUMA 的普通系统上,使用共享队列,我能够获得大约 4-5% 的速度提升。这发生的原因是:EEVDF 或 Linux 调度器使用每个 CPU 一个运行队列,然后有负载均衡器。数学理论告诉我们,如果有多个服务器(CPU),使用单个队列比每个服务器一个队列更高效。就像去杂货店,如果能去第一个可用的收银台排队会更好。那么为什么 Linux 要那样做?有多个原因:上下文切换更快,因为不需要迁移。另一个原因是缓存一致性(cache coherency)利用得更好,因为你们更有可能(稍微更可能)留在同一个 CPU 上,只在负载均衡器决定时才迁移。但在像构建器这样的特定工作负载中,你们从缓存局部性中获益不多,因为你们生成目标文件后就丢弃所有内容。因此,实际上摆脱每 CPU 队列而使用共享队列更好,因为它可以提高整体核心利用率。这在实践中非常有效。实际上在 bpf_land
中,我添加了一个选项(bpf_land -p
)来做这个,这使你们的调度器对构建器友好。
Candace: 看起来我们快没时间了… Andre,我们时间如何?… 我们有点超时了,但如果还有最后的问题,我们肯定可以回答完。看起来有一个关于小时间片的问题在 Q&A。我想这可能是最后一个问题了?小时间片会导致系统颠簸(thrashing)吗?
Andrea: 是的,没错。如果你们减少时间片,会增加上下文切换的数量,从而增加系统的开销。所以是的,没错。找到正确的平衡总是很困难。时间片大小取决于调度器逻辑决定分配给每个任务多少。
另一个问题: 既然你在 NVIDIA 工作,假设你对机器学习工作负载的调度器非常精通,特别是因为这些任务是同质的(homogeneous),对吗?
Andrea: 老实说,我对机器学习了解不多。我更多的是内核方面的人。我知道该问谁,但就像我之前说的,我们离让 AI 设计一个好的调度器还很远。我们能做的,就像我之前说的,也许是生成更多数据(生成跟踪),并用这些数据喂养一个 AI,也许能得到一些东西。但我没有魔法棒说“嘿,AI,设计最好的调度器”,至少根据我的经验,它产生的结果很差。
Candace: 我们超时快五分钟了… 我们有几个人举手了,不知道你们是否有问题?… Q&A 里有一个关于工作窃取(work stealing)的问题,我想是最后一个问题了。工作窃取在每 CPU 队列之间会是个好主意吗?
Andrea: 是的,工作窃取可以让你们的调度器更加工作守恒(work-conserving),无论是通过使用单个全局队列,还是在负载均衡上更激进(aggressive),都能帮助大规模并行构建工作负载。当然,如果你们能最大化核心利用率,它就有帮助。但再次强调,如果你们发现一些东西在你们的用例下工作得非常好,但很难上游化,那么现在可以使用 sched_ext
。例如,对于一个构建器,使用单个共享 DSQ 更好,那么用 BPF 在 sched_ext
中实现它。这就是为什么一开始我说感觉有很多低垂的果实可以通过使用专门的调度器获得。所以,是的,所有这些事情(工作窃取会是个好主意吗?),你们都可以通过在 sched_ext
中测试快速得到答案。如果你们发现一些有效并且不会对其他工作负载造成回退(regress)的东西,我们可以将其上游化,那对默认调度器会是一个很好的贡献。
Candace: 谢谢 Andre。我将把它交回给 Candace 来结束会议。
Candace: 非常感谢 Andre 和 Shiru(注:可能是会议组织者或主持人)今天的时间。感谢大家的参与。提醒一下,本次录影稍后将在 Linux 基金会的 YouTube 页面上发布,演示文稿副本将添加到 Linux 基金会网站上。希望大家能参加未来的导师会议。祝大家有美好的一天!