磁盘调度算法的实现

题目 4 磁盘调度算法的实现4.1 题目的主要研究内容及预期达到的目标(1) 设计磁盘调度请求队列(请求数±10)(2) 设定单位寻道时间；(3) 可动态修改磁盘请求时间和磁道；(4) 分别实现四种磁盘调度算法；A、先来先服务算法(FCFS)。B、最短寻道时间优先算法(SSTF)。C、扫描算法(SCAN)。D、循环扫描算法(CSCAN)。(5) 实现动态调度并输出调度序列。(6) 理解磁盘调度相关理论；(7) 掌握多种磁盘调度算法。4.2 题目研究的工作基础或实验条件(1) 硬件环境：装有 Linux 操作系统(虚拟机)的计算机一台。(2) 软件环境：vim编辑器、Visual C+。4.3 设计思(1) 磁盘调度磁盘可供多个进程共享，当有多个进程要求访问磁盘时，应采用一种调 度算法，以使各进程对磁盘的平均访问时间最小，由于在访问磁盘的时间中，主 要是寻道时间，因此磁盘调度的目标就是使磁盘的平均寻道时间最短。(2) 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(SCAN)、循环扫描算法(CSCAN)。A、先来先服务算法(FCFS)这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次 序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理， 不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化 在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。因为每个 请求都会按照到达先后顺序得到处理，不会出现某个进程的请求长期得不到处理 的情况，算法具有一定的公平性。B、最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离 最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保 证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而 导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请 求将会无限期的被延迟，有些请求的响应时间将不可预期。 此算法会导致与当 前磁道距离较远的访问请求长期等待得不到服务，发生进程“饥饿”现象。C、扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是 磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下 一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自 里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这 时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内， 从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行， 故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中 于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点 即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访 问的频率仍低于中间磁道。此算法与自然界中电梯的工作方式极为相像，故也称 “电梯调度”算法。D、循环扫描算法（CSCAN）循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布 的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。 这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求 等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如， 只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访 磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。4.4流程图磁盘调度算法的实现先来先服务算法(FC)SSTF扫描算法SC循环扫描算法CSC图4-1 模块调用关系图输入初始磁道号； 输入查找范围Limit显示超出范围随机产生10个磁道号按产生的磁道序列输出求平均寻道长度显示移动磁道数及平均寻道长度结束）图4-2 先来先服务算法（FCFS）流程图图4-5 最短寻道时间优先算法(SSTF)流程图4.5主要程序代码(代码使用Times New Roman,五号)# include "stdio.h"#include "stdlib.h"void CopyL(int Sour,int Dist ,int x); 数组 Sour 复制到数组 Dist，复制到 x 个数 void SetDI(int DiscL); 随机生成磁道数void Print(int Pri,int x); 打印输出数组 Privoid DelInq(int Sour,int x,int y);数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y)void FCFS(int Han,int DiscL); 先来先服务算法(FCFS)void SSTF(int Han,int DiscL); 短寻道时间优先算法(SSTF)int SCAN(int Han,int DiscL,int x,int y); 扫描算法(SCAN) void CSCAN(int Han,int DiscL); 循环扫描算法(CSCAN) / void PaiXu(); /寻道长度由低到高排序void Pri();int NAll=0; /ALLint Best52; /用作寻道长度由低到高排序时存放的数组int Limit=0; /输入寻找的范围磁道数 iint Jage;float Aver=0; /求平均寻道次数int main()int i;int DiscLine10; /声明准备要生成的随机磁道号的数组int Hand; /磁道数int Con=1;int n;while(Con=1),&Limit);if(Limit>65536) elseprintf(" printf( printf( printf( printf( printf( printf( printf(printf(”超出范围!");*n"); * 磁盘调度算法 *n"*n");*n");*n");*n");*n");1先来先服务算法(FCFS)2短寻道时间优先算法(SSTF)3扫描算法(SCAN)4循环扫描算法(CSCAN)*n");scanf("%d",&n);if(n=0) exit(0);printf("n");switch(n) case 1:SetDI(DiscLine); /随机生成磁道数FCFS(Hand,DiscLine); 先来先服务算法(FCFS)break;case 2:SetDI(DiscLine); /随机生成磁道数SSTF(Hand,DiscLine); /短寻道时间优先算法(SSTF)break;case 3:SetDI(DiscLine); /随机生成磁道数SCAN(Hand,DiscLine,0,9); 扫描算法(SCAN) break;case 4:SetDI(DiscLine); /随机生成磁道数 CSCAN(Hand,DiscLine); /循环扫描算法(CSCAN) break;case 5:SetDI(DiscLine); /随机生成磁道数FCFS(Hand,DiscLine); 先来先服务算法(FCFS)SSTF(Hand,DiscLine); /短寻道时间优先算法(SSTF) SCAN(Hand,DiscLine,0,9); 扫描算法(SCAN) CSCAN(Hand,DiscLine); 循环扫描算法(CSCAN)PaiXu(); /寻道长度由低到高排序 printf("nn+ 寻道长度由低到高排序:");for(i=0;i<4;i+)printf("%4d ",Besti0);break;printf("nn+ 是否继续(按 0 结束,按 1 继续)?"); scanf("%5d",&Con);数组Sour复制到数组Dist，复制到x个数void CopyL(int Sour,int Dist ,int x) int i;for(i=0;i<=x;i+)Disti=Souri;void Print(int Pri,int x) /打印输出数组 Pri int i;for(i=0;i<=x;i+)printf("%5d",Prii);void SetDI(int DiscL) 随机生成磁道数 int i; for(i=0;i<=9;i+)DiscLi=rand()%Limit;随机生成 10 个磁道号printf("+ 需要寻找的磁道号:");Print(DiscL,9); /输出随机生成的磁道号printf("n");数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会 出现 2 个 y)void DelInq(int Sour,int x,int y) int i; for(i=x;i<y;i+)Souri=Souri+1;x+;void FCFS(int Han,int DiscL)先来先服务算法(FCFS)int RLine10; 将随机生成的磁道数数组Discl复制给数组RLineint i,k,All,Temp; /Temp 是计算移动的磁道距离的临时变量All=0; /统计全部的磁道数变量k=9; /限定 10 个的磁道数CopyL(DiscL,RLine,9); /复制磁道号到临时数组 RLineprintf("n+ 按照 FCFS 算法磁道的访问顺序为:");All=Han-RLine0;for(i=0;i<=9;i+)Temp=RLine0-RLine1;求出移动磁道数，前一个磁道数减去后一个磁道数得出临 时的移动距离if(Temp<0)Temp=(-Temp);/移动磁道数为负数时,算出相反数作为移动磁道数printf("%5d",RLine0);All=Temp+All;/求全部磁道数的总和DelInq(RLine,0,k);每个磁道数向前移动一位k-;BestJage1=All;/Best1存放移动磁道数BestJage0=1; Best0存放算法的序号为:1Jage+;排序的序号加1Aver=(float) All)/10;/求 平均寻道长度printf("n+ 移动磁道数:<%5d> ”,All);printf("n+ 平均寻道长度:*%0.2f* ",Aver);void SSTF(int Han,int DiscL)短寻道时间优先算法(SSTF) int i,j,k,h,All;int Temp; /Temp 是计算移动的磁道距离的临时变量int RLine10;将随机生成的磁道数数组Discl复制给数组RLineint Min;All=0; /统计全部的磁道数变量k=9; /限定 10 个的磁道数CopyL(DiscL,RLine,9); /复制磁道号到临时数组 RLineprintf("n+ 按照 SSTF 算法磁道的访问顺序为:");for(i=0;i<=9;i+) Min=64000;for(j=0;j<=k;j+) /内循环寻找与当前磁道号短寻道的时间的磁道号if(RLinej>Han) /如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLinej-Han; /求出临时的移动距离elseTemp=Han-RLinej; /求出临时的移动距离if(Temp<Min) 如果每求出一次的移动距离小于Min，执行下一句Min=Temp; /Temp 临时值赋予 Minh=j; /把近当前磁道号的数组下标赋予 hAll=All+Min; /统计一共移动的距离printf("%5d",RLineh);Han=RLineh;DelInq(RLine,h,k); /每个磁道数向前移动一位k-;BestJagel=All;/Bestl存放移动磁道数BestJage0=2;/Best0存放算法的序号为:2Jage+;排序序号加1Aver=(float)All)/10;/求平均寻道次数printfC'n+ 移动磁道数:<%5d> ”,All);printf("n+ 平均寻道长度:*%0.2f* ",Aver);扫描算法(SCAN)int SCAN(int Han,int DiscL,int x,int y)int j,n,k,h,m,All;int t=0;int Temp;int Min;int RLine10将随机生成的磁道数数组Disci复制给数组RLine口int Order;Order=1;k=y;m=2;/控制while语句的执行，即是一定要使当前磁道向内向外都要扫描到Aii=0; /统计全部的磁道数变量CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLinePRintf (r按照SCAN算法磁道的访冋顺序为:)； Min=64000;for(j=x;j=y;j+)寻找与当前磁道号短寻道的时间的磁道号if(RLinejHan)/如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 TemP=RLinej-Han; /求出临时的移动距离elseTemp=Han -RLinej; /求出临时的移动距离 if(TemPMin)Min=Temp;/Temp 临时值赋予 Minh=j; /把近当前磁道号的数组下标赋予hAll=All+Min;pRintf("%5d",RLineh);if(RLineh=Han)/判断磁道的移动方向，即是由里向外还是由外向里ORdeR=0;t=1;Han=RLineh;DelInq(RLine,h,k) /g个磁道数向前移动一位k-while(m0)if(Order=l) /ordeRt判断磁盘扫描的方向标签，order是1的话，磁道向内移动for(j=x;j=y;j+)h=-1;Min=64000;for(n=x;n<=k;n+) /判断离当前磁道近的磁道号if(RLinen<=Han)Temp=Han-RLinen;if(Temp<Min)Min=Temp; /Temp 临时值赋予 Minh=n; /把近当前磁道号的数组下标赋予 hif(h!=-1)All=All+Min; /叠加移动距离 printf("%5d",RLineh);Han=RLineh; /近的磁道号作为当前磁道DelInq(RLine,h,k);k-;Order=0; 当完成向内的移动，order赋予0,执行else语句，使磁道向外移动 m-; /向内完成一次， m 减一次，保证 while 循环执行两次else /order 是 0 的话，磁道向外移动for(j=x;j<=y;j+)h=-1;Min=64000;for(n=x;n<=k;n+) /判断离当前磁道近的磁道号if(RLinen>=Han)Temp=RLinen-Han;if(Temp<Min)Min=Temp; /Temp 临时值赋予 Minh=n; /把近当前磁道号的数组下标赋予 hif(h!=-1)All=All+Min; /叠加移动距离 printf("%5d",RLineh);Han=RLineh; /近的磁道号作为当前磁道DelInq(RLine,h,k);k-;Order=1; /当完成向内的移动， order 赋予 0，执行 else 语句，使磁道向外移动m-;向内完成一次，m减一次，保证while循环执行两次/ NAll=NAll+All;if(y-x)>5)BestJagel=All;/Bestl存放移动磁道数BestJage0=3;/Best0存放算法的序号为:3Jage+;排序序号加1Aver=(float)All)/10;/求平均寻道次数printf("n+ 移动磁道数:<%5d> ",All);printf("n+ 平均寻道长度:*%0.2f* ",Aver);if(t=1) printf("n+ 磁道由内向外移动");elseprintf("n+ 磁道由外向内移动");return(Han);循环扫描算法(CSCAN)void CSCAN(int Han,int DiscL) int j,h,n,Temp,m,k,All,Last,i;int RLine10; 将随机生成的磁道数数组Discl复制给数组RLineint Min;int tmp=0;m=2;k=9;All=0;/统计全部的磁道数变量Last=Han;CopyL(DiscL,RLine,9); /复制磁道号到临时数组 RLine printf("n+ 按照 CSCAN 算法磁道的访问顺序为:");while(k>=0)for(j=0;j<=9;j+) /从当前磁道号开始，由内向外搜索离当前磁道近的磁道号h=-1;Min=64000;for(n=0;n<=k;n+)if(RLinen>=Han)Temp=RLinen-Han;if(Temp<Min)Min=Temp;h=n;if(h!=-1)All=All+Min; /统计一共移动的距离 printf("%5d",RLineh);Han=RLineh;Last=RLineh;DelInq(RLine,h,k);k-;if(k>=0)tmp=RLine0;for(i=0;ivk;i+)/算出剩下磁道号的小值if(tmp>RLinei) tmp=RLinei;Han=tmp;把小的磁道号赋给HanTemp=Last-tmp;求出大磁道号和小磁道号的距离差All=All+Temp; /whileBestJagel=All;/Bestl存放移动磁道数BestJage0=4;/Best0存放算法的序号为:4Jage+;排序序号加1Aver=(float)All)/10;/求平均寻道次数printfC'n+ 移动磁道数:<%5d> ”,All);printf("n+ 平均寻道长度:*%0.2f* ",Aver);void PaiXu()int i,j,Temp;for(i=0;i<4;i+)for(j=0;j<3;j+)if(Bestj1>Bestj+11) /如果前一个算法的移动磁道距离大于后一个移动磁道 数，执行下面语句Temp=Bestj+11;/从这起下三行执行冒泡法将移动距离大小排序，排完后则执行每个算法的排序Bestj+11=Bestj1;Bestjl=Temp;Temp=Bestj+lO; 将每个算法的序号用冒泡法排序Bestj+10=Bestj0;Bestj0=Temp;46运行结果及分析a o,cpp b+cpp- c.cpp c*cpp tangubdntu:/os/ctpandtaoddS ./a请输人初始的蹴道Si(9<n<65536)：10O9 +输人寻找的范1512 2030r* it*-*-?-*1*-*-*-*-*-?!*7 盖虽、* 盖虽 * * * * iA- -/e -ak §兹'岸* k-A A k-A 占鼻亡金虽* * * G * ir* -Jt-ir-Jr * -k * -Ar-*- * * -k -ir-Jb* * * 士 -k ir* 吉士it*1c*1.先来先月艮务算fS(FCFS)* 冬毎寻道时间优先算法(5STF)* 3*扫橢算法(SCAM?* 4”循环扫描算法(C5CAN)ir-Jr jk -ir-Jr 去* -k -ir Jr * 去击 氐金* fc亡 * *吐 卄 *去 dtdt* it* -fc 占* * 亡古fc吐 fc亡需要寻找的磴道号：1383806777915 17933351386492649 1421披照FCFS算袪嵐逍的访问顺序九：133S 886 移动础道数K 5571>平均寻道Kg:*557,10*777S15 1793335 1386492649 1421+ 需要寻找的礴道号：3622769359 1763 1926513 1426 1172 1736按照SSTF算法镒迫的访问顺序为；117 142& 173& 1763 192&690540 騒25&274移动磁直数X 2825>4-平均弄道虽滾汁2曲*5刖34-需要寻找的晞道号：1211 1368567429 1782 153&8C2 112S<57 1135+按照SCAN算法陽道的访问顺存対：11Z3 1135+移动鐵逍数沦2497>+平均寻道长康汁2胛畀护+璀道由内向外移动4+需要寻找的磁迺号：1929 180222 1058 1069十按照CSCAN算法礪道的访问顺序齿；1011 1056 +越动隔道数皿3270>+平均寻道低度卢呻丁.日旷1211136615301782S625674296716713934561011421069139319021929224216745647心得体会磁盘调度算法上课时老师讲过，课本上有对算法的说明，根据以上两点很容易实现了此功能的模拟。