实验二作业调度一、实验名称作业调度算法的模拟实现二、实验目标作业调度又称宏观调度，其主要任务是对磁盘设备上大量的后备作业，以一定的原则进行挑选，给选中的作业分配内存等必须的资源，建立其相应的进程，让其投入运行。本实验要求学生用高级程序设计语言编写和调试一个简化的作业调度程序， 模拟实现的调度算法包括： 先来先服务调度算法， 短作业优先调度算法，响应比高者优先调度算法等，并对这些算法的性能做比较和评价。以加深学生对作业、作业调度以及作业调度的各种算法的理解。三、实验环境要求Windows+Visual C+ 6.0；四、实验基本原理作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。（1）创建 JCB（作业控制块）：系统在作业进入后备状态时为每个作业创建一个作业控制块 （JCB）,从而使该作业可被调度程序感知。当该作业执行完毕进入完成状态时候，系统自动撤销其JCB并释放有关资源，进而撤销该作业。（2）按照作业调度算法，从后备队列中挑选一作业投入运行。作业调度程序为运行作业建立相应的进程，并分配资源。（3）主要的作业调度算法包括：先来先服务（FCFS） 、短作业优先和最高响应比。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 - - - - - - - - - （4）调度策略的指标：最常用的调度性能指标有，周转时间（带权）、吞吐率、响应时间以及设备利用率。五、数据结构设计（1）作业控制块，包括作业的基本信息描述。struct time /时间的数据结构 int hour; int minute; ; struct Job / 作业 string jobname; /作业名time intime; /进入时间int runtime; /作业估计运行时间time starttime; /作业开始时间time endtime; /作业结束时间int cycletime; /作业周转时间float cltime; /作业带权周转时间bool haverun; /是否已运行; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 六、流程图图 1 作业调度算法流程图七、源代码#include #include using namespace std; struct time /时间的数据结构 int hour; int minute; ; struct Job / 作业 string jobname; /作业名time intime; /进入时间int runtime; /作业估计运行时间time starttime; /作业开始时间time endtime; /作业结束时间Y 用户选择进入系统选择调度算法FCFS 调度算法短作业优先响应比优先是 E 或 e 退出系统名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - int cycletime; /作业周转时间float cltime; /作业带权周转时间bool haverun; /是否已运行; float T=0;/作业平均周转时间float W=0;/作业带权平均周转时间void showInput(Job job,int &n) /输入提示 cout*请按作业进入时间先后顺序输入*endl; for(int i=0;in;i+) cout作业 i+1:endl; coutjobi.jobname; cout作业进入时间 :; scanf(%d:%d,&jobi.intime.hour,&jobi.intime.minute); coutjobi.runtime; jobi.starttime.hour=0; jobi.starttime.minute=0; jobi.endtime.hour=0; jobi.endtime.minute=0; jobi.cycletime=0; jobi.cltime=0; jobi.haverun=false; /标记为未运行cout*endl; void Init(Job job,int &n)/ 初始化 for(int i=0;in;i+) jobi.starttime.hour=0; jobi.starttime.minute=0; jobi.endtime.hour=0; jobi.endtime.minute=0; jobi.cycletime=0; jobi.cltime=0; jobi.haverun=false; /标记为未运行 T=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - - W=0; void showTime(time time) /显示时间 couttime.hour:=60) time.hour+; time.minute-=60; return time; bool comtime(time t1,time t2)/比较两个时间的大小，第一个大就返回TRUE if(t1.hourt2.hour) return true; else if(t1.hour=t2.hour&t1.minute=t2.minute) return true; else return false; void showResult(Job job,int &n) /显示结果 coutjobnametintimetruntimetsttimetendtimet 周转时间 (分钟)t 带权周转时间 endl; cout*endl; for(int i=0;in;i+) coutjobi.jobnamet; showTime(jobi.intime); couttjobi.runtimet; showTime(jobi.starttime); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - coutt; showTime(jobi.endtime); coutt jobi.cycletimett jobi.cltimeendl; cout作业平均周转时间： T=T/(n*1.0)endl; cout作业带权平均周转时间： W=W/(n*1.0)endl; int minRuntime(Job job,int &n,time &t) / 找出作业中最短作业下标 int min=-1; for(int i=0;in;i+) if(jobi.haverun=false & comtime(t,jobi.intime)=true) min=i; break; for(int j=min+1;jn;j+) if(jobj.haverun=false & jobj.runtimejobmin.runtime & comtime(t,jobj.intime)=true) min=j; return min; void SJF(Job job,int &n)/ 短作业优先作业调度 struct time t; job0.starttime.hour=job0.intime.hour; job0.starttime.minute=job0.intime.minute; job0.endtime=timeAdd(job0.starttime,job0.runtime); job0.haverun=true; job0.cycletime=timeDiff(job0.endtime,job0.intime); job0.cltime=job0.cycletime*1.0/job0.runtime; T+=job0.cycletime; W+=job0.cltime; t=job0.endtime; while(minRuntime(job,n,t)!=-1) int i=minRuntime(job,n,t); if(comtime(jobi.intime,t) jobi.starttime=jobi.intime; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - jobi.starttime=t; jobi.endtime=timeAdd(jobi.starttime,jobi.runtime); jobi.haverun=true; jobi.cycletime=timeDiff(jobi.endtime,jobi.intime); jobi.cltime=jobi.cycletime*1.0/jobi.runtime; T+=jobi.cycletime; W+=jobi.cltime; t=jobi.endtime; int Firstintime(Job job,int &n) / 找出作业中最先到的 int min=-1; for(int i=0;in;i+) if(jobi.haverun=false) min=i; break; for(int j=min+1;jn;j+) if(jobj.haverun=false & comtime(jobmin.intime,jobj.intime) min=j; return min; void FCFS(Job job,int &n)/ 先来先服务作业调度 struct time t; job0.starttime.hour=job0.intime.hour; job0.starttime.minute=job0.intime.minute; job0.endtime=timeAdd(job0.starttime,job0.runtime); job0.haverun=true; job0.cycletime=timeDiff(job0.endtime,job0.intime); job0.cltime=job0.cycletime*1.0/job0.runtime; T+=job0.cycletime; W+=job0.cltime; t=job0.endtime; while(Firstintime(job,n)!=-1) int i=Firstintime(job,n); if(comtime(jobi.intime,t) jobi.starttime=jobi.intime; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - else jobi.starttime=t; jobi.endtime=timeAdd(jobi.starttime,jobi.runtime); jobi.haverun=true; jobi.cycletime=timeDiff(jobi.endtime,jobi.intime); jobi.cltime=jobi.cycletime*1.0/jobi.runtime; T+=jobi.cycletime; W+=jobi.cltime; t=jobi.endtime; void main() coutn; Job *job=new Jobn; if(n=0) cout输入不合法 !; exit(-1); else showInput(job,n); coutendl; FCFS(job,n); cout先来先服务： endl; showResult(job,n); coutendl; Init(job,n); SJF(job,n); /短作业优先cout短作业优先： endl; showResult(job,n); system(pause); 八、运行结果用户输入作业的相关信息，程序输出相应的各种算法运行结果。以下为程序运行后的输出数据：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - 输入信息：运行结果：九、结果分析(1) 先来先服务输出数据分析：作业至作业的提交时间分别为8：00、8：50、9：00、9：50。所以作名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - 业的执行序列为作业1、作业 2 、作业和作业。前一个作业的完成时间即为后一个作业的开始时间。(2) 短作业优先输出数据分析：作业至作业的提交时间分别为8：00、8：50、9：00、9：50。系统时间时间 8：00：作业提交，马上被调度运行，开始时间为8：00，运行时间为 2：00。时间 8：50：作业提交，因作业在运行，故作业暂时等待。时间 9：00：作业提交，因作业在运行，故作业暂时等待。时间 9：50：作业提交，因作业在运行，故作业暂时等待。时间 10：00：作业完成，进入完成队列。目前提交的作业有：作业、作业、作业；按短作业优先原则，作业运行时间为0：10 最短，故作业被调度运行。作业和作业继续等待。时间 10：10：作业完成，进入完成队列。目前提交的作业有：作业和作业。按短作业优先原则， 作业的运行时间为0：20 最短，故作业 4 被调度运行，作业继续等待。时间 10：30：作业完成，进入完成队列。目前提交的作业仅有作业，故作业被调度运行，运行时间为0：5。时间 11：20：作业完成，进入完成队列。程序执行完毕。十、本次实验体会加深了对作业的理解，掌握了基本的作业调度算法。通过对各种作业调度算法的综合比较，理解各种算法的优劣。十一、参考资料(1) 陈向群 杨芙清著操作系统教程北京大学出版社(2) Andrew S. Tanenbaum 著 陈 向群马 洪兵等译 现代操作 系统机械工业出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -