操作系统基础56-磁盘调度算法

2021-02-08 02:15·重学IT的老猫

操作系统的职责之一是有效使用硬件。对于磁盘驱动器，满足这个要求具有较快的访问速度和较宽的磁盘带宽。对于磁盘，访问时间包括两个主要部分：

寻道时间：是磁臂移动磁头到包含目标扇区的柱面的时间；
旋转延迟：是磁盘旋转目标扇区到磁头下的额外时间；

磁盘带宽是传输字节的总数除以从服务请求开始到最后传递结束时的总时间。通过管理磁盘 I/O 请求的处理次序，可以改善访问时间和带宽。每当进程需要进行磁盘 I/O 操作时，它就向操作系统发出一个系统调用。这个请求需要一些信息：

这个操作是输入还是输出；
传输的磁盘地址是什么；
传输的内存地址是什么；
传输的扇区数是多少；

如果所需的磁盘驱动器和控制器空闲，则立即处理请求。如果磁盘驱动器或控制器忙，则任何新的服务请求都会添加磁盘驱动器的待处理请求队列。对于具有多个进程的一个多道程序系统，磁盘队列可能有多个待处理的请求。因此，当一个请求完成时，操作系统可以选择哪个待处理的请求服务。操作系统如何进行选择？有多个磁盘调度算法可以使用。

FCFS 调度

磁盘调度的最简单形式当然是先来先服务(FCFS)算法。虽然这种算法比较公平，但是它通常并不提供最快的服务。例如，考虑一个磁盘队列，其 I/O 请求块的柱面的顺序如下：

98,183,37,122,14,124,65,67

如果磁头开始位于柱面 53，那么它首先从 53 移到 98，接着再到 183、37、122、14、124、65，最后到 67，磁头移动柱面的总数为 640。这种调度如图1所示。

图1 FCFS 磁盘调度

从 122 到 14 再到 124 的大摆动说明了这种调度的问题。如果对柱面 37 和 14 的请求一起处理，不管是在 122 和 124 之前或之后，总的磁头移动会大大减少，并且性能也会因此得以改善。

SSTF调度

在移动磁头到别处以便处理其他请求之前，处理靠近当前磁头位置的所有请求可能较为合理。这个假设是最短寻道时间优先(SSTF)算法的基础。 SSTF 算法选择处理距离当前磁头位置的最短寻道时间的请求。换句话说，SSTF 选择最接近磁头位置的待处理请求。对于上面请求队列的示例，与开始磁头位置(53)的最近请求位于柱面65。一旦位于柱面 65，下个最近请求位于柱面 67。从那里，由于柱面 37 比 98 还要近，所以下次处理37。如此，会处理位于柱面 14 的请求，接着 98，122，124，最后183(图2)。

图2 SSTF磁盘调度

这种调度算法的磁头移动只有236个柱面，约为FCFS调度算法的磁头移动总数的三分之一多一点。显然，这种算法大大提高了性能。 SSTF调度本质上是一种最短作业优先（SJF）调度；与 SJF 调度一样，它可能会导致一些请求的饥饿。请记住，请求可能随时到达。假设在队列中有两个请求，分别针对柱面 14 和 186，而当处理来自 14 的请求时，另一个靠近 14 的请求来了，这个新的请求会下次处理，这样位于 186 的请求需要等待。当处理该请求时，另一个 14 附近的请求可能到达。理论上，相互接近的一些请求会连续不断地到达，这样位于 186 上的请求可能永远得不到服务。当等待处理请求队列较长时，这种情况就很可能出现了。虽然 SSTF算法比FCFS算法有了相当改进，但是并非最优的。对于这个例子，还可以做得更好：移动磁头从 53 到 37（虽然 37 并不是最近的），再到 14，再到 65、67、98、122、124、183。这种策略的磁头移动的柱面总数为 208。

SCAN 调度

对于扫描算法，磁臂从磁盘的一端开始，向另一端移动；在移过每个柱面时，处理请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。SCAN算法有时称为电梯算法，因为磁头的行为就像大楼里面的电梯，先处理所有向上的请求，然后再处理相反方向的请求。下面回到前面的例子来说明。在采用SCAN来调度柱面98、183、37、122、14、124、65和67 的请求之前，除了磁头的当前位置，还需知道磁头的移动方向。

图3 SCAN磁盘调度

