操作系统磁盘调度算法实验报告.doc
- 文档编号:1238156
- 上传时间:2023-04-30
- 格式:DOC
- 页数:16
- 大小:317KB
操作系统磁盘调度算法实验报告.doc
《操作系统磁盘调度算法实验报告.doc》由会员分享,可在线阅读,更多相关《操作系统磁盘调度算法实验报告.doc(16页珍藏版)》请在冰点文库上搜索。
目录
一、课程设计目的 3
二、课程设计要求 3
三、课程设计原理 3
四、程序代码 5
五、流程图设计 11
六、运行结果 14
七、调试分析 16
八、心得体会 16
一、课程设计目的
操作系统是最重要的计算机系统软件,同时也是最活跃的学科之一,发展极为迅速。
我们在本课程的实验过程中,要了解实际操作系统的工作过程,加深对操作系统基础理论和重要算法的理解,在实践过程中加深对操作系统原理的理解。
通过设计一个磁盘调度模拟系统,以加深对先来先服务、最短寻道时间、电梯算法以及循环扫描算法等磁盘调度算法的理解。
让我们更好地掌握操作系统中磁盘调度的原理及实现方法,增强动手能力。
本实验通过对磁盘调度算法的实现,加深对算法的理解,同时通过用C++语言编写程序实现这些算法,并在windows平台上实现,也再一次提高了自己编程的能力,提高了综合运用专业课知识的能力。
二、课程设计要求
本设计的具体要求如下:
1.模拟一个磁盘调度算法
2.要求能够模拟FCFS、最短寻道时间、电梯算法等磁盘调度算法
3.输入为一组作业的磁道请求
4.输出为按选择的算法执行时的磁头移动轨迹
三、课程设计原理
1.各个算法分析
(1)先来先服务算法(FCFS)
这是一种最简单的磁盘调度算法。
它根据请求访问磁盘的先后次序进行调度。
此算法的优点是公平、简单,且每个进程的请求都能依次地得到处理,不会出现某一进程的请求长期得不到满足的情况。
但是此算法由于未对寻道进行优化,致使平均寻道时间可能较长。
当有进程先后提出磁盘I/O请求时,先按他们发出请求的先后次序排队。
然后依次给予服务。
其平均寻道距离较大,故先来先服务算法仅适用于请求磁盘I/O进程数目较少的场合。
(2)最短寻道时间优先算法(SSTF)
该算法选择这样的进程:
其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次寻道时间最短。
但这种算法不能保证平均寻道时间最短。
有可能导致某个进程出现“饥饿”现象,因为只要不断有新进程请求到达,且其所要访问的磁道与磁头当前所在的磁道的距离较近,这种新进程的I/O请求必然优先满足。
(3)扫描算法(SCAN)
该算法不仅考虑到正欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。
例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象应该是其欲访问的磁道之外,又是距离最近的。
这样自里向外地访问,直至再无更外的磁道需要访问时,才将磁臂换向为自外向里移动。
这时,同样也是每次选择这样的进程来调度,既要访问的磁道在当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现象。
由于在这种算法中磁头移动的规律颇似电梯的运行,因而又常称之为电梯调度算法。
(4)循环扫描算法(CSCAN)
SCAN算法规定磁头单向移动,例如,只是自里向外移动,当磁头移动到最外的磁道并访问后,磁头立即返回到最里的欲访问的磁道,亦即将最小磁道号紧接着最大的磁道号构成循环,进行循环扫描。
2.磁盘调度思想
磁盘设备在工作时以恒定的速率旋转。
为了读或写,磁头必须能移动到所要求的磁道上,并等待所要求的扇区开始位置旋转到磁头下,然后或开始读或写数据。
故可把磁盘访问时间分成以下三部分。
(1)寻道时间Ts
这是把磁头移动到指定磁道上所经历的时间。
该时间是启动磁臂的时间s与磁头移动n条磁道所花费的时间之和,即
Ts=m*n+s
其中,m是一常数,与磁盘驱动器的速度有关。
对于一般磁盘,m=0.2;对于高速磁盘,m<=0.1,磁臂的启动时间+约为2ms。
这样,对于一般的温盘,对于一般的温盘,其寻道时间将随着寻道距离的增加而增大,大体上是5~30ms。
(2)旋转延迟时间Tr
这是指定扇区移动到磁头下面所经历的时间。
不同的磁盘类型中,旋转速度至少相差一个数量级,如软盘为300r/min,硬盘一般为7200~15000r/min,甚至更高。
对于磁盘旋转延迟时间而言,如硬盘,旋转速度为15000r/min,每转需时4ms,平均旋转延迟时间Tr为2ms;而软盘,其旋转速度为300r/min或600r/min,这样,平均Tr为50~100ms。
(3)传输时间Tt
这时指把数据从磁盘读出或向磁盘写入数据所经历的时间。
Tt的大小与每次所读/写的字节数b和旋转速度有关:
Tt=b/(r*N)
其中,r为磁盘每秒钟的转数;N为一条磁道上的字节数,当一次读/写的字节数相当于半条磁道上的字节数时,T3与T2相同。
因此,可将访问时间Ta表示为
Ta=Ts+1/(2*r)+b/(r*N)
由上式可以看出,在访问时间中,寻道时间和旋转延迟时间基本上都与所读/写数据的多少无关,而且它通常占据了访问时间中的大头。
磁盘是可供多个进程共享的设备,当有多个进程都要求访问磁盘时,应采用一种最佳调度算法,以使各进程对磁盘的平均访问时间最小。
由于在访问磁盘的时间中,主要是寻道时间,因此,磁盘调度的目标是使磁盘的平均寻道时间最少。
现在我们考虑平均寻道长度:
所有磁道所需移动距离之和除以总的所需访问的磁道数,所以寻道长度决定了寻道时间,我们需要从上面的算法中选择最优者。
四、程序代码
下面给出部分重要的程序
/*********************先来先服务调度算法**************************/
voidFCFS(intcidao[],intm)//磁道号数组,磁道数为m
{
intnow;//当前所在磁道号
intsum=0;//总寻道长度
inti;
intj;
inta;
charstr[max];
floatave;//平均寻道长度
cout<<"磁盘请求序列为:
";
for(i=0;i { cout< } cout< cout<<"请输入当前的磁道号: "; BB: cin>>str;//判断输入的数据是不是正确 a=panduan(str); if(a==0) { cout<<"数据类型错误,请重新输入! "< gotoBB; } else now=zhuanhuan(str,a);//当前磁道号 sum+=abs(cidao[0]-now); cout<<"磁盘扫描序列为: "; for(i=0;i { cout< } for(i=0,j=1;j { sum+=abs(cidao[j]-cidao[i]); ave=(float)(sum)/(float)(m); } cout< cout<<"平均寻道长度: "< } /**********************最短寻道时间优先调度算法********************/ voidSSTF(intcidao[],intm) { intk=1; intnow,l,r; inti,j,sum=0; inta; charstr[max]; floatave; cidao=paixu(cidao,m);//调用排序算法排序 cout<<"请输入当前的磁道号: "; CC: cin>>str;//判断输入的数据是不是正确 a=panduan(str); if(a==0) { cout<<"数据类型错误,请重新输入! "< gotoCC; } else now=zhuanhuan(str,a);//输入当前磁道号 if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者,则直接由外向内依次给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=m-1;i>=0;i--) cout< sum=now-cidao[0]; } if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=0;i cout< sum=cidao[m-1]-now; } if(now>cidao[0]&&now { cout<<"磁盘扫描序列为: "; while(cidao[k] { k++; } l=k-1; r=k; while((l>=0)&&(r { if((now-cidao[l])<=(cidao[r]-now))//选择与当前磁道最近的请求给予服务 { cout< sum+=now-cidao[l]; now=cidao[l]; l=l-1; } else { cout< sum+=cidao[r]-now; now=cidao[r]; r=r+1; } } if(l==-1)//说明磁头已移动到序列的最小号,现返回外侧扫描仍未扫描的磁道 { for(j=r;j { cout< } sum+=cidao[m-1]-cidao[0]; } else//说明磁头已移动到序列的最大号,现返回内侧扫描仍未扫描的磁道 { for(j=l;j>=0;j--) { cout< } sum+=cidao[m-1]-cidao[0]; } } ave=(float)(sum)/(float)(m); cout< cout<<"平均寻道长度: "< } /*****************************电梯算法*******************************/ voidSCAN(intcidao[],intm)//先要给出当前磁道号和移动臂的移动方向 { intk=1; intnow,l,r,d; inti,j,sum=0; inta; charstr[max]; floatave; cidao=paixu(cidao,m);//调用排序算法排序 cout<<"请输入当前的磁道号: "; DD: cin>>str;//判断输入的数据是否正确 a=panduan(str); if(a==0) { cout<<"数据类型错误,请重新输入! "< gotoDD; } else now=zhuanhuan(str,a);//输入当前磁道号 if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者,则直接由外向内依次给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=m-1;i>=0;i--) cout< sum=now-cidao[0]; } if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=0;i cout< sum=cidao[m-1]-now; } if(now>cidao[0]&&now { while(cidao[k] { k++; } l=k-1; r=k; cout<<"请输入当前移动臂的移动的方向(0表示由外向内,1表示由内向外): "; cin>>d; if(d==0)//选择移动臂方向向内,则先向内扫描 { cout<<"磁盘扫描序列为: "; for(j=l;j>=0;j--) { cout< } for(j=r;j { cout< } sum=now-2*cidao[0]+cidao[m-1]; } else//选择移动臂方向向外,则先向外扫描 { cout<<"磁盘扫描序列为: "; for(j=r;j { cout< } for(j=l;j>=0;j--)//磁头移动到最大号,则改变方向向内扫描未扫描的磁道 { cout< } sum=-now-cidao[0]+2*cidao[m-1]; } } ave=(float)(sum)/(float)(m); cout< cout<<"平均寻道长度: "< } /***********************循环扫描调度算法*****************************/ voidCSCAN(intcidao[],intm) { intk=1; intnow,l,r; inti,j,sum=0; inta; charstr[max]; floatave; cidao=paixu(cidao,m);//调用排序算法排序 cout<<"请输入当前的磁道号: "; EE: cin>>str;//判断输入的数据是否正确 a=panduan(str); if(a==0) { cout<<"数据类型错误,请重新输入! "< gotoEE; } else now=zhuanhuan(str,a);//输入当前磁道号 if(cidao[m-1]<=now)//若当前磁道号大于请求序列中最大者,则直接将移动臂移动到最小号磁道依次向外给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=0;i cout< sum=now-2*cidao[0]+cidao[m-1]; } if(cidao[0]>=now)//若当前磁道号小于请求序列中最小者,则直接由内向外依次给予各请求服务 { cout<<"磁盘扫描序列为: "; for(i=0;i cout< sum=cidao[m-1]-now; } if(now>cidao[0]&&now { cout<<"磁盘扫描序列为: "; while(cidao[k] { k++; } l=k-1; r=k; for(j=r;j { cout< } for(j=0;j { cout< } sum=2*cidao[m-1]+cidao[l]-now-2*cidao[0]; } ave=(float)(sum)/(float)(m); cout< cout<<"平均寻道长度: "< } 五、流程图设计 1..先来先服务算法流程图 输入当前磁道号now 磁头移动距离 sum=abs(now-cidao[0]) 磁头移动总距离sum+=abs(cidao[j]-cidao[i]) 输出磁盘调度序列cidao[j] 目前的位置变为当前的位置j++ j 输出平均寻道长度 ave=sum/(m) 2.最短寻道时间优先算法流程图 将磁道号从小到大排序 输入当前磁道号now cidao[m-1]<=now 输出磁盘调度序列cidao[j] 目前的位置变为当前的位置now=cidao[i] 磁头移动总距离sum=now-cidao[i] i>=0 输出磁盘调度序列cidao[j] (cidao[0]>=now 磁头移动总距离sum=now-cidao[i] 目前的位置变为当前的位置now=cidao[i] now=array[i] i 确定当前磁道在已排的序列中的位置 now-cidao[l])<=(cidao[r]-now 先向磁道号减小方向访问,再向磁道号增加方向访问 输出磁盘调度序列 先向磁道号增加方向访问,再向磁道号减小方向访问 输出磁盘调度序列 输出平均寻道长度ave=sum/(m) 3.扫描算法流程图 将磁道号从小到大排序 输入当前磁道号now,移动臂的移动的方向 cidao[m-1]<=now 磁头移动总距离sum=now-cidao[i] 输出磁盘调度序列cidao[j] i>=0 (cidao[0]>=now 输出磁盘调度序列cidao[j] i 磁头移动总距离sum=cidao[i]-now 确定当前磁道在已排的序列中的位置 switch(d) case0: 移动臂向磁道号减小方向访问 case1: 移动臂向磁道号增加方向访问 访问 输出磁盘调度序列 输出磁盘调度序列 输出平均寻道长度ave=sum/(m) 六、运行结果 1.程序运行后的开始界面如下: 图1 2.先来先服务算法程序运行界面如下: 图2 3.最短寻道时间优先算法程序运行界面如下: 图3 4.电梯算法程序运行界面如下: 图4 图5 5.循环扫描算法程序运行界面如下: 图6 七、调试分析 此程序结果显示的界面非常清楚、友好。 首先,需要用户输入所有的磁道号,此时若输入的不是数字,则提示有错误,重新输入,若正确,则可继续输入;若输入的是数字0,则结束输入。 用户输入的磁道号会按照输入的顺序依次显示在界面上,如图1。 选择调度算法1,则系统调用先来先服务算法,然后给出磁盘请求序列,然后依次按照请求序列给予服务,计算总寻道长度,最后计算平均寻道长度,如图2。 选择调度算法2,则系统调用最短寻道时间优先算法,先给出磁道排序序列,再给出磁道服务序列,计算总长度和平均长度,如图3。 选择调度算法3,则系统调用扫描算法,系统先给出排序序列,此时用户需要选择磁臂的移动方向,按由内向外或者由外向内两种方式给予服务,最后计算总寻道长度和平均长度,如图4、5。 选择调度算法4,系统调用循环扫描算法,先给出排序序列,再给出磁道扫描序列,最后计算总寻道长度和平均寻道长度,如图6。 八、心得体会 十几天的课设时间很快就过去了,其中既有欢乐又有痛苦。 通过这次的课程设计,我认识到要将操作系统这门计算机专业的课学好不仅仅是要把书上的基本知识学好,还要不断进行实践,将所学的跟实践操作结合起来才能更好地巩固所学,才能提高自己实践能力.通过这次的设计使我认识到只停留在表面理解问题是很难使问题得到很好的解决的,实践能力与理论知识同样重要。 这次试验的理论难度并不大,但是若要深入发掘其中的东西,并且实际去编程实现,就遇到了相当大的难度。 我们的编程能力并不是特别突出,又要在很短的时间
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 操作系统 磁盘 调度 算法 实验 报告