操作系统课程设计实验报告用C++实现驱动调度算法

1、操 作 系 统实验报告(4)学院：计算机科学与技术学院班级：计091学号： 2姓名：时间：2011/12/31目 录1. 实验名称32. 实验目的33. 实验内容34. 实验要求35. 实验原理36. 实验环境47. 实验设计47.1数据结构设计47.2算法设计57.3功能模块设计68. 实验运行结果109. 实验心得10附录：源代码（部分）11一、实验名称：用c+实现驱动调度算法二、实验目的：通过自己编程来实现驱动调度算法，进一步理解驱动调度算法的概念及含义，提高对驱动调度算法的认识，同时提高自己的动手实践能力。加强我们对磁盘调度的理解，有利于我们了解先来先服务算法、最短作业优先算法、响应比

2、最高优先者优先算法。三、实验内容：利用c+,实现驱动调度算法1. 先来先服务算法（fcfs）2. 最短作业优先算法（sjf）3. 响应比最高优先者优先算法（hrrf）四、实验要求：1.完成驱动调度算法的设计2.分别计算每种算法的经过磁道数五、实验原理：作为操作系统的辅助存储器，用来存放文件的磁盘是一类高速大容量旋转型存储设备，在繁重的i/o负载下，同时会有若干传输请求来到并等待处理，系统必须采用一种调度策略，按照最佳次序执行要求访问的诸多请求，减少为若干i/o请求服务所需消耗的总时间。磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效

3、率。1. 先入先出算法（fifo）：总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移动方向，效率有待提高2. 电梯调度算法：总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。3. 扫描算法（scan algorithm）：总是从最外向最内（或最内向最外）进行扫描，然后在从最内向最外（或最外向最内）扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最内的请求时不会移动到最外或最内柱面。六、实验环境：win-7系统visual c+ 6.0七、实验设计：1.数据结构设计定义结构体：str

4、uct magnetichead/磁头构成int site;/当前位置int count;/已扫描磁道数bool direct;/磁头移动方向;struct range/磁盘磁道范围int mstart;/起始值(0)int mend;/结束值();struct requestlist/请求序列int site;/请求磁道号bool state;/处理状态:true处理,false未处理;struct data/基本数据集合magnetichead magnetichead;/磁头requestlist *requestlist;/请求序列int *executelist;/执行序列range