假设磁头朝0移动并且磁头初始位置还是53，磁头接下来处理37，然后14。在柱面0时，磁头会反转，移向磁盘的另一端，并处理柱面 65、67、98、122、124、183(图3)上的请求。如果请求刚好在磁头前方加入队列，则它几乎马上就会得到服务；如果请求刚好在磁头后方加入队列，则它必须等待，直到磁头移到磁盘的另一端，反转方向，并返回。假设请求柱面的分布是均匀的，考虑当磁头移到磁盘一端并且反转方向时的请求密度。这时，紧靠磁头前方的请求相对较少，因为最近处理过这些柱面。磁盘另一端的请求密度却是最多。这些请求的等待时间也最长，那么为什么不先去那里？这就是下一个算法的想法。

C-SCAN 调度

循环扫描(C-SCAN)调度是SCAN的一个变种，以提供更均匀的等待时间。像SCAN一样，C-SCAN 移动磁头从磁盘一端到磁盘另一端，并且处理行程上的请求。然而，当磁头到达另一端时，它立即返回到磁盘的开头，而并不处理任何回程上的请求(图4)。

图4 C-SCAN磁盘调度

C-SCAN调度算法基本上将这些柱面作为一个环链，将最后柱面连到首个柱面

LOOK 调度

正如以上所述，SCAN和C-SCAN在磁盘的整个宽度内移动磁臂。实际上，这两种算法通常都不是按这种方式实施的。更常见的是，磁臂只需移到一个方向的最远请求为止。遵循这种模式的SCAN算法和C-SCAN算法分别称为LOOK 和C-LOOK调度，因为它们在向特定方向移动时查看是否会有请求(图5)。

图5 C-LOOK 磁盘调度

磁盘调度算法的选择

给出了如此多的磁盘调度算法，如何选择最佳的呢？ SSTF是常见的，并且具有自然的吸引力，因为它比FCFS具有更好的性能。对于磁盘负荷较大的系统，SCAN和C-SCAN表现更好，因为它们不太可能造成饥饿问题。对于任何特定的请求列表，可以定义最佳的执行顺序，但是计算最佳调度的所需时间可能得不到补偿。然而，对于任何调度算法，性能在很大程度上取决于请求的数量和类型。例如，假设队列通常只有一个待处理请求。这样，所有调度算法都一样，因为如何移动磁头只有一个选择：它们都与FCFS调度一样。文件分配方式可以大大地影响磁盘服务的请求。程序读取连续分配文件时，生成多个相近位置的磁盘请求，导致有限的磁头移动。相比之下，链接或索引的文件可能包括分散在磁盘上的多个块，导致更多的磁头移动。目录和索引块的位置也很重要，因为每个文件必须打开才能使用，并且打开文件需要搜索目录结构，所以目录会被经常访问。假设目录条目位于第一个柱面，而文件数据位于最后柱面，在这种情况下，磁头必须移过整个磁盘的宽度。如果目录条目位于中间柱面，则磁头只需移过不到一半的磁盘。目录和索引块的内存缓存也有助于降低磁臂移动，尤其对于读请求。由于这些复杂因素，磁盘调度算法应该作为操作系统的一个单独模块，这样如果需要，可以用不同的算法来替换。SSTF或 LOOK是默认算法的合理选择。这里描述的调度算法只考虑了寻道距离，对于现代磁盘，旋转延迟几乎与平均寻道时间一样大。不过，操作系统很难通过调度来改善旋转等待延迟，因为现代磁盘没有透露逻辑块的物理位置。通过磁盘驱动器的控制器硬件内的磁盘调度算法，磁盘制造商一直在缓解这点。如果操作系统向控制器发送一批请求，那么控制器可以对这些请求进行排队和调度，以改善寻道时间和旋转延迟。如果I/O性能是唯一的考虑，则操作系统会乐意将磁盘调度责任转交到磁盘硬件。然而实际上，操作系统对请求服务的顺序还有其他限制。例如，按需调页比应用程序I/O具有更高的优先级，并且当缓存将要用尽可用页面时，写比读更重要。此外，可能需要保证一组磁盘写入的顺序，使得文件系统在系统崩溃时更加稳健。假设操作系统分配了一个磁盘页面给一个文件，应用程序将数据写入这个页面，但操作系统还没有机会来刷新文件系统的元数据到磁盘，想想可能发生什么。为了适应这种要求，操作系统可能会选择自己的磁盘调度，将请求按批次（或一个一个地，对于有的 I/O类型）交到磁盘控制器。