1. 调度器概述：Linux 调度器发展史与设计哲学

进程调度是 Linux 内核最核心的子系统之一，它决定了哪个进程在何时获得 CPU 使用权。调度器的设计直接影响系统的吞吐量、响应延迟和公平性。本章从历史演进、核心目标与设计哲学三个维度，为后续的性能调优与延迟测量奠定基础。

1.1 Linux 调度器发展史

Linux 调度器经历了四次重大重构，每一次都针对特定负载场景做出了关键改进。下表总结了四个主要版本的对比：

调度器 内核版本 时间复杂度 核心数据结构 主要缺陷
O(n) 调度器 2.4 及更早 O(n) 全局运行队列 + 循环链表 多核扩展性差，交互体验糟糕
O(1) 调度器 2.6.0 ~ 2.6.22 O(1) 140 级优先级位图 + 活跃/过期数组 交互进程提升不足，公平性粗糙
CFS (完全公平调度器) 2.6.23 ~ 6.6 O(log n) 红黑树 (vruntime 为 key) 延迟敏感型负载仍有抖动
EEVDF (最早虚拟截止时间优先) 6.6+ (可选) O(log n) 红黑树 + 截止时间队列 仍在演进，生态尚未完全成熟

1.1.1 O(n) 调度器：简单但低效

在 Linux 2.4 及更早版本中，调度器使用一个全局运行队列，所有可运行进程被链接在一个循环链表中。每次调度时，内核需要遍历整个链表来计算每个进程的“好度”(goodness)，选择得分最高的进程运行。

关键问题： 当系统中存在 100 个进程时，每次调度都需要遍历 100 个节点。随着进程数增加，调度延迟线性增长，多核处理器上的锁竞争更是雪上加霜。
O(n) 调度器：全局链表遍历模型 运行队列 进程 A 进程 B 进程 C … ← 调度器每次遍历所有节点 计算每个进程的 "goodness" 值 时间复杂度 O(n)：进程数越多，调度延迟越大 多核场景下全局锁导致严重扩展性问题

1.1.2 O(1) 调度器：常数时间的突破

Linux 2.6.0 引入的 O(1) 调度器是调度史上的里程碑。它使用两个优先级数组（active 和 expired），每个优先级对应一个链表。调度器通过位图在常数时间内找到最高优先级的非空队列，实现了 O(1) 的选进程操作。

设计亮点： O(1) 调度器将进程分为 140 个优先级（0-99 为实时，100-139 为普通），每个优先级使用独立的链表。调度时只需扫描 140 位的位图，而非遍历所有进程。
O(1) 调度器：优先级位图 + 双数组结构 优先级位图 (140 bit) — 常数时间找到最高优先级非空队列 active 数组 (当前可运行) expired 数组 (时间片耗尽) prio=100 prio=101 prio=102 prio=100 prio=101 时间片耗尽 → 进程移入 expired 数组 active 为空时，交换两个数组指针 优点：调度延迟与进程数无关；缺点：交互进程响应不够好

1.1.3 CFS：完全公平调度器

Linux 2.6.23 合并了 CFS（Completely Fair Scheduler），由 Ingo Molnár 设计。CFS 摒弃了固定时间片和优先级数组，转而使用红黑树按虚拟运行时间（vruntime）排序，实现了“理想多任务处理器”的近似。

核心思想： CFS 模拟一个“完美的多任务处理器”——如果系统中有 N 个进程，每个进程应该获得 1/N 的 CPU 时间。vruntime 记录进程实际运行的时间（经过权重归一化），调度器总是选择 vruntime 最小的进程运行。 
// CFS 核心数据结构简化示意
struct cfs_rq {
    struct rb_root_cached tasks_timeline;  // 红黑树根
    u64 min_vruntime;                      // 最小虚拟运行时间
    unsigned int nr_running;               // 可运行进程数
    u64 exec_clock;                        // 执行时钟
};

