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

数据结构大型试验报告优先级作业调度系统的模拟课程名称：数据结构大型试验实验项目名称：优先级作业调度系统的模拟学院：计算机科学与技术学院专业：物联网工程班指导教师:黄伟报告人：李靖学号：201426811412班级:物联网1402目录.实验内容分析3实验目的实验要求设计分析.试验验证分析输入的形式及输入值的范围程序所能达到的结果测试数据.测试分析基础问题技术问题调试错误.调试结果分析程序的运行结果.附录、实验内容分析:实验目的：WindowsLinux等操作系统都支持同时运行多个作业，但作业的执行顺序却因调度算法的不同而不同。通常，操作系统都采用优先级作业调度，即操作系统根据作业的长短来设置优先级大小，优先级高的作业先执行，优先级低的作业后执行。作业调度的详细情况如下描述：一个作业Ji的长度为ti=（si,ei）,si为作业运行的开始时间（进入时间），ei为作业运行的结束时间（离开时间），ti则为完成作业Ji所需要的执行时间（单位：秒）。作业调度的基本任务是从作业队列中选取一个来执行，如果没有作业则执行空操作操作。而优先级作业调度，是指每次选取优先级最高的作业来调度，优先级可以用优先数（每个作业一个优先数pi）来表示，优先数越小，优先级越高。作业Ji进入系统时，即si时刻，系统给该作业指定其初始优先数pi=ti,从而使越短的作业优先级越高。该优先数在作业等待调度执行的过程中会不断减小，调整公式为：pi=pi-wi,其中wi为作业Ji的等待时间：wi=当前时间-si。一旦作业被调度，该作业就一直执行，不能被抢占，只有当前执行的作业完成时，才产生下一轮调度。所以需要在每次调度前动态调整各作业的优先数。在每次调度的时候，如果出现相同优先级的作业，则按照先进先出（FIFO:FirstInFirstOut）的原则进行调度。实验要求：.要求自己编程实现堆结构及其相关功能，从而实现优先级队列，不允许使用标准模板类的堆函数和优先级队列；测试时，各种情况都需要测试，并附上测试截图；.要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。.要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中。.要求源程序中有相应注释；.不强制要求采用类模板，也不要求采用可视化窗口；.要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确，包括何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等；.要求采用VisualC++6.0及以上版本进行调试；设计分析：类的设计'Work:自定义的作业类。《MyHeap自定义的优先级队列，帮助工程类的实现System：模拟作业调度系统定义的工程类，模拟处理作业的过程。

类的关系图Work数据类型(作业类)r类的关系图Work数据类型(作业类)r.System(工程类)实现工匕/MyHeapf(优先级队列类)/j基本数据结构类的设计:MyHeap优先级队列)：利用自定义的最小堆实现优先级队列，实现主要的功能，包括作业的插入、最小优先级作业的提取和删除、各个作业优先级的修改等，优先级队列采用的是模板类MyHeap();//队列的构造函数voidpop();//删除队首元素,并更新队列voidpush(constDATA&item);//DATAtop();//返回队首的元素voidpush(constDATA&item);//DATAtop();//返回队首的元素在队列中加入新项，并更新队列boolempty();//判断队列知否为空intsize();//返回队列的中元素的个数voidupdate();//将队列中每一项的优先级减一voidshow();//显示队列的所有信息

