跳到主要内容

第 10 章 CPU 调度器（第 1 部分）

章节引子​

前两章我们在内存管理的泥潭里摸爬滚打——MGLRU、DAMON、OOM Killer，这些名字现在听起来应该既熟悉又让人头大。我们要么在动态分配内存，要么在拼命回收内存，总之，我们一直在围着内存转。

现在，让我们换个频道。

这章和下一章，我们要把注意力从内存移到 CPU 上。准确地说，是 CPU 调度——也就是操作系统决定“谁该在 CPU 上跑，谁该滚下去等待”的那套机制。这不仅是写内核和驱动必须懂的基础，作为一个系统架构师，如果你想让你的用户空间程序在高并发环境下不卡顿、不崩，你也必须理解这块东西。

我们将从零开始：首先要搞清楚内核到底在调度谁（是进程还是线程？），然后理解 POSIX 定义的那些调度策略到底是个什么玩意儿。接着，我们会拿起 perf 这把“手术刀”，把 CPU 的运行时剖开来看——亲眼看着线程在核心之间跳来跳去。

在掌握了这些可视化工具之后，我们会像剥洋葱一样剥开内核内部，看看 Linux 是如何通过“模块化调度类”来实现复杂的调度逻辑的。最后，我们将深入代码级细节，搞清楚调度器函数到底是谁在调用、什么时候调用，以及上下文切换到底发生了什么。

但在我们一头扎进代码之前，有一个经常被误解的事实需要澄清：CPU 是一种共享资源，但这并不意味着只有进程在抢它。Linux 有一个更深层的资源管理框架——cgroups（控制组）。如果你看过前面的图 10.1，你可能会注意到顶部有一个模糊的“cgroups”层。现在先别管它，我们会在下一章专门讲它。但你要知道，最终的调度决策，往往是调度器和 cgroups 共同作用的结果。

准备好了吗？这趟旅程可能会有点晕车，但绝对值得。

10.1 CPU 调度器内核机理（第一部分）：必修背景知识​

在看复杂的调度算法之前，我们需要先把几个最基础的概念钉死在脑子里。这些是理解后面所有逻辑的地基。

10.1.1 Linux 的内核可调度实体（KSE）到底是哪个？​

我们在第 6 章讲进程和线程时提到过，每一个活着的用户模式线程，内核都会给它分配一个 task_struct 结构体，以及一个用户栈和一个内核栈。内核线程虽然也有 task_struct，但它们只有内核栈。

现在的关键问题是：当调度器说“该换人干活了”的时候，它换的到底是“谁”？

在操作系统术语里，这东西叫 Kernel Schedulable Entity (KSE)。

很多人直觉上认为“进程”是调度的基本单位。但在 Linux 上，这个直觉是错的。

Linux 的 KSE 是 线程，不是进程（当然，每个进程至少包含一个线程）。调度器是以线程为粒度进行操作的。

让我们用一个假想的场景来“锚定”这个认知。

假设你的系统只有 1 个 CPU 核心，上面跑了 3 个用户空间进程：

  • P1：只有 1 个线程。
  • P2：有 2 个线程。
  • P3：有 5 个线程。

除此之外，内核里还跑着 3 个内核线程。

那么，现在有多少个实体在抢这一个 CPU 核心？

不是 3（进程数），也不是 6（进程+内核线程数）。 答案是 1 + 2 + 5 + 3 = 11 个线程。

这 11 个线程，如果都处于“可运行”状态（也就是 Ready），它们就会在 CPU 的“运行队列”里打架。至于它们属于哪个进程，调度器并不关心。调度器眼里只有线程。

类比时刻 1：建立映射 你可以把调度器想象成一个交通指挥员。 进程就是车队，而线程是车队里的每一辆车。 调度员并不指挥“车队”走，他指挥的是“每一辆车”。一个车队可能有一辆车，也可能有十辆车，但这跟调度员没关系，他只看车。

类比时刻 2：揭示距离 但这个类比在优先级上会失效。 在现实交通中，车队里的车通常是一起走的。 但在 Linux 里，同一个进程（车队）里的不同线程（车），可以一个在高速上狂奔（高优先级），另一个在路边趴窝（低优先级）。它们在调度器眼里是独立的个体，没什么“兄弟情义”。

