illegalCreed

中文

English

中文

English

Appearance

调度性能指标与计算 ​

基于通用操作系统概念 · 核于 2026-08

速查 ​

  • 甘特图（Gantt Chart）：用横轴时间条可视化调度过程，每个进程占一段连续时间——是计算性能指标的必备工具。先画甘特图，再算各项指标。
  • 平均等待时间（Average Waiting Time）：所有进程的等待时间之和 / 进程数。等待时间 = 开始时间 − 到达时间（FCFS）；RR/抢占式则分段累加。SJF 最优。
  • 平均周转时间（Average Turnaround Time）：所有进程的周转时间之和 / 进程数。周转时间 = 完成时间 − 到达时间。SJF 最优。周转 = 等待 + 突发。
  • 平均响应时间（Average Response Time）：所有进程的响应时间之和 / 进程数。响应时间 = 首次被调度 − 到达时间。RR 最优（时间片保证快速首响应）。
  • CPU 利用率（CPU Utilization）：CPU 忙碌时间 / 总时间。越高越好，IO 密集型多时靠调度并发提升。
  • 吞吐量（Throughput）：单位时间完成的进程数。SJF 高（短作业先做完成多）。
  • 调度器（Scheduler）：策略层，从就绪队列选下一个进程（FCFS/SJF/RR 算法）。决策耗时也计入开销。
  • 分发器（Dispatcher）：机制层，把 CPU 控制权交给选中进程（上下文切换、切用户态、跳入口）。**分发延迟（dispatch latency）**约微秒级。
  • 上下文切换开销：保存/恢复寄存器、切栈、刷 TLB、CPU 流水线冲刷——约 1-10μs。RR 时间片太小则切换占比过高。
  • 时间片大小对 RR 影响：q=10-100ms 为佳。q 过小 → 切换开销超过实际工作（CPU 利用率低）；q 过大（如 >突发时间）→ 退化为 FCFS，响应变差。q 应远大于上下文切换时间。
  • 饥饿（Starvation）：SJF/优先级调度下某些进程（长作业/低优先级）永远等不到 CPU。
  • 老化（Aging）：解饥饿的标准机制——随等待时间增长逐步提升优先级（如每等 1 秒优先级 +1），等久了必能执行。
  • 进阶顺序：参考（算法对比大表 + 计算模板 + 易错点）。

一、甘特图：调度的可视化 ​

甘特图是分析调度的第一步——画出每个进程占用 CPU 的时段，所有指标都从图上读：

示例：FCFS，进程 P1(到达0,突发5) P2(到达1,突发3) P3(到达2,突发1)

甘特图：
时间： 0    1    2    3    4    5    6    7    8    9
      |----P1(0-5)----|--P2(5-8)--|-P3(8-9)-|
                                  （P3 到达2 但等 P1/P2 跑完，8 才开始）
  • 画法：横轴是时间，每段标注进程名与起止时间。抢占式算法（RR/抢占优先级）下，同一进程会被切成多段。
  • 作用：从图上可直接读出每个进程的开始时间、完成时间，进而算等待/周转/响应。
  • 考点：给定进程表（到达时间 + 突发时间）+ 算法，画甘特图 → 算平均等待/周转。这是 OS 考试的固定题型。

二、核心指标：等待、周转、响应 ​

三大核心指标的计算公式：

指标公式含义谁最优
等待时间完成 − 到达 − 突发 = 开始 − 到达（非抢占）在就绪队列里等了多久SJF
周转时间完成 − 到达从提交到完成的总时间SJF
响应时间首次调度 − 到达从输入到首次响应RR

完整计算示例（FCFS，P1 到达 0 突发 5，P2 到达 1 突发 3，P3 到达 2 突发 1）：

甘特图：|P1(0-5)|P2(5-8)|P3(8-9)|

进程  到达  突发  开始  完成  等待(开始-到达)  周转(完成-到达)  响应(首次调度-到达=等待)
P1    0     5     0     5     0                5                0
P2    1     3     5     8     4                7                4
P3    2     1     8     9     6                7                6

平均等待 = (0+4+6)/3 = 3.33
平均周转 = (5+7+7)/3 = 6.33
平均响应 = (0+4+6)/3 = 3.33（FCFS 下响应=等待）
  • 非抢占式简化：等待时间 = 开始 − 到达；周转 = 完成 − 到达；响应 = 开始 − 到达（= 等待，因为非抢占首次调度即开始）。
  • 抢占式（RR/SRTF）复杂：进程被切成多段，等待时间要分段累加：等待 = 周转 − 实际运行（突发）。响应 = 首次被调度 − 到达。

三、RR 的分段计算 ​

RR 下进程被时间片切成多段，计算时要逐段累加：

进程：P1(到达0,突发5) P2(到达0,突发3) P3(到达0,突发1)，q=2
轮转：P1(2)→P2(2)→P3(1)→P1(2)→P2(1)→P1(1)
甘特图：|P1(0-2)|P2(2-4)|P3(4-5)|P1(5-7)|P2(7-8)|P1(8-9)|

P1：运行时段(0-2)(5-7)(8-9)，完成9，到达0，突发5
    周转 = 9-0 = 9；等待 = 9 - 0 - 5 = 4
