《操作系统_磁盘调度算法》由会员分享,可在线阅读,更多相关《操作系统_磁盘调度算法(18页珍藏版)》请在金锄头文库上搜索。
1、操 作 系 统实验报告(4)学院:计算机科学与技术学院班级:计 091学号:0913022032姓名:曹恒楼时间:2011/12/31 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页,共 18 页 -2 目录1.实验名称3 2.实验目的3 3.实验内容3 4.实验要求3 5.实验原理3 6.实验环境4 7.实验设计4 7.1数据结构设计47.2算法设计57.3功能模块设计68.实验运行结果10 9.实验心得10 附录:源代码(部分)11名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 18 页 -3 一、实验名称:用 C+实现驱动调度算法二、实验目的:通过自己编程来实现驱
2、动调度算法,进一步理解驱动调度算法的概念及含义,提高对驱动调度算法的认识,同时提高自己的动手实践能力。加强我们对磁盘调度的理解,有利于我们了解先来先服务算法、最短作业优先算法、响应比最高优先者优先算法。三、实验内容:利用 C+,实现驱动调度算法1.先来先服务算法(FCFS)2.最短作业优先算法(SJF)3.响应比最高优先者优先算法(HRRF)四、实验要求:1.完成驱动调度算法的设计2.分别计算每种算法的经过磁道数五、实验原理:作为操作系统的辅助存储器,用来存放文件的磁盘是一类高速大容量旋转型存储设备,在繁重的I/O 负载下,同时会有若干传输请求来到并等待处理,系统必须采用一种调度策略,按照最佳
3、次序执行要求访问的诸多请求,减少为若干I/O 请求服务所需消耗的总时间。磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率,从而影响计算机系统的整体效率。1.先入先出算法(FIFO):总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平,不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移动方向,效率有待提高2.电梯调度算法:总是将一个方向上的请求全部处理完后,才改变方向继续处理其他请求。3.扫描算法(scan algorithm):总是从最外向最内(或最内向最外)进行扫描,然后在从最内向最外(或最外向最内)扫描。该算法与电梯
4、调度算法的区别是电梯调度在没有最外或最内的请求时不会移动到最外或最内柱面。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 18 页 -4 六、实验环境:Win-7 系统Visual C+6.0 七、实验设计:1.数据结构设计定义结构体:struct MagneticHead/磁头构成 int site;/当前位置int count;/已扫描磁道数bool direct;/磁头移动方向;struct Range/磁盘磁道范围 int mStart;/起始值(0)int mEnd;/结束值();struct RequestList/请求序列 int site;/请求磁道号bool s
5、tate;/处理状态:true 处理,false 未处理;struct Data/基本数据集合 MagneticHead magneticHead;/磁头RequestList*requestList;/请求序列int*executeList;/执行序列Range range;/磁盘磁道数范围int length;/请求数量;定义类对象:class Display/封装显示方法 private:public:名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 18 页 -5 Display()/构造函数 void displayExecuteList(Data*db)/输出执行列 c
6、out 执行列:;for(int i=0;ilength;i+)coutexecuteListi;coutexecuteListi;coutendl;cout 经过磁道数:magneticHead.count;coutendl;void displayRequestList(Data*db)/输出请求列 cout 请求列:;for(int i=0;ilength;i+)coutrequestListi.site;coutendl;2.算法设计2.1 FCFS 算法void fcfs(Data*db)/先来先服务算法 int t=0;for(int i=0;ilength;i+)db-execu
7、teListi+1=db-requestListi.site;db-magneticHead.site=db-requestListi.site;t=db-executeListi-db-requestListi.site;if(tmagneticHead.count+=t;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 18 页 -6 2.2 电梯调度算法void elevator(Data*db)/电梯算法 int*a;a=new intdb-length;for(int i=0;ilength;i+)ai=db-requestListi.site;int t;/冒泡排序if
8、(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.count=a0+db-m
9、agneticHead.site-2*adb-length-1;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页,共 18 页 -7 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;iexec
10、uteListl=aj-i-1;db-magneticHead.count=2*adb-length-1-a0-db-magneticHead.site;/计算扫描磁道数 2.3 扫描算法void scan(Data*db)/扫描算法 int*a;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页,共 18 页 -8 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;jle
11、ngth-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-range.mStart;else coutaan;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页,共
12、18 页 -9 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-db-magneticHead.site;3.功能
13、模块设计struct Data/基本数据集合class Display/封装显示方法class InitData/设置基本参数struct MagneticHead/磁头构成class MoveMethod/封装调度方法struct Range/磁盘磁道范围struct RequestList/请求序列void main()/主函数名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页,共 18 页 -10 八、实验运行结果:1.选择FCFS 算法实现:2.选择电梯调度算法实现3.选择扫描算法实现九、实验心得:经过本次实验,我更加了解了磁盘调度算法。先来先服务算法磁盘臂是随机移动的,进程等待
14、 I/O 请求的时间会很长,寻道性较差。电梯调度算法,磁盘柱面号通常由外向里递增,磁头越向外,所处的柱面号越小。最短查找时间优先算法,总是先执行查找时间最短的请求,有较好的寻道性能。当然在实验过程中,我也遇到了一些困难,但是我通过及时请教同学,查询相关资料,及时解决了问题,但仍有不足之处,我将会在今后学习中更加努力。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页,共 18 页 -11 附录:源代码(部分)#include using namespace std;struct MagneticHead/磁头构成 int site;/当前位置int count;/已扫描磁道数bool
15、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 range;/磁盘磁道数范围int length;/请求数量;class InitData/设置基本参数
16、private:public:InitData()/构造函数 void setRange(Data*db)/设置磁道范围 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;iexecuteListi=db-magneticHead.site;db-requestList9.state=false;void setMagneticHead(Data*db)/设置当前磁道位置及方向 int s,c,d;/cout 预置当前磁道位置:25,方向:从大到小 n;c=0;/d=0;co