5.6.3 主要的磁盘调度算法

一、磁头调度算法

(一)先来先服务算法

1、算法思想:按访问请求到达的先后次序服务。

2、优点:简单,公平。

3、缺点:效率不高,相邻两次请求可能会造成最内到最外的柱面寻道,使磁头反复移动,增加了服务时间,对机械也不利。

4、例子:

假设磁盘访问序列:98,183,37,122,14,124,65,67。读写头起始位置:53。求:磁头服务序列和磁头移动总距离(道数)。

由题意和先来先服务算法的思想,得到下图所示的磁头移动轨迹。由此:

磁头服务序列为:98,183,37,122,14,124,65,67

磁头移动总距离=(98-53)+(183-98)+|37-183|+(122-37)+|14-122|+(124-14)+|65-124|+(67-65)=640(磁道)

(二)最短寻道时间优先算法

1、算法思想:优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。

2、优点:改善了磁盘平均服务时间。

3、缺点:造成某些访问请求长期等待得不到服务。

4、例子:对上例的磁盘访问序列,可得磁头移动的轨迹如下图。请同学自己给出磁头服务序列并计算磁头移动总距离。

(三) 扫描算法(电梯算法)

1、算法思想:当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中对遇到的访问请求进行服务,然后判断该方向上是否还有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。如下图所示:

扫描算法(电梯算法)的磁头移动轨迹

2、优点:克服了最短寻道优先的缺点,既考虑了距离,同时又考虑了方向。

3、例子:下图是一个示例。请同学自己写出一个可能的磁盘访问序列,并计算磁头移动总距离。

扫描算法图例

(四)单向扫描调度算法

算法思想:

1、总是从0号柱面开始向里扫描。

2、按照各自所要访问的柱面位置的次序去选择访问者。

3、移动臂到达最后一个柱面后,立即带动读写磁头快速返回到0号柱面。

4、返回时不为任何的等待访问者服务。

5、返回后可再次进行扫描。

二、旋转调度算法

(一)旋转调度

根据延迟时间来决定执行次序的调度。

(二)计算延迟时间应考虑的因素

1、若干等待访问者请求访问同一磁道上的不同扇区。

2、若干等待访问者请求访问不同磁道上的不同编号的扇区。

3、若干等待访问者请求访问不同磁道上具有相同的扇区。

(三)解决方案

1、对于前两种情况:总是让首先到达读写磁头位置下的扇区先进行传送操作。

2、对于第三种情况:这些扇区同时到达读写磁头位置下,可任意选择一个读写磁头进行传送操作。

(四)例子

设磁盘旋转一周为20毫秒/周;花5毫秒对每个扇区的记录进行处理,有下述请求序列:

请求顺序    柱面号    磁头号    扇区号

  ①       5       4       1

  ②       5       1       5

  ③       5       4       5

  ④       5       2       8

请同学自己分析:给出时间最少的磁头服务序列和最少时间。