前文介绍的几个底层机制使得进程切换成为可能。
调度器 (scheduler) 所采用的高层策略则决定了 OS「选择哪个进程进行切换」。
调度指标
CPU 突发 (CPU burst)： 进程占用 CPU 的时间 $T_{burst}$。
周转时间 (turnaround time)，表征效率：$T_{turnaround}=T_{completion}-T_{arrival}$
响应时间 (response time)，表征公平：$T_{response}=T_{firstrun}-T_{arrival}$
等待时间 (wait time)：$T_{wait}=T_{turnaround}-T_{burst}$
FIFO
先进先出 (First-In-First-Out, FIFO) 策略。
车队效应 (convoy effects)：短进程可能被 CPU 密集型 (CPU-bounded) 进程阻塞，增大平均等待时间。
SJF
短任务优先 (Shortest-Job-First, SJF) 策略。
若所有任务的到达时间相同，SJF 策略最优。
非抢占式 (non-preemtive)：进程一旦开始运行就会一直占据 CPU 直到终止。导致车队效应。
长进程饥饿 (starvation)。
STCF
最短完成时间优先 (Shortest Time-to-Completion First, STCF) 策略。
SJF 的抢占式版本。
新到达的进程触发调度器，比较所有可运行进程（包括当前进程和新进程）剩余的执行时间，并切换到其中最短的那个。
若所有任务没有 I/O，STCF 策略最优。
RR
轮转 (Round-Robin, RR) 策略。
就绪队列中的每个进程依次按固定时间片 (time quantum) 轮流运行。就绪队列是 FIFO 的。
- 时间片一定是计时器中断周期的整数倍
交互式 (interactive) 进程希望尽量缩短响应时间，适用于 RR。
周转时间指标很差。
有 I/O 的任务
I/O 将任务的执行过程切分成多个 CPU burst。
当任务发起 I/O 时，它释放 CPU 并离开就绪队列；I/O 完成后，任务重新回到就绪队列，并准备继续执行下一个 CPU burst。
MLFQ
一个优秀的调度算法应该满足：
- 最小化交互式任务的响应时间
- 在没有关于任务的先验知识的情况下，最小化周转时间（学习算法？）
让我们见见 多级反馈队列 (Multilevel Feedback Queue, MLFQ) 策略。
MLFQ 维护多个优先级不同的就绪队列，其中优先级较高的队列时间片较小，较低的队列时间片较大。每个队列有一个时间额度 (time allotment)。
- 若 $\text{Priority}(A) > \text{Priority}(B)$，运行 $A$。
- 若 $\text{Priority}(A) = \text{Priority}(B)$，根据该队列的时间片大小使用轮转调度。
- 新任务进入最高优先级队列。
- 若一个任务用完了所在队列的时间额度，将其降低至下一个较低优先级队列。
- 以 $S$ 为周期将所有任务提升 (boost) 至最高优先级队列。
公平份额调度
公平份额调度 (fair share scheduling) 是进程组 (process groups) 级别的调度策略。
- 想要优先属于同一应用的多个进程？
- 多用户环境，保证每个用户所创建进程享有公平的份额？
彩票调度 (lottery scheduling)：恭喜这位中奖的进程！你可以来占用 CPU 了！
步长调度 (stride scheduling)
多处理器调度
单队列多核调度。
- 并发问题
- 处理器亲和性 (CPU affinity) 问题
多队列调度。
- 每个队列有自己的队列，新任务根据某个启发 (heuristic) 被分配给某个队列
- 队列间负载平衡：工作窃取 (work stealing)