磁盘的移臂调度算法

1、概要

        访问磁盘，首先要找到数据，但机械硬盘并不是直接电子读取，是需要移动磁头到相应的数据块上才能读取的，即需要磁头移动到目标柱面(磁道)，然后磁片旋转使磁头能访问到相应扇区，进而读取到数据。

        根据访问者指定的柱面位置(磁道)来决定执行次序的调度称为移臂调度。目的就是尽可能减少寻道时间。

2、算法

        常用的算法有：先来先服务、最短寻找时间优先、电梯调度、单向扫描。

        为了说明算法的移动柱面顺序，这里先假设磁盘有99个柱面，0在最外侧，99在最内侧。 进程访问顺序是  10,20,5,90,60。当前磁头在15柱面，方向是从外往内走。

        2.1 先来先服务

        该算法根据进程访问磁盘先后次序进行调度。基本没啥优化，效率最低。

        上面磁头访问顺序为：15,10,20,5,90,60，可以看出磁头在内外圈往返很多次，效率极低。假设跨越一个柱面距离为1，则移动距离为：|15-10|+|10-20|+|20-5|+|5-90|+|90-60| = 5+10+15+85+30 = 145。

        2.2 最短寻找时间优先

        也叫“最短移臂调度算法”。该算法每次访问当前磁头最近的柱面。优点是平均每次磁头移动距离明显低于先来先服务，过去曾被广泛使用。

        上面磁头访问顺序为：15,10,5,20,60,90。移动距离为：|15-10|+|10-5|+|5-20|+|20-60|+|60-90| = 5+5+15+40+30 = 95。

        2.3 电梯调度

        从当前臂移动方向选择离臂最近的柱面访问，直到当前方向没有需要访问的柱面，然后臂改变方向再选择离臂最近的柱面访问，直到所有柱面访问结束。(若磁头一开始无方向，是静止的，则找最近的柱面移动)

        上面磁头访问顺序为：15,20,60,90,10,5，移动距离为：|15-20|+|20-60|+|60-90|+|90-10|+|10-5| = 5+40+30+80+5 = 160。

        可以看出，电梯调度有些问题，方向不对最后走的距离比先来先服务还多！若能稍微分析下两个方向各柱面到当前柱面的最大距离，再决定先走最大距离小的方向会好很多。

        2.4 单向扫描

        总是从外向里开始扫描。只有从外向内扫描的时候才访问柱面，最内层快速返回最外层的0号磁道时不访问柱面。

        上面磁头访问顺序为：15,20,60,90,(0),5,10，其中90到0是不需要计入时间，因为这个跨越柱面不用访问柱面，时间非常短。移动距离为：|15-20|+|20-60|+|60-90|+|0-5|+|5-10| = 5+40+30+5+5 = 85。

        可以看出单向扫扫描最长只需花费单程磁盘柱面数量的长度的时间就可以访问所有柱面。当然，这个时间排除了最内层跳转到最外层0道的时间。