图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK

时间:2024-05-22 07:54:19

一. FCFS 调度(先来先服务)

磁盘调度的最简单形式当然是先来先服务(FCFS)算法。虽然这种算法比较公平,但是它通常并不提供最快的服务。

例如,考虑一个磁盘队列,其 I/O 请求块的柱面的顺序如下:
98,183,37,122,14,124,65,67

如果磁头开始位于柱面 53,那么它首先从 53 移到 98,接着再到 183、37、122、14、124、65,最后到 67,磁头移动柱面的总数为 640。这种调度如图 1 所示。
图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK
从 122 到 14 再到 124 的大摆动说明了这种调度的问题。如果对柱面 37 和 14 的请求一起处理,不管是在 122 和 124 之前或之后,总的磁头移动会大大减少,并且性能也会因此得以改善。

二.SSTF调度(最短寻道时间优先)

在移动磁头到别处以便处理其他请求之前,处理靠近当前磁头位置的所有请求可能较为合理。这个假设是最短寻道时间优先(SSTF)算法的基础。

SSTF 算法选择处理距离当前磁头位置的最短寻道时间的请求。换句话说,SSTF 选择最接近磁头位置的待处理请求。

对于上面请求队列的示例,与开始磁头位置(53)的最近请求位于柱面 65。一旦位于柱面 65,下个最近请求位于柱面 67。从那里,由于柱面 37 比 98 还要近,所以下次处理 37。如此,会处理位于柱面 14 的请求,接着 98,122,124,最后183(图 2)。
图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK

这种调度算法的磁头移动只有 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 的请求之前,除了磁头的当前位置,还需知道磁头的移动方向。

图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK

假设磁头朝 0 移动并且磁头初始位置还是 53,磁头接下来处理 37,然后 14。在柱面 0 时,磁头会反转,移向磁盘的另一端,并处理柱面 65、67、98、122、124、183(图 3)上的请求。如果请求刚好在磁头前方加入队列,则它几乎马上就会得到服务;如果请求刚好在磁头后方加入队列,则它必须等待,直到磁头移到磁盘的另一端,反转方向,并返回。

假设请求柱面的分布是均匀的,考虑当磁头移到磁盘一端并且反转方向时的请求密度。这时,紧靠磁头前方的请求相对较少,因为最近处理过这些柱面。磁盘另一端的请求密度却是最多。这些请求的等待时间也最长,那么为什么不先去那里?这就是下一个算法的想法。

四. C-SCAN 调度(循环扫描)

对于扫描算法,磁臂从磁盘的一端开始,向另一端移动;在移过每个柱面时,处理请求。当到达磁盘的另一端时,磁头移动方向反转,并继续处理。磁头连续来回扫描磁盘。SCAN 算法有时称为电梯算法,因为磁头的行为就像大楼里面的电梯,先处理所有向上的请求,然后再处理相反方向的请求。

下面回到前面的例子来说明。在采用 SCAN 来调度柱面 98、183、37、122、14、124、65 和 67 的请求之前,除了磁头的当前位置,还需知道磁头的移动方向。

图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK
C-SCAN 调度算法基本上将这些柱面作为一个环链,将最后柱面连到首个柱面。

五. LOOK 调度

正如以上所述,SCAN 和 C-SCAN 在磁盘的整个宽度内移动磁臂。实际上,这两种算法通常都不是按这种方式实施的。更常见的是,磁臂只需移到一个方向的最远请求为止。

遵循这种模式的 SCAN 算法和 C-SCAN 算法分别称为 LOOK 和 C-LOOK 调度,因为它们在向特定方向移动时查看是否会有请求(图 5)。
图解五种磁盘调度算法, FCFS, SSTF, SCAN, C-SCAN, LOOK