磁盘调度算法

深藏阁楼爱情的钟 2023-09-24 19:03 99阅读 0赞

### 磁盘调度算法 ###

为了减少对文件的访问时间，应采用一种最佳的磁盘调度算法，以使各进程对磁盘的平均访问时间最少。由于在访问磁盘时主要是寻道时间。因此，**磁盘调度的目标是使磁盘的平均寻道时间最少。**

![image-20230218223338628][]

#### 1.先来先服务（FCFS） ####

**算法原则：** 根据进程请求访问磁盘的先后顺序进行调度。

**优点：** 公平简单每个进程都能依次得到处理，不会出现某一进程长时间得不到满足的情况。

**缺点：** 平均寻道时间会有点长，适用于磁盘I/O进程数目较少的场合。

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。  
按照FCFS的规则，按照请求到达的顺序，磁头需要依次移动到55、58、39、18、90、160、150、38、184号磁道。

![image-20230218233213479][]

#### 2.最短寻找时间优先（SSTF） ####

**算法原则：** SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。(其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优)。

**优点：** 性能较好，平均寻道时间短。

**缺点：** 可能产生“饥饿”现象（磁头长时间在某一区域内移动）。

假设磁头的初始位置是100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。

![image-20230218233634875][]

#### 3.扫描算法(SCAN) ####

**算法原则：** 为了防止SSTF算法的“饥饿”问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法(SCAN)的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法。

**优点：** 性能较好，平均寻道时间较短，不会产生饥饿现象。

**缺点：**

①只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。  
②SCAN算法对于各个位置磁道的响应频率不平均（如:假设此时磁头正在往右移动，且刚处理过90号磁道，那么下次处理9O号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道的请求之后，很快又可以再次响应184号磁道的请求了)。

假设某磁盘的磁道为0~200号，磁头的初始位置是100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道。

![image-20230219000320143][]

#### 4.LOOK调度算法 ####

**算法原则：** 扫描算法(SCAN)中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK调度算法就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向(边移动边观察，因此叫LOOK)。

**优点：** 比起SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

![image-20230219000734717][]

#### 5.循环扫描算法(C-SCAN) ####

**算法原则：** SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN算法就是为了解决这个问题。规定只有磁头朝某个特定方向移动时才处理磁道访问请求，而返回时直接快速移动至起始端而不处理任何请求。

**优点：** 比起SCAN来，对于各个位置磁道的响应频率很平均。

**缺点：** 只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了，并且磁头返回时其实只需要返回到18号磁道即可，不需要返回到最边缘的磁道。另外，比起SCAN算法来，平均寻道时间更长。

![image-20230219001148751][]

#### 6.C-LOOK调度算法 ####

**算法原则：** C-SCAN算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

**优点：** 比起C-SCAN算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

![image-20230219001540273][]

[image-20230218223338628]: https://img-blog.csdnimg.cn/img_convert/da1acc974319800b2767c9bfa0641a60.png
[image-20230218233213479]: https://img-blog.csdnimg.cn/img_convert/519a86938f1f63d37b3e72949e9f1fff.png
[image-20230218233634875]: https://img-blog.csdnimg.cn/img_convert/2808f00c93222c4a30abdcb5db9a15d9.png
[image-20230219000320143]: https://img-blog.csdnimg.cn/img_convert/1a39266ea70188db6cf74e9b0c907ee1.png
[image-20230219000734717]: https://img-blog.csdnimg.cn/img_convert/98d8638b03da2652bad306e3249a0c5b.png
[image-20230219001148751]: https://img-blog.csdnimg.cn/img_convert/9256515872dee5ec71a96a4f969f858e.png
[image-20230219001540273]: https://img-blog.csdnimg.cn/img_convert/060cf4135c79a327966d674073b254a6.png