C 语言 FCFS 调度程序

在 C 语言编程中，CPU 调度是操作系统领域的一个普遍概念，它决定了进程运行的优先级。先来先服务（FCFS）是迄今为止最简单、最公平的算法。它就像现实生活中的排队，先到的人先得到服务，比如在售票窗口排队。

先来先服务（FCFS）是一种非抢占式调度算法；也就是说，当一个进程已经在执行时，它不能被抢占，直到它完成。进程按照它们到达的顺序被放入队列中，最先进入队列的进程首先获得 CPU 时间。这是最简单的 CPU 调度算法，并为研究其他更高级的方法（如轮询（Round Robin）和最短作业优先（SJF））提供了基础。

为什么需要 FCFS 调度？

在 C 语言编程中，当系统追求简单、公平和可预测性而非速度或响应性时，就需要 FCFS 调度。当工作以自然的流程进入并且必须按照其进入的顺序进行处理时，它特别有效。它适用于以下几种情况：

• 批处理系统，其中所有任务都是已知的，并且不需要抢占。
• 基于 I/O 的环境，如打印队列或磁盘访问队列，其中请求按先来先服务的原则处理。
• 嵌入式或资源有限的系统，其中必须将开销降至最低。
• 教育用途，因为它让学习者能够理解 CPU 调度的主要概念，而无需处理优先级或时间片。

虽然 FCFS 在现代多任务处理的世界中不适用，但它适用于顺序比速度更重要的情境。

FCFS 调度算法

在这里，我们将逐步讨论 FCFS 调度算法。

1. 启动程序并输入要调度的进程总数。
2. 对于每个进程：
   1. 输入突发时间，即进程执行所需的时间。
   2. 假设所有进程都在时间 0 到达（或最初在时间 0 处于就绪队列中），并且这些进程将按 FIFO 顺序执行。
   3. 对于第一个进程，我们将其等待时间设置为零，因此该进程将立即开始执行。
3. 考虑所有其他进程（即从第二个到最后一个）：
   1. 通过将所有先前进程的突发时间相加来计算其等待时间。
   2. 这是当前进程在获得 CPU 时间之前所需的等待时间。
4. 对于每个进程：
   1. 周转时间计算为其突发时间和等待时间的总和。
   2. 周转时间 = 突发时间 + 等待时间
5. 通过对所有进程的单个值求和，计算总等待时间和总周转时间。
6. 通过将总等待时间除以进程数来计算平均等待时间。
7. 通过将总周转时间除以进程数来计算平均周转时间。
8. 呈现结果
   1. 进程 ID
   2. 突发时间
   3. 等待时间
   4. 周转时间
   5. 终止程序。

C 语言中的 FCFS 调度示例

让我们举一个例子来说明 C 语言中的 FCFS 调度。

输出

Enter the number of processes: 4
Enter burst time for each process:
P[1]: 5
P[2]: 3
P[3]: 8
P[4]: 6

Process	Burst Time	Waiting Time	Turnaround Time
P[1]			5		0			5
P[2]			3		5			8
P[3]			8		8			16
P[4]			6		16			22

Average Waiting Time: 7.25
Average Turnaround Time: 12.75

说明

在这个例子中，我们演示了先来先服务（FCFS）调度算法。首先，它提示用户输入多个进程的突发时间，然后计算每个进程的等待时间和周转时间。在这里，第一个进程的等待时间为 0，后续进程的等待时间根据先前进程的突发时间累积。最后，它显示各个进程的统计数据，并计算平均等待时间和周转时间。

FCFS 的特点

C 语言中 FCFS 调度的几个特点如下：

• 基于顺序的执行： 进程的执行按其进入的顺序进行。
• 非抢占式： 一个进程会一直运行直到完成。
• 公平： 没有优先进程，服务完全基于到达顺序。
• 可能导致饥饿： 长时间运行的作业可能导致较短的作业饥饿（称为护航效应）。
• 可预测： 它是确定性的，适用于实时系统中重要的情境。

FCFS 调度的优点

C 语言中 FCFS 调度的几个优点如下：

