可变时间片轮转+先来先服务实验报告.doc

目的要求：用高级语言编写一个程序，先用可变时间片轮转法将输入的任意个进程进行调度，再用先来先服务法对它们进行作业调度，以加深对进程调度和作业调度算法的理解。数据结构设计：进程属性结构：struct PCBNodeint PID;/进程ID int priority;/优先数 int TrTime;/总运行时间 int RTime;/剩余运行时间 int ATime;/从开始到全部进入就绪队列所需的时间 int STime;/开始运行时间 int FTime;/完成运行时间 int tTime;/周转时间 float WtTime;/带权周转时间;队列属性结构：struct QNode/进程队列 int ID; struct QNode* next;/队列中下一个进程指针;队列头结构：struct LQQNode* head;/队列首部;进程输入类：void input(PCBNode* PT,int PN);进程初始化类：void InitialQueue(LQ& Q,PCBNode* PT,int PN);时间片轮转类void RoundRobin(LQ& Q,int piece,int& tTimeSum,int& WtTimeSum,PCBNode* PT);时间片分配类：bool Deal(LQ& Q,QNode* q,QNode* p,int piece,int& CTime,PCBNode* PT);先来先服务类：void FCFS(LQ& Q,int& tTimeSum,int& WtTimeSum,PCBNode* PT);实验环境：C+语言程序设计平台算法流程设计：开始在input文件中输入各个进程的从开始到全部进入就绪队列所需时间、剩余运行时间、优先数，一行一进程输入进程数和时间片大小初始化就绪队列，将文件中进程投入运行等待队列为空为队列首进程分配时间片进程在时间片内做完计算周转时间和带权周转时间将该进程退出队列，计算周转时间和带权周转时间将文件中的作业（进程）投入队列运行并确定其开始和完成时间运行队首作业，计算周转时间和带权周转时间，退出队列计算时间片轮转调度的平均周转时间和带权周转时间并打印将其后一作业移至队首计算先来先服务的平均周转时间和带权周转时间并打印结束YNYN下一进程到来将该进程移至队末，将其后一进程移至队首YN将其后一进程移至队首其后有进程YN等待队列为空其后有作业YYNN运行事例演示：input文本中输入： 运行结果： 在input文本中所输入的三列数据分别为：各进程的从开始到全部进入就绪队列所需的时间、剩余运行时间、优先数，而真正在轮转与服务中起到作用的只有前两者。上述程序0到4的编号是按每行进程的输入顺序分配的，在时间片轮转调度中，其执行顺序起初也按编号的从小到大排序，但当它们由于一次使用完时间片后为完成其所有工作量而需再次被调用时，其运行顺序就与input文本中第一列数据相关了，例如进程2和3，由于进程3全部进入队列的时间为11，而当进程2第一次运行后所过去的时间只有9（执行了三次大小为3的时间片），于是接下来仍运行一次进程2，之后才轮到进程3（此时过去时间为12），接着就是剩余进程轮转运行直到结束。其后就是先来先服务，按进程编号由小到大运行，各个进程所占的时刻数就是它们input文本中第二列的数据，也就是运行时间。源程序：#include<iostream>#include<cstdio>#include<cmath>#include<cstring>using namespace std;struct PCBNodeint PID;/进程ID int priority;/优先数 int TrTime;/总运行时间 int RTime;/剩余运行时间 int ATime;/从开始到全部进入就绪队列所需的时间 int STime;/开始运行时间 int FTime;/完成运行时间 int tTime;/周转时间 float WtTime;/带权周转时间;struct QNode/进程队列 int ID; struct QNode* next;/队列中下一个进程指针;struct LQQNode* head;/队列首部;void input(PCBNode* PT,int PN);void InitialQueue(LQ& Q,PCBNode* PT,int PN);void RoundRobin(LQ& Q,int piece,int& tTimeSum,int& WtTimeSum,PCBNode* PT);bool Deal(LQ& Q,QNode* q,QNode* p,int piece,int& CTime,PCBNode* PT);void FCFS(LQ& Q,int& tTimeSum,int& WtTimeSum,PCBNode* PT);int main()LQ Q;/就绪队列 Q.head=NULL; int PN;/进程数 int piece;/时间片大小 int tTimeSum=0;/周转时间 int WtTimeSum=0;/带权周转时间 PCBNode* PT=new PCBNodePN;/进程表 cout<<"请输入进程数：" cin>>PN;/输入在input文件中所输入的进程的个数（每行一个进程） cout<<"请输入时间片大小：" cin>>piece;/输入所需时间片的大小 input(PT,PN);/调用input.txt文件中进程数据 InitialQueue(Q,PT,PN);/初始化就绪队列 RoundRobin(Q,piece,tTimeSum,WtTimeSum,PT);/可变时间片轮转进程调度，调用Deal()，piece为时间片大小 cout<<"可变时间片轮的平均周转时间为："<<tTimeSum/PN<<endl; cout<<"可变时间片轮的平均带权周转时间为："<<WtTimeSum/PN<<endl; input(PT,PN); InitialQueue(Q,PT,PN); FCFS(Q,tTimeSum,WtTimeSum,PT);/先来先服务作业调度 cout<<"先来先服务的平均周转时间为："<<tTimeSum/PN<<endl; cout<<"先来先服务的平均带权周转时间为："<<WtTimeSum/PN<<endl; delete PT; return 0;void input(PCBNode* PT,int PN)FILE* fp;/读入进程相关内容 if(fp=fopen("input.txt","r")=NULL)/若无法访问input文件 cout<<"can not open file!"<<endl; exit(0); for(int i=0;i<PN;i+) fscanf(fp,"%d %d %d",&PTi.ATime,&PTi.RTime,&PTi.priority);/输入各进程从开始到全部进入就绪队列所需的时间、剩余运行时间、优先数 fclose(fp);void InitialQueue(LQ& Q,PCBNode* PT,int PN)for(int i=0;i<PN;i+)/进程初始化 PTi.PID=i; PTi.TrTime=PTi.RTime; PTi.FTime=0; PTi.STime=0; PTi.tTime=0; PTi.WtTime=0; Q.head=new QNode; Q.head->next=NULL; QNode* p; QNode* q; for(i=0;i<PN;i+)/进程入队列就绪 p=new QNode; p->ID=PTi.PID; p->next=NULL; if(i=0) Q.head->next=p; else q->next=p; q=p; void RoundRobin(LQ& Q,int piece,int& tTimeSum,int& WtTimeSum,PCBNode* PT)tTimeSum=0;/总的周转时间 WtTimeSum=0;/平均周转时间 int CTime=0;/当前时间 QNode* p; QNode* q; QNode* r; bool finish=false;/调用Deal()后，该进程是否已经做完退出 p=Q.head; q=p->next; while(q!=NULL)/从队列首部开始依次分配时间片 do cout<<"*"<<endl; cout<<"在时间片"<<(CTime+1)/piece+1<<"内，活动进程为："<<q->ID<<endl; cout<<"进程"<<q->ID<<" 现在需要的时间片为："<<PTq->ID.RTime<<endl; finish=Deal(Q,q,p,piece,CTime,PT);/分配时间片给q进程 cout<<endl; if(!finish)/若是进程在本时间片内做完，则跳出dowhile循环 if(q->next=NULL) r=Q.head->next; else r=q->next; else /若未做完，计算周转时间和带权周转时间 tTimeSum+=PTq->ID.tTime; WtTimeSum+=PTq->ID.WtTime; delete q;/删除q进程 q=p; while(!finish&&(PTr->ID.ATime>CTime+piece); p=q;/若下个进程不来，则继续给当前进程分配时间片 q=q->next; if(q=NULL&&Q.head->next!=NULL) p=Q.head; q=p->next; delete Q.head; Q.head=NULL;bool Deal(LQ& Q,QNode* q,QNode* p,int piece,int& CTime,PCBNode* PT)/分配时间片给q所指进程，p为刚退出的进程if (PTq->ID.RTime<=piece)/若在此时间片内能够做完，之后退出进程调度 PTq->ID.FTime=CTime+PTq->ID.RTime; PTq->ID.tTime+=PTq->ID.RTime; PTq->ID.WtTime=PTq->ID.tTime/PTq->ID.TrTime; CTime=PTq->ID.FTime; p->next=q->next; cout<<endl; cout<<"进程"<<q->ID<<"完成！"<<endl; return true; else/若此时间片内做不完 PTq->ID.RTime=PTq->ID.RTime-piece; PTq->ID.tTime+=piece; CTime+=piece; return false; void FCFS(LQ& Q,int& tTimeSum,int& WtTimeSum,PCBNode* PT)tTimeSum=0;/平均周转时间 WtTimeSum=0;/平均带权周转时间 QNode* p; QNode* q; p=Q.head->next; if(p!=NULL)/确定开始和完成时间 PTp->ID.STime=PTp->ID.ATime; PTp->ID.FTime=PTp->ID.ATime+PTp->ID.TrTime; for(q=p->next;q!=NULL;q=q->next) if(PTq->ID.ATime<PTp->ID.FTime) PTq->ID.STime=PTp->ID.FTime; PTq->ID.FTime=PTp->ID.FTime+PTq->ID.TrTime; else/若下个进程到达时间较晚 PTq->ID.STime=PTq->ID.ATime; PTq->ID.FTime=PTq->ID.ATime+PTq->ID.TrTime; p=q; for(q=Q.head->next;q!=NULL;q=q->next)/计算平均周转时间和平均带权周转时间 PTq->ID.tTime=PTq->ID.FTime-PTq->ID.ATime; PTq->ID.WtTime=PTq->ID.tTime/PTq->ID.TrTime; tTimeSum+=PTq->ID.tTime; WtTimeSum+=PTq->ID.WtTime; int t=0; for(q=Q.head->next;q!=NULL;q=q->next) cout<<"*"<<endl; while(t<PTq->ID.FTime) cout<<"时刻"<<t<<"：进程"<<q->ID<<"活动"<<endl; t+; if(q->next!=NULL) cout<<"时刻"<<t<<"：进程"<<q->ID<<"结束活动，开始下一个进程。"<<endl; cout<<"进程"<<q->ID<<"的周转时间为："<<PTq->ID.tTime<<endl; cout<<"进程"<<q->ID<<"的带权周转时间为："<<PTq->ID.WtTime<<endl<<endl; else cout<<"时刻"<<t<<"：进程"<<q->ID<<"结束活动。"<<endl<<endl; cout<<"进程"<<q->ID<<"的周转时间为："<<PTq->ID.tTime<<endl; cout<<"进程"<<q->ID<<"的带权周转时间为："<<PTq->ID.WtTime<<endl<<endl; cout<<"所有进程结束活动。"<<endl<<endl; p=Q.head; for(q=p->next;q!=NULL;q=q->next) delete p; p=q; 小结：由于原课本中对于轮转法的描述过于简练，使我无法真正了解轮转法的内涵，于是我在网上查了相当量的资料并且阅读了一些与轮转法相关的实例，终于对轮转法有了基本的理解。而在正式着手写程序前我也曾有过个疑惑：进程调度和作业调度我究竟该分开写还是并一起写，因为两种方针都各有利弊，而最终我为了缩短时间，依然选择了将两部分合二为一，但也随之引来了如何将两者相结合的问题。最终我另外定义了队列模块，使得进程和两种方法能相互调剂，得以解决。