磁盘调度算法程序课程设计报告

佥队科故寺院课程设计报告题目磁盘调度算法程序设计课程名称操作系统课程设计院部名称信息技术学院专业计算机科学与技术班级M11计算机科学与技术II学生姓名学号课程设计地点A205课程设计学时20指导教师李莉金陵科技学院教务处制目录TOC\o"1-5"\h\z\o"CurrentDocument"一、课程设计的目的和要求21、目的22、要求2二、设计任务介绍及系统需求分析2.1任务介绍22.2基本需求设计2\o"CurrentDocument"三、概要设计3\o"CurrentDocument"3.1程序主要流程33.2程序的函数调用关系4\o"CurrentDocument"四、详细设计54.1数据结构描述54.2各功能模块(或主要过程)分析54.3各子程序流程分析7FCFS()错误!未定义书签。SSTF()错误!未定义书签。SCAN()错误!未定义书签。五、调试与测试10\o"CurrentDocument"5.1程序运行初始界面10\o"CurrentDocument"5.2键盘输入磁道10\o"CurrentDocument"随机产生磁道10\o"CurrentDocument"先来先服务算法10\o"CurrentDocument"5.5最短寻道时间优先算法10\o"CurrentDocument"5.6扫描算法115.6.1先向外扫描115.6.2先向里扫描115.7退出程序11\o"CurrentDocument"六、结论与体会12参考文献12附件：源程序清单14一、课程设计的目的和要求1.1目的磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。1.2要求1）、设计一个函数完成先来先服务的磁盘调度功能。2）、设计一个函数完成最短寻道时间优先的磁盘调度功能。3）、设计一个函数完成电梯算法的磁盘调度功能。二、系统需求分析2.1任务介绍1、可利用先来先服务算法（FCFS即firstcomefirstserved）、最短寻道时间优先算法（SSTF即shortestseektimefirst）、扫描算法（SCAN），来实现磁盘的访问顺序。2、根据磁盘调度算法的不同的特性做好软件实现的需求分析。3、可根据问题的实际需要，可模拟数据在磁道的存放位置。4、当系统运行时，能直观地、动态地反映当前磁盘状态及不同算法的平均寻道时间。5、要求在系统安全状态的前提下，用户指定需要访问的磁道，软件自动模拟在不同算法情况下，磁盘寻道顺序和平均寻道时间。2.2基本需求设计系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）。1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2、最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。3、扫描算法(SCAN)扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。三、概要设计3.1程序主要流程下图3-1为磁盘调度算法总流程图，程序运行开始，进入选择界面，输入磁道数，然后依次调用decide()函数和trans()函数，再进入主循环界面，选择调度算法，直到选择4,程序执行完毕退出。开始结束图3-13.2程序函数调用关系下图为磁盘调度算法的函数之间的调用关系，主函数调用子函数，子函数也可以调用子函数，进行进程的初始化，排序等等。函数调用关系图，如图3-2：图3-2四、详细设计4.1数据结构描述本系统划分为三个模块：先来先服务算法模块voidFCFS(intcidao[],intm)、最短寻道时间优先算法模块voidSSTF(intcidao[],intm)、扫描算法模块voidSCAN(intcidao口，intm)。1.先来先服务算法模块：voidFCFS(intcidao[],intm)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。.最短寻道时间优先算法模块:voidSSTF(intcidao[],intm)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前磁道在己排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。.扫描算法模块:voidSCAN(intcidao[],intm)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。4.2各模块函数功能分析由于一开始我们要对键盘输入的磁道数和要使用的算法进行一次有效性的判断，我使用了intdecide(charstr[])，如果输入的信息不是0~9之间的数都将被判定为不合法，合法后才能进行下一步。判断完合法性后，要将我们输入的字符转化为数字，这里我用了inttrans(charstr[],inta)。当然系统自动生成的就不要使用以上两个函数了。一切都准备好后，开始选择要调用哪个算法了，先来先服务调度算法我使用了voidFCFS(intcidao[],intm)，这个算法主要完成按原来键盘输入的次序或系统自动生成的次序来寻到，然后输出总的寻道长度和平均寻道长度。以下两个算法都要用到排序算法，这里我使用了冒泡排序法int*sort(intcidao口，intm)，将磁道数按从小到大的序列排好。最短寻道时间优先调度算法我使用了voidSSTF(intcidao口，intm)，在排好序列磁道中选择离当前磁道最近的磁道开始寻道，然和再和相邻的两个磁道进行比较，看离哪个更近；如果当前磁道是最大值或是最小值，直接按倒叙或是正序寻道，最后输出总的寻道长度和平均寻道长度。扫描调度算法我使用了voidSCAN(intcidao口，intm)，在排好序的磁道序列中根据当前磁道数，选择是向外寻道还是向内寻道，如果当前磁道数是最大值或是最小值，直接向内或向外寻道，最后也要输出总的寻道长度和平均寻道长度。4.3各子函数流程分析4.3.1FCFS()下图4-1为FCFS函数的流程图:图4-1图4-2图4-3