类比时刻 3：回收验证 回到那个交通指挥员。 当我们说“系统负载很高”时，实际上是指马路上有 11 辆车在抢道（11 个线程），而不是只有 3 个车队在跑。 如果 P3 车队里的 5 辆车都在疯狂踩油门，那调度员就会一直盯着这 5 辆车，而根本不管 P1 车队那辆孤零零的车。

现在我们搞清楚了：KSE 是线程。所以接下来的讨论中，我们都会用“线程”这个词，而不是“进程”。如果你习惯看老式的 OS 教科书，它们可能还在说“进程状态机”，但现在请你在脑子里自动把它替换成“线程状态机”。

10.1.2 Linux 进程（线程）状态机​

每个 Linux 线程在它的生命周期里，都会在不同的状态之间流转。把这些状态画出来，就是一个状态机。

既然我们已经确立了 KSE 是线程，那我们接下来就用标准的 Linux 术语来描述这些状态。ps 命令通常用一个字母来表示这些状态，比如 R、S、D 等。

核心状态列表

  1. TASK_RUNNING (R state)：

    • 别名：Ready-to-run 或 Running。
    • 含义：这是最容易被误解的状态。它并不代表“正在运行”。它代表**“正在运行”或者“准备好运行”**。
    • 关键点：只要线程在这个状态，它就在运行队列里。Linux 不会刻意区分“正在 CPU 上跑”和“在队列里排队跑”，这两者都是 R。它们都是候选人，随时可能上 CPU。

  2. TASK_INTERRUPTIBLE (S state)：

    • 别名：可中断睡眠。
    • 含义：线程在睡觉（等待某个事件，比如网络包、磁盘 IO）。
    • 特征：虽然是“睡眠”，但它是可以被打扰的。如果这时候给它发个信号（Signal），它会被强行唤醒去处理信号。

  3. TASK_UNINTERRUPTIBLE (D state)：

    • 别名：不可中断睡眠。
    • 含义：线程在睡觉，而且雷打不动。
    • 特征：通常用于极其关键的 IO 等待，这时候不能被信号干扰。如果系统中出现大量 D 状态的进程，通常意味着存储系统挂了或者很慢。这也是为什么 ps 里它显示为 D（Dead？不，是 Disk Wait）。

  4. TASK_STOPPED (T state)：

    • 含义：线程被暂停了。通常是收到了 SIGSTOP 信号，或者正在被调试器跟踪。

  5. TASK_DEAD / TASK_ZOMBIE (X / Z state)：

    • 含义：线程已经挂了，或者变成了僵尸。
    • 僵尸：线程执行完了，父进程还没来给它“收尸”（调用 wait()）。这是一种半死不活的状态，必须在系统中被清理掉。

状态的动态流转

当一个线程刚被 fork() 或 pthread_create() 造出来后，内核会把它设为 TASK_RUNNING（R 状态）。这时它进了运行队列，时刻准备着被调度器选中。

如果这个线程需要等待某个资源（比如读文件），它就会调用调度器相关的睡眠函数，把自己的状态从 R 改成 S 或 D，并从运行队列里拿出来，放到一个等待队列里。

当它等待的事件发生了（比如磁盘数据读上来了），内核会把它“唤醒”。这实际上做了两件事：

  1. 把它从等待队列里摘掉。
  2. 把它重新挂回 CPU 的运行队列，状态改回 TASK_RUNNING。

注意，被唤醒并不意味着立刻就在 CPU 上跑了。它只是又变成了 R 状态的候选人，得排队等调度器翻它的牌子。

代码视角：__state

在代码层面，这一切是怎么实现的？答案在 task_struct 结构体里。

struct task_struct {
    // ...
    unsigned int __state;   // 注意：以前叫 'state'
    // ...
};

这个成员 __state 就是一个整数位掩码。当它是 TASK_RUNNING 时，线程就在跑；当它是 TASK_INTERRUPTIBLE 时，线程就在睡。

⚠️ 踩坑预警 千万别以为系统里只有一个全局的运行队列，也千万别以为只有一个等待队列。 Linux 为每个 CPU 核心都维护了一个独立的运行队列。 等待队列则是到处都是，每个驱动程序、内核模块想用就能建一个。

