理解Linux内核：调度器

# 调度器 来源：https://internals-for-interns.com/posts/linux-kernel-scheduler 在上一篇文章 (https://internals-for-interns.com/posts/linux-kernel-memory-manager/) 中，我们了解了内核如何为每个进程提供其独立的私有内存视图。但内存只是一个进程实际*运行*所需的一半。另一半是 CPU 本身——而一台机器中的 CPU 数量有限，通常却有数百或数千个任务想要在上面运行。 因此，必须有人不断地决定谁能获得 CPU 以及使用多长时间。这个角色就是**调度器**。每几毫秒，在每个核心上，内核都会问自己同样的问题——*在所有当前想要运行的任务中，接下来谁运行？*——答案必须快速、公平，并且足够好，以至于即使在编译任务占满所有核心时，你的文本编辑器也能保持响应。 让我们逐步深入，因为调度器包含许多活动部件。我们将从调度器到底在调度什么开始——进程和线程在底层究竟是什么。然后我们将看到 Linux 并非只有一个调度器，而是有多个，以**调度类**的形式堆叠。接着我们将研究一个运行中的任务何时停止运行（这比听起来更有趣），并查看从一个任务切换到另一个任务的开销。最后，我们将触及核心：内核究竟如何决定下一个运行哪个任务，使用的算法称为 **EEVDF**。 > **📌 范围说明** 本文所有内容基于 Linux **7.1**（调度器核心位于 `kernel/sched/` (https://github.com/torvalds/linux/tree/v7.1/kernel/sched)，主要在 `fair.c` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/fair.c) 和 `core.c` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/core.c) 中）。并且这是刻意的简化：真实实现有更多内容——跨 CPU 的负载均衡、通过 cgroups 的组调度、CPU 带宽控制、NUMA 感知以及无数边界情况——为了保持核心思路清晰，我跳过了这些。 那么，让我们从调度器本身开始的地方开始：即在 CPU 上实际被调度进出的事物。 ## 调度器实际调度什么 第一个惊喜来了，这能澄清很多混淆：内核并不调度“进程”或“线程”。这些是我们用户空间的用语。在内核中，只有一种可调度的东西——一个 **`task_struct`** (`include/linux/sched.h:820` (https://github.com/torvalds/linux/blob/v7.1/include/linux/sched.h#L820))，内核记录的一个执行流，一件可以在 CPU 上运行指令的事物。 你称之为“进程”和你称之为“线程”的东西，在底层都是完全相同的对象。唯一的区别在于**它们共享什么**。当你使用 `fork()` (https://github.com/torvalds/linux/blob/v7.1/kernel/fork.c#L2802) 创建一个新进程时，你会得到一个全新的 `task_struct`，它与父进程不共享任何东西——自己的内存、自己的文件描述符、自己的一切。当你创建一个线程（使用 `clone()` (https://github.com/torvalds/linux/blob/v7.1/kernel/fork.c#L2847) 和合适的标志位）时，你*也*会得到一个全新的 `task_struct`，只是这个 `task_struct` 与生成它的任务共享地址空间、打开的文件、信号处理程序等。因此，“多线程进程”实际上只是一堆恰好指向同一块内存的 `task_struct`。 描述使用 fork 创建的进程（一个拥有私有内存、文件和信号的 task_struct）与使用 clone 创建的线程（多个 task_struct 共享一个地址空间）的对比图，调度器在下方将所有任务简单视为 task_struct 从调度器的角度来看，这些都不重要——它不知道也不关心谁共享了什么。它只看到一堆 `task_struct`，有些是可运行的，有些不是，然后从可运行的任务中挑选。CPU 上所有可运行的东西都是一个 `task_struct`，仅此而已。 现在，`task_struct` 非常庞大——它包含了内核关于一个任务了解的所有信息——但调度器只关心其中很小一部分。每个任务内部都嵌入了一个小的调度状态包（称为 `sched_entity`，`include/linux/sched.h:575` (https://github.com/torvalds/linux/blob/v7.1/include/linux/sched.h#L575)），而这个小包——不是它周围庞大的结构体——才是调度器实际进行推理的对象。 这里有有趣的数字，名称如 `vruntime`、`vlag`、`deadline` 和 `slice`。暂时不必担心这些术语的含义——解读它们基本上就是本文其余部分的内容。现在只需记住这个结构：每个可运行的任务都携带一小块记账状态，调度器在决定下一个运行谁时会读取这一部分。 但“调度器”这个说法有点不太准确，因为实际上并不只有一个——因此，在我们继续之前，先看看谁得到了决策权。 ## 调度类：谁先被询问 在进入*那个*算法之前，有一个转折：Linux 实际上并不只有一个调度器。它有多个，并且它们以严格的等级顺序堆叠。这些堆叠的调度器被称为**调度类**，每个调度类都是一种针对不同类型工作负载的自包含策略。 它们协作的方式非常简单。当 CPU 需要运行某个东西时，内核从堆栈顶部开始向下询问每个类：“有可运行的东西吗？”第一个回答“有”的类胜出，其下的所有类甚至没有投票权。因此，一个类只有在*所有*它上面的类都没有提供任务时才会运行任务。 调度类作为从上到下的优先级堆栈的示意图——stop、deadline、rt、fair（EEVDF，突出显示为几乎所有代码运行的地方）、ext 和 idle——内核沿着堆栈向下询问每个类是否有可运行任务，第一个有工作的类获胜 那么这些框里有什么？顶部的三个都存在是为了赋予*某些*任务比普通工作更优先运行的权利。最顶部的是 `stop`，它实际上不是一个调度策略，而是内核在需要 CPU 立即执行一件紧急事情时使用的“放下一切”杠杆——比如将任务从一个正在关闭的核心上迁移出去。它下面是 `deadline`，处理有硬实时需求的任务（比如音频或机器人），你不是要求一个优先级，而是要求一个保证：“这个任务每段时间需要这么多毫秒的 CPU”。然后 `rt` 是经典实时优先级——一个实时任务可以运行任意长时间，只有在遇到更高优先级的任务时才会让出 CPU，这对延迟敏感的代码来说很棒，但如果这样的任务从不休眠，这也是冻结你的机器的好方法。 不过，问题是：在普通的桌面或服务器上，顶部的三个框几乎总是*空的*。这就引出了本文其余部分相关的那个类：**`fair`**。这实际上是你运行的所有东西所在的地方——你的 shell、浏览器、数据库、那个编译任务。这些任务都没有特殊的时序要求；它们只是想要 CPU 的一个合理时间片，而公平类的全部工作就是*公平地*分配这些时间片。由于它上面的类通常处于空闲状态，公平类几乎一直在主导运行——所以当人们说“Linux 调度器”时，他们几乎总是指的是这个。 底部还有两个类，只是为了完整性：`ext` 是一个较新的添加，允许你将整个调度策略作为 BPF 程序加载，便于在不重新编译内核的情况下进行实验；而 `idle` 是底线，一个什么都不做的任务，只在没有其他任务想要 CPU 时运行，并安静地让核心休眠以节省电能。我们不会详述这两个——从现在开始，一切都关于 `fair`。 公平类构建在一个名字吓人的算法上：**EEVDF**，*最早合格虚拟截止时间优先*。不要被名字吓倒——我们稍后会逐步解析它，结果发现它是一个相当直观的概念。 在我们深入 EEVDF 如何*选择*之前，先了解它何时有机会选择是有帮助的——即运行中的任务释放 CPU 的时刻。 ## 运行中的任务何时停止运行？ 假设一个任务正在 CPU 上愉快地运行。是什么让它*停止*以便其他任务可以运行？这是人们通常一带而过的部分，但正是整个系统的实际所在。任务放弃 CPU 实际上只有两种方式，理解这两种方式就理解了调度器的大部分内容。我们先来看比较温和的一种。 ### 方式一：自愿阻塞 任务停止运行的最常见原因是它请求一个尚未拥有的东西。它调用 `read()` 读取一个没有数据的 socket，获取被其他人持有的 `mutex`，调用 `sleep()`，等待条件变量——任何无法立即完成的操作。 当这种情况发生时，在阻塞原语的内部深处，内核将任务的状态设置为“不可运行”，并调用 **`schedule()`** (`kernel/sched/core.c:7273` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/core.c#L7273))。这是任务自愿地说“我现在无事可做，把 CPU 给别人吧”。调度器将任务从运行队列中彻底移除（它不可运行，所以没有必要考虑它），选择另一个任务，并切换到它。阻塞的任务稍后会在它等待的事件发生时被放*回*运行队列——那是一个**唤醒**操作，我们稍后会谈到。 这是干净的合作情况。任务自己发起了交接。但并非每个任务都这么有礼貌。 ### 方式二：被抢占 但如果有一个任务*从不*阻塞呢？一个密集计算的循环，一个 `while(1)`，一个占满核心的视频编码器。如果阻塞是放弃 CPU 的唯一方式，那么那个任务将永远运行下去，饿死所有其他任务。因此，内核必须能够*夺走*CPU——这就是**抢占**。 巧妙之处在于：抢占几乎从来不是立即发生的。内核不会在指令中间粗暴地拉走一个任务。相反，当它决定一个任务应该被抢占时，它只是**设置一个标志位**——`TIF_NEED_RESCHED`，字面意思是“这个任务需要重新调度”（`resched_curr()`，`kernel/sched/core.c:1212` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/core.c#L1212)）——然后让它继续运行一会儿。设置标志位很廉价且安全，即使在像定时器中断这样的尴尬位置进行操作，而实际切换任务在那里可能是危险的。这个标志位只是一个便利贴：“在下一个安全机会时把这个任务切换出去”。 这些安全机会是定义良好的点，内核在那里检查标志位，如果被设置，就调用 `schedule()` 进行真正的切换。最常见的点是**返回用户空间**——每次任务从内核弹出回到你的代码后（经过系统调用或中断），内核首先检查这个标志位。 因此，节奏始终是*决定 → 设置标志位 → 再运行一会儿 → 到达安全点 → 切换*。这种延迟的、由标志位驱动的设计是整个架构的脊梁——甚至一个**唤醒操作也从不直接切换任务。**它只是使一个任务变为可运行，并且如果该任务值得 CPU，就在当前运行的任务上设置标志位；实际的切换稍后在安全点发生。 任务三种状态的状态机——RUNNING（在 CPU 上）、RUNNABLE（在运行队列中等待）和 BLOCKED（睡眠，不在运行队列）——带有标注的转换：运行中通过调用 schedule() 阻塞；唤醒将其移回可运行；调度器通过上下文切换选择一个可运行任务；运行中的任务在安全点执行其重新调度标志时被抢占回可运行 就我们的目的而言，一个任务在三个主要状态之间移动。**Running** 下降到 **blocked**，当它自愿等待某个东西时；稍后一个**唤醒**将其从 blocked 移到 **runnable**（等待轮到它）。从 runnable，调度器通过选择它将其提升回 **running**；而 running 的任务在被抢占时被推回 runnable。注意从 blocked 到 running 没有直接的箭头——被唤醒的任务总是重新加入队列并等待被选择。 那么是谁决定设置那个抢占标志位，依据是什么？主要有两个触发点：周期性的 tick 和唤醒。先看 tick。 #### 周期性 tick——心跳 每个 CPU 都有一个以稳定、规律节奏触发的定时器——这被称为 **tick**。每次触发时，内核运行一个小例程 `sched_tick()` (`kernel/sched/core.c:5636` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/core.c#L5636))，它做两件事：累加当前任务到目前为止使用的 CPU 时间，然后检查这个时间是否超过了分配给该任务的时间片。如果任务用完了它的时间片，内核就在它上面设置抢占标志位，该任务将在下一个安全点被切换出去。 这就是调度器的心跳：它阻止了一个 CPU 密集型的、从不主动阻塞的任务永远占用一个核心。 tick 处理那些超时滞留的任务；另一个触发点发生在新的竞争者突然出现时。 #### 唤醒——出现了更值得运行的人 另一个触发点是**唤醒**。回想一下，阻塞的任务是正在睡眠、等待某个东西的任务——而某个时刻那个东西发生了：它的数据到达了，或者它想要的锁被释放了。当这种情况发生时，内核唤醒该任务并将其放回运行队列，准备再次运行。 但 CPU 可能已经忙着运行另一个任务。因此，内核停下来问一个问题（在 `wakeup_preempt_fair()` 中，`kernel/sched/fair.c:9055` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/fair.c#L9055)）：这个刚被唤醒的任务是否比当前运行的任务更值得获得 CPU？如果答案是肯定的——根据我们即将了解的 EEVDF 规则——它就在当前任务上设置抢占标志位。和往常一样，它不会立即切换，只是设置标志。这就是让机器感觉响应迅速的原因：当你按下一个键并唤醒编辑器时，编辑器几乎可以立即推开一个长期运行的后台编译任务。 我们一直在说切换“稍后在安全点发生”——那么让我们停止模糊处理，看看实际切换涉及什么，以及为什么内核如此不情愿立即执行它。 ## 上下文切换及其开销 一旦调度器选择了下一个任务，并且假设它与当前运行的任务不同，它就会调用 `context_switch()` (`kernel/sched/core.c:5328` (https://github.com/torvalds/linux/blob/v7.1/kernel/sched/core.c#L5328)) 来实际交出 CPU。（如果选择返回的是*同一个*任务——这很常见——它就会完全跳过切换；最便宜的上下文切换是你不需要做的那一种。） 那个小小的“如果不同”包含了很多工作，因为交换不是免费的。显而易见的开销是容易的部分：保存退出任务的 CPU 状态——其寄存器、程序计数器、栈指针——并加载进入任务的状态。这是真实但廉价的，大约微秒级别。 昂贵的部分是切换*之后*发生的一切，归结为缓存变冷。CPU 保存了几个最近使用东西的缓存以便快速访问，避免重复做慢速工作，而一次上下文切换往往会使它们失效。 最明显的例子是 **TLB**。正如我们在内存管理器文章 (https://internals-for-interns.com/posts/linux-kernel-memory-manager/) 中看到的，程序使用的每个内存地址都必须转换为实际的物理位置，而 TLB 是一个小的转换缓存，这样 CPU 就不必每次都重新查找。但如果下一个任务属于不同的进程，它有自己独立的内存布局——因此内核切换地址空间，这通常会清空 TLB。新的