作业类以及工程类的设计operator=operator>operator=operator>ostream&=Lintnumints;//作业进入的时间intt;//作业的执行时间intp;//作业的优先级intnum;//作业标号Work();//无参构造函数Work(intn,inta,intb);//有参构造函数Work&operator--();////自减操作重载Work&operator=(constWork&a);//赋值操作重载输出流重重定义小于输出流重重定义小于friendbooloperator<(constWork&a,constWork&b);//booloperator<(constWork&a,constWork&b){//重定义小于if(a.p!=b.p)returna.p<b.p;//先按优先级排，优先级小的小returna.s<b.s;//否则，先进入的小//因为创建的是最小堆，所以在队首的是优先级小的，符合题目要求}System(工程类)：模拟优先级作业调度系统的运行的过程，并设计调试程序代码函数MyHeap<Work>mwrSystemWorkwk;数据成员MyHeap<Work>mwrSystemWorkwk;数据成员boolisworkJintT,end,SIZErun()voidrun();//自动运作的工程{srand(time(0));//把时间作为种子，若不调用此函数，产生的随机数都是伪随机的，每次程序运行的结果都一样inttol=0;//表示作业的编号for(T=0;T<SIZE;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;i<num;i++){t=rand()%20+1;//随机产生作业的执行时间mw.push(Work(++tol,T,t));//调用构造函数printf("作业％~,进入时间为％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输出间T0呈□工呈口王呈□王M21业业3079青青青青”79级级00e«bQ16灵士一iiiid一:•上产■度圾招4长间作爵个冬入时工售鳖进入入入需需**009燃姆97仇先级为7*二二二%,111111士兀区业业业业业业理、：—一丁亍-丁一工工丁zlka执fck执执执整在在在在在彳迪正正正正正正乙1----，比123456司为为班执贫作业2,进人时间才。，等待时间为？，需执行时间9,优先级为2□ris-、二ri-X7G1L.-2-需执行时间9,优先级为3000-IT丸丸JIW需需du0，19为为为为"/089100i1亍一Tllr那执正正正□MnHMnnL1T1T,仃图圜矽3,4,业业D王0王口王ftt—1010二：二毕2.2.2.2.2.士兀业业业业业理“作咋乍^,止-1处一丁丁一丁一工丁12现仇决仇在在在在在作正正正正正16,12345UZ11111为司司司司司FB仃BB日BB云-fT-Tf丁逢闾和囹凰琳□土□王口王口王□王川等待时间为6,>444410业业业业-VLVL七LV1时决aa^A入专在在进正正正正47890L1112nnnHUDunn邙一丁一丁-丁一丁4nv/;6/>2>2-也运运运运M0王口王呈口王*-^1—可.用.国.闻.Jnnmmm2L*22220111154业业ii业i1II丁LF♦./I、一■-5-IJ:2J〉\在在在在都+正正正正用也心7,8,斯%F151555^iI”40,等待时间为20,需执行时间九优先级为-1回0用在在在套在在在一正正正正正正正正.1，下♦■,，■即tJL11234567^SEEbH&66.兀乍力夕夕夕力力力夕里-m=m~1nr?vlnrrTFFr._m.-JJ..阡.hunn0nnBnnnn001若lItT,.lI,(I,!T!I1T_,IT汉理运运运一E，程程，程gHg基业程i于--11---II---I.-；*ii---11---?---1!■4丁-丁-|-4丁-丁-丁-1—f-XT-VA4二，H/l■丸-9JyJiJ*lrrl.-.+''JyJ二dJ>-J'J.2.错误输入输入的数据都要大于0.r圆BC:\Windcw式5y5tlem32\cmd.exe三、调试分析基础问题l.vector的运用：①end()的误用解决：end()返回的向量中最后一个元素后面位置的指针②earse()函数的调用解决：函数括号内是迭代器，不是下标2.sleep()的用法Sleep函数//S要大写头文件#include<windows.h>③函数调用形式Sleep(500);//单位是毫秒技术问题.作业关系大小的设计错误理解：以为只要比较作业的优先级就可以了，这样设计无法实现先进先出的原则解决：设计作业大小比较时，优先考虑作业的优先级，如果优先级一样的话，再根据作业的num值比较大小(即进入系统的先后顺序).优先队列的设计

难点：①调整节点条件的分析当二叉树只有一个节点时，不需要进行下调工作因为进行下调操作的是一个最小堆，只要被调整元素比它的两个子节点都小，就可以直接跳出循环节点比较不需要考虑相等的情况，因为每个作业的num值一定是不一样的，所以就算优先级一样，也一定不会相等调试错误.编写最小堆的时候，有几个函数不小心写成了最大堆的效果，找了好久的错误.Work类,在编写赋值操作符重载时，用的是成员函数，却在函数里新创了个对象，结果出现了错误四、测试结果分析:程序的运行结果痢C：V//indowsVsystem3-2\cmd.exe旬为为为为为为为为为：间hMnn000conHHm00Du111-11...铿运运运运运运运运运一前.田口王口王匚王口王口王口石口王口三□王口±得度熠间聘长间作时间1个S日工塞必人人«£」请请刚开始只产生了一个作业，所以就执行改作业在在在在在在在在在正正正正正正正正正序运行时间为正程序运行时间为22完毕，用时2•等待0产生了两个作业，且此时没有作业在执行，作业4的优先级比作业3大，所以先执行作业43345上222A-二耳./耳/^，x^-_uunnnn堂u耳书运运运1口五口王口王M-聚*4,茁机机需需酒0>22为为;二LMHH曰-T--T口正□壬0200212:为为作爵父-AE轮进力,k此时共有Z作业等待处理,进入时间为等待时间为明需执行时间“优先级为2稣愉，…耕AFd向小70笛在口寸同小92214