5、 range;/磁盘磁道数范围int length;/请求数量;定义类对象：class display/封装显示方法private:public:display()/构造函数void displayexecutelist(data *db)/输出执行列cout执行列: ;for(int i=0;ilength;i+)coutexecutelisti ;coutexecutelisti;coutendl;cout经过磁道数: magnetichead.count;coutendl;void displayrequestlist(data *db)/输出请求列cout请求列: ;for(int i

6、=0;ilength;i+)coutrequestlisti.site ;coutendl;2.算法设计 2.1 fcfs算法void fcfs(data *db)/先来先服务算法int t=0;for(int i=0;ilength;i+)db-executelisti+1=db-requestlisti.site;db-magnetichead.site=db-requestlisti.site;t=db-executelisti-db-requestlisti.site;if(tmagnetichead.count+=t;2.2 电梯调度算法void elevator(data *db)

7、/电梯算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;/冒泡排序if(db-magnetichead.direct=false)/方向从小到大for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成执行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i

8、+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*adb-length-1;else /方向从大到小for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成执行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(in

9、t k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*adb-length-1-a0-db-magnetichead.site;/计算扫描磁道数2.3 扫描算法void scan(data *db)/扫描算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;if(db-magnetichead.dire

10、ct=true)for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*db-ran

11、ge.mstart;elsecoutaan;for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*db-range.mend-a0

12、-db-magnetichead.site; ;3.功能模块设计struct data/基本数据集合class display/封装显示方法class initdata/设置基本参数struct magnetichead/磁头构成class movemethod/封装调度方法struct range/磁盘磁道范围struct requestlist/请求序列void main() /主函数8、 实验运行结果：1.选择 fcfs算法实现：2.选择电梯调度算法实现3. 选择扫描算法实现九、实验心得：经过本次实验，我更加了解了磁盘调度算法。先来先服务算法磁盘臂是随机移动的，进程等待i/o请求的时间会

13、很长，寻道性较差。电梯调度算法，磁盘柱面号通常由外向里递增，磁头越向外，所处的柱面号越小。最短查找时间优先算法，总是先执行查找时间最短的请求，有较好的寻道性能。当然在实验过程中，我也遇到了一些困难，但是我通过及时请教同学，查询相关资料，及时解决了问题，但仍有不足之处，我将会在今后学习中更加努力。附录：源代码（部分）#includeusing namespace std;struct magnetichead/磁头构成int site;/当前位置int count;/已扫描磁道数bool direct;/磁头移动方向;struct range/磁盘磁道范围int mstart;/起始值(0)in

14、t mend;/结束值();struct requestlist/请求序列int site;/请求磁道号bool state;/处理状态:true处理,false未处理;struct data/基本数据集合magnetichead magnetichead;/磁头requestlist *requestlist;/请求序列int *executelist;/执行序列range range;/磁盘磁道数范围int length;/请求数量;class initdata/设置基本参数private:public:initdata()/构造函数void setrange(data *db)/设置磁道

15、范围int s=0,e=100;cout设置磁道范围: n;/coutse;db-range.mstart=s;db-range.mend=e;void setrequestlist(data *db)/设置请求列int len;int site=0;coutlen;/len=10;db-length=len;db-requestlist=new requestlistlen;db-executelist=new intlen+1;for(int i=0;ilen;i+)cout设置请求 isite;db-requestlisti.site=site;for( i=0;iexecutelist

16、i= db-magnetichead.site;db-requestlist9.state=false;void setmagnetichead(data *db)/设置当前磁道位置及方向int s,c,d;/cout预置当前磁道位置:25, 方向: 从大到小n;c=0;/d=0;couts;coutd;db-magnetichead.site=s;db-magnetichead.count=c;db-magnetichead.direct=d;class movemethod/封装调度方法private:public:movemethod()/构造函数void fcfs(data *db)/

17、先来先服务算法int t=0;for(int i=0;ilength;i+)db-executelisti+1=db-requestlisti.site;db-magnetichead.site=db-requestlisti.site;t=db-executelisti-db-requestlisti.site;if(tmagnetichead.count+=t;void elevator(data *db)/电梯算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;/冒泡排序i

18、f(db-magnetichead.direct=false)/方向从小到大for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成执行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.c

19、ount=a0+db-magnetichead.site-2*adb-length-1;else /方向从大到小for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;/生成执行序列for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1

20、;db-magnetichead.count=2*adb-length-1-a0-db-magnetichead.site;/计算扫描磁道数void scan(data *db)/扫描算法int *a;a=new intdb-length;for(int i = 0; ilength;i+)ai=db-requestlisti.site;int t;if(db-magnetichead.direct=true)for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;int j;for( i =

21、0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=a0+db-magnetichead.site-2*db-range.mstart;elsecoutaan;for( i = 1; ilength;i+)for(int j=0;jlength-i;j+)if(ajaj+1)t=aj;aj=aj+1;aj+1=t;i

22、nt j;for( i = 0; ilength;i+)if(db-magnetichead.site=ai)j=i;for(int k=0;klength;k+,i+)db-executelistk+1=ai;for(int l=db-length-j+1, i = 0; iexecutelistl=aj-i-1;db-magnetichead.count=2*db-range.mend-a0-db-magnetichead.site; ;class display/封装显示方法private:public:display()/构造函数void displayexecutelist(data *db)/输出执行列cout执行列: ;for(int i=0;ilength;i+)coutexecutelisti ;coutexecutelisti;coutendl;cout经过磁道数: magnetichead.count;coutendl;void displayreque