作业调度算法模拟-实验报告.doc

作业调度算法模拟1 课题内容和要求常见的作业调度算法有先来先服务算法、最短作业优先算法、响应比优先调度算法。(1) 参考操作系统教材理解这3种算法。(2) 实现这3个算法。(3) 已知若干作业的到达时间和服务时间，用实现的算法计算对该组作业进行调度的平均周转时间和平均带权周转时间。(4) 作业的到达时间和服务时间可以存放在文本文件中。(5) 设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计)2 需求分析class Job /作业类public:int ID; /作业编号Time enter; /进入时间int requesttime; /估计运行时间int priority; /优先数Time start; /开始时间Time end; /结束时间int Ttime; /周转时间double WTtime; /带权周转时间 ;这个模块是设计作业结构（本程序是用的类Job）包括作业编号，进入时间，估计运行时间，优先数，开始时间，结束时间，周转时间，带权周转时间等。class schedule /调度类private:int size; /作业数Job *job; /作业数组int *r; /排序用数组int Differ(Time t1,Time t2) /求两个时刻间的时间差int borrow = (t2.minutet1.minute) ? 1 : 0;return (t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute);这个模块是调度结构本程序为类scheduleb包括作业数，作业数组，排序用数组。void FCFS() /先来先服务(First Come First Serve)这个模块模拟实现算法先来先服务（FCFS）是按照各个作业进入系统的自然次序来调度算法。按照作业提交的先后次序分派CPU，当前作业或进程占用CPU，知道执行完成或阻塞，才出让CPU。在作业或进程被唤醒后，并不立即恢复执行，通常等到当前作业或进程出让CPU。void SJF() /短作业优先(Shortest Job First)这个模块模拟实现短作业优先，按照作业运行时间从低到高排序，优先处理短作业。所谓的短作业并不是指物理作业的长短，而是作业的运行时间短。void HPF() /基于优先数(Highest Priority First)这个模块模拟实现优先调度并处理优先数最高的作业。本程序仅针对外部优先数，即用户规定优先数。void HRN() /最高响应比优先(Highest Response_ratio Next)这个模块模拟实现优先处理并处理响应比最高的作业。要通过一个循环找到一个响应比响应比较高的作业。R=作业周转时间/作业处理时间。 开始3 概要设计 初始化所有的作业取下一个作业地址根据算法调度一个作业 结束作业是否处理完 否 结束计算相关数据并输出 是此程序设计作业结构（本程序为类Job），包括作业编码、进入时间、估计运行时间、优先数、开始时间、结束时间、周转时间和带权周转时间等；调度结构（本程序为类schedule），包括作业数、作业数组以及排序用的数组等。模拟实现作业调度算法，包括：FCFS（先来先服务算法）、SJF（短作业优先算法）、HRN（最高响应比优先算法）、HPF（基于优先数调度算法）。4 详细设计#include #include #include using namespace std;const int defMaxJobNumber = 10; /作业数量的最大值头文件分别定义输入输出流，iomanip定义关于cin cout的调用，以及sew函数的调用，定义一个作业数量的最大值的常量。class Time /时间类public:int hour;int minute;定义一个时间类，包括小时和分钟。class Job /作业类public:int ID; /作业编号Time enter; /进入时间int requesttime; /估计运行时间int priority; /优先数Time start; /开始时间Time end; /结束时间int Ttime; /周转时间double WTtime; /带权周转时间 ;定义一个作业类，定义作业编号，进入时间，估计运行时间，优先数，开始时间，结束时间，周转时间，带权周转时间的变量。class schedule /调度类private:int size; /作业数Job *job; /作业数组int *r; /排序用数组int Differ(Time t1,Time t2) /求两个时刻间的时间差int borrow = (t2.minutet1.minute) ? 1 : 0;return (t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute);这段代码定义了一个调度类包括作业数，作业数组，排序用数组、用int Differ球两个时刻间的时间差。void show() /输出计算结果double averageTime=0.0, /平均周转时间 wAverageTime=0.0; /带权平均周转时间cout编号 进入时间 运行时间 优先数 开始时间 结束时间 周转时间 带权周转时间endl;for(int i=0;isize;i+)coutsetw(4)jobi.IDsetw(7)jobi.enter.hour:;if(jobi.enter.minute10)cout0jobi.enter.minute;elsecoutjobi.enter.minute;coutsetw(10)jobi.requesttimesetw(8)jobi.prioritysetw(7)jobi.start.hour:;if(jobi.start.minute10)cout0jobi.start.minute;elsecoutjobi.start.minute;coutsetw(7)jobi.end.hour:;if(jobi.end.minute10)cout0jobi.end.minute;elsecoutjobi.end.minute;coutsetw(10)jobi.Ttimesetw(14)jobi.WTtimeendl;averageTime += jobi.Ttime;wAverageTime += jobi.WTtime;cout作业平均周转时间T=averageTime/size分钟endl;cout作业带权平均周转时间W=wAverageTime/sizeendlendl;Show输出计算结果。代码首先给初始化平均周转时间和平均带权周转时间都为0.0，然后分别显示编号、进入时间 、运行时间、优先数、开始时间、结束时间、 周转时间、带权周转时间。然后进入一个for循环，调用sew为作业号，进入时间的显示分派间距。如果进入时间小于10，输出0和进入时间，否则输出进入时间，然后输出需求时间，优先数，开始时间（小时），如果开始时间（分钟）小于10，同理输出0和开始时间。以下类同。分别输出结束时间，平均周转时间，平均带权周转时间。For循环结束后计算作业平均周转时间和作业带权周转时间。void readFile() /从文件读信息ifstream txtfile;txtfile.open(a.txt);if(!txtfile)cerr文本文件打开失败!jobi.IDentertimejobi.requesttimejobi.priority;jobi.enter.hour = entertime / 100;jobi.enter.minute = entertime % 100;i+;size+;txtfile.close();此代码段定义的是文件读取函数，并且计算出开始的小时和分钟。该函数能够直接读取一个文件，不需要在输入进去。通过i使整个进入时间分别算出小时和分钟。void FCFS() /先来先服务(First Come First Serve)int hour,minute,carry;cout先来先服务作业调度算法计算结果:endl;job0.start = job0.enter;/第一道作业到达的开始时间hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;for(int i=1;isize;i+)jobi.start = jobi-1.end;hour = jobi.requesttime / 60;minute = jobi.requesttime % 60;jobi.end.minute = (jobi.start.minute + minute) % 60;carry = (jobi.start.minute + minute) / 60;jobi.end.hour = jobi.start.hour + hour + carry;jobi.Ttime = Differ(jobi.enter,jobi.end);jobi.WTtime = (double)jobi.Ttime) / jobi.requesttime;show();此代码段定义一个先来现服务的函数，第一道作业开始时间开始计算，分别计算出开始时间的小时和分钟。第一道作业的结束时间（分钟）为第一道作业的开始时间加上估计运行的时间对60取余。同理算出开始时间（小时）,第一道作业的周转时间等于估计运行时间，第一道作业的带权周转时间等于周转时间除以需求时间。然后进入一个for循环算出每一个作业的结束时间，周转时间，带权周转时间。void SJF() /短作业优先(Shortest Job First)int hour,minute,carry;cout短作业优先作业调度算法计算结果:endl;job0.start = job0.enter;hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;for(int i=1;isize;i+)ri = i;for(i=1;isize-1;i+) /按照作业运行时间从低到高排序int index = i;for(int j=i+1;jsize;j+)if(jobrj.requesttimejobrindex.requesttime)index = j;if(index!=i)int w = ri;ri = rindex;rindex = w;int dest=0;for(i=1;isize;i+)int index = ri;jobindex.start = jobdest.end;hour = jobindex.requesttime / 60;minute = jobindex.requesttime % 60;jobindex.end.minute = (jobindex.start.minute + minute) % 60;carry = (jobindex.start.minute + minute) / 60;jobindex.end.hour = jobindex.start.hour + hour + carry;jobindex.Ttime = Differ(jobindex.enter,jobindex.end);jobindex.WTtime = (double)jobindex.Ttime) / jobindex.requesttime;dest = index;show();此代码段定义了一个短作业优先函数，第一道作业的开始时间就等于进入时间，第一道作业的结束时间（分钟）为第一道作业的结束时间加上估计运行时间对60取余。第一道作业的时间同先来现服务的算法一样。然后利用for循环分别对作业从低到高进行排序。排序后短作业的优先执行，所以最短的作业以第一个作业的结束时间为开始时间，然后一次这样下去。在分别计算出周转时间和带权周转时间以及平均周转时间和平均带权周转时间。void HRN() /最高响应比优先(Highest Response_ratio Next)作业周转时间/作业处理时间int hour,minute,carry;cout最高响应比优先作业调度算法计算结果:endl;job0.start = job0.enter;hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;int dest=0;for(int i=1;isize;i+)ri = i;for(i=1;isize;i+)int index = i;for(int j=i+1;j(double)Differ(jobrindex.enter,jobdest.end)/jobrindex.requesttime)index = j;if(index!=i)int w = ri;ri = rindex;rindex = w;index = ri;jobindex.start = jobdest.end;hour = jobindex.requesttime / 60;minute = jobindex.requesttime % 60;jobindex.end.minute = (jobindex.start.minute + minute) % 60;carry = (jobindex.start.minute + minute) / 60;jobindex.end.hour = jobindex.start.hour + hour + carry;jobindex.Ttime = Differ(jobindex.enter,jobindex.end);jobindex.WTtime = (double)jobindex.Ttime) / jobindex.requesttime;dest = index;show();此代码段定义一个最高响应比优先函数，第一道作业的开始时间，结束时间，带权周转时间，周转时间都与先来现服务的第一道作业的算法相同。从第二道开始，进入一个for循环，首先我们要计算出各个作业的响应比：响应比=1+（作业等待时间/作业处理时间）。然后通过循环比较找到响应比最高的那道作业首先执行，此作业的开始时间为第一道作业的结束时间，一次类推知道执行完最后一道作业为止。int main()schedule s;s.readFile(); /从文件读信息s.FCFS(); /先来先服务(First Come First Serve)s.SJF(); /短作业优先(Shortest Job First)s.HRN(); /最高响应比优先(Highest Response_ratio Next)s.HPF(); /基于优先数(Highest Priority First)return 0;定义主函数。5 测试数据及结果分析 六、调试过程中的问题调试过程中，对于C+代码不是很熟，所以经常编译失败，我通过老师的帮助以及上网查询解决方法来不断修改错误，完善代码。比如我们要输入8：00时，必须输入800的形式。而且我对短作业优先算法的理解不完善，所以一度导致短作业优先算法的运行结果不正确。后来通过看书和请教老师在不断调式下终于完善了该代码。7、 参考文献和查阅的资料黄刚、徐小龙、段卫华 操作系统教程 人民邮电出版社朱立华 朱建 俞琼 面向对象程序设计及C+ 人民邮电出版社陈向群、杨芙清 操作系统教程 北京大学出版社沈显君、杨进才、张勇 C+语言程序设计教程 清华大学出版社8、 程序设计总结通过本次专业课程设计，使我对操作系统这门课程有了更深入的理解。操作系统是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。一个人的力量是有限的，要想把课程设计做的更好，就要学会参考一定的资料，吸取别人的经验，让自己和别人的思想有机的结合起来，得出属于你自己的灵感。 在这个过程中，我也曾经因为实践经验的缺乏失落过，也曾经仿真成功而热情高涨。生活就是这样，汗水预示着结果也见证着收获。劳动是人类生存生活永恒不变的话题。虽然这只是一次的极简单的课程制作，可是平心而论，也耗费了我不少的心血，这就让我不得不佩服开发技术的前辈，才意识到老一辈对我们社会的付出，为了人们的生活更美好，他们为我们社会所付出多少心血啊！ 对我而言，知识上的收获重要，精神上的丰收更加可喜。让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！ 通过这次的专业课程设计我对于专业课的学习有了更加深刻的认识，以为现在学的知识用不上就加以怠慢，等到想用的时候却发现自己的学习原来是那么的不扎实。以后努力学好每门专业课，让自己拥有更多的知识，才能解决更多的问题！而且老师也给我许多的帮助。在此次实验中我对作业调度算法中的短作业优先算法不是很理解，不太明白该算法的中心思想，在老师和同学的帮助下，我弄懂了。所以我觉得同学之间的合作很重要。也很感谢老师这两个星期对我的帮助。 附录#include #include #include using namespace std;const int defMaxJobNumber = 10; /作业数量的最大值class Time /时间类public:int hour;int minute;class Job /作业类public:int ID; /作业编号Time enter; /进入时间int requesttime; /估计运行时间int priority; /优先数Time start; /开始时间Time end; /结束时间int Ttime; /周转时间double WTtime; /带权周转时间 ;class schedule /调度类private:int size; /作业数Job *job; /作业数组int *r; /排序用数组int Differ(Time t1,Time t2) /求两个时刻间的时间差int borrow = (t2.minutet1.minute) ? 1 : 0;return (t2.hour-t1.hour-borrow)*60+(borrow*60+t2.minute-t1.minute);void show() /输出计算结果double averageTime=0.0, /平均周转时间 wAverageTime=0.0; /带权平均周转时间cout编号 进入时间 运行时间 优先数 开始时间 结束时间 周转时间 带权周转时间endl;for(int i=0;isize;i+)coutsetw(4)jobi.IDsetw(7)jobi.enter.hour:;if(jobi.enter.minute10)cout0jobi.enter.minute;elsecoutjobi.enter.minute;coutsetw(10)jobi.requesttimesetw(8)jobi.prioritysetw(7)jobi.start.hour:;if(jobi.start.minute10)cout0jobi.start.minute;elsecoutjobi.start.minute;coutsetw(7)jobi.end.hour:;if(jobi.end.minute10)cout0jobi.end.minute;elsecoutjobi.end.minute;coutsetw(10)jobi.Ttimesetw(14)jobi.WTtimeendl;averageTime += jobi.Ttime;wAverageTime += jobi.WTtime;cout作业平均周转时间T=averageTime/size分钟endl;cout作业带权平均周转时间W=wAverageTime/sizeendlendl;public:schedule() /构造函数size = 0;job = new JobdefMaxJobNumber;r = new intdefMaxJobNumber-1;void readFile() /从文件读信息ifstream txtfile;txtfile.open(a.txt);if(!txtfile)cerr文本文件打开失败!jobi.IDentertimejobi.requesttimejobi.priority;jobi.enter.hour = entertime / 100;jobi.enter.minute = entertime % 100;i+;size+;txtfile.close();cout编号 进入时间 运行时间 优先数endl;for(i=0;isize;i+)coutsetw(4)jobi.IDsetw(7)jobi.enter.hour:;if(jobi.enter.minute10)cout0jobi.enter.minute;elsecoutjobi.enter.minute;coutsetw(10)jobi.requesttimesetw(8)jobi.priorityendl;coutendl;void FCFS() /先来先服务(First Come First Serve)int hour,minute,carry;cout先来先服务作业调度算法计算结果:endl;job0.start = job0.enter;/第一道作业到达的开始时间hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;for(int i=1;isize;i+)jobi.start = jobi-1.end;hour = jobi.requesttime / 60;minute = jobi.requesttime % 60;jobi.end.minute = (jobi.start.minute + minute) % 60;carry = (jobi.start.minute + minute) / 60;jobi.end.hour = jobi.start.hour + hour + carry;jobi.Ttime = Differ(jobi.enter,jobi.end);jobi.WTtime = (double)jobi.Ttime) / jobi.requesttime;show();void SJF() /短作业优先(Shortest Job First)int hour,minute,carry;cout短作业优先作业调度算法计算结果:endl;job0.start = job0.enter;hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;for(int i=1;isize;i+)ri = i;for(i=1;isize-1;i+) /按照作业运行时间从低到高排序int index = i;for(int j=i+1;jsize;j+)if(jobrj.requesttimejobrindex.requesttime)index = j;if(index!=i)int w = ri;ri = rindex;rindex = w;int dest=0;for(i=1;isize;i+)int index = ri;jobindex.start = jobdest.end;hour = jobindex.requesttime / 60;minute = jobindex.requesttime % 60;jobindex.end.minute = (jobindex.start.minute + minute) % 60;carry = (jobindex.start.minute + minute) / 60;jobindex.end.hour = jobindex.start.hour + hour + carry;jobindex.Ttime = Differ(jobindex.enter,jobindex.end);jobindex.WTtime = (double)jobindex.Ttime) / jobindex.requesttime;dest = index;show();void HPF() /基于优先数(Highest Priority First)int hour,minute,carry;cout基于优先数作业调度算法计算结果:endl;job0.start = job0.enter;hour = job0.requesttime / 60;minute = job0.requesttime % 60;job0.end.minute = (job0.start.minute + minute) % 60;carry = (job0.start.minute + minute) / 60;job0.end.hour = job0.start.hour + hour + carry;job0.Ttime = job0.requesttime;job0.WTtime = (double)job0.Ttime) / job0.requesttime;for(int i=1;isize;i+)ri = i;for(i=1;isize-1;i+) /按照优先数从高到低排序int index = i;for(int j=i+1;jjobrindex.priority)index = j;if(index!=i)int w = ri;ri = rindex;rindex = w;int dest=0;for(i=1;isize;i+)int index = ri;jobindex.start = jobdest.end;hour = jobindex.requesttime / 60;minute = jobindex.requesttime % 60;jobindex.end.minute = (jobindex.start.minute + minute) % 60;carry = (jobindex.start.minute + minute) / 60;jobindex.end.hour = jobindex.start.hour + hour + carry;jobindex.Ttime = Differ(jobindex.enter,jobindex.end);job