操作系统 - 先来先服务调度算法

---

---

在多道程序设计环境中，调度是由 CPU 执行的，用于决定下一个要执行的进程。这允许多个 CPU 进程同时存在，同时优化系统资源的使用以及执行时间。调度策略定义了一个从就绪队列中等待执行的进程中选择一个进程的过程。有各种各样的调度策略，其中最基本的一种是先来先服务 (FCFS) 调度算法。

FCFS 调度

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

FCFS 算法的主要特点

• FCFS 是一种非抢占式调度算法。
• 最先到达就绪队列的进程首先被分配执行。
• 实现简单，因为它不涉及任何复杂的算法。
• 它不需要任何关于进程的先验知识。此外，如果进程的运行时行为动态变化，对 FCFS 调度算法没有影响。
• 虽然这保证了公平的调度，但它可能导致单个进程的等待时间过长。

FCFS 调度的现实生活例子

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

FCFS 调度数学示例

在 CPU 调度问题中，解决问题时会使用一些术语，因此出于概念目的，这些术语将如下讨论 -

• 到达时间 (AT) - 到达时间是指进程到达就绪队列的时间。
• 突发时间 (BT) 或进程的 CPU 时间 - 突发时间是指特定进程完成执行所需的单位时间。
• 完成时间 (CT) - 完成时间是指进程终止的时间。
• 周转时间 (TAT) - 从到达时间到完成时间的总时间称为周转时间。TAT 可以写成，
• 等待时间 (WT) - 等待时间是指进程在等待分配时，前一个进程正在 CPU 中执行的时间。WT 写成，

周转时间 (TAT) = 完成时间 (CT) - 到达时间 (AT) 或 TAT = 突发时间 (BT) + 等待时间 (WT)

等待时间 (WT) = 周转时间 (TAT) - 突发时间 (BT)

• 响应时间 (RT) - 响应时间是指 CPU 首次分配给特定进程的时间。
• 在非抢占式调度的情况下，等待时间和响应时间通常相同。
• 甘特图 - 甘特图是一种可视化工具，有助于项目中特定任务的调度和管理。在解决调度问题时使用它，了解进程如何在不同算法中被分配。

问题 1

考虑下表，找到完成时间 (CT)、周转时间 (TAT)、等待时间 (WT)、响应时间 (RT)、平均周转时间和平均等待时间。

解决方案

甘特图

对于此问题，CT、TAT、WT、RT 显示在下表中 -

平均等待时间 = (9+8+0+4+12)/5 = 33/5 = 6.6 时间单位（时间单位可以视为毫秒）

平均周转时间 = (11+14+4+11+16)/5 = 56/5 = 11.2 时间单位（时间单位可以视为毫秒）

问题 2

考虑下表，找到完成时间 (CT)、周转时间 (TAT)、等待时间 (WT)、响应时间 (RT)、平均周转时间和平均等待时间。

解决方案

甘特图 -

对于此问题，CT、TAT、WT、RT 显示在下表中 -

平均等待时间 = (0+0+2+4+8)/5 = 14/5 = 2.8 时间单位（时间单位可以视为毫秒）

平均周转时间 = (2+1+5+9+13)/5 = 30/5 = 6 时间单位（时间单位可以视为毫秒）

*在空闲（非活动）CPU 期间，没有进程被安排终止，因此在此期间它会保持一段时间空闲。

FCFS 调度的优点

• 它易于实现，因为它不包含任何复杂的方式。
• 每个任务都应同时执行，因为它遵循 FIFO 队列。
• FCFS 不会优先考虑任何随机的重要任务，因此它是一种公平的调度。

FCFS 调度的缺点

• FCFS 会导致车队效应，这意味着如果突发时间较长的进程首先到达就绪队列，那么突发时间较短的进程可能会被阻塞，并且如果突发时间较长的任务永远占用时间，则突发时间较短的进程可能无法获得 CPU。
• 如果突发时间长的进程首先排队，那么其他突发时间短的进程必须等待很长时间，因此它对于分时系统来说不是很好。
• 由于它是不可抢占的，因此它不会在完全完成任务执行之前释放 CPU。

*车队效应和饥饿听起来很相似，但略有不同，因此建议不要将这两个术语视为相同的词。

结论

尽管 FCFS 易于实现和理解，但 FCFS 不适合交互式系统，并且在现代操作系统中未使用。可以使用其他 CPU 调度抢占式算法（如“轮转调度”）来防止 FCFS 中的车队效应。