cpu调度策略(1)

在谈调度策略前，我们先做一些假设。

1. 每个任务都运行相同的时间
2. 所有任务到达的时间都是一样的
3. 一旦运行了，任务就会运行到完成。
4. 所有的任务只占用cpu资源
5. 任务的运行时间是已知的
   这里的大部分假设都是不切合实际的，但是这个假设帮助我们更好的去理解和描述调度器。
   我们定义周转时间为完成时间减去任务到达时间。
   T_turnaround = T_completion - T_arrival

FIFO

最基本的调度算法就是先进先出FIFO模式，有时也被缩写成FCFS（先到先服务）。FIFO有一些优点：
非常简单所以容易实现。
假设所有的任务 A,B,C都大概同时到达系统,(T_arrival = 0)，具体时间A早于B，B早于C。假设每个任务都工作10秒，那么平均周转时间为(10+20+30)/3 = 20秒。
接下来我们去掉假设1，A运行100秒，B和C都是10秒。那么平均周转时间为(100+110+120)/3 = 110秒，周转时间比较高了。这个问题在于低消耗的任务排队到了高消耗的任务后面导致的。这个就导致我们想到了应该把低消耗的任务排在前面去。就是下面谈的SJF

SJF

上述的场景中，使用Shortest Job First (SJF)算法，那么B--C--A的顺序排序那么平均周转时间为(10+20+120)/3 =50。
基于假设，所有的任务都是同时到达的基础上，SJF的调度方法确实是个更好的优化算法。
接下来我们在放松假设2，任务可能在任何时候到达。假设A在t=0时到达并运行100秒，B和C分别在t=10时到达，并运行10秒。即使B和C任务更短，B和C还是必须等待A完成后才能执行。平均周转周期为(100+110-10 + 120-10) / 3 = 103.33秒。

STCF

我们在来放松假设3，调度器需要一些机制，时钟中断以及上下文切换。当B和C到达后，调度器会做些事情，会抢占A，然后决定运行一个其他任务然后在运行A。

把抢占模式加入SJF中后，产生了STCF算法。当有新任务到达系统后，STCF调度器会根据的剩下的所有任务哪个剩余时间最短就调度哪个。在我们的例子中会抢占A，运行B和C。平均周转周期为((120-0)+(20-10)+(30-10))/3 = 50秒。STCF是基于放松假设3的一个最好的优化。

一个新的衡量标准：响应时间

如果我们知道任务长度以及只是使用cpu这些假设，那么衡量标准就是周转时间，STCF就是个很好的策略。早期的批处理操作系统中，这类调度算法还是有意义。然而分时操作系统引入后，一切都改变了。因为需要交互，所以现在引入了一个新的衡量标准：响应时间。
定义响应时间为从任务第一次到达系统到第一次被调度的时间差。
T_response = T_firstrun - T_arrival
这种度量标准STCF也会有较差的响应时间。如果三个任务同时到达，最后一个任务需要等待前两个任务完全完成后才可以被调度到一次。然而很好的周转时间并不能带来很好的响应时间。

Round Robin

为了解决上述的问题，我们引入一个新的调度算法，传统上被称为Round Robin调度模式。RR运行一个任务一个时间片的时间，然后接着切换到队列中的下一个任务。调度器会重复这个过程，直到所有任务都完成。时间片的时间一定要是要是时钟中断的整数倍，如果每隔10ms时钟中断，那么时间片会是10,20或者其他整数倍于10ms。
时间片切的越小，响应时间就越短。但是如果时间片如果太短的话，上下文的切换的消耗就会影响性能了，因为不会不停的上下文切换。所以系统设计者会考虑一个折中的值，使得上下文切换的消耗和响应时间都能接受。
上下文切换的成本不仅仅是保存和恢复一些寄存器。当程序一直运行会有良好的状态，cpu cache，TLSB，分支预测以及其他硬件。当切换到其他程序后，这些状态都会被刷新掉，这会导致一些显而易见的性能消耗。
假设A，B，C同时到达，分别都运行5秒，时间片为1秒。在回到之前谈到的平均周转时间，在RR调度策略中，周转时间分别是13，14,以及15秒。平均周转为14秒。确实很糟糕。
如果衡量标准是周转时间，RR策略确实是个很差的方法。RR会延长把任务尽可能的延长，通过运行每个任务一小段时间然后切换到下一个。在度量周转时间上，RR甚至比FIFO还更差的一个策略。
RR牺牲周转时间换取响应时间，如果不想公平的话，那么就先运行短任务，但是代价就是响应时间。如果想公平的话，响应时间会很少，然后周转时间就会变大。这就是鱼和熊掌不可兼得啊。
我们已经有了低周转时间的策略（SJF，STCE）以及低响应时间的策略（RR）。我们仍然有2个假设还需要放开。假设4（任务没使用I/O）以及假设5（每个任务的运行时间是已知的）

合并I/O

我们首先放开假设4。假设一个程序没有输入，只产生输出。
当一个任务产生I/O请求时，调度器显然会采取一些措施，因为当前运行的程序在I/O期间不会在使用cpu了，中间会阻塞着等待I/O完成，完成后才会继续使用cpu。当I/O被发送到硬件驱动后，进程阻塞几毫秒甚至更长，因此调度器当然应该调度其他任务来运行了。
当I/O完成时，调度器同样会做一些决定。当I/O完成后，中断产生了，接着操作系统会把产生I/O并且阻塞的进程重新设置成就绪状态，甚至可以立马运行他。
为了更好的理解，我们假设有2个任务A和B，分别需要50ms的cpu时间。然而A运行10ms，然后产生个I/O请求（假设消耗10ms），B只是单纯的运行50ms，并没有任何I/O。调度器先运行A 然后在运行B。
假定我们使用STCF调度器，如果不允许重叠，就如图7.8所示，非常低的系统利用率。

一个通常的办法是把A的每个10ms运行的一个子任务当场一个独立的任务，使用STCF时，选择很明确的，每次选择A的子任务（10ms的子任务），在I/O等待期间在会运行B。通过允许重叠，这样会大大提高系统利用率。
此时，我们看到了调度器如何合并I/O。把任务划分成子任务时，cpu会更好保障交互式程序更频繁的运行着。当交互程序执行I/O时，cpu密集型的程序可以运行了，这样会提高系统利用率。

参考资料
http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched.pdf
http://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf