移臂调度算法研究

张菊

(辽宁省交通高等专科学校，辽宁沈阳110122)

磁盘是一种典型的共享存储设备，允许多个作业进程同时使用，而不是让一个作业在整个执行期间独占.当有很多进程提出I/O请求时，对它们就有一个调度安排问题:即让谁先用，让谁后用.当一个进程需要I/O时，它发出一个系统调用给操作系统，I/O请求要包含4方面必要的信息:输入还是输出、磁盘地址、内存地址和传送信息长度.如果所要求的磁盘驱动器和控制器是空闲的和可用的，则I/O请求被立即执行;如果设备和控制器正在为其它进程的I/O请求服务，则I/O请求必须排队等待.访问磁盘信息时，要经过移动磁头、扇区转动等待和读写操作3个步骤，即先要把移动臂移到相应的柱面上，然后等待数据所在的扇区旋转到磁头位置下，最后让指定的磁头读/写信息，完成数据的传输.因此，执行一次磁盘的输入输出需要花费的时间有:

(1)寻道时间，在移动臂的带动下，把磁头移动到指定柱面所需要的时间.

(2)等待时间，将指定的扇区旋转到磁头下所需要的时间.

(3)传输时间，由磁头进行读写操作，完成信息传送所需要的时间.

其中，传输时间是设备固有的特性.要提高磁盘的使用效率，只能减少查找时间和等待时间，它们都与I/O在磁盘上的分布位置有关.由于移动臂的移动是靠控制电路驱动步进电机来实现，它的运动速度相对于磁盘轴的旋转要缓慢，因此，减少查找时间比减少等待时间更能提高磁盘的使用效率［1］.

根据用户作业发出的磁盘I/O请求的柱面位置，来决定请求执行顺序的调度，被称为“移臂调度”.移臂调度的目标是使磁盘的平均寻道时间最少.移臂调度常采用的算法有:先来先服务、最短查找时间优先调度算法、扫描算法和单项扫描调度算法［2－7］.

1 算法描述

(1)先来先服务 FCFS(First Come First Served)

算法思想:它根据进程请求访问磁盘的先后次序进行调度.

这是一种最简单的磁盘调度算法.此算法的优点是公平、简单，每个进程的请求都能依次得到处理，不会出现某一进程的请求长时间得不到满足的情况.但此算法由于未对寻道进行优化，如果I/O请求很多，移动臂就有可能会里外地来回“振动”，致使平均寻道时间可能较长，极大地影响输入/输出的工作效率，因此这种算法并不理想.

(2)最短查找时间优先SSTF(Shortest Seek Time First)

算法思想:把距离磁头当前位置最近的I/O请求作为下一次调度的对象，这就是最短查找时间优先调度算法.

(3)扫描(SCAN)算法

算法思想:总是沿着磁盘移动臂的移动方向选择距离磁头当前位置最近的I/O请求，作为下一次调度的对象.如果该方向上已无I/O请求，则改变方向，再做选择.

该算法既考虑到要访问的磁道与当前磁道的距离，又考虑到磁头的当前移动方向，而且首先是方向一致，其次才是距离最短，从而避免了饥饿现象.因为该算法中磁头的移动规律与电梯类似，故称为电梯算法(Elevator Controller).

LOOK算法［8－9］是SCAN算法的一种改进.磁头只移动到一个方向上最远的请求为止，接着马上回头，而不是继续到磁盘的尽头.这种形式SCAN算法称为LOOK算法.

(4)单项扫描算法CSCAN(Circular SCAN)

算法思想:总是从0号柱面开始由里向外移动移动臂，遇到有I/O请求就进行处理，直到到达最后一个请求柱面;然后移动臂立即带动磁头不做任何服务地快速返回到0号柱面，开始下一轮扫描.

该算法是SCAN算法的变种，提供了一个更为均匀的等待时间.

2 案例分析

假设有一个磁盘组共有200个柱面，每个柱面上有8个磁道，每个盘面被划分成4个扇区.编号从0开始，假定读写磁头位于53号柱面，假设移动臂移动一个柱面需要3 ms，开始调度时，有8个I/O请求等待访问磁盘，如表1所示.

表1 I/O请求序列Table 1 The request sequence in disk I/O

2.1 各种算法的移动臂运动轨迹

(1)FCFS算法的移动臂运动轨迹如图1所示.

图1 先来先服务(FCFS)调度算法移动臂运动轨迹Fig.1 First come first served scheduling algorithm

(2)SSTF算法的移动臂运动轨迹如图2所示.

图2 最短查找时间优先(SSTF)调度算法移动臂运动轨迹Fig.2 Shortest seek time First scheduling algorithm

(3)LOOK算法的移动臂运动轨迹如图3、图4所示.

图3 LOOK算法(1)移动臂运动轨迹Fig.3 LOOK scheduling algorithm(1)

图4 LOOK算法(2)移动臂运动轨迹Fig.4 LOOK scheduling algorithm(2)

(4)CSCAN算法移动臂运动轨迹如图5所示.

图5 单项扫描(CSCAN)调度算法移动臂运动轨迹Fig.5 Circular SCAN scheduling algorithm

2.2 数据对比分析

将4种调度算法对同一I/O请求访问序列进行调度，所得到的响应次序如表2所示.

表2 各种调度算法的响应次序(从53号柱面开始)Table 2 Response sequence of various scheduling algorithms(From the 53 cylinder start)

所有请求访问柱面序列采用4种不同的调度算法的移动距离、寻道时间等数据如表3所示.

表3 各种调度算法的平均寻道时间Table 3 Average seek time of various scheduling algorithms(Millisecond)

可见，FCFS算法相对于各个请求进程的到达顺序来说，对各个请求进程是公平的，该算法也是非常简单、容易实现的，但是它的平均寻道时间最长，效率最低，可以作为衡量其它算法标准.

SSTF算法可以获得较好的寻道性能，但它可能导致某些进程发生饥饿现象(Starvation).因为只要不断地有新进程到达，而且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必须被优先满足.如果磁盘负载很重，SSTF算法存在一个问题:移动臂大部分时间将停留在柱面中部区域，而两端极端区域的请求将不得不等待，直到由于负载的统计波动使得中部区域没有请求位置.远离柱面中部区域的请求进程得到的服务很差.例如位于183号柱面的请求进程，虽然在请求序列中排在第2位，但是却是最后一个被响应.显然，SSTF和FCFS算法相比，将磁头移动减少了一半，SSTF算法虽然获得了较短的寻道时间，但是获得最短响应时间的目标和公平性之间存在着冲突，有失公平性.

LOOK算法是当磁头所移动的方向上不再有请求时立即改变运行方向，而CSCAN算法则需要移动到最底层或者最顶层时才改变运行方向.

LOOK(1)算法的平均响应时间比SSTF算法略短，但是响应时间方差比SSTF算法小很多，从统计学角度来讲 LOOK(1)算法要比SSTF算法稳定.

CSCAN算法是对SSTF算法的改进，也是LOOK算法的变种，能防止老进程出现饥饿现象，也能得到相对较好的寻道性能.但是，因为规定了磁头单向移动，例如只能由外向里移动，即当磁头移动到最大磁道号后立刻返回到0号柱面，开始下一次扫描，缺乏灵活性.

3 算法改进

FCFS、SSTF、LOOK和CSCAN 4种移臂调度算法，都可能出现磁臂停留在某处不动的情况，例如，有一个或几个进程对某一磁道有着较高的访问频率，即它们反复请求对某一磁道进行I/O，从而垄断了整个磁盘设备.这一现象称为磁臂粘着，在高密度磁盘上更容易出现此情况.下面改进一下LOOK算法.

(1)N-Step-LOOK算法

算法思想:把磁盘I/O请求队列分成若干个长度为n的子队列，磁盘调度将按FCFS算法依次处理这些子队列.按LOOK算法处理每一个队列，一个队列处理完后再处理其它队列.

