处理机调度：调度算法与评价指标

概念

处理机调度（CPU scheduling）就是按照某种算法，从就绪队列中挑出一个进程，把处理机分配给它。

就绪队列 \overset{调度算法}{\to} 被选中的进程 \overset{分配 CPU}{\to} 运行态

一句话说清它是什么：调度就是"CPU 该给谁、给多久"这两个问题的答案——"给谁"是选择策略（本节的七种算法），"给多久"是时间片与抢占规则。

调度的本质是取舍：要吞吐量就牺牲响应（批处理优先 FCFS/SJF），要响应就牺牲吞吐（分时优先 RR）。没有"全都最好"的算法——这正是 408 反复考"对比"的原因。

原理

一、三级调度及它们的分工

级别	别名	干什么	发生频率	谁需要它
高级调度	作业调度	从外存的后备队列挑作业，调入内存并建立进程	最低（分钟级）	批处理系统必需；分时/实时系统通常没有
中级调度	内存调度（交换）	把暂时不能运行的进程挂起到外存，条件具备时再激活回内存	中	提高内存利用率与吞吐量
低级调度	进程调度	从就绪队列挑进程，分配 CPU	最高（毫秒级、几十 ms 一次）	所有系统都必须有

三者关系（一句话记住）：

高级调度（要多少人进场） \Rightarrow 中级调度（谁先下场歇会儿） \Rightarrow 低级调度（场上谁拿球）

⚠️ 两个易错点：

"作业调度"与"进程调度"不是一回事：作业调度决定"谁进内存"（它创建进程），进程调度决定"谁上 CPU"。作业调度频率远低于进程调度。
分时、实时系统通常没有高级调度——用户敲命令就产生进程，不存在"作业排队等进场"这一环。

二、进程调度的时机（能调与不能调）

必须立刻"不能调度"的三种情况（因为此时切换会破坏一致性）：

不能调度的时机	为什么
处理中断的过程中	中断处理程序要跑完；中断处理过程中不允许被切换掉
进程在内核临界区中（访问临界资源）	中途换人会让临界资源处于半加工状态
执行原子操作（原语）过程中	原语本身靠关中断保证不可中断（回顾 `os/10-process.md`）

引起进程调度（可以调度）的时机：

时机	说明
当前进程运行结束 / 主动 `exit`	必须有新进程上 CPU
当前进程阻塞（等 I/O、等信号量）	CPU 不能让给"跑不动的人"，必须换人
时间片用完	分时系统的"换人闹钟"
有更高优先级进程到达/被唤醒（抢占式）	抢占式系统才在这里换人
中断处理完毕返回用户态时	检查"是否需要调度"（`need_resched`）

⚠️ 关键区别："不能调度"≠"不发生状态转换"。中断处理中进程可能被"置上重调度标志"，但要等中断返回、退出内核临界区后才真正切换——这叫**"延迟调度"**。

三、抢占式与非抢占式

类型	规则	缺点/特点
非抢占式（不可剥夺）	进程主动让出（结束、阻塞）才能换人	实现简单、开销小；一个长作业能让交互作业卡住（响应差）
抢占式（可剥夺）	时间片到 / 更高优先级到达 / 更短作业到达都可强行换人	响应好；切换开销大，且要处理"数据一致性"问题

抢占的三条常见原则：优先级原则（高优先级到达即抢占）、短作业（剩余时间）原则（SRTF）、时间片原则（用完即抢）。

四、评价指标（五个，公式必须默写）

指标	定义	公式
CPU 利用率	CPU 忙时间占比	$η = T_{忙} / T_{总}$
系统吞吐量	单位时间完成的作业数	$T P = N / T$
周转时间	从提交到完成	$T = T_{完成} - T_{到达}$
带权周转时间	周转时间相对自己服务时间的倍数	$W = T / T_{服务}$ （恒 ≥ 1）
等待时间	在队列里等的时间	$T_{等待} = T_{周转} - T_{服务}$ （对作业而言）

响应比（HRRN 专用）：

R = \frac{等待时间 + 要求服务时间}{要求服务时间} = 1 + \frac{等待时间}{服务时间}

⚠️ 四个易错点：

