模拟磁盘调度算法操作系统专业课程设计

Word优秀模拟磁盘调度算法操作系统专业课程设计Word优秀某某大学课程设计报告课程名称：操作系统设计题目：模拟磁盘调度算法系别：计算机系专业：计算机科学与技术组别：学生姓名:学号:起止日期:指导教师:目录第一章需求分析 1 1 1 1 2第二章概要设计 3 3数据结构 3 3 5第三章详细设计 6 6第四章代码测试 9 9 11 12第五章心得体会 13第六章致谢 13参考文献 1附源代码 2Word优秀第一章需求分析 这是一个用VC++、C++为编程语言而实现模拟先来先效劳算法〔FCFS〕、最短寻道时间优先算法〔SSTF〕、扫描算法〔SCAN〕的一个磁盘调度程序。该程序设计系统主界面可以灵活选择某种算法并算出磁头移动的总磁道数以及平均磁道数。 本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先效劳算法〔FCFS〕、最短寻道时间优先算法〔SSTF〕、扫描算法〔SCAN〕等磁盘调度算法的理解。

设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3局部构成，它们是查找〔查找磁道〕时间、等待〔旋转等待扇区〕时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。

平均寻道长度〔L〕为所有磁道所需移动距离之和除以总的所需访问的磁道数〔N〕，即：L=〔M1+M2+……+Mi+……+MN〕/N。其中Mi为所需访问的磁道号所需移动的磁道数。

启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：

寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。

延迟时间——指定扇区旋转到磁头下所需的时间。

传送时间——由磁头进程读写完成信息传送的时间。

其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。

为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序〔从0号柱面开始〕，每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。系统主界面可以灵活选择某种算法，算法包括：先来先效劳算法〔FCFS〕、最短寻道时间优先算法〔SSTF〕、扫描算法〔SCAN〕。并计算及比较磁头移动总磁道数和平均磁道数。、先来先效劳算法〔FCFS〕这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备效劳的吞吐量，致使平均寻道时间可能较长，但各进程得到效劳的响应时间的变化幅度较小。、最短寻道时间优先算法〔SSTF〕该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的效劳请求的响应时机不是均等的，因而导致响应时间的变化幅度很大。在效劳请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。、扫描算法〔SCAN〕扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而防止了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法根本上克服了最短寻道时间优先算法的效劳集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。第二章概要设计本次课程设计我们是以面向对象的思想为主，利用VisualC＋＋为工具实现模拟磁盘调度。程序主要是利用冒泡排序函数、FCFS函数、SSTF函数、SCAN函数、CSCAN函数实现函数的功能。利用菜单式的选择界面，方便的用户操作。最终对每一种模拟磁盘调度输出磁头平均移动的磁道数以及总磁道数。数据结构该程序主要是利用7个函数。Panduan〔〕函数：对输入的字符进行判断是否合法，zhuanhua〔〕函数：对输入合法的字符进行转化，bubble〔〕函数：对输入的磁道进行冒泡排序，FCFS〔〕函数，即先来先效劳函数，SSTF〔〕函数：最短最短寻道时间函数，SCAN〔〕函数：扫描函数，CSCAN〔〕函数：循环扫描函数。各函数之间有点可以相互调用，共同实现要求。本程序主要用到的数据结构为数组、字符串，包括对字符串的合法性判断，利用数组算磁头移动的总磁道数，平均移动磁道数。磁盘调度模拟系统先来先效劳最短寻道时间优先磁盘调度模拟系统先来先效劳最短寻道时间优先扫描算法退出图2-1磁盘调度模拟系统

