调度要解决什么

复习

进程的创建与结束：父子进程、退出状态和资源回收
进程控制块与进程状态：内核在哪里记录进程，以及三种状态的含义
上下文切换：保存一个进程的现场，再恢复另一个

TL;DR

调度要回答两个问题：下一个让谁跑？让它跑多久？
调度的目标彼此矛盾：响应快、吞吐高、够公平、分轻重
这些目标无法同时满足，只能权衡
没有“完美调度”，只有“适合某种场景的调度”

正文

　　就绪队列里排着一队进程，CPU 只有一个。该把 CPU 交给谁、交给它多久？这就是调度（scheduling）要解决的事。

　　听起来不过是从队伍里挑一个，可真正做起来，麻烦得很——因为我们想要的太多。

两个基本问题

　　任何调度策略，都绕不开两件事：

选谁：下一个运行哪个进程
跑多久：给它多长时间，之后要不要收回来

　　不同的回答方式，就构成了不同的调度算法。

四个互相打架的目标

　　我们希望调度做到下面这些事：

响应快：你点了按钮，界面立刻有反应
吞吐高：单位时间里，尽量多完成一些任务
够公平：每个进程都该有机会，不能有人一直排不上
分轻重：重要的任务（比如系统关键进程）应该优先

　　问题是，这四个目标经常互相拆台：

想让后台大任务“吞吐高”，它最好一口气跑完；可这样一来，前台小任务就得干等，“响应快”没了
想“够公平”，大家轮流跑；可“分轻重”又要求某些进程多占一些

　　想要面面俱到，往往哪一面都做不好。调度的本质，是在这些目标之间做取舍。

怎么衡量好坏

　　既然要取舍，就得有一套量尺。常用的有：

周转时间：从提交到完成一共花了多久
等待时间：在就绪队列里一共等了多久
响应时间：从提交到第一次有反应，隔了多久

　　不同的场景，看重的指标不同：批处理更在意吞吐和周转，交互系统更在意响应。

没有万能解

　　正因为目标互相冲突，调度领域里没有“一统天下”的算法。有的算法简单、公平，但一趟长任务就能把大家堵住；有的算法平均表现最好，却可能饿死个别进程。

　　理解了这些矛盾，再看后面几种具体算法，就会明白它们各自在“牺牲什么、换来什么”。先从最简单的两种说起。

思考题

　　“响应快”和“吞吐高”为什么经常打架？举一个你日常用电脑时能感受到的例子。

小结

知识点

调度回答“选谁”和“跑多久”
调度的目标：响应、吞吐、公平、优先级
这些目标彼此冲突，需要权衡
衡量指标：周转时间、等待时间、响应时间

参考资料

Wikipedia(zh)：调度：调度的基本问题
Wikipedia(zh)：排程：进程调度概述

思考题答案（仅供参考）

　　想让“吞吐高”，就希望一个任务尽量一气呵成地跑完，减少切换和等待；可这会让别的任务长时间得不到 CPU，交互操作就得干等，“响应”变差。反过来，为了“响应快”而频繁切换，又会让每次切换的开销累积起来，吞吐下降。例如一边下载大文件、一边敲字：下载希望占满带宽和磁盘，输入法却希望每个按键都被立刻响应。两者抢的就是同一份资源，天然的矛盾。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