操作系统课程设计报告磁盘调度算法.doc

课 程 设 计课程设计名称： 操作系统应用课程设计 专 业 班 级 ： 学 生 姓 名 ： xxxxx 学 号 ： 指 导 教 师 ： 课程设计时间： 2010.12.20-2010.12.26 计算机科学 专业课程设计任务书学生姓名专业班级学号题 目磁盘调度算法（SSTF，NstepSCAN）课题性质其它课题来源自拟课题指导教师于俊伟同组姓名张晓鹏主要内容磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。也正因为这样，我们有必要对各算法进行模拟，进而比较、分析、了解设计主界面以灵活选择某算法，且以下算法都要实现：1、最短寻道时间优先调度算法（SSTF）2、NStepSCAN调度算法并求出每种算法的总寻到长度、平均寻道长度任务要求理解磁盘调度算法，并进一步加深对调度算法及其实现过程的理解。1、模拟一个磁盘调度算法；2、要求能够模拟最短寻道时间优先（SSTF）、N步扫描算法（NStepSCAN）算法两个磁盘调度算法3、输入为一组作业的磁道请求，改组磁道好的获得从文件中取出；4、输出为按选择的算法执行时的磁头移动轨迹。参考文献1 任满杰等.操作系统原理实用教程.电子工业出版社,20062 张尧学,史美林.计算机操作系统教程实验指导.清华大学出版社,2000 3 罗宇.操作系统课程设计.机械工业出版社,20054 汤子瀛，哲凤屏，汤小丹编著.计算机操作系统.西安电子科技大学出版社, 20055 周敏，杨武，杨承玉编著.计算机操作系统原理实验指导基于LINUX（Ver3.0）.重庆：重庆工学院,20066 谭浩强编著.C语言程序设计（第3版）.清华大学出版社，2005审查意见指导教师签字：教研室主任签字： 年 月 日 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页一 .课程设计需求分析操作系统是计算机系统的一个重要系统软件。我们在本课程的实验过程中，了解实际操作系统的工作过程，在实践中加深对操作系统原理的理解。磁盘存储器不仅容量大，存取速度快，而且可以实现随机存取，是当前存放大量程序和数据的理想设备，故在现代计算机系统中，都配置了磁盘存储器，并以它为主来存放文件。这样，对文件的操作，都将涉及到对磁盘的访问。磁盘I/O速度的高低和磁盘系统的可靠性都将直接影响到系统性能。因此，设法改善磁盘系统的性能，已成为现代操作系统的重要任务之一。磁盘性能有数据的组织、磁盘的类型和访问时间等。磁盘调度的目标是使磁盘的平均寻道时间最少。也正因为这样，我们有必要对各算法进行模拟，进而比较、分析、了解。本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对最短寻道时间优先（SSTF）、N步扫描算法（NStepSCAN）等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。二.课程设计原理设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N。其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间；延迟时间指定扇区旋转到磁头下所需的时间；传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘是，应采用一种最佳调度算法，以使各种进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标，是使磁盘的平均寻道时间最少。三.算法分析及程序概要设计1.最短寻道时间优先算法（SSTF）1.1算法分析：最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。也就是说，该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。但这种算法不能保证平均寻道时间最短。现在利用一个例子来讨论，假设当前移动臂所在的磁道为100，进程请求访问磁盘的先后次序为：55、58、39、18、90、160、150、38、184。那么该算法将这样进行进程调度：现在当100号柱面的操作结束后，应该先处理90号柱面的请求，然后到达58号柱面执行操作，随后处理55号柱面请求，后继操作的次序应该是39、38、18、150、160、184。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”（Starvation）现象。因为只要不断有新进程的请求到达，且其所要访问的磁道与磁头当前所在磁道的距离较近，这种新进程的I/O请求必然优先满足。也就是说，SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（饥饿）。1.2概要设计（流程图）：将磁道号从小到大排序输入当前磁道号nowarraym-1<=now输出磁盘调度序列arrayj目前的位置变为当前的位置now=arrayi磁头移动总距离sum=now-arrayii>=0输出磁盘调度序列arrayj(array0>=now磁头移动总距离sum=now-arrayi目前的位置变为当前的位置now=arrayinow=arrayii<m确定当前磁道在已排的序列中的位置now-arrayl)<=(arrayr-now先向磁道号减小方向访问，再向磁道号增加方向访问输出磁盘调度序列先向磁道号增加方向访问，再向磁道号减小方向访问输出磁盘调度序列输出平均寻道长度avg=sum/(m)2、NStepSCAN算法2.1算法分析N步扫描算法是基于扫描算法发展而成的，故要想很好的了解它，首先得对扫描算法加以理解分析，只有这样才能很好地理解N步扫描算法。扫描算法（SCAN） 又称电梯调度算法。该算法不仅考虑到与访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法这种逐步自里向外又自外向里（或先自外向里又自外向里）的磁头移动规率，很好地避免了出现“饥饿”现象，并在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。N步扫描算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而没处理一个队列时又是按SCAN算法，对一个队列处理完后，在处理其他队列。当正在处理某子队列时，如果又出现新的I/O请求，便将新请求进程放入其他队列，这样就可以避免出现粘着现象，统称“磁盘粘着”（Armstickiness）(有一个或几个进程对某一磁道有较高的访问频率，即这些进程反复请求对某一磁道的I/O操作，从而垄断了整个磁盘设备的现象）。而在SSTF、SCAN及CSCAN几种调度算法中，都有可能出现磁臂留在某处不动的情况，即出现磁盘粘着现象。当N取值很大时，会使N步扫描的性能接近于SCAN算法的性能；当N=1时，N步扫描算法退化为FCFS算法。此外，需要了解的是N步SCAN算法的简化算法是FSCAN算法，即将磁盘请求队列分成两个子队列的算法。2.2概要设计（流程图）从文件中获取进程请求磁道号放入cidaoi统计总个数count输入当前磁道号now,子队列个数 N,移动臂的移动方向d从cidaoi中取出前count/N组成一个子队列，存入bi,最后一列将该子队列为剩余磁道号，存入biN！=0? Y N将磁道号从小到大排序arraym-1<=now磁头移动总距离sum=now-arrayi输出磁盘调度序列arrayji>=0(array0>=now输出磁盘调度序列arrayji<m磁头移动总距离sum=arrayi-now确定当前磁道在已排的序列中的位置switch(d)case 0:移动臂向磁道号减小方向访问case 1:移动臂向磁道号增加方向访问访问输出磁盘调度序列输出磁盘调度序列输出子队列寻道总道数sum输出子队列平均寻道长度avg=sum/(m)输出该算法下总的寻道数s输出该算法下平均寻道数四、详细设计#include"stdio.h"#include"stdlib.h"/#include"iostream.h"#define maxsize 100 /定义最大数组域int now,s;/最短寻道时间优先调度算法void SSTF(int array,int m)int temp;int k=1;int now,l,r; /当前磁道号now；找出的当前磁道左侧的磁道l，右侧的磁道rint i,j,sum=0;int avg;for(i=0;i<m;i+)for(j=i+1;j<m;j+)/对磁道号进行从小到大排列if(arrayi>arrayj)/两磁道号之间比较temp=arrayi;arrayi=arrayj;arrayj=temp;for( i=0;i<m;i+)/输出排序后的磁道号数组printf("%d ",arrayi);printf("n 请输入当前的磁道号：");scanf("%d",&now);printf("n SSTF调度结果: ");if(arraym-1<=now)/判断整个数组里的数是否都小于当前磁道号 for(i=m-1;i>=0;i-)/将数组磁道号从大到小输出printf("%d ",arrayi);sum=now-array0;/计算移动距离else if(array0>=now)/判断整个数组里的数是否都大于当前磁道号 for(i=0;i<m;i+)/将磁道号从小到大输出printf("%d ",arrayi);sum=arraym-1-now;/计算移动距离elsewhile(arrayk<now)/逐一比较以确定K值k+;l=k-1;r=k;/确定当前磁道在已排的序列中的位置while(l>=0)&&(r<m)if(now-arrayl)<=(arrayr-now)/判断最短距离 printf("%d ",arrayl);sum+=now-arrayl;/计算移动距离now=arrayl;l=l-1;else printf("%d ",arrayr);sum+=arrayr-now;/计算移动距离now=arrayr;r=r+1;if(l=-1) for(j=r;j<m;j+) printf("%d ",arrayj);sum+=arraym-1-array0;/计算移动距离else for(j=l;j>=0;j-) printf("%d ",arrayj);sum+=arraym-1-array0;/计算移动距离avg=sum/m;printf("n 移动的总道数： %d n",sum);printf(" 平均寻道长度： %d n",avg);/扫描调度方法void SCAN(int array,int m,int d)/先要给出当前磁道号和移动臂的移动方向int k=1;int l,r;int i,j,sum=0;int avg;int temp; /用于排序的临时参数int q; for(i=0;i<m;i+)for(j=i+1;j<m;j+)if(arrayi>arrayj)/对磁道号进行从小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;if(arraym-1<=now)/判断整个数组里的数是否都小于当前磁道号 printf("n SCAN调度结果: ");for(i=m-1;i>=0;i-)printf("%d ",arrayi);/将数组磁道号从大到小输出 q=arrayi;sum=now-q;/计算移动距离s=s+sum;now=q;else if(array0>=now)/判断整个数组里的数是否都大于当前磁道号 printf("n SCAN调度结果: ");for(i=0;i<m;i+)printf("%d ",arrayi);/将磁道号从小到大输出 q=arrayi;sum=arraym-1-now;/计算移动距离 s=s+sum;now=q;elsewhile(arrayk<now)/逐一比较以确定K值k+;l=k-1;r=k;printf("n SCAN调度结果: ");if(d=0)for(j=l;j>=0;j-)printf("%d ",arrayj); q=arrayj;for(j=r;j<m;j+)printf("%d ",arrayj); q=arrayj;sum=now-2*array0+arraym-1;/计算移动距离 s=s+sum;now=q;/磁道号减小方向elsefor(j=r;j<m;j+)printf("%d ",arrayj); q=arrayj;for(j=l;j>=0;j-)printf("%d ",arrayj); q=arrayj;sum=-now-array0+2*arraym-1;/计算移动距离 s=s+sum;now=q;/磁道号增加方向avg=sum/m;printf("n 该子队列移动的总道数： %d n",sum);printf(" 该子队列平均寻道长度： %d n",avg);void NStepSCAN(int array,int m) int sn,N,d; /sn标记每一子队列的长度，N记录子队列个数，now标记当前磁道号int b100,c100; /b100储存前几个子队列，c100储存最后一个子队列int i=0,j=0,k=0,n=1;int ave; printf("请输入当前磁道号：n");scanf("%d",&now);printf("请输入子队列的个数：n");scanf("%d",&N);while(N<1|N>m)printf("超出范围，文件中的磁道数不够分组，请重新输入：n"); scanf("%d",&N); printf("请输入当前移动臂的移动的方向 (1 磁道号增加方向，0磁道号减小方向) : "); scanf("%d",&d);sn=m/N;while(N!=1) /当不是最后一个子队列时，循环进行SCAN调度j=0;for(i=k;i<sn*n;i=k,j+)bj=arrayi;k=k+1; printf("n第%d个队列的排序结果为：n",n); SCAN(b,sn,d);N=N-1;n=n+1;if(N=1) /最后一个子队列时进行SCAN调度for(i=k,j=0;i<m;i+,j+)cj=arrayi; printf("n最后一个队列的调度结果为：n"); SCAN(c,m-k,d);ave=s/m;printf("n该调度总的结果为：n");printf("n 移动的总道数： %d n",s);printf(" 平均寻道长度： %d n",ave); / 操作界面int main()int c;int C=1;FILE *fp;/定义指针文件int cidaomaxsize;/定义磁道号数组int i=0,count;fp=fopen("cidao.txt","r+");/读取cidao.txt文件if(fp=NULL)/判断文件是否存在printf("n 请 先 设 置 磁 道! n");exit(0);while(!feof(fp)/如果磁道文件存在fscanf(fp,"%d",&cidaoi);/调入磁道号i+;count=i;printf("n -n");printf(" 10-11年度OS课程设计-磁盘调度算法模拟");printf("n -n"); printf("n 磁道读取结果：n");for(i=0;i<count;i+)printf("%5d",cidaoi);/输出读取的磁道的磁道号printf("n ");while(C=1) printf(" n");printf(" 操作系统课程设计 n"); printf(" 磁盘调度算法 n "); printf(" n"); printf(" n"); printf(" n"); printf(" 1.最短寻道时间优先算法(SSTF) n"); printf(" n"); printf(" n"); printf(" 2.N步扫描算法(NStepScan) n"); printf(" n"); printf(" n"); printf(" n"); printf(" n"); printf(" 请输入你的选择的算法(输入0离开) n"); printf(" n"); scanf("%d",&c); if(c=0) exit(0); printf(" ");while(c!=1&&c!=2)printf("输入数据超出范围，请重新输入您想进行的调度算法：n"); scanf("%d",&c);switch(c) case 1: SSTF(cidao,count);/最短寻道时间优先算法 printf("n"); break; case 2:i=0; fp=fopen("cidao.txt","r+");/读取cidao.txt文件 if(fp=NULL)/判断文件是否存在printf("n 请 先 设 置 磁 道! n"); exit(0); while(!feof(fp)/如果磁道文件存在 fscanf(fp,"%d",&cidaoi);/调入磁道号 i+; count=i; printf("n 磁道读取结果：n"); for(i=0;i<count;i+) printf("%5d",cidaoi);/输出读取的磁道的磁道号 printf("n ");NStepSCAN(cidao,count);/N步扫描算法 printf("n"); break;printf(" 是否继续(按0结束,按1继续)?");scanf("%5d",&C);return(0);五、调试运行结果1. 调试运行后的开始界面如下：2、调试运行各个算法结果如下:21运行最短寻道时间优先（SSTF）算法调度程序结果如下：22调试运行NStepSCAN调度程序结果如下：2.2.1移动臂的移动方向以磁道号增加方向：2.2.2移动臂的移动方向以磁道号减小方向：3输入错误后程序界面如下：3.1在选择算法时，如果输入数字不在1-2之间，出错界面如下：3.2在进行N步扫描算法时，当输入要进行分组的子队列个数少于文件中的磁盘号数时，出现如下界面：七调试分析及总结整个设计中最麻烦的就是整个程序模块的划分和各模块之间接口设计，编程中经常犯想当然的错误，编程中出现了不少奇怪的错误。再调试中尝试使用了分割法,对错误模块进行定位,再进行排查。还使用了单步调试法，很好地解决了某些逻辑错误，比如在利用N步SCAN算法时，其中对磁道号的分组时，出现了越界，开始时还以为是函数传递参数时出现了越界，导致分组后的数组值乱码，但通过单步调试很容易的找出了症结所在。原来是由于循环中的“j”值发生越界导致的结果错误。在N步扫描算法中，还出现了这样一个问题。就是，在对磁道号进行分组时，最后一列的处理问题。在开始时由于笼统地进行了平均分组，而没有考虑无法完全分尽的情况，进而导致最后一个甚至一些磁道号丢失的问题。不过最后，在单列最后一组后（即将最后一组与前面各组分开后）问题得到了解决。将余下的一个或一些磁道号全部加至最后一列末尾，很好地处理了数据丢失问题。通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(SSTF,NstepSCAN)，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。