2.4 进程调度算法

2.4.2 短作业优先

　　短作业优先（SJF）调度算法是指短作业或短进程优先调度的算法。短进程优先调度算法，是选择就绪队列中估计运行时间最短的进程进入执行。它既可采用抢占方式，也可采用非抢占方式。抢占的SJF算法通常也叫做最短剩余时间优先算法。SJF算法能有效地缩短作业的平均周转时间，提高系统的吞吐量，但不利于长作业和紧迫作业的运行。由于估计的运行时间不一定准确，因而它不一定能真正做到短作业优先。
　　例如，若有以下四个作业几乎同时到达系统并立即进入调度，如表2-2所示。

　　假设系统中没有其他作业，现对它们实施SJF 调度算法，这时的作业调度顺序为作业2、4、1、3，则：

平均作业周转时间T = (4+12+21+31)/4 = 17
平均带权作业周转时间W =(4/4+12/8+21/9+31/10)/4 = 1.98

　　如果对它们施行FCFS 调度算法，则：

平均作业周转时间T =(9+13+23+31)/4 = 19
平均带权作业周转时间W =(9/9+13/4+23/10+31/8)/4 = 2.51

　　由此可见，SJF 的平均作业周转时间比FCFS 要小，故它的调度性能比FCFS 好。但实现SJF 调度算法需要知道作业所需运行时间，否则调度就没有依据，作业运行时间只知道估计值，要精确知道一个作业的运行时间是办不到的。
　　SJF 算法是非抢占式的，可以改进成抢占式的调度算法。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业需要的CPU 时间比当前正在执行的作业剩余下来还需的CPU 时间短，抡占式短作业优先调度算法强行赶走当前正在执行的作业，这种方式叫最短剩余时间优先算法SRTF（Shortest Remaining Time First）算法。此算法不但适用于作业调度，同样也适用于进程调度。