版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
PAGEPAGE1实验七磁盘调度算法实验目的本课程设计是学习完《计算机操作系统》课程后,进行的一次全面的综合训练,通过课程设计,我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解,加强了动手能力。实验内容和要求编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度,要求设计主界面以灵活选择某算法,且以下算法都要实现:1、先来先服务算法(FCFS)2、最短寻道时间优先算法(SSTF)3、扫描算法(SCAN)//4、循环扫描算法(CSCAN)下面给出的程序中已经给出了1、2两个算法,请根据这两个算法完成3、4算法。三.实现原理设备的动态分配算法与进程调度相似,也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中,低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中,对磁盘的访问要求来自多方面,常常需要排队。这时,对众多的访问要求按一定的次序响应,会直接影响磁盘的工作效率,进而影响系统的性能。访问磁盘的时间因子由3部分构成,它们是查找(查找磁道)时间、等待(旋转等待扇区)时间和数据传输时间,其中查找时间是决定因素。因此,磁盘调度算法先考虑优化查找策略,需要时再优化旋转等待策略。平均寻道长度(L)为所有磁道所需移动距离之和除以总的所需访问的磁道数(N),即:L=(M1+M2+……+Mi+……+MN)/N其中Mi为所需访问的磁道号所需移动的磁道数。启动磁盘执行输入输出操作时,要把移动臂移动到指定的柱面,再等待指定扇区的旋转到磁头位置下,然后让指定的磁头进行读写,完成信息传送。因此,执行一次输入输出所花的时间有:寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。延迟时间——指定扇区旋转到磁头下所需的时间。传送时间——由磁头进程读写完成信息传送的时间。其中传送信息所花的时间,是在硬件设计就固定的。而寻找时间和延迟时间是与信息在磁盘上的位置有关。为了减少移动臂进行移动花费的时间,每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后,再放到下一个盘面上。而是按柱面存放,同一柱面上的各磁道被放满信息后,再放到下一个柱面上。所以各磁盘的编号按柱面顺序(从0号柱面开始),每个柱面按磁道顺序,每个磁道又按扇区顺序进行排序。算法实现1.先来先服务算法(FCFS)先来先服务(FCFS)调度:按先来后到次序服务,未作优化。最简单的移臂调度算法是“先来先服务”调度算法,这个算法实际上不考虑访问者要求访问的物理位置,而只是考虑访问者提出访问请求的先后次序。例如,如果现在读写磁头正在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号柱面的访问者服务。之后,由于在向外移方向已无访问等待者,故改变移动臂的方向,由外向里依次为各访问者服务。在这种情况下为等待访问者服务的次序是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号柱面的访问者服务。除了“先来先服务”调度算法外,其余三种调度算法都是根据欲访问的柱面位置来继续调度的。在调度过程中可能有新的请求访问者加入。在这些新的请求访问者加入时,如果读写已经超过了它们所要访问的柱面位置,则只能在以后的调度中被选择执行。在多道程序设计系统中,在等待访问磁盘的若干访问者请求中,可能要求访问的柱面号相同,但在同一柱面上的不同磁道,或访问同一柱面中同一磁道上的不同扇区。所以,在进行移动调度时,在按照某种短法把移动臂定位到某个柱面后,应该在等待访问这个柱面的各个访问者的输入输出操作都完成之后,再改变移动臂的位置。五.三个模块之间的调用关系图登录模块登录模块参数输入模块算法实现模块六.实现代码#include<stdio.h>#include<math.h>voidFCFS(intb[],intn,intinit)//先来先服务{ inti,s,sum; inta[20]; for(i=0;i<n;i++) a[i]=b[i]; s=init; sum=0; for(i=0;i<n;i++) { printf("第%d次访问的磁道:%d\n",i+1,a[i]); sum+=abs(s-a[i]); s=a[i]; } printf("平均寻道长度:%f\n",sum*1.0/n);}voidSSTF(intb[],intn,intk)//最短寻道法{ inti,j,s,sum=0,p; inta[20]; for(i=0;i<n;i++) a[i]=b[i]; for(i=n-1;i>=0;i--) { s=a[0]; p=0; for(j=0;j<=i;j++) if(abs(a[j]-k)<abs(s-k)) { s=a[j]; p=j; } a[p]=a[i]; printf("第%d次访问的磁道:%d\n",n-i,s); sum+=abs(s-k); k=s; } printf("平均寻道长度:%f\n",sum*1.0/n);}//电梯调度算法//循环扫描算法voidmain(){ inta[20]; inti,n,k,k1,init; printf("请输入需要访问的磁道总数:"); scanf("%d",&n); for(i=0;i<n;i++) { printf("需要访问的磁道%d:",i+1); scanf("%d",&a[i]); } printf("请输入指针所在磁道:"); scanf("%d",&init); k=1; while(k) { 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) { case1:FCFS(a,n,init);break; case2:SSTF(a,n,init);break; case3:k1=1; while(k1) { printf("*********************************\n"); printf("########程倩--磁盘调度###########\n"); printf("****1.移动臂由里向外**\n"); printf("****2.移动臂由外向里**\n"); printf("****0.返回上一层**\n"); printf("*********************************\n"); printf("#############谢谢使用############\n"); printf("请在下面输入您的选择:"); scanf
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025常用版固定期限聘用合同书
- 2025年有限公司报税代理合同模板范文
- 大班数学活动统计动物数量
- 提高教师教学质量的评估指
- 2024年江苏省南通市中考历史真题卷及答案解析
- 兼职研究员数据分析合同
- 纺织品店冬季取暖安全管理办法
- 酒店财务经理聘用协议
- 动物园墙面施工协议
- 桥梁施工脚手架租赁协议样本
- 校园文化建设先进个人苟光武同志事迹材料
- 舞蹈教育专业建设调研报告
- 安徽六国化工股份有限公司磷石膏生态环境影响综合整治及绿色发展项目环境影响报告书
- TOEFL阅读100篇附答案
- 2023年高考四省联考化学试题解析
- 医院煎药室-煎药试题
- 古今医学文献研究方法与实践(视频课)知到章节答案智慧树2023年浙江中医药大学
- 来曲唑超说明书用药
- 中等专业学校毕业生登记表
- 同一适宜生态区主要农作物品种引种备案办事指南
- 矿山地质环境保护与治理恢复方案编制规范
评论
0/150
提交评论