操作系统课程设计-模拟电梯调度算法 实现对磁盘的驱动调度.doc

-衡阳师范学院操作系统课程设计报告设计题目：驱动调度系 别：计算机科学系专 业：计算机科学与技术（师范）班 级：1001班姓 名：肖瑶 张雅蓉学 号：10190125 10190133指导教师：王玉奇 2012年11月26日目录一、程序设计内容原理及目的 1、设计内容 2、设计原理 3、设计目的二、程序设计过程 1、驱动调度中的数据结构设计 2、程序算法设计三、用户手册 1、运行坏境 2、执行文件四、程序实现及运行结果 1、源代码 2、代码 3、 运行结果五、心得总结六、参考文献-二、程序设计内容原理及目的1、 设计内容 模拟电梯调度算法，实现对磁盘的驱动调度。2、 设计原理 作为操作系统的辅助存储器，用来存放文件的磁盘是一类高速大容量旋转型存储设备，在繁重的I/O负载下，同时会有若干传输请求来到并等待处理，系统必须采用一种调度策略，按照最佳次序执行要求访问的诸多请求，减少为若干I/O请求服务所需消耗的总时间。 磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。 电梯调动算法总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。3、 设计目的 磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。一、程序设计过程 1、 驱动调度中的数据结构设计typedef struct Process /描述进程信息char nameN; /进程名int cyl_num; /柱面号int tra_num; /磁道号int rec_num; /物理记录号int signal; /标记，用以判断结构体数组中该元素是否有效process;2、算法设计函数模块各函数调用关系如图1所示，箭头指向被调用的函数- 26 - 主函数随机数函数旋转调度函数移臂调度函数电梯调度函数接收请求函数图1 函数调用关系流程图各函数功能及流程图如下： 1)主函数：void main()函数功能：显示提示信息，初始化进程数组，根据随机数的值选择调用驱动调度和接收请求或者选择继续和退出程序。入口参数：无出口参数：无流程图：如图2所示开始信息输出提示初始化进程请求表（实际为进程的结构体数组）输入一个随机数驱动调度接收请求继续否是随机数0.5是否结束图2 主函数流程图2）随机数函数：float Ran_Num()函数功能：接收随机数入口参数 ：无出口参数：接收进来的随机数流程图：无3） 接收请求函数：void list(int pro_count,int pro_num,process proM) 函数功能：存放输入的进程信息，创建等待进程列表入口参数：初始化后的进程数组出口参数：无流程图：如图3所示开始i+有请求输入要输入的进程个数当前进程数组存入i=0否否是是第i个元素有效 否输入进程信息是输入信息有错是已输入的进程数+1+1已输入的进程数小于要输入的进程数否是返回图3 接收请求流程图4）旋转调度函数：void cir_sec(process proM)函数功能：如果有请求与当前柱面号相同，进行旋转调度，选择旋转距离最小的进程入口参数：部分全局变量及进程数组出口参数：选择的数组元素编号开始流程图：如图4所示否当前访问者旋转距离小于最小旋转距离是选择当前的访问进程结束图4 旋转调度流程图5) 移臂调度函数：void mov_sec(process proM)函数功能：没有与当前柱面号相同的访问请求时，进行移臂调度入口参数：进程数组出口参数：选择的数组元素编号流程图：如图5所示否是当前移臂方向是向里移开始有比当前柱面号小的访问请求有比当前柱面号大的访问请求否否是是置当前移臂方向为向里移置当前移臂方向为向外移从大于当前柱面号的访问请求中选择一个最小者从小于当前柱面号的访问请求中选择一个最小者旋转调度结束图5 移臂调度流程图6 ) 驱动调度函数：void dri_sch(int pro_count,process proM )函数功能：进行进程调度，按照电梯调度算法选择进程 入口参数：当前有效进程数、进程数组出口参数：无流程图：如图6所示开始查“请求I/O表”是否有等待访问者输出“请求I/O表”有请求与当前柱面号相同否是旋转调度移臂调度登记当前位置：柱面号，物理记录号输出选择的进程被选中者退出“请求I/O表”结束图6 驱动调度流程图三、用户手册1、 运行坏境Microsoft Visual C6.02、 执行文件文件夹中 .cpp文件或 .dsw四、程序实现及运行结果1、 源代码qddr.cpp 主函数pro_struct.h 结构体定义pro_list.h 创建进程请求表ran_num.h 接收随机数Driver_Scheduling.h 驱动调度2、 代码pro_struct.h#ifndef PRO_STRUCT_H#define PRO_STRUCT_H#define N 10typedef struct Processchar nameN;/进程名int cyl_num;/请求的柱面号int tra_num;/请求的磁道号int rec_num;/请求的物理记录号int signal;/标记位process;#endifpro_list.h#ifndef PRO_LIST_H#define PRO_LIST_H#include#include#includepro_struct.husing namespace std;#define M 100void list(int pro_count,int pro_num,process proM)/创建等待进程表coutpro_num;if(pro_num0&(pro_num+pro_count)=M)/判断要输入的进程数是否合法，输入后是否超出进程等待表所允许的最大值cout开始输入endl;int i,j=0,h;for(i=0;iM;i+)for(;proi.signal=0&proi.cyl_numproi.tra_numproi.rec_num;for(h=0;h10) cout进程名不合规定，超出指定长度或已存在，请重新输入进程名:; while(proi.cyl_num199)/判断柱面号是否越界 cout柱面号不合规定，请重新输入柱面号:proi.cyl_num;while(proi.tra_num19)/判断磁道号是否越界cout磁道号不合规定，请重新输入磁道号:proi.tra_num;while(proi.rec_num7)/判断物理记录号是否越界cout物理记录号不合规定，请重新输入物理记录号:proi.rec_num;proi.signal=1; elseif(pro_num=0)cout要输入的进程个数必须为正整数endl;elsecout进程数超出进程等待表所允许的最大量endl;cout当前最多允许输入(M-pro_count)个进程endl;#endif3Driver_Scheduling.h#include#include#includepro_list.h#includepro_struct.hint dir=0; /0,up向里；1,down向外int cylinder=0;int record=0;int min_rec=0;/移动到当前进程扇区所要移动的距离int min_r=8;/旋转调度中最小移动距离int max_min_cyl=200;/大于当前柱面号的访问请求中的最小者int min_min_cyl=200;/小于当前柱面号的访问请求中的最小者int x;int choosen=0;/被选中的进程void cir_sec(process proM) /旋转调度if(prox.rec_numrecord)min_rec=8-(record-prox.rec_num);elsemin_rec=prox.rec_num-record;if(min_rec=min_r)/首选移动距离最小，再选磁盘号最小min_r=min_rec;/选择移动距离最小的请求choosen=x;void mov_sec(process proM)/移臂调度int count_abo=0;int count_low=0;if(dir=0)/如果方向向里upfor(x=0;xcylinder)count_abo+;if(count_abo0)/有进程柱面号大于当前柱面号for(x=0;xcylinder&prox.cyl_nummax_min_cyl)/从大于当前柱面号的访问请求中选择一个最小者 max_min_cyl=prox.cyl_num;choosen=x;for(x=0;xM;x+)if(prox.signal=1) if(prox.cyl_num=max_min_cyl)/从大于当前柱面号的访问请求中选择一个最小者cir_sec(pro);/旋转调度elsedir=1;/改方向为向外，downfor(x=0;xM;x+)if(prox.signal=1) if(prox.cyl_numcylinder&prox.cyl_nummin_min_cyl)/从小于当前柱面号的访问请求中选择一个最小者min_min_cyl=prox.cyl_num;choosen=x; for(x=0;xM;x+)if(prox.signal=1)if(prox.cyl_num=min_min_cyl)cir_sec(pro);/旋转调度elsefor(x=0;xM;x+)if(prox.signal=1)if(prox.cyl_num0)/有进程柱面号大于当前柱面号for(x=0;xM;x+)if(prox.signal=1) if(prox.cyl_numcylinder&prox.cyl_nummin_min_cyl)/从小于当前柱面号的访问请求中选择一个最小者min_min_cyl=prox.cyl_num;choosen=x;for(x=0;xM;x+)if(prox.signal=1)if(prox.cyl_num=min_min_cyl)cir_sec(pro);/旋转调度 elsedir=0;/改方向为向里upfor(x=0;xcylinder&prox.cyl_nummax_min_cyl)/从大于当前柱面号的访问请求中选择一个最小者max_min_cyl=prox.cyl_num;choosen=x;for(x=0;xM;x+)if(prox.signal=1)if(prox.cyl_num=max_min_cyl)/从大于当前柱面号的访问请求中选择一个最小者cir_sec(pro);/旋转调度void dri_sch(int pro_count,process proM )/电梯调度max_min_cyl=200;/大于当前柱面号的访问请求中的最小者min_min_cyl=200;/小于当前柱面号的访问请求中的最小者min_r=8;choosen=0;int count_equ=0;if(pro_count!=0)/有等待访问的进程cout当前请求I/O表为:endl;coutendl;cout进程名柱面号磁道号物理记录号endl;coutendl;cout.setf(ios:left);for(x=0;xM;x+)if(prox.signal=1)cout setw(10)setw(8)prox.cyl_numsetw(8)prox.tra_numsetw(8)prox.rec_numendl; cout.unsetf(ios:left);for(x=0;x0)for(x=0;xM;x+)if(prox.signal=1)if(prox.cyl_num=cylinder)cir_sec(pro);/旋转调度 elsemov_sec(pro);/移臂调度cylinder=prochoosen.cyl_num;record=prochoosen.rec_num;prochoosen.signal=0;if(dir=0)cout选择的进程为:endl;coutendl;cout进程名柱面号物理记录号方向endl; coutendl;cout.setf(ios:left);cout setw(10)setw(8)prochoosen.cyl_numsetw(10)prochoosen.rec_numsetw(8)upendl;cout.unsetf(ios:left);elsecout选择的进程为:endl;coutendl;cout进程名柱面号物理记录号方向 endl; coutendl;cout.setf(ios:left); cout setw(10)setw(8)prochoosen.cyl_numsetw(10)prochoosen.rec_numsetw(8)downendl;cout.unsetf(ios:left);else cout请求I/O表为空endl;ran_num.h#includefloat Ran_Num()float ran_num;/*float i;i=float(rand();if(i=0|1)ran_num=i;elseran_num=1/i; */cout输入随机数0,1:endl;cout0.5时转入电梯调度endl;cout随机数=0.5时转入接收请求ran_num;return(ran_num);qddd.cpp#include#includeDriver_Scheduling.h#includepro_list.h#includepro_struct.h#includeran_num.husing namespace std;void main()cout*endl;cout请按照如下顺序输入各进程信息,以空格分开,每条进程信息输入完成后按回车键结束:endl;cout进程名 柱面号 磁道号 物理记录号endl;cout注：进程名不超过10个字符，柱面号为0-199，磁道号为0-19，物理记录号为0-7endl;cout*endl;int i; process proM;/创建进程数组for(i=0;i0.5)/如果随即数大于0.5，转到调度模块pro_count=0;for(i=0;iM;i+)if(proi.signal=1)pro_count+;/统计进程等代表中有效进程数dri_sch(pro_count,pro); else/若随机数小于等于0.5，转到接受请求，即创建等待进程表pro_count=0;list(pro_count,pro_num,pro);coutendlsignal;while(signal!=Y&signal!=N&signal!=y&signal!=n)cout输入错误，请输入Y(y)或N(n)signal;3、 运行结果1）初始状态，结果如图7所示 图7 初始状态2） 输入0.4，输入进程数据并选择继续，结果如图8所示 图8 输入5个进程的相关信息3）重复选择继续，进行驱动调度直到等待进程表为空，结果如图9图13所示第一次选择P5 图9 第一次选择后结果第二次选择P3图10 第二次选择后结果第三次选择P1图11 第三次选择后结果第四次选择P4图12 第四次选择后结果第五次选择P2，当前等待表为空图13 第五次选择后，进程等待表为空4）选择继续，输入0.4，再输入3个进程，结果如图14所