先来先服务 CPU 进程调度

算法。重要的概念名称是先来先服务。这是每个学生都必须学习以理解 CPU 进程调度算法所有基本知识的基础算法。

先来先服务为理解其他算法铺平了道路。该算法可能有许多缺点。但这些缺点催生了许多新的高效算法。因此，我们有责任了解先来先服务 CPU 进程调度算法。

FCFS 被认为是 CPU 调度算法中最简单的。在 FCFS 算法中，首先请求 CPU 的进程首先被分配到 CPU。FCFS 算法的实现由 FIFO（先进先出）队列管理。FCFS 调度是非抢占式的。非抢占式意味着一旦 CPU 分配给了一个进程，该进程就会一直持有 CPU，直到它执行完工作或任务并释放 CPU，或者通过请求 I/O 来释放 CPU。

FCFS 调度的现实生活示例

作为 FCFS 调度的现实生活示例，可以观察到购物中心的计费柜台系统。排在第一位的人先得到账单，然后下一个人才有机会得到账单并付款，依此类推。如果没有给 VIP 客户任何优先权，那么计费系统将继续这样运行（意味着排队中的第一个人（第一个任务）将先得到账单，并且在完成第一个客户的付款（执行）后，柜台人员（CPU）将关注其他客户（单独的任务），因为他们排队）。由于 FCFS 是非抢占式的，因此不会给随机重要任务任何优先权。

CPU 调度中使用的术语

• 到达时间：进程进入就绪队列的时间。
• 完成时间：进程完成执行的时间。
• 周转时间：完成时间和到达时间之间的时间差。周转时间 = (完成时间 - 到达时间)
• 等待时间 (W. T)：周转时间和突发时间之间的时间差。CPU 突发时间是进程所需的总 CPU 时间。

重要缩写

1. CPU - - - > 中央处理器
2. FCFS - - - > 先来先服务
3. AT - - - > 到达时间
4. BT - - - > 突发时间
5. WT - - - > 等待时间
6. TAT - - - > 周转时间
7. CT - - - > 完成时间
8. FIFO - - - > 先进先出

先来先服务

先来先服务 CPU 调度算法，简称 FCFS，是 CPU 进程调度算法的第一个算法。在先来先服务算法中，我们做的是允许进程按线性方式执行。

这意味着无论哪个进程首先进入就绪队列，都会被首先执行。这表明先来先服务算法遵循先进先出（FIFO）原则。

先来先服务算法可以以抢占式和非抢占式方式执行。在举例之前，让我们先了解一下 CPU 进程调度中的抢占式和非抢占式方法。

抢占式方法

在这种抢占式进程调度的情况下，操作系统会为进程分配资源一段时间。进程在资源分配期间从运行状态转换为就绪状态，或从等待状态转换为就绪状态。之所以发生这种切换，是因为 CPU 可能会为其他进程分配优先级，并用较高优先级的进程替换当前正在运行的进程。

非抢占式方法

在这种非抢占式进程调度的情况下，在进程完成运行之前，资源不能被撤销。当一个正在运行的进程完成并转换为等待状态时，会切换资源。

先来先服务 (FCFS) 中的队列效应

队列效应（Convoy Effect）是先来先服务 (FCFS) 调度算法中发生的一种现象。先来先服务调度算法以非抢占的方式发生。

非抢占方式意味着如果一个进程或作业开始执行，那么操作系统必须完成其进程或作业。在进程或作业完成之前，新的或下一个进程或作业不会开始执行。从操作系统的角度来看，非抢占式调度的定义意味着 CPU 将完全致力于第一个开始的进程或作业，并且只有在旧进程或作业完成后才会执行新的进程或作业。

可能存在一些情况，这些情况可能导致 CPU 分配过多时间。这是因为在先来先服务调度算法的非抢占式方法中，进程或作业是按顺序选择的。因此，由于这个原因，排在较大进程或作业后面的较短作业或进程需要很长时间才能完成其执行。由于这个原因，等待时间、周转时间和完成时间都会非常高。

因此，在这里，如果第一个进程很大或完成时间太高，那么就会发生先来先服务算法中的队列效应。

假设较长的作业需要无限时间才能完成。那么，剩余的进程将不得不等待相同的时间。由于较长作业造成的队列效应，等待进程的饥饿现象会急剧增加。这是 FCFS CPU 进程调度最大的缺点。

