磁盘调度实验报告.doc

操作系统课程设计-磁盘调度算法12一.课程设计目的和要求操作系统是计算机系统的一个重要系统软件。我们在本课程的实验过程中，了解实际操作系统的工作过程，在实践中加深对操作系统原理的理解。本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对FCFS、最短寻道时间以及电梯等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。课程设计要求模拟一个磁盘调度算法；要求能够模拟FCFS、最短寻道时间、电梯算法三个磁盘调度算法；输入为一组作业的磁道请求；输出为按选择的算法执行时的磁头移动轨迹。二系统需求分析磁盘调度主要思想：设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。目前常用的磁盘帝调度算法有：先来先服务、最短寻道时间优先及扫描等算法。三 概要设计系统流程图开始输入数据选择算法？调用FCFS（）算法调用SSTF（）算法调用SCAN（）算法输出退出是否系统模块图磁盘调度系统删除结点建立单链表输出单链表添加结点函数调用关系图Main函数SCAN函数SSTF函数FCFS函数输出四、详细设计(1)先来先服务算法（FCFS）先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。.输入当前磁道号now磁头移动距离sum=abs(now-array0)磁头移动总距离Sum+=abs(arrayj-arrayi)输出磁盘调度序列arrayj目前的位置变为当前的位置j+jm输出平均寻道长度avg=sum/(m)先来先服务算法流程图 (2)最短寻道时间优先算法（SSTF）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。12将磁道号从小到大排序输入当前磁道号nowarraym-1=0输出磁盘调度序列arrayj(array0=now磁头移动总距离sum=now-arrayi目前的位置变为当前的位置now=arrayinow=arrayiim确定当前磁道在已排的序列中的位置now-arrayl)=(arrayr-now先向磁道号减小方向访问，再向磁道号增加方向访问输出磁盘调度序列先向磁道号增加方向访问，再向磁道号减小方向访问输出磁盘调度序列输出平均寻道长度avg=sum/(m)最短寻道时间优先算法流程图(3)电梯算法（SCAN）SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。将磁道号从小到大排序输入当前磁道号now, 移动臂的移动的方向arraym-1=0(array0=now输出磁盘调度序列arrayjim磁头移动总距离sum=arrayi-now确定当前磁道在已排的序列中的位置switch(d)case 0:移动臂向磁道号减小方向访问case 1:移动臂向磁道号增加方向访问访问输出磁盘调度序列输出磁盘调度序列输出平均寻道长度avg=sum/(m) 电梯算法流程图五、调试过程将15 25 35 45保存在cidao.txt文件中，运行程序，得到运行结果图如下：六、结论与体会通过这次课程设计，我对磁盘调度算法有了更深的认识，我学会了用C语言编写这个算法，当然这当中我遇到了许多问题，这更使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，提高自己的能力。 七、参考文献1计算机操作系统 汤小丹等 西安电子科技大学出版社2操作系统设计教程 张丽芬等 清华大学出版社 2006年附件：源程序清单磁盘调度系统源程序清单#includestdio.h#includestdlib.h#includeiostream.h#include #define maxsize 100/*先来先服务调度算法*/void FCFS(int array,int m)int sum=0,j,i,now;for(i=0;im;i+)coutarrayi ;coutnow;for(i=0,j=1;jm;i+,j+) if(i=0) sum=abs(now-arrayi);sum+=abs(arrayj-arrayi);cout移动的总道数：sumendl;/*最短寻道时间优先调度算法*/void ShortPath(int array,int m)int temp;int k=1;int now,l,r;int i,j,sum=0;for(i=0;im;i+)for(j=i+1;jarrayj)temp=arrayi;arrayi=arrayj;arrayj=temp;for(i=0;im;i+)coutarrayi ;coutnow;if(arraym-1=0;i-)coutarrayi=now)for(i=0;im;i+)coutarrayi ;sum=arraym-1-now;elsewhile(arrayk=0)&(rm)if(now-arrayl)=(arrayr-now)coutarrayl ;sum+=now-arrayl;now=arrayl;l=l-1;elsecoutarrayr ;sum+=arrayr-now;now=arrayr;r=r+1;if(l=-1)for(j=r;jm;j+)coutarrayj=0;j-)coutarrayj ;sum+=abs(arrayj-now);now=arrayj;cout移动的总道数：sumendl;/*电梯调度算法*/void Elevator(int array,int m)/*先要给出当前磁道号和移动臂的移动方向*/int temp;int k=1;int now,l,r,d;int i,j,sum=0;for(i=0;im;i+)for(j=i+1;jarrayj)temp=arrayi;arrayi=arrayj;arrayj=temp;for(i=0;im;i+)coutarrayi ;coutnow;if(arraym-1=0;i-)coutarrayi=now)for(i=0;im;i+)coutarrayi ;sum=arraym-1-now;elsewhile(arrayknow)k+;l=k-1;r=k;coutd;if(d=0)for(j=1;j=0;j-)coutarrayj ;for(j=r;jm;j+)coutarrayj ;sum=now-2*array0+arraym-1;elsefor(j=r;jm;j+)coutarrayj=0;j-)coutarrayj ;sum=-now-array0+2*arraym-1;cout移动的总道数: sumendl;/主程序int main()int c;FILE *fp;int cidaomaxsize;int i=0,count;fp=fopen(cidao.txt,r+);if(fp=NULL)cout文件打不开!endl;/exit(0);elsewhile(!feof(fp)fscanf(fp,%d,&cidaoi);i+;count=i;for(i=0;icount;i+)coutcidaoi ;c