五、调试过程5.1运行程序初始界面运行程序，显示初始界面如图5-1所示，选择产生磁道的方式。,"F:\MicrQ5QftVisualStudiQ\MyPrcjects\zh\D&bug\zh.e-xe,"F:\MicrQ5QftVisualStudiQ\MyPrcjects\zh\D&bug\zh.e-xeB图5-15.2随机产生磁道输入1可随机产生磁道数，如图5-2所示。(SSTF；FS先H)FC输入1可随机产生磁道数，如图5-2所示。(SSTF；FS先H)FC优31可S.1..111.■服»B度面先寻调界来通雷先最扫退-1-2CP晴选择算法,图5-25.3键盘输入磁道输入2进行键盘输入，并附带错误提醒功能，如图5-3所示。**蕙迎进入磁盘调度夏萤**k-福机产生«2-曲输入«章输入磁道序列结束）:4455&&77SS99100sli隔入救据的类型错误-请重新输入！图5-3

5.4先来先服务算法输入1，选择先来先服务算法，如图5-4所示。**襄迎融磁盘调度蚤蜜**-1.席机广生*2-慕盏输入*1随机产生的磁道序列为；15885060741215156427（SSIF）FS先M)FC（SSIF）FS先M)FC优漩(58.1..111.■务时服SB度面先寻调界来短雷先最扫退77224665991122477086600555?1-1-QJ-!!zZ1为为■■■■度度序/K-fe-隼椅晅道蓄扫寻寻选盘盘的坞总平图5-45.5最短寻道时间优先算法输入2,选择最短寻道时间优先算法，如图5-5所示。服道度面先寻调界来短理

先最扫退S84?4660572211550J12--..列度度a-序-fe-fc富道道择扫寻寻选盘的均图5-55.6扫描算法5.6.1先向外扫描：输入3后，选择扫描算法，再输入1选择先向外扫描，如图5-6所示。*1-先来先服务（FCFS）*2.最弟旦寻道曲胡尤先（SSTF）«3-扫描调度（SCON）3一闻..为.■■.移列度度法前序##算道道择入扫寻寻选譬的均请总平«4-iSto-W-面皿表示向内）=112臂的移动的方向＜1表示向外:2750即£43一闻..为.■■.移列度度法前序##算道道择入扫寻寻选譬的均请总平皿表示向内）=1125.6.2先向里扫描：输入3后，选择扫描算法，再输入0选择先向里扫描，如图5-7所示。*2.取短寻道耐间忱克（SSTF）*3.扫捕调度（GCfiN）*4.退出鬼面3动为::.■移列度度3动为::.■移列度度怯前序*算s道择入扫寻寻选譬的均青主勺5,B1-a.-5『哆1与9.B14率司8表示向外，2750606474图5-75.7退出程序输入4退出，如图5-8所示。FT88FFT88F步NCtftFflG(0-s.1..111.■-^-.^771域度面先寻调界来短3先最扫退|Pr~EssanykeytoEontzhme图5-8六、结论与体会这次操作系统的课程设计，从理论到实践，我学到很多很多的的东西，不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如：在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来又转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。至此，计算机操作系统课程设计算法已经完成。但由于这次设计的时间比较仓促，其中不免会有些纸漏，在设计的过程中我也发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序编写不太会……通过这次课程设计之后，一定把以前所学过的知识重新温故。在此，也感谢在课程设计过程中帮我解惑的老师和同学。七、参考文献汤小丹、汤子赢等.计算机操作系统.西安：西安电子科技大学出版社，2007.张丽芬.操作系统实验教程[M].北京：清华大学出版社，2006.附件：源程序清单磁盘调度算法源程序清单#include<stdio.h>#include<stdlib.h>#include<iostream.h>#include<math.h>#include<ctime>#definemaxsize100/*********************判断输入数据是否有效**************************/intdecide(charstr[])//判断输入数据是否有效{inti=0;while(str[i]!='\0'){if(str[i]<'0'||str[i]>'9'){return0;break;}i++;}returni;/******************将字符串转换成数字***********************/inttrans(charstr[],inta)//将字符串转换成数字{inti;intsum=0;for(i=0;i<a;i++){sum=sum+(int)((str[i]-'0')*pow(10,a-i-1));}returnsum;/*********************冒泡排序算法**************************/int*sort(intcidao[],intm){inti,j;inttemp;for(i=0;i<m;i++)//使用冒泡法按从小到大顺序排列for(j=i+1;j<m;j++){if(cidao[i]>cidao[j]){temp=cidao[i];cidao[i]=cidao[j];cidao[j]=temp;}}returncidao;/*********************先来先服务调度算法**************************/voidFCFS(intcidao[],intm)//磁道号数组，个数为m{intnow=20;//当前磁道号intsum=0;〃总寻道长度intj,i;floatave;//平均寻道长度cout<<"磁盘请求序列为：";for(i=0;i<m;i++)//按先来先服务的策略输出磁盘请求序列{cout<<cidao[i]<<"";}cout<<endl;sum+=abs(cidao[0]-now);cout<<"磁盘扫描序列为：";for(i=0;i<m;i++)//输出磁盘扫描序列{cout<<cidao[i]<<"";}for(i=0,j=1;j<m;i++,j++)//求平均寻道长度{sum+=abs(cidao[j]-cidao[i]);ave=(float)(sum)/(float)(m);}cout<<endl;cout<<"总的寻道长度："<<sum<<endl;cout<<"平均寻道长度："vvavevvendl;/**********************最短寻道时间优先调度算法********************/voidSSTF(intcidao[],intm){intk=1;intnow=20;intl,r;inti,j,sum=0;floatave;cidao=sort(cidao,m);〃调用冒泡排序算法排序if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务{cout<<"磁盘扫描序列为：";for(i=m-1;i>=0;i--)cout<<cidao[i]<<"";sum=now-cidao[0];}if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务{cout<<"磁盘扫描序列为：";for(i=0;i<m;i++)cout<<cidao[i]<<"";sum=cidao[m-1]-now;}if(now>cidao[0]&&now<cidao[m-1])//若当前磁道号大于请求序列中最小者且小于最大者{cout<<"磁盘扫描序列为：";while(cidao[k]<now)〃确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。{k++;}l=k-1;r=k;while((l>=0)&&(r<m))//当前磁道在请求序列范围内{if((now-cidao[l])<=(cidao[r]-now))〃选择与当前磁道最近的请求给予服务{cout<<cidao[l]<<"";sum+=now-cidao[l];now=cidao[l];l=l-1;}else{cout<<cidao[r]<<"";sum+=cidao[r]-now;now=cidao[r];r=r+1;}}if(l==-1)//磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道{for(j=r;j<m;j++){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}else//磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道{for(j=l;j>=0;j--){cout<<cidao[j]<<"";}sum+=cidao[m-1]-cidao[0];}}ave=(float)(sum)/(float)(m);cout<<endl;cout<<"总的寻道长度："<<sum<<endl;cout<<"平均寻道长度："<<ave<<endl;/*****************************扫描调度算法*******************************/voidSCAN(intcidao[],intm)/冼要给出当前磁道号和移动臂的移动方向{intk=1;intnow=20;intl,r,d;inti,j,sum=0;floatave;cidao=sort(cidao,m);〃调用冒泡排序算法排序if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务，此情况同最短寻道优先{cout<<"磁盘扫描序列为：";for(i=m-1;i>=0;i--)cout<<cidao[i]<<"";sum=now-cidao[0];}if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先{cout<<"磁盘扫描序列为：";for(i=0;i<m;i++)cout<<cidao[i]<<"";sum=cidao[m-1]-now;}if(now>cidao[0]&&now<cidao[m-1])//若当前磁道号大于请求序列中最小者且小于最大者{while(cidao[k]<now){k++;}l=k-1;r=k;cout<<"请输入当前移动臂的移动的方向(1表示向外，0表示向内):”;cin>>d;if(d==0)〃选择移动臂方向向内，则先向内扫描{cout<<"磁盘扫描序列为：";for(j=l;j>=0;j--){cout<<cidao[j]<<"”;//输出向内扫描的序列}for(j=r;j<m;j++)//磁头移动到最小号，则改变方向向外扫描未扫描的磁道{cout<<cidao[j]<<"”;//输出向外扫描的序列}sum=now-2*cidao[0]+cidao[m-1];}else〃选择移动臂方向向外，则先向外扫描{cout<<"磁盘扫描序列为：";for(j=r;j<m;j++){cout<<cidao[j]<<"”;//输出向外扫描的序列}for(j=l;j>=0;j--)//磁头移动到最大号，则改变方向向内扫描未扫描的磁道{cout<<cidao[j]<<"";}sum=-now-cidao[0]+2*cidao[m-1];}}ave=(float)(sum)/(float)(m);cout<<endl;cout<<"总的寻道长度："<<sum<<endl;cout<<"平均寻道长度："<<ave<<endl;}/“““““““““““““““““““““““““““““T—'.、1».1*“““““““““““““““““““““““““““““““//*****************************王函数*******************************/voidmain(){inta,b;intc;//菜单项intcidao[maxsize];inti=0,count;charstr[100];cout<<"**欢迎进入磁盘调度算法**"<<endl;cout<<"*1.随机产生*2,键盘输入*”<<endl;cin>>b;if(b==1){srand((unsigned)time(0));for(i=0;i<10;i++){cidao[i]=rand()%maxsize;}count=i;//要访问的磁道数coutvv”随机产生的磁道序列为："；for(i=0;i<count;i++){cout<<cidao[i]<<"";//输出磁道序列}cout<<endl;}if(b==2){cout<<"请输入磁道序列(0结束)："vvendl;A:cin>>str;//对输入数据进行有效性判断a=decide(str);if