〔FCFS〕流程图：〔SSTF〕流程图〔SCAN〕流程图第三章详细设计本系统划分为四个模块：先来先效劳算法模块intFCFS(intarray[],intm)、最短寻道时间优先算法模块intSSTF(intarray[],intm)、扫描算法模块intSCAN(intarray[],intm)先来先效劳算法模块：intFCFS(intarray[],intm)输入磁道号，按先来先效劳的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。主要代码：for(i=0,j=1;j<m;i++,j++){sum+=abs(array[j]-array[i]);ave=(float)(sum)/(float)(m);}最短寻道时间优先算法模块：intSSTF(intarray[],intm)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：for(i=0;i<m;i++)/*使用冒泡法按从小到大顺序排列*/for(j=i+1;j<m;j++){if(array[i]>array[j]){temp=array[i];array[i]=array[j];array[j]=temp;}}if(array[m-1]<=now)/*假设当前磁道号大于请求序列中最大者，那么直接由外向内依次给予各请求效劳*/{ for(i=m-1;i>=0;i--)cout<<array[i]<<"";sum=now-array[0];}elseif(array[0]>=now)/*假设当前磁道号小于请求序列中最小者，那么直接由内向外依次给予各请求效劳*/while((l>=0)&&(r<m))/*当前磁道在请求序列范围内*/{if((now-array[l])<=(array[r]-now))/*选择与当前磁道最近的请求给予效劳*/{cout<<array[l]<<"";sum+=now-array[l];now=array[l];l=l-1;}扫描算法模块：intSCAN(intarray[],intm)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：if(d==0)/*选择移动臂方向向内，那么先向内扫描*/{for(j=l;j>=0;j--){cout<<array[j]<<"";/*输出向内扫描的序列*/}for(j=r;j<m;j++)/*磁头移动到最小号，那么改变方向向外扫描未扫描的磁道*/{cout<<array[j]<<"";/*输出向外扫描的序列*/}sum=now-2*array[0]+array[m-1];}else/*选择移动臂方向向外，那么先向外扫描*/{for(j=r;j<m;j++){cout<<array[j]<<"";/*输出向外扫描的序列*、}for(j=l;j>=0;j--)/*磁头移动到最大号，那么改变方向向内扫描未扫描的磁道*/{cout<<array[j]<<"";}sum=-now-array[0]+2*array[m-1];}}ave=(float)(sum)/(float)(m);第四章测试先来先效劳算法输入磁道序列：65783423871001826当前磁道号：80磁盘扫描序列为：65783423871001826平均寻到长度：磁头移动总磁道数：250最短寻道时间优先算法〔1〕当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：200磁盘扫描序列为10087786534262318平均寻到长度：磁头移动总磁道数：182〔2〕当前磁道号小于磁道序列中的最小的磁道号时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：10磁盘扫描序列为：18232634657887100平均扫描长度：磁道移动总磁道数：90〔3〕当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：80磁盘扫描序列为：78871006534262318平均扫描长度：磁道移动总磁道数：106扫描算法〔1〕当前磁道号大于磁道序列中的最大的磁道号时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：200磁盘扫描序列为10087786534262318平均寻到长度：磁头移动总磁道数：182〔2〕当前磁道号小于磁道序列中的最小的磁道号时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：10磁盘扫描序列为：18232634657887100平均扫描长度：磁道移动总磁道数：90〔3〕当前磁道号大于磁道序列中的最小的磁道号且小于最大磁道号〔磁头向外〕时输入磁道序列：65783423871001826排序后的磁道序列为：18232634657887100当前磁道号：80请输入当前移动臂的移动的方向〔1表示向外，0表示向内〕：1磁盘扫描序列为：87100786534262318平均寻到长度：磁道移动总磁道数：102

第五章心的体会通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的根本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地稳固所学，，实践能力与理论知识同样重要。可以说此课程设计的理论难度并不大，但是假设要深入开掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。通过本次课程设计，通过模拟磁盘调度及进程排队算法来加深对操作系统中各个磁臂调度算法概念的理解。模拟磁盘调度算法(FCFS,SSTF,SCAN,CSCAN)，实现各种不同调度算法的过程，并计算各算法的平均寻道长度，以便于我们判断各种算法的优劣以及各种算法使用的场合。对VC++。致谢感谢陕粉丽老师和本组成员在这次系统开发过程中对我的帮助参考文献[1]计算机操作系统高等教育出版社，孙钟秀，费翔林，骆斌等编著[2]

VC++深入详解电子工业出版社孙鑫，余指导教师评语：指导教师签名：年月日成绩评定项目权重成绩1、设计过程中出勤、学习态度等方面0.12、设计技术水平3、平安程度及可操作程度4、设计报告书写及图纸标准程度0.3总成绩教研室审核意见：教研室主任签字：年月日教学院〔系〕审核意见：主任签字：年月日 Word优秀附源代码#include<>#include<>#include<>#include<>constintmaxsize=1000;intpanduan(charstr[]);intzhuanhua(charstr[],inta);int*bubble(intcidao[],intm);intFCFS(intcidao[],intm);voidSSTF(intcidao[],intm);voidSCAN(intcidao[],intm);intmain(){inta; intc;intcidao[maxsize];inti=0,count;charstr[100];cout<<"请输入磁道序列〔0结束〕："<<endl;bei1:cin>>str;a=panduan(str);if(a==0){ cout<<"输入数据的类型错误,请重新输入！"<<endl; gotobei1;} else cidao[i]=zhuanhua(str,a);i++;while(cidao[i-1]!=0){ cin>>str;a=panduan(str);if(a==0) cout<<"输入数据的类型错误,请重新输入！"<<endl;else { cidao[i]=zhuanhua(str,a);i++; }}count=i-1;cout<<"你输入的磁道序列为：";for(i=0;i<count;i++){cout<<cidao[i]<<"";}cout<<endl;while(1){cout<<endl; cout<<"|____________________________________________|"<<endl; cout<<"|(*^__^*)系统菜单(*^__^*)|"<<endl; cout<<"|____________________________________________|"<<endl; cout<<"||"<<endl; cout<<"|1.先来先效劳|"<<endl; cout<<"||"<<endl; cout<<"|2.最短寻道时间优先|"<<endl; cout<<"||"<<endl; cout<<"|3.扫描调度|"<<endl; cout<<"||"<<endl; cout<<"|4.退出|"<<endl; cout<<"||"<<endl; cout<<"|____________________________________________|"<<endl; cout<<"|____________________________________________|"<<endl;bei7:cout<<"请选择算法："; bei6:cin>>str;a=panduan(str);if(a==0) { cout<<"输入数据的类型错误,请重新输入！"<<endl; gotobei6; } else c=zhuanhua(str,a);if(c==5)break; if(c>5) { cout<<"数据输入错误！请重新输入"<<endl; gotobei7; }switch(c) {case1:FCFS(cidao,count);break;case2:SSTF(cidao,count);break;case3:SCAN(cidao,count);break; }}return0;}/*********************判断输入数据是否有效**************************/intpanduan(charstr[]){inti=0; while(str[i]!='\0') { if(str[i]<'0'||str[i]>'9') { return0; break; } i++; } returni;}/******************将字符串转换成数字***********************/intzhuanhua(charstr[],inta){ inti; intsum=0; for(i=0;i<a;i++) { sum=sum+(int)((str[i]-'0')*pow(10,a-i-1)); } returnsum;}/*********************冒泡排序算法**************************/int*bubble(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; }}cout<<"排序后的磁盘序列为：";for(i=0;i<m;i++){cout<<cidao[i]<<"";} cout<<endl;returncidao;}/*********************先来先效劳调度算法**************************/intFCFS(intcidao[],intm){intnow;intsum=0;intj,i; inta; charstr[100];floatave; cout<<"磁盘请求序列为：";for(i=0;i<m;i++){cout<<cidao[i]<<"";} cout<<endl;cout<<"请输入当前的磁道号：";bei2:cin>>str;a=panduan(str);if(a==0) { cout<<"输入数据的类型错误,请重新输入！"<<endl; gotobei2; }else now=zhuanhua(str,a);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<<"平均寻道长度："<<ave<<endl; cout<<"磁头移动总磁道数："<<sum<<endl; return0;}/**********************最短寻道时间优先调度算法********************/voidSSTF(intcidao[],intm){intk=1;intnow,l,r;inti,j,sum=0;inta;charstr[100];floatave;cidao=bubble(cidao,m);cout<<"请输入当前的磁道号：";bei3:cin>>str;a=panduan(str);if(a==0){ cout<<"输入数据的类型错误,请重新输入！"<<endl; gotobei3;}else now=zhuanhua(str,a);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<<"平均寻道长度："<<ave<<endl;cout<<"磁头移动总磁道数："<<sum<<endl;}/*****************************扫描调度