优先级作业调度系统实验报告

实验报告——优先级作业调度系统的模拟课程名称：数据结构大型试验实验项目名称：优先级作业调度系统的模拟学院：计算机科学与技术学院专业：计算机科学与技术指导教师：刘端阳报告人：学号：班级：目录1.实验内容分析......................................31.1实验目的..................................................1.2实验要求...................................................1.3设计分析...................................................2.试验验证分析......................................2.1输入的形式及输入值的范围..................................2.2程序所能达到的结果........................................2.3测试数据..................................................3.测试分析..........................................3.1基础问题...................................................3.2技术问题...................................................3.3调试错误4.调试结果分析......................................4.1程序的运行结果.............................................5.附录..............................................一、实验内容分析：实验目的：Windows、Linux等操作系统都支持同时运行多个作业，但作业的执行顺序却因调度算法的不同而不同。通常，操作系统都采用优先级作业调度，即操作系统根据作业的长短来设置优先级大小，优先级高的作业先执行，优先级低的作业后执行。作业调度的详细情况如下描述：一个作业Ji的长度为ti=（si，ei），si为作业运行的开始时间（进入时间），ei为作业运行的结束时间（离开时间），ti则为完成作业Ji所需要的执行时间（单位：秒）。作业调度的基本任务是从作业队列中选取一个来执行，如果没有作业则执行空操作操作。而优先级作业调度，是指每次选取优先级最高的作业来调度，优先级可以用优先数（每个作业一个优先数pi）来表示，优先数越小，优先级越高。作业Ji进入系统时，即si时刻，系统给该作业指定其初始优先数pi=ti，从而使越短的作业优先级越高。该优先数在作业等待调度执行的过程中会不断减小，调整公式为：pi=pi-wi，其中wi为作业Ji的等待时间：wi=当前时间-si。一旦作业被调度，该作业就一直执行，不能被抢占，只有当前执行的作业完成时，才产生下一轮调度。所以需要在每次调度前动态调整各作业的优先数。在每次调度的时候，如果出现相同优先级的作业，则按照先进先出(FIFO:FirstInFirstOut)的原则进行调度。实验要求：1.要求自己编程实现堆结构及其相关功能，从而实现优先级队列，不允许使用标准模板类的堆函数和优先级队列；测试时，各种情况都需要测试，并附上测试截图；2.要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。3.要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。4.要求源程序中有相应注释；5.不强制要求采用类模板，也不要求采用可视化窗口；6.要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确，包括何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等；7.要求采用VisualC++6.0及以上版本进行调试；设计分析：类的设计Work:自定义的作业类。MyHeap：自定义的优先级队列，帮助工程类的实现System：模拟作业调度系统定义的工程类，模拟处理作业的过程。类的关系图基本数据结构类的设计：MyHeap(优先级队列)：利用自定义的最小堆实现优先级队列，实现主要的功能，包括作业的插入、最小优先级作业的提取和删除、各个作业优先级的修改等，优先级队列采用的是模板类MyHeap();//队列的构造函数voidpop();//删除队首元素,并更新队列voidpush(constDATA&item);//在队列中加入新项，并更新队列DATAtop();//返回队首的元素boolempty();//判断队列知否为空intsize();//返回队列的中元素的个数voidupdate();//将队列中每一项的优先级减一voidshow();//显示队列的所有信息作业类以及工程类的设计Work（作业类）System（工程类）MyHeap(优先级队列类)数据类型实现工具MyHeapemptysizetoppopVectorDATAmhupdatepush成员函数数据成员showWork（作业类）：ints;//作业进入的时间intt;//作业的执行时间intp;//作业的优先级intnum;//作业标号Work();//无参构造函数Work(intn,inta,intb);//有参构造函数Work&operator--();////自减操作重载Work&operator=(constWork&a);//赋值操作重载friendostream&operator(ostream&out,constWork&a);//输出流重载friendbooloperator(constWork&a,constWork&b);//重定义小于booloperator(constWork&a,constWork&b){//重定义小于if(a.p!=b.p)returna.pb.p;//先按优先级排，优先级小的小returna.sb.s;//否则，先进入的小//因为创建的是最小堆，所以在队首的是优先级小的，符合题目要求}System(工程类)：模拟优先级作业调度系统的运行的过程，并设计调试程序代码函数WorkintsIntpInttintnum数据成员operator=ostream&=成员函数Systemrun()operator数据成员MyHeapWorkmwmwmwmw;Workwk;boolisworkintT,end,SIZEvoidrun();//自动运作的工程{srand(time(0));//把时间作为种子，若不调用此函数，产生的随机数都是伪随机的，每次程序运行的结果都一样inttol=0;//表示作业的编号for(T=0;TSIZE;T++){//这段时间会随机产生新的作业mw.update();//因为等待时间+1，所以队列里所有的作业的优先级-1if(iswork&&end==T){//如果正在运行的作业结束了iswork=false;//表示没有作业在运行cout***程序运行时间为T,作业wk.num处理完毕，用时wk.t,等待T-wk.t-wk.s\n\n;//输出信息}if(iswork){//若有程序在运行cout程序运行时间为T,正在执行作业wk.num...\n;Sleep(500);//滞留0.5s，表示正在运行}if(T%10==0){//如果是10的倍数intnum=rand()%3+1,t;//随机产生1-3个新作业printf(***新加入%d作业：\n,num);for(inti=0;inum;i++){t=rand()%20+1;//随机产生作业的执行时间mw.push(Work(++tol,T,t));//调用构造函数printf(作业%d,进入时间为%d,需执行时间为%d,优先级为%d\n,tol,T,t,t);//输出新作业的信息}printf(\n);//输出更新后的队列的信息printf(***此时共有%d作业等待处理\n{\n,mw.size());mw.show();//输出队列里的所有的作业信息，无序printf(}\n\n);}if(!iswork&&!mw.empty()){wk=mw.top();mw.pop();//取出队首元素printf(***开始执行作业%d，进入时间为%d，等待时间为%d，需执行时间%d,优先级为%d\n,wk.num,wk.s,T-wk.s,wk.t,wk.p);end=T+wk.t;//更新结束时间iswork=true;}}while(!mw.empty()||iswork){//不再加入新作业，将剩余的所有作业运行完…}…}二、实验验证分析输入形式：需要输入4个整型数据，分别是时间间隔、工作时间、作业长度上限以及每个间隔产生的作业上限。输出形式：模拟系统运行过程，详细显示运行过程中系统内各个作业的信息，以及新加入作业组的信息，加入新作业后系统内作业组的信息。每个作业运行结束，显示当前作业等待时间和运行时间。程序所能达到的结果：能使模拟系统根据作业的优先级大小顺序处理作业，原始优先级只与作业的长度相关，但运行过程的优先级要根据系统运行的时间发生改变，以实现先入先出的原则。运行过程中，系统会随机产生作业组加到系统中，系统将新的工作组按照优先级大小进行排序。系统能随时提取出，当前正在处理的作业的详细信息，以及系统内正在等待处理的作业组的信息。测试数据：1．正确输入：输入：1060103输出2．错误输入输入的数据都要大于0.三、调试分析基础问题1.vector的运用：①end()的误用解决：end（）返回的向量中最后一个元素后面位置的指针②earse()函数的调用解决：函数括号内是迭代器，不是下标2.sleep（）的用法①Sleep函数//S要大写②头文件#includewindows.h③函数调用形式Sleep(500);//单位是毫秒技术问题1.作业关系大小的设计错误理解：以为只要比较作业的优先级就可以了，这样设计无法实现先进先出的原则解决：设计作业大小比较时，优先考虑作业的优先级，如果优先级一样的话，再根据作业的num值比较大小（即进入系统的先后顺序）2.优先队列的设计难点：①调整节点条件的分析当二叉树只有一个节点时，不需要进行下调工作因为进行下调操作的是一个最小堆，只要被调整元素比它的两个子节点都小，就可以直接跳出循环节点比较不需要考虑相等的情况，因为每个作业的num值一定是不一样的，所以就算优先级一样，也一定不会相等调试错误1.编写最小堆的时候，有几个函数不小心写成了最大堆的效果，找了好久的错误2.Work类,在编写赋值操作符重载时，用的是成员函数，却在函数里新创了个对象，结果出现了错误四、测试结果分析：程序的运行结果刚开始只产生了一个作业，所以就执行改作业产生了两个作业，且此时没有作业在执行，作业4的优先级比作业3大，所以先执行作业4作业2、5的优先级是相同的，而作业2先进入队列，所以先执行作业2作业执行时，输出执行语句，并调用Sleep函数，表示正在执行五、附录Heap.h#includeiostream#includevectorusingnamespacestd;#ifndefMYHEAP#defineMYHEAP//防止因头文件被反复调用，而导致重复定义//应用模板类templatetypenameDATAclassMyHeap{vectorDATA