SCAN 和 C-SCAN 算法

高效的磁盘调度对于优化操作系统性能至关重要，尤其是在处理大量 I/O 请求时。在众多旨在减少磁盘寻道时间的算法中，SCAN 和 C-SCAN 是两种流行的策略。它们的目的都是通过组织磁盘臂的移动方式来提高效率——无论是来回扫描（SCAN）还是圆形扫描（C-SCAN）。本文将展示这些算法的工作原理、它们的优点、缺点以及何时使用它们。

什么是磁盘调度？

磁盘调度是由操作系统使用的过程，用于决定如何服务磁盘 I/O（输入/输出）请求的顺序。当多个进程请求访问硬盘时，磁盘调度算法确定处理这些请求的最有效序列。

由于移动读/写磁头需要时间，磁盘调度的主要目标是减少寻道时间、提高吞吐量并最大化整体系统性能。

为什么磁盘调度很重要？

• 减少 I/O 请求的等待时间
• 提高用户和应用程序的响应时间
• 通过有效地组织磁头移动来提高磁盘利用率
• 防止低优先级或远程请求被饿死（在公平算法中）

SCAN 算法

SCAN 算法在磁盘臂向一个方向（高编号或低编号）移动时，服务沿途的所有请求。一旦它到达该方向的最后一个请求或磁盘的末端，磁头就会反转方向，并继续处理返回路径上的剩余请求。这种持续的移动方式使得 SCAN 也被称为电梯算法。

它也称为电梯算法。在此算法中，磁盘臂朝一个特定方向移动到末端，服务于沿途遇到的所有请求，然后掉头反向移动，服务于沿途遇到的请求。

它的工作方式类似于电梯，电梯会朝一个方向一直运行到该方向的最后一层，然后掉头返回。

SCAN 如何工作？

SCAN 磁盘调度算法通过在某个方向上移动磁盘的读/写磁头来工作，服务于位于其路径上的所有待处理 I/O。一旦磁头到达磁盘的末端或该方向的最后一个请求，它就会反转其方向并开始在相反方向上处理请求。这种方法会反复进行，进行一种类似于电梯工作的来回运动——因此得名电梯算法。

首先，确定磁盘磁头的当前位置和移动方向。磁头沿当前方向（高编号或低编号磁道）的柱面逐渐移动，检查并服务于与当前柱面匹配的任何请求。此扫描持续进行，直到该方向上没有其他请求，或者磁头到达外层磁道。

当磁头在一个方向上完成移动后，它不会停止。相反，它会反转方向并开始向相反方向移动，再次沿途服务请求。此反向扫描会一直持续到到达另一端，之后重复该过程。

由于 SCAN 在两个方向上都服务请求，因此确保了磁盘的所有区域都会定期得到访问，从而降低了发生饥饿的可能性。然而，在磁头刚刚经过的附近出现的请求可能需要等待更长时间，直到磁头在下一次扫描时返回。尽管如此，在 I/O 负载很高的系统中，SCAN 的性能优于先来先服务 (FCFS) 等简单算法，它在公平性和性能之间取得了良好的平衡。

示例

考虑一个具有 100 个磁道的磁盘的以下磁盘请求序列：

98, 137, 122, 183, 14, 133, 65, 78

磁头指针从 54 开始并向左移动。使用 SCAN 调度计算磁头移动的柱面数。

柱面数 = 40 + 14 + 65 + 13 + 20 + 24 + 11 + 4 + 46 = 237

SCAN 的优点

1. 减少寻道时间

SCAN 通过服务直到到达末端并反转方向，从而减少了总磁头移动。这减少了不必要的来回移动，与 FCFS 相比，平均寻道时间更短。

2. 公平性

每个请求最终都会被服务，因为磁头会扫描整个磁盘。这确保了任何请求都不会无限期等待，从而防止了饥饿。

3. 可预测的性能

规律的扫描模式使得 SCAN 的性能更易于预测。由于请求沿磁头路径按顺序处理，因此很容易估计待处理操作的响应时间。