有了这些背景知识，我们接下来看看 Linux 具体支持哪些调度策略——也就是，它是根据什么规则从运行队列里挑人的。

10.1.3 POSIX 调度策略​

你可以把“调度策略”大致理解为“选拔人才的算法”。

Linux 并不是只有一种调度算法。POSIX 标准强制要求任何合规的操作系统至少得实现三种策略。Linux 不光实现了这三种，还加了几种自己的，并且通过模块化调度类的设计把它们完美地融合在了一起。

首先，我们需要建立一个大前提：系统里的每一个线程，在任何一个时刻，都必然绑定着一种特定的调度策略。 这个策略是可以动态改的。

下面这个表是 Linux 调度策略的速查表，建议你先扫一眼，有点印象，我们后面会挑重点细讲。

调度策略关键特性优先级范围
SCHED_OTHER
(也叫 SCHED_NORMAL)		默认策略。它是“普通人”的策略，追求的是公平和整体吞吐量。它属于 CFS（完全公平调度器）类。Nice 值：
-20 (最高) ~ +19 (最低)
默认为 0
SCHED_FIFO非常激进的实时策略。一旦上了 CPU，除非自己愿意下来（阻塞/退出），或者被更高优先级的线程踹下去，否则它一直占着，时间片无限大。实时优先级：
1 ~ 99
数字越大越猛
SCHED_RR轮转式实时策略。跟 FIFO 一样猛，但它有时间片（默认 100ms）。时间片用完了，如果优先级相同，就换人玩，大家轮流上。实时优先级：
1 ~ 99
SCHED_BATCH适合批处理任务。适合那种不跟人交互、闷头计算的程序。内核会尽量减少对它的抢占，以此来提高吞吐量。Nice 值：-20 ~ +19
SCHED_IDLE极其卑微的策略。优先级比 Nice 19 还低。只有当 CPU 没事儿干的时候，才会让它跑跑。PID 0 的 swapper 空闲线程就是这类。最低（比 nice 19 还低）

表 10.1：Linux（POSIX 兼容）调度策略一览

⚠️ 概念区分：硬实时 vs 软实时 这里的 SCHED_FIFO 和 SCHED_RR 被称为软实时策略。Linux 作为一个通用操作系统（GPOS），默认不是硬实时操作系统（RTOS）。 “硬实时”意味着“万无一失，必须在 deadline 前做完”，而“软实时”意味着“尽量快，但不保命”。 你可以通过打补丁把 Linux 变成硬实时系统，但我们通常跑的都是通用版。

深入细节：SCHED_FIFO vs SCHED_RR

虽然它们都是实时策略，但有个微妙的区别，这在使用中非常关键：

  • SCHED_FIFO：没有时间片概念。如果两个 FIFO 线程优先级相同（比如都是 50），那么先跑的那个会一直跑，直到它主动阻塞或者被高优先级打断。另一个同优先级的线程只能干瞪眼。后果：如果你设计不好，同一个优先级下可能会有线程饿死。
  • SCHED_RR：有时间片（Round Robin）。同优先级的线程大家轮流上，时间片到了就换下一个。这比 FIFO 友好一点。

中断的至高地位

这里必须插入一个“安全刹车”机制。

不管你的线程是 SCHED_FIFO 优先级 99（理论上最高），硬件中断和软件中断永远比它高。中断来了，你的线程也得乖乖让路。这是系统稳定性的最后一道防线。

线程优先级的层级

现在我们把视角拉高，看看 Linux 整个优先级的阶梯图（见图 10.3）。

  1. 实时优先级 (1 ~ 99)：
    • 给 SCHED_FIFO 和 SCHED_RR 用的。
    • 规则：只要有一个实时线程在运行队列里，所有的 SCHED_OTHER（普通线程）都靠边站。它们不在一个竞技场里。
  2. 普通优先级 (Nice 值: -20 ~ +19)：
    • 给 SCHED_OTHER 用的。
    • Nice 值越小，优先级越高。0 是默认值。
    • 这就是个“好人卡”系统：你越“Nice”（大度），你让 CPU 的次数就越多（优先级越低）。

