Linux内核CFS调度器的核心演进与设计哲学

1965年，假设你是一名操作系统工程师。当时，计算机正从单任务时代迈向多任务时代——一台机器可以同时运行多个程序了。

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

这问题看似简单，实则复杂。如果处理不好，各种古怪的问题都会涌现：

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

为此，你必须设计一个“调度器”来分配宝贵的CPU时间。

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

最朴素的想法是：先来先服务（FIFO）。就像在银行排队，谁先到谁先办业务。

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）。

至此，一套全新的调度机制诞生了。它不再基于固定的时间片轮转，也不再依赖不可靠的启发式规则，而是通过持续追踪和比较每个任务的 vruntime，来逼近一种理想的公平状态。这套机制，就是如今 Linux 内核 中大名鼎鼎的 完全公平调度器（Completely Fair Scheduler, CFS）。

从先来先服务的朴素，到优先级的引入，再到时间片轮转的修补，最终回归“公平记账”的本质，CFS的演进历程深刻地揭示了操作系统核心机制的设计哲学。想了解更多关于 操作系统 和底层原理的深度讨论，欢迎访问云栈社区，与更多开发者一同探索技术的本质。其中，进程调度是计算机基础领域永恒的话题之一。