1. 调度器概述：Linux调度器发展历史、CFS调度器原理、BFS与MuQSS的诞生背景
1.1 Linux调度器发展历史
Linux内核调度器经历了多次重大重写，每一次演进都围绕吞吐量、公平性、交互响应和可扩展性之间的权衡展开。下表梳理了从2.4到5.x版本的关键里程碑：
| 内核版本 | 调度器名称 | 核心算法 | 主要问题 |
|---|---|---|---|
| 2.4 (2001) | O(1) 调度器前身 | 循环时间片 + 优先级队列 | O(n) 扫描进程链表，多核扩展差 |
| 2.6.0 (2003) | O(1) 调度器 | 双优先级位图 + 活跃/过期数组 | 交互性启发式复杂，桌面响应不稳定 |
| 2.6.23 (2007) | CFS (完全公平调度器) | 红黑树 + 虚拟运行时间 (vruntime) | 服务器/桌面兼顾，但延迟敏感场景仍有抖动 |
| 3.14 (2014) | CFS + EEVDF 改进 | 负载跟踪 + 组调度 + 带宽控制 | NUMA 感知增强，但全局锁竞争仍存在 |
| 5.x (2020+) | CFS + 核心调度 (Core Scheduling) | 细粒度负载均衡 + 核心隔离 | 安全隔离需求上升，实时性依赖外部补丁 |
关键认知： 调度器演进本质是“公平”与“响应”的博弈。O(1) 用位图换取了常数时间选择，但交互性判断依赖启发式；CFS 用红黑树实现了数学上的完美公平，却在高竞争桌面场景下引入“平滑但迟钝”的调度延迟。
1.2 CFS调度器原理
CFS (Completely Fair Scheduler) 由 Ingo Molnár 于 2007 年引入，核心思想是：让每个可运行进程获得 CPU 时间的 1/n。它摒弃了固定时间片和优先级队列，转而使用红黑树维护进程的虚拟运行时间 (vruntime)。
CFS 关键数据结构与流程：
- 红黑树 (rbtree)：以 vruntime 为键值，最左节点是 vruntime 最小的进程，即“最需要 CPU”的进程。
- 虚拟运行时间 (vruntime)：
vruntime += delta_exec * (NICE_0_LOAD / se.load.weight)。权重越高，vruntime 增长越慢，获得更多 CPU。 - 调度点 (schedule())：每次时钟中断或进程主动让出 CPU 时，调用
__schedule()选择红黑树最左节点。 - 负载均衡：在多个调度域 (sched_domain) 之间迁移进程，保持各 CPU 运行队列负载均衡。
CFS 调度周期示例： 假设两个进程 A (权重 1024) 和 B (权重 2048)，调度延迟目标 6ms。A 获得 2ms，B 获得 4ms。每次调度后，A 的 vruntime 增加 2ms，B 的 vruntime 增加 1ms（因为权重高，增长慢）。红黑树始终选择 vruntime 最小的进程，保证长期公平。
1.3 CFS 的局限性
尽管 CFS 在服务器和通用桌面场景表现出色，但在以下场景暴露出明显短板：
- 桌面交互响应抖动：CFS 追求长期公平，短期调度延迟可能达到 10~20ms，导致鼠标/键盘操作出现可感知的卡顿。
- 高负载下的饥饿风险：当大量 CPU 密集型进程竞争时，交互式进程的 vruntime 追赶缓慢，响应时间恶化。
- NUMA 感知不足：默认负载均衡策略在跨 NUMA 节点迁移时产生额外缓存缺失和延迟。
- 全局锁竞争：rq->lock 在大型系统上成为瓶颈，影响多核扩展性。
注意： CFS 的“完全公平”是数学意义上的长期公平，而非瞬时公平。对于毫秒级交互响应要求，CFS 的调度粒度（通常 4~6ms 调度周期）和 vruntime 累积机制会引入不可忽略的延迟。
1.4 BFS 与 MuQSS 的诞生背景
BFS (Brain Fuck Scheduler) 由 Con Kolivas 于 2009 年发布，MuQSS (Multiple Queue Skiplist Scheduler) 是 BFS 的后续多队列版本，于 2016 年推出。它们的诞生直接源于对 CFS 桌面响应不满的社区分歧。
BFS 核心设计理念：
- 单运行队列 (Single Runqueue)：所有 CPU 共享一个全局优先级链表，避免负载均衡复杂性。
- O(n) 调度选择：每次调度遍历整个链表选择最佳进程，但通过虚拟 deadline 和优先级位图加速。
- 虚拟 deadline 调度：为每个进程计算“最晚开始时间”，优先选择 deadline 最早的进程。
- 抢占粒度更细：默认调度延迟 1~2ms，远低于 CFS 的 4~6ms。
MuQSS 改进点：
- 多队列 (Per-CPU Runqueue)：每个 CPU 独立维护跳表 (Skiplist)，消除全局锁竞争。
- 跳表替代链表：O(log n) 插入/删除，O(1) 选择最小 deadline 进程。
- NUMA 感知：进程优先在本地 CPU 队列调度，减少跨节点迁移。
- 可配置调度粒度：通过
sched_granularity_ns调整，适应桌面/服务器不同需求。
1.5 BFS/MuQSS 与 CFS 的核心差异
| 特性 | CFS | BFS | MuQSS |
|---|---|---|---|
| 数据结构 | 红黑树 (O(log n)) | 优先级链表 (O(n)) | 跳表 (O(log n)) |
| 运行队列 | Per-CPU 队列 + 负载均衡 | 全局单队列 | Per-CPU 跳表 |
| 调度选择依据 | vruntime 最小 | 虚拟 deadline 最早 | 虚拟 deadline 最早 |
| 默认调度延迟 | 4~6ms | 1~2ms | 1~2ms (可配置) |
| NUMA 感知 | 通过调度域实现 | 无 | 内置 NUMA 优先 |
| 锁竞争 | rq->lock 全局锁 | 全局链表锁 | Per-CPU 锁，无竞争 |
| 桌面交互响应 | 中等，偶发抖动 | 优秀，低延迟 | 优秀，低延迟 |
| 多核扩展性 | 良好 (16~32核) | 差 (4~8核上限) | 良好 (64核+) |
社区评价： Con Kolivas 称 BFS 为“桌面调度器的最后一块拼图”。尽管 BFS 未合入主线，但其设计思想深刻影响了后续调度器优化方向，尤其是对调度延迟的极致追求。MuQSS 在保留 BFS 低延迟特性的同时，通过多队列和跳表解决了扩展性问题，成为许多桌面 Linux 发行版（如 Liquorix、XanMod）的默认调度器。
1.6 为什么需要移植 BFS/MuQSS？
主线内核持续演进，BFS/MuQSS 作为外部补丁，需要跟随内核 API 变化进行移植。移植动机包括：
- 桌面/游戏场景优化：降低输入延迟、帧率抖动，提升交互流畅度。
- 嵌入式/实时场景：BFS 的细粒度抢占适合对调度延迟敏感的嵌入式系统。
- 旧硬件优化：在低核数 CPU 上，BFS 的简单设计反而比 CFS 更高效。
- 学术研究：对比不同调度策略在实际负载下的表现，验证调度理论。