2. Linux 调度器发展史：从 O(n) 到 EEVDF 的演进脉络

Linux 内核调度器在过去三十年间经历了多次重大重构，每一次演进都针对特定负载场景下的性能瓶颈进行优化。理解这一演进脉络，有助于我们把握 CFS 调度器的设计哲学，并为后续的参数调优打下基础。

2.1 调度器演进总览

下表总结了 Linux 调度器四个主要版本的核心特征与关键局限：

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

早期 Linux 内核（2.4 及之前）使用 O(n) 调度器，其核心是一个全局循环链表。每次调度时，调度器需要遍历所有可运行进程，计算每个进程的"好度"（goodness），选择值最高的进程执行。

• 数据结构： 全局运行队列，所有 CPU 共享一个链表。
• 时间片分配： 基于静态优先级，优先级高的进程获得更长的时间片。
• 调度时机： 进程主动让出 CPU、时间片耗尽或发生中断。

/* O(n) 调度器核心伪代码 */
for_each_process_in_runqueue(p) {
    goodness = calculate_goodness(p);
    if (goodness > best_goodness) {
        best = p;
        best_goodness = goodness;
    }
}
switch_to(best);

2.3 O(1) 调度器：常数时间的突破

Linux 2.6.0 引入的 O(1) 调度器 由 Ingo Molnár 设计，彻底解决了 O(n) 调度器的扩展性问题。其核心思想是使用 优先级位图 和 双队列结构（active 队列 + expired 队列）。

• 数据结构： 每个 CPU 维护独立的运行队列，包含 140 个优先级链表（0~139）。
• 调度算法： 通过位图操作在 O(1) 时间内找到最高优先级的非空队列。
• 时间片： 优先级越高，时间片越长（与 O(n) 相反）。

/* O(1) 调度器核心：位图查找最高优先级 */
struct prio_array {
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

/* 查找最高优先级进程：常数时间 */
idx = sched_find_first_bit(array->bitmap);
next = list_entry(array->queue[idx].next, struct task_struct, run_list);

2.4 CFS 调度器：公平性的革命

Linux 2.6.23 合并了 Con Kolivas 开发的 CFS（Completely Fair Scheduler），由 Ingo Molnár 重写并合入主线。CFS 抛弃了固定时间片和优先级数组，转而使用 红黑树 和 虚拟运行时间（vruntime） 的概念。

• 核心思想： 理想情况下，每个进程应获得 1/n 的 CPU 时间。CFS 通过维护每个进程的 vruntime，总是选择 vruntime 最小的进程运行。
• 数据结构： 红黑树（rbtree），以 vruntime 为键值，左子树 vruntime 小于右子树。
• 调度复杂度： O(log n)，插入和删除操作与进程数对数相关。

/* CFS 调度器核心：选择 vruntime 最小的进程 */
static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;
    struct sched_entity *se = rb_entry(left, struct sched_entity, run_node);
    return se;
}

/* 更新 vruntime */
se->vruntime += delta_exec * NICE_0_LOAD / se->load.weight;

2.5 BFS 调度器：桌面交互的极致追求

BFS（Brain Fuck Scheduler） 由 Con Kolivas 在 2009 年开发，作为对 CFS 在桌面交互场景下延迟问题的回应。BFS 并未进入 Linux 主线内核，但在 Android 和某些桌面发行版中得到了应用。

• 核心算法： 使用 双链表 和 虚拟截止时间，每次选择"最饥饿"（等待时间最长）的进程。
• 调度复杂度： O(n)，但针对桌面负载（通常进程数较少）做了优化。
• 设计哲学： 优先保证交互式进程的响应延迟，牺牲部分吞吐量。

2.6 EEVDF 调度器：延迟边界的新范式

Linux 6.6 内核引入了 EEVDF（Earliest Eligible Virtual Deadline First） 调度器作为可选调度类。EEVDF 在 CFS 的公平性基础上，增加了 虚拟截止时间 机制，为每个进程提供明确的延迟保证。

• 核心算法： 每个进程维护一个"eligible time"（最早可运行时间）和"deadline"（最晚应运行时间）。调度器选择 eligible time 最早且 deadline 最紧迫的进程。
• 数据结构： 红黑树 + 虚拟时间轴，同时支持公平分配和延迟约束。
• 优势： 对延迟敏感型负载（如音视频、游戏）提供更可预测的调度行为。

/* EEVDF 核心概念：虚拟截止时间计算 */
se->deadline = se->vruntime + sched_latency / se->weight;
se->eligible_time = max(se->vruntime, cfs_rq->min_vruntime);

/* 选择条件：eligible_time 最早，且 deadline 最紧迫 */
if (se->eligible_time <= cfs_rq->min_vruntime)
    pick_eevdf(cfs_rq);

2.7 调度器演进脉络图

下图展示了 Linux 调度器从 O(n) 到 EEVDF 的演进路径，以及各调度器的核心数据结构与算法特征：

2.8 演进背后的设计哲学

从 O(n) 到 EEVDF，Linux 调度器的演进反映了操作系统设计理念的深刻变化：

1. 从"静态优先级"到"动态公平"： O(n) 和 O(1) 依赖静态优先级分配时间片，而 CFS 通过 vruntime 实现了"按权重公平分配"。
2. 从"启发式"到"确定性"： O(1) 的交互式进程判断依赖复杂的启发式规则，容易误判；CFS 和 EEVDF 使用数学上可证明的公平算法。
3. 从"单队列"到"多队列"： 全局运行队列 → 每 CPU 运行队列 → 负载均衡框架，多核扩展性逐步提升。
4. 从"吞吐优先"到"延迟感知"： 早期调度器追求 CPU 利用率最大化，现代调度器开始关注尾延迟和交互体验。