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。由此可以看出，FCFS 调度算法的平均作业周转时间与作业提交及调度的顺序有关。