操作系统--课程设计报告.doc

1、课程设计一、课题设计目的a、观察、体会操作系统的磁盘调度方法，并通过一个简单的磁盘调度模拟程序的实现，加深对磁盘调度的理解。b、提高实际动手编程能力，为日后从事软件开发工作打下坚实基础。c、通过对磁盘调度算法的设计，深入理解提高磁盘访问速度的原理。二、课题实现环境VC+6.0 MFC三、课题设计思路 算法描述：1.服务算法（FCFS）先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问

2、的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2.算法（SCAN）SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前

3、移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8层带到15层，然后电梯换成下行方向，把乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。1.移动臂由里向外移动开始时，在50号

4、柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是32号柱面。所以应先为32号柱面的访问者服务，然后是为15号柱面的访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199。2.移动臂由外向里移动开始时，正在50号柱面执行操作的读写磁头的移动臂是由外向里（即向柱面号增大的内圈方向）趋向61号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的柱面是61号柱面。所以，应先为61号柱面服务

5、，然后按移动臂由外向里移动的方向，依次为99、130、148、159、199柱面的访问者服务。当201号柱面的操作结束后，向里移动的方向已经无访问等待者，所以改变移动臂的前进方向，由里向外依次为32、15柱面的访问者服务。“电梯调度”与“最短寻找时间优先”都是要尽量减少移动臂时所花的时间。所不同的是：“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的那个柱面，这种选择可能导致移动臂来回改变移动方向；“电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个柱面的访问者，仅当沿移动臂的前进移动方向无访问等待者时，才改变移动臂的前进方向。由于移动臂改变方向是机械动作，速度相对较

6、慢，所以，电梯调度算法是一种简单、使用且高效的调度算法。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。 设计流程图：l FCFS流程图：l SCAN流程图l 总流程图四、课题设计代码#include #include#include#include const int MAXQUEUE=200; /义请求队列最大长度/磁道号请求结构体定义 typedef struct TRACK_Nodeint iGo;/访问的磁道号int iVisited;/磁道是否已经访问标志（1：已访问；0：末访问）TRACK; TRACK queueMAXQUEUE;

7、/磁道号请求队列数组int iReqNum=0;/磁道访问请求数int iStart=0;/磁头初始位置int iNow=0;/磁头当前位置int iSum=0;/总移动磁道数int iInput;/用户当前输入的整数char sFileName20;/文件名void Init()/初始化函数int i; for(i=0;iMAXQUEUE;i+)queuei.iGo=-1;/设置要访问的磁道号为不可能的数-1，以区别正常请求磁道号queuei.iVisited=0;/设置磁道是否已经访问标志为0：末访问 /void Init()void Reset()/重置访问标志、磁头当前位置、总移动磁道

8、数int i; for(i=0;iiReqNum;i+) queuei.iVisited=0; /设置磁道是否已经访问标志为0：末访问 printf( n请输入磁头的初始磁道号（整数）: ); scanf(%d,&iStart);/从标准输入获取用户当前输入的磁头初始位置iNow=iStart;/磁头当前位置iSum=0;/总移动磁道数 /void Reset()int ReadTrackFile() /读入磁道号流文件FILE *fp; int iTemp; coutsFileName; /从标准输入获取用户当前输入的文件名if(fp=fopen(sFileName,r)=NULL) cou

