2. 早期调度器回顾：Linux 0.11 的调度算法与 O(n) 调度器

在理解现代 CFS 调度器之前，有必要回溯 Linux 调度器的起点。早期调度器设计简单、直观，但随着硬件复杂度和负载规模的提升，其缺陷逐渐暴露，直接催生了 O(1) 调度器的诞生。

2.1 Linux 0.11 调度算法：时间片 + 优先级循环

Linux 0.11（1991 年）的调度器是教科书式的时间片轮转（Round-Robin）变体，核心思想是：每个进程拥有一个时间片，时间片用完后必须让出 CPU，等待下一次调度。调度器通过 counter 字段实现时间片计数，通过 priority 字段决定初始时间片长度。

调度流程（简化）

1. 遍历所有进程：从 task[0] 到 task[NR_TASKS-1]，检查每个进程的状态。
2. 选择 counter 最大的就绪进程：counter 值越大，表示剩余时间片越多，优先级越高。
3. 运行选中的进程：每次时钟中断（10ms）递减 counter。
4. counter 归零时触发调度：进程被挂起，调度器重新选择下一个进程。
5. 所有进程 counter 都为零时：调度器为每个进程重新分配时间片：counter = counter/2 + priority。

SVG 图：Linux 0.11 调度器核心循环

2.2 O(n) 调度器的诞生背景

Linux 1.2 到 2.4 内核使用的调度器被称为 O(n) 调度器。其名称来源于调度算法的时间复杂度：每次调度都需要遍历所有进程（n 个进程），时间复杂度为 O(n)。随着系统中进程数量的增加，调度开销线性增长。

诞生背景

• 多任务需求增长：90 年代末，服务器和桌面系统同时运行的进程数从几十个增长到数百个。
• SMP（对称多处理）初步支持：Linux 2.0 开始支持 SMP，但调度器仍使用单一全局运行队列，所有 CPU 共享一个锁。
• 交互式响应要求：桌面用户对 GUI 响应速度的要求提高，调度器需要更好地区分 I/O 密集型和 CPU 密集型进程。

2.3 O(n) 调度器的核心缺陷

O(n) 调度器的缺陷可以归纳为以下四个方面，这些缺陷直接推动了 O(1) 调度器的设计。

SVG 图：O(n) 调度器架构与缺陷示意

2.4 代码片段：O(n) 调度器的核心逻辑

以下代码展示了 O(n) 调度器的核心调度函数 schedule() 的简化逻辑。注意 for 循环遍历所有进程，以及 goodness() 函数计算每个进程的“调度权重”。

// Linux 2.4 调度器核心 (简化版)
asmlinkage void schedule(void) {
    struct task_struct *prev, *next, *p;
    int this_cpu, c;

    prev = current;
    this_cpu = smp_processor_id();

    // 检查是否需要重新调度
    if (prev->state == TASK_RUNNING)
        goto still_running;

    // 遍历所有进程 (O(n) 核心)
    repeat_schedule:
    next = idle_task(this_cpu);
    c = -1000;
    for_each_task(p) {  // 遍历 task[] 数组
        if (p->state != TASK_RUNNING)
            continue;
        int weight = goodness(p, this_cpu); // 计算调度权重
        if (weight > c) {
            c = weight;
            next = p;
        }
    }

    // 如果没有可运行进程，使用 idle 进程
    if (!next)
        next = idle_task(this_cpu);

    // 上下文切换
    switch_to(prev, next);
    return;

still_running:
    c = goodness(prev, this_cpu);
    next = prev;
    goto repeat_schedule;
}

// 计算进程的调度权重
static inline int goodness(struct task_struct *p, int cpu) {
    int weight;
    weight = p->counter;  // 剩余时间片
    if (weight) {
        weight += 20 - p->nice;  // nice 值调整
        // 交互式进程加分 (基于平均睡眠时间)
        if (p->avg_sleep > 0)
            weight += p->avg_sleep >> 4;
    }
    return weight;
}

2.5 从 O(n) 到 O(1) 的驱动力

O(n) 调度器的缺陷在 2.4 内核后期变得不可接受，尤其是 SMP 服务器场景。以下表格总结了 O(n) 与后续 O(1) 调度器的关键差异，为下一章的学习建立对比基础。