为为为为

及及及及

w+-mt£*:-

先先先先睡C:\V/indowsVsystem52\cmd.exe»>■/3J2三111AAAA进进进进2214「m_xm、-m、-m00@01111为为为为-1J.-m.-m…开埴执行作业3,进入中间为也等待时间为%霄执行时间工，优先级为i岸运柠时间为H恒山处理完单，用毗.等制嚼辘黑,懿翳为椒等待时间为却需执行时间会.优先级为］三客y婚彳霸五军％感理器电用时2.等待1—开阳拉正作业5,进入时间为1M等待时间为露需执行时间入优先级为程序运打;询为14,正在就行待业5…程序运四间夕・•凡作必居里完毕，用时2.等待3运运运口王口王口王1亡4天运运运口王口王口王1亡4天丸日00中亍亍一丁^Rzn.1i■:等二年，4.4,4.»■10业业业理5-T-1T4-寸丸丸日一匕一匕一人在进正正正以*KFKhj467B11isJr—-LMJ.一---t,用用即:B-TUMLT优先级为T作业2、5的优先级是相同的，而作业2先进入队列，所以先执行作业2作业执行时，输出执行语句，并调用Sleep函数，表示正在执行34为34为为-日ial・HQHQ-1T——J-需需0055为为-miTm力力日日进进0055为为一m一日入次1TAh.Ta**12i1日B五、附录Heap.h#include<iostream>#include<vector>usingnamespacestd;#ifndefMYHEAP#defineMYHEAP//防止因头文件被反复调用，而导致重复定义//应用模板类template<typenameDATA>classMyHeap{vector<DATA>mh;//用向量实现堆public:MyHeap();//构造函数boolempty();//判空函数DATAtop();//取队首元素voidpop();//删除队首元素voidpush(constDATA&item);//压入元素voidupdate();//所有元素-1intsize();//获取元素个数voidshow();//调用graph()private:voidpush_down();//向下更新voidpush_up();//向上更新voidswap(DATA&a,DATA&b);//交换两个元素boolcan_push(intpos);//判断是否需要向下更新voidgraph(ints);//输出队列的所有信息};template<typenameDATA>MyHeap<DATA>二MyHeap(){mh.clear();//清空队列}template<typenameDATA>boolMyHeap<DATA>二empty(){returnmh.size()==0;//判断向量里是否有元素}template<typenameDATA>DATAMyHeap<DATA>::top(){returnmh[0];//向量的第一个元素就是队首}template<typenameDATA>voidMyHeap<DATA>::swap(DATA&a,DATA&b){DATAc=a;a=b;b=c;}template<typenameDATA>boolMyHeap<DATA>::can_push(intpos){intl=mh.size();//若没有左节点或当前节点小于左节点且没有右节点或当前节点小于右节点，那么就不需要再下移if((pos*2+1>=l||mh[pos]<mh[pos*2+1])&&(pos*2+2>=l||mh[pos]<mh[pos*2+2]))returnfalse;returntrue;}template<typenameDATA>voidMyHeap<DATA>二push_down(){intpos=0,l=mh.size();while(can_push(pos)){//若需要下移，则一定有左儿子，因为堆是一个完全二叉树inttar=pos*2+1;//tar先指向左节点if(pos*2+2<l&&mh[pos*2+2]<mh[pos*2+1])//若有右节点且右节点比左节点小tar++;//则tar指向右节点swap(mh[pos],mh[tar]);//交换当前节点和他左右节点中较小的那个pos=tar;//当前节点移到交换的子节点处}}template<typenameDATA>voidMyHeap<DATA>二pop(){swap(mh[0],mh[mh.size()-1]);//将队首元素放到最后vector<DATA>::iteratorit=mh.end();//迭代器先指向end();it--;//自减操作，此时it指向最后一个元素mh.erase(it);//删除最后一个元素，即删除了原队首元素push_down();//从队首向下更新}template<typenameDATA>voidMyHeap<DATA>二push_up(){intnow=mh.size()-1,tar;while(now>0){//从最后一个元素开始，直到队首tar=(now-1)/2;//tar指向当前节点的父节点if(mh[tar]<mh[now])break;//如果父节点是小于当前节点，则不用再上移swap(mh[tar],mh[now]);//否则交换父节点和当前节点now=tar;//当前节点改为父节点}}template<typenameDATA>voidMyHeap<DATA>二push(constDATA&item){mh.push_back(item);//先将新节点加到最后push_up();//再向上更新}template<typenameDATA>voidMyHeap<DATA>二update(){//所有元素-1for(inti=0;i<mh.size();i++)mh[i]--;

