磁臂调度—先来先服务算法-Read.ppt

1、磁臂调度先来先服务算法,福州大学阳光学院 03-3 林飞鹏 240390742 指导老师:吕书龙,摘要:,磁臂调度是指当同时有多个访盘要求时在等待时,对这些要求的顺序的确定安排或调整,旨在减少平均磁盘服务时间.磁臂调度由操作系统中的磁盘设备驱动完成,相应的算法称为磁臂调度算法;磁臂调度算法包括两个方面的考虑:首先要根据这些要求所访问的磁道按照某种标准对这些要求排序,旨在减少寻道时间,称为磁臂调度,仅在移动头磁盘中采用;其次对同一磁道我多个要求扇区顺序排列,旨在减少延迟时间，称为扇区排队，仅在无控制器磁道缓冲的系统中采用； 关键词: 磁臂调度 先来先服务,一.设计的背景介绍,1.1先来先服务是指

2、是指按申请扫描的先后顺序进行扫描.是最简单的磁臂调度算法,易于编程,而且公平,但平均而言却不能提供很好的服务.存在磁头疯狂移动,平均服务时间长,磁盘吞吐量小等问题. 1.2算法介绍:根据申请扫描的时间先后依次对其进行扫描.例如一个磁盘请求队列为:98,183,37,122,124,65,67,88,99,58,69 其最后扫描的序列也是: 98,183,37,122,124,65,67,88,99,58,69;,1.3实现环境:DOS/WINDOWS平台,TC2.0/3.0/VC+ LINUX平台,VI/EMACS等编辑器,CC/GCC编译器,二设计思路和总体流程图,2.1 基本思路 从文件中

3、读入磁盘请求队列.根据先来先服务算法知道其既为最后磁头所扫描经过的路径;所以最后的扫描序列就是磁盘请求队列.磁头移动的总路程就是:当前磁头所在的磁道号和序列中第一个磁道号差的绝对值,加上第二个和第一个差的绝对值,以此类推加到倒数第一个和倒数第二个的差的绝对值.,2.2 数据文件格式说明 文件格试如下: tracknum:9 current:90 currents:98,183,37,122,124,65,67, 88,99,58,69 其中tracknum:是代表请求访问的磁道总数. current:是代表磁头最初所在的磁道号. currents:是代表申请访问的磁道序列;,2.3 数据结构定

4、义 磁道访问结构: typedef struct int tracknum,current;/申请访问的磁道数量,磁头最初所在的磁道号; int *currents;/一个动态的指针用来存放申请访问的磁道序列; TRACK;,2.4 总体流程图,从文件中读入的一组数据已经放在动态数数comerow中,定义最后的位移用shift表示,并赋给其初值为0,用一个FOR语句把动态数组currents中的内容按currents+i输出 ,其中i从0到num-1,当输出一个时,并把相应的磁道号付给当前的磁头所在的磁道号,并且a=abs( current-*( currents+i) shift+=a,i

5、tracknum,Y,输出shift=多少并返回主函数,N,图一 总体流程图,(1):从文件中读入数据模块,i=0;,*(Track.currents+i)=从文件中读入数据,Itrack.tracknum,输出currents的内容并进入下一个模块,图二 从文件中读入数据模块图,分为二个模块,i+,Y,N,(2)计算位移和最后磁头移动路线的模块,i=0;,a=abs( current-*( currents+i) shift+=a current=*(currents+i),Itrack.tracknum,输出shift 就是磁头移动的总距离,并返回,图三 计算位移和最后磁头移动路线的模块图

6、,i+,Y,N,三算法的实现: 3.1 第一个模块算法实现: if (argc!=2) printf(errorn); exit(0); if(file=fopen(argv1,r)=NULL) printf(read file failedn); else fscanf(file,%9s%d,temp,track.currents=(int*)malloc(sizeof(int) *track.tracknum); for(i=0;itrack.tracknum;i+) fscanf(file,%d,track.currents+i); printf(the original track i

7、s:n); for(i=0;itrack.tracknum;i+) printf( %d,*(track.currents+i); ,3.2 第二个模块算法实现: for(i=0;itrack.tracknum;i+) a=abs(track.current-*(track.currents+i); track.current=*(track.currents+i); shift+=a; printf(n); printf(use the fcfs method the shift is:n); printf(shift=); printf(%d,shift);,3.3 编译及使用说明 用户首先在文件track中在相相应的位置输入 相应的参数其中: tracknum:在此位置输入请求访盘的磁道总数 current: 在此位置输入当前磁头所在的磁道号; trackserial: 在此位置输入申请访盘的磁道序列; 在以上相应位置输入相应的参数后度保存; 在DOS/WINDOWS平台,TC2.0/3.0/VC+环境下编译 fcfs（）函数，运行生成可执行文件main.exe；,把可执行文件fcfs.exe 和文本文件 track.txt放在同一目录下;在DOS下