调度
引入
词汇
| English | 释义 | 拼音 |
|---|---|---|
| FCFS | 先来先服务 | xiān lái xiān fú wù |
| SJF | 短作业优先 | duǎn zuò yè yōu xiān |
| round robin/raʊnd ˈrɒbɪn/ | 时间片轮转 | shí jiān piàn lún zhuàn |
| Gantt chart/ɡænt tʃɑːt/ | 甘特图 | gān tè tú |
| turnaround time | 周转时间 | zhōu zhuǎn shí jiān |
| waiting time | 等待时间 | děng dài shí jiān |
三种策略，一组作业
- 课程作业集：P1 = 7、P2 = 4、P3 = 1、P4 = 4，全部 0 时刻到达。先来先服务 FCFS 按序执行；短作业优先 SJF 先跑最短；时间片轮转 round robin（时间片 2）轮流切片——甘特图 Gantt chart 展示谁在何时运行。
{exercise:uni-cs0702-policies}
练习
课程作业集（0 时刻到达，突发 7、4、1、4）平均周转最低的策略是——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
SJF 平均 7.75，FCFS 11.5，RR 11.25。
公式与数字
- 周转时间 turnaround time = 完成 − 到达；等待时间 waiting time = 周转 − 突发。FCFS 完成 $7, 11, 12, 16$——平均周转 $11.5$。SJF（P3、P2、P4、P1）完成 $1, 5, 9, 16$——平均 $7.75$。
- RR（$q = 2$）顺序 P1 P1 | P2 P2 | P3 | P4 P4 | P1 P1 | P2 P2 | P4 P4 | P1 P1 | P1——完成 P3 $= 5$、P2 $= 11$、P4 $= 13$、P1 $= 16$：平均 $11.25$。同样作业、三个答案。
{exercise:uni-cs0702-numbers}
练习
FCFS 下该作业集完成于——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
先来先服务：累积 7、11、12、16。
护航与时间片
- 护航效应：FCFS 下 7 个时间单位的作业先到，P3 为 1 个单位的工作等 11 个单位——FCFS 对交互用户的标志性失败。
- 时间片选择：$q$ 太大退化成 FCFS；$q$ 太小把 CPU 耗在切换上——1 µs 切换在 2 ms 片里浪费 0.05%，在 20 µs 片里 5%。切换是开销，不是进展。
{exercise:uni-cs0702-quantum}
练习
1 µs 切换在 20 µs 时间片里浪费——
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
1 µs / 20 µs = 5%——片太小就把 CPU 花在切换上。