第3章 进程调度（Process Scheduling）

一、导读

1.1 本章学习目标

理解进程调度的基本概念：为什么需要调度器、调度的目标是什么

掌握 Linux 支持的各类调度策略（SCHED_NORMAL、SCHED_FIFO、SCHED_RR、SCHED_BATCH、SCHED_IDLE）

深入理解 CFS（Completely Fair Scheduler）的设计思想和实现原理

掌握调度实体（sched_entity）和虚拟运行时间（vruntime）的概念

理解红黑树在 CFS 中的应用及其 O(log N) 的调度复杂度

了解实时调度器的优先级驱动机制及其与 CFS 的协作关系

掌握进程优先级的计算方法：nice 值、权重与 vruntime 的关系

理解调度时机（schedule() 的调用点）和负载均衡的基本概念

1.2 为什么本章如此重要

进程调度是操作系统的核心决策机制。在多任务操作系统中，CPU 是最宝贵的资源，调度器决定了哪个进程在什么时刻获得 CPU，这直接影响系统的吞吐量、响应时间和公平性。一个设计精良的调度器可以让系统在高负载下仍然保持良好的交互性，而一个糟糕的调度器则会导致系统卡顿、饥饿甚至死锁。

Linux 的调度器经历了多次重大演进：从早期的简单轮转调度，到 2.5 开发系列引入的 O(1) 调度器，再到 2.6.23 引入的 CFS（完全公平调度器）。CFS 的设计哲学是"完全公平"——它试图模拟理想的多任务处理器，让每个进程获得与其权重成比例的 CPU 时间。CFS 的实现优雅而高效，使用红黑树在 O(log N) 时间内完成调度决策，取代了 O(1) 调度器中复杂的运行队列和过期列表。

对于系统管理员和性能工程师而言，理解调度器的工作原理是进行性能调优的基础。合理设置进程的调度策略和优先级，可以显著改善关键应用的性能。对于内核开发者而言，调度器是必须深入理解的核心子系统。

1.3 核心问题引导

为什么"完全公平"是一个好的调度目标？它如何平衡吞吐量和交互性？

CFS 的 vruntime 是什么？为什么需要"虚拟"运行时间而不是实际运行时间？

红黑树在 CFS 中起什么作用？为什么选择红黑树而不是其他数据结构？

nice 值如何影响进程获得的 CPU 时间？nice 值从 -20 到 19 的权重差异有多大？

实时进程和普通进程在调度上如何协调？实时进程会不会完全饿死普通进程？

调度器在什么时刻被触发？时钟中断在调度中扮演什么角色？

多核系统中，调度器如何实现负载均衡？进程迁移的代价是什么？

SCHED_BATCH 和 SCHED_IDLE 策略适用于什么场景？

二、核心概念详解

3.1 CFS 完全公平调度器

CFS（Completely Fair Scheduler）由 Ingo Molnar 在 2007 年引入 Linux 2.6.23，取代了之前的 O(1) 调度器。CFS 的核心思想是：维护一个"理想的多任务处理器"模型，在这个理想模型中，每个可运行进程同时获得 CPU 的 1/N 时间（N 为可运行进程数）。CFS 的任务就是尽可能逼近这个理想模型。

CFS 通过虚拟运行时间（vruntime）来跟踪每个进程的实际运行与理想分配之间的偏差。vruntime 表示进程"应该"已经运行的时间量。当一个进程实际运行时，其 vruntime 会增加，但增加的速度与其权重（由 nice 值决定）成反比。高优先级进程的 vruntime 增长更慢，因此调度器选择 vruntime 最小的进程运行时，实际上是在补偿那些"跑得少"的进程。

CFS 使用红黑树来组织所有可运行的进程，以 vruntime 为排序键。红黑树的"最左"节点（vruntime 最小的节点）就是下一个应该运行的进程。红黑树的插入、删除和查找操作都是 O(log N) 的，这保证了调度决策的高效性。与 O(1) 调度器的固定时间复杂度相比，CFS 的 O(log N) 在实际场景中通常更快，因为 O(1) 调度器需要维护复杂的运行队列和过期数组，其常数因子很大。

3.2 调度策略与优先级

Linux 支持多种调度策略，分为两大类：普通调度策略和实时调度策略。

