Linux中的CFS调度器是如何一步步发明出来的？

1965年，你是一名操作系统工程师，计算机刚刚从单任务时代进入多任务时代——现在一台计算机可以同时运行多个程序了。

但你面临一个棘手的问题：只有一个CPU，10个程序都想运行，该让谁先执行？

这是个看似简单实则困难的问题，如果处理不好，可能会出现各种各样的古怪问题：

• 重要的程序等待太久
• 用户的交互操作（如键盘输入）响应缓慢
• 某些程序永远无法获得CPU时间

你需要设计一个"调度器"来分配CPU时间。

第一次尝试：按到达顺序排队

你的第一个想法很简单：先来先服务，就像银行排队一样，谁先到谁先执行。

void schedule() {
    if (head != tail) {
        struct task *t = &queue[head++];
        t->run();  // 执行任务
    }
}

这个调度器实现非常简单，很快你就把它部署到系统上，运行了半天后用户开始抱怨，它敲击键盘输入一个字符需要等待半天才会有响应。

你帮忙排查了半天发现这个系统中有一个需要10分钟的科学计算程序，这个程序运行时系统不可能会对其它任务有相应，因为调度器是按排队顺序来的。

你意识到：简单排队根本无法满足实际需求！

引入优先级机制

你思考了很久，想出一个改进方案：给每个任务分配一个数字，数字越小越重要，总是让最重要的任务先执行。

void schedule() {
    struct task *highest = NULL;

    // 找到数字最小（最重要）的任务
    for (int i = 0; i < num_tasks; i++) {
        if (highest == NULL || tasks[i].priority < highest->priority) {
            highest = &tasks[i];
        }
    }

    if (highest) {
        highest->run();
    }
}

这个数字就是所谓的优先级（Priority）。

你把新系统部署出去，期待能解决先来先服务调度器的问题。

但半天后，你就收到一个严重的错误报告。

用户报告它的一个日志写入程序已经等待了2个小时，仍然没有获得CPU时间。

你一通排查，发现有一个视频解码程序优先级更高的任务一直在运行。由于它的优先级高，调度器总是选择它，日志程序永远轮不到！

这就是所谓的饥饿（Starvation）的问题：低优先级任务可能永远得不到执行机会。

1990年：给每个任务分配固定配额

你思考了很久：问题的根源是什么？

高优先级任务会无限期地占用CPU！

你想出一个新方法：给每个任务分配固定的"运行配额"，配额用完就必须让出CPU，让其他任务运行。

void schedule() {
    struct task *current = get_highest_priority_task();

    if (current->quota > 0) {
        current->run();
        current->quota -= 1;  // 消耗1ms配额
    } else {
        // 配额用完，放入等待队列
        current->quota = 计算新配额(current->priority);
        移到等待队列(current);
    }
}

这个"运行配额"，就是所谓的时间片（Time Slice）。

你部署新系统，监控数据显示：低优先级任务终于能获得CPU时间了！饥饿问题解决了。

但很快你发现了一个恼人的问题：敲击键盘后到字符的显示能明显感觉到卡顿。

你分析原因：终端程序其实大部分时间都在等待用户输入（处于睡眠状态），只有用户敲键盘的那一刻才需要CPU，而且只需要几微秒就能处理完，但如果此时还有其它任务在排队，那么就必须等待，这类交互式任务应该被优先响应，但你的调度器根本无法区分它们。

你尝试修补：增加一套启发式规则来猜测哪些任务是交互式的，如果是交互式任务就给更高的优先级。

void 检测交互式任务(struct task *t) {
    // 如果任务经常主动让出CPU（等待IO），就认为它是交互式的
    if (t->睡眠时间 > t->运行时间) {
        t->is_interactive = 1;
        t->priority -= 5;   // 给它更高优先级
    }
}

这个方法有时有效，有时又判断错误。一个频繁读取磁盘的数据库程序被误判为"交互式任务"，优先级被拉高，反而饿死了真正的终端程序。

你不断增加判断条件：看睡眠次数、看平均运行时间、看IO等待比例......代码越来越复杂，但效果总是时好时坏。

你开始怀疑：是不是这整个思路就有问题？

从头开始想

2004年的某个深夜，你决定把之前所有的设计推倒，从最根本的问题重新想起：我到底想要什么？

你在纸上写下答案：我想要每个任务都获得公平的CPU时间。

什么是"公平"？

你想了一个例子：如果有10个同等重要的任务，理想情况下，它们应该各自获得10%的CPU时间。

那为什么不直接追踪每个任务已经获得了多少CPU时间？总是让获得时间最少的任务先执行，不就自然公平了吗？

你开始在白板上画新的设计：

struct task {
    int pid;
    uint64 runtime;  // 这个任务已经运行了多久
};

void schedule() {
    // 找到运行时间最短的任务
    struct task *next = 找到runtime最小的任务();

    uint64 start = now();
    next->run();
    uint64 delta = now() - start;

    // 更新运行时间
    next->runtime += delta;
}

思路很简单：

• 不再分配固定配额
• 只记录每个任务"已经运行了多久"
• 总是让"运行时间最短"的任务先执行

你部署到测试系统上，效果惊人：10个任务的CPU时间差异很小！

然后你做了一个关键测试：在编译大项目的同时，打开终端输入命令。

你屏住呼吸，敲下键盘——

字符瞬间就显示出来了。

你愣了一下，然后意识到为什么：

编译程序：一直在疯狂使用CPU
  → runtime 增长很快 → 比如已经累积到 5000ms

终端程序：大部分时间在等待你敲键盘（睡眠状态）
  → runtime 几乎不增长 → 比如只有 3ms

当你敲下键盘的那一刻，终端程序从睡眠中醒来，调度器一看：它的运行时间只有 3ms，编译程序已经 5000ms了——终端程序立刻获得CPU！

你突然明白了：之前那套令人头疼的"启发式交互式检测"，在这套新方案里根本不需要了！

不需要猜测哪个任务是交互式的，不需要任何特殊规则。IO密集型任务因为频繁睡眠，运行时间天然增长得慢，醒来后天然排在队列最前面。这不是一个专门设计的特性，而是"追踪已用时间"这个思路带来的自然结果，哪个任务的运行时间少，谁先执行。

虚拟时间

然而用户任务还是需要区分重要程度——比如数据库进程应该比日志备份进程获得更多CPU时间。

该怎么实现优先级呢，能不能在记账的时候做手脚？

就像不同国家的货币有不同的汇率：

• 重要任务：实际运行10秒，账本上只记1秒（"汇率"高）
• 普通任务：实际运行1秒，账本上记1秒
• 不重要任务：实际运行1秒，账本上记10秒（"汇率"低）

这样，重要任务的运行时间增长慢，自然会更频繁地被调度——而且仍然是同一套规则，不需要额外的机制！

你修改代码，给每个任务加上一个"汇率"：

struct task {
    int pid;
    int nice;         // 用户设置的重要程度（-20到+19）
    u64 vruntime;     // 换算后的运行时间
    int weight;       // 汇率（由nice值决定）
};

void schedule() {
    struct task *next = 找到vruntime最小的任务();

    u64 start = now();
    next->run();
    u64 delta = now() - start;  // 实际运行时间

    // 用汇率换算后再记账
    next->vruntime += delta * 1024 / next->weight;
}

这个"换算后的运行时间"，就是所谓的的虚拟运行时间（Virtual Runtime，简称vruntime）。

这套调度机制就是所谓的CFS调度，Completely Fair Scheduler。

最后提前祝大家新年快乐，我们年后见！