『面试问答』：常见的磁盘调度算法有哪些？

面试官： 请说一下，常见的磁盘调度算法有哪些？

在计算机系统中，各个进程可能会不断提出对磁盘进行读写操作的请求。由于这些进程的发送请求的速度可能比磁盘响应的速度还要快，因此，我们有必要为每个磁盘设备建立一个等待队列，磁盘调度算法通过优化磁盘的访问请求顺序来提高磁盘的访问性能。寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。

常见的磁盘调度算法有以下六种：

1 先来先服务算法

先来先服务算法根据进程请求访问磁盘的先后顺序进行调度，先到来的请求先被服务。先来先服务算法中每个进程请求都能依次得到处理，不会出现某一进程的请求长期得不到满足，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，在性能上就会显得很差，所以先来先服务算法适用于磁盘I/O进程数目较少的场合。

2 最短寻找时间优先算法

最短寻找时间优先算法每次优先选择从当前磁头位置所需寻道时间最短的请求。这种算法性能较好，但是可能产生饥饿现象，因为磁盘请求是一个动态的过程，可能会有距离磁头位置较近的请求不断过来，导致磁头在一小块区域来回移动，而距离磁头位置较远的请求一直得不到调度。

3 扫描算法

扫描算法是磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向。扫描算法也叫电梯算法，就好像电梯保持一个方向移动，直到在那个方向上没有请求为止，然后再改变方向。扫描算法性能较好，不会产生饥饿现象，但是每个磁道的响应频率不平均，因为它只有到达最内侧或者最外侧才可以改变磁头移动方向，导致中间部分相比其他部分响应的频率会比较多。

4 循环扫描算法

循环扫描算法只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。循环扫描算法使得每个磁道的响应频率基本一致，但是只有到达最边上的磁道时才会改变方向，效率还不够高。

5 LOOK算法

扫描算法中磁头只有移动到最内侧或者最外侧才能改变磁头方向，事实上有的时候最外侧已经没有请求了，这样就会造成时间的浪费。LOOK算法对扫描算法进行了优化，如果在某个方向上已经没有了请求，那么磁头可以直接改变方向。

6 C-LOOK 算法

循环扫描算法到达最边上的磁道时才能改变磁头方向，并且磁头返回时需要返回到最边缘的磁道上，C-LOOK算法对循环扫描算法进行了优化，如果磁头移动方向上已经没有请求时，就立即让磁头返回，并且磁头只需要返回到有磁盘访问请求的位置即可。