带权周转时间恒 ≥ 1，它消除了"作业大小"的影响——所以比较算法优劣时更常看"平均带权周转时间"。
"等待时间"对进程口径要加上"等 I/O 的时间"（进程在阻塞队列里也是等待）；对作业口径只看"在队列里等 CPU 的时间"。答题必须先声明口径。
响应比里"等待越久，响应比越高"——这就是 HRRN 不会饿死长作业的原因。
CPU 利用率与吞吐量不是一回事：一个长作业独占 CPU 时利用率可以 100%，但吞吐量很低。

五、七种调度算法

1. FCFS 先来先服务（First Come First Served）

按到达顺序排队，非抢占。实现最简单（就是一个 FIFO 队列）。特点：有利于长作业、CPU 繁忙型作业；不利于短作业、I/O 繁忙型作业（短作业等在长作业后面，带权周转时间会非常大）。

2. SJF / SPF 短作业优先（Shortest Job First）

挑"要求服务时间最短"的作业，非抢占。其抢占版叫 SRTF（Shortest Remaining Time First，最短剩余时间优先）。特点：

在所有作业同时到达的前提下，SJF 的平均等待时间/平均周转时间最短（这是可证明的最优性）。
缺点：对长作业不利，可能造成"长作业饥饿"；"服务时间"往往无法预知（只能估计）。

3. HRRN 高响应比优先（Highest Response Ratio Next）

非抢占，每次选响应比 $R$ 最大的作业。特点： $R = 1 + 等待 / 服务$ ——等待越久 $R$ 越大，长作业不会被饿死；但从平均指标看不如 SJF 好（见例 2 的反直觉结果）。

4. 优先级调度

按优先级挑。分静态优先级（创建时定死）与动态优先级（运行中调整）；分抢占式与非抢占式。 确定优先级的常见依据：系统 > 用户、交互 > 批处理、I/O 繁忙 > CPU 繁忙（让 I/O 型先跑，它很快会去等 I/O，CPU 好让给算的）。

5. RR 时间片轮转（Round Robin）

就绪队列按 FCFS 排队，每个进程最多跑一个时间片 $q$ ；用完回队尾。抢占式（按时间片抢占）。特点：

q \to \infty \Rightarrow 退化为 FCFS; q \to 0 \Rightarrow 切换开销占比 f_{o v} \to 100 %

⚠️ 时间片大小的两个极端：

$q$ 太大 → 退化成 FCFS，响应变差（例 1 里 $q = 4$ 已接近 FCFS 的表现）。
$q$ 太小 → 上下文切换成为瓶颈（回顾 os/10-process.md 例 2： $q = 1 ms$ 时切换开销占 0.9901%；再小就危险了）。

6. 多级反馈队列（Multilevel Feedback Queue）

最通用、综合最好的方案：设置多个优先级递减的就绪队列，第 1 级时间片最短。

三条规则（必背）：

新进程进第 1 级队尾；在某一级用完时间片还没跑完 → 降到下一级队尾（"降级"= 惩罚 CPU 型作业）。
只有第 $k$ 级为空时，才调度第 $k + 1$ 级（高优先级严格优先）。
被抢占的进程放回"本级"队尾（不降级——它还没用完时间片）。

为什么它"综合最好"：短作业在第 1 级就跑完（像 SJF 一样快）；长作业逐步降级（像 FCFS 一样不被饿死）；I/O 型作业总在第 1 级（响应快）。

7. 算法对比总表

算法	抢占?	选谁	优点	缺点
FCFS	否	最先到达	简单、无饥饿	短作业不利、带权周转差
SJF	否	服务时间最短	平均周转最短（同批到达时）	长作业饥饿、需预知服务时间
SRTF	是	剩余时间最短	平均周转更短	饥饿更严重、切换更多
HRRN	否	响应比最高	不饥饿、兼顾长短	平均指标不如 SJF
优先级	可选	优先级最高	灵活（可区分实时/交互）	低优先级饥饿
RR	是	队头（每片一个）	响应快、公平	$q$ 难定； $q$ 小则开销大
多级反馈队列	是	高优先级队列先	综合最好、无需预知服务时间	参数多、实现复杂

示例

例 1：六种算法的完整计算

