操作系统课程设计
骨连接-父子情深的句子
2023年3月18日发(作者：泰安南关中学)1
前言
摘要：本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更
加形象化，使磁盘调度的特点更简单明了，这里主要实现磁盘调度的四种算法，分别
是：1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法
（SCAN）4、循环扫描算法（CSCAN）。启动磁盘执行输入输出操作时，要把移动臂
移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读
写，完成信息传送；因此，执行一次输入输出所花的时间有：寻找时间——磁头在
移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所
需的时间。传送时间——由磁头进程读写完成信息传送的时间，寻道时间——指计
算机在发出一个寻址命令，到相应目标数据被找到所需时间；其中传送信息所花的时
间，是在硬件设计时固定的，而寻找时间和延迟时间是与信息在磁盘上的位置有关；
然后设计出磁盘调度的设计方式，包括算法思路、步骤，以及要用到的主要数据结构、
函数模块及其之间的调用关系等，并给出详细的算法设计，对编码进行了测试与分析。
最后进行个人总结与设计体会。
关键词：最短寻道时间优先算法、扫描算法、总寻道长度.
2
目录
前言......................................................1
2.课程设计任务及要求........................................3
2.1设计任务..............................................3
2.2设计要求..............................................3
3.算法及数据结构............................................3
3.1算法的总体思想（流程）................................3
3.2实现过程中用到的数据结构..............................4
3.3实现过程中用到的系统调用..............................9
4.程序设计与实现............................................9
4.1最短寻道时间优先算法（SSTF）模块......................9
4.1.1程序流程图.......................................9
4.1.2程序说明.......................................11
4.1.3程序关键代码...................................11
4.2扫描算法（SCAN）模块.................................12
4.2.1程序流程图.........................................12
4.2.2程序说明.......................................14
4.2.3程序关键代码...................................14
4.3实验结果.............................................15
5.结论.....................................................24
6.参考文献.................................................24
7.收获、体会和建议.........................................25
3
2.课程设计任务及要求
2.1设计任务
1.熟悉并掌握磁盘调度算法管理系统的设计方法，加强对所学各种调度算
法及相应算法的特点了解。
2.掌握磁盘调度的基本概念，深刻体会各个算法的优缺点，以及算法间的相
似点。
2.2设计要求
1)定义与算法相关的数据结构，如PCB、队列等；
2）实现2种不同的调度算法（可使用伪代码或流程图进行分析）；
3）算法执行结束时，应给出总的寻道长度；
4）磁道访问序列随机生成，且要满足一定的数量要求（不少于100个）；
5）系统实现必须提供一定的交互性，所需测试数据应当以文件形式提供或者由
用户在测试过程中给出，不可将测试数据“写死”在系统实现代码中；
6）必须给出足够的注释，注释量不得少于代码量的一半；
7）对于系统中所使用到的系统调用（API函数），必须给出函数的定义原型、使
用方法，参数较为复杂的，还应该给出参数的具体描述；
3.算法及数据结构
3.1算法的总体思想（流程）
4
总流程图
YN
YN
3.2实现过程中用到的数据结构
1.最短寻道时间优先（SSTF）
开始
输入磁道的个数
生成随机的磁道
用户输入所选择的算法进行磁盘调度
输入数字为
1-2？
输出排序后
的磁盘序列
用户输入当
前磁道号
显示磁盘调
度顺序
输入为3？
退出程序
结束
5
（从100号磁道开始）
被访问的下一个磁道号移动距离（磁道数）
5545
583
3919
1821
9072
16070
15010
38112
184146
平均寻道长度：55.3
图aSSTF调度算法示例图
用冒泡法对磁道数组进行排序
返回内侧（外侧）扫描
图bSSTF算法流程示例图
原磁道号随机组成的数组：cidao[]={55,58,39,18,90,160,150,38,184}；
排序后的数组={18,38,39,5,58,90,150,160,184}；
输入当前磁道号：now=100；
ciidao[]={55,58,39,18,90,160,150,38,184}（可随机生成多个）
用户输入当前磁道号now，比较当前磁道到每个磁道的移动距
离，选择最短距离的磁道进行移动。now指向当前磁道号，计
算寻道长度sum。
将当前磁道号与剩余没有访问的磁道号进行比
较，重复上述操作。并计算平均寻道长度ave。
6
38
3939
555555
58585858
9090909090
now值:1
184
160160
150150150
18181818
38383838
39393939
55555555
58585858
90909090
now值：
图cSSTF算法队列示意图(按磁道访问顺序)
7
2.扫描（SCAN）算法
（从100号磁道开始，向磁道号增加方向访问）
被访问的下一个磁道号移动距离（磁道数）
15050
16010
18424
9094
5832
553
3916
381
1820
平均寻道长度：27.8
图dSCAN算法示例图
原磁道号随机组成的数组：cidao[]={55,58,39,18,90,160,150,38,184}；
排序后的数组={18,38,39,5,58,90,150,160,184}；
输入当前磁道号：now=100；
选择磁道移动方向；
以磁道号增加的方向移动为例：
8
55
5858
909090
4
160
150150
now值：1058
18
3838
393939
555555
585858
909090
184184184
160160160
150150150
now值:553938
图eSCAN算法队列示意图（按磁道访问顺序）
9
3.3实现过程中用到的系统调用
系统模块调用关系图
4.程序设计与实现
4.1最短寻道时间优先算法（SSTF）模块
4.1.1程序流程图
磁盘调度算法模拟系统
最
短
寻
道
时
间
优
先
扫
描
算
法
退
出
10
now<=cidao[0]cidao[0] now>=cidao[m-1] 输入磁道号串 用冒泡法将磁道号从大到小排序 判断now的大小 调用SSTF()函数 输入当前磁道号 开始 结束 优先服务离now最近的磁 道移动方向，再掉头服务 计算总寻道长度，并输出移动的平 均寻道长度 直接从大到小给 予磁道服务 直接从小到大给 予磁道服务 找到离now寻道 时间最短的磁道 11 4.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 for(j=i+1;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< sum=now-array[0]; } else 12 if(array[0]>=now)/*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予 各请求服务*/ while((l>=0)&&(r { if((now-array[l])<=(array[r]-now))/*选择与当前磁道最近的请求给予服务*/ { cout< sum+=now-array[l]; now=array[l]; l=l-1; } 4.2扫描算法（SCAN）模块 4.2.1程序流程图 13 d=1 d=0 开始 输入磁道号串 调用SCAN（）函数 调用冒泡排序法进行排序 输入当前磁道号now 从磁道最外端 开始向内扫描 计算总寻道长度，并 输出平均寻道长度 从磁道最内端 开始向外扫描 向内扫描 向外扫描 选择磁道扫描方向 结束 14 4.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< } for(j=r;j { cout< } sum=now-2*array[0]+array[m-1]; } 15 else/*选择移动臂方向向外，则先向外扫描*/ { for(j=r;j { cout< } for(j=l;j>=0;j--)/*磁头移动到最大号，则改变方向向内扫描未扫描的磁道*/ { cout< } sum=-now-array[0]+2*array[m-1]; } ave=(float)(sum)/(float)(m); 4.3实验结果 运行界面截图及相应代码 1.主界面 voiddisplay(){ cout<<"nnnnOperatingSystemsCurriculumDesignn"; cout<<"n╔———————————————————————————————╗ "; cout<<"n││ "; cout<<"n│名称:磁盘调度│ "; cout<<"n││ "; cout<<"n│工具:VisualStudio2010│ "; cout<<"n││ "; cout<<"n│班级:1205│ "; cout<<"n││ "; cout<<"n│作者:施静│ "; cout<<"n││ "; cout<<"n│学号：211214020│ "; cout<<"n││ "; 16 cout<<"n╚———————————————————————————————╝ n"; system("pause"); system("cls"); 2.前言提示用户此程序实现的算法 cout<<"【载入完成】"< cout<<"前言"< cout<<"欢迎使用『磁盘调度算法系统』，本程序实现了常用的磁盘调度算法如下所示： nn"; cout<<"①最短寻道时间优先（SSTF）：最短寻道时间优先算法要求访问的磁盘与当前 磁头所在的n"; cout<<"磁盘距离最近，以使每次的寻道时间最短。nn"; cout<<"②扫描算法(SCAN)电梯调度：扫描算法不仅考虑到欲访问的磁道与当前磁道的 距离n"; cout<<"更优先考虑的是磁头的当前移动方向。nn"; system("pause"); system("cls");//清屏 17 3.用户选择所使用的算法（先随机生成101个磁道号） voidshowMenu(intcidao[],intn){ intchoice; 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< while(true){ cout<<"现在您选择的算法号是（1-3）："; cin>>choice; switch(choice){/*case1: FCFS(a,n); break;*/ case1: SSTF(cidao,n); 18 break; case2: SCAN(cidao,n); break; case3: cout<<"n要退出系统了欢迎使用本系统n"; exit(0); } } } } 19 4.最短寻道时间优先算法 /**********************最短寻道时间优先调度算法********************/ voidSSTF(intcidao[],intm) { system("cls"); intk=1; intnow,l,r; inti,j,sum=0; inta; charstr[100]; floatave; cidao=bubble(cidao,m);//调用冒泡排序算法排序 cout<<"请输入当前的磁道号："; C:cin>>str;//对输入数据进行有效性判断 a=decide(str); if(a==0) { cout<<"输入数据的类型错误,请重新输入！"< gotoC; } else now=trans(str,a);//输入当前磁道号 if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务 { cout<<"磁盘扫描序列为："; for(i=m-1;i>=0;i--) cout< sum=now-cidao[0]; } if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 { cout<<"磁盘扫描序列为："; for(i=0;i cout< sum=cidao[m-1]-now; } if(now>cidao[0]&&now { cout<<"磁盘扫描序列为："; while(cidao[k] 接复制后少量修改，节省时间。 { k++; 20 } l=k-1; r=k; while((l>=0)&&(r { if((now-cidao[l])<=(cidao[r]-now))//选择与当前磁道最近的请求给予服务 { cout< sum+=now-cidao[l]; now=cidao[l]; l=l-1; } else { cout< sum+=cidao[r]-now; now=cidao[r]; r=r+1; } } if(l==-1)//磁头移动到序列的最小号，返回外侧扫描仍未扫描的磁道 { for(j=r;j { cout< } sum+=cidao[m-1]-cidao[0]; } else//磁头移动到序列的最大号，返回内侧扫描仍未扫描的磁道 { for(j=l;j>=0;j--) { cout< } sum+=cidao[m-1]-cidao[0]; } } ave=(float)(sum)/(float)(m);//求平均寻道长度 cout< cout<<"总的寻道长度："< cout<<"平均寻道长度："< cout<<"请按任意键返回系统菜单"< getch(); showMenu(cidao,m);//回到主界面 21 } 最短寻道时间优先（SSTF）算法实现界面 （2）扫描（SCAN）算法 /*****************************扫描调度算法*******************************/ voidSCAN(intcidao[],intn)//先要给出当前磁道号和移动臂的移动方向 { inttemp; inti,j; intnow; intsum; for(i=0;i for(j=i+1;j if(cidao[i]>cidao[j]){ temp=cidao[i]; cidao[i]=cidao[j]; cidao[j]=temp; 22 } } cout<<"n按非递减顺序排列好的磁道:n"; for(i=0;i cout< cout< cout<<"n请输入当前的磁道号:"; cin>>now;//用户自定义当前磁道号 if(cidao[n-1]<=now) { for(i=n-1;i>=0;i--) cout< sum=now-cidao[0]; } else//cidao[n-1]>now if(cidao[0]>=now){ for(i=0;i cout< sum=cidao[n-1]-now; } else//cidao[0]now { intpointer; intlocation=1; intleft,right; while(cidao[location] 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< for(j=right;j cout< sum=now+cidao[n-1]-2*cidao[0]; cout< } if(pointer==1)//磁头向右移动到最大号，再改变方向向内扫描未扫描的磁道 23 { for(j=right;j cout< for(j=left;j>=0;j--) cout< sum=2*cidao[n-1]-now-cidao[0];//求总寻道长度 cout< } } else{ cout<<"n输入不合法!!请输入0或1:n"; gotoloop; } } cout<<"nn需要移动的总磁道数为:"< cout<<"请按任意键返回系统菜单"< getch(); showMenu(cidao,n);//回到主界面 24 5.结论 （1）用户界面友好，采用了选择菜单模式，用户只需按“回车键”即可再现主界 面；结构清晰，操作简单易懂，界面清爽整洁； （2）控制变量对比，各磁盘调度算法均对同一组随机磁道号进行调度，但并不会 改变随机磁道内容，保证了平均寻道长度对比的真实性、有效性。 （3）各种算法都有优点，也各有不足，需要权衡利弊，使用才能达到最好的效果。 6.参考文献 《计算机操作系统(修订版)》汤子瀛西安电子科技大学出版社 《操作系统教程》方敏编西安电子科技大学出版社 《数据结构（C++版）》王红梅、胡明、王涛编著清华大学出版社 25 7.收获、体会和建议 在做本次课程设计之前，对于磁盘调度，我完全没有概念。通过努力以及结合老 师之前讲的内容，我终于深刻理解了磁盘调度算法的内涵。在研究自己所选的两种算 法的同时，对磁盘调度的四种算法——先来先服务算法（FCFS）、最短寻道时间优先 算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）都有了更深刻的理解和掌 握，使我能够为磁盘调度选择适当的算法，提高CPU工作效率。设计过程中遇到的困 难在老师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序 的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学 习中有极大帮助。 每一次的课程设计都是对自己之前所学知识的强化，是一次难得的学习机会。在 课程设计的每一个步骤、每一段代码的执行，都要反复去斟酌，反复运行调试，一点 点的小偏差都会导致失败。因为成功不易，所以当调试板上显示“生成成功”时，满 腹的成就感是不言而喻的。通过自己的动手动脑，不仅增加了知识，还给了我专业知 识以及专业技能上的提升，对提高自己的思维能力和操作能力也有很大的帮助。同时 我也会更加有信心，更加努力，认真学习，争取在以后的课程中做得更好！