操作系统课程设计-磁盘调度算法

1、摘要：本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，使磁盘调度的特点更简单明了，这里主要实现磁盘调度的四种算法，分别是：1、先来先服务算法（FCFS2、最短寻道时间优先算法（SSTF3、扫描算法（SCAN4、循环扫描算法（CSCAM启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送；因此，执行一次输入输出所花的时间有：寻找时间一一磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间一一指定扇区旋转到磁头下所需的时间。传送时间一一由磁头进程读写完成信息传送的时间，寻道时间一一指计算机在发

2、出一个寻址命令，到相应目标数据被找到所需时间；其中传送信息所花的时问，是在硬件设计时固定的，而寻找时间和延迟时间是与信息在磁盘上的位置有关；然后设计出磁盘调度的设计方式，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等，并给出详细的算法设计，对编码进行了测试与分析。最后进行个人总结与设计体会。关键词：最短寻道时间优先算法、扫描算法、总寻道长度前言12 .课程设计任务及要求32.1 设计任务32.2 设计要求33 .算法及数据结构33.1 算法的总体思想（流程）33.2 实现过程中用到的数据结构43.3 实现过程中用到的系统调用94 .程序设计与实现94.1 最短寻道时

3、间优先算法（SSTF模块94.1.1 程序流程图94.1.2 程序说明114.1.3 程序关键代码114.2 扫描算法（SCAN模块124.2.1 程序流程图124.2.2 程序说明144.2.3 程序关键代码144.3 实验结果155 .结论246 .参考文献247 .收获、体会和建议252.课程设计任务及要求2.1 设计任务1 .熟悉并掌握磁盘调度算法管理系统的设计方法，加强对所学各种调度算法及相应算法的特点了解。2. 掌握磁盘调度的基本概念，深刻体会各个算法的优缺点，以及算法间的相似点。2.2设计要求1）定义与算法相关的数据结构，如PCB队列等；2）实现2种不同的调度算法（可使用伪代码或

4、流程图进行分析）；3）算法执行结束时，应给出总的寻道长度；4）磁道访问序列随机生成，且要满足一定的数量要求（不少于100个）；5）系统实现必须提供一定的交互性，所需测试数据应当以文件形式提供或者由用户在测试过程中给出，不可将测试数据“写死”在系统实现代码中；6）必须给出足够的注释，注释量不得少于代码量的一半；7）对于系统中所使用到的系统调用（API函数），必须给出函数的定义原型、使用方法，参数较为复杂的，还应该给出参数的具体描述；3.算法及数据结构3.1 算法的总体思想（流程）总流程图开始3.2实现过程中用到的数据结构1.最短寻道时间优先（SSTF（从100号磁道开始）被访问的下一个磁道号移动

5、跑离（磁道数）5545583391918219072160701501038112184146平均寻道长度：55.3图aSSTF调度算法示例图图bSSTF算法流程示例图原磁道号随机组成的数组：cidao=55,58,39,18,90,160,150,38,184)排序后的数组=18,38,39,5,58,90,150,160,184);输入当前磁道号：now=10039555558585890909090now值:10090585518416016015015015018181818383838383939393955555555585858589090-90-90-now值：18150160

6、184图cSSTFT法队歹U示意图（按磁道访问顺序）3839555890392.扫描（SCAN算法（从100号磁道开始，向磁道号增加方向访问）被访问的下一个磁道号移动跑离（磁道数）1505016010184249094583255339163811820平均寻道长度：27.8图dSCAN算法示例图原磁道号随机组成的数组：cidao=55,58,39,18,90,160,150,38,184）排序后的数组=18,38,39,5,58,90,150,160,184）;输入当前磁道号：now=100选择磁道移动方向；以磁道号增加的方向移动为例：5890901841841841601601601601

7、5015015015015090now值：10015016018418383839393955555558585890909018418418416016C16015015C150now值:553938图eSCANT法队列示意图（按磁道访问顺序）555890184160150583.3实现过程中用到的系统调用系统模块调用关系图4.程序设计与实现4.1 最短寻道时间优先算法（SSTF）模块4.1.1 程序流程图，:开始')输入磁道号串调用SSTF阚数用冒泡法将磁道号从大到小排序结束4.1.2程序说明算法分析优点：相较于先来先服务算法（FCFS有更好的寻道性能，使每次的寻道时间最短。缺点：