template<typenameDATA>intMyHeap<DATA>::size(){returnmh.size();//返回向量的大小}template<typenameDATA>voidMyHeap<DATA>::show(){graph(0);}递归调用，输出以s递归调用，输出以s为根节点的子树先输出左子树若当前节点存在，输出当前节输出右子树voidMyHeap<DATA>::graph(ints){//if(s*2+1<mh.size())graph(s*2+1);//if(s<mh.size())cout<<mh[s]<<"\n";//点的信息if(s*2+2<mh.size())graph(s*2+2);//}#endifWork.h#include<iostream>usingnamespacestd;#ifndefMYWORK#defineMYWORKclassWork{public:ints,t,p,num;Work();Work(intn,inta,intb);friendbooloperator<(constWork&a,constWork&b);//重定义小于Work&operator--();////自减操作重载Work&operator=(constWork&a);//赋值操作重载friendostream&operator<<(ostream&out,constWork&a);//输出流重载};#endifSystem.h#ifndefMYSYSTEM#defineMYSYSTEM#include<iostream>#include<stdio.h>#include<vector>#include<time.h>//系统自带的头文件都可以#include"Heap.h"//自己写的头文件，要用引号#include"Work.h"#include<windows.h>usingnamespacestd;classSystem{MyHeap<Work>mw;//队列，存储所有工作intT;//记录系统运行的时间intend;//如果有作业在运行，记录该作业结束时的系统时间booliswork;//是否有作业正在运行Workwk;〃若有作业在运行，记录该作业的信息intSIZE;//系统允许新增工作的时间，超过此时间后，系统执行完所有作业后，就结束public:System();//构造函数，在创建变量时才会调用boolrun();//执行函数，模拟作业的调度};#endifWork.cpp#include"Work.h"Work::Work(){}Work::Work(intn,inta,intb){//构造函数num=n;//作业的编号s=a;//作业进入的时间t=p=b;〃作业的执行时间和优先级}booloperator<(constWork&a,constWork&b){//重定义小于if(a.p!=b.p)returna.p<b.p;//先按优先级排，优先级小的小returna.num<b.num;//否贝U,先进入的小//因为创建的是最小堆，所以在队首的是优先级小的，符合题目要求)Work&Work::operator--(){//自减操作重载P--；return*this;)Work&Work::operator=(constWork&a){//赋值操作重载s=a.s;t=a.t;P=a.p;num=a.num;return*this;)ostream&operator<<(ostream&out,constWork&a){//输出流重载returnout<<"作业"<<a.num<<”进入时间为"<<a.s<<"执行时间"<<a.t<<"优先级为“<<a.p;)System.cpp#include"System.h"System::System(){T=0;//初始系统时间为0iswork=false;//初始没有作业在运行SIZE=60;)boolSystem::run(){system("cls");intD,L,N;cout<<"请输入时间问隔：";cin>>D;if(D<=0){printf("时间间隔要大于0!!!\n");Sleep(500);returnfalse;)cout<<"请输入工作时间：";cin>>SIZE;if(SIZE<=0){printf("工作时间要大于0!!!\n");Sleep(500);returnfalse;)cout<<”请输入作业长度上限：";cin>>L;if(L<=0){printf("作业长度要大于0!!!\n");Sleep(500);returnfalse;)cout<<"请输入每个间隔产生的作业数的上限：";cin>>N;if(N<=0){printf("产生作业数的上限要大于0!!!\n");Sleep(500);returnfalse;)srand(time(0));〃把时间作为种子，若不调用此函数，产生的随机数都是伪随机的，每次程序运行的结果都一样inttol=0;//表示作业的编号for(T=0;T<SIZE;T++){〃这段时间会随机产生新的作业mw.update();//因为等待时间+1,所以队列里所有的作业的优先级-1if(iswork&&end==T){//如果正在运行的作业结束了iswork=false;//表示没有作业在运行cout<<"***程序运行时间为"<<T<<",