Linux 调度器演进：从 O(n) 到 BFS

Linux 内核的进程调度器经历了多次重大重构，每一次演进都针对特定硬件时代（单核 → 多核 → 大规模异构）的负载特征进行优化。理解这四代调度器的设计哲学与缺陷，是掌握内核抢占配置与实时性调优的基础。

2.1 O(n) 调度器（Linux 2.4 ~ 2.6.0）

O(n) 调度器是 Linux 早期使用的 基于优先级的时间片轮转 调度器。其名称来源于调度算法的时间复杂度为 O(n)，其中 n 为系统中可运行进程的数量。

核心设计

• 单一运行队列： 所有可运行进程被放入一个全局链表。
• 静态优先级 + 时间片： 每个进程分配一个固定时间片，优先级高的进程获得更长的时间片。
• 每次调度遍历全链表： 调度器每次选择下一个进程时，需要遍历整个运行队列，计算每个进程的“好度（goodness）”，选出最大值。

// O(n) 调度器核心伪代码（简化）
for_each_process_in_runqueue(p) {
    goodness = p->counter + p->priority;
    if (goodness > best_goodness) {
        best = p;
        best_goodness = goodness;
    }
}
switch_to(best);

O(n) 调度器结构示意

2.2 O(1) 调度器（Linux 2.6.0 ~ 2.6.22）

为解决 O(n) 调度器的性能瓶颈，Ingo Molnár 在 Linux 2.6.0 中引入了 O(1) 调度器。其核心思想是 用空间换时间，将调度算法的时间复杂度降低为常数 O(1)。

关键改进

• 多级优先级队列（140 级）： 每个优先级对应一个链表，进程按优先级入队。
• 活跃队列 + 过期队列双结构： 活跃队列中的进程用完时间片后进入过期队列，所有进程时间片用完后交换指针。
• 位图查找： 使用一个 140 位的 bitmap 标记非空队列，通过 __ffs() 指令在常数时间内找到最高优先级非空队列。

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

// 找到最高优先级非空队列（O(1)）
idx = __ffs(array->bitmap);  // 返回第一个置位位
next = list_entry(array->queue[idx].next, struct task_struct, run_list);

O(1) 调度器双队列结构

2.3 CFS 调度器（Linux 2.6.23 至今）

CFS（Completely Fair Scheduler，完全公平调度器）由 Con Kolivas 的“楼梯调度器”启发，由 Ingo Molnár 在 Linux 2.6.23 中合入主线。它彻底抛弃了固定时间片和优先级队列，采用 红黑树 + 虚拟运行时间（vruntime） 模型。

核心原理

• 虚拟运行时间（vruntime）： 每个进程的 vruntime 按实际运行时间加权计算（权重由优先级决定）。
• 红黑树排序： 所有可运行进程按 vruntime 排序，最左侧节点（vruntime 最小）即为下一个被调度进程。
• 目标： 让所有进程的 vruntime 尽可能相等，实现“完全公平”。

// CFS 核心：vruntime 更新与红黑树选择
// 每次时钟 tick 更新当前进程的 vruntime
curr->vruntime += delta_exec * NICE_0_LOAD / curr->load.weight;

// 选择下一个进程：红黑树最左节点
next = rb_entry(cfs_rq->rb_leftmost, struct sched_entity, run_node);

CFS 调度器红黑树结构

2.4 BFS 调度器（Con Kolivas，2009）

BFS（Brain Fuck Scheduler）由 Con Kolivas 开发，旨在解决 CFS 在桌面交互场景下的延迟问题。BFS 采用 单链表 + 全局优先级队列，专为 桌面和实时交互 优化。

设计特点

• 单链表运行队列： 所有进程按优先级排序，插入时保持有序。
• 虚拟截止时间（Virtual Deadline）： 每个进程计算一个“截止时间”，调度器选择截止时间最早的进程。
• 全局队列（非 per-CPU）： 所有 CPU 共享一个运行队列，通过锁保护。

四代调度器对比

2.5 调度器演进总结