如果第一个作业的突发时间在所有作业中最高, 则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 |
文章图片
【FCFS中的车队效应】平均等待时间= 6/3
推荐阅读
- 系统临界区问题
- 系统CPU调度
- 计数信号量
- 磁盘的连续分配
- 内存压缩
- 动态分区的位图
- 二进制信号量或互斥量
- 贝拉迪异常(Belady’s Anomaly)
- Win10系统组策略编辑器怎样打开?