FCFS中的车队效应

如果第一个作业的突发时间在所有作业中最高, 则FCFS可能会受到车队的影响。与现实生活中一样, 如果车队正在通过这条路, 那么其他人可能会被挡住, 直到完全通过。这也可以在操作系统中进行模拟。

如果CPU在就绪队列的前端获得了较高突发时间的进程, 则突发时间较低的进程可能会被阻塞, 这意味着如果执行中的作业具有非常高的突发时间, 它们可能永远无法获取CPU。这称为车队效应或饥饿。

在示例中, 我们有3个进程分别命名为P1, P2和P3。进程P1的Burt时间最高。

下表中的周转时间和等待时间由公式计算得出,

Turn Around Time = Completion Time - Arrival Time
		Waiting Time = Turn Around Time - Burst Time

在第一种情况下, 进程P1到达队列中的第一个；该进程的突发时间最高。由于调度算法是FCFS, 因此CPU将首先执行进程P1。

在此时间表中, 系统的平均等待时间将非常长。那是由于车队效应。尽管其他进程P2, P3的突发时间非常短, 但它们必须等待40单位时间的轮换。这个时间表饱受饥饿之苦。

进程ID	Arrival Time	Burst Time	Completion Time	周转时间	Waiting Time
1	0	40	40	40	0
2	1	3	43	42	39
3	1	1	44	43	42

平均等待时间= 81/3

在第二种情况下, 如果进程P1会到达队列的最后, 而其他进程P2和P3会更早到达, 那么饥饿的问题就不会出现了。

以下示例显示了两种情况下等待时间的偏差。尽管时间表的长度相同, 为44个单位, 但此时间表中的等待时间会更少。

进程ID	到达时间	Burst Time	完成时间	周转时间	等待的时间
1	1	40	44	43	3
2	0	3	3	3	0
3	0	1	4	4	3

平均等待时间= 6/3