磁盘调度算法文档

《操作系统原理及应用》课程设计报告磁盘调度算法学院（系）：计算机科学与工程学院班级：37-5学号学生姓名：时间：从2013年12月16日到2013年12月20日1、课程设计的目的本课程设计是学生学习完《操作系统原理及应用》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。2、课程设计的内容及要求编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度：要求设计主界面以灵活选择某算法，且以下算法都要实现1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）3、实现原理磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N其中Mi为磁头从上一各磁道到这个磁道所需移动的距离。4、算法1.先来先服务算法（FCFS）这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。2.短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当前磁道号也跟着变化，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，就逆序访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，就正序访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。3.扫描算法（SCAN）SCAN算法又称电梯调度算法。该算法先考虑磁头的移动方向，再考虑距离近的访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再逆向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后逆向访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，两种方向都是逆序对磁道号访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，两种方向都是正序对磁道号访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。4.循环扫描算法（CSCAN）CSCAN算法是在SCAN算法的基础上规定磁头单向移动，即扫描时要么向磁道号增加的方向的访问，要么向磁道号减小的方向访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再返回磁道最里面朝增加的方向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后返回到磁道最外层访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当向磁道号增加的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是正序访问；而当向磁道号减小的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是逆序访问；此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。5、程序中使用的数据结构及使用的变量说明和作用int[]cidao=newint[1000];//将被访问的磁道号存入cidao数组intsum=0;//求移动距离之和doubleavg=0;//求平均寻道时间string[]str=txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号intnow=Convert.ToInt32(txtnow.Text);//获取当前的磁道号for(inti=0;istr.Length;i++){//将获取的磁道号存入磁道号数组cidao[i]=Convert.ToInt32(str[i]);}privatevoidbtnFCFS_Click(objectsender,EventArgse)先来先服务FCFS算法privatevoidbtnSSTF_Click(objectsender,EventArgse)最短寻道时间优先SSTFprivatevoidbtnSCANhigh_Click(objectsender,EventArgse)从里向外扫描privatevoidbtnSCANlow_Click(objectsender,EventArgse)从外向里扫描privatevoidbtnCSCANhigh_Click(objectsender,EventArgse)从里向外循环扫描privatevoidbtnCSCANlow_Click(objectsender,EventArgse)从外向里循环扫描privatevoidbtnexit_Click(objectsender,EventArgse)退出窗体privatevoidtxtnum_KeyDown(objectsender,KeyEventArgse)快捷键Tab选择输入框6、关键算法实现流程图先来先服务FCFS算法：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组求出移动距离之和再除以访问的磁道个数平均寻道长度按按钮输出最短寻道时间算法：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组从小到大排序平均寻道长度按按钮输出磁道数组当前磁道号与磁道数组比较数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和数组的第一个数大于当前磁道号，正序输出，求移动距离之和当前磁道号处于数组最大数与最小数之间，选择离当前磁道号最近的输出，求移动距离之和平均寻道长度获取磁道数组扫描算法：向磁道号增加的方向：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组从小到大排序平均寻道长度按按钮输出磁道数组当前磁道号与磁道数组比较数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和数组的第一个数大于当前磁道号，正序输出，求移动距离之和当前磁道号处于数组最大数与最小数之间，按照增加的方向先输出比当前磁道号大的，接着向减小的方向访问，求移动距离之和平均寻道长度获取磁道数组从磁道号减小的方向：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组从小到大排序平均寻道长度按按钮输出磁道数组当前磁道号与磁道数组比较数组的最后一个小于当前磁道号，则数组逆序输出，求移动距离之和数组的第一个数大于当前磁道号，正序输出，求移动距离之和当前磁道号处于数组最大数与最小数之间，按照减小的方向先输出比当前磁道号小的，接着向增加的方向访问，求移动距离之和平均寻道长度获取磁道数组循环扫描算法：从磁道号增加的方向：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组从小到大排序平均寻道长度按按钮输出磁道数组当前磁道号与磁道数组比较数组的最后一个数小于当前磁道号或第一个数小于当前磁道号，则数组正序输出，求移动距离之和当前磁道号处于数组最大数与最小数之间，按照增加的方向先输出比当前磁道号大的，接着回到最里层，继续向增加的方向访问，求出移动距离之和获取磁道数组从磁道号减小的方向：输入当前磁道号输入下一个被访问的磁道号，各磁道号之间用逗号隔开磁道数组从小到大排序平均寻道长度按按钮输出磁道数组当前磁道号与磁道数组比较数组的最后一个数小于当前磁道号或第一个数小于当前磁道号，则数组逆序输出，求移动距离之和当前磁道号处于数组最大数与最小数之间，按照减小的方向先输出比当前磁道号小的，接着回到最外层，继续向减小的方向访问，求出移动距离之和获取磁道数组7、实现代码///summary///先来先服务FCFS////summary///paramname=sender/param///paramname=e/paramprivatevoidbtnFCFS_Click(objectsender,EventArgse){txtresult.Clear();//清除显示int[]cidao=newint[1000];//被访问的磁道号数组intsum=0;//移动距离之和doubleavg=0;//平均寻道时间string[]str=txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号intnow=Convert.ToInt32(txtnow.Text);//当前的磁道号for(inti=0;istr.Length;i++){//将获取的磁道号存入磁道号数组cidao[i]=Convert.ToInt32(str[i]);}sum+=Math.Abs(now-cidao[0]);//当前的磁道号减去磁道号数组中的第一个值取绝对值for(inti=0;istr.Length;i++){//输出FCFS磁盘调度结果txtresult.Text=txtresult.Text+cidao[i]+',';}for(inti=0,j=1;jstr.Length;i++,j++){//累计总的移动距离sum+=Math.Abs(cidao[j]-cidao[i]);}avg=(double)sum/str.Length;//平均寻道长度lblsum.Text=总移动距离：+sum.ToString();//在Label中显示总移动距离lblavg.Text=平均寻道长度：+avg.ToString(0.00);//在Label中显示平均寻道时间}///summary///最短寻道时间优先SSTF////summary///paramname=sender/param///paramname=e/paramprivatevoidbtnSSTF_Click(objectsender,EventArgse){txtresult.Clear();//清除显示int[]cidao=newint[1000];//被访问的磁道号数组intsum=0;//移动距离之和doubleavg=0;//平均寻道时间inttemp;//中间变量intk=1;intm,n;string[]str=txtnum.Text.Split(',');//从txtnum里面获取访问的磁道号intnow=Convert.ToInt32(txtnow.Text);//当前的磁道号for(inti=0;istr.Length;i++){//将获取的磁道号存入磁道号数组cidao[i]=Convert.ToInt32(str[i]);}//对磁道号进行从小到大排列for(inti=0;istr.Length;i++){for(intj=i+1;jstr.Length;j++){if(cidao[i]cidao[j]){temp=cidao[i];cidao[i]=cidao[j];cidao[j]=temp;}}}//数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最