2. 进程调度基础概念：进程状态模型、上下文切换、调度延迟与吞吐量

在深入 O(1) 与 CFS 调度器架构之前，必须建立坚实的进程调度基础。本节将围绕三个核心概念展开：进程状态模型（描述进程生命周期）、上下文切换（调度执行的具体代价）以及调度延迟与吞吐量（衡量调度器性能的关键指标）。这些概念是所有调度算法选型的基石。

2.1 进程状态模型：就绪、运行与阻塞

操作系统通过状态机管理进程的生命周期。Linux 内核将进程抽象为三种基本状态，以及两种辅助状态（创建与终止）。调度器主要关注前三种状态的转换。

核心状态定义：
  • 运行（Running）： 进程正在 CPU 上执行指令。在单核系统中，同一时刻只有一个进程处于此状态。
  • 就绪（Ready）： 进程已具备运行条件，等待 CPU 调度。它位于调度器的就绪队列中，随时可以被选中执行。
  • 阻塞（Blocked）： 进程因等待某事件（如 I/O 完成、信号量、定时器）而暂停执行。即使 CPU 空闲，该进程也无法运行。

下图展示了进程状态之间的典型转换路径，以及调度器介入的关键点：

进程状态转换模型与调度器介入点 运行 (Running) 就绪 (Ready) 阻塞 (Blocked) 调度器选中 时间片耗尽/抢占 等待 I/O 或锁 事件完成（唤醒） 调度器核心职责：管理就绪队列，决定哪个就绪进程进入运行状态。 阻塞状态不参与调度竞争，直到被唤醒回到就绪队列。
调度器视角： 调度器只关心“就绪”和“运行”两个状态。阻塞状态的进程被移出调度队列，不参与 CPU 竞争。当进程从阻塞变为就绪时，调度器将其重新插入就绪队列。

2.2 上下文切换：调度的核心代价

当调度器决定将 CPU 从当前进程切换到另一个进程时，必须执行上下文切换。这是调度操作的主要开销来源，直接影响系统性能。

上下文切换的内容：

  • 硬件上下文： CPU 寄存器（通用寄存器、程序计数器 PC、栈指针 SP）、状态寄存器。
  • 内存上下文： 页表基地址（切换地址空间，涉及 TLB 刷新）。
  • 内核栈： 每个进程拥有独立的内核栈，切换时需切换内核栈指针。

上下文切换的代价分析：

代价类型 具体开销 影响程度
直接 CPU 开销 保存/恢复寄存器、切换栈指针、执行调度算法 微秒级（通常 1-10 μs）
缓存污染 L1/L2 缓存、TLB 失效，新进程需重新加载数据 毫秒级性能下降（间接代价更大）
地址空间切换 切换 CR3 寄存器（x86），刷新 TLB 数百纳秒至微秒
关键认知： 上下文切换的“隐藏成本”远大于指令执行时间。频繁切换会导致缓存颠簸（Cache Thrashing），使系统吞吐量急剧下降。调度器设计必须在“公平性”与“切换开销”之间取得平衡。

下图展示了上下文切换的完整流程：

上下文切换流程（进程 A → 进程 B） 1. 保存 A 的寄存器 2. 切换内核栈指针 3. 切换地址空间 4. 恢复 B 的寄存器 上下文切换详细步骤 ① 保存进程 A 的通用寄存器、PC、SP 到 A 的内核栈或进程控制块（PCB）。 ② 将 CPU 内核栈指针切换到进程 B 的内核栈。 ③ 加载进程 B 的页表基地址（如 x86 的 CR3），使 MMU 映射 B 的地址空间。 ④ 从进程 B 的内核栈恢复其寄存器状态，然后通过“iret”或类似指令返回到 B 的用户态执行。

2.3 调度延迟与吞吐量：性能度量指标

调度器的性能通过两个核心指标衡量：调度延迟（响应速度）和吞吐量（处理能力）。这两个指标通常相互制约。

2.3.1 调度延迟

调度延迟指从进程变为就绪状态到它实际开始运行所经历的时间。它直接决定了系统的交互响应体验。

  • 抢占延迟（Preemption Latency）： 从外部事件（如硬件中断）发生到调度器开始执行调度决策的时间。
  • 调度决策延迟（Scheduling Decision Latency）： 调度器遍历就绪队列、选择下一个进程所花费的时间。
  • 切换延迟（Switch Latency）： 执行上下文切换本身的时间。

2.3.2 吞吐量

吞吐量衡量系统在单位时间内完成的进程数量或工作量。对于批处理系统，吞吐量是首要优化目标。

  • 进程吞吐量： 单位时间内完成的进程数。
  • CPU 利用率： CPU 处于“忙”（执行用户代码或内核代码）的时间比例。高吞吐量通常伴随高 CPU 利用率。

延迟与吞吐量的权衡：

调度策略倾向 调度延迟 吞吐量 典型场景
交互优先（如 CFS 默认） 低（毫秒级） 中等 桌面系统、Web 服务器
吞吐优先（如批处理调度） 高（秒级） 高 科学计算、视频渲染
实时调度（如 FIFO/RR） 极低（微秒级） 低 工业控制、音频处理
调度器设计目标： 理想的调度器应在保证可接受的调度延迟前提下，最大化系统吞吐量。O(1) 调度器通过位图算法实现常数时间的调度决策，以降低调度延迟；CFS 则通过红黑树和虚拟运行时间实现完全公平，同时保持对数时间复杂度的调度延迟。

下图展示了调度延迟与吞吐量之间的典型关系曲线：

调度延迟 vs 吞吐量：权衡曲线 调度延迟（越低越好） → 低 高 吞吐量 → 交互式（低延迟，中吞吐） 批处理（高延迟，高吞吐） 注：曲线仅示意趋势，实际数值取决于硬件、负载和调度器实现。

2.4 基础概念与调度器选型的关联

理解上述基础概念后，可以建立与 O(1) 和 CFS 调度器架构的直接关联：

基础概念 对 O(1) 调度器的影响 对 CFS 调度器的影响
进程状态模型 O(1) 使用 140 级优先级队列，就绪进程按优先级入队；阻塞进程被移出活跃队列。 CFS 使用红黑树管理就绪进程，键值为虚拟运行时间；阻塞进程从树中移除。
上下文切换 O(1) 通过位图快速找到最高优先级队列，减少调度决策时间，间接降低切换频率。 CFS 每次调度都需从红黑树中选取最左节点（最小 vruntime），切换次数与进程数对数相关。
调度延迟 O(1) 保证调度决策时间为常数 O(1)，延迟可预测，适合实时性要求高的场景。 CFS 调度延迟为 O(log N)，N 为进程数；通过目标延迟（targeted latency）控制最大延迟。
吞吐量 O(1) 的静态优先级可能导致低优先级进程饥饿，但整体吞吐量稳定。 CFS 通过公平分配 CPU 时间，避免饥饿，但频繁切换可能降低极端负载下的吞吐量。
← 上一章 📖 返回目录 下一章 →