illegalCreed

中文

English

中文

English

Appearance

调度算法详解：FCFS/SJF/RR/优先级/MLFQ ​

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

速查 ​

  • FCFS（First-Come First-Served，先来先服务）：按到达顺序排队，非抢占式，先到先得。最简单公平，但有护航效应（一个长作业拖累后面所有短作业），对 CPU 密集型友好、对 IO 密集型交互差。
  • SJF（Shortest Job First，短作业优先）：选预估 CPU 突发时间最短的进程先执行（非抢占式=SJF，抢占式=SRTF 短剩余优先）。平均等待时间最优，但长作业会饥饿（源源不断的短作业让它永远等不到），且难以准确预估 CPU 突发时间。
  • RR（Round Robin，轮转）：就绪队列轮流执行，每个进程一次一个固定时间片（如 10ms），时间片用完排到队尾。交互响应最好、绝对公平，但时间片太小则切换开销爆炸，太大退化为 FCFS。一般时间片 10-100ms。
  • 优先级调度（Priority）：每个进程有优先级，调度器选优先级最高的。静态优先级（创建时定）/ 动态优先级（运行中调）。问题：低优先级饥饿——解法是老化（aging）：随等待时间增长逐步提升优先级。
  • MLFQ（Multi-Level Feedback Queue，多级反馈队列）：多个不同优先级的队列，新进程进最高优先级队列（用 RR 短时间片），用完时间片降级（更长的时间片但更低优先级），主动让出/IO 密集型留在高优先级。综合了 RR 的响应 + SJF 的吞吐，是现代通用 OS（Linux CFS/Windows/macOS）的鼻祖。
  • 护航效应（Convoy Effect）：FCFS 下一个长作业先到，后面短作业全跟着排长队——平均等待时间暴涨。是 FCFS 的致命伤。
  • 饥饿（Starvation）：SJF/优先级下，某些进程（长作业/低优先级）永远等不到 CPU。解法是老化：等待越久优先级越高。
  • 时间片选择：RR 时间片经验值 10-100ms。太小（<1ms）切换开销超过实际工作；太大（>100ms）退化为 FCFS，响应变差。时间片应远大于上下文切换时间（切换约微秒级，时间片毫秒级，开销占比 <1%）。
  • 抢占点：FCFS/SJF 非抢占式经典版；RR/优先级/MLFQ 都可抢占（RR 时间片到就抢，优先级可被更高优先级抢占）。
  • CFS（Completely Fair Scheduler）：Linux 2.6.23 起的默认调度器，理念是"完全公平"——按**虚拟运行时间（vruntime）**排序，vruntime 最小的先跑，用红黑树维护就绪队列，O(log n)。可视为 RR 的"加权精细化"版本。
  • 进阶顺序：调度性能指标与计算 → 参考。

一、FCFS：先来先服务 ​

最简单的调度——按进程到达就绪队列的顺序排队，先到先得，非抢占式：

进程：  P1(突发24)  P2(突发3)  P3(突发3)  同时到达 t=0
顺序：  P1 → P2 → P3
甘特图：|----P1(0-24)----|--P2(24-27)--|--P3(27-30)--|
平均等待时间 = (0 + 24 + 27) / 3 = 17
  • 优点：简单（一个 FIFO 队列）、公平（绝对按顺序，无饿死）、无竞态（非抢占，只在自愿点切换）。
  • 缺点：护航效应——上面例子如果 P1 是长作业，P2/P3 这种短作业要等 24ms 才能跑（哪怕它们只需要 3ms），平均等待时间暴涨。就像高速公路慢车后面拖一串快车。
  • 适用：批处理系统（无交互、求吞吐）、CPU 密集型工作负载。不适用：交互式系统（响应差）、IO 密集型多的场景。
  • 护航效应的根源：FCFS 不看作业长短，长作业先到就霸占，短作业被动排队。

二、SJF：短作业优先 ​

选预估 CPU 突发时间最短的进程先执行——平均等待时间理论上最优：

进程：  P1(突发6)  P2(突发8)  P3(突发7)  P4(突发3)  同时到达
SJF 选最短：P4(3) → P1(6) → P3(7) → P2(8)
甘特图：|-P4(0-3)-|--P1(3-9)--|--P3(9-16)--|--P2(16-24)--|
平均等待 = (3 + 16 + 9 + 0) / 4 = 7
（FCFS 顺序 P1→P2→P3→P4 平均等待 = (0+6+14+21)/4 = 10.25，SJF 更优）
  • 优点：平均等待时间最优（可数学证明：把短作业放最前，减少被它阻塞的进程数，总和最小）。
  • 缺点①——饥饿：长作业（如 P2 突发 8）后面如果源源不断来短作业，P2 永远等不到 CPU。这是 SJF 的致命伤。
  • 缺点②——难预估 CPU 突发时间：进程的 CPU 突发时间事先不知道（用户不会告诉你"我要算 6ms"），只能预估（如指数加权平均：τ(n+1) = α·t(n) + (1-α)·τ(n)，结合历史实际与上次预估）。
  • 抢占式版本 SRTF（Shortest Remaining Time First）：新进程到达时，若其剩余时间比当前运行进程的剩余时间还短，则抢占。SRTF 比 SJF 平均等待更优，但切换更频繁、饥饿更严重。
  • 适用：批处理、长短期作业混合且能预估时间的场景。不适用：交互式（用户无法预知自己要算多久）、长作业为主的场景。

三、RR：轮转 ​

就绪队列轮流执行，每个进程一次一个固定时间片，用完排到队尾——绝对公平、交互响应最好：

