FCFS 中的车队效应

当一个运行时间长、（具有显著突发时间）的活动或进程长时间占用 CPU 时，在调度算法中，尤其是在 FCFS（First Come First Serve，先来先服务）中，就会发生护航效应。这可能导致其他较短的进程被困在其后方就绪队列中，从而导致长时间的等待，甚至可能发生饿死。

在FCFS 调度下，进程按照它们到达就绪队列的顺序执行。如果一个具有显著突发时间的进程先到达，它将占用更多 CPU 时间，迫使后续较短的进程等待。护航效应类似于道路上的汽车护航：如果一队缓慢行驶的车辆堵塞了道路，后面的其他车辆将被延误。

护航效应可能需要进行修订，因为它与资源优化概念相悖。操作系统旨在最大化 CPU 利用率，同时保持进程的公平性。另一方面，当较短的进程被阻塞并等待一个长时间运行的操作时，护航效应可能导致资源利用不足。它可能导致更长的周转时间，并降低整体系统性能。

可以采用最短作业优先 (SJF) 或优先级调度等替代调度策略来减少护航效应。这些算法试图优先处理较短的进程，以减少较短作业的等待时间并避免饿死。然而，重要的是要认识到这些算法可能存在缺点和问题。

需要考虑的点

• 资源利用率： 在 FCFS 调度中，进程的优先级不基于执行时间。因此，一个长突发时间的进程可能会占用 CPU，从而减慢其他操作。CPU 需要更有效地利用，因为单个操作会长时间占用它。
• 等待时间： 稍后到达的较短进程可能具有比第一个长进程短得多的突发时间，并且执行速度快得多。然而，由于 FCFS 的性质，它们被排在长进程后面，导致更长的等待时间，并可能降低系统性能。
• 饿死： 虽然“护航效应”一词通常用来描述长时间运行的进程导致延误的情况，但需要强调的是，这也可能导致进程饿死。较短的进程可能会经历极长的等待时间，并要在长进程完成后才能运行。
• 性能： 护航效应有降低整体系统性能的潜力。虽然 FCFS 很简单，但它并不总是能实现最优的资源利用率或公平的进程处理。

为了避免 FCFS 调度中的护航效应，可以使用一种可以优先处理较短工作负载的抢占式调度方法。考虑最短剩余时间优先 (SRTF) 调度技术，它是最短作业优先 (SJF) 的抢占式变体。

使用 SRTF 调度克服护航效应

假设有三个进程 P1、P2 和 P3，它们的到达时间和突发时间如下：

• 进程 P1：到达时间 = 0，突发时间 = 40
• 进程 P2：到达时间 = 1，突发时间 = 3
• 进程 P3：到达时间 = 1，突发时间 = 1

将使用 SRTF（最短剩余时间优先）调度技术，在该技术中，每当有新进程到达或正在运行的进程完成其时间片时，CPU 就会切换到剩余突发时间最短的进程。

时间线

• 进程 P1 到达并开始执行。1 个时间单位后，P2 到达，突发时间为 3，因此 P1 被抢占。
• 进程 P2 开始执行。1 个时间单位后，P3 到达，突发时间为 1，因此 P2 被抢占。
• 进程 P3 开始执行，并在 1 个时间单位后完成。
• 进程 P2 恢复执行，并在 2 个时间单位后完成。
• 进程 P1 恢复执行，并在 40 个时间单位后完成。

计算

• 周转时间 (P1) = 完成时间 (P1) - 到达时间 (P1) = 44 - 0 = 44
• 周转时间 (P2) = 完成时间 (P2) - 到达时间 (P2) = 5 - 1 = 4
• 周转时间 (P3) = 完成时间 (P3) - 到达时间 (P3) = 3 - 1 = 2
• 等待时间 (P1) = 周转时间 (P1) - 突发时间 (P1) = 44 - 40 = 4
• 等待时间 (P2) = 周转时间 (P2) - 突发时间 (P2) = 4 - 3 = 1
• 等待时间 (P3) = 周转时间 (P3) - 突发时间 (P3) = 2 - 1 = 1

平均等待时间 = (4+1+1)/3= 2 单位

使用 SRTF 调度算法可以有效缓解护航效应。较短的进程得到优先处理，从而减少等待时间并提高资源利用率。在此场景中，平均等待时间为 2 个单位，远优于原始 FCFS 场景中具有护航效应的 27 个单位。

抢占式调度和护航效应缓解

抢占式调度方法对于最小化护航效应至关重要。它们允许操作系统暂停一个进程的执行，并切换到另一个具有较短突发持续时间的进程。这确保了较短的程序可以运行，防止较长的活动长时间占用 CPU。

• 带优先级队列的循环调度：这种方法将循环调度与优先级队列混合。调度程序根据每个进程的突发时间对其进行优先级排序，并在每个优先级级别内使用循环算法。此技术优先处理较短的程序，从而提高资源利用率。

优点

FCFS 中的护航效应有几个优点。FCFS 中护航效应的一些主要优点如下：