• 易于使用： FCFS 具有类似队列的结构，这意味着它是最容易编码和理解的调度算法之一。
• 公平性： 所有进程都被视为平等：按先来先服务的原则进行调度，没有偏好或优先。
• 无饥饿： 与基于优先级的算法不同，没有进程会被永远延迟。进程最终都会被执行到完成。
• 可预测性： 其确定性特性在行为相对容易理解且可以轻松建模的系统应用中是有利的。

FCFS 调度的缺点

C 语言中 FCFS 调度的几个缺点如下：

• 平均等待时间差： 先处理的较长进程的执行可能会导致后续的较小作业等待更长时间（护航效应），从而降低系统的响应性。
• 护航效应： 一个繁重（长突发时间）的进程能够拖慢队列中其后的所有进程。
• 不适用于时间敏感系统： FCFS 不允许抢占，因此它不是用于实时操作系统的理想选择，因为在实时系统中响应性和及时性都是关键因素。
• CPU 利用率低： 当一个进程正在进行 I/O 操作时，尽管队列中存在其他就绪进程，CPU 可能仍处于空闲状态。

FCFS 调度的实际应用

C 语言中 FCFS 调度的几个实际应用如下：

• 打印假脱机： 当多个打印作业被发送到打印机时，它们被放入队列中并按顺序打印。FCFS 是一种公平的调度方法，不会跳过作业。
• 银行排队系统： 在银行或 ATM 中，客户完全按照他们到达的顺序得到服务。没有人可以插队，这正是 FCFS 自然应用的场景。
• 磁盘调度（简单系统）： 在基本的磁盘 I/O 系统中，FCFS 可以用于顺序处理读/写请求，但当需要更高效率时，在高性能系统的情况下可以选择其他算法。
• 呼叫中心或服务台工单系统： 呼叫或支持请求按先来先服务的原则处理，因此最早的客户会得到支持，没有人会受到不公平的延迟。

结论

总之，FCFS 调度可能不是最高效的算法，但它清晰、公平且可预测。因此，它在操作系统领域是一个不可避免的概念。无论我们是在设计嵌入式系统的调度程序还是在建模 CPU 行为，都需要学习 FCFS 来控制进程。

给定的 C 程序证明了我们可以多快地应用 FCFS 并计算在实践中证明很重要的性能指标。尽管它可能不适用于时间敏感的情况，但 FCFS 仍然是理论和实践的坚实基础。

FCFS 调度程序常见问题解答

1) FCFS 调度与其他 CPU 调度算法有何不同？

在 C 语言编程中，FCFS（先来先服务）调度是一种非抢占式算法，它按进程到达的顺序执行，而不考虑突发时间或优先级。它的简单性使其易于实现和理解。然而，它可能导致资源利用率低和等待时间长，特别是当短进程排在长进程之后时（即“护航效应”）。

2) 在 C 语言中，FCFS 如何处理到达时间相同的进程？

在不同进程同时到达的情况下，FCFS 根据它们的列表或输入顺序来处理它们。它无法通过突发时间或优先级来内部解决冲突。两个进程中先输入的将首先执行。这保持了公平性，但如果顺序不佳，可能会导致更差的周转时间。

3) 是什么让 FCFS 不适合实时或交互式系统？

在 C 语言编程中，FCFS 缺乏抢占机制，无法快速处理紧急任务。如果一个长作业正在执行，短的或关键的任务就必须等待。这可能导致糟糕的用户体验或系统延迟。实时系统需要响应灵敏的算法。因此，FCFS 主要局限于更简单或后台的批处理系统。

4) 当进程具有不同的到达时间时，可以使用 FCFS 吗？

是的，如果进程在调度前按到达时间排序，FCFS 可以处理不同的到达时间。使用未排序的数据计算等待时间将不精确。排序后，可以正常计算等待时间和周转时间。处理到达时间会使实现变得稍微复杂一些。这使 FCFS 更接近于现实世界中任务的处理方式。

5) 在 C 语言中，FCFS 如何影响 CPU 利用率和吞吐量？

FCFS 可能导致 CPU 利用率不佳，特别是当长工作进程在等待 I/O 时。由于进程是顺序运行的，CPU 可能会不必要地保持空闲。短进程会被长进程阻塞，从而降低整体吞吐量。它的顺序性限制了系统在高负载时的性能。高吞吐量操作更适合使用更动态的算法。