⚠️ 实战经验：Autogroups 的干扰 很多现代发行版开启了 CONFIG_SCHED_AUTOGROUP。这会利用 cgroups 技术给终端窗口下的进程“加成”优先级。这会导致传统的 nice 值看起来失效了。如果你在测试时发现 nice 值不起作用，查一下这个内核选项。

现在我们知道了有哪些策略。接下来，我们需要直观地看一看，这些策略到底是如何在 CPU 上运转的。

10.1.4 可视化调度流​

多核系统让线程可以在不同的 CPU 上并行执行。这提高了吞吐量，但也带来了调试的噩梦。如果几个线程同时操作一块共享内存，谁先谁后？这很难肉眼看出来。

我们需要一种方法，能像看回放一样，看到哪个线程在哪个时刻占了哪个 CPU 核心。

这里有两个工具：一个是简单的 GUI 工具 gnome-system-monitor，另一个是内功深厚的 perf。

方法一：使用 gnome-system-monitor​

这是 GNOME 桌面环境自带的系统监控工具。

为了看到有趣的现象，我们需要制造点“负载”。我们将运行三个 CPU 密集型的进程，并手动把它们绑死在不同的 CPU 核心上。

这里我们要用到一个强力工具：taskset（属于 util-linux 包）。

实验步骤

假设你的系统有 6 个核心（编号 0 到 5）。

  1. 在 CPU 1 上跑一个 yes 进程（这是一个无限循环打印 'y' 的程序，CPU 杀手）： 
    taskset -c 1 yes > /dev/null &
  2. 同理，在 CPU 2 和 CPU 3 上也各跑一个： 
    taskset -c 2 yes > /dev/null &
    taskset -c 3 yes > /dev/null &

现在打开 gnome-system-monitor，点击“资源”标签页。

你会看到类似图 10.4 的画面：CPU 2、3、4（注意 GUI 显示编号通常从 1 开始，所以对应核心 1、2、3）的负载直接拉满到 100%。这就是直观的并发和并行。

用 pkill yes 可以结束这场闹剧。

方法二：使用 perf 工具​

如果你觉得 gnome-system-monitor 太玩具，那 perf 绝对能满足你的极客心。它是 Linux 内核自带的性能分析神器。

⚠️ 前置条件 perf 是跟内核版本强绑定的。在 Ubuntu 上你需要装 linux-tools-$(uname -r)。 如果你编译的是自己魔改过的内核（比如书里自带的 6.1），可能没有对应的 perf 包。建议用发行版自带的内核来做这个实验。

1. 命令行模式：perf sched map

还是刚才的实验场景。为了方便，书里提供了一个脚本 ch10/concurrent_exercise/concurrency，它可以一次性在所有核心上起 yes 进程。

cd ch10/concurrent_exercise
./concurrency 6  # 在 6 个核心上各起一个 yes

在另一个终端窗口，开始录制调度事件：

sudo perf sched record

让它跑个十几秒，然后按 Ctrl+C 停止。这会生成一个名为 perf.data 的二进制文件。

现在，让我们把它变成人能看懂的“地图”：

sudo perf sched map > mymap.txt

打开 mymap.txt，你会看到一堆字符流。这看起来像乱码，但仔细看非常有规律（参考图 10.5）。

  • 每一行代表一个时间点。
  • 每一列代表一个 CPU 核心。
  • 两个字符的代号代表线程。比如 A0 是迁移线程，B0 是我们的 yes 线程。

最震撼的是，如果你用 vim 搜索 B0..D0..F0...，你会发现这几个字符在同一行同时出现（如图 10.6）。这证明了什么？证明了它们真的在并行运行！

2. 图形化模式：perf timechart

如果字符流看着眼晕，perf 还能生成 SVG 矢量图，用浏览器打开，视觉效果拉满。

命令如下：

sudo perf timechart -i ./perf.data

这会生成一个 output.svg 文件。用 Firefox 或 Chrome 打开它（如图 10.7 和 10.8）。

你会看到彩色的条形图。

  • 蓝色代表 Running 状态。
  • 你会清晰地看到我们的 yes 进程像长城一样铺在 CPU 核心上，没完没了地跑。
  • 下面还穿插着其他进程，大部分是灰色的（睡眠状态）。

