3. Linux调度器演进

Linux 内核调度器经历了多次重大重构，每一次演进都旨在解决特定场景下的性能瓶颈。对于实时系统开发者而言，理解调度器的演进历史，是掌握调度延迟根源、正确配置 Cyclictest 测试环境的前提。本章将依次剖析 O(n)、O(1)、CFS 以及实时调度类 (RT) 的设计哲学与核心差异。

3.1 O(n) 调度器：早期内核的遍历之痛

在 Linux 2.4 及更早版本中，调度器采用最简单的 O(n) 算法。其核心数据结构是一个全局运行队列，所有可运行进程被链接在一个链表中。

• 调度流程：每次发生调度时，调度器必须遍历整个运行队列，计算每个进程的“好度 (goodness)”，选出得分最高的进程执行。
• 时间复杂度：O(n)，其中 n 为系统中可运行进程的数量。当进程数增多时，调度开销线性增长。
• 多核问题：全局运行队列使用一把大内核锁，多核 CPU 无法并行调度，严重限制 SMP 扩展性。
• 实时性缺陷：遍历时间不可预测，高优先级进程可能因遍历长链表而延迟获得 CPU。

3.2 O(1) 调度器：可扩展性的里程碑

Linux 2.6.0 引入的 O(1) 调度器彻底改变了调度算法的时间复杂度。它使用两个优先级数组（active 和 expired），每个优先级对应一个 FIFO 队列，并利用位图快速查找最高优先级非空队列。

• 核心数据结构：140 个优先级队列（0-99 为实时，100-139 为普通），每个队列是一个链表头。
• 调度决策：通过 __ffs() 位图指令在常数时间内找到最高优先级非空队列，时间复杂度降为 O(1)。
• 时间片分配：基于优先级静态分配时间片，高优先级进程获得更长的时间片。
• 多核友好：每个 CPU 拥有独立的运行队列，减少锁竞争，提升 SMP 扩展性。

3.3 完全公平调度器 (CFS)：公平与交互的平衡

Linux 2.6.23 引入的 CFS 由 Ingo Molnár 设计，彻底放弃了固定时间片和优先级数组，转而采用基于 虚拟运行时间 (vruntime) 的红黑树模型。CFS 的目标是让每个进程获得 CPU 时间的“公平份额”。

• 核心数据结构：红黑树 (Red-Black Tree)，键值为进程的 vruntime。最左侧节点（vruntime 最小）即为下一个被调度执行的进程。
• vruntime 计算：vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)。权重由优先级决定，高优先级进程 vruntime 增长更慢，从而获得更多 CPU 时间。
• 调度延迟目标：引入 targeted_latency（默认 6ms）和 minimum_granularity（默认 0.75ms），确保每个进程在调度周期内至少运行一次。
• 组调度：支持将进程分组，在组间按权重分配 CPU 时间，实现更细粒度的资源控制。

3.4 实时调度类 (RT)：确定性优先

实时调度类独立于 CFS，专门管理 SCHED_FIFO 和 SCHED_RR 实时进程。它采用优先级驱动的调度策略，确保最高优先级的实时进程能够立即抢占 CPU。

• SCHED_FIFO：先进先出调度。一旦获得 CPU，除非被更高优先级进程抢占或主动阻塞，否则会一直运行。
• SCHED_RR：时间片轮转调度。与 FIFO 类似，但相同优先级的进程按时间片轮转执行。
• 优先级范围：0-99，数值越大优先级越高。所有实时进程优先级高于普通进程 (100-139)。
• 调度类层次：内核先检查 RT 调度类是否有可运行进程，若有则直接调度，否则回退到 CFS。

3.5 调度器演进对比总结

下表从时间复杂度、公平性、实时性、多核扩展性四个维度对比四种调度器，帮助理解为何实时测试必须关注调度类选择。