P2：运行时段(2-4)(7-8)，完成8，到达0，突发3
    周转 = 8；等待 = 8 - 0 - 3 = 5
P3：运行时段(4-5)，完成5，到达0，突发1
    周转 = 5；等待 = 5 - 0 - 1 = 4

平均等待 = (4+5+4)/3 = 4.33
平均周转 = (9+8+5)/3 = 7.33
平均响应 = (0+2+4)/3 = 2  ← RR 首响应极快（最多等一个时间片）
  • RR 响应最优：每个进程最多等一个时间片（N 个进程，q 时间片，最坏等 (N−1)·q）。
  • RR 周转一般：频繁切换让进程完成时间拉长，平均周转比 SJF 差。
  • 分段计算要点：先画完整甘特图，标出每个进程所有运行段，等待 = 周转 − 突发（周转 = 完成 − 到达）。

四、SJF 最优性的直观证明 ​

为什么 SJF 平均等待最优？直观：短作业放最前，被它阻塞的进程最少（后面所有进程都少等一段短时间）：

反证：若有顺序 ...长(8)...短(3)...，把短提前到长前：
原顺序：短等 0，长等 3 → 平均等待 (0+3)/2 = 1.5
颠倒：  长等 0，短等 8 → 平均等待 (0+8)/2 = 4 ← 更差
  • 任何把长作业排在短作业前面的顺序，交换两者都能减小平均等待。故最优顺序是按突发时间升序——即 SJF。
  • SRTF（抢占式）更优：新短进程到达时立刻抢占当前长进程，平均等待比非抢占 SJF 还小。

五、时间片大小对 RR 的影响 ​

时间片 q 是 RR 的唯一参数，选择直接影响性能：

q 大小切换开销占比CPU 利用率响应延迟退化
q → 0（极小）~100%（光切换不干活）极低极快系统瘫痪
q = 1ms（小）高（如切换 5μs，占比 0.5%）低快接近处理器共享
q = 10ms（佳）低（切换 5μs，占比 0.05%）高好（10 进程最多等 90ms）正常 RR
q = 100ms（大）极低高中（10 进程最多等 900ms）接近 FCFS
q → ∞0最高差退化为 FCFS
  • 经验法则：q 应远大于上下文切换时间（切换约 1-10μs，q 10ms，开销占比 <0.1%），同时远小于典型交互间隔（让交互进程快速被轮到）。多数系统取 10-100ms。
  • 规则 80%：80% 的 CPU 突发应短于时间片——这样大部分进程在一个时间片内完成，少切换。

六、调度器 vs 分发器 ​

调度过程分策略层（选谁）和机制层（怎么交接）：

   就绪队列 → [调度器] → 选定进程 → [分发器] → CPU 运行
              ↑ 策略                ↑ 机制
              FCFS/SJF/RR...        上下文切换
  • 调度器（scheduler）：策略——从就绪队列选下一个进程。决策依据是算法（FCFS 按到达序、SJF 按突发、RR 轮转）。决策本身也有开销（遍历队列），高级算法用优先队列/红黑树（O(log n)）优化。
  • 分发器（dispatcher）：机制——把 CPU 控制权交给选中进程：
    1. 保存当前进程上下文（寄存器/PC/SP）到 PCB。
    2. 切换到内核栈 → 切换到目标进程地址空间（页表）。
    3. 加载目标进程上下文。
    4. 切换到用户态，跳到目标进程 PC。
  • 分发延迟（dispatch latency）：分发器完成切换的时间，约 1-10μs。包含上下文切换 + 可能的 TLB flush（KPTI 后更多）。
  • 为何分离：策略与机制分离——换调度算法（如 Linux 从 O(1) 换 CFS）不动分发机制，便于演进。这也是 OS 设计的经典原则。

七、饥饿与老化 ​

饥饿（Starvation）指某些进程无限期等不到 CPU——发生在 SJF（长作业）和优先级调度（低优先级）：

  • SJF 饥饿：源源不断的短作业让一个长作业永远排在后面。例：长作业突发 100ms，但每 10ms 就来一个突发 5ms 的短作业，长作业永远等不到执行。
  • 优先级饥饿：低优先级进程在源源不断的高优先级进程面前永远得不到调度。经典案例：早期 Multics 系统低优先级作业几天没跑。
  • MLFQ 饥饿：低优先级队列被高优先级队列源源不断抢占——除非有老化或定期优先级提升。

解法——老化（Aging）：随等待时间增长逐步提升优先级：

规则：每等待 1 秒，进程优先级 +1（数字越小越高，则 -1）
初始：长作业优先级 10（很低）
等 5 秒后：优先级升到 5
等 10 秒后：优先级升到 0（最高）→ 必然被调度
  • 老化是优先级/MLFQ 调度的标配——保证任何进程最终都能执行，消除饥饿。
  • Linux CFS 的处理：CFS 用 vruntime（虚拟运行时间）排序，vruntime 增长慢的进程（少占 CPU）自然优先——本质上是"运行少的优先"，不依赖优先级数字，从根本上避免饥饿（每个进程按权重公平分享 CPU）。

下一步 ​

掌握了指标与计算后，下一步看参考——算法对比大表、复杂度、计算模板、易错点清单与权威链接，作为速查与备考工具。