操作系统基础21-先来先服务调度(FCFS)算法

操作系统基础21-先来先服务调度(FCFS)算法

2020-11-24 09:51·重学IT的老猫

作业、进程和程序之间的联系:

一个作业(job)通常包括程序数据操作说明书3部分。每一个进程PCB程序数据集合组成。这说明程序是进程的一部分,是进程的实体。因此,一个作业可划分为若干个进程来完成,而每一个进程有其实体——程序和数据集合

最简单的CPU调度算法是先来先服务(First-Come First-Served, FCFS)调度算法。釆用这种方案,先请求CPU的进程首先分配到CPU

操作系统基础21-先来先服务调度(FCFS)算法

假设有如下一组进程,它们在时间0到达,CPU执行长度按ms计:

操作系统基础21-先来先服务调度(FCFS)算法

如果进程按 P1、P2、P3 的顺序到达,并且按FCFS顺序处理,那么得到如下Gantt 图所示的结果(这种 Gantt 图为条形图,用于显示调度情况,包括每个进程的开始与结束时间):

操作系统基础21-先来先服务调度(FCFS)算法

进程P1的等待时间为 0ms,进程 P2 的等待时间为 24ms,而进程 P3 的等待时间为 27ms。因此,平均等待时间为 (0 + 24 + 27)/3 = 171ms。不过,如果进程按P2、P3、P1的顺序到达,那么结果如以下 Gantt 图所示:

操作系统基础21-先来先服务调度(FCFS)算法

现在平均等待时间为 (6 + 0+3)/3 = 3ms。这个减少是相当大的。因此,FCFS 策略的平均等待时间通常不是最小,而且如果进程的CPU执行时间变化很大,那么平均等待时间的变化也会很大。
另外,考虑动态情况下的FCFS调度性能。假设有一个CPU密集型进程和多个I/O密集型进程。随着进程在系统中运行,可能发生如下情况:CPU 密集型进程得到CPU,并使用它。在这段时间内,所有其他进程会处理完它们的 I/O,并转移到就绪队列来等待CPU。当这些进程在就绪队列中等待时,I/O设备空闲。最终,CPU密集型进程完成CPU执行并且移到I/O设备。所有I/O密集型进程,由于只有很短的CPU执行,故很快执行完并移回到I/O队列。这时,CPU空闲。之后,CPU密集型进程会移回到就绪队列并分配到CPU。再次,所有I/O进程会在就绪队列中等待CPU密集型进程的完成。由于所有其他进程都等待一个大进程释放CPU,故称之为护航效果。与让较短进程先进行相比,这会导致CPU和设备的使用率降低。
FCFS 调度算法是非抢占的。一旦CPU分配给了一个进程,该进程就会使用CPU直到释放CPU为止,即程序终止或是请求I/OFCFS 算法对于分时系统(每个用户需要定时得到一定的CPU时间)是特别麻烦的。允许一个进程使用CPU过长将是个严重错误。

参考资料:《操作系统概念 operating system concepts》

-------------本文结束 感谢阅读-------------