普通调度策略包括：SCHED_NORMAL（也叫 SCHED_OTHER），用于普通的非实时进程，由 CFS 管理；SCHED_BATCH，用于批处理作业，调度器假设这类进程是 CPU 密集型的，不会频繁唤醒，因此不会为了交互性而提前调度；SCHED_IDLE，优先级最低的调度策略，进程只在系统完全空闲时才获得 CPU。

实时调度策略包括：SCHED_FIFO（先到先服务），实时进程运行直到自愿放弃 CPU 或被更高优先级的实时进程抢占；SCHED_RR（轮转），与 FIFO 类似，但在时间片用完后会让出 CPU，让同优先级的其他实时进程运行。实时进程的优先级范围是 0-99（数字越大优先级越高），远高于普通进程。

普通进程的优先级通过 nice 值调整，范围从 -20（最高优先级）到 19（最低优先级），默认值为 0。nice 值通过权重表映射为调度权重。权重表的设计使得 nice 值每降低 1，权重增加约 10%。这意味着 nice 值 -20 的进程权重约为 nice 值 0 的进程的 8 倍，获得的 CPU 时间也约为 8 倍。

3.3 调度时机与上下文切换

调度器并非持续运行，而是在特定时机被触发。主要的调度时机包括：时钟中断（tick），调度器在中断处理程序中检查当前进程的时间片是否用完；进程唤醒，当一个高优先级的进程从睡眠中被唤醒时，调度器会比较它与当前进程的优先级；系统调用，某些系统调用（如 nice()、sched_yield()）会显式触发调度。

调度器的核心函数是 schedule()，它执行以下步骤：选择最高优先级的运行队列（在多核系统中，每个 CPU 有自己的运行队列）；对于 CFS，从红黑树中选择 vruntime 最小的进程作为下一个运行进程；执行上下文切换（context switch），保存当前进程的 CPU 寄存器状态，恢复下一个进程的寄存器状态。上下文切换是内核中最昂贵的操作之一，因为它涉及 TLB 刷新、缓存失效等硬件级别的代价。

3.4 多核调度与负载均衡

在多核系统中，每个 CPU 核心有自己的运行队列。调度器需要在两个目标之间取得平衡：一是保持进程在同一个 CPU 上运行以利用缓存局部性（cache affinity），二是在各 CPU 之间均衡分配负载以避免某些核心过载而其他核心空闲。

Linux 采用分层调度域（scheduling domain）的概念来实现负载均衡。调度域按照硬件拓扑结构组织：最底层是单个 CPU 核心，往上是核心所在的处理器包（package），再往上是 NUMA 节点。负载均衡器定期检查各运行队列的负载差异，当差异超过阈值时，将进程从过载的 CPU 迁移到空闲的 CPU。进程迁移的代价包括缓存失效和 TLB 刷新，因此调度器会尽量减小迁移频率。

三、深入分析与讨论

3.1 CFS 的公平性保证与局限性

CFS 的公平性保证建立在 vruntime 的基础上。理论上，如果所有进程的 nice 值相同，每个进程获得的 CPU 时间应该完全相等。但在实际中，由于进程的行为模式不同（CPU 密集型 vs I/O 密集型），公平性的含义更加复杂。I/O 密集型进程频繁进入睡眠和唤醒，每次唤醒时 vruntime 较小，因此会获得更多的 CPU 时间来"追赶"。这种行为实际上有利于交互性——用户输入触发的唤醒会立即获得 CPU 响应。

然而，CFS 也有局限性。在大量短生命周期进程频繁创建和销毁的场景下，CFS 的调度开销会增加（因为红黑树的插入和删除操作）。此外，CFS 对 NUMA 架构的感知有限，可能导致进程被调度到远端内存节点，增加内存访问延迟。Linux 4.x 引入的 NUMA 平衡机制部分解决了这个问题。

3.2 实时调度的风险与防护

实时调度策略赋予了进程极高的优先级，但也带来了风险。如果一个实时进程进入死循环而不让出 CPU，它会饿死所有普通进程，甚至导致系统无法响应。为了防止这种情况，Linux 提供了 RLIMIT_RTTIME 资源限制，限制实时进程在没有自愿让出 CPU 的情况下可以连续运行的时间。超过限制的实时进程会收到 SIGXCPU 信号。

