时间片与优先级调度
复习
- 上下文切换：保存一个进程的现场，再恢复另一个
- 调度要解决什么：响应、吞吐、公平和优先级之间的矛盾
- 先来先服务与最短任务优先：简单调度为何会出现等待和饥饿
TL;DR
- 时间片轮转：每个进程只跑一小段，时间一到就换人，保证人人有份
- 时间片太小，切换开销大；太大，又退化成先来先服务
- 优先级调度：重要的先跑，但低优先级可能被饿死
- 老化：等得越久，临时提高优先级，防止长期挨饿
正文
先来先服务和最短任务优先，一个太“死板”，一个太“理想”。现实中的系统，既想让交互程序快速响应，又想让重要任务优先完成。于是有了两种更实用的思路：切小片轮着跑，以及按重要性排座次。
时间片轮转
时间片轮转（RR，Round Robin）的做法是：给每个进程一小段时间，叫一个时间片（time slice），让它跑；时间一到，无论跑没跑完，都强制换下一个，自己回到就绪队列的队尾。
A 跑一个片 │ B 跑一个片 │ C 跑一个片 │ A 再跑一个片 │ ……
这样，每个进程最多等“队伍长度 × 时间片”的时间，就能轮到自己。交互程序要的“响应快”，靠它来保证。
时间片的大小很有讲究：
- 太小：进程还没干多少活就被换下，切换开销占比变大，吞吐下降
- 太大：一个进程又要等很久才轮到，退化成先来先服务，响应变差
所以时间片要取一个折中值——通常远大于一次上下文切换的开销，又不至于让人明显感到卡顿。
优先级调度
可有些进程就是更“要紧”：负责接收用户输入的、负责网络通信的、系统的关键进程……时间片轮转一视同仁，对它们不够友好。
于是有了优先级调度：给每个进程一个优先级，优先级高的先上 CPU。同优先级之间，可以再用时间片轮转。
优先级有两种来路：
- 静态：一开始定好，运行中不变
- 动态：根据情况调整，比如刚用完 CPU 的降一点、刚等待完 I/O 的升一点
饥饿与老化
优先级调度有个老毛病：低优先级的进程可能一直排不上队。只要高优先级的任务源源不断，低优先级的就会一直等下去，这叫饥饿（starvation）。
解决办法叫老化（aging）：进程等待的时间越长，就慢慢把它的优先级抬一点。等得够久，再低的优先级也能熬出头，最终被调度一次。这样一来，“分轻重”和“够公平”之间就有了一条折中的路。
现实里的组合
真实的调度器，很少只用一种办法，而是把上面几招组合起来：优先级决定大致座次，时间片保证人人轮得到，老化兜住被冷落的进程。 调度的艺术，就在于把这些互相拉扯的目标，调到一个多数场景都满意的平衡点。
到这里，调度的基本招式就讲完了。可有心的读者会问：如果系统里有成千上万个进程，一个个比较优先级是不是太慢？还有一个更聪明的“反馈”办法。下一章，我们看多级反馈队列——它连“任务大概要跑多久”都不用事先知道。
思考题
时间片设成多大才合适？如果系统主要跑的是交互程序，你会倾向选大还是选小？如果主要跑的是批量计算任务呢？
小结
知识点
- 时间片轮转：轮流跑一小段，保证响应
- 时间片大小的权衡
- 优先级调度：重要的先跑
- 饥饿与老化
- 现实调度常把优先级、时间片、老化组合使用
参考资料
- Wikipedia(zh)：时间片：时间片轮转
- Wikipedia(zh)：优先级调度：优先级与老化
- Wikipedia(zh)：饥饿 (计算机科学)：进程饥饿
思考题答案（仅供参考）
时间片要足够大，能盖过一次上下文切换的开销，又不至于让等待的人明显感到卡顿。若主要跑交互程序，倾向选小一些：宁可多切换几次，也要让每次点击、按键都尽快有反应。若主要跑批量计算任务，倾向选大一些：这类程序对响应不敏感，少切换反而更省，吞吐更高。所以没有固定答案，要看系统主要面对什么样的负载。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