2. 调度器基础概念
调度器是操作系统的核心组件，负责在多个可运行进程之间分配有限的 CPU 资源。理解调度器的工作原理，首先需要掌握四个基础概念：进程状态、上下文切换、调度时机和调度策略分类。这些概念构成了后续分析 O1 调度器与 CFS 调度器演进与对比的基石。
2.1 进程状态与状态转换
进程在其生命周期中会经历多种状态。Linux 内核使用一组明确定义的状态来描述进程当前的活动情况。调度器只对处于 TASK_RUNNING 状态的进程进行调度。
| 内核状态标识 | 状态名称 | 说明 | 是否参与调度 |
|---|---|---|---|
TASK_RUNNING |
可运行状态 | 进程正在执行或位于就绪队列中等待 CPU | 是 |
TASK_INTERRUPTIBLE |
可中断睡眠 | 进程等待某事件（如 I/O 完成），可被信号唤醒 | 否 |
TASK_UNINTERRUPTIBLE |
不可中断睡眠 | 进程等待内核态事件（如磁盘 I/O），不响应信号 | 否 |
TASK_STOPPED |
暂停状态 | 进程收到 SIGSTOP 等信号，执行被暂停 | 否 |
TASK_TRACED |
跟踪状态 | 进程被 ptrace 系统调用跟踪，常用于调试器 | 否 |
EXIT_ZOMBIE |
僵尸状态 | 进程已终止，但 PCB 尚未被父进程回收 | 否 |
EXIT_DEAD |
死亡状态 | 进程最终状态，PCB 即将被释放 | 否 |
关键点：调度器只操作
TASK_RUNNING 状态的进程。其他状态的进程被阻塞或等待，不参与 CPU 竞争。
下图展示了进程在 Linux 内核中的核心状态转换关系：
2.2 上下文切换
上下文切换（Context Switch）是指内核将 CPU 从当前正在执行的进程切换到另一个进程的过程。这是调度器执行调度决策的直接结果，也是操作系统多任务能力的核心机制。
一次完整的上下文切换包含以下步骤：
- 保存当前进程的上下文：将 CPU 寄存器（通用寄存器、程序计数器、栈指针等）保存到当前进程的 PCB（进程控制块）中。
- 更新内核数据结构：将当前进程的状态从
TASK_RUNNING切换为其他状态（如果不再运行），或将其放回就绪队列。 - 选择下一个进程：调度器根据调度策略从就绪队列中选择下一个要运行的进程。
- 加载新进程的上下文：从新进程的 PCB 中恢复 CPU 寄存器、页表指针（切换地址空间）等。
- 切换地址空间：如果新进程与旧进程属于不同的地址空间，需要刷新 TLB（转换后备缓冲器）并加载新进程的页表。
- 开始执行新进程：通过跳转到新进程的程序计数器位置，恢复用户态执行。
性能开销：上下文切换是纯开销操作。一次典型的上下文切换耗时在微秒级（1-10 μs），包括直接开销（寄存器保存/恢复）和间接开销（缓存/TLB 失效）。调度器设计的目标之一就是尽量减少不必要的上下文切换。
下图展示了上下文切换的核心流程：
2.3 调度时机
调度器并非随时都可以执行调度。调度行为只在特定的调度时机（Scheduling Points）发生。理解调度时机有助于分析调度器的响应延迟和吞吐量特性。
Linux 内核中的主要调度时机包括：
| 调度时机 | 触发条件 | 调度类型 | 典型场景 |
|---|---|---|---|
| 时钟中断 | 周期性定时器中断（tick） | 抢占式调度 | 时间片耗尽，强制切换 |
| 进程阻塞 | 进程主动调用 sleep()、wait() 或发起 I/O 操作 |
主动调度 | 进程等待资源，自愿让出 CPU |
| 进程退出 | 进程调用 exit() 终止运行 |
主动调度 | 进程生命周期结束 |
| 系统调用返回 | 从内核态返回用户态时检查 need_resched 标志 |
抢占式调度 | 高优先级进程就绪，抢占当前进程 |
| 中断处理返回 | 硬件中断处理完成后返回用户态 | 抢占式调度 | I/O 完成唤醒高优先级进程 |
| 唤醒进程 | wake_up() 将进程加入就绪队列 |
抢占式调度 | 被阻塞的进程条件满足，重新就绪 |
注意：在 Linux 2.4 及之前的 O1 调度器中，调度时机主要依赖时钟中断（tick）。而在 CFS 调度器中，调度时机更加细粒度，除了 tick 之外，还通过
sched_yield()、try_to_wake_up() 等路径实现更及时的抢占。
2.4 调度策略分类
调度策略决定了在多个可运行进程之间如何分配 CPU 时间。根据设计目标和应用场景，调度策略可以分为以下几类：
2.4.1 按调度目标分类
- 批处理调度：追求高吞吐量，减少上下文切换次数。典型算法：FCFS（先来先服务）、SJF（短作业优先）。
- 交互式调度：追求低响应延迟，保证用户交互流畅。典型算法：时间片轮转（RR）、多级反馈队列（MLFQ）。
- 实时调度：满足任务的截止时间要求，分为硬实时和软实时。典型算法：速率单调（RM）、最早截止时间优先（EDF）。
2.4.2 按决策方式分类
| 分类 | 说明 | 代表算法 | 优缺点 |
|---|---|---|---|
| 非抢占式 | 进程一旦获得 CPU，除非主动阻塞或退出，否则一直运行 | FCFS、SJF（非抢占版） | 实现简单，上下文切换少；但响应延迟不可控 |
| 抢占式 | 调度器可以在任意时刻中断当前进程，强制切换 | RR、MLFQ、CFS | 响应快，适合交互式系统；但上下文切换开销较大 |
2.4.3 按优先级动态性分类
- 静态优先级调度：进程优先级在创建时确定，运行期间不变。O1 调度器使用静态优先级 + 动态调整的混合机制。
- 动态优先级调度：优先级根据进程行为（如睡眠时间、CPU 使用量）动态调整。CFS 调度器通过虚拟运行时间（vruntime）实现完全公平的动态优先级。
下图展示了调度策略的分类体系：
2.5 调度策略的核心指标
评估调度策略优劣时，通常关注以下指标：
- CPU 利用率：CPU 处于忙碌状态的时间百分比。理想情况下应接近 100%。
- 吞吐量：单位时间内完成的进程数量。批处理系统更关注此指标。
- 周转时间：从进程提交到进程完成的总时间。包括等待时间、执行时间和 I/O 时间。
- 等待时间：进程在就绪队列中等待 CPU 的总时间。交互式系统更关注此指标。
- 响应时间：从提交请求到产生第一次响应的时间。用户交互体验的核心指标。
- 公平性：每个进程获得 CPU 时间的比例是否符合预期。CFS 调度器将此作为首要设计目标。
演进视角：O1 调度器（Linux 2.4/2.6 早期）更关注吞吐量和交互式响应，使用多级反馈队列和启发式优先级调整。CFS 调度器（Linux 2.6.23+）则重新定义了公平性，使用红黑树和虚拟运行时间，在保证公平的前提下兼顾响应延迟和吞吐量。