2. Linux 调度器演进：从 O(n) 到 EEVDF

Linux 内核的进程调度器经历了多次重大重构，每一次演进都旨在解决特定负载场景下的性能瓶颈与公平性问题。从早期的 O(n) 调度器，到广为人知的 O(1) 与 CFS，再到近年来引入的 EEVDF，调度算法的演进史就是一部操作系统对“吞吐、响应、公平”三者平衡的探索史。

2.1 O(n) 调度器：简单但低效

O(n) 调度器是 Linux 2.4 及早期版本使用的调度算法。其核心数据结构是一个全局的进程链表，每次调度时，调度器需要遍历整个链表来查找“最佳”候选进程。

• 调度复杂度： O(n)，其中 n 为系统中进程总数。进程数越多，调度开销越大。
• 时间片分配： 基于静态优先级，所有进程共用一个时间片池，缺乏动态调整机制。
• 多核支持： 极差。全局链表导致严重的锁竞争，无法有效利用 SMP 架构。
• 交互性： 对 I/O 密集型进程不友好，容易导致桌面响应迟钝。

2.2 O(1) 调度器：里程碑式的改进

Linux 2.6.0 引入的 O(1) 调度器彻底解决了 O(n) 的扩展性问题。其核心思想是使用多级优先级队列（Multi-Level Queue），将进程按优先级分散到 140 个不同的队列中，调度复杂度降为 O(1)。

O(1) 调度器引入了 active 和 expired 双数组结构。进程在 active 数组中用完时间片后，被移动到 expired 数组并重新计算优先级。当 active 数组为空时，交换两个数组的指针，实现 O(1) 的队列切换。

2.3 CFS 调度器：完全公平的革新

Linux 2.6.23 合并了 CFS（Completely Fair Scheduler），由 Ingo Molnár 设计。CFS 抛弃了固定时间片和优先级队列，转而使用 红黑树 和 虚拟运行时间（vruntime） 来模拟“理想多任务处理器”。

• 核心思想： 在理想多任务处理器中，每个进程获得 1/n 的 CPU 时间。CFS 通过 vruntime 衡量进程的运行进度，调度器总是选择 vruntime 最小的进程运行。
• 数据结构： 红黑树（rbtree），插入和查找复杂度为 O(log n)。
• 时间片： 不固定。CFS 使用 targeted latency（目标延迟）和 minimum granularity（最小粒度）动态计算时间片。
• 权重： 通过 nice 值映射到权重，权重越高的进程 vruntime 增长越慢，从而获得更多 CPU 时间。

2.4 BFS 调度器：桌面响应优先

BFS（Brain Fuck Scheduler）由 Con Kolivas 开发，旨在优化桌面交互体验。BFS 使用 单链表 和 全局优先级位图，调度复杂度为 O(n)，但针对桌面负载（通常进程数较少）做了极致优化。

2.5 EEVDF 调度器：延迟边界的新时代

Linux 6.6 合入了 EEVDF（Earliest Eligible Virtual Deadline First）调度器，由 Peter Zijlstra 实现。EEVDF 在 CFS 的 vruntime 基础上，引入了 虚拟截止时间（virtual deadline） 和 eligible time 的概念，为每个进程提供明确的延迟边界。

• 核心思想： 每个进程被分配一个 虚拟截止时间，调度器选择 eligible（符合条件的）且截止时间最早的进程运行。
• 数据结构： 红黑树 + 时间排序树，同时维护 vruntime 和 deadline 两个维度。
• 优势： 提供更可预测的调度延迟，减少“饥饿”现象，对实时和交互负载更友好。
• 兼容性： 完全兼容 CFS 的权重和 nice 值语义，用户态无感知。

2.6 调度器演进对比总结