操作系统课程设计磁盘调度报告.docx

《操作系统课程设计磁盘调度报告.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计磁盘调度报告.docx（15页珍藏版）》请在三一文库上搜索。

1、题目：磁盘调度一.设计目的本课程设计是学习完计算机操作系统课程后，进行的一次全面的综合训 练，通过课程设计，我们更好地掌握操作系统的原理及实现方法，加深对操作系统基础理论和重要算法的理解，加强了动手能力 。二.课程设计内容和要求编程序实现下述磁盘调度算法，并求出每种算法的平均寻道长度，要求设计 主界面以灵活选择某算法，且以下算法都要实现：1、先来先服务算法（FCFS2、最短寻道时间优先算法（SSTF3、扫描算法（SCAN4、循环扫描算法（CSCAN三.算法及数据结构3.1 算法的总体思想设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的 分配策略有先请求先分配、优先级高者先分配

2、等策略。在多道程序系统中，低效 率通常是由于磁盘类旋转设备使用不当造成的。 操作系统中，对磁盘的访问要求 来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直 接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构 成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间， 其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再 优化旋转等待策略。平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道 数（N）,即：L= （M1+M2 +Mi+MN /N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操

3、作时，要把移动臂移动到指定的柱面，再等待指定 扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此， 执行一次输入输出所花的时间有：寻找时间一一磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间一一指定扇区旋转到磁头下所需的时间。传送时间一一由磁头进程读写完成信息传送的时间。其中传送信息所花的时间，是在硬件设计就固定的。而寻找时间和延迟时间 是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道 顺序存放满一个盘面后，再放到下一个盘面上。而是按柱面存放，同一柱面上的 各磁道被放满信息后，再放到下一个柱面上。所以各磁盘的编号按柱面顺序（从

4、 0号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序 。3.2 算法实现1 .先来先服务算法（FCFS先来先服务（FCFS调度：按先来后到次序服务，未作优化。最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问 者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如 果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱 面为130、199、32、159、15、148、61、99,那么，当50号柱面上的操作结束 后，移动臂将按请求的先后次序先移到 130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的

5、次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长， 所以执行输入输出操作的总时 间也很长。2 .短寻道时间优先算法（SSTF最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个 请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论， 现在当50号柱面的操作结束后，应该先处理 61号柱面的请求，然后到达32号 柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、 159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了 200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找 时间，因而缩

6、短了为各访问者请求服务的平均时间，也就提高了系统效率。 但最短查找时间优先（SSTF调度，FCF8引起读写头在盘面上的大范围移动， SST成找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。 SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖 延（又称饥饿）。3 .扫描算法（SCANSCAN算法又称电梯调度算法。SCANT法是磁头前进方向上的最短查找时间 优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了 SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前 移动

7、臂最近的那个柱访问者，如果沿臂的移动方向无请求访问时，就改变臂的移 动方向再选择。这好比乘电梯，如果电梯已向上运动到4层时，依次有3位乘客 陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2层等待去10层；伍生在5层等待去底层；张生在8层等待15层。由于电梯目前运动方向是向上， 所以电梯的形成是先把乘客张生从 8层带到15层，然后电梯换成下行方向，把 乘客伍生从5层带到底层，电梯最后再调换方向，把乘客陈生从2层送到10层。我们仍用前述的同一例子来讨论采用“电梯调度”算法的情况。由于磁盘移 动臂的初始方向有两个，而该算法是与移动臂方向有关，所以分成两种情况来讨 论。1.移动臂由里向外移动开始时

8、，在50号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32号柱面的位置，因此，当访问50号柱面的操作结束后，沿臂移动方向最近的 柱面是32号柱面。所以应先为32号柱面的访问者服务，然后是为 15号柱面的 访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向， 由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199。2.移动臂由外向里移动开始时，正在50号柱面执行操作的读写磁头的移动臂是由外向里（即向柱 面号增大的内圈方向）趋向61号柱面的位置，因此，当访问50号柱面的操作结 束后，沿臂移动方向最近的柱面是 61号柱面。所

