OS实验指导五——磁盘调度模拟(新2014-12-15).doc

OS实验指导五 2013级师范+2014信管专业操作系统实验指导五开课实验室： 实验楼A207，A209 实验项目（五）磁盘调度模拟实验实验类型验证实验学时4一、实验目的 用不同算法实现对磁盘调度的模拟实现，并比较各算法性能。二、设备与环境 1. 硬件设备：PC机一台2. 软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C C+Java 等编程语言环境。三、实验要求设计并实现一个分别利用下列磁盘调度算法进行磁盘调度的模拟程序。l （1）扫描算法l （2）循环扫描算法设计要求：l1. 磁头初始磁道号，磁头初始运动方向，序列长度，磁道号序列等数据可键盘输入。l 2. 最好能实现磁道号序列中磁道号的动态增加。l 3. 磁道访问序列以链表的形式存储。l 4. 给出各磁盘调度算法的调度顺序和平均寻道长度。四、实验设计参考1. 算法说明（1）扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。2、循环扫描算法（CSCAN）循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。2. 主要功能模块流程图 开始手动输入磁道选择调度算法SCAN算法CSCAN算法向内寻道向外寻道显示运行结果结束3.源程序参考如下： #include #include #include #include #include#include using namespace std;class LinList;struct LinNodeint no;LinNode *next;class LinListprivate :LinNode *head;public :int size;LinList() /构造函数，用于构造头结点和声明长度head=new LinNode;head-next=NULL;size=0;void Insert(int no)/插入函数LinNode *newnode=new LinNode;newnode-no=no;newnode-next=NULL;Index(size-1)-next=newnode;size+;LinNode *Index(int i)/定位函数if(isize-1)coutnext;LinNode *p=head-next;int k=0;while(p!=NULL&knext;k+;return p;void SCAN1(int start_place)/电梯调度算法（向外寻道）coutSCAN调度算法(向外寻道)如下: ; float sum=0;float ave;int *a=sort();for( i=0 ; isize ; i+ )if(start_place=ai)for(int m=i;msize;m+)if(i=0&m=size-1)coutamendl;sum+=abs(am-am-1);elsecoutam;if(m=i)sum+=abs(start_place-ai);elsesum+= abs(am-ai) ;for(int n=i-1;n=0;n-)if(n=i-1)sum+=abs(an-asize-1);if(n!=i-1)sum+=abs(an-an+1);if(n=0)coutanendlendl;elsecoutan;ave= sum/size ;cout平均寻道长度为:aveendl;break;void SCAN2(int start_place)/电梯调度算法（向内寻道）coutSCAN调度算法(向内寻道)如下: ; float sum=0;float ave;int *a=sort();for(int i=0;isize;i+)if(start_place=0;n-)if(n=i-1)sum+=abs(an-ai);if(n!=i-1)sum+=abs(an-an+1);if(n=0)coutan;elsecoutan;for(int m=i;msize;m+)coutam;if(m=i)sum+=abs(start_place-a0);elsesum+=abs(am-am-1);coutn;ave= sum/size ;cout平均寻道长度为:aveendl;break;void CSCAN(int start_place) /循环算法coutCSCAN调度算法如下: ;float sum=0;float ave;int *a=sort();for(int i=0;isize;i+)if(start_place= ai )for(int m=i;msize;m+)if(i=0&m=size-1)coutamendl;sum+=abs(am-am-1);elsecoutam;if(m=i)sum+=abs(start_place-ai);elsesum+=abs(am-am-1);for(int n=0;n=i-1;n+)if(n=0)sum+=abs(an-asize-1);if(n!=0)sum+=abs(an-an-1);if(n=i-1)coutanendlendl;elsecoutan;ave= sum/size ;cout平均寻道长度为:aveendl;break;void show()/显示函数for(int i=0;isize;i+)if(i=size-1)coutnoendlendl;break;coutno;int *sort()/排序int count=0;int *a=new int size;a0=Index(0)-no;count+;for(int i=1;isize;i+)for(int j=0;jnoj;k-)ak=ak-1;aj=Index(i)-no; count+ ;break;if(Index(i)-no=aj)if(j=count-1)acount=Index(i)-no;count+;break;elsecontinue;return a;void main()cout *endl;cout * 丨磁*盘*调*度*2丨 *endl;cout *endl;LinList linlist;int i,start_place;cout请输入需要调度的序列(以0结束)：;while(cini&i)linlist.Insert(i);cout请输入开始的磁道号：;cinstart_place;cout链表的长度为：linlist.sizeendl;cout单链表显示：;linlist.show();int flag=1;while(flag)cout*endl;cout* 1:返回重新输入磁道 *endl; cout* 2:循环扫描算法 *endl;cout*3:扫描算法 *endl; cout*4:EXIT退出 *endl;cout*endl;cout请输入数字:;int k;cink;switch(k)case 1:main();break;case 2:linlist.CSCAN(start_place);break;case 3:cout *endl;cout * 5:向外寻道按，6:向内寻道按 *endl;cout *endl;cout;int j;cinj;switch(j)case 5:linl