• 公平性： 抢占式调度确保所有进程，无论其突发时间如何，都有机会运行。它通过防止长进程饿死短进程来促进平等。
• 减少等待时间： 较短的进程可以更快地完成执行，从而缩短等待时间。这提高了系统性能和响应能力。
• 最优资源利用率： 抢占式调度允许 CPU 切换到较短的任务，从而优化了资源利用率。CPU 被有效地利用，从而提高了吞吐量。
• 缓解饿死： 由于调度程序优先处理较短的进程，它们遭受饿死的可能性较小。这可以防止长进程无限期地控制 CPU。

使用循环调度和优先级队列的示例

假设有三个进程：P1、P2 和 P3。您在每个优先级级别内构建了一种采用循环调度的抢占式调度方法。每个进程的优先级由其突发时间定义，较短的进程具有较高的优先级。此方法确保护航效应得到降低。

• 进程 P2 开始执行。1 个时间单位后，P3 到达，突发时间为 1，因此 P2 被抢占。
• 进程 P3 开始执行，并在 1 个时间单位后完成。
• 进程 P1 开始执行，并在 40 个时间单位后完成。
• 进程 P2 恢复执行，并在 2 个时间单位后完成。

平均等待时间：(1+0+1)/3=0.67 单位

SRTF 或循环调度与优先级队列的组合等抢占式调度算法通过优先处理较短的活动来缓解护航效应。这会导致更短的等待时间、更公平的待遇和更有效的资源利用率。该示例说明了抢占式调度策略如何提高系统性能并更有效地分配 CPU 时间。

用于护航效应缓解的动态时间片

在循环调度等抢占式调度算法中最小化护航效应的另一种方法是使用动态时间片。时间片是进程在被抢占并推到队列末尾之前可以运行的时间。动态时间片会根据当前进程的突发时间进行调整。较短的进程被分配较长的时间片，而较长的进程被分配较短的时间片。

时间片的工作原理

• 当一个突发时间短的进程到达时，它会被分配一个较长的时间片。这允许它在不被抢占的情况下相对较长时间地执行。
• 当一个突发时间长的进程到达时，它会被分配一个较短的时间片。这确保了长进程不会长时间垄断 CPU。

优点

• 适应性： 动态时间片会根据进程的特性进行调整。短进程可以在没有过多抢占的情况下完成执行，而长进程会被更频繁地抢占，以防止护航效应。
• 公平性： 该方法通过防止长进程延迟短进程来确保公平性。每个进程都能获得适当的 CPU 时间。
• 开销减少： 虽然纯粹的循环调度可能导致对短进程的不必要抢占，但动态时间片通过允许短进程更长的执行时间来减少此开销。

示例

假设有三个进程：突发时间为 40 的 P1，突发时间为 3 的 P2，以及突发时间为 1 的 P3。在循环调度中使用动态时间片

• P1 获得较长的时间片，以避免过多的抢占。
• P2 获得中等的时间片。
• P3 获得最短的时间片，以防止其造成延误。

这种动态调整确保了护航效应得到缓解，同时优化了资源利用率。

动态时间片是一种根据进程的突发时间调整分配给进程的时间片的方法。这种方法可以通过防止大型操作垄断 CPU 并允许较短的进程不间断地运行，从而显著减少护航效应。这是一种复杂的策略，结合了主动调度和定制的时间管理，可提高系统性能和公平性。

进程优先级

除了抢占式调度和动态时间片之外，进程优先级是限制护航效应的另一种方法。基于优先级的调度根据重要性、资源需求或特性等属性对进程进行优先级排序。较短的程序可以被赋予更高的优先级，确保它们尽快完成。此策略可以防止较长的操作干扰较短的操作，从而减少等待时间并提高整体系统响应能力。

现实世界中的例子

以超市结账队伍为例，说明护航效应。如果一位顾客有大量商品排在队伍最前面，那么其他商品较少的顾客可能会被延误。然而，如果超市为商品较少的顾客提供快速通道，那么每个人的等待时间都会缩短。同样，在调度中优先处理较短的进程可以产生更有效的队列，防止较长的进程造成延误。

抢占开销

虽然抢占式调度显著缓解了护航效应，但多次抢占可能会带来一些开销。每次进程被抢占时，都会产生与保存和恢复进程状态相关的上下文切换成本。此开销可能会影响系统性能，尤其是当时间片或抢占频率设置得太低时。在应用抢占式方法时，必须平衡抢占成本与减少护航效应的好处。

交互式进程与批处理进程

不同类型的进程在护航效应方面的行为可能不同。抢占式调度有利于需要频繁用户交互的交互式进程。另一方面，批处理进程可能具有较长的执行时间。然而，可以使用基于优先级的调度或动态时间片来优化它们，以避免阻塞较短的批处理操作。

策略组合

操作系统可以采用调度算法的组合来缓解护航效应并优化系统性能。例如，系统可以结合使用基于优先级的调度和动态时间片，以在公平性和有效的资源利用率之间取得平衡。