9、tendl错误：磁道号流文件 sFileName 打不开，请检查文件名和路径!endl;return -1;elsewhile(!feof(fp)/将文件中输入的磁道号依次存入磁道号请求队列数组 fscanf(fp,%d ,&iTemp); queueiReqNum.iGo=iTemp; iReqNum+;/磁道访问请求数 /if(fp=fopen(sFileName,r)=NULL)return 0; /void ReadTrackFile()void FCFS() /先来先服务调度算法int i; Reset();/重置访问标志、磁头当前位置、总移动磁道数coutendl-endl; co

10、ut先来先服务调度算法的调度结果: endlendl; cout 初始磁道号: iStartendl; cout序号 下一磁道号 移动的磁道数endl; for(i=0;iiReqNum;i+) cout i+1 queuei.iGo abs(queuei.iGo-iNow)endl;iSum+=abs(queuei.iGo-iNow);/累加总移动磁道数iNow=queuei.iGo;/设置磁头当前位置为当前访问磁道号 coutendl总调度次数: iReqNumendl;coutendl总移动磁道数: iSumendl;printf(n平均移动磁道数: %.2fnn,(float)iSum

11、 / (float)iReqNum); /void FCFS()void SCAN()/电梯调度算法 int i,j; int iNext;/下一磁道号 int iMinMove;/当前方向上最短寻道距离coutendl-endl; coutendl请选择磁头初始方向（1 OR 2）：endlendl;cout1 磁头初始向内endlendl2 磁头初始向外endlendliInput;/从标准输入获取用户当前输入的整数switch(iInput)/用户当前输入的整数case 1:/磁头初始向内Reset();/重置访问标志、磁头当前位置、总移动磁道数coutendl-endl; cout电梯

12、调度算法-磁头初始向内的调度结果: endlendl; cout 初始磁道号: iStartendl; cout序号 下一磁道号 移动的磁道数endl; for(i=0;iiReqNum;i+)iMinMove=9999; iNext=-1; for(j=0;j=iNow)if(abs(queuej.iGo-iNow)iMinMove) iNext=j; iMinMove=abs(queuej.iGo-iNow); /if(abs(queuej.iGo-iNow)=iNow) /for(j=0;jiReqNum;j+)if(iNext!=-1)cout i+1 queueiNext.iGo a

13、bs(queueiNext.iGo-iNow)endl;iSum+=abs(queueiNext.iGo-iNow); /累加总移动磁道数iNow=queueiNext.iGo;/设置磁头当前位置为当前访问磁道号queueiNext.iVisited=1;/设置磁道是否已经访问标志为1：已访问 /if(iNext!=-1)else/掉头向外 for(j=0;jiReqNum;j+)/寻找当前方向上寻道距离最短的末访问磁道号 if(queuej.iVisited=0)&(queuej.iGoiNow) if(abs(queuej.iGo-iNow)iMinMove)iNext=j; iMinMo

14、ve=abs(queuej.iGo-iNow); /for(j=0;jiReqNum;j+)cout i+1 queueiNext.iGo abs(queueiNext.iGo-iNow)endl;iSum+=abs(queueiNext.iGo-iNow); /累加总移动磁道数iNow=queueiNext.iGo; /设置磁头当前位置为当前访问磁道号queueiNext.iVisited=1;/设置磁道是否已经访问标志为1：已访问 /if(iNext!=-1) /for(i=0;iiReqNum;i+)coutendl总调度次数: iReqNumendl;coutendl总移动磁道数: i

15、Sumendl;printf(n平均移动磁道数: %.2fnn,(float)iSum / (float)iReqNum);break;case 2:/磁头初始向外 Reset();/重置访问标志、磁头当前位置、总移动磁道数coutendl-endl;coutendlendl电梯调度算法-磁头初始向外的调度结果: endlendl; cout 初始磁道号: iStartendl; cout序号 下一磁道号 移动的磁道数endl; for(i=0;iiReqNum;i+) iMinMove=9999; iNext=-1; for(j=0;jiReqNum;j+)/寻找当前方向上寻道距离最短的末访

16、问磁道号if(queuej.iVisited=0)&(queuej.iGo=iNow) if(abs(queuej.iGo-iNow)iMinMove)iNext=j; iMinMove=abs(queuej.iGo-iNow); /if(abs(queuej.iGo-iNow)iMinMove) /if(queuej.iVisited=0)&(queuej.iGo=iNow) /for(j=0;jiReqNum;j+)if(iNext!=-1) cout i+1 queueiNext.iGo abs(queueiNext.iGo-iNow)endl;iSum+=abs(queueiNext.

17、iGo-iNow);/累加总移动磁道数iNow=queueiNext.iGo;/设置磁头当前位置为当前访问磁道号queueiNext.iVisited=1;/设置磁道是否已经访问标志为1：已访问 else/掉头向内 for(j=0;jiNow)if(abs(queuej.iGo-iNow)iMinMove) iNext=j; iMinMove=abs(queuej.iGo-iNow); /if(abs(queuej.iGo-iNow)iNow)/for(j=0;jiReqNum;j+)cout i+1 queueiNext.iGo abs(queueiNext.iGo-iNow)endl;iS

18、um+=abs(queueiNext.iGo-iNow); /累加总移动磁道数iNow=queueiNext.iGo; /设置磁头当前位置为当前访问磁道号queueiNext.iVisited=1;/设置磁道是否已经访问标志为1：已访问/if(iNext!=-1)/for(i=0;iiReqNum;i+)coutendl总调度次数: iReqNumendl;coutendl总移动磁道数: iSumendl;printf(n平均移动磁道数: %.2fnn,(float)iSum / (float)iReqNum);break;default:printf(n输入错误!nn);return;/sw

19、itch(iInput) /void SCAN()void Version()/显示版权信息函数 coutendlendl; coutendl;cout 磁盘调度算法模拟系统 endl;coutendl;cout (c)All Right Reserved endl;cout 王利君&杜荣峰 endl;coutVersion 2012 build 1.0 endl;coutendl;coutendlendl; / void Version()void main() int i; bool bGoOn;/是否继续磁盘调度算法模拟的标志char sGoOn1;/用户输入是否继续磁盘调度算法模拟的字

20、母：y、Y、N、nVersion();/显示版权信息函数Init();/初始化函数if(ReadTrackFile()=-1) /读入磁道号流文件 printf(读入磁道号流文件失败!nn);elsebGoOn= true;while (bGoOn)coutendl-endl;cout从磁道号流文件 sFileName 所读入的磁道号流如下:endlendl; for(i=0;iiReqNum;i+)coutqueuei.iGo ; coutendlendl请求数为: iReqNumendlendl; iInput=-1;/用户输入的整数以选择算法coutendl请输入算法编号（1 OR 2

21、）选择调度算法：endlendl; cout1 先来先服务调度算法endlendl2 电梯调度算法endlendliInput;/从标准输入获取用户当前输入的整数switch(iInput)/用户输入的整数以选择算法case 1:FCFS();/先来先服务调度算法break;case 2:SCAN();/电梯调度算法break;default:printf(n输入的算法编号错误!nn);return;/switch(iInput)bGoOn= false;strcpy(sGoOn, );cout要继续进行磁盘调度算法模拟吗?(Y/N)endlsGoOn;bGoOn=(sGoOn0=y|sGoO

22、n0=Y); /while bGoOn/if(ReadTrackFile()=-1) 五、课题运行结果注意：实验前需要在工作区创建（如：1.txt）文件，然后在件中输入需要调度的磁道号。本次调试文件名为Test.txtTest.txt中内容为：55 58 39 18 90 160 150 38 184实验结果：六、总结杜荣峰：通过这次的课程设计使我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好而且还要不断进行实践，将所学的跟实践操作结合起来才能更好地巩固所学，才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的，实践能力与理论知

23、识同样重要。可以说此课程设计的理论难度并不大，但是若要深入发掘其中的东西，并且实际去编程实现，就遇到了相当大的难度。因为与之涉及的很多方面并没有学过，需要自己去自学和实践检验。所以在以后的学习中一方面我要不断的巩固自己所学的理论知识，一方面还要多参加实际操作工作以便提高自己的实际操作能力。其实这次课程设计的最大收获应该是找到了解决问题的几个很好的途径：1.讨论2.通过网络,在自己的网站上也收获了很多，共享让我们共同进步。此外，我学会了对程序的效用和算法的效率角度去思考。并体会到：问别人只能帮你开拓思路，真正解决问题还是要靠自己去摸索。当然讨论是很好的学习途径,它会让你事半功倍.由于时间不是很充

24、裕，程序中有很多值得改善的地方。 王利君：通过这次课程设计，系统的理解了磁盘调度算法的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。同时也提高了我对学习操作系统的积极性，虽然内容并不是很复杂，程序也不够完善和严谨，但是我们觉得设计的过程是相当重要的，从中我学到了很多，收获了很多，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。我觉得课程设计反映的是一个从理论到实际应用的过程，但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程。我觉得作为一名软件工程专业的学生，这次课程设计是很有意义的。在这次设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题不但要深入地理解，而且要不断地更正以前的错误思维。一切问题必须要靠自己一点一滴的解决。同时也感谢张老师的悉心指导！七、参考文献 计算机操作系统 西安电子科技大学出版社 作者：汤子赢、哲风屏、汤小舟VC+深入详解 电子工业出版社作者：孙鑫，余安萍数据结构 清华大学出版社 作者： 严蔚敏、吴伟民