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

  1. 每个任务都运行相同的时间

  2. 所有任务到达的时间都是一样的

  3. 一旦运行了,任务就会运行到完成。

  4. 所有的任务只占用cpu资源

  5. 任务的运行时间是已知的

    这里的大部分假设都是不切合实际的,但是这个假设帮助我们更好的去理解和描述调度器。

    我们定义周转时间为完成时间减去任务到达时间。

    Tturnaround = Tcompletion - Tarrival

FIFO

最基本的调度算法就是先进先出FIFO模式,有时也被缩写成FCFS(先到先服务)。FIFO有一些优点:

非常简单所以容易实现。

假设所有的任务 A,B,C都大概同时到达系统,(Tarrival = 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就是个很好的策略。早期的批处理操作系统中,这类调度算法还是有意义。然而分时操作系统引入后,一切都改变了。因为需要交互,所以现在引入了一个新的衡量标准:响应时间。

定义响应时间为从任务第一次到达系统到第一次被调度的时间差。

Tresponse = Tfirstrun - Tarrival

这种度量标准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密集型的程序可以运行了,这样会提高系统利用率。

 

Multi-level Feed- back Queue (MLFQ) 图灵奖

Logo

更多推荐