四个作业同时已在系统里，到达时间与服务时间如下（时间单位：ms）。分别用 FCFS、SJF（非抢占）、SRTF、HRRN、RR（ $q = 1$ ）、RR（ $q = 4$ ） 调度，求完成顺序、每个作业的周转时间与带权周转时间、以及平均值。
作业到达服务
A 0 7
B 2 4
C 4 1
D 5 4

作业	到达	服务
A	0	7
B	2	4
C	4	1
D	5	4

统一口径（先写在答题纸上，避免争议）：

周转时间 = 完成 − 到达；带权周转 = 周转 / 服务。
RR 规则：新到达的进程在其到达时刻入队尾；时间片用尽的进程也入队尾；同一时刻两者相撞，先入"新到达"。
SRTF / SJF 遇相同的服务时间时按"到达早者优先"。

（1）FCFS

执行时序（甘特图）：

|----A(7)----|--B(4)--|-C(1)|--D(4)--|
0            7        11    12       16

逐步算周转：

作业	完成	周转 = 完成 − 到达	带权 = 周转 / 服务
A	7	$7 - 0 = 7$	$7 / 7 = 1.000$
B	11	$11 - 2 = 9$	$9 / 4 = 2.250$
C	12	$12 - 4 = 8$	$8 / 1 = 8.000$
D	16	$16 - 5 = 11$	$11 / 4 = 2.750$

平均周转 = \frac{7 + 9 + 8 + 11}{4} = \frac{35}{4} = 8.7500

平均带权周转 = \frac{1.000 + 2.250 + 8.000 + 2.750}{4} = \frac{14.000}{4} = 3.5000

看 C：它只要 1 ms，却因为"排在长作业后面"而带权周转达到 8.000。这就是 FCFS 对短作业的伤害。

（2）SJF（非抢占）

$t = 0$ 只有 A 到达 → A 先跑 7 ms； $t = 7$ 时 B、C、D 都到了（4、1、4 ms），挑最短的 C；然后 B、D 服务时间相同，按到达早者优先 → B。

|----A(7)----|-C|-B(4)--|--D(4)--|
0            7 8       12       16

作业	完成	周转	带权
A	7	7	1.000
B	12	$12 - 2 = 10$	2.500
C	8	$8 - 4 = 4$	4.000
D	16	$16 - 5 = 11$	2.750

平均周转 = \frac{7 + 10 + 4 + 11}{4} = 8.0000 平均带权 = \frac{1.000 + 2.500 + 4.000 + 2.750}{4} = 2.5625

（3）SRTF（抢占）

逐时刻推演（这是唯一需要"逐步"的算法，务必按事件时间点走）：

时刻	事件	就绪/剩余	选中
0	A 到（剩 7）	A:7	A
2	B 到（4），A 剩 5	A:5, B:4	B（抢占 A）
4	C 到（1），B 剩 2	A:5, B:2, C:1	C（抢占 B）
5	D 到（4），C 已完成	A:5, B:2, D:4	B
7	B 完成	A:5, D:4	D
11	D 完成	A:5	A
16	A 完成	—	—

|-A-|-B-|-C|-B-|--D(4)--|----A(5)----|
0   2   4 5   7        11           16

作业	完成	周转	带权
A	16	16	$16 / 7 = 2.286$
B	7	$7 - 2 = 5$	$5 / 4 = 1.250$
C	5	$5 - 4 = 1$	$1 / 1 = 1.000$
D	11	$11 - 5 = 6$	$6 / 4 = 1.500$

平均周转 = \frac{16 + 5 + 1 + 6}{4} = 7.0000 平均带权 = \frac{2.286 + 1.250 + 1.000 + 1.500}{4} = 1.5089

对比 FCFS：平均周转 8.75 → 7.00，平均带权 3.5000 → 1.5089（降了 56.9%）。代价是 A 被反复打断（A 的周转从 7 涨到 16）。

（4）HRRN（非抢占）

$t = 0$ ：只有 A → A 跑 7 ms。 $t = 7$ ：算三个候选的响应比（ $R = 1 + 等待 / 服务$ ，等待 = $7 - 到达$ ）：

候选	等待	服务	$R$
B	5	4	$1 + 5 / 4 = 2.250$
C	3	1	$1 + 3 / 1 = 4.000$ ← 最大
D	2	4	$1 + 2 / 4 = 1.500$

→ 选 C（ $t = 7 \sim 8$ ）。 $t = 8$ ：B 等待 6 → $R = 1 + 6 / 4 = 2.500$ ；D 等待 3 → $R = 1 + 3 / 4 = 1.750$ → 选 B（ $8 \sim 12$ ）→ D（ $12 \sim 16$ ）。

结果与 SJF 完全相同：

作业	完成	周转	带权
A	7	7	1.000
B	12	10	2.500
C	8	4	4.000
D	16	11	2.750

平均周转 = 8.0000 平均带权 = 2.5625

⚠️ 这是本题的一个"巧合"：本例中 HRRN 与 SJF 选了同一批顺序。两者不一定相同——例 2 给出它们分歧的最小反例。

（5）RR（ $q = 1$ / $q = 4$ ）

$q = 1$ ：按"新到达先入队、时间片到期后入队尾"逐时刻轮转，得：

作业	完成	周转	带权
A	15	15	$15 / 7 = 2.143$
B	12	10	2.500
C	6	2	2.000
D	16	11	2.750

平均周转 = 9.5000 平均带权 = 2.3482

$q = 4$ ：

作业	完成	周转	带权
A	12	12	$12 / 7 = 1.714$
B	8	6	1.500
C	9	5	5.000
D	16	11	2.750

平均周转 = 8.5000 平均带权 = 2.7411

六种算法汇总：

算法	完成顺序	平均周转	平均带权周转
FCFS	A → B → C → D	8.7500	3.5000（最差）
SJF	A → C → B → D	8.0000	2.5625
HRRN	A → C → B → D	8.0000	2.5625
SRTF	C → B → D → A	7.0000（最好）	1.5089（最好）
RR $q = 1$	C → B → A → D	9.5000	2.3482
RR $q = 4$	B → C → A → D	8.5000	2.7411

三条结论：

SRTF 的平均周转最小（7.0000）——"抢占版最短剩余时间"在平均指标上确实最强，代价是 A 被拆成 6 段、切换次数最多。
RR 的两个时间片给出相反的结论： $q = 1$ 平均周转最差（9.5000）但平均带权较好（2.3482）； $q = 4$ 反过来。这正是"平均周转"与"平均带权"两个指标口径不同导致的—— $q$ 越大越像 FCFS。
SJF 与 HRRN 在本例并列（2.5625），但两者对"长作业"的态度完全不同（见例 2）。

例 2：SJF 与 HRRN 的分歧——"最优"与"公平"的取舍

作业集：A(到达 0，服务 1)、B(到达 0，服务 10)、C(到达 1，服务 1)、D(到达 1，服务 1)。分别用 **SJF（非抢占）**与 **HRRN（非抢占）**调度。

SJF： $t = 0$ 时 A、B 都到了 → 选 A（1 ms）； $t = 1$ 时 C、D 到达，候选 B(10)、C(1)、D(1) → 选 C、D，最后 B。

作业	完成	周转	带权
A	1	1	1.000
B	13	13	1.300
C	2	1	1.000
D	3	2	2.000

平均周转 = 4.2500 平均带权 = 1.3250

HRRN： $t = 1$ 时算响应比：B 等待 1 → $R = 1 + 1 / 10 = 1.100$ ；C、D 等待 0 → $R = 1 + 0 / 1 = 1.000$ 。B 的响应比反而最高 → 先跑 B。

作业	完成	周转	带权
B	10	10	1.000
A	11	11	11.000
D	12	11	11.000
C	13	12	12.000

平均周转 = 11.0000 平均带权 = 8.7500

两条截然相反的结论（都要记住）：

视角	SJF	HRRN
平均带权周转	1.3250（好得多）	8.7500（差得多）
最长作业 B 的周转	13（被一直往后推）	10（被提前照顾）
公平性	长作业会饥饿	不会饥饿

⚠️ 反直觉的点：HRRN 的平均指标远差于 SJF——因为 $R = 1 + 等待 / 服务$ 中，"服务时间越长， $R$ 的抬升越慢但起点也只要 1.1 就能赢过新到达的 1.0"。式子的结构决定了：当"等待时间"还很小的时候，长作业的 $R$ 与短作业几乎一样（都接近 1），一旦略高就抢先。
所以正确结论是：HRRN 用"平均指标变差"换"长作业不被饿死"——"公平"是有价格的。答题时别写成"HRRN 比 SJF 更好"，必须说清是哪个口径。

