在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把CPU 分配给队首进程,并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之,系统能在给定的时间内响应所有用户的请求。
12.4.2 多级反馈队列调度算法 前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法,仅照顾了短进程而忽略了长进程,而且如果并未指明进程的长度,则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间,而且还可以满足各种类型进程的需要,因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下所述。
(1) 应设置多个就绪队列,并为各个队列赋予不同的优先级。第一个队列的优先级最高,第二个队列次之,其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,为每个进程所规定的执行时间片就愈小。例如,第二个队列的时间片要比第一个队列的时间片长一倍,……,第i+1个队列的时间片要比第i个队列的时间片长一倍。
(2) 当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行;如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……,如此下去,当一个长作业(进程)从第一队列依次降到第n队列后,在第n 队列便采取按时间片轮转的方式运行。
(3) 仅当第一队列空闲时,调度程序才调度第二队列中的进程运行;仅当第1~(i-1)队列均空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时,又有新进程进入优先权较高的队列(第1~(i-1)中的任何一个队列),则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回到第i队列的末尾,把处理机分配给新到的高优先权进程。
高层建筑中电梯请求不断地到来,控制电梯的计算机能够很容易地跟踪顾客按下请求的顺序。如果使用先来先服务算法调度,同时如果电梯负载很重,那么大部分时间电梯将停留在电梯的中部区域,而电梯两端区域的请求将不得不等待,直到负载中的统计波动使得中部区域没有请求位置,这样导致远离中部区域的请求得到的服务很差。因此获得最小响应时间的目标和公平性之间存在着冲突。
大多数电梯使用电梯算法来协调效率和公平性这两个相互冲突的目标。电梯算法电梯保持按一个方向移动,直到在那个方向上没有请求位置,然后改变方向。
电梯算法(elevation algorithm)需要软件维护一个二进制位,即当前方向位:向上(up)或向下(down)。当一个请求处理完成之后,电梯的驱动程序检查该位,如果是up,电梯移至下一个更高的未完成的请求。如果更高的位置没有未完成的请求,则方向位取反。当方向位设置为down时,同时存在一个低位置的请求,则移向该位置。
现在我们明白了,电梯的上下箭头按钮是为了告诉电梯你想向上还是向下去),而不是让电梯向上还是向下。