N-Step-LOOK算法可以有效避免粘着现象.

说明:当n=1时，N-Step-LOOK算法退化为FCFS算法;当 n很大时，该算法接近于LOOK算法.

案例:假定当前读写磁头位于53号柱面，则LOOK算法和N-Step-LOOK算法对同一个请求序列的响应次序如表4所示.

表4 LOOK算法和N-Step-LOOK算法的响应次序Table 4 Response sequence of LOOK algorithm and N-Step-LOOK algorithm

显然，有4个进程反复请求对53号磁道进行磁盘I/O操作，如果采用LOOK算法，磁臂就会粘着在53号磁道上，从而垄断了整个磁盘设备，不能及时响应其它进程的磁盘I/O请求，这样对其它进程不公平.若采用N-Step-LOOK算法，假设令n=4，把磁盘I/O请求序列按长度为4划分成2个子队列，磁盘调度将按FCFS算法先处理队列1，再处理队列2，而队列1和队列2内部又是按LOOK算法处理.当正在处理队列1或队列2时，如果又出现新的磁盘I/O请求，便将新请求进程放入队列3，依此类推.这样就可避免出现粘着现象.当n值取得很大时，会使N-Step-LOOK算法的性能接近于LOOK算法的性能;当N=1时，N步 LOOK算法便蜕化为FCFS算法.

(2)FLOOK算法

算法思想:把磁盘I/O请求队列分成2个队列.一个队列:由当前所有请求磁盘I/O的进程组成，按LOOK算法处理;另一个队列:由新出现的所有请求磁盘I/O的进程组成.

FLOOK算法实质是N-Step-LOOK算法的简化，即n=2.

4 结语

诸多移臂调度算法各有利弊，如何选择一个最佳的算法很重要.FCFS算法简单，容易实现，但性能欠佳;SSTF算法较为普通而且很有吸引力，因为它比FCFS算法的性能要好;LOOK和CSCAN算法对于磁盘负荷较大的系统会更好，因为它们能避免“饥饿”现象的发生.对于一个特定的请求队列，能定义一个最佳的执行顺序，但是查找最佳调度序列所需的时间有可能很长，总的来说可能并不比SSTF算法或FCFS算法节省时间.

总之，无论何种调度算法，其性能主要依赖于I/O请求的数量和类型，在设计操作系统的移臂调度算法时应综合考虑各种因素，特别是系统性能的要求，来进行寻道算法的设计和选择.

［1］ 宗大华，宗涛，陈吉人.操作系统［M］.3版.北京:人民邮电出版社，2011:119.

［2］ 汤子赢，哲凤屏，汤小丹.计算机操作系统［M］.西安:西安电子科技大学出版社，1996:260－262.

［3］ 彭广习，余胜生，周敬利.基于磁盘性能模型的优化调度算法［J］.计算机工程，2002，28(5):20－22.

［4］ Hu ming.A Disk Scheduling Algorithm:SPFF［J］.Wuhan University Journal ofNatural Sciences，2005，10(6):983－987.

［5］ 崔英志.面向多媒体应用的磁盘调度算法研究［D］.重庆:重庆理工大学计算机应用技术系，2010:20－21.

［6］ Rahmani Hossein，Faghih Mohammad Mehdi，Moghaddam Mohsen Ebrahimi.A New Real Time Diskscheduling Method Based on GSR Algorithm［J］.Journal of Systems and Software，2010，83(11): 2147－2164.

［7］ CHANG H P，CHANG R I，SHIH W K，et al.GSR: A Global Seek-optimizing Real-time Disk-scheduling Algorithm［J］.Journal of Systems and Software，2007，80(2):198－215.

［8］ 周湘贞，曾宪权.操作系统原理与实践教程［M］.北京:清华大学出版社，2006:305.

［9］ 张顺香，朱广丽.一种基于平均寻道时间的磁盘调度优化算法［J］.计算机应用，2009，29(4):1147－1150.