《磁盘调度算法的实现.doc》由会员分享，可在线阅读，更多相关《磁盘调度算法的实现.doc（15页珍藏版）》请在三一办公上搜索。
1、姓名学号专业班级实验项目实验三：磁盘调度算法的实现课程名称操作系统课程代码 实验时间2011 年11月06日 2011 年11月09日 2011 年12月13日 2011 年12月16日实验地点软件实验室7-215批改意见成绩教师签字： 【实验环境】Windows操作系统环境下的个人微机【实验目的】 了解操作系统磁盘调度的基本概念，磁盘调度程序的功能，常用的磁盘调度算法。【实验要求】 学生应正确地设计有关的数据结构与各个功能模块，画出程序的流程图，编写程序，程序执行结果应正确。【实验内容】1) 本实验是模拟操作系统的磁盘寻道方式，运用磁盘访问顺序的不同来设计磁盘的调度算法。2) 实现的磁盘调度
2、算法有FCFS，SSTF，SCAN，CSCAN和 NStepSCAN算法。3) 设定开始磁道号寻道范围，依据起始扫描磁道号和最大磁道号数，随机产生要进行寻道的磁道号序列。4) 选择磁盘调度算法，显示该算法的磁道访问顺序，计算出移动的磁道总数和平均寻道总数。按算法的寻道效率进行排序，并对各算法的性能进行分析比较。【实验原理】1) FCFS这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。2) SSTF该算法选择这样的进程：其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。3) SCAN该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前
3、的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直至再无更外的磁道需要访问时，才将磁臂换向为自外向里移动。4) CSCANCSCAN算法规定磁头单向移动，例如，只是自里向外移动，当磁头移到最外的磁道并访问后，磁头立即返回到最里的欲访问的磁道，亦即将最小磁道号紧接着最大磁道号构成循环，进行循环扫描。5) NStepSCAN N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列。而每处理一个队列时又是按SCAN算法，对一个队列处理完后，再处理其他
4、队列。【实验步骤、过程】 1、程序主要流程(1)手动输入当前的磁道号,该磁道号在0n65536以内(65536是2的16次方),超出范围则需重新输入。(2)手动输入要寻找磁道的范围。(3)主菜单,选择要进行磁道调度算法,此时会随机生成一个在第二步生成磁道范围以内的10个磁道数,由SetDI方法生成,再将生成的随机磁道号以数组形式作为参数被某个算法调用。 2、程序部分代码1) 函数声明及数据定义#include stdio.h#include stdlib.h#include iostream.hvoid CopyL(int Sour,int Dist ,int x); /数组Sour复制到数组
5、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); /扫描算法(SC
6、AN)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 N_Step_SCAN(int Han1,int DiscL); /N步扫描算法(NStepScan)void PaiXu(); /寻道长度由低到高排序void Pri();int NAll=0;int Be
7、st52; /用作寻道长度由低到高排序时存放的数组int Limit=0; /输入寻找的范围磁道数iint Jage;float Aver=0;2) 随机生成磁道数/随机生成磁道数void SetDI(int DiscL) int i;for(i=0;i=9;i+) DiscLi=rand()%Limit;/随机生成10个磁道号 printf(n需要寻找的磁道号:); Print(DiscL,9); /输出随机生成的磁道号printf( );3) FCFS/先来先服务算法(FCFS)void FCFS(int Han,int DiscL) int RLine10; /将随机生成的磁道数数组Di
8、scl复制给数组RLine int i,k,All,Temp; /Temp是计算移动的磁道距离的临时变量 All=0; /统计全部的磁道数变量k=9; /限定10个的磁道数 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(n按照FCFS算法磁道的访问顺序为:); All=Han-RLine0; for(i=0;i=9;i+) Temp=RLine0-RLine1;/求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离 if(Temp0) Temp=(-Temp);/移动磁道数为负数时,算出相反数作为移动磁道数 printf(%5d,RLin
9、e0); All=Temp+All;/求全部磁道数的总和 DelInq(RLine,0,k);/每个磁道数向前移动一位 k-; BestJage1=All;/Best1存放移动磁道数BestJage0=1; /Best0存放算法的序号为:1 Jage+;/排序的序号加1 Aver=(float) All)/10;/求平均寻道次数 printf(n移动磁道数: ,All);printf(n平均寻道长度:*%0.2f* ,Aver);4) SSTF/最短寻道时间优先算法(SSTF)void SSTF(int Han,int DiscL) int i,j,k,h,All;int Temp; /Tem
10、p是计算移动的磁道距离的临时变量 int RLine10; /将随机生成的磁道数数组Discl复制给数组RLine int Min; All=0; /统计全部的磁道数变量 k=9; /限定10个的磁道数 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(n按照SSTF算法磁道的访问顺序为:);for(i=0;i=9;i+) Min=64000; for(j=0;jHan) /如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLinej-Han; /求出临时的移动距离 else Temp=Han-RLinej; /求出临时的移动距离 i
11、f(TempMin) /如果每求出一次的移动距离小于Min，执行下一句 Min=Temp; /Temp临时值赋予Min h=j; /把最近当前磁道号的数组下标赋予h All=All+Min; /统计一共移动的距离 printf(%5d,RLineh); Han=RLineh; DelInq(RLine,h,k); /每个磁道数向前移动一位 k-; BestJage1=All;/Best1存放移动磁道数 BestJage0=2;/Best0存放算法的序号为:2 Jage+;/排序序号加1 Aver=(float)All)/10;/求平均寻道次数printf(n移动磁道数: ,All);print
12、f(n平均寻道长度:*%0.2f* ,Aver);5) SCAN/扫描算法(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; /将随机生成的磁道数数组Discl复制给数组RLine int Order; Order=1; k=y; m=2; /控制while语句的执行，即是一定要使当前磁道向内向外都要扫描到 All=0; /统计全部的磁道数变量 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(
13、n按照SCAN算法磁道的访问顺序为:); Min=64000; for(j=x;jHan) /如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLinej-Han; /求出临时的移动距离 else Temp=Han-RLinej; /求出临时的移动距离 if(Temp=Han) /判断磁道的移动方向，即是由里向外还是由外向里 Order=0; t=1; Han=RLineh;DelInq(RLine,h,k); /每个磁道数向前移动一位k-;while(m0) if(Order=1) /order是判断磁盘扫描的方向标签，order是1的话，磁道向内移动 for(j=x;j=
14、y;j+) h=-1; Min=64000; for(n=x;n=k;n+) /判断离当前磁道最近的磁道号 if(RLinen=Han) Temp=Han-RLinen; if(TempMin) Min=Temp; /Temp临时值赋予Min h=n; /把最近当前磁道号的数组下标赋予h if(h!=-1) All=All+Min; /叠加移动距离 printf(%5d,RLineh); Han=RLineh; /最近的磁道号作为当前磁道 DelInq(RLine,h,k); k-; Order=0; /当完成向内的移动，order赋予0，执行else语句，使磁道向外移动 m-; /向内完成一
15、次，m减一次，保证while循环执行两次else /order是0的话，磁道向外移动 for(j=x;j=y;j+) h=-1; Min=64000; for(n=x;n=Han) Temp=RLinen-Han; if(Temp5) BestJage1=All;/Best1存放移动磁道数 BestJage0=3;/Best0存放算法的序号为:3 Jage+;/排序序号加1 Aver=(float)All)/10;/求平均寻道次数 printf(n移动磁道数: ,All); printf(n平均寻道长度:*%0.2f* ,Aver); if(t=1) printf(n磁道由内向外移动);els
16、e printf(n磁道由外向内移动); return(Han);6) CSCAN/循环扫描算法(CSCAN)void CSCAN(int Han,int DiscL)int j,h,n,Temp,m,k,All,Last,i;int RLine10; /将随机生成的磁道数数组Discl复制给数组RLine int 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
17、;j=9;j+) /从当前磁道号开始，由内向外搜索离当前磁道最近的磁道号 h=-1; Min=64000; for(n=0;n=Han) Temp=RLinen-Han; if(Temp=0) tmp=RLine0; for(i=0;iRLinei) tmp=RLinei; Han=tmp;/把最小的磁道号赋给Han Temp=Last-tmp;/求出最大磁道号和最小磁道号的距离差 All=All+Temp; BestJage1=All;/Best1存放移动磁道数 BestJage0=4;/Best0存放算法的序号为:4 Jage+;/排序序号加1 Aver=(float)All)/10;/求
18、平均寻道次数printf(n移动磁道数: ,All); printf(n平均寻道长度:*%0.2f* ,Aver);7) NStepSCAN/N步扫描算法(NStepScan)void N_Step_SCAN(int Han1,int DiscL) int i,m,k;int RLine110; NAll=0; m=2; k=9; /限定10个磁道数 i=-1; CopyL(DiscL,RLine1,9); /复制磁道号到临时数组RLine printf(n按照N_Step_SCAN算法磁道的访问顺序为:); for(m=0;m2;m+) /由于限定10磁道数，将10个磁道数分为两组，每组5个
19、磁道数，每个组按照SCAN算法执行，该循环循环2次 Han1=SCAN(Han1,RLine1,i+1,i+5); i=i+5; BestJage1=NAll;/Best1存放移动磁道数BestJage0=5;/Best0存放算法的序号为:5 Aver=(float)NAll)/10;/求平均寻道次数 printf(n移动磁道数: ,NAll); printf(n平均寻道长度:*%0.2f* ,Aver);8) 按算法的寻道效率进行排序/寻道长度由低到高排序void PaiXu() int i,j,Temp;for(i=0;i5;i+) for(j=0;jBestj+11) /如果前一个算法的
20、移动磁道距离大于后一个移动磁道数，执行下面语句 Temp=Bestj+11; /从这起下三行执行冒泡法将移动距离大小排序，排完后则执行每个算法的排序 Bestj+11=Bestj1; Bestj1=Temp; Temp=Bestj+10; /将每个算法的序号用冒泡法排序 Bestj+10=Bestj0; Bestj0=Temp; 9) 主函数int main() int i; int DiscLine10; /声明准备要生成的随机磁道号的数组 int Hand; /磁道数 int Con=1;int n; while(Con=1) Jage=0; printf(n请输入初始的磁道数(0n655
21、36) printf(超出范围!); else printf( n); printf( 操作系统课程设计 n); printf( 磁盘调度算法 n);printf( n); printf( n); printf( 1.先来先服务算法(FCFS) n); printf( n); printf( 2.最短寻道时间优先算法(SSTF) n); printf( n); printf( 3.扫描算法(SCAN) n); printf( n); printf( 4.循环扫描算法(CSCAN) n); printf( n); printf( 5.N步扫描算法(NStepScan) n); printf( n
22、); printf( 6.各类算法的比较 n); printf( n); printf( n);printf( n); printf( 请输入你的选择的算法(输入0离开) n); printf( n); scanf(%d,&n); if(n=0) exit(0);printf( );switch(n) case 1: SetDI(DiscLine); /随机生成磁道数 FCFS(Hand,DiscLine); /先来先服务算法(FCFS) break; case 2: SetDI(DiscLine); /随机生成磁道数 SSTF(Hand,DiscLine); /最短寻道时间优先算法(SSTF
23、) break;case 3: SetDI(DiscLine); /随机生成磁道数 SCAN(Hand,DiscLine,0,9); /扫描算法(SCAN) break; case 4: cout注：规定磁头由内向外单方向移动。endl;SetDI(DiscLine); /随机生成磁道数 CSCAN(Hand,DiscLine); /循环扫描算法(CSCAN) break;case 5: SetDI(DiscLine); /随机生成磁道数 N_Step_SCAN(Hand,DiscLine); /N步扫描算法(NStepScan)break; case 6: SetDI(DiscLine);
24、/随机生成磁道数 FCFS(Hand,DiscLine); /先来先服务算法(FCFS) SSTF(Hand,DiscLine); /最短寻道时间优先算法(SSTF) SCAN(Hand,DiscLine,0,9); /扫描算法(SCAN) CSCAN(Hand,DiscLine); /循环扫描算法(CSCAN) N_Step_SCAN(Hand,DiscLine); /N步扫描算法(NStepScan) PaiXu(); /寻道长度由低到高排序 printf(n寻道长度由低到高排序:); for(i=0;i5;i+) printf(%4d ,Besti0); break; printf(n是否继续(按0结束,按1继续)?); scanf(%5d,&Con); return 0;3、 运行结果1) 输入初始磁道数及寻找范围 2) 选择FCFS算法3) 重新随机生成磁道数，选择SSTF4) 重新随机生成磁道数，选择SCAN5) 重新随机生成磁道数，选择CSCAN6) 重新随机生成磁道数，选择 NStepSCAN7) 对同一磁道序列，按算法的寻道效率进行排序8） 退出