8、易造成某个进程发生“饥饿”现象。最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。例如，如果现在读写磁头正在100号柱面上执行输出操作，而等待访问者依次要访问的柱面为55,58,39,18,90,160,150,38,184,那么，当100号柱面的操作结束后，应该先处理90号柱面的请求，然后到达58号柱面执行操作，随后处理55号柱面请求，后继操作的次序应该是39,38,18,150,160,184,采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，具有更

9、好的寻道性能，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF调度，FCF8引起读写头在盘面上的大范围移动，SSTF®找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF®找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。算法流程：输入磁头初始磁道号，序列长度，磁道号序列。选择磁盘调度算法（最短寻道时间优先调度（SSTF）或（扫描调度算法（SCAN）中的任意一个，若选择SSTF则输出各进程被调度的顺序，并计算总的寻道长度和平均寻道长度，选择关闭则结束磁盘调度。4.1.3程序关键代码for

10、(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)/*若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务*/(for(i=m-1;i>=0;i-)cout<<arrayi<<""sum=now-array0;)else11if(array0>=now)/*若当前磁道号小于请求序列中最小者，则直接由内向外依次给

11、予各请求服务*/while(l>=0)&&(r<m)/*当前磁道在请求序列范围内*/(*/if(now-arrayl)<=(arrayr-now)/*选择与当前磁道最近的请求给予服务(cout<<arrayl<<""sum+=now-arrayl;now=arrayl;l=l-1;4.2 扫描算法(SCAN)模块4.2.1 程序流程图12选择磁道扫描方向d=1从磁道最内端开始向外扫描向内扫描计算总寻道长度，并输出平均寻道长度13结束4.2.2 程序说明算法分析优点：排除了磁头在盘面局部位置上的往复移动，SCANJ法在

12、很大程度上消除了SST尊法的不公平性，但仍有利于对中间磁道的请求。缺点：新进来的访问此磁道的进程的请求会被大大地推迟。增加延迟。SCAN算法又称电梯调度算法。SCANT法是磁头前进方向上的最短查找时间优先算法。注：“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客张一、张二、张三在等候乘电梯。他们的要求是：张一在2层等待去10层；张二在5层等待去底层；张三在8层等待去15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张三从8层带到

13、15层，然后电梯换成下行方向，把乘客张二从5层带到底层，电梯最后再调换方向，把乘客张一从2层送到10层。我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨论。这里是：移动臂先由里向外移动，再由外向里移动。开始时，在100号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问100号柱面的操作结束后，沿臂移动方向最近的柱面是150号柱面。所以应先为150号柱面的访问者服务，然后是为160号柱面的访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问

14、者服务。在这种情况下为等待访问者服务的次序是184,90,58,55,39,38,18。算法流程：输入磁头初始磁道号，序列长度，磁道号序列。选择磁盘调度算法(最短寻道时间优先调度(SSTF)或(扫描调度算法(SCAN)中的任意一个，若选择SCAN则需要选择磁头移动方向是“向磁道号增加方向访问”或“向磁道号减少方向访问”，之后，输出各进程被调度的顺序，并计算总的寻道长度和平均寻道长度，选择关闭则结束磁盘调度。4.2.3 程序关键代码if(d=0)/*选择移动臂方向向内，则先向内扫描*/(for(j=l;j>=0;j-)(cout<<arrayj<<"&qu

15、ot;/*输出向内扫描的序列*/for(j=r;j<m;j+)/*磁头移动到最小号，则改变方向向外扫描未扫描的磁道*/(cout<<arrayj<<""/*输出向外扫描的序列*/sum=now-2*array0+arraym-1;14else/*选择移动臂方向向外，则先向外扫描*/(for(j=r;j<m;j+)(cout<<arrayj<<""/*输出向外扫描的序列*/)for(j=l;j>=0;j-)/*磁头移动到最大号，则改变方向向内扫描未扫描的磁道*/(cout<<ar

16、rayj<<"")sum=-now-array0+2*arraym-1;)ave=(float)(sum)/(float)(m);4.3 实验结果运行界面截图及相应代码1 .主界面voiddisplay()cout<<"nnnnOperatingSystemsCurriculumDesignn"cout<<"nIcout<<"ncout<<"ncout<<"ncout<<"ncout<<"ncout&

17、lt;<"ncout<<"ncout<<"ncout<<"ncout<<"ncout<<"n名称：磁盘调度工具：VisualStudio2010班级:1205作者：施静学号：21121402015cout<<"nn"system("pause");system("cls");C:UsersAdmiriistrfltor.QH-20140605VHPSdocumentsvisuaIstudio2010

18、ProjectssjOperatingSystensCiirriciilunDesign名称：磁盘调度工具：UisualStudio2010班级ra05作者:施静学号*211214020请懈Ss演二二2 .前言提示用户此程序实现的算法cout<<"【载入完成】"<<endl<<endl;cout<<"前言"<<endl<<endl;cout<<"欢迎使用磁盘调度算法系统，本程序实现了常用的磁盘调度算法如下所示:nn"cout<<"

19、最短寻道时间优先(SSTF：最短寻道时间优先算法要求访问的磁盘与当前磁头所在的n"cout<<"磁盘距离最近，以使每次的寻道时间最短。nn"cout<<"扫描算法(SCAN)电梯调度：扫描算法不仅考虑到欲访问的磁道与当前磁道的距离n"cout<<"更优先考虑的是磁头的当前移动方向。nn"system("pause");system("cls");/清屏16，.C:UsersAdministfator.QH-20140605VHPSdocumentsv

20、i£ualstudio2010Proiect式可需弛.1载入完成】刖三欢迎使用磁盘调度算法系统，本程序实现了常用的磁盘调度算法如下所示：最短寻道时间优先（SSTF）;最短寻道时间优先算法要求访问的磁盘与当前斑头,在贯盘距离最近，以使每次的寻道时间最屈扫喳算法CAN电叠谡度;扫描算法不仅考虑到欲访问的磁道与当前磁道的距离更优先考虑苗富磁头的雪箭籁动方向.请按任意键继续-.3 .用户选择所使用的算法（先随机生成101个磁道号）voidshowMenu（intcidao,intn）intchoice;while（true）cout<<"请您选择喜欢的算法来实现调度（输

21、入1-3）:"cout<<"nI1cout<<"ncout<<"n"1.最短寻道时间优先（SSTF）|"cout<<"n"cout<<"n2.扫描算法(SCAN)"cout<<"n"cout<<"n3.退出(EXIT)"cout<<"n"cout<<"n11n"cout<<endl;while(tr

22、ue)cout<<"现在您选择的算法号是(1-3):"cin>>choice;switch(choice)/*case1:FCFS(a,n);break;*/case1:SSTF(cidao,n);17break;case2:SCAN(cidao,n);break;case3:cout<<"n要退出系统了欢迎使用本系统n"exit(0);C!U£ersAdininjstratcir.QH-20140605VHPSdocumentsvi£ualstudio2010Proi请输入隘道的个数:1奥2扫描算

23、法SCAN）3.退出EXITL现在您选择的算法号是（工3）二8&8279S0生成的随机磁道号分别为:251153243236635412719728611216&5220610S200IIS85148263194172212232132365638138152531141957118614215191111252971764414&2041163133225272992921871702952321996。I回29174502416816108229224101412918156257707528S202S247741915711841984272203013Q1491

24、1980254109298283请您选择喜欢的算法来实现调度输入=1.最短寻道时间优先SgTF,184.最短寻道时间优先算法/*最短寻道时间优先调度算法*/voidSSTF(intcidao,intm)(system("cls");intk=1;intnow,l,r;inti,j,sum=0;inta;charstr100;floatave;cidao=bubble(cidao,m);/调用冒泡排序算法排序cout<<"请输入当前的磁道号:C:cin>>str;/对输入数据进行有效性判断a=decide(str);if(a=0)(cout&

25、lt;<"输入数据的类型错误，请重新输入！"<<endl;gotoC;elsenow=trans(str,a);/输入当前磁道号if(cidaom-1<=now)/若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务(cout<<"磁盘扫描序列为："for(i=m-1;i>=0;i-)cout<<cidaoi<<""sum=now-cidao0;if(cidao0>=now)/若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务(cou

26、t<<"磁盘扫描序列为："for(i=0;i<m;i+)cout<<cidaoi<<""sum=cidaom-1-now;if(now>cidao0&&now<cidaom-1)/若当前磁道号大于请求序列中最小者且小于最大者(cout<<"磁盘扫描序列为："while(cidaok<now)/确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。(k+;19)l=k-1;r=k;while(l>=0)&

27、;&(r<m)/当前磁道在请求序列范围内(if(now-cidaol)<=(cidaor-now)/选择与当前磁道最近的请求给予服务(cout<<cidaol<<""sum+=now-cidaol;now=cidaol;l=l-1;)else(cout<<cidaor<<""sum+=cidaor-now;now=cidaor;r=r+1;)if(l=-1)/磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道(for(j=r;j<m;j+)(cout<<cidaoj&l

28、t;<"")sum+=cidaom-1-cidao0;)else/磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道(for(j=l;j>=0;j-)(cout<<cidaoj<<"")sum+=cidaom-1-cidao0;)ave=(float)(sum)/(float)(m);/求平均寻道长度cout<<endl;cout<<"总的寻道长度："<<sum<<endl;cout<<"平均寻道长度："<<

29、ave<<endl;cout<<"请按任意键返回系统菜单"<<endl;getch();showMenu(cidao,m);/回到主界面20寻道时间优先(SSTF)算法实现界面C:UsersAdmini5trator.QH-20140605VHPSdocumentsvi£ualMudio2010Proiect5sj.Li_i_Ei排序后的磁盘序列为：工78913141618192324272910516321529574?580828586969810113314614814915215315619719820820220420

30、62122E02632822832B&28S292S35456S7637071611912512713S13291841871911941956243250251254257，：口道f勺；56987163707156575453527475808250474442858696984136309125127130418719119413219513319714619814814?2B02021S22B4153如61011562121051632151061662192的均按道道意寻寻任51£键25425?26H度：355度:：3*51485法回系统菜单26328228328&a

31、mp;28829229529730363841424447S010610810911111211416E168170172174176219220224225229232297299292724231918161410810911111211411G16817017217417&179220224225229232236299(2)扫描(SCAN算法/*扫描调度算法*/voidSCANQntcidao,intn)/先要给出当前磁道号和移动臂的移动方向(inttemp;inti,j;intnow;intsum;for(i=0;i<n;i+)/给磁道号排序for(j=i+1;j<

32、;n;j+)if(cidaoi>cidaoj)temp=cidaoi;cidaoi=cidaoj;cidaoj=temp;21)cout<<"n按非递减顺序排列好的磁道：n"for(i=0;i<n;i+)/输出排好序的磁道号cout<<cidaoi<<""cout<<endl;cout<<"n请输入当前的磁道号："cin>>now;/用户自定义当前磁道号if(cidaon-1<=now)for(i=n-1;i>=0;i-)cout<&

33、lt;cidaoi<<""sum=now-cidao0;)else/cidaon-1>nowif(cidao0>=now)for(i=0;i<n;i+)cout<<cidaoi<<""sum=cidaon-1-now;)else/cidao0<now&&cidaon-1>nowintpointer;intlocation=1;intleft,right;while(cidaolocation<now)location+;left=location-1;right=lo

34、cation;cout<<"n请输入当前磁头想要移动的方向(1磁道号增加方向，0磁道号减小方向):"loop:cin>>pointer;cout<<"n磁盘调度顺序为:n"if(pointer=0|pointer=1)if(pointer=0)/磁头向左移动到最小号，再改变方向向外扫描未扫描的磁道for(j=left;j>=0;j-)cout<<cidaoj<<""for(j=right;j<n;j+)cout<<cidaoj<<"

35、;"sum=now+cidaon-1-2*cidao0;cout<<endl;)if(pointer=1)/磁头向右移动到最大号，再改变方向向内扫描未扫描的磁道22for(j=right;j<n;j+)cout<<cidaoj<<""for(j=left;j>=0;j-)cout<<cidaoj<<""sum=2*cidaon-1-now-cidao0;/求总寻道长度cout<<endl;else(cout<<"n输入不合法！请输入0或1:

36、n"gotoloop;cout<<"nn需要移动的总磁道数为："<<sum<<endl;cout<<"请按任意键返回系统菜单"<<endl;getch();showMenu(cidao,n);/回到主界面C:UsersAdministratorQH-20140605VHPSdocumentsvisualstudio2010Proj.17_*八*13.退出EXIT)L,_J|请您选择喜欢的算法来实现调度输入IT”1 .最短寻道时间优先：2 .扫描算法懦的心现在您选择的算法号是(1-3)：

37、2按非递减顺序排列好的磁道工1?891314161«1923242?293036384142444?50525354565?63?07174758SS28586969SIffi.10S1061881991111121141161191251271301321331461481491521531561631661631701721741761791B41871911941951971982002022042062122152192202242252292322362432582512542572&026328228328628829229529?299请输入当前的磁道号;160请输入当前磁头想要移动的方向<工磁道号增加方向，0磁道号减小方向1磁盘调度顺序为二23CUsersAdministrator.QH-20140605VHPSdccurrient£visualstudio2010ProjectsEj.按非递减顺序排列好的磁道；1?891314161«192324272930363841424447565253545657E37H7174758032858