磁盘地调度算法.doc

《磁盘地调度算法.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验七磁盘的调度算法一.实验要求设计五个算法,分别是先来先服务算法,最短寻道时间优先算法,扫描(SCAN)算法,循环扫描(CSCAN)算法,NStepSCAN算法.由人工输入当前的磁道数,由系统随即生成要访问的磁道.二、开发环境操作系统:RadHatLinux,开发环境:C语言.三、分析设计（一）实验原理.磁盘是可被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问(主要是寻道)时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。(1)先来先服务．(First-Com

2、e，First-Served，FCFS):这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。(2)最短寻道时间优先(ShortestSeekTimeFirst，SSTF):该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。(3)扫描(SCAN)算法:SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先

3、考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。(4)循环扫描(CSCAN)算法:处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头

4、立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。(5)N_Step_SCAN算法:N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按FCFS算法依次处理这些子队列.而每处理一个队列时又是按SCAN算法,对一个队列处理完后,再处理其他队列.当正在处理某子队列时,如果又出现新的磁盘I/O请求,便将新请求进程放进其他队列.（二）程序结构第一部分:程序的主要流程(1)手动输入当前的磁道号,该磁道号在0

5、调度算法,此时会随机生成一个在第二步生成磁道围以的10个磁道数,由SetDI方法生成,再将生成的随机磁道号以数组形式作为参数被某个算法调用.例如,选择了case1,则先调用SetDI方法,再执行FCFS算法.如下:case1:SetDI(DiscLine);//随机生成磁道数FCFS(Hand,DiscLine);//先来先服务算法(FCFS)break;第二部分:部分的代码实现(1)就每个算法而言,都有调用一个子算法CopyL把函数SetDI随机生成的磁道数数组复制给RLine[],为什么要复制,原因是在整个程序中的最后一项功能是实现5种算法对一次随即生成的磁道数

6、的比较,所以在每次调用一种算法时需要设置一个临时的数组Rline[]来存放.(2)在这5个算法中都有一个字函数DelInq，该函数的作用是使每个磁道数向前移动一位，简单地以FCFS算法为例，这里只FCFS其中的核心代码：All=Han-RLine[0];for(i=0;i<=9;i++){Temp=RLine[0]-RLine[1];//求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离if(Temp<0)Temp=(-Temp);//移动磁道数为负数时,算出相反数作为移动磁道数printf("%5d",RLine[0]);All=Temp+All;//

7、求全部磁道数的总和DelInq(RLine,0,k);//每个磁道数向前移动一位k--;}Han是当前磁道数，RLine[0]是第一个随机磁道数，Han-RLine[0]得到的是一次磁头移动的距离，再赋予All，即All是存放磁头移动的距离总和，for循环是执行10次，Temp变量是求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离，All=Temp+All是求全部磁道数的总和之后是DelInq函数，使每个磁道数向前移动一位。例如随机生成的磁道数数组RLine是：583286177115593535586492249421因为当前的磁道数是500，通