3. Linux 2.4 调度器回顾：O(n)调度器的设计、运行队列遍历、时间复杂度分析

3.1 设计背景与核心思想

Linux 2.4 内核（2001年发布）采用的 O(n)调度器，是 Linux 调度史上第一个全局统一调度器。在此之前，调度逻辑分散在各架构代码中。O(n)调度器的设计目标是在多任务环境下提供公平的 CPU 时间分配，但其核心数据结构——全局运行队列——决定了它的性能瓶颈。

3.2 全局运行队列结构

O(n)调度器的运行队列是一个双向循环链表，所有 CPU 共享同一个队列（SMP 系统通过大内核锁保护）。每个进程的 task_struct 通过 run_list 字段链接到队列中。

/* 内核源码：include/linux/sched.h (2.4.x) */
struct task_struct {
    volatile long state;        /* -1 unrunnable, 0 runnable, >0 stopped */
    struct list_head run_list;  /* 运行队列链表节点 */
    unsigned long policy;       /* 调度策略：SCHED_OTHER, SCHED_FIFO, SCHED_RR */
    int priority;               /* 静态优先级 (0-99 实时, 100-139 普通) */
    int counter;                /* 动态时间片计数器 */
    unsigned long rt_priority;  /* 实时优先级 */
    /* ... 其他字段 ... */
};

/* 全局运行队列定义 */
struct list_head runqueue_head;  /* 所有可运行进程的链表头 */

3.3 调度算法核心：goodness 函数

调度器通过 goodness() 函数为每个进程打分，分数最高的进程获得 CPU。这个函数是 O(n)调度器的灵魂，它综合了进程类型、优先级和时间片剩余量。

/* 内核源码：kernel/sched.c (2.4.x) - 简化版 */
static inline int goodness(struct task_struct *p, int this_cpu, struct mm_struct *this_mm)
{
    int weight;

    /* 1. 实时进程直接返回高权重 */
    if (p->policy != SCHED_OTHER) {
        weight = 1000 + p->rt_priority;
        goto out;
    }

    /* 2. 普通进程：基础权重 = counter + priority */
    weight = p->counter;
    if (!weight)
        goto out;

    /* 3. 奖励：如果进程上次运行在同一 CPU 且共享内存描述符 */
    if (p->mm == this_mm || !p->mm)
        weight += 1;
    weight += 20 - p->priority;  /* priority 越小优先级越高 */

out:
    return weight;
}

3.4 调度主流程：schedule() 函数

每次调用 schedule() 时，调度器执行以下步骤。注意第 2 步的 全链表遍历 是 O(n) 复杂度的根源。

1. 关闭内核抢占，获取大内核锁。
2. 遍历 runqueue_head 链表，对每个进程调用 goodness()，记录最高分进程。
3. 如果所有进程的 counter 都为 0（时间片耗尽），则执行 重新计算时间片：遍历所有进程（包括睡眠进程），按 counter = counter/2 + priority 重新分配。
4. 选择 goodness 最高的进程，执行上下文切换。

/* 内核源码：kernel/sched.c (2.4.x) - schedule() 核心逻辑 */
asmlinkage void schedule(void)
{
    struct task_struct *prev, *next, *p;
    int this_cpu, c;

    prev = current;
    this_cpu = smp_processor_id();

    /* 步骤 2：遍历运行队列，寻找最佳进程 */
    next = &init_task;  /* idle 进程作为默认 */
    c = -1000;
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (p->state == TASK_RUNNING) {
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c) {
                c = weight;
                next = p;
            }
        }
    }

    /* 步骤 3：如果所有 counter 为 0，重新计算 */
    if (!c) {
        recalc_task_timeslice(prev, this_cpu);
        /* 重新遍历一次 ... */
    }

    /* 步骤 4：上下文切换 */
    if (prev != next)
        switch_to(prev, next);
}

3.5 时间复杂度分析

O(n)调度器的时间复杂度可以从两个维度分析：

3.6 O(n)调度器架构总览

下面的 SVG 图展示了 O(n)调度器的完整架构，包括全局运行队列、调度决策流程和时间片重新计算路径。

3.7 O(n)调度器的历史局限

从今天的视角看，O(n)调度器存在以下明显缺陷，这些缺陷直接推动了 O(1) 调度器的诞生：

• 可扩展性差： 调度开销随进程数线性增长，在桌面系统（几十个进程）尚可接受，但在服务器（数百上千进程）场景下成为瓶颈。
• SMP 性能低下： 全局运行队列和大内核锁导致多 CPU 系统无法并行调度，CPU 越多锁竞争越严重。
• 交互性响应不稳定： 时间片重新计算时所有进程的 counter 被重置，导致交互式进程无法获得及时响应。
• 缺乏 CPU 亲和性支持： 虽然 goodness 函数有简单的缓存奖励，但没有显式的 CPU 绑定机制，进程在不同 CPU 间频繁迁移，缓存命中率低。