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

前 言摘要：本课程设计目标是经过设计一个磁盘调度模拟系统，从而使磁盘调度算法愈加形象化，使磁盘调度特点更简单明了，这里关键实现磁盘调度四种算法，分别是：1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN）。 开启磁盘实施输入输出操作时，要把移动臂移动到指定柱面，再等候指定扇区旋转到磁头位置下，然后让指定磁头进行读写，完成信息传送；所以，实施一次输入输出所花时间有： 寻求时间磁头在移动臂带动下移动到指定柱面所花时间。 延迟时间指定扇区旋转到磁头下所需时间。 传送时间由磁头进程读写完成信息传送时间，寻道时间指计算机在发出一个寻址命令，到对应目标数据被找到所需时间；其中传送信息所花时间，是在硬件设计时固定，而寻求时间和延迟时间是和信息在磁盘上位置相关；然后设计出磁盘调度设计方法，包含算法思绪、步骤，和要用到关键数据结构、函数模块及其之间调用关系等，并给出具体算法设计，对编码进行了测试和分析。 最终进行个人总结和设计体会。关键词：最短寻道时间优先算法、扫描算法、总寻道长度.目 录前 言22. 课程设计任务及要求42.1 设计任务42.2 设计要求43. 算法及数据结构53.1算法总体思想（步骤）53.2 实现过程中用到数据结构63.3 实现过程中用到系统调用114. 程序设计和实现114.1 最短寻道时间优先算法（SSTF）模块114.1.1程序步骤图114.1.2 程序说明134.1.3 程序关键代码134.2扫描算法（SCAN）模块144.2.1 程序步骤图144.2.2 程序说明164.2.3 程序关键代码164.3 试验结果175. 结论266. 参考文件267. 收获、体会和提议272. 课程设计任务及要求2.1 设计任务 1.熟悉并掌握磁盘调度算法管理系统设计方法，加强对所学多种调度算法及对应算法特点了解。 2.掌握磁盘调度基础概念，深刻体会各个算法优缺点，和算法间相同点。 2.2 设计要求 1)定义和算法相关数据结构，如PCB、队列等；2） 实现2种不一样调度算法（可使用伪代码或步骤图进行分析）；3） 算法实施结束时，应给出总寻道长度；4） 磁道访问序列随机生成，且要满足一定数量要求（不少于100个）；5）系统实现必需提供一定交互性，所需测试数据应该以文件形式提供或由用户在测试过程中给出，不可将测试数据“写死”在系统实现代码中；6）必需给出足够注释，注释量不得少于代码量二分之一；7）对于系统中所使用到系统调用（API函数），必需给出函数定义原型、使用方法，参数较为复杂，还应该给出参数具体描述；3. 算法及数据结构 3.1算法总体思想（步骤） 开始输入磁道个数生成随机磁道号用户输入所选择算法进行磁盘调度输入数字为1-2？输出排序后磁盘序列用户输入目前磁道号显示磁盘调度次序输入为3？退出程序 结束总步骤图 Y N Y N 3.2 实现过程中用到数据结构 1.最短寻道时间优先（SSTF）（从100号磁道开始）被访问下一个磁道号移动距离（磁道数）5545583391918219072160701501038112184146平均寻道长度：55.3 图a SSTF调度算法示例图ciidao=55,58,39,18,90,160,150,38,184（可随机生成多个）用户输入目前磁道号now，比较目前磁道到每个磁道移动距离，选择最短距离磁道进行移动。now指向目前磁道号，计算寻道长度sum。用冒泡法对磁道数组进行排序 返回内侧（外侧）扫描 将目前磁道号和剩下没有访问磁道号进行比较，反复上述操作。并计算平均寻道长度ave。 图b SSTF算法步骤示例图原磁道号随机组成数组：cidao=55,58,39,18,90,160,150,38,184；排序后数组=18,38,39,5,58,90,150,160,184；输入目前磁道号：now=100； 38 39 39 55 55 55 58 58 58 58 90 90 90 90 90now值:100 90 58 55 39 184 160 160 150 150 150 18 18 18 18 38 38 38 38 39 39 39 39 55 55 55 55 58 58 58 58 90 90 90 90 now值：18 150 160 184 图c SSTF算法队列示意图(按磁道访问次序)2.扫描（SCAN）算法（从100号磁道开始，向磁道号增加方向访问）被访问下一个磁道号移动距离（磁道数）1505016010184249094583255339163811820平均寻道长度：27.8 图d SCAN算法示例图原磁道号随机组成数组：cidao=55,58,39,18,90,160,150,38,184；排序后数组=18,38,39,5,58,90,150,160,184；输入目前磁道号：now=100；选择磁道移动方向；以磁道号增加方向移动为例： 55 58 58 90 90 90 184 184 184 184 160 160 160 160 160 150 150 150 150 150 150now值：100 150 160 184 90 58 18 38 38 39 39 39 55 55 55 58 58 58 90 90 90 184 184 184 160 160 160 150 150 150 now值:55 39 38 图e SCAN算法队列示意图（按磁道访问次序） 3.3 实现过程中用到系统调用系统模块调用关系图磁盘调度算法模拟系统最短寻道时间优先扫描算法退出 4. 程序设计和实现 4.1 最短寻道时间优先算法（SSTF）模块 4.1.1程序步骤图输入磁道号串用冒泡法将磁道号从大到小排序判定now大小调用SSTF()函数输入目前磁道号now开始结束优先服务离now最近 磁道移动方向，再掉头服务计算总寻道长度，并输出移动平均寻道长度直接从大到小给磁道服务直接从小到大给磁道服务找到离now寻道时间最短磁道now<=cidao0 cidao0<now<cidaom-1 now>=cidaom-14.1.2 程序说明算法分析 优点：相较于先来先服务算法（FCFS）有愈加好寻道性能，使每次寻道时间最短。 缺点：易造成某个进程发生“饥饿”现象。 最短寻求时间优先调度算法总是从等候访问者中挑选寻求时间最短那个请求先实施，而不管访问者到来前后次序。比如，假如现在读写磁头正在100号柱面上实施输出操作，而等候访问者依次要访问柱面为55,58,39,18,90,160,150,38,184，那么，当100号柱面操作结束后，应该先处理90号柱面请求，然后抵达58号柱面实施操作，随即处理55号柱面请求，后继操作次序应该是39,38,18,150,160,184.采取最短寻求时间优先算法决定等候访问者实施操作次序时，读写磁头总共移动多个柱面距离，和先来先服务、算法比较，大幅度地降低了寻求时间，含有愈加好寻道性能，所以缩短了为各访问者请求服务平均时间，也就提升了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引发读写头在盘面上大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）请求作为下一次服务对象。SSTF查找模式有高度局部化倾向，会推迟部分请求服务，甚至引发无限拖延（又称饥饿）。 算法步骤：输入磁头初始磁道号，序列长度，磁道号序列。选择磁盘调度算法（最短寻道时间优先调度(SSTF)）或（扫描调度算法(SCAN)）中任意一个，若选择SSTF，则输出各进程被调度次序，并计算总寻道长度和平均寻道长度，选择关闭则结束磁盘调度。4.1.3 程序关键代码for(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;else if(array0>=now) /*若目前磁道号小于请求序列中最小者，则直接由内向外依次给各请求服务*/ 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 程序步骤图开始输入磁道号串调用SCAN（）函数调用冒泡排序法进行排序输入目前磁道号now从磁道最外端开始向内扫描计算总寻道长度，并输出平均寻道长度从磁道最内端开始向外扫描向内扫描向外扫描选择磁道扫描方向结束 d=1 d=04.2.2 程序说明算法分析 优点：排除了磁头在盘面局部位置上往复移动，SCAN算法在很大程度上消除了SSTF算法不公平性，但仍有利于对中间磁道请求。 缺点：新进来访问此磁道进程请求会被大大地推迟。增加延迟。 SCAN 算法又称电梯调度算法。SCAN算法是磁头前进方向上最短查找时间优先算法。 注：“电梯调度”算法是从移动臂目前位置开始沿着臂移动方向去选择离目前移动臂最近那个柱访问者，假如沿臂移动方向无请求访问时，就改变臂移动方向再选择。这好比乘电梯，假如电梯已向上运动到4层时，依次有3位乘客张一、张二、张三在等候乘电梯。她们要求是：张一在2层等候去10层；张二在5层等候去底层；张三在8层等候去15层。因为电梯现在运动方向是向上，所以电梯形成是先把乘客张三从8层带到15层，然后电梯换成下行方向，把乘客张二从5层带到底层，电梯最终再调换方向，把乘客张一从2层送到10层。 我们仍用前述同一例子来讨论采取“电梯调度”算法情况。因为磁盘移动臂初始方向有两个，而该算法是和移动臂方向相关，所以分成两种情况来讨论。这里是：移动臂先由里向外移动，再由外向里移动。开始时，在100号柱面实施操作读写磁头移动臂方向是由里向外，趋向32号柱面位置，所以，当访问100号柱面操作结束后，沿臂移动方向最近柱面是150号柱面。所以应先为150号柱面访问者服务，然后是为160号柱面访问者服务。以后，因为在向外移方向已无访问等候者，故改变移动臂方向，由外向里依次为各访问者服务。在这种情况下为等候访问者服务次序是184,90,58,55,39,38,18。 算法步骤：输入磁头初始磁道号，序列长度，磁道号序列。选择磁盘调度算法（最短寻道时间优先调度(SSTF)）或（扫描调度算法(SCAN)）中任意一个，若选择SCAN，则需要选择磁头移动方向是“向磁道号增加方向访问”或“向磁道号降低方向访问”，以后，输出各进程被调度次序，并计算总寻道长度和平均寻道长度，选择关闭则结束磁盘调度。4.2.3 程序关键代码if(d=0) /*选择移动臂方向向内，则先向内扫描*/ for(j=l;j>=0;j-) cout<<arrayj<<" " /*输出向内扫描序列*/ for(j=r;j<m;j+) /*磁头移动到最小号，则改变方向向外扫描未扫描磁道*/ cout<<arrayj<<" " /*输出向外扫描序列*/ sum=now-2*array0+arraym-1; else /*选择移动臂方向向外，则先向外扫描*/ for(j=r;j<m;j+) cout<<arrayj<<" " /*输出向外扫描序列*/ for(j=l;j>=0;j-) /*磁头移动到最大号，则改变方向向内扫描未扫描磁道*/ cout<<arrayj<<" " sum=-now-array0+2*arraym-1; ave=(float)(sum)/(float)(m);4.3 试验结果 运行界面截图及对应代码1. 主界面void display() cout<<"nnnn Operating Systems Curriculum Designn" cout<<"n "cout<<"n "cout<<"n 名称: 磁盘调度 " cout<<"n "cout<<"n 工具: Visual Studio " cout<<"n "cout<<"n 班级:1205 " cout<<"n "cout<<"n 作者:施静 " cout<<"n "cout<<"n 学号： " cout<<"n "cout<<"n n" system("pause");system("cls");2. 序言 提醒用户此程序实现算法cout<<"【载入完成】"<<endl<<endl;cout<<" 序言"<<endl<<endl;cout<<" 欢迎使用磁盘调度算法系统，本程序实现了常见磁盘调度算法以下所表示：nn"cout<<" 最短寻道时间优先（SSTF）：最短寻道时间优先算法要求访问磁盘和目前磁头所在n"cout<<" 磁盘距离最近，以使每次寻道时间最短。nn"cout<<" 扫描算法(SCAN)电梯调度：扫描算法不仅考虑到欲访问磁道和目前磁道距离n"cout<<" 更优先考虑是磁头目前移动方向。nn" system("pause");system("cls");/清屏3. 用户选择所使用算法（先随机生成101个磁道号）void showMenu(int cidao,int n) int choice; while(true) cout<<"请您选择喜爱算法来实现调度(输入1-3):" cout<<"n " cout<<"n " cout<<"n 1.最短寻道时间优先(SSTF) |" cout<<"n " cout<<"n 2.扫描算法(SCAN) " cout<<"n " cout<<"n 3.退出(EXIT) " cout<<"n " cout<<"n n" cout<<endl; while(true) cout<<"现在您选择算法号是（1-3）：" cin>>choice; switch(choice) /*case 1: FCFS(a,n); break;*/ case 1: SSTF(cidao,n); break; case 2: SCAN(cidao,n); break; case 3: cout<<"n要退出系统了欢迎使用本系统n" exit(0); 4. 最短寻道时间优先算法/*最短寻道时间优先调度算法*/void SSTF(int cidao,int m) system("cls"); int k=1; int now,l,r; int i,j,sum=0; int a; char str100; float ave; cidao=bubble(cidao,m); /调用冒泡排序算法排序 cout<<"请输入目前磁道号：" C: cin>>str; /对输入数据进行有效性判定 a=decide(str); if(a=0) cout<<"输入数据类型错误,请重新输入！"<<endl; goto C; else now=trans(str,a); /输入目前磁道号 if(cidaom-1<=now) /若目前磁道号大于请求序列中最大者，则直接由外向内依次给各请求服务 cout<<"磁盘扫描序列为：" for(i=m-1;i>=0;i-) cout<<cidaoi<<" " sum=now-cidao0; if(cidao0>=now) /若目前磁道号小于请求序列中最小者，则直接由内向外依次给各请求服务 cout<<"磁盘扫描序列为：" for(i=0;i<m;i+) cout<<cidaoi<<" " sum=cidaom-1-now; if(now>cidao0&&now<cidaom-1) /若目前磁道号大于请求序列中最小者且小于最大者 cout<<"磁盘扫描序列为：" while(cidaok<now) /确定目前磁道在已排序列中位置，后面算法全部用到了，能够直接复制后少许修改，节省时间。 k+; l=k-1; r=k; while(l>=0)&&(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<<" " 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<<"平均寻道长度： "<<ave<<endl; cout<<"请按任意键返回系统菜单"<<endl; getch(); showMenu(cidao,m); /回到主界面最短寻道时间优先（SSTF）算法实现界面 （2） 扫描（SCAN）算法/*扫描调度算法*/void SCAN(int cidao,int n)/先要给出目前磁道号和移动臂移动方向int temp;int i,j;int now;int sum;for(i=0;i<n;i+) /给磁道号排序 for(j=i+1;j<n;j+) if(cidaoi>cidaoj) temp=cidaoi; cidaoi=cidaoj; cidaoj=temp; 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<<cidaoi<<" " sum=now-cidao0; else /cidaon-1>now if(cidao0>=now) for(i=0;i<n;i+) cout<<cidaoi<<" " sum=cidaon-1-now; else /cidao0<now && cidaon-1>now int pointer; int location=1; int left,right; while(cidaolocation<now) location+; left=location-1; right=location; 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<<" " sum=now+cidaon-1-2*cidao0; cout<<endl; if(pointer=1)/磁头向右移动到最大号，再改变方向向内扫描未扫描磁道 for(j=right;j<n;j+) cout<<cidaoj<<" " for(j=left;j>=0;j-) cout<<cidaoj<<" " sum=2*cidaon-1-now-cidao0;/求总寻道长度 cout<<endl; else