9、以，应先为61号柱面服务，然 后按移动臂由外向里移动的方向，依次为 99、130、148、159、199柱面的访问 者服务。当201号柱面的操作结束后，向里移动的方向已经无访问等待者， 所以 改变移动臂的前进方向，由里向外依次为 32、15柱面的访问者服务。“电梯调度”与“最短寻找时间优先”都是要尽量减少移动臂时所花的时间。 所不同的是：“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写 磁头最近的那个柱面，这种选择可能导致移动臂来回改变移动方向；“电梯调度” 是沿着臂的移动方向去选择离当前读写词头最近的哪个柱面的访问者，仅当沿移动臂的前进移动方向无访问等待者时，才改变移动臂的前进方向

10、。由于移动臂改 变方向是机械动作，速度相对较慢，所以，电梯调度算法是一种简单、使用且高 效的调度算法。但是，“电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必 须记住移动臂的当前前进方向。4 .循环扫描算法（CSCAN单项扫描调度算法的基本思想是，不考虑访问者等待的先后次序，总是从 0 号柱面开始向里道扫描，按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后，立即快速返回到0号柱面，返回时不为任何的访问 者等待服务。在返回到0号柱面后，再次进行扫描。由于该例中已假定读写的当前位置在 50号柱面，所以，指示了从50号柱面 继续向里扫描，依次为61、99、130、1

11、48、159、199各柱面的访问者服务，止匕 时移动臂已经是最内的柱面，于是立即返回到 0号柱面，重新扫描，依次为15、 32号柱面的访问者服务。除了 “先来先服务”调度算法外，其余三种调度算法都是根据欲访问的柱面 位置来继续调度的。在调度过程中可能有新的请求访问者加入。在这些新的请求 访问者加入时，如果读写已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。在多道程序设计系统中，在等待访问磁盘的若干访问者请求 中，可能要求访问的柱面号相同，但在同一柱面上的不同磁道，或访问同一柱面 中同一磁道上的不同扇区。所以，在进行移动调度时，在按照某种短法把移动臂 定位到某个柱面后，应该在等

12、待访问这个柱面的各个访问者的输入输出操作都完 成之后，再改变移动臂的位置。3.3 .三个模块之间的调用关系图3.4 实现代码#include#includevoid FCFS(int b口,int n,int init) /先来先服务int i,s,sum;int a20;for(i=0;in;i+)ai=bi；s=init;sum=0;for(i=0;in;i+) printf(第做访问的磁道:%dn,i+1,ai);sum+=abs(s-ai); s=ai；printf(平均寻道长度:%fn,sum*1.0/n);void SSTF(int b口,int n,int k) /最短寻道法in

13、t i,j,s,sum=0,p;int a20;for(i=0;i=0;i-) s=a0;p=0；for(j=0;j=i;j+)if(abs(aj-k)abs(s-k) s=aj； p=j； ap=ai；printf(第做访问的磁道：dn,n-i,s);sum+=abs(s-k); k=s;printf(平均寻道长度:%fn,sum*1.0/n);void SCAN1(int b,int n,int k) /扫描算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j=i;j+)if(aj-k0)biaoji=1;

14、P=j； break;if(biaoji=1)s=ap；for(j=0;j=i;j+) if(ajk&k-ajk-s)s=aj；P=j；ap=ai；printf(第做访问的磁道：dn,n-i,s);sum+=k-s;k=s;elses=a0;for(j=0;j=i;j+) if(aj-k=s-k)s=aj;p=j;ap=ai;printf(第做访问的磁道：dn,n-i,s); sum+=abs(k-s);k=s;printf(平均寻道长度：fn,sum*1.0/n);void SCAN2(int b口,int n,int k) /循环算法int i,j,s,sum=0,p,biaoji;int