4. 对高负载系统更有效

SCAN 比简单算法更有效地处理大量请求。其系统的移动方式有助于在队列很长或持续变化时保持稳定的性能。

SCAN 的缺点

1. 某些请求等待时间长

紧随磁头移动方向出现的请求可能需要等待磁头反转方向。这可能导致延迟，尤其是对于靠近磁盘边缘的请求。

2. 响应时间不均匀

SCAN 提供的性能优于 FCFS，但响应时间仍可能存在差异。靠近磁盘末端的请求可能比靠近中心的请求经历更长的等待时间。

3. 末端有浪费的移动

即使磁盘的极端末端没有请求，磁头在反转之前仍然会朝每个方向移动到那里。这可能导致不必要的磁头移动，从而稍微降低效率。

4. 对实时系统不理想

由于某些请求可能存在延迟，因此 SCAN 不是实时系统的最佳选择，因为实时系统需要一致且即时的响应时间。

C-SCAN 算法

C-SCAN（循环扫描）算法是磁盘调度方法的一个变体。与 SCAN 类似，它将磁盘磁头移动到一个方向以服务请求，但它不是在磁盘末端反转方向，而是跳回到磁盘的开头并以相同的方向继续服务。这确保了所有请求以一种均匀和循环的方式得到处理，从而提供了更一致的响应时间。

C-SCAN 的工作原理是：从当前磁头位置扫描到磁盘末端（通常是最低的柱面），沿途服务所有待处理请求。一旦磁头到达最后一个柱面，它不会在返回途中服务任何请求。相反，它会立即返回到磁盘的开始位置，并以相同的方向再次开始扫描。

在 C-SCAN 算法中，磁盘臂朝一个特定方向移动，服务请求，直到它到达最后一个柱面，然后它会跳到相反方向的最后一个柱面，而不服务任何请求，然后掉头并开始朝该方向移动，服务剩余的请求。

该算法将磁盘视为一个柱面的循环列表，这有助于维持均匀的等待时间。请求始终朝一个方向被服务，从而减少了 SCAN 在磁头反转时可能发生的响应时间变化。

C-SCAN 在磁盘 I/O 繁重的系统中特别有用，因为它提供了更好的公平性和更可预测的性能，尤其是在请求队列不断变化的情况下。然而，磁盘磁头的返回移动会增加总寻道时间，因为它在那个阶段不会处理任何请求。

C-SCAN 如何工作？

C-SCAN（循环扫描）算法的工作原理与 SCAN 类似，但在处理磁盘末端的方式上存在显著差异。当磁头到达最后一个磁道时，C-SCAN 不会反转方向，而是跳回到磁盘的开头，并以相同的原始方向继续服务请求。

最初，磁头朝一个特定方向移动——通常是从低编号磁道向高编号磁道。在移动过程中，它服务于路径上的所有待处理请求。一旦到达最高磁道编号，它在返回途中不会服务任何请求。相反，磁头会快速回到最低磁道，在此过程中不会停下来处理任何请求。

回到开头后，磁头会开始另一次向前扫描，以与之前相同的方向服务请求。这个过程以循环或圆形的方式持续进行，这就是为什么该算法被称为循环扫描。

始终朝一个方向扫描，C-SCAN 确保了更均匀的等待时间。与 SCAN 可能根据移动方向偏向某些请求不同，C-SCAN 为所有请求提供更一致和公平的体验，无论它们位于磁盘的哪个位置。

示例

考虑一个具有 100 个磁道的磁盘的以下磁盘请求序列：

98, 137, 122, 183, 14, 133, 65, 78

磁头指针从 54 开始并向左移动。使用 C-SCAN 调度计算磁头移动的柱面数。

穿过的柱面数 = 40 + 14 + 199 + 16 + 46 + 4 + 11 + 24 + 20 + 13 = 387

C-SCAN 的优点

1. 均匀的等待时间

