2、Linux调度器演进：从O(n)到O(1)再到CFS，以及RT调度器的引入
Linux内核调度器的发展史，本质上是一部在交互响应、吞吐效率、公平保障与实时确定性之间不断权衡与重构的演进史。从早期简单粗暴的O(n)调度器，到里程碑式的O(1)调度器，再到当前主流的完全公平调度器（CFS），以及为实时任务引入的RT调度器，每一步都深刻影响了操作系统的行为特性。
2.1 早期调度器：O(n)调度器（Linux 2.4及之前）
在Linux 2.4内核时代，调度器采用了一种相对简单的设计。每次进行调度决策时，调度器需要遍历整个就绪队列中的所有进程，计算每个进程的“好度”（goodness）值，然后选择“好度”最高的进程来运行。
O(n)调度器的主要特点与局限如下表所示：
| 特性 | 描述 | 局限性 |
|---|---|---|
| 数据结构 | 单一全局就绪链表 | 多核CPU访问时需要全局锁，扩展性差 |
| 时间复杂度 | O(n)，遍历所有进程 | 进程数增多时，调度开销线性增长 |
| 优先级计算 | 动态计算“好度”值 | 计算逻辑复杂，且对交互式进程的识别不够精准 |
| 对称多处理（SMP） | 支持较弱 | CPU负载不均衡，进程迁移开销大 |
下图展示了O(n)调度器在单核环境下的工作流程：
2.2 里程碑式改进：O(1)调度器（Linux 2.6.0 - 2.6.22）
为了解决O(n)调度器的可扩展性问题，Linux内核在2.6版本引入了由Ingo Molnár设计的O(1)调度器。其核心思想是使用多级优先级队列和位图技术，将调度决策的时间复杂度降低为常数级 O(1)。
O(1)调度器引入了两个关键数据结构：活跃（active） 队列和 过期（expired） 队列。每个优先级（140个级别）对应一个独立的链表。调度器通过位图快速找到非空的最优优先级队列，然后从该队列头部取出进程运行，整个过程不依赖进程总数。
- 双队列结构： 活跃队列与过期队列分离，进程时间片耗尽后从活跃队列移至过期队列，当活跃队列为空时，交换两个队列的指针，实现O(1)的队列切换。
- 位图查找： 使用一个140位的位图标记每个优先级队列是否为空，通过CPU指令（如
__ffs）在常数时间内找到最高优先级的非空队列。 - 时间片计算： 时间片在进程创建时预先计算好，调度时直接使用，无需动态计算。
O(1)调度器与O(n)调度器的核心差异对比：
| 对比维度 | O(n) 调度器 | O(1) 调度器 |
|---|---|---|
| 时间复杂度 | O(n) | O(1) |
| 数据结构 | 单一链表 | 多级优先级队列 + 位图 |
| 队列结构 | 单队列 | 活跃队列 + 过期队列 |
| SMP扩展性 | 差（全局锁） | 好（每个CPU独立调度） |
| 交互式进程识别 | 基于平均睡眠时间 | 基于睡眠时间与运行时间差值 |
下图展示了O(1)调度器的双队列结构与位图查找机制：
2.3 完全公平调度器：CFS（Linux 2.6.23至今）
为了解决O(1)调度器的启发式复杂性和公平性问题，Con Kolivas开发的“楼梯调度器”（Staircase Scheduler）和“RSDL”（Rotating Staircase Deadline Scheduler）提供了重要思路。最终，Ingo Molnár在Linux 2.6.23内核中集成了完全公平调度器（CFS）。
CFS的核心思想不再是维护优先级队列和时间片，而是模拟一个“理想、精确的多任务CPU”。它使用一个红黑树来组织就绪进程，以进程的虚拟运行时间（vruntime）作为键值。vruntime越小，表示进程被CPU“亏待”得越多，调度器就会优先选择它。
- 红黑树： 自平衡二叉搜索树，所有就绪进程按vruntime排序，最左侧节点（vruntime最小）即为下一个要运行的进程。
- vruntime： 虚拟运行时间，是进程实际运行时间经过优先级（nice值）加权后的结果。高优先级（nice值小）的进程，其vruntime增长更慢，从而获得更多CPU时间。
- 目标延迟： 调度器保证在一个“目标延迟”周期内，所有可运行进程至少被调度一次，确保交互性。
- 粒度控制： 通过
min_granularity参数控制最小调度粒度，避免过于频繁的上下文切换。
CFS与O(1)调度器的核心差异：
| 对比维度 | O(1) 调度器 | CFS 调度器 |
|---|---|---|
| 核心数据结构 | 多级优先级队列 + 位图 | 红黑树（按vruntime排序） |
| 公平性模型 | 基于时间片轮转 | 基于加权公平排队（WFQ） |
| 优先级实现 | 静态优先级 + 动态调整 | 通过vruntime增长率（nice值）实现 |
| 交互式识别 | 复杂的启发式算法 | 无需启发式，睡眠进程vruntime不增长，自然获得补偿 |
| 时间复杂度 | O(1) | O(log n)（红黑树插入/删除） |
下图展示了CFS调度器的红黑树结构与调度决策流程：
2.4 RT调度器的引入：实时任务与普通任务的分治
随着Linux被广泛应用于嵌入式、工业控制和多媒体领域，对实时性的需求日益迫切。CFS虽然公平，但其设计目标是最大化系统吞吐量和交互响应，无法保证任务的截止时间。因此，Linux内核引入了实时（RT）调度器，与CFS协同工作。
RT调度器为实时任务提供了两种调度策略：
- SCHED_FIFO（先进先出）： 优先级最高的任务一旦获得CPU，将一直运行直到主动阻塞或更高优先级任务出现。没有时间片限制。
- SCHED_RR（轮转）： 与SCHED_FIFO类似，但相同优先级的任务之间采用时间片轮转，防止单个任务独占CPU。
下表总结了Linux内核中三种调度器的共存关系：
| 调度器类型 | 调度策略 | 优先级范围 | 适用场景 | 与CFS的关系 |
|---|---|---|---|---|
| RT调度器 | SCHED_FIFO / SCHED_RR | 0 - 99（实时优先级） | 硬实时任务、中断处理、高精度控制 | 优先级高于CFS，RT任务就绪时抢占CFS |
| CFS调度器 | SCHED_NORMAL / SCHED_BATCH / SCHED_IDLE | 100 - 139（nice值映射） | 普通用户进程、批处理任务、后台服务 | 默认调度器，处理所有非实时任务 |
| 空闲调度器 | SCHED_IDLE | 最低 | 低优先级后台任务 | 仅在CPU空闲时运行 |
下图展示了RT调度器与CFS调度器在Linux内核中的协作架构：