操作系统作业调度实验.doc

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date操作系统作业调度实验操作系统作业调度实验实验二 作业调度一、实验名称作业调度算法的模拟实现二、实验目标作业调度又称宏观调度，其主要任务是对磁盘设备上大量的后备作业，以一定的原则进行挑选，给选中的作业分配内存等必须的资源，建立其相应的进程，让其投入运行。本实验要求学生用高级程序设计语言编写和调试一个简化的作业调度程序，模拟实现的调度算法包括：先来先服务调度算法，短作业优先调度算法，响应比高者优先调度算法等，并对这些算法的性能做比较和评价。以加深学生对作业、作业调度以及作业调度的各种算法的理解。三、实验环境要求Windows+Visual C+ 6.0；四、实验基本原理作业调度主要是完成作业从后备状态到执行状态的转变，以及从执行状态到完成状态的转变。（1）创建JCB（作业控制块）：系统在作业进入后备状态时为每个作业创建一个作业控制块（JCB）,从而使该作业可被调度程序感知。当该作业执行完毕进入完成状态时候，系统自动撤销其JCB并释放有关资源，进而撤销该作业。（2）按照作业调度算法，从后备队列中挑选一作业投入运行。作业调度程序为运行作业建立相应的进程，并分配资源。（3）主要的作业调度算法包括：先来先服务（FCFS）、短作业优先和最高响应比。（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; /是否已运行;六、流程图Y用户 选择进入系统选择调度算法FCFS调度算法短作业优先响应比优先是E或e退出系统图1 作业调度算法流程图七、源代码#include <iostream>#include <string>using namespace std;struct time /时间的数据结构int hour;int minute;struct Job /作业string jobname; /作业名time intime; /进入时间int runtime; /作业估计运行时间time starttime; /作业开始时间time endtime; /作业结束时间int cycletime; /作业周转时间 float cltime; /作业带权周转时间bool haverun; /是否已运行;float T=0;/作业平均周转时间float W=0;/作业带权平均周转时间void showInput(Job job,int &n) /输入提示cout<<"*请按作业进入时间先后顺序输入*"<<endl;for(int i=0;i<n;i+)cout<<"作业"<<i+1<<":"<<endl;cout<<"作业名:"cin>>jobi.jobname;cout<<"作业进入时间:"scanf("%d:%d",&jobi.intime.hour,&jobi.intime.minute);cout<<"作业估计运行时间:"cin>>jobi.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;i<n;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;W=0;void showTime(time time) /显示时间cout<<time.hour<<":"<<time.minute;int timeDiff(time t1,time t2) /计算时间差,时间t1比t2大return t1.hour*60+t1.minute-(t2.hour*60+t2.minute);time timeAdd(time time,int addtime) /时间相加time.hour+=addtime/60;time.minute+=addtime%60;if(time.minute>=60)time.hour+;time.minute-=60;return time;bool comtime(time t1,time t2)/比较两个时间的大小，第一个大就返回TRUEif(t1.hour>t2.hour)return true;else if(t1.hour=t2.hour&&t1.minute>=t2.minute)return true;elsereturn false;void showResult(Job job,int &n) /显示结果cout<<"jobnametintimetruntimetsttimetendtimet周转时间(分钟)t带权周转时间"<<endl;cout<<"*"<<endl;for(int i=0;i<n;i+)cout<<jobi.jobname<<"t"showTime(jobi.intime);cout<<"t"<<jobi.runtime<<"t"showTime(jobi.starttime);cout<<"t"showTime(jobi.endtime);cout<<"t "<<jobi.cycletime<<"tt "<<jobi.cltime<<endl;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;i<n;i+)if(jobi.haverun=false && comtime(t,jobi.intime)=true)min=i;break;for(int j=min+1;j<n;j+)if(jobj.haverun=false && jobj.runtime<jobmin.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;elsejobi.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;i<n;i+)if(jobi.haverun=false)min=i;break;for(int j=min+1;j<n;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;elsejobi.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()cout<<"请输入作业数："int n; /作业数cin>>n;Job *job=new Jobn;if(n<=0)cout<<"输入不合法!"exit(-1);elseshowInput(job,n);cout<<endl;FCFS(job,n);cout<<"先来先服务："<<endl;showResult(job,n);cout<<endl;Init(job,n);SJF(job,n); /短作业优先cout<<"短作业优先："<<endl;showResult(job,n);system("pause");八、运行结果用户输入作业的相关信息，程序输出相应的各种算法运行结果。以下为程序运行后的输出数据：输入信息：运行结果：九、结果分析(1) 先来先服务输出数据分析：作业至作业的提交时间分别为8：00、8：50、9：00、9：50。所以作业的执行序列为作业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 著 陈向群 马洪兵等译 现代操作系统 机械工业出版社-