多级反馈队列调度算法的实现

学生实习报告课程名称_数据结构与数据处理应用训练目名称多级反馈队列调度算法的实现学生学院计算机与计算科学专业班级学号学生姓名指导教师2012年2月16日多级反馈队列调度算法的实现【摘要】多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8，最后一级就绪队列采用FIFO调度，将任务进入多级队列进行模拟，任务从优先级高的队列到优先级地的队列的顺序逐一进入，还用了算法支持抢占式，最后完成模拟，得到各个任务先后完成的顺序，还有得到各个任务的响应时间、离开时间、周转时间。【关键词】队列优先级任务时间1与要求【内容】多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，本次试验就是试用C语言模拟某多级反馈队列调度算法，通过输入任务号、到达时间、运行时间，求出任务完成的先后顺序以及各个任务的响应时间、离开时间、周转时间。【要求】多级反馈队列调度算法描述：1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8；最后一级就绪队列采用FIFO调度。2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。5、在低优先级的队列中的任务在运行时，又有新到达的任务，CPU马上分配给新到达的任务。（注：与原来的题目不同，原题是在低优先级的队列中的任务在运行时，又有新到达的任务时，要在运行完这个时间片后，CPU马上分配给新到达的任务，而本题不需要在运行完这个时间片，即正在进行的任务立刻停止，CPU马上分配给新到达的任务）6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务（即输入）。2总体2.1算法总体思路：这是建立在一个时间轴上的，即时刻，一个一个时刻（时间点）进行。2.1.1主函数思路：先初始化所有队列，再输入任务个数，如果输入个数为0，则重新输入，然后输入各个任务的信息，即任务号、到达时间、运行时间，再当时刻到任务的到达时间时，就创建任务，然后运行任务，时刻自动加1，创建任务与运行任务进行循环，直到所有任务进行完或所有队列为空才跳出循环，最后清空所有队列。2.1.2功能函数思路：voidcreate(LinkQueue*x,Jobjob)：使任务的已运行时间为0，再使任务进入第一个队列。voidfunction(LinkQueue*x,inttiming)：四个队列从第一个到第四个，即从最高优先级开始，任务在4个队列中逐个进行，根据任务是否为第一次执行，求出响应时间，任务完成时，求出离开时间和周转时间输出信息，在前3个队列，如果任务刚完成一个就绪队列的时间片，就降低优先级，使任务进入下一个队列。2.2功能模块介绍：voidmain()函数功能：主函数voidInitQueue(LinkQueue&HQ)：队列的初始化voidEnQueue(LinkQueue&HQ,ElemTypeitem)函数功能：向队列中插入一个元素ElemTypeOutQueue(LinkQueue&HQ)函数功能：从队列中删除一个元素ElemType*PeekQueue(LinkQueue&HQ)函数功能：读取队首元素boolEmptyQueue(LinkQueue&HQ)函数功能：检查队列是否为空voidClearQueue(LinkQueue&HQ)函数功能：清除链队中的所有元素，使之变为空队voidcreate(LinkQueue*x,Jobjob)函数功能：创建任务。voidfunction(LinkQueue*x,inttiming)函数功能：任务运行。2.3输入输出输入：任务号到达时间运行时间输出：任务号响应时间离开时间周转时间、2.4文件介绍main.cpp:主函数的存放，功能函数的调用。queue.h:队列的各个基本功能函数，任务的创建函数与运行函数。3详细设计3.1存储结构描述structJob{intjobnum;//任务号intarrivetime;//到达时间intburst;//运行时间intretime;//响应时间intleavetime;//离开时间introundtime;//周转时间intruntime;//已运行时间};//任务的存储结构typedefJobElemType;//任务的类型定义structLNode{ElemTypedata;//值域LNode*next;//链接指针域};structLinkQueue{LNode*front;//队首指针LNode*rear;//队尾指针};3.2参数说明timing是时刻，时间轴；Job*jobing：任务数组（动态分配）intleatime[4];//时间片大小到达时间：任务请求的时刻运行时间：任务运行完需要的时间响应时间：任务从到达时间到任务第一次执行的时间差周转时间：任务从开始请求（到达时间）到任务完成离开的时间已运行时间：任务已运行的时间离开时间：任务运行完后离开队列的时刻3.3具体算法voidInitQueue(LinkQueue&HQ)算法：队首队尾设置为空。voidEnQueue(LinkQueue&HQ,ElemTypeitem)算法：得到一个新结点，把item的值赋给新结点的值域，再把新结点的指针域置空，若链队为空，则新结点既是队首又是队尾，若链队非空，则新结点被链接到队尾并修改队尾指针。ElemTypeOutQueue(LinkQueue&HQ)算法：若链队为空则中止运行，暂存队首元素以便返回，暂存队首指针以便收回队首节点，使队首指针指向下一个结点，若删除后链队为空，则使队尾指针为空，然后回收原队首节点，返回被删除的队首元素。ElemType*PeekQueue(LinkQueue&HQ)算法：若链队为空则中止运行，返回队首元素指针（Job*）。boolEmptyQueue(LinkQueue&HQ)算法：判断队首或队尾任一个指针是否为空即可。voidClearQueue(LinkQueue&HQ)算法：队首指针赋给p，依次删除队列中的每个结点，然后循环结束后队首指针已经变空，置队尾指针为空。voidcreate(LinkQueue*x,Jobjob)算法：使任务的已运行时间为0，再使任务进入第一个队列。voidfunction(LinkQueue*x,inttiming)算法：将4个队列设为循环，从第一个队列开始到第四个队列逐个进行以下操作。判断队列是否为空，当队列不为空时，则继续，若该队列的已运行时间为1并且时刻已等于或大于任务的到达时间，即判断任务是否为第一次执行，若是，求出任务响应时间=当前时刻-任务到达时间，即发出请求到任务开始的时间差。如果运行完，求出任务离开时间=当前时刻+1，周转时间=离开时间-到达时间，输出任务信息，再判断该任务是否完成该队列的时间片，若是，则降低优先级，任务进入下一级队列。所有队列遍历完，任务均完成，循环结束。4程序测试测试一：测试数据：1082643912测试二：测试数据：10725437134129测试三：当输入错误，输入任务个数是0，重新输入测试数据：10725437134129测试四：测试数据：115242测试五：测试数据：12823237549105146选作（同个时间点多个任务请求）测试六：测试数据：1232243694675这次实验用了多级反馈队列调度算法，这个算法我们没有学过，所以理解有点困难，但是，这个算法中涉及到了队列，它是队列的升级，是多级队列，因此，我在此不仅学到了新的知识，还是对数据结构中队列部分的熟悉与加深，更好的掌握了队列知识。这次实验我的题目与原题有点差别，在低优先级的队列中的任务在运行时，又有新到达的任务，那么在运行完这个时间片后，CPU马上分配给新到达的任务，即算法支持抢占式，但我的程序确是在新到达的任务，那么这个任务立即中止，CPU马上分配给新到达的任务，我觉得这样更好。当然，这次编程中遇到过许多困难，比如存储结构顺序的错误，又比如ElemType*PeekQueue(LinkQueue&HQ)，这是与队列的原基础功能函数有所区别，它需要的是返回元素指针（Job*），我原来返回的是元素，后来经过调试，错误提示，才改正确等等。多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法。现实中，我们在计算机中打开各种程序，就是多级反馈队列调度算法的应用，这次是我们对操作系统操作的模拟，与实际相联系，增加了趣味性。这次是我们第一次接触操作系统，对操作系统原理有了一定的了解，为我们将来学习操作系统打下了基础。参考文献《数据结构实用教程》附录main.cpp#include#include#include#include"queue.h"voidmain(){LinkQueue*x;intn,i;inttiming=0;//时刻Job*jobing;//任务数组（动态分配）x=(LinkQueue*)malloc(sizeof(LinkQueue)*5);for(i=1;i<=4;i++)//初始化所有队列InitQueue(x[i]);cout<<"请输入任务个数："<>n;if(n==0){cout<<"没有任务，请重新输入"<>n;}jobing=newJob[n];//动态空间分配cout<<"请输入各个任务信息："<>jobing[i].jobnum>>jobing[i].arrivetime>>jobing[i].burst;i=0;while(i!=n||!(EmptyQueue(x[1])&&EmptyQueue(x[2])&&EmptyQueue(x[3])&&EmptyQueue(x[4]))){while(timing==jobing[i].arrivetime){create(x,jobing[i]);//创建任务i++;}function(x,timing);//任务运行timing++;}for(i=1;i<=4;i++)ClearQueue(x[i]);//清空队列}queue.hstructJob{intjobnum;//任务号intarrivetime;//到达时间intburst;//运行时间intretime;//响应时间intleavetime;//离开时间introundtime;//周转时间intruntime;//已运行时间};typedefJobElemType;structLNode{ElemTypedata;LNode*next;};structLinkQueue{LNode*front;LNode*rear;};voidInitQueue(LinkQueue&HQ){HQ.front=HQ.rear=NULL;}voidEnQueue(LinkQueue&HQ,ElemTypeitem){LNode*newptr=newLNode;newptr->data=item;newptr->next=NULL;if(HQ.rear==NULL)HQ.front=HQ.rear=newptr;elseHQ.rear=HQ.rear->next=newptr;}ElemTypeOutQueue(LinkQueue&HQ){if(HQ.front==NULL){cerr<<"QueueNULL."<data;LNode*p=HQ.front;HQ.front=p->next;if(HQ.front==NULL)HQ.rear=NULL;deletep;returntemp;}ElemType*PeekQueue(LinkQueue&HQ){if(HQ.front==NULL){cerr<<"队列为空无首元素。"<data;}boolEmptyQueue(LinkQueue&HQ){returnHQ.front==NULL;}voidClearQueue(LinkQueue&HQ){LNode*p=HQ.front;while(p!=NULL){HQ.front=HQ.front->next;deletep;p=HQ.front;}HQ.rear=NULL;}voidfunction(LinkQueue*x,inttiming)//任务运行{intleatime[4];//时间片的大小leatime[0]=0;leatime[1]=2;leatime[2]=6;leatime[3]=14;Job*t=NULL;inti=1;while(i<5){if(EmptyQueue(x[i])==false)//如果队列不为空{t=PeekQueue(x[i]);//读取队首元素t->runtime++;//已运行时间+1if(t->runtime==1&&timing>=t->arrivetime)t->retime=timing-t->arrivetime;if(t->runtime==t->burst){t->leavetime=timing+1;t->roundtime=t->leavetime-t->arrivetime;cout<<"任务号:"<jobnum<<""<<"响应时间:"<retime<<"";cout<<"离开时间:"<leavetime<<""<<"周转时间:"<roundtime;cout<runtime==leatime[i])&&(i<=3)){//调整优先级EnQueue(x[i+1],OutQueue(x[i]));}break;}i++;}}voidcreate(LinkQueue*x,Jobjob){job.runtime=0;EnQueue(x[1],job);}