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

Linux 内核调度器是操作系统的核心组件，负责决定哪个进程在何时获得 CPU 使用权。其发展历程经历了从简单到复杂、从低效到高效的演进，深刻反映了操作系统设计理念的变迁。本章将梳理 Linux 调度器的三个主要阶段：O(n) 调度器、O(1) 调度器和完全公平调度器 (CFS)，并剖析其核心目标与设计哲学。

1.1 Linux 调度器发展历史

Linux 调度器的演进可以划分为三个标志性阶段，每个阶段都解决了前一代调度器的关键瓶颈。

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

在 Linux 2.4 内核中，调度器采用最简单的全局优先级队列设计。每次调度时，调度器需要遍历所有可运行进程，计算每个进程的“好度 (goodness)”值，选择值最高的进程运行。

• 核心机制：所有进程共用一个运行队列，调度时全量扫描。
• 时间复杂度：O(n)，n 为系统中可运行进程总数。当进程数增多时，调度开销线性增长。
• 主要缺陷：
  • 多处理器 (SMP) 环境下，全局队列竞争锁严重，扩展性差。
  • 交互式进程响应延迟不可控，桌面体验糟糕。
  • 缺乏对实时进程的有效支持。

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

Linux 2.6.0 内核引入了由 Ingo Molnár 设计的 O(1) 调度器，这是调度器发展史上的里程碑。其核心思想是使用双优先级位图 + 活跃/过期数组结构，将调度决策的时间复杂度降低到常数级别。

• 核心机制：
  • 为每个 CPU 维护两个优先级数组：active (活跃) 和 expired (过期)。
  • 使用 140 级优先级位图 (0-99 为实时，100-139 为普通)，通过位运算快速找到最高优先级进程。
  • 进程时间片耗尽后从 active 移到 expired，当 active 为空时交换两个数组指针。
• 时间复杂度：O(1)，无论进程数量多少，调度决策时间恒定。
• 主要缺陷：
  • 交互性判断依赖复杂的启发式规则 (如睡眠时间统计)，容易误判。
  • 时间片分配粒度固定，对“公平”的定义不够精确。
  • 负载均衡算法在多核场景下表现不稳定。

1.1.3 CFS 调度器：完全公平的哲学

Linux 2.6.23 内核中，CFS (Completely Fair Scheduler) 由 Ingo Molnár 重新设计，彻底摒弃了固定时间片和优先级数组的思路，引入了虚拟运行时间 (vruntime) 和红黑树的数据结构。

• 核心机制：
  • 每个进程维护一个 vruntime，表示其已运行的“虚拟时间”。
  • 所有可运行进程按 vruntime 组织在红黑树中，最左侧节点 (vruntime 最小) 即为下一个要运行的进程。
  • 调度器总是选择 vruntime 最小的进程运行，确保所有进程获得公平的 CPU 份额。
• 时间复杂度：O(log n)，红黑树插入/删除操作的对数复杂度。
• 设计哲学：“理想公平”模型——在一个无限细粒度的时间分时系统中，每个进程应该获得完全相等的 CPU 时间比例。

1.2 调度器核心目标与设计哲学

无论调度器如何演进，其核心目标始终围绕以下三个维度展开，这些目标也是评估调度器性能的关键指标。

1.2.1 公平性：CFS 的基石

CFS 的设计哲学建立在“理想多任务处理器”模型之上。假设存在一个完美的处理器，能以无限小的粒度同时运行所有进程，那么每个进程在任意时间点都应该获得与其权重相等的 CPU 份额。CFS 通过 vruntime 来模拟这一理想模型：

• vruntime 计算公式：vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)
• 权重映射：nice 值 0 对应权重 1024，nice 值每增减 1，权重约增减 10%。
• 公平性保证：红黑树确保 vruntime 最小的进程总是被优先调度，从而逐步缩小所有进程的 vruntime 差距。

1.2.2 吞吐量与延迟的权衡

调度器必须在吞吐量和响应延迟之间做出权衡。过于频繁的上下文切换会降低吞吐量，但能提高交互响应速度；反之，过长的调度周期会提高吞吐量，但可能导致交互式进程响应迟钝。

• 调度粒度控制：CFS 通过 sched_latency (默认 6ms) 和 min_granularity (默认 0.75ms) 两个参数控制调度周期。
• 目标延迟：在 sched_latency 时间内，所有可运行进程至少被调度一次。
• 动态调整：当可运行进程数量增多时，CFS 会适当增加调度周期，避免上下文切换开销过大。

1.2.3 负载跟踪：从 CFS 到 PELT 的演进

CFS 调度器虽然实现了公平调度，但在多核负载均衡场景下，需要精确知道每个进程对 CPU 的“真实负载”是多少。早期的 CFS 使用简单的平均负载统计，但存在以下问题：

• 历史遗忘过快：短时间内的负载波动无法反映进程的长期行为。
• 无法区分运行/睡眠状态：睡眠进程的负载贡献被忽略，导致负载均衡决策偏差。
• 缺乏时间衰减模型：无法区分近期负载和远期负载的重要性差异。

正是为了解决这些问题，PELT (Per-Entity Load Tracking) 算法应运而生。PELT 为每个调度实体 (进程或任务组) 维护一个衰减累积负载值，通过半衰期机制精确跟踪负载的时变特性。这将是本课程后续章节的核心内容。

1.3 本章小结

Linux 调度器从 O(n) 到 O(1) 再到 CFS 的演进，体现了操作系统设计从“简单可用”到“高效可扩展”再到“精确公平”的追求。CFS 调度器通过 vruntime 和红黑树实现了比例公平调度，但其负载跟踪机制的不足催生了 PELT 算法。理解这段历史，是深入掌握 PELT 原理的必要前提。