此外，/proc/sys/kernel/sched_rt_runtime_us 和 sched_rt_period_us 参数控制实时进程在一个周期内最多可以使用的 CPU 时间。默认配置下，实时进程最多使用 95% 的 CPU 时间，保留 5% 给普通进程，确保系统不会完全无响应。

四、实践案例

4.1 案例一：使用 chrt 和 nice 调整进程调度

在服务器环境中，可以通过 nice 命令调整普通进程的优先级。例如，nice -n -10 ./compute-intensive-task 将进程的 nice 值设为 -10，使其获得更多 CPU 时间。对于需要严格实时响应的应用（如音频处理），可以使用 chrt 命令设置实时调度策略：chrt -f 50 ./audio-processor 将进程设置为 SCHED_FIFO 策略，优先级 50。需要注意的是，设置实时策略需要 CAP_SYS_NICE 能力。

4.2 案例二：分析调度延迟与性能问题

当系统出现交互延迟时，可以使用 ftrace 的 sched 跟踪点来分析调度行为。通过跟踪 sched_switch、sched_wakeup 等事件，可以观察进程从唤醒到实际获得 CPU 之间的延迟（wakeup latency）。如果某个进程的唤醒延迟过高，可能是因为运行队列过长或当前进程占用 CPU 时间过长。解决方案可能包括：调整 nice 值、使用实时策略、减少 CPU 密集型任务的运行时间等。

五、常见误区与注意事项

误区：nice 值越小进程运行越快。nice 值影响的是进程获得的 CPU 时间比例，而非单次运行的速度。一个 nice 值 -20 的进程并不会比 nice 值 0 的进程在单次运行中更快，只是它获得更多运行机会。

误区：CFS 保证每个进程获得完全相同的 CPU 时间。CFS 保证的是按权重比例的公平分配，而非绝对平均。nice 值不同的进程获得的 CPU 时间不同。

误区：实时进程总是优先于普通进程。虽然实时进程的优先级确实更高，但 sched_rt_runtime_us 限制了实时进程的 CPU 使用时间，保留部分 CPU 给普通进程。

注意：频繁上下文切换会严重影响性能。每次上下文切换涉及寄存器保存/恢复、TLB 刷新、缓存失效等代价。在高并发服务器中，过多的线程竞争 CPU 会导致频繁的上下文切换，反而降低吞吐量。

注意：时钟频率（HZ）影响调度精度。内核配置中的 CONFIG_HZ 决定了每秒的时钟中断次数。更高的 HZ 值意味着更精细的调度粒度，但也增加了中断开销。

六、本章小结

本章深入讲解了 Linux 的进程调度机制。CFS（完全公平调度器）是 Linux 的默认调度器，通过虚拟运行时间（vruntime）和红黑树实现了高效的公平调度。调度策略分为普通策略（SCHED_NORMAL、SCHED_BATCH、SCHED_IDLE）和实时策略（SCHED_FIFO、SCHED_RR），分别适用于不同的应用场景。nice 值允许用户调整普通进程的优先级，影响其获得的 CPU 时间比例。调度时机包括时钟中断、进程唤醒和显式系统调用。在多核系统中，调度域和负载均衡机制确保各 CPU 之间的工作负载均衡。理解调度器的工作原理，对于编写高性能程序、优化系统响应时间以及进行故障排查都至关重要。

七、思考题与练习

计算：如果系统中有一个 nice 值为 0 的进程和一个 nice 值为 -10 的进程同时竞争 CPU，它们各自大约能获得多少 CPU 时间？

分析 CFS 中红黑树的时间复杂度：为什么是 O(log N) 而不是 O(1)？在实际场景中，N 通常有多大？

设计一个实验，测量不同 nice 值下进程获得的 CPU 时间比例，验证权重表的设计。

比较 CFS 与 O(1) 调度器的优缺点。为什么 CFS 最终取代了 O(1) 调度器？

分析一个实时进程饿死普通进程的场景，说明 sched_rt_runtime_us 如何防止这种情况。

研究 Linux 的调度跟踪工具（如 /proc/schedstat、ftrace sched 事件），分析一个实际系统中的调度行为。

讨论在多核 NUMA 系统中，调度器如何平衡缓存局部性和负载均衡之间的矛盾。

解释"调度延迟"（scheduling latency）的概念，以及它对交互式应用和实时应用的不同影响。