Appearance
多级队列调度
2026 大纲 二（二）4 CPU 调度算法的多级队列调度（MLQ），它是把单一就绪队列拆成多个后引出的一类算法。指标口径沿用 调度的基本概念与目标。
交互可视化
一种算法伺候不了所有进程
前面五种算法，每一种都在整个就绪队列上用同一套规则。 可就绪队列里躺着的东西性质差得非常远：
系统进程短小紧急、可能还持着锁；交互进程背后坐着人，要的是响应； 批处理作业无人等待，要的是吞吐。让它们用同一套规则，一定有一方被亏待。
于是很自然的做法是：别用一个队列了，拆开。 不同类型的进程进不同的子队列， 每条队列内部可以用不同的算法。
拆开之后要额外决定三件事：队列之间怎么调度、每条队列内部用什么算法、 进程按什么规则分配到队列。
第二件事有一条很好的判据：看这类进程的用户在等什么。 交互队列用 RR（用户坐在终端前，要响应时间的上界）； 批处理队列用 FCFS / SJF（无人在等，切换纯属损耗）； 系统进程队列用 FCFS（短小紧急，而且它可能持着锁，被切走会连累别人）。
第一件事有两种做法，各有代价：固定优先级保证紧急任务最快完成， 但低优先级队列可能饥饿；按队列划分时间片保证每类都有份， 但高优先级不再绝对优先。
⚠️ 最后一条是它与下一节的唯一分界：进程被永久分配到某条队列，不能移动。 这也意味着必须提前知道进程属于哪一类——而这个要求，正是下一节要解决的问题。
一、算法规则
单队列时只需要决定一件事："选谁"。拆成多队列后，这一件事分裂成三件，每一件都必须单独作出决策：
| 决策 | 可选做法 | 影响什么 |
|---|---|---|
| 队列间怎么调度 | 固定优先级：高优先级队列非空就先调度；或时间片划分：各队列按比例分配 CPU 时间 | 低优先级队列会不会饥饿 |
| 队列内用什么算法 | 每个队列独立选择（FCFS / RR / 优先级…） | 该类进程的响应与周转特性 |
| 进程如何分配到队列 | 按进程类型永久分配，不能在队列间移动 | 分类错了就永远错，且需要提前知道进程类型 |
二、队列内算法为什么要和队列类型匹配
"系统进程用 FCFS、交互进程用 RR、批处理用 FCFS"不是约定俗成，每一条都能从该类进程的目标指标推出来：
| 队列 | 该类进程最在乎的指标 | 因此内部算法应该 | 推导 |
|---|---|---|---|
| 系统进程 | 尽快做完（它往往持有内核资源，别人在等它） | FCFS（不切换） | 系统进程短小且紧急 ⇒ 切换开销相对于它的服务时间占比高 ⇒ 用 RR 反而亏；且它可能正持有内核锁，中途换下去会让其他进程一起等 |
| 交互进程 | 响应时间 | RR | 用户在终端前等着 ⇒ 必须给出响应时间的上界 ⇒ 只有 RR 提供 |
| 批处理进程 | 吞吐量，无人在等 | FCFS 或 SJF | 没有响应要求 ⇒ 每一次切换都是纯损耗 ⇒ 应尽量少切换 ⇒ FCFS 最省；若能预知服务时间，SJF 可进一步压低平均周转 |
三、队列间调度：两种方式的分工
| 指标（本篇算例） | 固定优先级 | 时间片划分 | 谁更好 |
|---|---|---|---|
| 平均周转时间 | 8.00 | 10.25 | 固定优先级 |
| 平均带权周转 | 1.79 | 2.48 | 固定优先级 |
| B1（最低队列）首次上 CPU | 10 | 7 | 时间片划分 |
| 平均响应时间 | 4.00 | 2.75 | 时间片划分 |
| S2（系统进程）完成时刻 | 6 | 12 | 固定优先级 |
固定优先级把 CPU 全部先给高优先级队列，高优先级队列的进程完成得最快，代价是低优先级队列被压在最后；时间片划分保证每个队列都拿到份额，低优先级队列提前拿到 CPU，代价是高优先级队列不再绝对优先。要保证紧急任务最快完成就用固定优先级，要保证每类进程都不被完全饿死就用时间片划分。
四、与优先级调度的关系
| 连续优先级调度 | 多级队列（固定优先级） | |
|---|---|---|
| 优先级取值 | 每个进程一个数值，可有很多档 | 只有 |
| 选人的开销 | 需在整个就绪队列里找最大值， | 只需找最高的非空队列， |
| 同档内如何区分 | 用数值区分 | 不区分，交给队列内算法（FCFS/RR…）决定 |
| 灵活性 | 同一套规则管所有进程 | 不同档可用不同的调度规则 |
五、优缺点
| 优点 | 缺点 |
|---|---|
| 不同类型进程用不同策略，针对性强 | 进程不能在队列间移动，分类一旦错了就永远错 |
| 选人开销只与队列数有关，与进程数无关 | 需要提前知道进程类型才能分配队列 |
| 队列间调度方式可选，能在"绝对优先"和"人人有份"之间取舍 | 固定优先级方案下低优先级队列可能饥饿 |
两种队列间调度方式在同一组数据上各推一遍（想看份额怎么切、低优先级队列何时才拿到 CPU 时展开）
三条队列：Q1 系统进程（FCFS）、Q2 交互进程（RR，
| 进程 | 所属队列 | 到达时间 | 服务时间 |
|---|---|---|---|
| S1 | Q1 系统 | 0 | 3 |
| S2 | Q1 系统 | 3 | 3 |
| I1 | Q2 交互 | 0 | 4 |
| B1 | Q3 批处理 | 0 | 6 |
方案一：固定优先级（抢占式）——任何时刻都执行优先级最高的非空队列的队首进程。
- t=0：三条队列都非空，选最高的 Q1 → S1 运行 0–3，完成。
- t=3：S2 恰好在此刻到达 Q1 ⇒ Q1 又变成非空 ⇒ 仍选 Q1 → S2 运行 3–6，完成。这一步关键：I1 和 B1 已经等了 3 个单位，但在固定优先级下"等多久"完全不进入比较，只看队列号。
- t=6：Q1 空，选 Q2 → I1 按 RR 运行 6–8（剩 2），队列里只有它，再取它 8–10，完成。
- t=10：Q1、Q2 都空，才轮到 Q3 → B1 运行 10–16，完成。
| 时间区间 | 0–3 | 3–6 | 6–10 | 10–16 |
|---|---|---|---|---|
| 执行进程 | S1 | S2 | I1 | B1 |
| 进程 | 完成时间 | 周转时间 | 带权周转 | 等待时间 | 首次上 CPU | 响应时间 |
|---|---|---|---|---|---|---|
| S1 | 3 | 3 | 3/3 = 1.00 | 0 | 0 | 0 |
| S2 | 6 | 3 | 3/3 = 1.00 | 0 | 3 | 0 |
| I1 | 10 | 10 | 10/4 = 2.50 | 6 | 6 | 6 |
| B1 | 16 | 16 | 16/6 ≈ 2.67 | 10 | 10 | 10 |
| 平均 | 8.00 | 1.79 | 4.00 | 4.00 |
方案二：时间片划分——把时间切成长度为 10 的循环周期，Q1 拿 4、Q2 拿 3、Q3 拿 3，按 Q1 → Q2 → Q3 轮流；某队列在自己的份额内没有就绪进程时，剩余份额作废，立刻轮到下一队列。
第一周期（t=0 起）：Q1 份额 4——S1 运行 0–3 完成（用掉 3），t=3 时 S2 到达，用掉份额剩下的 1 → S2 运行 3–4，份额耗尽被打断（剩 2 个服务单位）。Q2 份额 3——I1 按 RR 运行 4–6（剩 2），再取它，份额只剩 1 → 6–7（剩 1）。Q3 份额 3——B1 运行 7–10（剩 3）。
第二周期（t=10 起）：Q1 份额 4——S2 剩 2 → 10–12 完成，Q1 空，剩余的 2 个份额作废。Q2 份额 3——I1 剩 1 → 12–13 完成。Q3 份额 3——B1 剩 3 → 13–16 完成。
| 时间区间 | 0–3 | 3–4 | 4–7 | 7–10 | 10–12 | 12–13 | 13–16 |
|---|---|---|---|---|---|---|---|
| 执行进程 | S1 | S2 | I1 | B1 | S2 | I1 | B1 |
| 所属队列 | Q1 | Q1 | Q2 | Q3 | Q1 | Q2 | Q3 |
| 进程 | 完成时间 | 周转时间 | 带权周转 | 等待时间 | 首次上 CPU | 响应时间 |
|---|---|---|---|---|---|---|
| S1 | 3 | 3 | 3/3 = 1.00 | 0 | 0 | 0 |
| S2 | 12 | 9 | 9/3 = 3.00 | 6 | 3 | 0 |
| I1 | 13 | 13 | 13/4 = 3.25 | 9 | 4 | 4 |
| B1 | 16 | 16 | 16/6 ≈ 2.67 | 10 | 7 | 7 |
| 平均 | 10.25 | 2.48 | 6.25 | 2.75 |
考点速记
- 多级队列把就绪队列拆成多个独立子队列，不同类型的进程进不同队列、每条队列内部可用不同算法。
- 拆开后要额外决定三件事：队列之间怎么调度、每条队列内部用什么算法、进程如何分配到队列。
- ⚠️队列内算法要匹配"这类进程的用户在等什么"：交互队列用 RR（要响应时间上界）；批处理队列用 FCFS / SJF（无人在等，切换是纯损耗）；系统进程队列用 FCFS（短小紧急、而且可能持锁，被切走会连累别人）。
- 队列间调度两种做法各有代价：固定优先级保证紧急任务最快完成，但低优先级队列可能饥饿；按队列划分时间片保证每类都有份，但高优先级不再绝对优先。
- ⚠️进程被永久分配到某条队列、不能在队列间移动——这是它与多级反馈队列的唯一分界，也导致它必须提前知道进程类型。
- 固定优先级方案本质是把优先级离散成
档，选人开销从 降为 ，代价是同档内不再区分。
这一节在真题里被考过的形式：
多级队列（固定分配、不可移动的那一种）至今不单独成题。 本页下方练习区渲染的是整个 cpu-scheduling-algorithm 标签下的 12 道题、 由 8 篇算法共享，范围比本节宽，属正常——真题考的是它的改良版 多级反馈队列（2019-27、2020-26）。
不单独成题不等于不用读，理由有两条：
第一，它是理解 MLFQ 的必经一步。 MLFQ 的全部改良只有一处—— 允许进程在队列间移动（速记第五条）。不先看清多级队列"必须提前知道进程类型" 这个硬伤，就体会不到 MLFQ"让进程自己暴露长短"的价值。
第二，速记第三条那条判据（队列内算法要匹配用户在等什么）是选项素材。 凡出现"交互进程队列应采用哪种算法"这类问法，答案都由它给出。
复习优先级：读懂即可，重点是第五条那个分界。 把"多级队列不能移动、 多级反馈队列可以"这一句钉死，再理解第三条的匹配判据，就够了。 第四条那两种队列间调度方式的取舍不必细记。
易错：把多级队列和多级反馈队列混为一谈。唯一分界是进程能不能在队列间移动。
易错：认为多级队列不需要提前知道进程类型。必须知道——进程被永久分配，分错了改不了。
易错：给交互队列配 FCFS。交互进程背后坐着人，要的是响应时间上界，应该用 RR。
易错：认为固定优先级的队列间调度不会饥饿。低优先级队列可能一直排不上。
教材出处
- 汤小丹《计算机操作系统》3.3.4 多队列调度算法（把单一就绪队列拆分为若干个、不同类型或性质的进程固定分配在不同就绪队列、不同队列采用不同调度算法、队列本身也可设置不同优先级），印刷 p95
相关知识
调度的基本概念与目标｜高响应比优先调度｜多级反馈队列调度｜时间片轮转调度｜FCFS 先来先服务调度