C-SCAN 为所有请求提供更一致的响应时间。由于磁盘磁头始终沿一个方向移动并将磁盘视为圆形，因此磁盘的任何部分都不会比其他部分得到偏袒。

2. 公平性

所有请求都被平等对待，无论其位置如何。每个请求都需要等待一个完整的扫描周期，这可以防止饥饿并减少响应时间的不平衡。

3. 对高负载系统更有效

在请求数量庞大的 I/O 环境中，C-SCAN 通过避免不必要的来回移动来保持效率。其单向扫描模式有助于更可预测地管理长队列。

4. 可预测的性能

由于磁头移动始终沿同一方向，因此很容易预测请求何时会被服务。这种可预测性对于时间敏感型应用程序很有用。

C-SCAN 的缺点

1. 浪费的移动

C-SCAN 的主要缺点之一是，从磁盘末端返回的移动不会服务任何请求。这导致了额外的磁头移动，增加了总寻道时间。

2. 更长的平均寻道时间

与 SCAN 相比，C-SCAN 的平均寻道时间可能稍长，因为它总是跳回到开头，即使当前磁头位置后面还有待处理的请求。

3. 对低负载系统不理想

在磁盘请求负载较轻或不均衡的系统中，返回到开头的开销可能会抵消平均等待时间带来的好处，使得 C-SCAN 的效率较低。

4. 略显复杂

实施 C-SCAN 可能比 SCAN 稍微复杂一些，因为它需要处理循环跳转并保持仅沿一个方向的连续扫描的逻辑。

SCAN 与 C-SCAN 的比较

1. 磁头移动

SCAN 在朝向磁盘末端时，磁头在两个方向上都向前移动——第一次服务请求，然后反转方向，在返回途中服务请求。

另一方面，C-SCAN 的磁头仅沿一个方向移动。到达末端后，它会跳回到开头，在返回期间不服务任何请求。

2. 响应时间

SCAN 可能会导致响应时间不均匀，因为靠近磁盘末端的请求可能需要很长时间等待，尤其是在磁头反转之后。

C-SCAN 提供更均匀的等待时间，因为所有请求都以循环和一致的方式进行处理，从而提高了公平性。

3. 效率

SCAN 在总磁头移动方面略微更有效率，因为它在两个方向上都服务请求。

C-SCAN 由于需要不自然地从末端返回到开头，可能会导致稍多的磁头移动，但它提供了更好的可预测性和公平性。

4. 用例

SCAN 非常适合 I/O 请求相对均衡，并且性能比一致性更重要的系统。

C-SCAN 更适用于高负载或对时间敏感的系统，这些系统需要可预测且公平的响应时间。

5. 饥饿

两种算法都能防止饥饿，但 C-SCAN 在确保所有请求频繁获得服务方面做得更好，无论它们在磁盘上的位置如何。

常见问题解答

Q1：SCAN 和 C-SCAN 的主要区别是什么？

主要区别在于磁头的移动方式。SCAN 在两个方向（向前和向后）上都服务请求，而 C-SCAN 只在一个方向上服务请求，然后跳回到开头继续。

Q2：为什么 SCAN 被称为“电梯算法”？

SCAN 被称为“电梯算法”，因为磁盘磁头像电梯一样在磁盘上来回移动——在上上下下时在两个方向上服务请求。

Q3：哪个算法提供更均匀的等待时间？

C-SCAN 提供更均匀和可预测的等待时间，因为它将磁盘视为一个循环列表，并且始终在同一方向上服务请求。

Q4：SCAN 或 C-SCAN 会导致任何请求被饿死吗？

不会，SCAN 和 C-SCAN 都旨在防止饥饿。随着磁盘磁头继续扫描，每个请求最终都会得到服务。

Q5：哪个算法的平均寻道时间更好？

SCAN 通常具有稍好的平均寻道时间，因为它在两个方向上都服务请求，从而减少了不必要的磁头移动。然而，C-SCAN 在公平性和可预测性方面更好。