磁臂调度—---扫描算法.doc

《磁臂调度—---扫描算法.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、磁臂调度—---扫描算法摘要：磁臂调度是指当同时有多个访盘要求时在等待时（每个要求访问一个扇区或一块），对些要求的顺序的确定安排或调整,旨在减少平均磁盘服务时间.磁臂调度由操作系统中的磁盘设备驱动完成,相应的算法称为磁臂调度算法;磁臂调度算法包括两个方面的考虑:首先要根据这些要求所访问的磁道按照某种标准对这些要求排序,旨在减少寻道时间,称为磁臂调度,仅在移动头磁盘中采用;其次对同一磁道我多个要求扇区顺序排列,旨在减少延迟时间，称为扇区排队，仅在无控制器磁道缓冲的系统中采用；关键词：扫描算法（电梯算法），磁道调度序列，移动磁道数，先向右后向左前言磁臂调度由操作系统中的磁盘设备驱动程序完成，相应的

2、算法称为磁臂调度算法。磁臂调度算法包括两个方面的考虑：首先，要根据这些要求访问的磁道按照，某种标准对这些要求排序，目的是减少磁头移动距离，即磁臂调度，仅在移动头磁盘中采用；其次，对同一磁道的多个要求按扇区顺序排队，为的是减少延迟时间，称为扇区排队，仅在无控制磁道缓冲的系统中采用；磁臂调度算法的标准是速度，公平，对共享的影响等，不仅在考虑寻道时间和延迟时间，还要考虑用户程序的等待时间等。一.设计的背景介绍1.1扫描调度（SCANScheduling）算法介绍:磁头总是单向移动的，但到达盘边缘则改变方向，磁头移动中为途中的所有请求服务。在下例中，磁头最初向右移动，则SCAN算法产生的顺序是65，6

3、7，98，122，124，183，37，14，如下图所示。如果一个请求到达时其要访问的磁道刚好在磁头移动前方，则该请求立即得到服务，反之如果刚好在磁头后，则要等到磁头返回以后再得到响应。例如：队列=98，183，37，122，14，124，65，67读写头起始位置：53183124122986765533714图1扫描算法图例1.2实现环境:DOS/WINDOWS2000（XP）平台,VC++编译器二．设计思路和总体流程图2.1基本思路本程序的前提是：先向右扫描，再向左扫描；首先，定义一个有关待访序列的结构体node，包含数据和标志两个成员。且各数据的标志初始为0，表示未被访问过；第二，将待访

4、序列按从小到大进行排序；第三，申请一个node型的动态的指针数组空间serial用来存放排序后的序列；第四，从左向右扫描，输出比当前磁头大且标志为0的磁道号，并将该磁道的标志置1；当扫描到最后一个磁道后，再从右向左扫描，输出比当前磁头小且标志为0的磁道号；第五，计算移动磁道数：移动的总磁道数为当前磁头与最大的磁道号之间的磁道数加上最大磁道与最小磁道之间的磁道数；最后，释放serial指针。2.2数据文件格式说明(1)输入文件格式如下:track_numbers:18current_location:53track_serial:19352565…………(2)其中,track_numbers表示

5、待访问的磁道数;current_location表示磁头当前位置;track_serial表示磁道序列2.3数据结构定义typedefstruct{//定义序列的结构体，其中data为磁道号，flag为访问状态标志intdata;//磁道号intflag;//标志}node;2.4总体流程图写出要访问的磁道的数据结构,该结构包括磁道号data和状态访问标志flag。另外，定义要访问的磁道数track_numbers,当前磁头所在的磁道号current_location和一个动态数组serial用来存放要访问的磁道,其大小等于要访问的磁道数读取文件,并将待访问的磁道序列号存入serial中。并定

6、义一个排序的子函数以供扫描算法使用。该函数按从小到大进行排序。用SWITCH语句来实现五种不同的选择：按数字1：FCFS的调度；数字2：扫描算法的调度；数字3：最短路径优先算法的调度；数字5：结束程序，将返回到重新开始调度的界面；除此之外的其他任何按键都将显示选择无效的提示。每做完一种选择都可自动清除界面。4：号功能：当改变数据文件后，不须关闭程序只须重新编译便可以继续执行相映的功能。根据界面上的提示，选择相应的功能2.5分模块流程图(先向右扫描子模块流程图)从文件中读入申请访盘要求的磁道总数.并把它放入track_numbers,中,读入最初磁头所在的磁道号,读入申请访盘的数组,并存入动态数

7、组serial中.将磁道序列复制到数组queue中，在调用排序子函数。先定义一个结构体node，定义磁道相关信息queue[i].data>clN不访问，i++，移动到下个磁道处，直到queue[i].data>cl为止Yqueue[i].flag==0输出该磁道号，并令queue[i].flag=1YN说明该磁道已经被访问过了，i++，访问下个磁道。当访问完最后一个磁道后，计算移动磁道数为当前磁