常见磁盘调度算法总结

由于IO的高成本，操作系统在决定发送给磁盘的I/O顺序方面历来发挥作用，更具体的说，给定一组I/O请求，磁盘调度程序检查请求并决定下一个要调度的请求.

与任务调度不同，每个任务的长度通常是不知道的，对于磁盘调度，我们可以很好的猜测 “任务” 需要多长时间，通过估计请求的查找和可能的旋转延迟，磁盘调度程序可以知道每个请求将花费多长时间，因此选择先服务花费最少时间的请求. 因此，磁盘调度程序将尝试在其操作中遵循SJF的原则.（principle of SJF，shortest job first）

📖1. 最短寻道时间优先（SSTF）

一种早期的磁盘调度方法称为最短寻道时间优先(Shortest-Seek-Time-First, SSTF)，SSTF按磁道对I/O请求队列排序，选择在最近磁道上的请求先完成.

例如：假设磁头当前位置在内圈磁道上，并且我们请求扇区21（中间磁道）和2（外圈磁道），那么我们会首先发出对21的请求，等待它完成，然后发出对2的请求.

在这个例子中，SSTF运作良好，首先寻找中间磁道，然后寻找外圈磁道，但SSTF不是万能的，原因如下：

1. 主机操作系统无法利用驱动器的几何结构，而是只会看到一系列的块，但这个问题可以解决，操作系统可以简单的实现最近块优先(Nearest-Block-First)，然后用最近的地址块来请求调度.
2. 第二个问题更根本：饥饿问题. 如果有过多的内圈磁道请求，那么外圈磁道上的请求将得不到调度，产生饥饿.

SSTF总结：

• 优点：寻道时间最短
• 缺点：可能会造成饥饿（当某个请求的磁盘距离磁头较远，而一直有比其更近的请求时，这个请求一直无法执行）

📖2. 电梯算法（SCAN或C-SCAN）

该算法最初称为SCAN，简单的以跨越磁道的顺序来服务磁盘请求，我们将一次跨越磁盘称为扫一遍. 因此，如果请求的块所属的磁道在这次扫一遍中已经服务过了，它就不会立即处理，而是排队等待下一次扫一遍.

C-SCAN是一种SCAN的变体，即循环SCAN的缩写. 不是在一个方向扫过磁盘，该算法从外圈扫到内圈，然后从内圈扫到外圈，如此下去.

这种算法有时被称为电梯算法(elevator)，因为它的行为像电梯，电梯要么向上，要么向下，而不只根据哪层楼更近来服务请求，在磁盘中，它就防止饥饿.

📖3. 最短定位时间优先（SPTF）

在讨论最短定位时间优先之前（有时也称为最短接入时间优先），我们先来看一个例子，在这个例子中，磁头当前定位在内圈磁道上的扇区30上方. 因此，调度程序必须决定：下一个请求应该安排扇区16还是扇区8，接下来应该服务哪个请求.

答案是：“视情况而定”.

这里的情况是旋转与寻道相比的相对时间，如果在我们的例子中，寻道时间远远高于旋转延迟，那么SSTF就行，但是，如果寻道比旋转块的多，那么，在我们的例子中，寻道远一点的、在外圈磁道的服务请求8，比寻道近一点的、在中间磁道的服务请求16更好，因为16必须旋转很长的距离才能移到磁头下.

在现代驱动器中，正如上面所看到的，查找和旋转大致相当（当然，视具体的请求而定），因此 SPTF 是有用的，它提高了性能。然而，它在操作系统中实现起来更加困难，操作系统通常不太清楚磁道边界在哪，也不知道磁头当前的位置（旋转到了哪里）。因此，SPTF通常在驱动器内部执行.

📖4. 总结

在现代系统中，磁盘可以接受多个分离的请求，它们本身具有复杂的内部调度程序（它们可以准确地实现 SPTF.在磁盘控制器内部，所有相关细节都可以得到，包括精确的磁头位置）. 因此，操作系统调度程序通常会选择它认为最好的几个请求（如 16），并将它们全部发送到磁盘。磁盘然后利用其磁头位置和详细的磁道布局信息等内部知识，以最佳可能（SPTF）顺序服务于这些请求.

磁盘调度程序执行的另一个重要相关任务是I/O 合并（I/O merging）.

例如，设想一系列请求读取块 33，然后是 8，然后是 34，如文中的图所示. 在这种情况下，调度程序应该将块 33 和34 的请求合并为单个两块请求. 调度程序执行的所有请求都基于合并后的请求.合并在操作系统级别尤其重要，因为它减少了发送到磁盘的请求数量，从而降低了开销.