3. 调度算法评价指标：公平性、响应时间、周转时间、CPU利用率、吞吐量、可扩展性
评价一个调度算法的优劣，不能仅凭单一维度。在操作系统内核设计中，调度器需要在多个相互冲突的目标之间寻找平衡。本节将系统梳理六大核心评价指标，为后续对比 O(1) 与 CFS 的架构差异奠定理论基础。
核心观点： 调度算法的设计本质是在“公平”与“效率”之间做权衡。没有绝对完美的调度器，只有最适合特定负载场景的调度器。
3.1 六大指标定义与对比
下表从定义、度量方式、优化方向三个维度，对六大指标进行横向对比：
| 指标 | 定义 | 度量方式 | 优化方向 |
|---|---|---|---|
| 公平性 | 每个进程获得 CPU 时间片的比例是否与其优先级或权重匹配 | 最大-最小公平分配偏差、调度延迟方差 | 减少饥饿，保证每个进程都能得到应有的执行机会 |
| 响应时间 | 从进程提交请求到系统产生首次响应所经过的时间 | 毫秒级延迟（交互式场景通常要求 < 100ms） | 降低交互式任务的调度延迟，提升用户体验 |
| 周转时间 | 从进程提交到进程完成所经过的总时间 | 完成时间 - 提交时间 | 缩短批处理任务的总体执行周期 |
| CPU 利用率 | CPU 处于忙碌状态的时间占总时间的比例 | 忙碌时间 / (忙碌时间 + 空闲时间) | 减少空闲等待，最大化硬件资源使用率 |
| 吞吐量 | 单位时间内系统完成的进程数量 | 进程数 / 时间单位（如 进程/秒） | 提高系统整体处理能力，减少上下文切换开销 |
| 可扩展性 | 调度器在 CPU 核心数、进程数增加时保持性能的能力 | 锁竞争开销、负载均衡效率、调度延迟随核心数增长曲线 | 避免调度器成为多核系统的瓶颈 |
面试高频点： 响应时间与周转时间常常相互冲突。例如，短作业优先（SJF）可以优化周转时间，但可能导致长作业响应时间恶化；而时间片轮转（RR）能保证响应时间，但会因频繁切换降低吞吐量。
3.2 指标间的内在矛盾与权衡
六大指标并非独立存在，它们之间存在天然的制约关系。理解这些矛盾是进行调度算法选型的前提。
- 公平性 vs. 吞吐量： 过度追求公平（如完全公平调度）会增加上下文切换次数，降低 CPU 利用率与吞吐量。
- 响应时间 vs. 周转时间： 交互式任务需要快速响应，但频繁抢占会延长批处理任务的周转时间。
- CPU 利用率 vs. 响应时间： 保持 CPU 高利用率通常意味着让进程长时间运行，这会牺牲响应时间。
- 可扩展性 vs. 公平性： 多核环境下，维护全局公平性需要复杂的锁机制和负载均衡，这会降低可扩展性。
工程陷阱： 在实时系统中，过度强调“公平性”可能导致关键任务错过截止时间。调度器选型必须根据业务场景明确指标的优先级排序。
3.3 指标关系 SVG 架构图
下图展示了六大指标之间的相互影响关系，以及它们在不同负载场景下的权重分布：
3.4 不同负载场景下的指标优先级
在实际工程中，调度算法的选型取决于系统的主要负载类型。以下是三种典型场景的指标优先级排序：
| 负载场景 | 第1优先级 | 第2优先级 | 第3优先级 | 典型系统 |
|---|---|---|---|---|
| 交互式桌面 | 响应时间 | 公平性 | CPU利用率 | Linux桌面、Windows GUI |
| 批处理服务器 | 吞吐量 | 周转时间 | CPU利用率 | HPC集群、大数据计算 |
| 实时系统 | 响应时间（确定性） | 可扩展性 | 公平性 | 嵌入式系统、自动驾驶 |
关键洞察： O(1) 调度器通过优先级数组和位图实现了 O(1) 时间复杂度的调度决策，在可扩展性上表现优异，但公平性较差（优先级高的进程可能长期占用 CPU）。CFS 调度器通过红黑树和虚拟运行时间实现了近乎完美的公平性，但在极端高负载下，红黑树的插入/删除开销会略微影响吞吐量。这正是两种架构在指标权衡上的典型体现。
3.5 指标量化示例：响应时间与周转时间
假设系统中有三个进程 P1、P2、P3，到达时间均为 0，执行时间分别为 5ms、3ms、2ms。对比不同调度策略下的指标表现：
| 调度策略 | P1 响应时间 | P2 响应时间 | P3 响应时间 | 平均响应时间 | 平均周转时间 |
|---|---|---|---|---|---|
| FCFS（P1→P2→P3） | 0ms | 5ms | 8ms | 4.33ms | 8.33ms |
| SJF（P3→P2→P1） | 2ms | 2ms | 0ms | 1.33ms | 5.67ms |
| RR（时间片=1ms） | 0ms | 1ms | 2ms | 1.00ms | 7.67ms |
分析： RR 调度在响应时间上表现最佳（1ms），但周转时间最差（7.67ms）；SJF 在周转时间上最优（5.67ms），但长作业 P1 的响应时间被延迟到 2ms。这验证了响应时间与周转时间之间的经典矛盾。
3.6 可扩展性：多核时代的核心挑战
随着 CPU 核心数从单核发展到数百核，调度器的可扩展性成为关键瓶颈。主要挑战包括：
- 锁竞争： 全局运行队列需要加锁保护，高并发下锁争用会严重降低性能。
- 缓存亲和性： 频繁将进程迁移到不同核心会导致缓存失效，增加内存访问延迟。
- 负载均衡开销： 在核心之间迁移进程需要消耗 CPU 周期，且可能破坏局部性。
O(1) 调度器通过每个 CPU 独立的运行队列（per-CPU runqueue）来减少锁竞争，这是其可扩展性优于早期调度器的关键设计。CFS 继承了这一设计，并通过调度域（sched domain）实现了层次化的负载均衡。
工程实践： 在 NUMA（非统一内存访问）架构下，跨节点迁移进程的内存访问延迟可能增加 2-3 倍。现代调度器（如 CFS 的 NUMA 感知调度）会优先将进程绑定在同一个 NUMA 节点上，以牺牲部分公平性换取更好的内存局部性。