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

1前言摘要：本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，使磁盘调度的特点更简单明了，这里主要实现磁盘调度的四种算法，分别是：1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送；因此，执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间，寻道时间——指计算机在发出一个寻址命令，到相应目标数据被找到所需时间；其中传送信息所花的时间，是在硬件设计时固定的，而寻找时间和延迟时间是与信息在磁盘上的位置有关；然后设计出磁盘调度的设计方式，包括算法思路、步骤，以及要用到的主要数据结构、函数模块及其之间的调用关系等，并给出详细的算法设计，对编码进行了测试与分析。最后进行个人总结与设计体会。关键词：最短寻道时间优先算法、扫描算法、总寻道长度.2目录前言......................................................12.课程设计任务及要求........................................32.1设计任务..............................................32.2设计要求..............................................33.算法及数据结构............................................33.1算法的总体思想（流程）................................33.2实现过程中用到的数据结构..............................43.3实现过程中用到的系统调用..............................94.程序设计与实现............................................94.1最短寻道时间优先算法（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.收获、体会和建议.........................................2532.课程设计任务及要求2.1设计任务1.熟悉并掌握磁盘调度算法管理系统的设计方法，加强对所学各种调度算法及相应算法的特点了解。2.掌握磁盘调度的基本概念，深刻体会各个算法的优缺点，以及算法间的相似点。2.2设计要求1)定义与算法相关的数据结构，如PCB、队列等；2）实现2种不同的调度算法（可使用伪代码或流程图进行分析）；3）算法执行结束时，应给出总的寻道长度；4）磁道访问序列随机生成，且要满足一定的数量要求（不少于100个）；5）系统实现必须提供一定的交互性，所需测试数据应当以文件形式提供或者由用户在测试过程中给出，不可将测试数据“写死”在系统实现代码中；6）必须给出足够的注释，注释量不得少于代码量的一半；7）对于系统中所使用到的系统调用（API函数），必须给出函数的定义原型、使用方法，参数较为复杂的，还应该给出参数的具体描述；3.算法及数据结构3.1算法的总体思想（流程）4总流程图YNYN3.2实现过程中用到的数据结构1.最短寻道时间优先（SSTF）开始输入磁道的个数生成随机的磁道号用户输入所选择的算法进行磁盘调度输入数字为1-2？输出排序后的磁盘序列用户输入当前磁道号显示磁盘调度顺序输入为3？退出程序结束5（从100号磁道开始）被访问的下一个磁道号移动距离（磁道数）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=100；ciidao[]={55,58,39,18,90,160,150,38,184}（可随机生成多个）用户输入当前磁道号now，比较当前磁道到每个磁道的移动距离，选择最短距离的磁道进行移动。now指向当前磁道号，计算寻道长度sum。将当前磁道号与剩余没有访问的磁道号进行比较，重复上述操作。并计算平均寻道长度ave。6383939555555585858589090909090now值:10090585539184160160150150150181818183838383839393939555555555858585890909090now值：18150160184图cSSTF算法队列示意图(按磁道访问顺序)72.扫描（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；选择磁道移动方向；以磁道号增加的方向移动为例：8555858909090184184184184160160160160160150150150150150150now值：1001501601849058183838393939555555585858909090184184184160160160150150150now值:553938图eSCAN算法队列示意图（按磁道访问顺序）93.3实现过程中用到的系统调用系统模块调用关系图4.程序设计与实现4.1最短寻道时间优先算法（SSTF）模块4.1.1程序流程图磁盘调度算法模拟系统最短寻道时间优先扫描算法退出10now=cidao[0]cidao[0]nowcidao[m-1]now=cidao[m-1]输入磁道号串用冒泡法将磁道号从大到小排序判断now的大小调用SSTF()函数输入当前磁道号now开始结束优先服务离now最近的磁道移动方向，再掉头服务计算总寻道长度，并输出移动的平均寻道长度直接从大到小给予磁道服务直接从小到大给予磁道服务找到离now寻道时间最短的磁道114.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;im;i++)/*使用冒泡法按从小到大顺序排列*/for(j=i+1;jm;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--)coutarray[i];sum=now-array[0];}else12if(array[0]=now)/*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务*/while((l=0)&&(rm))/*当前磁道在请求序列范围内*/{if((now-array[l])=(array[r]-now))/*选择与当前磁道最近的请求给予服务*/{coutarray[l];sum+=now-array[l];now=array[l];l=l-1;}4.2扫描算法（SCAN）模块4.2.1程序流程图13d=1d=0开始输入磁道号串调用SCAN（）函数调用冒泡排序法进行排序输入当前磁道号now从磁道最外端开始向内扫描计算总寻道长度，并输出平均寻道长度从磁道最内端开始向外扫描向内扫描向外扫描选择磁道扫描方向结束144.2.2程序说明算法分析优点：排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了SSTF算法的不公平性，但仍有利于对中间磁道的请求。缺点：新进来的访问此磁道的进程的请求会被大大地推迟。增加延迟。SCAN算法又称电梯调度算法。SCAN算法是磁头前进方向上的最短查找时间优先算法。注：“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客张一、张二、张三在等候乘电梯。他们的要求是：张一在2层等待去10层；张二在5层等待去底层；张三在8层等待去15层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张三从8层带到15层，然后电梯换成下行方向，把乘客张二从5层带到底层，电梯最后再调换方向，把乘客张一从2层送到10层。我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移动臂的初始方向有两个，而该算法是与移动臂方向有