磁盘寻道算法

Question

什么是磁盘调度

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。我们不妨将磁道由内向外进行编号 1，2，3...n。

常用的磁盘调度算法

常用的磁盘调度算法有以下四种：

FCFS（先到先服务）

这种算法最公平，谁先来谁就先被服务。但是相应地，其可能会出现排在后面的进程长期无法得到满足。另外，假如先来一个 1 号磁道的请求，然后是 n 号，然后又 1 号，这样效率就会很低，我们先处理完成 1 号的两个请求，再处理最号，实际上这就是我们接下来要讲的 SSTF（最短寻道时间优先）。

SSTF（最短寻道时间优先）

SCAN（扫描）

这种算法是在 SSTF（最短寻道时间优先）的基础上，我们增加一个考虑因素 当前磁头移动的方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。

CSCAN（循环扫描）

实际上，当我们从 1 号磁道，到达 n 号磁道的时候，这个时候 1 号磁道的请求应该会很多，因为我们刚刚响应过了 n 号磁道，其 n-1，n-2 相对来说请求比 1，2，3... 请求少。为了解决这个问题就发明了 CSCAN（循环扫描）。循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。