2022年磁盘调度报告 .pdf

1 操作系统课程设计题 目：磁盘调度指导老师：邹云 康姓名：程倩班级： 080412 学号： 08041214 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 14 页 - - - - - - - - - 2 一 课程设计目的本课程设计是学习完计算机操作系统课程后，进行的一次全面的综合训练，通过课程设计，我们更好地掌握操作系统的原理及实现方法, 加深对操作系统基础理论和重要算法的理解，加强了动手能力。二 课程设计内容和要求编程序实现下述磁盘调度算法, 并求出每种算法的平均寻道长度，要求设计主界面以灵活选择某算法，且以下算法都要实现：1、先来先服务算法（ FCFS ）2、最短寻道时间优先算法（SSTF ）3、扫描算法（ SCAN ）4、循环扫描算法（ CSCAN）三实现原理设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、 优先级高者先分配等策略。 在多道程序系统中， 低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率， 进而影响系统的性能。 访问磁盘的时间因子由3 部分构成，它们是查找（查找磁道） 时间、等待（旋转等待扇区） 时间和数据传输时间，其中查找时间是决定因素。 因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。平均寻道长度（ L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N） ，即：L=（M1+M2+ ,+Mi+,+MN ）/N 其中 Mi 为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。因此，执行一次输入输出所花的时间有：寻找时间磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间指定扇区旋转到磁头下所需的时间。传送时间由磁头进程读写完成信息传送的时间。其中传送信息所花的时间， 是在硬件设计就固定的。 而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后， 再放到下一个盘面上。 而是按柱面存放， 同一柱面上的各磁道被放满信息后， 再放到下一个柱面上。 所以各磁盘的编号按柱面顺序（从0 号柱面开始），每个柱面按磁道顺序，每个磁道又按扇区顺序进行排序。三 算法实现1. 先来先服务算法（ FCFS ）先来先服务（ FCFS ）调度 : 按先来后到次序服务，未作优化。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 14 页 - - - - - - - - - 3 最简单的移臂调度算法是 “先来先服务” 调度算法， 这个算法实际上不考虑访问者要求访问的物理位置， 而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50 号柱面上执行输出操作，而等待访问者依次要访问的柱面为 130、199、32、159、15、148、61、99，那么，当 50 号柱面上的操作结束后，移动臂将按请求的先后次序先移到130 号柱面，最后到达99 号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2. 短寻道时间优先算法（ SSTF ）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当 50 号柱面的操作结束后，应该先处理61 号柱面的请求，然后到达32 号柱面执行操作， 随后处理 15 号柱面请求， 后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了 200 多个柱面的距离， 与先来先服务、 算法比较， 大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（ SSTF ）调度，FCFS 会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。3. 扫描算法（ SCAN ）SCAN 算法又称电梯调度算法。 SCAN 算法是磁头前进方向上的最短查找时间优先算法，它排除了磁头在盘面局部位置上的往复移动，SCAN算法在很大程度上消除了 SSTF算法的不公平性，但仍有利于对中间磁道的请求。“电梯调度”算法是从移动臂当前位置开始沿着臂的移动方向去选择离当前移动臂最近的那个柱访问者， 如果沿臂的移动方向无请求访问时，就改变臂的移动方向再选择。 这好比乘电梯， 如果电梯已向上运动到4 层时，依次有 3 位乘客陈生、伍生、张生在等候乘电梯。他们的要求是：陈生在2 层等待去 10 层；伍生在 5 层等待去底层；张生在8 层等待 15 层。由于电梯目前运动方向是向上，所以电梯的形成是先把乘客张生从8 层带到 15 层，然后电梯换成下行方向，把乘客伍生从 5 层带到底层， 电梯最后再调换方向， 把乘客陈生从 2 层送到 10 层。我们仍用前述的同一例子来讨论采用“电梯调度” 算法的情况。 由于磁盘移动臂的初始方向有两个， 而该算法是与移动臂方向有关，所以分成两种情况来讨论。1. 移动臂由里向外移动开始时， ，在 50 号柱面执行操作的读写磁头的移动臂方向是由里向外，趋向32 号柱面的位置，因此，当访问50 号柱面的操作结束后，沿臂移动方向最近的柱面是 32 号柱面。所以应先为32 号柱面的访问者服务，然后是为15 号柱面的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 14 页 - - - - - - - - - 4 访问者服务。之后，由于在向外移方向已无访问等待者，故改变移动臂的方向，由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是61、99、130、148、159、199。2. 移动臂由外向里移动开始时，正在 50 号柱面执行操作的读写磁头的移动臂是由外向里（即向柱面号增大的内圈方向） 趋向 61 号柱面的位置， 因此，当访问 50 号柱面的操作结束后，沿臂移动方向最近的柱面是61 号柱面。所以，应先为 61 号柱面服务，然后按移动臂由外向里移动的方向，依次为99、130、148、159、199 柱面的访问者服务。当 201号柱面的操作结束后， 向里移动的方向已经无访问等待者，所以改变移动臂的前进方向，由里向外依次为32、15 柱面的访问者服务。“电梯调度”与 “最短寻找时间优先” 都是要尽量减少移动臂时所花的时间。所不同的是：“最短寻找时间优先”不考虑臂的移动方向，总是选择离当前读写磁头最近的那个柱面， 这种选择可能导致移动臂来回改变移动方向； “电梯调度”是沿着臂的移动方向去选择离当前读写词头最近的哪个柱面的访问者，仅当沿移动臂的前进移动方向无访问等待者时，才改变移动臂的前进方向。 由于移动臂改变方向是机械动作，速度相对较慢，所以，电梯调度算法是一种简单、使用且高效的调度算法。但是， “电梯调度”算法在实现时，不仅要记住读写磁头的当前位置，还必须记住移动臂的当前前进方向。4. 循环扫描算法（ CSCAN）单项扫描调度算法的基本思想是，不考虑访问者等待的先后次序，总是从0号柱面开始向里道扫描， 按照各自所要访问的柱面位置的次序去选择访问者。在移动臂到达最后一个柱面后， 立即快速返回到0 号柱面，返回时不为任何的访问者等待服务。在返回到0 号柱面后，再次进行扫描。由于该例中已假定读写的当前位置在50 号柱面，所以，指示了从 50 号柱面继续向里扫描，依次为61、99、130、148、159、199 各柱面的访问者服务，此时移动臂已经是最内的柱面，于是立即返回到0 号柱面，重新扫描，依次为15、32 号柱面的访问者服务。除了“先来先服务” 调度算法外， 其余三种调度算法都是根据欲访问的柱面位置来继续调度的。 在调度过程中可能有新的请求访问者加入。在这些新的请求访问者加入时， 如果读写已经超过了它们所要访问的柱面位置，则只能在以后的调度中被选择执行。 在多道程序设计系统中， 在等待访问磁盘的若干访问者请求中，可能要求访问的柱面号相同，但在同一柱面上的不同磁道，或访问同一柱面中同一磁道上的不同扇区。 所以，在进行移动调度时， 在按照某种短法把移动臂定位到某个柱面后， 应该在等待访问这个柱面的各个访问者的输入输出操作都完成之后，再改变移动臂的位置。五三个模块之间的调用关系图登录模块参数输入模块算法实现模块名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 14 页 - - - - - - - - - 5 六实现代码#include #include void 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(第%d次访问的磁道 :%dn,i+1,ai); sum+=abs(s-ai); s=ai; printf(平均寻道长度 :%fn,sum*1.0/n); void SSTF(int b,int n,int k) /最短寻道法 int 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(第%d次访问的磁道 :%dn,n-i,s); sum+=abs(s-k); k=s; printf(平均寻道长度 :%fn,sum*1.0/n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 14 页 - - - - - - - - - 6 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; 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(第%d次访问的磁道 :%dn,n-i,s); sum+=k-s; k=s; else s=a0; for(j=0;j=i;j+) if(aj-k=s-k) s=aj; p=j; ap=ai; printf(第%d次访问的磁道 :%dn,n-i,s); sum+=abs(k-s); k=s; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 14 页 - - - - - - - - - 7 printf(平均寻道长度 :%fn,sum*1.0/n); void SCAN2(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;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(第%d次访问的磁道 :%dn,n-i,s); sum+=s-k; k=s; else s=a0; for(j=0;j=i;j+) if(k-aj=k-s) s=aj; p=j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 14 页 - - - - - - - - - 8 ap=ai; printf(第%d次访问的磁道 :%dn,n-i,s); sum+=abs(k-s); k=s; printf(平均寻道长度 :%fn,sum*1.0/n); void C_SCAN(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;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(第%d次访问的磁道 :%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次访问的磁道 :%dn,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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 14 页 - - - - - - - - - 10 printf(*n); printf($程倩磁盘调度 $n); printf(* 1.先来先服务 (FCFS) *n); printf(* 2.最短寻道时间优先 (SSTF) *n); printf(* 3.扫描算法 (SCAN) *n); printf(* 4.循环算法 (C-SCAN) *n); printf(* 0.退出 *n); printf(*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(* 2.移动臂由外向里 *n); printf(* 0.返回上一层 *n); printf(*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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 14 页 - - - - - - - - - 11 七运行结果1. 选择调度方法2.最短寻道时间优先名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 14 页 - - - - - - - - - 12 3.先来先服务4.循环算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 14 页 - - - - - - - - - 13 5循环算法（1）磁头由里向外移动（2）磁头由外向里移动八心得体会通过此次课程设计， 我明白了实践的意义， 要把书本上的知识转换为现实中的成果，创新与不懈的努力也是成功的重要因素。如果没有一定的耐心， 这次的课程设计也不能成功。“磁盘调度”是我本学期操作系统课程设计的题目。 在设计此程序的过程中，我遇到过许多问题，也学到了很多东西。本程序的设计实现主要是用C+语言实现，通过对程序算法的设计优化、 输出显示的格式设计、输入过程中的异常处理等一些设计过程中的问题的考虑解决，在 C+学习上也有了很大的进步。在程序设计中先后参考了很多网络资料，也参考了一些别人写的的程序， 综合这些算法思想和自己的思路对程序做了很好的设计方式，对一些算法的优越性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 14 页 - - - - - - - - - 14 等也作了一些考虑。 此外考虑最多的就是异常错误处理的设计。在设置程序的显示优化时，发现暂停函数在不同的情况下执行顺序不同，如此等等。最后要感谢邹云康老师的不倦教导，我在将来会继续努力的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 14 页 - - - - - - - - -