先来先服务与最短任务优先
复习
- 进程控制块与进程状态：内核在哪里记录进程，以及三种状态的含义
- 上下文切换：保存一个进程的现场，再恢复另一个
- 调度要解决什么：响应、吞吐、公平和优先级之间的矛盾
TL;DR
- 先来先服务（FCFS）：按到达顺序排队，简单，但一个长任务会堵住所有人
- 最短任务优先（SJF）：先做预计最快的，平均等待时间最短
- SJF 的难点：事先并不知道任务要跑多久，还可能饿死长任务
正文
调度的第一层问题，是“选谁”。最自然、最符合直觉的两种选法，是先来先服务和最短任务优先。
先来先服务
先来先服务（FCFS，First Come First Served）就是排队买票：谁先到，谁先上；上了就一直跑，直到完成或主动让出。
它足够简单、足够公平——按到达顺序来，谁也挑不出毛病。但它有个要命的毛病：一个长任务，会把后面所有人堵住。
举个例子。三个任务几乎同时到达，分别要跑 1、1、10 个单位时间。若按这个顺序：
A(1) │ B(1) │ C(10)
等待：A=0，B=1，C=2，平均等待 ≈ 1
没问题。可如果长任务 C 偏偏排在前面：
C(10) │ A(1) │ B(1)
等待：C=0，A=10，B=11，平均等待 = 7
两个一眨眼就能完的小任务，硬生生被压在后面等了很久。这种现象叫护航效应：一个“大块头”霸着 CPU，后面一队“小船”只能干等。
最短任务优先
既然长任务挡路是问题所在，那就反过来：先做预计最快的。这就是最短任务优先（SJF，Shortest Job First）。
还是那三个任务，两个 1 和一个 10。不管谁先到，只要让两个短任务先跑，平均等待时间就是最小的：
A(1) │ B(1) │ C(10)
等待：A=0，B=1，C=2，平均等待 = 1
可以证明，在所有任务都同时到达的情况下，SJF 的平均等待时间是所有调度中最小的。这也是它最大的优点。
可惜，两个现实问题
SJF 好，但有两个绕不过去的问题：
- 怎么知道要跑多久？ 调度器手里只有一个准备运行的进程，它没法准确预知“这个进程还需要多少时间”。只能靠历史来猜，猜得准不准，全看运气。
- 长任务会被饿死。 只要短任务源源不断地来，长任务就一直排不上队——理论上的“平均最优”，换来的是个别进程的“永不执行”。这叫饥饿（starvation）。
抢占还是不抢占
上面的 SJF，默认是“一旦开始就跑完”，这叫非抢占。如果允许在更短的任务到来时打断当前任务，就叫抢占式。抢占能进一步降低平均等待，但代价是更多的上下文切换。
这两种朴素算法，一个赢在简单，一个赢在平均表现，却都照顾不好“交互体验”。现实中的系统，还需要更灵活的办法——让每个进程都能在短时间内轮上一圈。下一章，我们看时间片和优先级。
思考题
FCFS 的“护航效应”，和你生活里哪些排队场景很像？如果只能知道每个任务“大概要多久”，你会怎么决定先服务谁？
小结
知识点
- FCFS：按到达顺序，简单但可能产生护航效应
- SJF：最短的优先，平均等待时间最小
- SJF 不知道运行时间，且可能饿死长任务
- 抢占式与非抢占式的区别
参考资料
- Wikipedia(zh)：先来先服务：FCFS
- Wikipedia(zh)：最短作业优先：SJF
思考题答案（仅供参考）
超市只开一个收银台、前面的人买了一大车东西，后面的队伍就全卡住了，这很像护航效应；高速收费站只有一个窗口、前面一辆大货车，也一样。如果知道每个任务“大概多久”，一个朴素而有效的办法是：让快的先过，长任务则排在有快任务之后，同时给长任务一个“等待补偿”——等得越久，越优先，避免它被一直插队饿死。这正是“优先级加老化”的思路。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