这种可视化的能力对于分析性能瓶颈（比如为什么我的应用一秒卡顿了两次）简直是救命稻草。

有了这些直观的感受和背景知识，我们现在可以潜入内核深处，看看这套复杂的机制到底是怎么设计出来的。下一节，我们将深入剖析 模块化调度类。

练习题​

练习 1：understanding​

题目：在 Linux 调度器的状态机模型中，TASK_UNINTERRUPTIBLE (D 状态) 和 TASK_INTERRUPTIBLE (S 状态) 都表示进程处于睡眠状态。请从系统管理的角度分析：为什么 Linux 需要 D 状态？如果系统出现大量处于 D 状态的进程且无法恢复，通常暗示了什么系统层面的问题？

答案与解析

答案：D 状态用于处理不可中断的睡眠，通常应用于等待关键 I/O 操作（如磁盘 swap 写入）的场景，以防止进程在数据写入过程中被信号中断而导致数据损坏。如果系统出现大量且无法恢复的 D 状态进程，通常暗示底层存储子系统（如 NFS 挂载无响应、磁盘故障或由于 I/O 栈拥塞导致的“卡死”）出现了严重的阻塞。

解析：本题考察对进程状态机中 S 和 D 状态区别的理解。

  1. 概念区分：S 状态允许被信号唤醒（如用户按 Ctrl+C），适用于大多数等待；D 状态忽略信号，必须等待等待的事件（如硬件 I/O 完成）发生。
  2. 设计意图：D 状态保证了某些关键操作（如写入磁盘数据结构）的原子性，防止进程在持有锁或操作硬件关键路径时被意外终止。
  3. 故障排查：D 状态通常是短暂的。如果进程永久处于 D 状态，意味着它在等待的资源永远无法就绪（例如服务器宕机导致网络 I/O 挂起），这被称为“ uninterruptible sleep deadlock”，是系统管理员需要高度警惕的故障信号。

练习 2：application​

题目：假设你正在开发一个高性能计算应用，其中一个线程需要进行密集的数学运算。默认情况下，该线程使用 SCHED_OTHER 策略。为了保证该线程获得最大的 CPU 时间片且尽可能减少被其他普通进程抢占，在不使用实时策略（SCHED_FIFO/RR）的前提下，你应该如何调整其 Nice 值？对应的命令是什么？

答案与解析

答案：应将 Nice 值调整为 -20（最高优先级）。可以使用命令 nice -n -20 ./your_program 启动程序，或使用 renice -n -20 -p <PID> 修改运行中进程的 Nice 值。

解析：本题考察对 SCHED_OTHER 策略中 Nice 值的实际应用。

  1. 策略限制：SCHED_OTHER 是 Linux 普通进程的默认策略，基于 CFS 算法。它与实时进程（优先级 1-99）不同，无法通过改变策略来抢占。
  2. Nice 值范围：-20 到 +19。-20 代表最高优先级，+19 代表最低。
  3. 应用场景：对于 CPU 密集型任务，将 Nice 值设为 -20 会让 CFS 调度器在计算 vruntime（虚拟运行时间）时给予该任务更高的权重（更小的 vruntime 增长），从而使其在红黑树中更倾向于被调度，减少被其他低优先级（Nice 值大）任务抢占的频率。

练习 3：application​

题目：在一个单核 CPU 系统中，有两个线程：

  • 线程 A：SCHED_FIFO 策略，优先级 10，执行一个无限循环（while(1);）。
  • 线程 B：SCHED_FIFO 策略，优先级 5，试图计算 1+1。
  • 系统中还有若干中断服务程序（ISR）在运行。

请问：线程 B 能有机会运行吗？中断服务程序能运行吗？请详细解释调度器的行为。

答案与解析

答案：线程 B 没有机会运行（直到线程 A 主动让出 CPU 或退出）。中断服务程序（ISR）可以正常运行并抢占线程 A。