例 3：C 实现——FCFS / SJF / HRRN 的调度模拟

#include <stdio.h>

/* 四个作业: 到达时间, 服务时间 */
static const char *NAME[4] = {"A", "B", "C", "D"};
static const int  ARR[4]  = {0, 2, 4, 5};
static const int  SVC[4]  = {7, 4, 1, 4};
#define N 4

/* 挑下一个作业: mode = 0 FCFS(最早到达), 1 SJF(服务最短), 2 HRRN(响应比最大) */
static int pick(int done[], int t, int mode) {
    int best = -1;
    double best_ratio = -1.0;
    for (int i = 0; i < N; i++) {
        if (done[i] || ARR[i] > t) continue;         /* 没做完且已到达 */
        if (best < 0) { best = i; best_ratio = (t - ARR[i] + SVC[i]) / (double)SVC[i]; continue; }
        if (mode == 0) {                             /* FCFS: 到达早者优先 (同到达则编号小者) */
            if (ARR[i] < ARR[best]) best = i;
        } else if (mode == 1) {                      /* SJF: 服务短者优先 */
            if (SVC[i] < SVC[best] || (SVC[i] == SVC[best] && ARR[i] < ARR[best])) best = i;
        } else {                                     /* HRRN: 响应比大者优先 */
            double r = (t - ARR[i] + SVC[i]) / (double)SVC[i];
            if (r > best_ratio) { best = i; best_ratio = r; }
        }
    }
    return best;
}

static void run(int mode, const char *tag) {
    int done[N] = {0, 0, 0, 0}, fin[N] = {0, 0, 0, 0}, tmp[N];
    int t = 0, cnt = 0;
    double sum_t = 0.0, sum_w = 0.0;
    while (cnt < N) {
        int i = pick(done, t, mode);
        if (i < 0) { t++; continue; }                 /* 此刻无人可跑 */
        t += SVC[i];
        fin[i] = t; done[i] = 1; cnt++;
    }
    /* 先算指标, 再按"完成时刻升序"输出 (否则会破坏 fin[]) */
    for (int i = 0; i < N; i++) {
        sum_t += fin[i] - ARR[i];
        sum_w += (fin[i] - ARR[i]) / (double)SVC[i];
        tmp[i] = fin[i];
    }
    printf("%-5s 完成:", tag);
    for (int k = 0; k < N; k++) {                     /* 按完成时刻从小到大输出 */
        int m = 0;
        for (int i = 1; i < N; i++) if (tmp[i] < tmp[m]) m = i;
        printf(" %s=%d", NAME[m], tmp[m]);
        tmp[m] = 1 << 30;                             /* 用过就置大, 相当于删掉 */
    }
    printf(" | 平均周转 %.4f 平均带权 %.4f\n", sum_t / N, sum_w / N);
}

int main(void) {
    printf("作业集 A(0,7) B(2,4) C(4,1) D(5,4)\n");
    run(0, "FCFS");
    run(1, "SJF");
    run(2, "HRRN");
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

作业集 A(0,7) B(2,4) C(4,1) D(5,4)
FCFS  完成: A=7 B=11 C=12 D=16 | 平均周转 8.7500 平均带权 3.5000
SJF   完成: A=7 C=8 B=12 D=16 | 平均周转 8.0000 平均带权 2.5625
HRRN  完成: A=7 C=8 B=12 D=16 | 平均周转 8.0000 平均带权 2.5625

两个要点：

SJF 与 HRRN 在本例给出同一结果——这不是 bug，而是"本题数据使两种策略的偏好一致"（例 2 才是它们的分歧）。
SVC[i] == SVC[best] 时的"到达早者优先"必须写进代码：B 与 D 服务时间都是 4，没有这个兜底规则，同一份数据可能算出 B、D 顺序颠倒的结果——考场上也必须在答题纸上写明并列时怎么裁决。

例 4：Python——六种算法与指标全表验算

JOBS = [('A', 0, 7), ('B', 2, 4), ('C', 4, 1), ('D', 5, 4)]

def report(tag, fin):
    tot_t = tot_w = 0.0
    seq = sorted(JOBS, key=lambda j: fin[j[0]])
    for n, a, s in JOBS:
        t = fin[n] - a
        tot_t += t
        tot_w += t / s
    return '%-9s 完成顺序 %s | 平均周转 %.4f 平均带权 %.4f' % (
        tag, ' -> '.join(j[0] for j in seq), tot_t / len(JOBS), tot_w / len(JOBS))

def nonpre(key):
    rem, t, fin = list(JOBS), 0, {}
    while rem:
        rd = [j for j in rem if j[1] <= t]
        if not rd:
            t = min(j[1] for j in rem); continue
        p = key(rd, t)
        t = max(t, p[1]) + p[2]; fin[p[0]] = t; rem.remove(p)
    return fin

def srtf():
    rem = {j[0]: j[2] for j in JOBS}; fin = {}; t = 0
    while len(fin) < len(JOBS):
        rd = [j for j in JOBS if j[1] <= t and j[0] not in fin]
        if not rd:
            t = min(j[1] for j in JOBS if j[0] not in fin); continue
        p = min(rd, key=lambda j: (rem[j[0]], j[1], j[0]))
        rem[p[0]] -= 1; t += 1
        if rem[p[0]] == 0:
            fin[p[0]] = t
    return fin

def rr(q):
    pend = sorted(JOBS, key=lambda j: (j[1], j[0]))
    rem = {j[0]: j[2] for j in JOBS}; fin = {}; qq = []; t = 0; cur = None; used = 0
    for j in list(pend):
        if j[1] <= 0:
            qq.append(j[0]); pend.remove(j)
    while len(fin) < len(JOBS):
        if cur is None:
            if qq:
                cur = qq.pop(0); used = 0
            else:
                t += 1
                for j in list(pend):
                    if j[1] <= t:
                        qq.append(j[0]); pend.remove(j)
                continue
        rem[cur] -= 1; used += 1; t += 1
        new = []
        for j in list(pend):
            if j[1] <= t:
                new.append(j[0]); pend.remove(j)
        if rem[cur] == 0:
            fin[cur] = t; cur = None; qq.extend(new)
        elif used == q:
            qq.extend(new); qq.append(cur); cur = None
        else:
            qq.extend(new)
    return fin

print(report('FCFS',  nonpre(lambda rd, t: min(rd, key=lambda j: (j[1], j[0])))))
print(report('SJF',   nonpre(lambda rd, t: min(rd, key=lambda j: (j[2], j[1], j[0])))))
print(report('HRRN',  nonpre(lambda rd, t: max(rd, key=lambda j: ((t - j[1] + j[2]) / j[2], -j[1], j[0])))))
print(report('SRTF',  srtf()))
print(report('RR q=1', rr(1)))
print(report('RR q=4', rr(4)))

print('')
print('RR 口径: 新到达先入队尾, 时间片到期者后入队尾; 并列时到达早者优先')
print('q -> 无穷 时 RR 退化为 FCFS (SJF 平均周转 8.0000 仍优于 FCFS 8.7500)')

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照：得 FCFS 8.7500/3.5000、SJF 8.0000/2.5625、HRRN 8.0000/2.5625、SRTF 7.0000/1.5089、RR q=1 9.5000/2.3482、RR q=4 8.5000/2.7411——与例 1 手算逐位一致。

⚠️ 一个口径提醒：RR 的"完成顺序"与"周转时间"依赖"新到达与到期同时刻的入队顺序"。本题采用"新到达先入队尾"；若改成"到期者先入队尾"，RR $q = 1$ 的完成时刻会变。 考试时必须把这条规则写出来（真题答案通常也会显式说明），否则同一份数据可以算出不同答案，会被判错。

考点

1. 必背结论

三级调度：高级=作业调度（外存→内存，频率最低）、中级=内存调度（挂起/激活）、低级=进程调度（就绪→CPU，频率最高）。分时/实时系统通常没有高级调度。
不能调度的三种时机：中断处理过程中、内核临界区中、原子操作中。
能调度的时机：进程结束、进程阻塞、时间片用完、更高优先级到达（抢占式）、中断返回时检查标志。
评价指标： $T_{周转} = T_{完成} - T_{到达}$ ； $W = T_{周转} / T_{服务} \geq 1$ ； $R = (等待 + 服务) / 服务 = 1 + 等待 / 服务$ 。
SJF 在"所有作业同时到达"时平均等待（周转）最短；其抢占版 SRTF 更强（本题 7.0000 最优）。
HRRN 的核心优势是"不饥饿"，代价是平均指标可能比 SJF 差（例 2：8.7500 vs 1.3250）。
RR 的时间片是唯一参数： $q \to \infty$ 退化为 FCFS； $q$ 太小则切换开销占比飙升（ $f_{o v} = t_{s w} / (q + t_{s w})$ ）。
多级反馈队列三条规则：新进程进第 1 级；用完时间片降级；只有第 $k$ 级空才调度第 $k + 1$ 级；被抢占者回本级队尾（不降级）。
多级反馈队列的优点：不必预知服务时间，且长短作业、I/O 型作业都能照顾到。

2. 高频陷阱

把"作业调度"与"进程调度"当同一件事：错。一个决定"谁进内存"，一个决定"谁上 CPU"；后者频率高得多。
说"时间片越小越好"：错。 $q$ 越小切换越频繁，开销占比 $t_{s w} / (q + t_{s w})$ 越大（ $q = 1 ms$ 时已达 0.9901%）。
说"HRRN 一定比 SJF 好"：错。HRRN 的公平性好，但平均带权周转可能差得多（例 2）。必须分口径说。
说"RR 的完成顺序唯一"：错。它依赖"新到达与时间片到期撞车时谁先入队"——答题不写这条规则就是给自己埋雷。
把"等待时间"算错口径：作业口径 = 周转 − 服务（不含等 I/O）；进程口径要加上在阻塞队列里等的时间。
忘了"带权周转恒 ≥ 1"：算出小于 1 的数说明周转时间或服务时间代错了。
说"SRTF 因为抢占所以切换少"：错。抢占式切换次数更多（本例 A 被切成 6 段），只是平均周转更好。
说"FCFS 有利于短作业"：错，正好相反。FCFS 有利于长作业与 CPU 繁忙型，不利于短作业与 I/O 繁忙型。
把"优先级调度"与"抢占式"绑死：错。优先级调度既有抢占式也有非抢占式（优先级只决定"选谁"，抢占决定"能不能中断当前"）。
多级反馈队列里把"被抢占"也降级：错。被抢占的进程还没用完时间片，回本级队尾；只有"用完时间片没跑完"才降级。

3. 解题模板（"调度计算题"）

① 先写口径: 周转/带权公式 + 并列裁决规则 + RR 的入队顺序规则
② 画时序表或甘特图: 逐事件时刻推进 (到达、完成、时间片到期、抢占)
   - 非抢占: 只在一段跑完后才重新选
   - 抢占: 每次"新到达"都要重新比较 (SRTF 比剩余时间)
   - RR: 严格按时间片切, 用队列模拟
③ 算每个作业: 完成时刻 -> 周转 -> 带权
④ 求平均, 并回答"谁优谁劣 + 代价是什么"
⑤ 若题目问"能否更优": 用 SJF/SRTF 的最优性作答, 同时指出"饥饿"代价

4. 与相邻章节的接口

os/10-process.md（进程与线程）：调度只从"就绪队列"里挑人；"就绪 → 运行"的唯一入口就是本篇的调度程序。"时间片"这个词在那里第一次出现。
os/13-semaphore.md（信号量）："运行 → 阻塞"最常见的触发器是 P 操作失败；调度器此时必须换人。
os/16-deadlock.md（死锁）：调度策略不当会造成优先级翻转（低优先级持锁、高优先级自旋），那里的解法之一就是赋予持锁者高优先级。
os/01-overview.md（概述）："多道批处理提高利用率"的锚点数据（40% → 66.67%）就来自那篇——调度算法决定了 CPU 与外设能不能重叠起来。
arch/33-exception.md（异常与中断）：**"中断返回时检查是否需要调度"**是硬件与 OS 交接的关键时刻；时钟中断就是"时间片的发条"。

小结

调度就是回答两件事：CPU 给谁（选谁）、给多久（时间片/抢占）。三级调度：作业调度进内存、内存调度挂起激活、进程调度上 CPU。
五个指标：利用率、吞吐量、周转时间、带权周转（≥1）、等待时间；HRRN 另有响应比 $R = 1 + 等待 / 服务$ 。
例 1 全部算完：FCFS 8.7500/3.5000、SJF 与 HRRN 8.0000/2.5625、SRTF 7.0000/1.5089（最优）、RR $q = 1$ 9.5000/2.3482、RR $q = 4$ 8.5000/2.7411。
"最优"与"公平"是两件事：例 2 里 SJF 平均带权 1.3250（远胜 HRRN 的 8.7500），但长作业 B 的周转是 13 vs HRRN 的 10——前者最优、后者不饥饿。
RR 的一切都取决于 $q$ ： $q \to \infty$ 退化为 FCFS； $q$ 太小则上下文切换吃掉 CPU。答题必须写明"新到达与到期撞车时谁先入队"。
多级反馈队列是工程上的最终答案：不必预知服务时间、长短通吃、I/O 型响应快。

下一篇：同步与互斥：临界区、软硬件实现

处理机调度：调度算法与评价指标

概念

原理

一、三级调度及它们的分工

二、进程调度的时机（能调与不能调）

三、抢占式与非抢占式

四、评价指标（五个，公式必须默写）

五、七种调度算法

1. FCFS 先来先服务（First Come First Served）

2. SJF / SPF 短作业优先（Shortest Job First）

3. HRRN 高响应比优先（Highest Response Ratio Next）

4. 优先级调度

5. RR 时间片轮转（Round Robin）

6. 多级反馈队列（Multilevel Feedback Queue）

7. 算法对比总表

示例

例 1：六种算法的完整计算

（1）FCFS

（2）SJF（非抢占）

（3）SRTF（抢占）

（4）HRRN（非抢占）

（5）RR（ $q = 1$ / $q = 4$ ）

例 2：SJF 与 HRRN 的分歧——"最优"与"公平"的取舍

例 3：C 实现——FCFS / SJF / HRRN 的调度模拟

例 4：Python——六种算法与指标全表验算

考点

小结

我的笔记

评论（0）

处理机调度：调度算法与评价指标 ​

概念 ​

原理 ​

一、三级调度及它们的分工 ​

二、进程调度的时机（能调与不能调） ​

三、抢占式与非抢占式 ​

四、评价指标（五个，公式必须默写） ​

五、七种调度算法 ​

1. FCFS 先来先服务（First Come First Served） ​

2. SJF / SPF 短作业优先（Shortest Job First） ​

3. HRRN 高响应比优先（Highest Response Ratio Next） ​

4. 优先级调度 ​

5. RR 时间片轮转（Round Robin） ​

6. 多级反馈队列（Multilevel Feedback Queue） ​

7. 算法对比总表 ​

示例 ​

例 1：六种算法的完整计算 ​

（1）FCFS ​

（2）SJF（非抢占） ​

（3）SRTF（抢占） ​

（4）HRRN（非抢占） ​

（5）RR（q=1 / q=4） ​

例 2：SJF 与 HRRN 的分歧——"最优"与"公平"的取舍 ​

例 3：C 实现——FCFS / SJF / HRRN 的调度模拟 ​

例 4：Python——六种算法与指标全表验算 ​

考点 ​

小结 ​

我的笔记

评论（0）

处理机调度：调度算法与评价指标

概念

原理

一、三级调度及它们的分工

二、进程调度的时机（能调与不能调）

三、抢占式与非抢占式

四、评价指标（五个，公式必须默写）

五、七种调度算法

1. FCFS 先来先服务（First Come First Served）

2. SJF / SPF 短作业优先（Shortest Job First）

3. HRRN 高响应比优先（Highest Response Ratio Next）

4. 优先级调度

5. RR 时间片轮转（Round Robin）

6. 多级反馈队列（Multilevel Feedback Queue）

7. 算法对比总表

示例

例 1：六种算法的完整计算

（1）FCFS

（2）SJF（非抢占）

（3）SRTF（抢占）

（4）HRRN（非抢占）

（5）RR（ $q = 1$ / $q = 4$ ）

例 2：SJF 与 HRRN 的分歧——"最优"与"公平"的取舍

例 3：C 实现——FCFS / SJF / HRRN 的调度模拟

例 4：Python——六种算法与指标全表验算

考点

小结