Linux任务调度(6): CFS不是银弹
Posted 2023-11-20 12:59 +0800 by ZhangJie ‐ 1 min read
演进过程
首先，再次回顾下下Linux进程调度器的一个发展历史：
- v0.01~v2.4.x: the very first scheduler，复杂度O(n)
- v2.6.0~v2.6.22: O(1) scheduler，复杂度O(1)
- v2.6.23~: Completely Fair Scheduler (CFS)，复杂度O(log(n))
前一篇文章中我们介绍了完全公平调度器CFS（Completely Fair Scheduler)，我们介绍了它的核心思想，并结合我们之前的几个顾虑给出了在CFS调度器下如何来解决顾虑的问题。CFS自从诞生以来，一直是Linux内核的默认调度器实现。它也先后经历了多次演进，如前文提到的对sched_entity的抽象改进以实现对组调度（group scheduling)的支持。看上去CFS已经是非常好的调度器实现了，事实上CFS也不是银弹。
没有银弹
尽管Torvalds、Ingo等人坚持希望在内核中维护一个通用的调度器实现，来支撑不同的场景。这个理想很丰满，但是从实践上来看，确实在某些领域CFS的表现仍然并不是很令人满意。
比如在个人桌面场景下，也不需要NUMA、也不要求在4096个处理器上具有良好扩展性，有没有比CFS更合适的调度器实现方案呢？那么在移动设备中呢？在其他更广泛的应用场景下呢？我们真的需要一个以一当十的CFS scheduler吗？还是需要一个个更适应各自领域的专用的scheduler？
BFS调度器
2009年，Con Kolivas 又带着他的新版本调度器实现方案BFS回归了内核开发社区，BFS是Brain Fucker Scheduler的简称，挑衅意味浓厚，这与其主张的希望为Linux kernel在不同场景下允许提供多样化的scheduler方案相关，而Torvalds、Ingo等人主张用一个通用的scheduler统领各种场景。
有些开发者进行了测试，在桌面场景下，BFS比CFS的效果好很多，但是因为理念的问题，BFS当时也被认为不会被合入内核，但是确实引发了广泛的关于scheduler的讨论。如今已经是2023年，Linux kernel仍然是采用CFS作为调度器，内核主线代码并没有BFS的身影。
关于BFS scheduler的设计，您可以通过阅读这篇文章来了解：BFS cpu scheduler v0.304 stable release。
BFS设计实现的内容，感兴趣的读者可以自行搜索，本文就不展开了。这里只是想跟大家强调，调度场景的多样性，以及内核大佬们对于CFS的不满以及孜孜不倦的探索。
Con Kolivas的方向是对的，内核应该有这种机制来支持用户选择对应的调度器实现以适应不同场景。
在论文BFS vs. CFS - scheduler comparison的摘要部分，作者也清晰表达了这种看法：
Our results indicate that scheduler performance varies dramatically according to hardware and workload, and as a result we strongly encourage Linux distributions to take an increased level of responsibility for selecting appropriate default schedulers that best suit the intended usage of the system.
尽管BFS不支持NUMA场景，不支持需要扩展到4096个处理器的场景，但是不妨碍它可以在桌面、终端中表现更过CFS。没有银弹这种思想，已经基本被大家所接受了，合理质疑是应该保持的。我也很乐于见到更适用的调度器能带来更好的桌面交互体验。
bpf扩展 (sched_ext)
还是相同的原因，CFS并不是银弹，在某些场景下还是希望能够亲自干预调度器的行为。2021年社区有篇文章讨论了如何使用bpf扩展来控制调度器的调度行为，Controlling the CPU scheduler with BPF。
有意思的是，之前Linus Torvalds和Ingo都坚持想通过一个大一统的调度器来解决所有问题，而CK反复建议、提供相应的调度器实现来建议朝这个可扩展的方向走，但是始终没有达成共识。而sched_ext这种可扩展的思路最后却被合入了内核主线。
我们不要阴谋论，从技术的层面来考虑的话，可能通过bpf扩展的方式确实是一种更合适的实现方式吧，至少对Linux维护者而言。bpf-based sched_ext，它提供了可扩展的方式，同时也没有增加额外的维护多个不同调度器实现的负担，至少bpf扩展的方式完全将“谁来维护扩展出来的多个版本的调度器”这个负担撇的一干二净了。可以肯定的是，Con Kolivas的这个想法是正确的，他与内核维护人员关系紧张，但是我更愿意相信不同的技术方案不同维护人员的看法不同，Torvalds、Ingo有他们自己的坚持。
本文小结
本文简单介绍了BFS调度器以及bpf-based调度器扩展sched_ext，前者是对CFS大一统的策略的一种挑衅，后者则最终成为了CFS调度能力的bpf扩展，能够让我们在运行时干预调度器的行为。从中我们可以感受到的是，不同调度场景的多样性，以及对特定场景优化的调度器的诉求。我们将再接下来合适的时候进一步介绍sched_ext这个调度器扩展的细节，再介绍它之前，我们可能需要先介绍下bpf子系统，大家才方便理解它。OK，本文到此结束，欢迎关注我并点赞转发！
参考文献
- BFS cpu scheduler v0.304 stable release
- BFS vs. CFS - scheduler comparison
- Controlling the CPU scheduler with BPF
- sched_ext: a BPF-extensible scheduler class
- BPF Opens Door to Linux Extensible Scheduling (Maybe with Rust!)
- Sched Ext: The pluggable Linux Scheduler
- Linux Torvalds Merging Extensible Scheduler ‘sched_ext’ in Linux 6.11