解析：本题考察对 SCHED_FIFO 抢占模型和中断优先级的理解。

  1. 线程间调度：SCHED_FIFO 是实时抢占策略。线程 A (Prio 10) 的优先级高于线程 B (Prio 5)。根据规则，只有当高优先级任务（A）阻塞（I/O）、退出或主动放弃 CPU 时，低优先级任务（B）才能运行。由于 A 是无限循环且无阻塞，B 将永久饥饿。
  2. 中断与进程的优先级：Linux 内核的中断（硬件和软中断）优先级高于所有进程（包括 SCHED_FIFO 的优先级 99）。因此，尽管 A 占据了 CPU，当硬件中断发生时（如时钟中断或网络包到达），CPU 仍然会暂停线程 A，转而去执行 ISR。ISR 执行完毕后，才会恢复线程 A 的执行。
  3. 结论：B 饥饿，中断不受影响。这就是为什么编写 SCHED_FIFO 程序时必须小心，避免死循环导致系统软死机（忽略干预的话）。

练习 4：thinking​

题目：Linux 内核源码中有一个被称为“黄金法则”的调度器设计原则：“调度器代码永远不能在原子上下文（包括中断上下文）中运行。” 请思考：如果打破这个原则，允许在持有自旋锁或处于中断上下文时调用 schedule() 进行进程切换，会发生什么灾难性的后果？请结合中断处理和锁机制进行深度分析。

答案与解析

答案：如果打破该原则，会导致“双重获取锁”或死锁，甚至导致系统彻底死锁或内核崩溃。核心原因是 schedule() 会触发 switch_to，切换到另一个可能也试图获取同一个自旋锁的进程，或者在同一 CPU 上再次触发中断。

解析：本题考察对内核调度深层原理和并发控制的综合理解。

  1. 原子上下文的定义：原子上下文意味着内核正在执行临界区代码（持有自旋锁 spinlock）或正在处理中断。此时不能睡眠，不能发生进程调度。
  2. 死锁场景分析（自旋锁视角）：
    • 假设进程 P1 在 CPU0 上持有自旋锁 L（此时禁止抢占），进入临界区。
    • 如果允许在持有锁时调用 schedule()，调度器将 P1 移出运行队列，换入进程 P2。
    • 如果 P2（在 CPU0 上运行）也试图获取锁 L，它将自旋等待 P1 释放锁。
    • 然而，P1 只有在被重新调度回 CPU0 并执行时才能释放锁。
    • 结果：P2 等待 P1，P1 等待 P2（调度器资源），形成死锁。系统将失去响应。
  3. 中断上下文分析：
    • 中断处理程序（ISR）并不属于任何进程，它是“借”当前进程的栈和资源运行的。
    • 如果 ISR 中调用 schedule()，内核将尝试保存“中断上下文”并恢复“进程上下文”。这不仅是逻辑混乱（谁在中断里睡觉？），而且如果中断再次发生（递归中断），内核栈可能溢出或状态完全错乱。
  4. 设计哲学：因此，Linux 强制要求所有可能引起睡眠（进而调用调度器）的函数路径都必须是非原子上下文，这是保证内核并发安全的最基本底线。

要点提炼​

Linux 的内核可调度实体（KSE）是线程而非进程，调度器以线程为粒度进行操作，同一个进程内的不同线程在调度器眼中是完全独立的个体，没有任何“兄弟情义”或必然的同步关系。

理解线程状态流转的关键在于区分 TASK_RUNNING 与实际执行的区别，R 状态仅代表线程处于运行队列中（正在执行或准备好执行），而非 R 状态（如 S 或 D）则意味着线程已放弃 CPU 并进入等待队列，唤醒操作仅是将其重新放回运行队列，并不代表立即获得 CPU。

Linux 将线程优先级严格划分为实时（1-99）和普通两类，只要运行队列中存在实时线程，普通线程无论 Nice 值如何都会被靠边站，且即便是最高优先级的实时线程也必须服从硬件中断和软中断的绝对权威。

虽然 SCHED_FIFO 和 SCHED_RR 均为软实时策略，但前者一旦占用 CPU 只要自身不阻塞或被更高优先级抢占就会一直运行，容易导致同优先级线程饿死，而后者引入了时间片机制，保证了同优先级线程间的公平轮转。

利用 perf sched map 和 perf timechart 等工具可以将 CPU 的运行时数据可视化为字符地图或 SVG 图谱，这不仅能直观验证多核并行性（不同核心同时运行线程），更是诊断复杂调度场景和性能瓶颈的“手术刀”。

编辑此页
最后由 Charliechen114514 于 更新