15、 a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j0)biaoji=1;P=j； break;if(biaoji=1)s=ap；for(j=0;jk&aj-ks-k)s=aj；P=j；ap=ai；printf(第做访问的磁道：dn,n-i,s);sum+=s-k;k=s;elses=a0;for(j=0;j=i;j+) if(k-aj=k-s) s=aj;p=j;ap=ai；printf(第做访问的磁道：dn,n-i,s);sum+=abs(k-s);k=s;printf(平均寻道长度：fn,sum*1.0/n);void C_SCAN(int b口,int n,in

16、t k) /循环算法int i,j,s,sum=0,p,biaoji;int a20;for(i=0;i=0;i-)biaoji=0;for(j=0;j0)biaoji=1;p=j；break;if(biaoji=1)s=ap；for(j=0;jk&aj-ks-k)s=aj；p=j；ap=ai；printf(第做访问的磁道：dn,n-i,s);sum+=s-k;k=s;if(biaoji=0) break;s=a0;for(j=0;j=i;j+)if(aj=0;i-)s=a0;for(j=0;j=i;j+) if(aj-ks-k)s=aj； P=j；ap=ai；printf(第做访问的磁道：d

17、n,n-i,s); sum+=s-k;k=s;printf(平均寻道长度：fn,sum*1.0/n); void main()int a20;int i,n,k,k1,init;printf(”请输入需要访问的磁道总数：);scanf(%d,&n);for(i=0;in;i+)printf( 需要访问的磁道d:,i+1); scanf(%d”,&ai);printf(请输入指针所在磁道：”)； scanf(%d”,&init);k=1;while(k)printf(*n);printf($ 程倩磁盘调度 $n”);printf(* 1.先来先服务(FCFS) *n);printf(* 2. 最

18、短寻道时间优先(SSTF) *n);printf(* 3.扫描算法(SCAN)*n);printf(* 4.循环算法(C-SCAN)*n);printf(* 0. 退出*n);printf(I*n);printf(&谢谢使用 &n); printf( 请在下面输入您的选择:);scanf(%d,&k);switch(k)case 1:FCFS(a,n,init);break;case 2:SSTF(a,n,init);break; case 3:k1=1;while(k1)printf(*n);printf(#程倩磁盘调度 #n);printf(* 1.移动臂由里向外*n);printf(*

19、2.移动臂由外向里*n);printf(* 0. 返回上一层 *n);printf(I*n);printf(# 谢谢使用 #n);printf(请在下面输入您的选择:);scanf(%d,&k1);switch(k1)case 1:SCAN1(a,n,init);break;case 2:SCAN2(a,n,init);break;break;case 4:C_SCAN(a,n,init);break;四.运行结果及分析H :最原始磁盘调度模拟苴法,exe,1! x|1您您您您您迂显的的的的磁rrfhJfsrrhrrfhJfsrrhr*M-*3 *4.彳三孑田.退由法CYCAH YiMMMXX

20、MM磁盘调度晴在下面输入您的选择J2.最短寻道时间优先国H：最原始：.磁盘调度模拟算法.E吒-! x|Md+H* 制*=H第涸=H= *型#、#IrkTfMirwrarruMrrw fwfwwi工蕾军冒娱田*2 .先乘先服务FCFS)| 周 | th- rwFVFwrjwwwKrfwwwtrrwMr国简优先MSTP-M* 拧加心退田CC-SCfiNYiWfH#箕 ME MAAHMXMXMXXXXMMiK需展龄雒逑择门 唇遍麒黔底第4次访的磁道：9的磁道X可的磁道:m5次访问的磁道:三 寻道长度江. 4西碘目3.先来先服务国HA最原始磁盘调度模拟苴法,exe-|n| x| 日*1落*2冼*3.f

21、S*4.扫：退出.fuwruwzvruwzvruw庭服务FCF MCC-SCfiN 算 Y*HMbDOOtM人人rjT |JF) j 周 |-H- zzfvzzzfvzzzfvzzz情在下面输入您的选择;2 底第1次访儿a* -I I 的磁道口的磁道：6的磁道;3的磁道：4的磁道4.循环算法5.循环算法(1)磁头由里向外移动H：最原始遨盘调度模拟篁法,EXE刖，山5HU心十-Fi-r i-r u xji ujM M M JH M M HM HHfl -H M请标您平睽牖勺磁道嘱;揩敕* Ww 卜 4 I4次访的窿道：3可的磁道;95次访问的磁道：9 寻道长度:2.2酗酬目(2)磁头由外向里移动-|n| x|函H:.品原始，磁盘调度模拟苴法附* * 2.磁头由外向0.返回上一层fdwrhrzruwrhrzruwrhnj 干电，1；,土mruwrijwruwrijwruwrijwrv杯JI |芯人您存乳次访您堂2次访您意3次访您第4次访勺磁道二9问的磁道：6问的磁道：4您第5次访 平均寻道长度工40股眄