进程：  P1(突发24)  P2(突发3)  P3(突发3)  时间片 q=4
轮转：  P1(4) → P2(3) → P3(3) → P1(4) → P1(4) → ... → P1
甘特图：|P1(0-4)|P2(4-7)|P3(7-10)|P1(10-14)|P1(14-18)|P1(18-22)|P1(22-26)|P1(26-30)|
平均等待 = (P1: 6 + P2: 4 + P3: 7) / 3 = 5.67
  • 优点：绝对公平（每个进程每轮都跑一个时间片）、交互响应好（时间片到就轮转，交互进程最多等一个时间片就能响应）、无饥饿（每个进程必然被轮到）。
  • 缺点：切换开销——时间片越小，切换越频繁（每次切换上下文保存/恢复约微秒级）。若时间片 = 突发时间，RR 退化为 FCFS。
  • 时间片选择经验值 10-100ms：
    • 太小（<1ms）：切换开销超过实际工作，CPU 利用率低（大部分时间在切换）。
    • 太大（>100ms）：退化为 FCFS，交互响应变差。
    • 经验法则：时间片应远大于上下文切换时间（切换约 1-10μs，时间片 10ms，开销占比 <0.1%）。
  • 适用：分时/交互式系统（Linux/Windows 桌面、服务器）。RR 是交互响应的金标准。
  • 变体：加权 RR（不同进程时间片不同，权重高的更长）——让重要进程获得更多 CPU。

四、优先级调度 ​

每个进程有优先级（整数，数字越小优先级越高 或 数字越大优先级越高，看系统约定），调度器选优先级最高的：

进程：  P1(优先级2,突发4)  P2(优先级1,突发3)  P3(优先级3,突发1)  P4(优先级2,突发5)
（数字越小优先级越高）
调度：  P2(优1) → 同优2按到达：P1 → P4 → P3
甘特图：|--P2(3)--|--P1(4)--|--P4(5)--|--P1(1)--|
  • 静态优先级：进程创建时确定，运行中不变。简单，但低优先级饥饿。
  • 动态优先级：运行中可调（如 IO 密集型提高、CPU 密集型降低）。灵活但开销大。
  • 致命问题——饥饿：低优先级进程在源源不断的高优先级进程面前永远等不到 CPU。
  • 解法——老化（Aging）：随等待时间增长逐步提升优先级——如每等 1 秒优先级 +1，等久了自然升到最高优先级必能执行。这是优先级调度的标配补偿机制。
  • 适用：实时系统（硬实时需保证截止时间）、批处理、对关键任务优先的场景。现代 OS（Linux/Windows）混合使用——核心系统进程高优先级，用户进程动态调整。

五、MLFQ：多级反馈队列 ​

多级反馈队列综合了 RR 的响应 + SJF 的吞吐——多个不同优先级的队列，进程在队列间动态调整：

   Q0（最高优先级，时间片 2ms）   ← 新进程进这里（RR）
   Q1（中优先级，时间片 4ms）     ← 用完 Q0 时间片降到这里
   Q2（最低优先级，FCFS 或长时片） ← 用完 Q1 时间片降到这里

   规则①：新进程进 Q0（最高优先级）
   规则②：用完当前队列时间片 → 降级（Q0→Q1→Q2）
   规则③：主动让出（IO 完成/睡眠）→ 留在原队列（甚至升回 Q0）——照顾 IO 密集型
   规则④：低优先级队列用 FCFS 或更长的时间片（避免被高优先级饿死则需老化）
  • 关键洞察：MLFQ 用反馈机制动态学习进程类型——
    • 短作业/交互进程：在 Q0 用一两个短时间片就完成或 IO，留在高优先级，响应快（像 SJF）。
    • 长作业/CPU 密集型：用完 Q0 时间片被降级到 Q1、Q2，最终在最低优先级 FCFS 跑，不抢占交互（像 RR 兼顾 CPU 密集型）。
  • 优点：自适应——无需事先知道进程是 CPU 还是 IO 密集型，反馈机制自动判断；响应好（交互/短作业留在高优先级）；吞吐好（长作业在低优先级 FCFS 不频繁切换）。
  • 缺点：参数复杂（队列数、各队列时间片、升降级规则、老化策略），调优困难；可能饥饿（低优先级队列被高优先级源源不断抢占）——需老化机制提升等待久的进程。
  • 改进规则（现代 MLFQ）：①优先级提升——定期把所有进程升回 Q0 防止饥饿；②voodoo 规则——用总占用 CPU 时间而非单次时间片判断降级（防止进程在时间片快用完时故意让出 CPU 逃避降级）。
  • 代表实现：BSD/早期 Unix 调度器、Windows 调度器、macOS 调度器；Linux CFS 借鉴了 MLFQ 的公平思想但用了红黑树 + vruntime 的"完全公平"实现。

六、算法对比与选型 ​

算法抢占公平平均等待响应饥饿适用
FCFS否顺序公平差（护航效应）差无批处理、CPU 密集
SJF/SRTF否/是不公平最优差有（长作业）批处理（需预估）
RR是绝对公平中最优无分时、交互式
优先级可选不公平看优先级分布中有（低优先级）实时、关键任务
MLFQ是动态公平较优好需老化防现代通用 OS
  • 通用 OS（Linux/Windows/macOS）：用 MLFQ 的变种（CFS/Windows 调度器），自适应各类工作负载。
  • 批处理（HPC）：FCFS/SJF，求吞吐，无交互需求。
  • 实时系统（RTOS）：速率单调（RMS）或最早截止时间优先（EDF）——保证截止时间，超出本叶范围。
  • 交互式桌面：RR/MLFQ，求响应。

下一步 ​

理解了五种算法原理后，下一步是调度性能指标与计算——如何画甘特图、算平均等待/周转/响应时间、分析时间片大小对 RR 的影响、以及饥饿与老化机制的细节。