2.3.1 进程调度概述
本课核心知识点整理
本节导学
进程状态图告诉我们：就绪态的进程已经具备运行条件，只差 CPU。进程调度要解决的就是“就绪队列里有多个进程时，CPU 下一段时间给谁”。软件设计师题通常不只考概念，还会给出到达时间、服务时间，让你计算完成时间、周转时间、带权周转时间。
调度题的关键不是急着套公式，而是先把执行顺序画出来。执行顺序一错，后面所有完成时间和周转时间都会连锁错误。
调度发生在哪里
调度对象是就绪队列中的进程。阻塞进程还在等 I/O、资源或事件，即使给它 CPU 也不能运行；运行进程正在 CPU 上执行；只有就绪队列才是调度程序挑选下一个运行进程的地方。
单处理机系统中，同一时刻运行态通常只有一个进程。多个就绪进程之间如何排队，体现了调度算法的策略取舍：有的追求简单公平，有的追求平均周转时间，有的追求响应性。
常见调度算法
| 算法 | 要点 |
|---|---|
| 先来先服务 FCFS | 谁先到谁先执行，简单但短作业可能等很久 |
| 短作业优先 SJF | 优先服务时间短的作业，平均等待时间可能更小 |
| 优先级调度 | 按优先级选择，可能产生饥饿 |
| 时间片轮转 RR | 每个进程轮流获得时间片，适合分时系统 |
FCFS 的优势是规则简单、实现容易；缺点是长作业排在前面时，短作业可能等待很久。SJF 往往能降低平均等待时间，但长作业可能长期等不到机会。优先级调度表达能力强，但低优先级进程可能饥饿。时间片轮转牺牲一部分切换开销，换来更好的交互响应，适合分时系统。
性能指标怎么理解
- 周转时间 = 完成时间 - 到达时间。
- 等待时间 = 周转时间 - 服务时间。
- 带权周转时间 = 周转时间 / 服务时间。
周转时间描述一个进程从到达到完成总共经历了多久；等待时间描述它扣除真正运行时间后，在队列里等了多久；带权周转时间用“总耗时 / 自身服务时间”衡量相对等待程度，小作业如果等很久，带权周转时间会非常难看。
计算题路线
- 按题目算法确定执行顺序。
- 画时间轴，标出每段 CPU 给了哪个进程。
- 记录每个进程的完成时间。
- 用完成时间减到达时间，得到周转时间。
- 用周转时间除以服务时间，得到带权周转时间。
- 最后再求平均值。
不要把“服务时间”当成“周转时间”。服务时间是进程实际需要 CPU 的时间；周转时间包含等待、排队和执行的全过程。
与分时系统的衔接
前面特殊操作系统里提到分时系统，其核心就是把 CPU 时间切成时间片，让多个用户或任务轮流获得服务。时间片轮转算法就是这种思想在进程调度中的体现。时间片太长会接近 FCFS，响应性变差；时间片太短会导致频繁上下文切换，系统开销增加。
做题路线
- 问“调度从哪里选”，答就绪队列。
- 问算法特点，按 FCFS 简单公平、SJF 偏短作业、优先级可能饥饿、RR 适合分时记忆。
- 问计算题，先画时间轴，再算完成时间、周转时间、带权周转时间。
- 看到“时间片用完”，同时联想到运行态回就绪态。
例题
低级进程调度通常从哪里选择进程投入运行？
周转时间的计算公式是：
分时系统中常用、能让多个进程轮流获得 CPU 的算法是：
自查要点
- 调度为什么发生在就绪队列？
- FCFS 和 SJF 各有什么优缺点？
- 计算题为什么要先画时间轴？