FCFS CPU 进程调度的特点

FCFS CPU 进程调度的特点是：

1. 实现简单。
2. 使用时不会造成任何事故。
3. 它采用非抢占式和抢占式策略。
4. 它按接收顺序运行每个过程。
5. 到达时间用作过程的选择标准。

FCFS CPU 进程调度的优点

FCFS CPU 进程调度的优点是：

1. 为了分配进程，它使用先进先出队列。
2. FCFS CPU 调度过程直接且易于实现。
3. 在 FCFS 抢占式调度情况下，进程不会发生饥饿。
4. 由于不考虑进程优先级，因此它是一种公平的算法。
5. 它是一种易于实现的算法，因为它不包含任何复杂的方法。
6. 每个任务都应该同时执行，因为它遵循 FIFO 队列。
7. FCFS 不会优先处理任何随机的重要任务，因此它是一种公平的调度。

FCFS CPU 进程调度的缺点

FCFS CPU 进程调度的缺点是：

• FCFS CPU 调度算法具有较长的等待时间
• FCFS CPU 调度优先考虑 CPU 而非输入或输出操作
• 在 FCFS 中，可能会发生队列效应
• 由于 FCFS 非常直接，因此通常效率不高。长时间的等待与之相伴。如果 CPU 忙于处理一个耗时的订单，那么所有其他订单都将处于空闲状态。
• FCFS 导致队列效应，这意味着如果一个突发时间较长的进程首先进入就绪队列，那么突发时间较短的进程可能会被阻塞，而突发时间较短的进程可能无法获得 CPU，如果突发时间较长的任务永远需要时间。
• 如果一个具有长突发时间的进程首先排队，那么其他短突发时间的进程将不得不长时间等待，因此它不像分时系统那样好。
• 由于它是非抢占式的，因此在完成任务执行之前，它不会释放 CPU。

实施

输入：进程及其突发时间 (bt)。
输出：所有进程的等待时间、周转时间。

1. 由于第一个到达的进程无需等待，因此进程 1 的等待时间为 0，即 wt[0] = 0。
2. 为所有其他进程 i.e. 进程 i 找到等待时间
   wt[i] = bt[i-1] + wt[i-1]。
3. 为所有进程找到周转时间= 等待时间 + 突发时间。
4. 找到平均等待时间= 总等待时间 / 进程数。
5. 类似地，找到平均周转时间= 总周转时间 / 进程数。

使用编程语言实现 FCFS 调度

C++ 代码

输出

Processes  Burst time  Waiting time  Turn around time
 1		7	 0		 7
 2		3	 7		 10
 3		1	 10		 11
Average waiting time = 5.66667
Average turn around time = 9.33333

计算平均等待时间

周转时间是进程完成请求所花费的时间。可以通过计算完成时间与到达时间之差来计算。

等待时间是进程在队列中等待执行的时间。周转时间与突发时间之差。所有等待时间之和除以进程数即为平均等待时间。

常见问题解答：-

1. FCFS 如何处理具有不同突发时间的进程？

FCFS 不考虑突发时间，因此先于短进程到达的长进程会导致短进程等待过久。这可能导致队列效应，显着增加平均等待时间。

2. FCFS 对缓存性能有何影响？

在 FCFS 中，进程按到达顺序执行，不考虑缓存局部性。如果具有大型工作集的进程替换了后续进程所需的缓存条目，则可能导致缓存未命中，从而导致内存利用效率低下。

3. 如何在 FCFS 中减轻队列效应？

• 实现优先级调度以优先处理较短的作业。
• 使用抢占式算法，如 SJF 或 RR，以防止长进程垄断 CPU。
• 引入老化技术，其中等待进程会随着时间的推移获得更高的优先级。

4. FCFS 如何处理具有相同到达时间的进程？

如果多个进程同时到达，FCFS 将选择队列中第一个出现的进程。如果顺序没有预定义，可能会导致行为不一致，从而影响吞吐量。

5. FCFS 在高系统负载下如何影响吞吐量？

在高负载下，FCFS 会显着降低吞吐量，因为长时间运行的进程会阻塞队列。短进程可能会不必要地长时间等待，导致 CPU 周期利用率不足。