在对进程调度策略进行探讨之前,我们先进行一些简化假设,这些假设与系统中运行的进程有关,被称之为工作负载。
每一个工作运行相同的时间所有的工作同时到达一旦开始,每个工作保持运行直到完成所有工作只是用CPU每个工作的运行时间是已知的为了衡量不同调度策略的优劣,我们需要定义一个指标,它将在接下来的讨论中发挥重要的作用。现在,我们把周转时间作为我们的指标,它的定义如下:
T周转时间 = T完成时间 - T到达时间我们先在工作负载的假设下,举一个简单的例子。
假设有三个任务A、B、C,他们在同时到达系统,到达时间设为0(T到达时间=0)
因为FIFO需要有工作的先来后到,我们假设到达顺序是A->B->C。
再假设A、B、C都运行相同的时间10s。
由以上假设我们得出,A在10s时完成,B在20s时完成,C在30s时完成,周转时间分别为10s,20s,30s。
则这三个任务的平均周转时间为
(10+20+30)/3=20现在,我们放宽一下假设1
每一个工作运行相同的时间假设有三个任务A、B、C,到达时间和顺序不变。
A的运行时间为100s,B和C的运行时间为10s。
此时,只有A运行100s完成任务之后,才能运行B和C。
所以A的完成时间变为100s,B的完成时间变为100s+10s=110s,C的完成时间变为110s+10s=120s。
这时,这三个任务的平均周转时间为
(100+110+120)/3=110这样看起来,在理想状态下,FIFO策略还算合理,平均周转时间还在我们可以接受的范围内。
但是在非理想状态下,这样的平均周转时间相较于A的周转时间而言,是可以接受的,但相对于B和C的周转时间而言,却是难以忍受的。
这种问题被称为护航效应(convoy effert),一些耗时较少的潜在资源消费者被安排在重量级的资源消费者之后。
在现实生活中我们也会遇到这样的情况,比如在超市购物排队结账时,你的前面是一个装满三辆购物车的人在结账,而你自己却只拿着一瓶可乐,你的感受会如何?
我相信大多数人都会觉得,这种情况是不合理的,为什么不让东西少的人先结账呢?
当然,聪明的超市也会有种种方法解决这种问题,那在计算机中,我们会怎么解决这样的问题呢?
事实证明,一个非常简单的方法解决了这个问题。
实际上这是从运筹学中借鉴的一个想法,然后应用到计算机系统的任务调度中,这种调度准则被称之为最短任务优先。
我们用SJF策略重新处理之前的问题,按照最短任务优先的原则,三个任务的处理顺序应该为B->C->A。
所以B的完成时间变为10s,C的完成时间变为10s+10s=20s,C的完成时间变为20s+100s=120s。
则这三个任务的平均周转时间为
(10+20+120)/3=50现在,我们放宽一下假设2
所有的工作同时到达假设有三个任务A、B、C,A在 t = 0 时到达,且需要运行100s,B和C在 t = 10 时同时到达,且各需要运行10s。
此时,A先到达,运行10s之后,B和C同时到达,但A未运行完,只有等到A在100s完成任务后,B和C才能相继运行。
所以A的完成时间变为100s,B的完成时间变为100s+10s=110s,C的完成时间变为110s+10s=120s。
这时,这三个任务的平均周转时间为
(100+(110-10)+(120-10)/3=103.33显然,在理想状态下,较之之前平均周转时间为110s的FIFO策略而言,SJF策略表现得非常优秀。
在现实生活中,也有对SJF策略的应用,比如在大超市中通常有一个“零散购物”的通道,以确保仅购买了几件东西的购物者,不会被塞满几辆购物车的购物者堵在后面。
但是在非理想状态下,平均周转时间增加了1倍多,但由于到达时间的变化,又比之FIFO策略少,可是差距又微乎其微。
可以说,在非理想状态下,依然可以称之为是难以忍受的。
为了解决这个问题,需要放宽假设3
一旦开始,每个工作保持运行直到完成我们还需要调度程序本身的一些机制,我们知道,由于SJF策略是非抢占式的,所以A任务的运行直到完成前都不能被打断,导致了糟糕的周转时间出现。
所以,我们可以向SJF添加抢占来优化SJF,这种策略被称为最短完成时间优先(Shortest Time-to-Completion First,STCF)或
抢占式最短作业优先(Preemptive Shortest Job,PSJF)。
每当有新作业进入系统时,他就会确定剩余工作和新工作中,谁的剩余时间最少,然后调度该作业。
在之前的例子中,A在运行到10s时,B和C作业到达,STCF比较得知B的运行时间10s小于A的剩余时间(100-10)=90s,将抢占A运行B和C,待到他们完成后,才能调度A的剩余时间
所以B的完成时间变为10s+10s=20s,C的完成时间变为20s+10s=30s,C的完成时间变为30s+90s=120s。
这时,这三个任务的平均周转时间为
(120+(20-10)+(30-10)/3=50在使用了新的策略之后,平均周转时间与理想状态下的SJF策略一样。
可以说,在到达时间一样的情况下,SJF是最优的,但考虑到到达时间不同的情况,STCF是最优的。
那么,即使两者在最优情况下平均周转时间是一样的,但STCF的最优性是不言而喻的。
在之前的讨论中,我们发现,在知道任务长度,任务只使用CPU,而我们唯一的衡量是周转时间的情况下,STCF将是一个很好的策略。
事实上,对于早期的批处理系统,这些类型的调度算法有一定的意义。
然而,引入分时系统改变了这一切。
现在,用户将会坐在终端面前,他们要求系统的交互性好。
因此,一个新的度量指标诞生:响应时间(response time)
T响应时间 = T首次运行 - T到达时间在之前的例子中,响应时间分别如下:作业A为0,B为0,C为10,则平均周转时间为3.3。
可以想象,用户在终端前运行一个程序,却要等3.3秒后才能看到系统的回应,那用户的体验会多么的差,这样的交互性可以用糟糕来形容。
所以,我们又有了一个问题,如何构建一个对响应时间敏感的调度程序?
为了解决这个问题,我们将介绍一种被称为轮转(Round-Robin,RR)调度的调度算法。
RR会在一个时间片(time slice,有时被称为调度量子,scheduling quantum)内运行一个工作,然后切换到运行队列中的下一个任务,而不是运行一个任务直到结束,它反复执行,知道所有任务完成。
因此,RR有时被称为时间切片(time-slicing)。
时间片长度必须是时钟中断周期的倍数。
我们举一个例子,假设三个任务A、B、C在系统中同时到达,并且运行时间都为5s。
则SJF将顺序执行A->B->C,平均响应时间是(0+5+10)/3=5s,而1s时间片的RR可以快速循环工作,平均响应时间为(0+1+2)/3=1s。
显然,SJF在这个例子中,可以看作是时间片为5s的RR。
从中我们可以看出,时间片长度对于RR是至关重要的。越短,RR在响应时间上表现越好。
然而时间片太短也有问题,上下文转换需要成本,频繁的上下文转换将影响整体性能。
因此,系统设计者需要权衡时间片的长度,使其足够长,以便摊销上下文切换成本,而又不会是系统不及时响应。
例如,上下文切换时间为1ms,如果时间片设置为10ms,则会浪费10%的时间用于上下文切换;如果要摊销这个成本,可以把时间片设置为100ms,那么会有不到1%的时间用于上下文切换。
请注意,上下文切换的成本不仅仅来自保存和恢复少量寄存器的操作系统操作。
程序运行时,它们在CPU高速缓存、TLB、分支预测器和其他片上硬件中建立了大量的状态。
切换到另一个工作会导致此状态被刷新,且与当前运行的作业相关的新状态被引入,这可能导致显著的性能成本。
如果响应时间是我们的唯一指标,那么带有合理时间片的RR会是一个非常好的调度程序。
但是如果考虑到周转时间,那么RR的表现就不遂人意。
在上一个例子中,使用1s时间片的RR,平均周转时间将会达到可怕的14s。
如果周转时间是我们的指标,RR无疑是最糟糕的策略之一。
我们可以把至今讨论到的调度策略分为两类,RR是一类,它们优化响应时间,但对周转时间不利;SJF和STCF是另一类,它们优化周转时间,但对响应时间不利。从这两类中可以看出,周转时间和响应时间是难以双赢的两个指标,如何选择调度策略,则需要在两者中权衡,才能选出适当的策略。
现在,我们放宽假设4
所有工作只是用CPUI/O操作是很多程序避免不了的一个操作,当I/O操作发生时,正在运行的作业不会使用CPU。
所以,调度程序应该在此时向CPU安排另一项工作。
当I/O操作完成时,调度程序将发出I/O的进程从阻塞状态移回就绪状态,可以决定是否在此时切换到该进程继续运行。
我们可以举一个例子,假设有两个工作A、B,每项工作都需要50ms的CPU时间。但是,A每运行10ms,需要发出I/O请求(假设每次I/O需要10ms),而B不需要执行I/O。
调度程序先运行A,再运行B。
假设我们尝试构建STCF调度程序,我们应该如何考虑这样的情况呢?
一种常见的方法就是将A的每个10ms的子工作视为独立的工作,对于10ms的子工作和50ms的B,STCF会选择更短时间的子工作。
每两个10ms的子工作之间的I/O操作,视为CPU有10ms的空闲时间,这个时候CPU会调用B。
一次I/O操作完成时,会再次调用时间更少的子工作。
如此反复,直到最后A和B全部完成。
这样做可以实现重叠(overlap),一个进程再等待另一个进程的I/O完成时使用CPU,系统因此得到更好的利用。