FCFS、SSTF、SCAN、CSCAN磁盘调度算法

三个疑问，什么是磁盘调度算法？它又有什么作用呢？常见的磁盘调度算法又有哪些呢？

1、什么是磁盘调度算法
磁盘调度算法，顾名思义是计算机操作系统中用于优化磁盘I/O（输入/输出）操作的一类算法。那什么是磁盘呢，磁盘就是计算机系统中常用的数据存储设备之一,那为什么要给它研究算法呢，因为计算机在对磁盘进行读写操作时，磁头的寻道和定位过程是相对耗时，因此，研究了磁盘调度算法，为的就是优化磁盘I/O的性能，减少磁头的寻道时间同时提高磁盘的效率。

2、那研究出来的作用是什么呢

1. 减少寻道时间： 磁盘调度算法的主要目标之一是减少磁头的寻道时间。寻道时间是指磁头从当前磁道移动到目标磁道的时间，而有效的磁盘调度可以使磁头在移动时经过的磁道尽可能地有序，从而降低寻道时间。
2. 提高磁盘性能： 通过降低磁头的寻道时间和最小化旋转延迟，磁盘调度算法可以提高磁盘的读写性能，从而加快数据访问速度。
3. 公平性： 一些磁盘调度算法还考虑了对磁盘上的不同任务的公平分配，以确保各个任务在进行磁盘I/O时都能够获得相对公平的服务。

3、常见的磁盘调度算法有哪些

• 先来先服务算法（FCFS）： 按照请求的到达顺序进行服务，简单但可能导致”电梯”效应。
• 最短寻道时间优先算法（SSTF）： 选择距离当前磁头位置最近的磁道进行服务，可以减少寻道时间，但可能导致某些请求长时间等待。
• 扫描算法（SCAN）： 磁头按照一个方向移动，直到到达磁盘的边缘，然后反向移动。可以减少寻道时间，但不够公平，可能导致一些请求长时间等待。
• 循环扫描算法（C-SCAN）： 类似于扫描算法，但当磁头到达磁盘的边缘时直接返回到最外圈，形成一个循环。减少寻道时间，对所有请求更公平。

下面我们来一一介绍这些算法

1、先来先服务算法（FCFS）顾名思义就是按照磁盘I/O请求的到达顺序进行服务。即，先到达的请求先被执行。如一个请求队列顺序为[55、58、39、18、90、160、150、38、184]，从100号磁道开始

如在上图中，可看到顺序是与队列顺序是一致的，即先来先服务（注：磁道号是越往内越大，因此此时可把比100号大的包括100称为内道，把比100号小的称为外道）

2、最短寻道时间优先算法 (SSTF) 顾名思义就是选择距离当前磁头位置最近的磁道进行服务。下面用上面的例子来分析一下，SSTF是从距离磁头位置最近的开始访问（即100号磁头所在位置），那我们拿那队列的数依次来和当前磁头所在位置来进行距离比较，从最近的开始排，如第一个最近的是90，相差10，然后磁头来到90的位置，其次离最近的就是58，相差32，此时磁头来到58，同理再依次比较下去，能得到[90，58，55，39，38，18，150，160，184]这个队列，再来看其实际执行过程

从上图中可看到确实是按上述如此执行的

3、扫描算法 (SCAN) 也名为电梯调度算法，因为它就像电梯一样，到底了就往上走，到顶了就往下走，实际上也是这样的，就是磁头按照一个方向移动，直到到达磁盘的边缘，然后反向移动。下面也用上面的例子分析一下执行过程，我们在上面第一个FCFS算法的分析中，已经说了磁道号是越往内越大，因此此时可把比100号大的包括100称为内道，把比100号小的称为外道，在这基础上，有一个初始条件，就是磁头一开始就向磁道号增加的地方行进，那么就有从100开始，先访问磁道号比它大的150，再160，再184，然后发现到顶了，因为比它大的数已经没有了，之后就开始逐次往外道走，90，58，55，39，38，18直到到达最外道停止。

从上图可知执行过程确实如此像电梯一样。

4、循环扫描算法 (C-SCAN) 其很类似于扫描算法，唯一不同就是当磁头到达磁盘的边缘时直接返回到最外圈，形成一个循环（注：该算法规定磁头单向移动），同理，我们也用上面的例子来分一下，此时磁头初始也是向磁道号增加的地方行进，那么就有首先到150，再到160，再到184，然后发现到顶了，没有更大的号数了，此时，就会跳转到磁盘最外圈（即号数最小的哪一个磁道），然后继续向磁道号增加的方向进行。那么就会再有[18，38，39，55，58，90]

据上图，确实是到达磁盘边缘就跳转到最外盘

那么对比这几种算法，你会发现它们的优缺点

1. 先来先服务算法 (FCFS):

– 优点： 简单，易于实现。
– 缺点： 可能导致”电梯”效应，即磁头在磁盘上来回移动，效率不高。

2. 最短寻道时间优先算法 (SSTF):

– 优点： 减少寻道时间，能够快速响应就近的请求。
– 缺点： 可能导致某些请求长时间等待，可能出现”饥饿”现象。

3. 扫描算法 (SCAN)（电梯算法）:

– 优点： 减少寻道时间，避免了一直向一个方向移动导致的”饥饿”问题。
– 缺点： 可能导致在磁盘边缘的请求等待时间较长。

4. 循环扫描算法 (C-SCAN):

– 优点： 减少寻道时间，对所有请求更公平。
– 缺点： 仍然可能导致某些请求等待时间较长。