FCFS 调度算法：什么是示例程序
纳撒尼尔·布鲁克斯
什么是先到先得方法？
先到先得 (FCFS) 是一种操作系统调度算法，它自动按照到达顺序执行排队的请求和进程。它是最简单、最容易的 CPU 调度算法。在这种类型的算法中，首先请求 CPU 的进程首先获得 CPU 分配。这是通过 FIFO 队列进行管理的。FCFS 的全称是先来先服务。
当进程进入就绪队列时，它的PCB（进程控制块）与队列的尾部相链接，当CPU空闲时，应该将其分配给队列开头的进程。
FCFS 方法的特点
- 它支持非抢占和抢占调度算法。
- 工作总是按照先到先得的原则执行。
- 它易于实施和使用。
- 这种方式性能较差，一般等待时间比较长。
FCFS 调度示例
FCFS 方法的一个现实示例是在售票柜台购买电影票。在此调度算法中，按照排队方式为人们提供服务。队列中第一个到达的人首先购买票，然后购买下一张票。这将一直持续到队列中的最后一个人购买票。使用此算法，CPU 进程以类似的方式工作。
FCFS 如何工作？计算平均等待时间
以下是五个进程在不同时间到达的示例。每个进程都有不同的突发时间。
| 流程 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
使用FCFS调度算法，这些进程处理如下。
步骤1） 该过程从 P4 开始，到达时间为 0
步骤2） 在时间=1时，P3到达。P4仍在执行。因此，P3被保留在队列中。
| 流程 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤3） 在时间 = 2 时，P1 到达并保存在队列中。
| 流程 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤4） 在时间=3时，P4进程完成执行。
步骤5） 在时间=4时，队列中第一个 P3 开始执行。
| 流程 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤6） 在时间=5时，P2到达，并且被保存在队列中。
| 流程 | 爆发时间 | 到达时间 |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
步骤7） 在时刻 11，P3 完成执行。
步骤8） 在时间=11时，P1开始执行。它的突发时间为6。它在时间间隔17处完成执行
步骤9） 在时间=17时，P5开始执行。它的突发时间为4。它在时间=21时完成执行
步骤10） 在时间=21时，P2开始执行。它的突发时间为2。它在时间间隔23处完成执行
步骤11） 让我们计算一下上述例子的平均等待时间。
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5= 17-4 = 13
P2= 21-5= 16
平均轮候时间
= 40/5= 8
FCFS 的优点
以下是使用 FCFS 调度算法的优点/好处：
- 最简单的形式 CPU 调度算法
- 易于编程
- 先到先得
FCFS 的缺点
以下是使用 FCFS 调度算法的缺点/缺点：
- 它是一种非抢占式 CPU 调度算法，因此在进程被分配给 CPU 之后，它永远不会释放 CPU，直到它执行完毕。
- 平均等待时间很长。
- 位于队列后面的短进程必须等待位于队列前面的长进程完成。
- 对于分时系统来说，这不是一个理想的技术。
- 由于其简单性，FCFS 效率不高。
结语
- 定义：FCFS 是一种操作系统调度算法，它自动按照到达的顺序执行排队的请求和进程
- 支持非抢占式和抢占式调度
- 算法。
- FCFS 代表先来先服务
- FCFS 方法的一个现实生活例子是在售票柜台购买电影票。
- 它是 CPU 调度算法的最简单形式
- 它是一种非抢占式 CPU 调度算法，因此在进程被分配给 CPU 之后，它永远不会释放 CPU，直到它执行完毕。
