调度
调度策略
先做基本假设
- 每个工作运行相同的时间。
- 所有的工作同时到达。
- 一旦开始，每个工作保持运行直到完成。
- 所有的工作只是用CPU(无I/O操作)
- 每个工作的运行时间是已知的。
定义衡量指标。
- 周转时间。
= - - 响应时间。
= -
这2个指标其实是互相矛盾的，不同同时最优。
先进先出(FIFO)
又称为先到先服务(First Come First Served 或 FCFS)。
这种策略既简单又容易实现，在基本假设中，效果也挺好。
但是，如果去掉假设1， 问题就变得糟糕了。
譬如 A,B,C 同时到达，A运行100ms, B和C运行10ms, 平均周转时间就是(100+110+120)/3 = 110ms, B和C都被A给拖累了，这叫护航效应。
既然是被A给拖累了，那么后运行A就行了。譬如 A,B,C 同时到达，A运行100ms, B和C运行10ms, 平均周转时间就是(100+110+120)/3 = 110ms,
最短任务优先(SJF)
Shortest Job First。 很容易理解，谁运行的快，谁先运行，这样被拖累的效应最低。
但是如果去掉假设2， 问题又来了。
譬如 A 先到达,B,C 在10ms时到达，A运行100ms, B和C运行10ms, 平均周转时间就是(100+100+110)/3 = 103ms。
问题的根源在于长任务A已经运行了，B和C不得不等待。
解决的办法也很简单，中断任务A, 改成运行任务B不就行了。所以这里需要去掉假设3. 而现实中的操作系统恰恰支持暂停一个进程，运行另一个进程。
对应的策略是最短完成时间优先
最短完成时间优先(STCF)
Shortest Time-To-Completion First。
当新任务B到达时，发现A还需要90ms, B只需要10ms, 于是暂停A运行，改成B运行。
平均周转时间为 ( 120+10+20)/3 = 50ms, 缩短了103-50=53ms.
轮转
Round-Robin = RR.
前面的3个算法衡量的都是 平均周转时间。
但实际上对于终端运行程序，主要是人和计算机打交互，更看重的是最佳响应时间。
轮转算法就是每个任务运行一个时间片。
所以对于时间片的选择很重要：
- 时间片越小，响应时间越低。
- 时间片越小，用于上下文切换的时间越长，影响整体性能。
ps: 上下文切换的成本 不仅仅来自 保存和恢复少量寄存器的操作系统操作。程序运行时，它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。这些状态的刷新也会导致显著的性能成本。
结合I/O
去掉假设4，实际情况不可能没有I/O。
解决办法是 把有I/O 操作的任务切分成多个任务。
譬如任务A 没运行10ms CPU, 就需要运行10ms 的I/O. 一个需要运行50ms CPU。
那么把任务A 看成5个任务即可。
这样在A运行10ms的I/O时，CPU可以运行其他任务。
无法预知
来到第5个假设。好吧，这是最不现实的。未运行前谁都不知道任务要运行多久，而且任务本身就是动态的，和数据有关，运行时间也不固定。
有2类任务。1是运行时间相对固定的周期任务。2是运行时间不固定的。
操作系统可以统计信息，以便将来调度决策。