概述

对磁盘发起I/O操作的时间主要由寻道时间和旋转时间决定，磁盘在不同时刻访问不同扇区的时间成本是不同的。当有多个I/O请求发出时,磁盘先服务哪个请求会极大地影响I/O性能。比如，当前磁头在内侧磁道上，有三个I/O请求分别访问内、中、外侧磁道上的扇区。显然，这种情况下自内向外处理请求比从外向内处理请求更加高效。

为了获得更高的I/O性能，磁盘必须对I/O请求进行调度。这些调度的主要依据是当前磁头的位置和要访问的扇区的位置信息。在早期的计算机系统中，磁盘调度由操作系统实现；在现代计算机系统中，磁盘调度算法被内置到磁盘中，磁盘利用内部的各种信息来完成磁盘调度。

磁盘的调度与进程的调度有相似之处，比如都追求高性能，都要考虑公平性，避免饿死的发生。但是磁盘调度与进程调度也有着明显的不同：进程的生命期是不确定的，而I/O操作的时间却可以被估算出来。所以我们自然地想到了SJF(shortest job first)的原则。

SSTF: Shortest Seek Time First

SSTF的思路非常简单，每次都先服务访问扇区所在磁道离磁头当前位置最近的请求。

SSTF易于实现，但是却存在明显的缺陷：

1. 公平性

SSTF总是先服务那些访问扇区所在磁道离当前磁头所在磁道最近的请求，很可能会出现某个I/O请求运气特别差，总是有别的请求比它更先被服务，最终导致饿死。想象一下，某个人在队伍最前面，但是接受服务的次序却不是按先来后到，每次它要接受服务时，都有别人合法地插队，明明他在最前面却无法接受服务。

2. 性能

SSTF只考虑到了寻道时间，却忽略了旋转时间，这种粗粒度的策略并不能实现接近最优的性能。

SPTF: Shortest Positioning Time First

SPTF从性能的角度改良了SSTF策略。每次确定要服务的I/O请求时，都计算访问各个请求扇区的时间，并服务其中耗时最短的请求。

SPTF策略同时考虑到了寻道时间和旋转时间，因此每次判断服务哪个请求都是综合判断的结果。

对于以下磁盘，分别有两个访问扇区8和扇区16的I/O请求。

在SSTF策略下，扇区16所在磁道距离磁头所在磁道最近，因此磁盘先服务访问扇区16的请求。但是这种决策既有可能不是最佳的。假如在这个磁盘中，旋转时间大于寻道实践，访问扇区8反而会是最好的选择。SPTF策略选择总体定位时间（寻道时间加旋转时间）最短的
I/O请求进行服务，在这里选扇区8。

Elevator(SCAN)

电梯算法（也叫SCAN）从处理I/O请求的公平性着手进行调度。在电梯算法中，磁头从最外侧磁道到最内侧磁道（反之）叫做一边扫描。

电梯算法的原理就蕴含在它的名字中：
电梯上上下下（磁头不断扫描），每次是否开门（服务I/O请求），取决于是否在该层是否有人要下电梯（该磁道是否有请求访问的扇区）。

每次扫描中，如果磁盘发现有请求访问的扇区在磁头所在磁道中，就访问该扇区，否则继续扫描。

电梯算法的基本原理相同,但却有许多变种，比如F-SCAN，C-SCAN。

F-SCAN

在磁头扫描的过程中，系统可能会像磁盘发起I/O请求，F-SCAN变种不处理这些新发起的请求，而将它们加入到等待队列中，在下一次扫描时再处理这些请求。

C-SCAN

在电梯算法中，一次扫描结束就进行下一次扫描。当一次扫描结束后，最简单的想法是从上一次扫描结束位置反方向扫描。比如，上一次从外到内，下一次就从结束位置（最内侧）向外扫描。
这种策略符合直觉，但是会导致一些“不够公平”，在中间的磁道被扫描的时间会比在两侧的磁道更长（这么说可能不太准确，总之中间的磁道会比两侧的更占优势）。

为了解决这个问题，C-SCAN策略确定了统一的扫描方向：从一端开始扫描，并在扫描结束后回到起始位置开始新一轮的扫描。

C-SCAN策略统一扫描方向带来了一些好处：

• 统一的等待时间
• 较小的响应时间

同时也导致了一些问题:

• 更多的寻道动作
• 即使没有I/O请求，磁头可能要进行寻道，除非已经待在特定的磁道。