进程调度算法

2.4 进程调度算法2.4进程调度算法在早期的计算机系统中，调度大多数是非剥夺的；进程一直占用CPU直到进程阻塞或 终止。这种方法比较适用对于响应时间不关心或者关心甚少的批处理作业。在现代的交互 式系统中，使用剥夺调度，调度程序为了把CPU分配给另外的进程，可能在一个进程终止 或阻塞之前就剥夺其执行权。在一个交互的系统中剥夺是必需的，否则不需要I/O操作的 长进程会独占CPU，使得就绪队列中的进程没有机会响应它们用户的输入。当前，已有6 种进程调度算法已被广泛地使用。2.4.1先来先服务先来先服务（FCFS）调度算法是目前最简单的CPU调度算法。先来先服务调度算法 根据就绪队列，按进入的先后次序来分配处理机，这是一种不可抢占、非剥夺的调度方式 一旦一个进程占有处理机，就一直运行下去，直到该进程完成其工作，或因等待某一事件 而不能继续执行时，才释放处理机。采用这种进程调度方式，若一个运行时间长的作业先 占有了处理机，则会使很多晚到的、运行时间短的作业等待时间过长，引起许多短作业用 户的不满。因此，这种方式很少被用作主要调度策略，但它常作为一种辅助调度算法使用例如，表 2-1是三个作业几乎同时到达系统并立即进入调度。假设系统中没有其他作业，现采用 FCFS 算法进行调度，那么三个作业的周转时间分 别为：28、37和40,因此，平均作业周转时间T=（28+37+40）/3 = 35。若这三个作业调度顺序改为作业2、 1、 3，平均作业周转时间缩短为约29。如果三个 作业调度顺序改为作业3、 2、 1，则平均作业周转时间缩短为约18。由此可以看出， FCF S 调度算法的平均作业周转时间与作业提交及调度的顺序有关。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 = 198如果对它们施行 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)算法。此算法不但适用 于作业调度，同样也适用于进程调度。