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

成绩 课程设计报告 题 目 磁盘调度算法程序设计 课 程 名 称 操作系统课程设计 院 部 名 称 信息技术学院 专 业 计算机科学与技术 班 级 M11计算机科学与技术 学 生 姓 名 学 号 课程设计地点 A205 课程设计学时 20 指 导 教 师 李 莉 金陵科技学院教务处制目录一、课程设计的目的和要求21、目的22、要求2二、设计任务介绍及系统需求分析2.1 任务介绍22.2基本需求设计2三、概要设计33.1程序主要流程33.2 程序的函数调用关系5四、详细设计54.1数据结构描述54.2各功能模块（或主要过程）分析54.3各子程序流程分析74.3.1 FCFS( )74.3.2 SSTF()84.3.3 SCAN( )9五、调试与测试105.1 程序运行初始界面105.2 键盘输入磁道105.3 随机产生磁道105.4 先来先服务算法105.5 最短寻道时间优先算法10 5.6 扫描算法125.6.1先向外扫描115.6.2先向里扫描115.7 退出程序11六、结论与体会12参考文献12附件：源程序清单13 一、课程设计的目的和要求1.1目的磁盘是经常使用的一种重要的外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。1.2 要求1）、设计一个函数完成先来先服务的磁盘调度功能。2）、设计一个函数完成最短寻道时间优先的磁盘调度功能。3）、设计一个函数完成电梯算法的磁盘调度功能。二、系统需求分析2.1 任务介绍1、可利用先来先服务算法（FCFS即first come first served）、最短寻道时间优先算法（SSTF即shortest seek time first）、扫描算法（SCAN），来实现磁盘的访问顺序。2、根据磁盘调度算法的不同的特性做好软件实现的需求分析。3、可根据问题的实际需要，可模拟数据在磁道的存放位置。4、当系统运行时，能直观地、动态地反映当前磁盘状态及不同算法的平均寻道时间。5、要求在系统安全状态的前提下，用户指定需要访问的磁道，软件自动模拟在不同算法情况下，磁盘寻道顺序和平均寻道时间。2.2基本需求设计 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）。1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2、最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。3、扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。三、概要设计3.1程序主要流程下图3-1为磁盘调度算法总流程图，程序运行开始，进入选择界面，输入磁道数，然后依次调用decide()函数和trans()函数，再进入主循环界面，选择调度算法，直到选择4，程序执行完毕退出。开始进入选择界面，手动输入还是系统自动生成磁道序列调用decide（）函数调用trans（）函数进入while(1)主循环输入14中的一数值，选择相应操作是输入是否为4？否判断键值，选择相应的调度算法，完成相应的功能结束图3-13.2程序函数调用关系下图为磁盘调度算法的函数之间的调用关系，主函数调用子函数，子函数也可以调用子函数，进行进程的初始化，排序等等。函数调用关系图，如图3-2：main()decide()SCAN()trans()SSTF()FCFS()Sort()图3-2四、详细设计4.1数据结构描述 本系统划分为三个模块：先来先服务算法模块void FCFS(int cidao,int m)、最短寻道时间优先算法模块void SSTF(int cidao,int m)、扫描算法模块void SCAN(int cidao,int m) 。1. 先来先服务算法模块：void FCFS(int cidao,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。2 .最短寻道时间优先算法模块：void SSTF(int cidao,int m)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。3 .扫描算法模块：void SCAN(int cidao,int m)将磁道号用冒泡法从小到大排序，输出排好序的序列，输入当前磁道号，选择移动臂的移动方向，根据当前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。4.2各模块函数功能分析由于一开始我们要对键盘输入的磁道数和要使用的算法进行一次有效性的判断，我使用了int decide(char str)，如果输入的信息不是09之间的数都将被判定为不合法，合法后才能进行下一步。判断完合法性后，要将我们输入的字符转化为数字，这里我用了int trans(char str,int a)。当然系统自动生成的就不要使用以上两个函数了。一切都准备好后，开始选择要调用哪个算法了，先来先服务调度算法我使用了void FCFS(int cidao,int m)，这个算法主要完成按原来键盘输入的次序或系统自动生成的次序来寻到，然后输出总的寻道长度和平均寻道长度。以下两个算法都要用到排序算法，这里我使用了冒泡排序法int *sort(int cidao,int m)，将磁道数按从小到大的序列排好。最短寻道时间优先调度算法我使用了void SSTF(int cidao,int m)，在排好序列磁道中选择离当前磁道最近的磁道开始寻道，然和再和相邻的两个磁道进行比较，看离哪个更近；如果当前磁道是最大值或是最小值，直接按倒叙或是正序寻道，最后输出总的寻道长度和平均寻道长度。扫描调度算法我使用了void SCAN(int cidao,int m)，在排好序的磁道序列中根据当前磁道数，选择是向外寻道还是向内寻道，如果当前磁道数是最大值或是最小值，直接向内或向外寻道，最后也要输出总的寻道长度和平均寻道长度。4.3各子函数流程分析4.3.1 FCFS()下图4-1为FCFS函数的流程图：开始输入磁道号或系统随机生成按原顺序将磁道序列输出求总的寻道长度sum+=abs(cidao0-now)求平均寻道长度ave=sum/m结束图4-14.3.2 SSTF()下图4-1为FCFS函数的流程图：开始输入磁道号或系统随机生成调用sort（）否minnow=now是是按排好的顺序直接输出磁道序列按排好的顺序倒序输出磁道序列按离当前磁道now最短的顺序输出磁道序列求总的寻道长度和平均寻道长度结束图4-24.3.3 SCAN()下图4-1为FCFS函数的流程图：开始输入磁道号或系统随机生成调用sort（）否minnowmax否now=min是是选择先向外还是向内扫描，再一次输出磁道序列直接向内扫描，从大到小输出磁道序列直接向外扫描，按从小到大输出磁道序列求总的寻道长度和平均寻道长度结束图4-3 五、调试过程5.1 运行程序初始界面运行程序，显示初始界面如图5-1所示，选择产生磁道的方式。图5-15.2 随机产生磁道输入1可随机产生磁道数，如图5-2所示。图5-25.3键盘输入磁道输入2进行键盘输入，并附带错误提醒功能，如图5-3所示。图5-35.4先来先服务算法输入1，选择先来先服务算法，如图5-4所示。图5-45.5最短寻道时间优先算法输入2，选择最短寻道时间优先算法，如图5-5所示。图5-55.6扫描算法5.6.1先向外扫描：输入3后，选择扫描算法，再输入1选择先向外扫描，如图5-6所示。图5-65.6.2先向里扫描：输入3后，选择扫描算法，再输入0选择先向里扫描，如图5-7所示。图5-75.7退出程序输入4退出，如图5-8所示。图5-8六、结论与体会这次操作系统的课程设计，从理论到实践，我学到很多很多的的东西，不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；各功能模块与主程序要正确衔接。在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如：在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来又转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。至此，计算机操作系统课程设计算法已经完成。但由于这次设计的时间比较仓促，其中不免会有些纰漏，在设计的过程中我也发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序编写不太会通过这次课程设计之后，一定把以前所学过的知识重新温故。在此，也感谢在课程设计过程中帮我解惑的老师和同学。七、参考文献1汤小丹、汤子赢等.计算机操作系统.西安：西安电子科技大学出版社，2007.2张丽芬. 操作系统实验教程M.北京：清华大学出版社，2006.附件：源程序清单磁盘调度算法源程序清单#include#include#include#include#include #define maxsize 100/*判断输入数据是否有效*/int decide(char str) /判断输入数据是否有效int i=0;while(stri!=0)if(stri9)return 0;break;i+;return i;/*将字符串转换成数字*/int trans(char str,int a) /将字符串转换成数字int i;int sum=0;for(i=0;ia;i+)sum=sum+(int)(stri-0)*pow(10,a-i-1);return sum;/*冒泡排序算法*/int *sort(int cidao,int m) int i,j;int temp;for(i=0;im;i+) /使用冒泡法按从小到大顺序排列for(j=i+1;jcidaoj) temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;return cidao; /*先来先服务调度算法*/void FCFS(int cidao,int m) /磁道号数组，个数为mint now=20;/当前磁道号int sum=0; /总寻道长度int j,i;float ave; /平均寻道长度cout磁盘请求序列为：;for( i=0;im;i+) /按先来先服务的策略输出磁盘请求序列coutcidaoi ;coutendl;sum+=abs(cidao0-now);cout磁盘扫描序列为：;for( i=0;im;i+) /输出磁盘扫描序列coutcidaoi ;for(i=0,j=1;jm;i+,j+) /求平均寻道长度sum+=abs(cidaoj-cidaoi);ave=(float)(sum)/(float)(m);coutendl;cout总的寻道长度：sumendl;cout平均寻道长度：aveendl;/*最短寻道时间优先调度算法*/void SSTF(int cidao,int m)int k=1;int now=20;int l,r;int i,j,sum=0;float ave;cidao=sort(cidao,m); /调用冒泡排序算法排序if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务cout=0;i-)coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务cout磁盘扫描序列为：;for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者cout磁盘扫描序列为：;while(cidaok=0)&(rm) /当前磁道在请求序列范围内if(now-cidaol)=(cidaor-now) /选择与当前磁道最近的请求给予服务coutcidaol ;sum+=now-cidaol;now=cidaol;l=l-1;elsecoutcidaor ;sum+=cidaor-now;now=cidaor;r=r+1;if(l=-1) /磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道for(j=r;jm;j+)coutcidaoj=0;j-)coutcidaoj ;sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);coutendl;cout总的寻道长度： sumendl;cout平均寻道长度： aveendl;/*扫描调度算法*/void SCAN(int cidao,int m) /先要给出当前磁道号和移动臂的移动方向int k=1;int now=20;int l,r,d;int i,j,sum=0;float ave;cidao=sort(cidao,m); /调用冒泡排序算法排序if(cidaom-1=now) /若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务,此情况同最短寻道优先 cout=0;i-)coutcidaoi=now) /若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务,此情况同最短寻道优先 cout磁盘扫描序列为：; for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1) /若当前磁道号大于请求序列中最小者且小于最大者while(cidaoknow)k+;l=k-1;r=k;coutd;if(d=0) /选择移动臂方向向内，则先向内扫描cout=0;j-)coutcidaoj ; /输出向内扫描的序列for(j=r;jm;j+) /磁头移动到最小号，则改变方向向外扫描未扫描的磁道coutcidaoj ; /输出向外扫描的序列sum=now-2*cidao0+cidaom-1;else /选择移动臂方向向外，则先向外扫描cout磁盘扫描序列为：;for(j=r;jm;j+)coutcidaoj=0;j-) /磁头移动到最大号，则改变方向向内扫描未扫描的磁道coutcidaoj ;sum=-now-cidao0+2*cidaom-1;ave=(float)(sum)/(float)(m);coutendl;cout总的寻道长度： sumendl;cout平均寻道长度： aveendl;/*主函数*/void main()int a,b;int c; /菜单项int cidaomaxsize;int i=0,count;char str100;cout * * 欢迎进入