FCFS中的车队效应

如果第一个作业的突发时间在所有作业中最高, 则FCFS可能会受到车队的影响。与现实生活中一样, 如果车队正在通过这条路, 那么其他人可能会被挡住, 直到完全通过。这也可以在操作系统中进行模拟。
如果CPU在就绪队列的前端获得了较高突发时间的进程, 则突发时间较低的进程可能会被阻塞, 这意味着如果执行中的作业具有非常高的突发时间, 它们可能永远无法获取CPU。这称为车队效应或饥饿。

FCFS中的车队效应

文章图片
例子
在示例中, 我们有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
FCFS中的车队效应

文章图片
平均等待时间= 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
FCFS中的车队效应

文章图片
【FCFS中的车队效应】平均等待时间= 6/3

    推荐阅读