搜索
作业调度算法模拟一、课题内容和要求常见的作业调度算法有先来先服务算法、最短作业优先算法、响应比优先调度算法。(1)参考操作系统教材理解这3种算法。(2)实现这3个算法。(3)已知若干作业的到达时间和服务时间，用实现的算法计算对该组作业进行调度的平均周转时间Ttime和平均带权周转时间WTtime。(4)作业的到达时间和服务时间可以存放在文本文件record.txt中。(5)设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计)（6）可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。二、需求分析模拟实现作业调度算法，包括：FCFS（先来先服务算法）、SJF（短作业优先算法）、HRN（最高响应比优先算法）、HPF（基于优先数调度算法）。先来先服务算法：按照各个作业进入系统（输入井）的自然次序来调度算法。短作业优先算法：优先调度并处理短作业。所谓的“短作业”并不是指物理作业长度短，而是指作业的运行时间短。最高响应比优先算法：优先调度并处理响应比最高的作业。三、概要设计函数中一些类：Time类inthour小时intminute分钟Job类IntID作业编号Timestart开始时间Timeenter进入时间Timeend结束时间intrequesttime估计运行时间intTtime周转时间intpriority优先数doubleWTtime带权周转时间Schedule类intsize作业数schedule()构造函数Job*job作业数组voidreadFile()从文件读信息int*r排序用数组voidFCFS()先来先服务IntDiffer()求时间差voidSJF()短作业优先voidHRN()最高响应比优先主要功能函数的流程图1、2、先来先服务：YN开始job[0]结束job[i]isize开始readFile()给变量赋值OnButton2()SJFEDIT4平均周转时间EDIT5平均带权周转时间EDIT2平均周转时间EDIT1平均带权周转时间EDIT6平均周转时间EDIT7平均带权周转时间结束OnButton1()FCFSOnButton3()HRN3、最短作业优先：YN4、最高响应比：YN开始job[0]剩余作业按运行时间最短排序job[i]isize结束开始job[0]剩余作业按响应比排序计算各作业响应比job[i]isize结束四、详细设计1、程序代码MFC头文件a.h内容：constintdefMaxJobNumber=10;//作业数量的最大值classTime//时间类{public:inthour;intminute;};classJob//作业类{public:intID;//作业编号Timeenter;//进入时间intrequesttime;//估计运行时间intpriority;//优先数Timestart;//开始时间Timeend;//结束时间intTtime;//周转时间doubleWTtime;//带权周转时间};classschedule//调度类{public:intsize;//作业数Job*job;//作业数组int*r;//排序用数组intDiffer(Timet1,Timet2)//求两个时刻间的时间差t2-t1{intborrow=(t2.minutet1.minute)?1:0;return((t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute));}public:schedule()//构造函数{size=0;job=newJob[defMaxJobNumber];r=newint[defMaxJobNumber-1];}voidreadFile()//从文件读信息{ifstreamtxtfile;txtfile.open(record.txt);inti=0;intentertime;while(!txtfile.eof()){txtfilejob[i].IDentertimejob[i].requesttimejob[i].priority;job[i].enter.hour=entertime/100;//取小时job[i].enter.minute=entertime%100;//取分钟i++;size++;}txtfile.close();}voidFCFS()//先来先服务(FirstComeFirstServe){inthour,minute,carry;job[0].start=job[0].enter;hour=job[0].requesttime/60;minute=job[0].requesttime%60;job[0].end.minute=(job[0].start.minute+minute)%60;carry=(job[0].start.minute+minute)/60;//carry是分钟累积超过60商job[0].end.hour=job[0].start.hour+hour+carry;job[0].Ttime=job[0].requesttime;job[0].WTtime=((double)job[0].Ttime)/job[0].requesttime;for(inti=1;isize;i++){job[i].start=job[i-1].end;hour=job[i].requesttime/60;minute=job[i].requesttime%60;job[i].end.minute=(job[i].start.minute+minute)%60;carry=(job[i].start.minute+minute)/60;job[i].end.hour=job[i].start.hour+hour+carry;job[i].Ttime=Differ(job[i].enter,job[i].end);//周转时间job[i].WTtime=((double)job[i].Ttime)/job[i].requesttime;//带权周转时间}}voidSJF()//短作业优先(ShortestJobFirst){inthour,minute,carry;job[0].start=job[0].enter;hour=job[0].requesttime/60;minute=job[0].requesttime%60;job[0].end.minute=(job[0].start.minute+minute)%60;carry=(job[0].start.minute+minute)/60;//carry是分钟累积超过60的商job[0].end.hour=job[0].start.hour+hour+carry;job[0].Ttime=job[0].requesttime;//周转时间job[0].WTtime=((double)job[0].Ttime)/job[0].requesttime;//带权周转时间for(inti=1;isize;i++)r[i]=i;for(i=1;isize-1;i++)//按照作业运行时间从低到高排序{intindex=i;for(intj=i+1;jsize;j++)if(job[r[j]].requesttimejob[r[index]].requesttime)index=j;if(index!=i){intw=r[i];r[i]=r[index];r[index]=w;}}intdest=0;for(i=1;isize;i++)//按排序后的作业序继续执行{intindex=r[i];job[index].start=job[dest].end;hour=job[index].requesttime/60;minute=job[index].requesttime%60;job[index].end.minute=(job[index].start.minute+minute)%60;carry=(job[index].start.minute+minute)/60;job[index].end.hour=job[index].start.hour+hour+carry;job[index].Ttime=Differ(job[index].enter,job[index].end);job[index].WTtime=((double)job[index].Ttime)/job[index].requesttime;dest=index;}}voidHRN()//最高响应比优先(HighestResponse_ratioNext){inthour,minute,carry;job[0].start=job[0].enter;hour=job[0].requesttime/60;minute=job[0].requesttime%60;job[0].end.minute=(job[0].start.minute+minute)%60;carry=(job[0].start.minute+minute)/60;//carry是分钟累积超过60的商job[0].end.hour=job[0].start.hour+hour+carry;job[0].Ttime=job[0].requesttime;//周转时间job[0].WTtime=((double)job[0].Ttime)/job[0].requesttime;带权周转时间intdest=0;for(inti=1;isize;i++)r[i]=i;for(i=1;isize;i++){intindex=i;for(intj=i+1;jsize;j++)//按照响应比从大到小排序if(((double)Differ(job[r[j]].enter,job[dest].end))/job[r[j]].requesttime((double)Differ(job[r[index]].enter,job[dest].end))/job[r[index]].requesttime)//响应比=作业周转时间/作业处理时间index=j;if(index!=i){intw=r[i];r[i]=r[index];r[index]=w;}//按排序后的作业序继续执行index=r[i];job[index].start=job[dest].end;hour=job[index].requesttime/60;minute=job[index].requesttime%60;job[index].end.minute=(job[index].start.minute+minute)%60;carry=(job[index].start.minute+minute)/60;job[index].end.hour=job[index].start.hour+hour+carry;job[index].Ttime=Differ(job[index].enter,job[index].end);job[index].WTtime=((double)job[index].Ttime)/job[index].requesttime;dest=index;}}};五、测试数据及其结果分析从文本文件中读取数据（书上的例子）：18001202285050339001014950204输出的平均周转时间、平均带权周转时间结果正确。六、调试过程中的问题调试过程中，对于MFC里面许多函数不熟悉，所以经常编译失败，我通过老师的帮助以及上网查询解决方法来不断修改错误，完善代码。这个程序没有考虑一些特殊情况，如：若有作业5的到达时间为11：10，执行时间是5分钟，则是否先于其它作业调入内存执行。七、参考文献和查阅的资料（1）黄