第 3 章 · 处理机调度

调度 = 在多道程序间分配 CPU，目标是公平、高吞吐、响应快、周转短（常冲突，需取舍）。

指标：CPU 利用率、吞吐量、周转时间、等待时间、响应时间。批处理看重吞吐与周转，交互看重响应。

• 抢占式：可剥夺 CPU（现代系统主流）。
• 非抢占式：进程主动让出。

3.1 调度层次

层次	调度对象	频率	作用
作业调度（高级）	作业（外存→内存）	低	决定哪些作业进入内存
中级调度（内存）	进程（挂起↔就绪）	中	换入换出，调节内存压力
进程调度（低级）	就绪队列进程	高	决定 CPU 给谁，核心

低级调度频率最高，算法研究集中于此。

3.2 调度算法

设三个进程：P1 到达 0、运行 24；P2 到达 1、运行 3；P3 到达 2、运行 3。

• FCFS（先来先服务）：非抢占，按到达顺序。简单公平，但长进程在前短进程陪等（护航效应）。
• SJF/SRTF（短作业优先）：选运行时间最短（可抢占版 = 最短剩余时间优先）。平均等待最短，但长作业可能饿死，且需预知运行时间。
• 优先级调度：选优先级最高。低优先级可能饿死，用老化（aging）随时间提升优先级解决。
• 时间片轮转（RR）：就绪队列按 FCFS，每进程最多跑一个时间片 q，用完回队尾。响应快公平，但 q 太大退化 FCFS，q 太小切换开销暴涨。
• 多级反馈队列（MLFQ）：多级队列 + 时间片递增 + 抢占。新进程进最高级，用不完降到下一级；CPU 密集沉底，I/O 密集留高层。无需预知，兼顾响应与吞吐，Linux CFS 类似思想。

3.3 平均周转时间计算

对上面例子用 FCFS：

• 完成时间：P1=24，P2=27，P3=30。
• 周转时间（完成 − 到达）：P1=24，P2=26，P3=28。

$\text{平均周转时间}=\frac{24+26+28}{3}=26$

带权周转时间 = 周转时间 ÷ 运行时间：

$\text{平均带权周转时间}=\frac{\sum \frac{T_i}{r_i}}{n}$

用 SJF（非抢占）：P1 先到先占 CPU，之后选短的，结果同 FCFS——SJF 要占优，需「短进程先到」。

3.4 各算法优劣对比

算法	抢占	平均等待	响应时间	优点	缺点
FCFS	否	差	差	简单、无饿死	护航效应
SJF	可	最优	差	平均等待最短	长作业饿死、需预知
优先级	可	取决于策略	中	灵活	低优先级饿死
RR	是	中	好	公平、响应快	q 敏感、开销
MLFQ	是	好	好	兼顾，无需预知	实现复杂