2025-05-09-进程调度算法分析
post on 09 May 2025 about 11198words require 38min
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
进程调度算法分析
参考资料
概述
调度指标与目标
单核 CPU 处理多个进程和线程
操作系统进程调度的核心目标在于合理分配 CPU 资源，使系统能够同时满足多个性能指标。常见的评估指标包括：
- CPU 利用率（CPU Utilization）
- CPU 在单位时间内非空闲状态的比例。理想情况下应尽量接近 100%。
- 吞吐量（Throughput）
- 单位时间内完成的作业（或进程）数量。吞吐量越高，单位时间完成任务越多。
- 周转时间（Turnaround Time）
- 从进程提交（到达）到完全执行结束所经历的总时间。
- 带权周转时间（Weighted Turnaround Time）
- 周转时间与执行时间之比，用于衡量短作业或长作业的相对等待公平性。
- 等待时间（Waiting Time）
- 进程在就绪队列中等待 CPU 的累积时间。
- 响应时间（Response Time）
- 从进程提交到系统开始响应（第一次分配 CPU）的时间。
- 公平性
- 同类进程应获得相似的资源分配和等待时间；避免饥饿（Starvation）。
不同的调度算法在上述指标上表现各异，系统应根据场景需求权衡：
- 交互式系统：关注响应时间（如 GUI 系统、服务器应用）。
- 批处理系统：关注吞吐量与周转时间（如科学计算、大规模数据处理）。
- 实时系统：关注任务能否在规定的截止时间前完成，使用实时调度算法（如 Rate Monotonic Scheduling、Earliest Deadline First）。
调度算法的分类
根据是否支持抢占（Preemptive）和队列策略，可将操作系统中的调度算法大致分为两类：
- 非抢占式调度（Non-preemptive Scheduling）
- 一旦进程被分配 CPU，直到该进程自愿放弃 CPU（如执行完成或进入 I/O 阻塞）才会切换。
- 算法典型：先来先服务 (FCFS)、短作业优先 (SJF，非抢占版本)、优先级非抢占。
- 抢占式调度（Preemptive Scheduling）
- 若有更高优先级的进程到达或某种时间片用尽，会强制剥夺当前进程的 CPU。
- 算法典型：短剩余时间优先 (SRTF)、优先级抢占、时间片轮转 (RR)、多级反馈队列等。
此外，按照就绪队列结构的不同，调度亦可分为：
- 单级队列（Single Queue）：所有就绪进程放在同一队列中，统一调度（上述 FCFS、SJF、RR 等）。
- 多级队列（Multi-Level Queue）：根据进程类型（交互式 vs 批处理）、优先级等分类，将进程放入多个队列，根据队列优先级逐级调度。
- 多级反馈队列（Multi-Level Feedback Queue, MLFQ）：在多级队列的基础上，允许进程在不同队列间动态迁移，从而兼顾响应时间和吞吐量。
常见单队列调度算法
先来先服务 (FCFS)
概念：
- 最简单的调度算法，类比数据结构中的队列,按照进程到达就绪队列的先后顺序分配 CPU，不做抢占。
- 类似排队买票：先到先服务。
基本流程：
- 就绪队列中，按照到达时间排序。
- CPU 空闲时，从队头取出第一个进程执行，运行完毕后再取下一个。
优点：
- 实现简单，易于理解和维护。
- 进程切换开销少，无抢占导致的上下文切换开销。
缺点：
- 等待时间不可控：一旦前面有一个长作业，后续短作业就会被“长作业阻塞”（Convoy Effect），导致平均等待时间变长。
- 平均周转时间较大：对短作业不友好。
- 无差别对待：不支持优先级，易造成关键任务延迟。
适用场景：
- 适合批处理系统中长时间运行、无需交互的作业调度。
短作业优先 (SJF) 与 最短剩余时间优先 (SRTF)
短作业优先 (SJF, Shortest Job First)
概念：
- 按照进程的估计执行时间（CPU Burst）长短来调度，优先选择执行时间最短的进程（非抢占）。
- 可以最大化减少平均等待时间。
流程：
- 当 CPU 空闲时，从就绪队列中选择执行时间最短的进程。
- 该进程运行至完成，然后再次从剩余进程中选择最短的继续。
优点：
- 平均等待时间最小（经证明）。
缺点：
- 需要预知执行时间：在实际系统中很难准确知道每个进程的执行时间，只能通过历史统计或猜测。
- 可能导致饥饿：如果系统中不断有短作业到来，长作业可能一直得不到执行机会。
最短剩余时间优先 (SRTF, Shortest Remaining Time First)
概念：
- 是 SJF 的抢占式版本。
- 当有新进程到达，若其估计总执行时间小于当前正在执行进程的剩余执行时间，则抢占当前进程，优先执行新进程。
流程：
- 维护就绪队列中各进程的剩余执行时间。
- 当新进程到达或某进程完成后，重新比较就绪队列中剩余时间最小的进程；若与当前执行进程不同，则进行抢占切换。
优点：
- 平均等待时间更小，响应更及时。
缺点：
- 更频繁的上下文切换：可能每次新进程到来都要抢占，增加系统负载。
- 难以预测与饥饿问题：同样存在长进程饥饿风险。
适用场景：
- 对平均等待时间要求很高、可接受大量切换开销的批处理环境。
优先级调度 (Priority Scheduling)
概念：
- 每个进程都与一个优先级（Priority）相关联，调度时始终选择优先级最高（数值最小或最大，取决于实现约定）的进程执行。
- 可分为非抢占式优先级调度和抢占式优先级调度：
- 非抢占式优先级：一旦进程被选中，直到它完成或自愿阻塞，其他高优先级进程到达也不能抢占。
- 抢占式优先级：如果有更高优先级的进程到达，会中断当前进程并调度高优先级进程执行。
优点：
- 可以根据任务重要程度分配资源，实现“关键任务优先”。
缺点：
- 饥饿（Starvation）：低优先级进程可能长时间无法获得 CPU。如果系统中高优先级任务持续到达，则低优先级任务可能永远得不到服务。
- 优先级反转（Priority Inversion）：低优先级进程持有资源（如锁），阻止高优先级进程执行，造成高优先级任务等待。可通过“优先级继承”等机制缓解。
优先级分配策略：
- 静态优先级：在进程创建时分配，不随运行时变化。
- 动态优先级：随着进程运行行为或等待时间动态调整。例如：长时间在就绪队列中等待，优先级随时间递增；使用 “ aging” 技术防止饥饿。
时间片轮转 (Round Robin, RR)
概念：
- 将 CPU 时间分成若干固定长度的时间片（Time Quantum），系统维护一个进程就绪队列（通常是 FIFO）。
- 每次调度时，将队头进程分配一个完整时间片或直到进程自行阻塞（I/O）／完成。时间片用完后，将该进程移动到队尾，依此循环。
流程：
- 初始化就绪队列，所有进程先按到达顺序加入队列。
- 系统为队头进程分配时钟中断，每次时钟中断到来时：
- 若进程尚未完成，且时间片已用完，则将其移动到队尾；
- 若进程完成或主动阻塞，直接移除或放入相应 I/O 等待队列。
- 选取下一个队头进程，重复上述步骤。
关键参数：
- 时间片大小 (Quantum)：
- 小时间片 → 系统响应快，适合交互式处理；但上下文切换频繁，开销大。
- 大时间片 → 切换开销小，但响应时间变长，接近 FCFS 效果。
- 通常取值应使上下文切换开销远小于时间片时长（如上下文切换需要 1–2 μs，时间片一般设为 10–100 ms）。
优点：
- 对所有进程一视同仁，易于实现和理解；
- 响应时间有保证（最坏响应时间 = 时间片 × 就绪进程数）；
- 无饥饿，进程最终会被分配 CPU。
缺点：
- 需要设置合适时间片；
- 上下文切换带来额外开销；
- 对 CPU 密集型与 I/O 密集型进程无区分，可能浪费时间片给 CPU 密集型作业；
- 如果时间片与进程执行时间不匹配，则吞吐量和周转时间可能不理想。
适用场景：
- 交互式系统，要求快速响应用户输入的环境（如终端、桌面交互系统）。
多级队列调度与多级反馈队列调度
4.1. 多级队列调度 (Multi-Level Queue)
概念：
- 根据进程的类别、优先级、服务需求等，将进程划分到不同的就绪队列中。每个队列可应用不同的调度算法或不同时间片长度。
- 各队列本身也按照优先级排列。当 CPU 空闲时，始终从最高优先级队列调度，若高优先级队列为空，才调度低优先级队列。
队列示例：
- 系统交互进程队列：RR 调度，时间片短；
- 批处理进程队列：FCFS 调度；
- 守护进程队列：优先级调度或 FCFS；
特点：
- 不同类型进程获得不同的服务策略；
- 各队列永久划分，不动态调整。
缺点：
- 需要在设计阶段预先进行进程分类，不灵活；
- 高优先级队列如果繁忙，低优先级队列可能饥饿。
多级反馈队列调度 (Multi-Level Feedback Queue, MLFQ)
概念：
时间片轮转和最高优先级算法的综合和拓展
- 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
- 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
- 在多级队列基础上，为了提高灵活性，允许进程在不同队列间根据行为“反馈”向下或向上移动。
- 目标：使得 I/O 密集型（短 CPU burst）进程获得较高优先级，CPU 密集型（长 CPU burst）进程优先级逐渐降低，从而兼顾系统响应性和吞吐量。
常见策略参数：
- 队列数 (N)：一般设为 3–5 级，从高到低优先级递减编号。
- 时间片 (Quantum)：不同队列拥有不同时间片长度。一般高优先级队列时间片短（例如 8ms），中/低级队列时间片依次加倍（16ms、32ms）。
- 晋升与降级规则：
- 降级：进程若在本级队列用完完整时间片（表明可能较 CPU 密集），则移动到下一低级队列；
- 晋升（或 Aging）：为了防止长期在低级队列的进程饥饿，可在一定条件下（如等待时间超过阈值）将其提升至更高级队列。
典型流程：
- 所有进程初始进入最高优先级队列（队列 0）。
- CPU 空闲时，从优先级最高且非空队列选取队头进程执行一个时间片或至该进程阻塞/完成。
- 若用完时间片且仍未完成，则降级到下一级队列尾。
- 若在某队列执行过程中阻塞（如进入 I/O），则保持在当前队列级别（或执行完成后重新进入高优先级队列，具体实现可不同）。
- 周期性或按需检查低级队列中的进程等待时间，执行晋升。
优点：
- 区分不同工作特征的进程（I/O 密集 vs CPU 密集），提高响应速度；
- 通过动态反馈减少饥饿。
缺点：
- 参数较多（队列数、时间片长度、晋升/降级阈值等），需要调优；
- 实现复杂度较高；
- 若设计不合理，仍可能出现低优先级进程饥饿。
适用场景：
- 一般通用操作系统（如 Linux 的 O(1) 调度器、早期 UNIX 调度），可兼顾交互式任务与后台批处理任务。
- 要求较高响应性的桌面系统或要求分时公平性的多用户系统。
调度算法的性能评估示例
下面通过假设的进程集合与到达时间、执行（CPU）时间示例，分别在 FCFS、SJF/SRTF、RR、和多级反馈队列环境下进行调度，计算关键指标并进行比较。
示例流程与假设数据
假设有 5 个进程，属性如下：
| 进程 PID | 到达时间 (Arrival) | CPU 执行时间 (Burst) | 优先级 (Priority)\* |
| P1 | 0 | 8 | 2 |
| P2 | 1 | 4 | 1 |
| P3 | 2 | 9 | 3 |
| P4 | 3 | 5 | 2 |
| P5 | 4 | 2 | 1 |
*仅在优先级调度或 MLFQ 中使用，数值越小优先级越高。
- 假设系统在时刻 0 之后开始调度，并且已知所有进程到达时间与执行时间。
- 时间单位可视为毫秒 (ms)。
我们分别对以下调度算法进行分析：
- FCFS (非抢占)
- SJF (假设非抢占)
- SRTF (抢占式短作业优先)
- RR (时间片 = 3)
- 多级反馈队列 (3 级队列，时间片分别 4、8、∞；无晋升)
FCFS 调度示例分析
调度顺序
| 时间区间 | 执行进程 |
| 0–8 | P1 |
| 8–12 | P2 |
| 12–21 | P3 |
| 21–26 | P4 |
| 26–28 | P5 |
解释：
- 时刻 0：P1 到达，分配 CPU；
- P1 用到时刻 8 才完成；
- 时刻 1–4 期间，P2、P3、P4、P5 依序到达并进入队列；
- 时刻 8：CPU 分配给队列头进程 P2（到达时间最早）；
- 依此类推。
关键指标计算
| PID | 到达时间 | 完成时间 (Finish) | 周转时间 = Finish - Arrival | 执行时间 (Burst) | 等待时间 = Turnaround - Burst |
| P1 | 0 | 8 | 8 | 8 | 0 |
| P2 | 1 | 12 | 11 | 4 | 7 |
| P3 | 2 | 21 | 19 | 9 | 10 |
| P4 | 3 | 26 | 23 | 5 | 18 |
| P5 | 4 | 28 | 24 | 2 | 22 |
- 平均周转时间
- 平均等待时间
- 平均带权周转时间
SJF/SRTF 调度示例分析
非抢占式 SJF
- 排除尚未到达的进程，只在 CPU 空闲且队列中已有进程时进行选择。
调度顺序：
- 时刻 0，P1 到达，CPU 分配给 P1。
- P1 执行到 8，期间 P2(1)、P3(2)、P4(3)、P5(4) 到达，队列内剩余执行时间分别 $P2:4, P3:9, P4:5, P5:2$。
- CPU 空闲时，于时刻 8 选择执行时间最短的 P5（Burst=2），执行 8–10。
- 时刻 10 选择剩余执行时间最短的 P2（Burst=4），执行 10–14。
- 时刻 14 选择 P4（Burst=5），执行 14–19。
- 最后执行 P3（Burst=9），时刻 19–28。
| 时间区间 | 执行进程 |
| 0–8 | P1 |
| 8–10 | P5 |
| 10–14 | P2 |
| 14–19 | P4 |
| 19–28 | P3 |
SJF 指标计算
| PID | 到达 | 完成 | 周转 = 完成−到达 | 执行 | 等待 = 周转 − 执行 |
| P1 | 0 | 8 | 8 | 8 | 0 |
| P2 | 1 | 14 | 13 | 4 | 9 |
| P3 | 2 | 28 | 26 | 9 | 17 |
| P4 | 3 | 19 | 16 | 5 | 11 |
| P5 | 4 | 10 | 6 | 2 | 4 |
- 平均周转时间：$(8 + 13 + 26 + 16 + 6)/5 = 69/5 = 13.8$
- 平均等待时间：$(0 + 9 + 17 + 11 + 4)/5 = 41/5 = 8.2$
相比 FCFS，SJF 平均周转、等待时间更低。
5.3.2. 抢占式 SRTF
在 SJF 基础上，当有新进程到达且其剩余执行时间小于当前正在执行进程的剩余时间时，会发生抢占。
调度细节：
- 时刻 0–1：P1 执行 0–1（剩余 7）
- 时刻 1：P2 到达 (Burst=4)，7 (P1 剩余) > 4 → 抢占。P2 执行 1–2（剩余 3），P1 剩余 7
- 时刻 2：P3 到达 (Burst=9)，当前最短为 P2(3)，继续。P2 执行 2–3（剩余 2）
- 时刻 3：P4 到达 (Burst=5)，当前最短为 P2(2)，继续。P2 执行 3–4（剩余 1）
- 时刻 4：P5 到达 (Burst=2)，此时 P2(1) 与 P5(2)，P2 更短 → P2 执行 4–5（完成）
- 较早完成 P2，队列剩余 P1(7)、P3(9)、P4(5)、P5(2)
- 时刻 5：当前最短 P5(Burst=2)，执行 5–7（完成）
- 时刻 7：队列剩余 P1(7)、P3(9)、P4(5)，最短为 P4(5)，执行 7–12（剩余 0 → 完成）
- 时刻 12：剩余 P1(7)、P3(9)，选择 P1(7)，执行 12–19（完成）
- 时刻 19–28：最后 P3(9)，执行到 28（完成）
| 时间区间 | 执行进程 |
| 0–1 | P1 |
| 1–4 | P2 |
| 4–5 | P2 |
| 5–7 | P5 |
| 7–12 | P4 |
| 12–19 | P1 |
| 19–28 | P3 |
注意：由于多个时间点属于同一进程的继续执行，合并相邻时间段可简化为：
1
2
3
4
5
P1: 0−1, 12−19
P2: 1−5
P5: 5−7
P4: 7−12
P3: 19−28
SRTF 指标计算
| PID | 到达 | 完成 | 周转 = 完成−到达 | 执行时间 | 等待 = 周转 − 执行 |
| P1 | 0 | 19 | 19 | 8 | 11 |
| P2 | 1 | 5 | 4 | 4 | 0 |
| P3 | 2 | 28 | 26 | 9 | 17 |
| P4 | 3 | 12 | 9 | 5 | 4 |
| P5 | 4 | 7 | 3 | 2 | 1 |
- 平均周转时间：$(19 + 4 + 26 + 9 + 3)/5 = 61/5 = 12.2$
- 平均等待时间：$(11 + 0 + 17 + 4 + 1)/5 = 33/5 = 6.6$
相比 SJF，SRTF 的平均等待、周转时间略有改进，但切换开销更高。
RR 调度示例分析（时间片 = 3）
假设时间片（Quantum） = 3。采用抢占式策略，时钟中断每 3 单位触发一次。
调度步骤
- 时刻 0–1
- P1 到达并开始执行。
- 经过 1 单位（时刻 1），P2 到达，仍在 P1 时间片内继续。剩余时间：P1 (7)。
- 时刻 1–3
- P1 继续执行至用完剩余时间片（3 单位），时刻 3 停止，剩余 P1(5)。
- 队列顺序：P2 (到达时刻 1)、P3(2)、P4(3)。
- 时刻 3–6
- 从队头取 P2（执行 3 单位），时刻 6 剩余 P2（1）。
- 新到达 P5(4) 已在队列尾。队列顺序：P3、P4、P5、P1（回到队尾）、P2(1)。
- 时刻 6–9
- 执行 P3 3 单位，时刻 9 剩余 P3(6)。队列：P4、P5、P1(5)、P2(1)、P3(6)。
- 时刻 9–12
- 执行 P4 3 单位，时刻 12 剩余 P4(2)。队列：P5、P1(5)、P2(1)、P3(6)、P4(2)。
- 时刻 12–14
- 执行 P5 2 单位（用完）、时刻 14 完成。队列：P1(5)、P2(1)、P3(6)、P4(2)。
- 时刻 14–17
- 执行 P1 3 单位，时刻 17 剩余 P1(2)。队列：P2(1)、P3(6)、P4(2)、P1(2)。
- 时刻 17–18
- 执行 P2 1 单位（完成），时刻 18。队列：P3(6)、P4(2)、P1(2)。
- 时刻 18–21
- 执行 P3 3 单位，时刻 21 剩余 P3(3)。队列：P4(2)、P1(2)、P3(3)。
-
时刻 21–23
- 执行 P4 2 单位（完成），时刻 23。队列：P1(2)、P3(3)。
-
时刻 23–25
- 执行 P1 2 单位（完成），时刻 25。队列：P3(3)。
-
时刻 25–28
- 执行 P3 3 单位（完成），时刻 28。队列空。
调度时间线（Gantt 图）
合并表示为各个片段与时间区间：
1
2
3
4
5
6
7
8
9
10
11
[0−3]: P1
[3−6]: P2
[6−9]: P3
[9−12]: P4
[12−14]: P5
[14−17]: P1
[17−18]: P2
[18−21]: P3
[21−23]: P4
[23−25]: P1
[25−28]: P3
RR 指标计算
| PID | 到达 | 完成 | 周转 = 完成−到达 | 执行时间 | 等待 = 周转−执行 |
| P1 | 0 | 25 | 25 | 8 | 17 |
| P2 | 1 | 18 | 17 | 4 | 13 |
| P3 | 2 | 28 | 26 | 9 | 17 |
| P4 | 3 | 23 | 20 | 5 | 15 |
| P5 | 4 | 14 | 10 | 2 | 8 |
- 平均周转时间：$(25 + 17 + 26 + 20 + 10)/5 = 98/5 = 19.6$
- 平均等待时间：$(17 + 13 + 17 + 15 + 8)/5 = 70/5 = 14$
相比 FCFS、SJF/SRTF，RR 的平均等待与周转时间更高，但响应时间更有保障（最坏响应时间为 3× 队列长度 ≈ 3×5 = 15）。
多级反馈队列示例分析
参数假设
- 队列数：3（Q0、Q1、Q2），优先级从高到低依次为 Q0 > Q1 > Q2。
- 时间片：
- Q0: 4
- Q1: 8
- Q2: FCFS（不再分时间片，相当于单独的 FCFS 队列）
- 进入队列规则：
- 所有进程初始进入 Q0。
- 在 Q0 中用完 4 单位还未完成，则降级到 Q1 队尾；
- 在 Q1 中用完 8 单位还未完成，则降级到 Q2 队尾；
- 在 Q2 中 FCFS 执行直至完成（不再降级）。
- 未用满本级时间片而发生阻塞，则保持本级队列（按到达顺序放回队尾）。
- 无晋升机制（简化模型）。
调度流程
- 时刻 0–4
- Q0 队列：P1(8) → 执行 4 单位至 剩余 P1(4)，时刻 4，降级至 Q1 队尾。
- 在时刻 1–4，P2(4)、P3(9)、P4(5)、P5(2) 先后到达，依次进入 Q0 队尾。
- 时刻 4–8
- Q0 调度队头为 P2(4) → 执行 4 单位 完成，时刻 8。
- Q0 队列剩余：P3(9)、P4(5)、P5(2)
- 时刻 8–12
- Q0 队头 P3(9) → 执行 4 单位，剩余 P3(5)，时刻 12，降级到 Q1 队尾。
- Q0 队列剩余：P4(5)、P5(2)
- 时刻 12–16
- Q0 队头 P4(5) → 执行 4 单位，剩余 P4(1)，时刻 16，降级到 Q1 队尾。
- Q0 队列剩余：P5(2)
- 时刻 16–18
- Q0 队头 P5(2) → 执行 2 单位 完成（未用满时片），时刻 18。
- Q0 队列空，此时切换到 Q1 队列。
- Q1 轮询
-
Q1 队列：
- P1(4) → 执行 4 单位 完成，时刻 22（未用满时片、直接完成，出列）。
- P3(5) → 执行 5 单位 完成，时刻 27（未用满时片、直接完成）。
- P4(1) → 执行 1 单位 完成，时刻 28。
- Q2
- 对本示例数据，无进程在 Q1 用满 8 单位，因此 Q2 无进程。
调度时间线（简化）
1
2
3
4
5
6
7
8
[0−4] P1 (Q0)
[4−8] P2 (Q0)
[8−12] P3 (Q0)
[12−16] P4 (Q0)
[16−18] P5 (Q0)
[18−22] P1 (Q1)
[22−27] P3 (Q1)
[27−28] P4 (Q1)
多级反馈队列指标计算
| PID | 到达 | 完成 | 周转 = 完成−到达 | 执行时间 | 等待 = 周转 − 执行 |
| P1 | 0 | 22 | 22 | 8 | 14 |
| P2 | 1 | 8 | 7 | 4 | 3 |
| P3 | 2 | 27 | 25 | 9 | 16 |
| P4 | 3 | 28 | 25 | 5 | 20 |
| P5 | 4 | 18 | 14 | 2 | 12 |
- 平均周转时间：$(22 + 7 + 25 + 25 + 14)/5 = 93/5 = 18.6$
- 平均等待时间：$(14 + 3 + 16 + 20 + 12)/5 = 65/5 = 13$
相比 FCFS、SJF、RR，MLFQ 在该示例中：
- 短作业（P2、P5）在 Q0 快速完成，等待时间明显较少；
- 长作业（P3、P4、P1）因在 Q0 多次降级，等待较长，但总周转时间依然优于简单 RR；
- 综合考虑响应与吞吐，有一定折中效果。
调度算法的优缺点总结
| 算法 | 优点 | 缺点 | 适用场景 |
| FCFS | 实现简单；没有抢占开销 | 平均等待/周转时间较大；易出现 Convoy Effect；无优先级区分 | 批处理系统、后台任务 |
| SJF | 平均等待/周转时间最小 | 需要预知执行时间；可能导致长作业饥饿 | 静态或可预估作业的批处理 |
| SRTF | 响应迅速、平均等待较小 | 抢占频繁，上下文切换开销大；同样存在饥饿 | 对延迟敏感的批处理、实验环境 |
| 优先级 | 可根据重要性分配资源；实现灵活 | 低优先级饥饿；优先级反转问题；需优先级分配策略 | 实时系统、含不同优先级任务的系统 |
| RR | 公平分配、多用户响应快；无饥饿 | 平均等待/周转时间偏大；需合理设置时间片 | 交互式系统、时分多用户环境 |
| 多级队列 | 可对不同进程类型采用不同策略；实现简洁 | 队列静态划分；低队列容易饥饿 | 操作系统进程分层管理 |
| 多级反馈队列 | 综合考虑CPU/I-O 进程；响应与吞吐折中；防止饥饿 | 参数较多，调优复杂；实现与维护开销大 | 通用操作系统（如 Linux 早期调度） |
| 实时调度 | 能保证任务在截止时间前完成；满足实时要求 | 算法复杂；只能针对实时任务；可能牺牲吞吐量和公平性 | 硬实时/软实时系统（如航天、工业控制） |
在实际操作系统中的典型应用
- UNIX/Linux 调度器
- 早期 UNIX 采用基于优先级的多级反馈队列调度（BSD 4.4 era）。
- Linux 2.6 → 3.x 采用 O(1) 调度器（使用固定数量队列和计时桶），基于多级反馈队列思想。
- 从 Linux 2.6.23 以后，切换到 CFS（Completely Fair Scheduler，完全公平调度器），采用红黑树实现时间共享，极大提高公平性与可伸缩性。
- Windows 调度器
- 采用最高响应优先级线程抢占 (preemptive, priority-based preemptive scheduling)，具有 32 级动态优先级和 1 级实时优先级。
- 同时对 I/O 密集型与 CPU 密集型线程进行动态优先级调整（I/O 密集型短期优先，避免饥饿）。
- 实时操作系统（RTOS）
- 典型算法：固定优先级抢占调度（Rate Monotonic Scheduling, RMS）、最早截止时间优先 (Earliest Deadline First, EDF)。
- 可保证在一定负载下满足硬实时任务的周期性执行约束。
- 虚拟化 / 容器调度
- Xen、KVM 等虚拟化平台需为每个虚拟 CPU 分配物理 CPU 时间片。
- Kubernetes 等容器编排系统中，每个容器对应多个线程/进程，调度器采用 CFS，配合 cgroups 限制和调节 CPU 份额。
优化思路与扩展
- 自适应时间片
- 动态调整 RR 时间片大小：初始时给交互进程较小的时间片，若长时间占用则增大；
- 可以减少上下文切换并兼顾 I/O 密集型进程响应。
- 混合调度
- 在多级队列中对不同队列采用不同算法。例如：Q0 用 RR，Q1 用优先级，Q2 用 FCFS；
- 结合实时任务与后台批处理任务，保证实时约束的同时兼顾吞吐。
- 基于负载的动态调度
- 在线监测系统负载、进程行为特征，对队列数、时间片长度、优先级自适应调整；
- 典型做法：短进程优先、I/O 密集任务优先、长时间等待任务提升优先级。
- 考虑缓存与上下文切换开销
- 在多核环境中，调度器需考虑缓存亲和性（CPU Affinity）、减少缓存抖动；
- 结合软/硬 NUMA 拓扑结构，将线程更合理地分配到 CPU 核心。
- 公平性与服务质量(QoS)
- 引入公平队列思路（如 CFS 红黑树），每个就绪线程按“虚拟运行时间”排序；
- 在云/容器环境中，根据配额/优先级设定不同权重，保证租户公平与性能可预测。
- 能源感知 (Energy-aware Scheduling)
- 通过调度让低优先级进程在低频核上执行，高性能进程在高频核执行；
- 动态调整 CPU 频率与电压（DVFS），配合负载情况与性能需求。
总结
- 进程调度算法是操作系统核心组件之一，直接影响系统性能、响应速度和公平性。
- 常见单队列算法（FCFS、SJF/SRTF、优先级调度、RR）应用于不同场景，各有优缺点：
- FCFS 实现简单，适合批处理；
- SJF/SRTF 平均等待最小，但需预估执行时间；
- 优先级调度可区分任务重要性，但需防止饥饿；
- RR 公平且适合交互式系统，但需谨慎设置时间片。
- 多级队列与多级反馈队列结合了多种策略，兼顾交互与吞吐，可在通用操作系统中灵活应用，但实现与调优复杂。
- 实际操作系统中（Linux、Windows、RTOS）多采用多级/公平调度或基于红黑树的 CFS，以满足多核、多租户、实时与能耗等综合需求。
- 调度器优化方向：
- 提高公平性（如 CFS/Fair Queue）；
- 降低上下文切换与缓存抖动开销；
- 引入实时、能耗、负载感知等扩展；
- 动态自适应调度参数以应对多变负载。
无论在桌面、服务器、嵌入式还是云环境中，选择合适的调度算法并进行针对性优化，都是提升系统响应能力与吞吐效率的关键环节。
参考文献
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th Edition). Wiley.
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems (4th Edition). Pearson.
- Stallings, W. (2018). Operating Systems: Internals and Design Principles (9th Edition). Pearson.
- Love, R. (2010). Linux Kernel Development (3rd Edition). Addison-Wesley.
- Bovet, D. P., & Cesati, M. (2005). Understanding the Linux Kernel (3rd Edition). O’Reilly Media.
- Docker 官方文档：“Resource Management and Scheduling”
- Mozilla 开源项目 “NSScheduler” 源码与文档
- “Rate Monotonic Scheduling (RMS)” Tutorial, Real-Time Systems Community.
- “Earliest Deadline First (EDF) Scheduling”, Real-Time Systems Tutorial.
延伸阅读方向：
- 现代多核环境下的调度（例如 CFS 的 Red-Black Tree 结构）
- 云计算平台中的容器/虚拟机资源调度策略
- 实时操作系统中固定优先级 vs 动态优先级调度算法对比
Related posts
Loading comments...