// 调度实体
struct sched_entity {
    struct rb_node run_node;               // 红黑树节点
    u64 vruntime;                          // 虚拟运行时间
    u64 sum_exec_runtime;                  // 实际执行时间
    struct load_weight load;               // 权重
};
CFS 调度器：红黑树按 vruntime 排序 cfs_rq vruntime=100 vruntime=200 vruntime=300 vruntime=400 vruntime=50 vruntime=150 vruntime=250 vruntime=350 调度器始终选择最左节点（vruntime 最小）运行 运行后 vruntime 增加，重新插入红黑树 时间复杂度 O(log n)，兼顾公平性与交互响应

1.1.4 EEVDF：最早虚拟截止时间优先

EEVDF（Earliest Eligible Virtual Deadline First）是 Linux 6.6 开始引入的可选调度器，由 Peter Zijlstra 实现。它在 CFS 的 vruntime 基础上增加了“截止时间”维度，更适合延迟敏感型工作负载。

关键改进： EEVDF 为每个调度实体维护一个“虚拟截止时间”，调度器选择“最早虚拟截止时间”且“已满足可调度条件”的进程。这为实时和低延迟场景提供了更确定性的调度行为。

1.2 调度器核心目标

无论调度器如何演进，其核心目标始终围绕以下四个维度：

  1. 公平性 (Fairness)： 每个进程应获得与其优先级/权重成比例的 CPU 时间。
  2. 吞吐量 (Throughput)： 单位时间内完成的有用工作量最大化。
  3. 响应延迟 (Response Latency)： 交互式进程从就绪到获得 CPU 的时间应尽可能短。
  4. 可扩展性 (Scalability)： 随着 CPU 核心数和进程数增加，调度开销应保持可控。
目标 衡量指标 典型瓶颈 调优方向
公平性 vruntime 偏差、CPU 时间分配比例 权重设置不合理、组调度配置不当 调整 nice 值、使用 cgroup cpu.shares
吞吐量 上下文切换次数、CPU 利用率 过度抢占、TLB 抖动 调整 sched_min_granularity、sched_wakeup_granularity
响应延迟 调度延迟 (sched_latency)、唤醒延迟 CFS 的 vruntime 累积、负载均衡延迟 使用 EEVDF、调整 sched_latency_ns
可扩展性 调度器开销 vs 核心数曲线 运行队列锁争用、调度域层级过深 优化调度域拓扑、使用 NO_HZ_FULL

1.3 设计哲学：从“时间片”到“虚拟时间”

Linux 调度器的设计哲学经历了根本性转变：

  • O(n)/O(1) 时代： 基于固定时间片和静态优先级，调度器决定“谁该运行多久”。
  • CFS 时代： 基于虚拟运行时间，调度器回答“谁最需要运行”。公平性由数学保证，而非人为设定的时间片。
  • EEVDF 时代： 在公平性基础上引入截止时间约束，为延迟敏感负载提供确定性保证。
性能调优启示： 理解调度器的设计哲学是调优的前提。CFS 的“公平”并不意味着所有进程获得相同时间——权重（nice 值）和 cgroup 配置会改变公平的基准。EEVDF 的“截止时间”则要求调优者理解工作负载的延迟特征。
调度器设计哲学演进 O(n) / O(1) 固定时间片 + 优先级 CFS 虚拟运行时间 + 红黑树 EEVDF 虚拟截止时间 + 可调度条件 核心转变：从“分配时间”到“按需调度” 公平性由数学保证，延迟由截止时间约束

1.4 本章小结

Linux 调度器从 O(n) 到 EEVDF 的演进，反映了对公平性、延迟和可扩展性不断深化的理解。作为性能调优工程师，需要掌握：

  • 不同调度器版本的核心数据结构和时间复杂度。
  • CFS 的 vruntime 机制是理解调度延迟的基础。
  • EEVDF 为延迟敏感负载提供了新的调优维度。
  • 调度器的设计哲学决定了调优策略的边界。
← 上一章 📖 返回目录 下一章 →