操作系统——调度算法
作业调度算法
先来先服务调度算法（first-come first-served,FCFS）
FCFS是最简单的调度算法，既可以用于作业调度，也可以用于进程调度，系统将按照作业到达的先后次序来进行调度。
短作业优先调度算法（short job first,SJF）
SJF算法是以作业的长短来计算优先级，作业越短，优先级越高。作业的长短是以作业所要求的运行时间来衡量的。可以分别用于作业调度和进程调度。
缺点：
- 必须预知作业的运行时间
- 对长作业很不利，长作业的周转时间会明显地增长。可能使长作业等待时间过长，出现饥饿现象
- 在采用SJF算法时，无法实现人机交互
- 不能保证紧迫性作业能得到及时处理
优先级调度算法（priority-scheduling algorithm,PSA）
基于作业的紧迫程度的算法，由外部赋予作业相应的优先级，根据优先级进行调度，可以保证紧迫性作业优先运行。可以分别用于作业调度和进程调度。
高响应比优先调度算法（Highest Response Ratio Next,HRRN）
采用一种动态的优先级，优先级随着等待时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，就有机会获得处理机。优先级 = （等待时间 + 要求服务时间） / 要求服务时间
由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比Rp
Rp = （等待时间 + 要求服务时间） / 要求服务时间 = 响应时间 / 要求服务时间
进程调度算法
时间片轮转调度算法（round robin,RP）
原理：
在轮转(RR)法中,系统根据 FCFS 策略,将所有的就绪进程排成一个就绪队列,并可设置每隔一定时间间隔(如30 ms)即产生一次中断,激活系统中的进程调度程序,完成一次调度,将CPU分配给队首进程,令其执行。当该进程的时间片耗尽或运行完毕时,系统再次将CPU分配给新的队首进程(或新到达的紧迫进程)。由此,可保证就绪队列中的所有进程在一个确定的时间段内,都能够获得一次CPU 执行。
切换时机：
在RR调度算法中,应在何时进行进程的切换,可分为两种情况:
- 若一个时间片尚未用完,正在运行的进程便已经完成,就立即激活调度程序,将它从就绪队列中删除,再调度就绪队列中队首的进程运行,并启动一个新的时间片。
- 在一个时间片用完时,计时器中断处理程序被激活。 如果进程尚未运行完毕,调度程序将把它送往就绪队列的末尾。
时间片大小的确定：
在轮转算法中,时间片的大小对系统性能有很大的影响。 若选择很小的时间片,将有
利于短作业,因为它能在该时间片内完成。 但时间片小,意味着会频繁地执行进程调度和
进程上下文的切换,这无疑会增加系统的开销。 反之,若时间片选择得太长,且为使每个
进程都能在一个时间片内完成,RR算法便退化为FCFS算法,无法满足短作业和交互式用
户的需求。 一个较为可取的时间片大小是略大于一次典型的交互所需要的时间,使大多数
交互式进程能在一个时间片内完成,从而可以获得很小的响应时间。
多级反馈队列调度算法（multileved feedback queue）
前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的过程如下所述。
- 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。
当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。
仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。