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

1、目的要求：用高级语言编写一个程序，先用可变时间片轮转法将输入的任意个进程进行调度，再用先来先服务法对它们进行作业调度，以加深对进程调度和作业调度算法的理解。数据结构设计：进程属性结构：struct pcbnodeint pid;/进程id int priority;/优先数 int trtime;/总运行时间 int rtime;/剩余运行时间 int atime;/从开始到全部进入就绪队列所需的时间 int stime;/开始运行时间 int ftime;/完成运行时间 int ttime;/周转时间 float wttime;/带权周转时间;队列属性结构：struct qnode/进程队列

2、 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& cti

3、me,pcbnode* pt);先来先服务类：void fcfs(lq& q,int& ttimesum,int& wttimesum,pcbnode* pt);实验环境：c+语言程序设计平台算法流程设计：开始在input文件中输入各个进程的从开始到全部进入就绪队列所需时间、剩余运行时间、优先数，一行一进程输入进程数和时间片大小初始化就绪队列，将文件中进程投入运行等待队列为空为队列首进程分配时间片进程在时间片内做完计算周转时间和带权周转时间将该进程退出队列，计算周转时间和带权周转时间将文件中的作业（进程）投入队列运行并确定其开始和完成时间运行队首作业，计算周转时间和带权周转时间，退出队列计算时

4、间片轮转调度的平均周转时间和带权周转时间并打印将其后一作业移至队首计算先来先服务的平均周转时间和带权周转时间并打印结束ynyn下一进程到来将该进程移至队末，将其后一进程移至队首yn将其后一进程移至队首其后有进程yn等待队列为空其后有作业yynn运行事例演示：input文本中输入： 运行结果： 在input文本中所输入的三列数据分别为：各进程的从开始到全部进入就绪队列所需的时间、剩余运行时间、优先数，而真正在轮转与服务中起到作用的只有前两者。上述程序0到4的编号是按每行进程的输入顺序分配的，在时间片轮转调度中，其执行顺序起初也按编号的从小到大排序，但当它们由于一次使用完时间片后为完成其所有工作量

5、而需再次被调用时，其运行顺序就与input文本中第一列数据相关了，例如进程2和3，由于进程3全部进入队列的时间为11，而当进程2第一次运行后所过去的时间只有9（执行了三次大小为3的时间片），于是接下来仍运行一次进程2，之后才轮到进程3（此时过去时间为12），接着就是剩余进程轮转运行直到结束。其后就是先来先服务，按进程编号由小到大运行，各个进程所占的时刻数就是它们input文本中第二列的数据，也就是运行时间。源程序：#include#include#include#includeusing namespace std;struct pcbnodeint pid;/进程id int priorit

6、y;/优先数 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

7、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 wttimesu

8、m=0;/带权周转时间 pcbnode* pt=new pcbnodepn;/进程表 coutpn;/输入在input文件中所输入的进程的个数（每行一个进程） coutpiece;/输入所需时间片的大小 input(pt,pn);/调用input.txt文件中进程数据 initialqueue(q,pt,pn);/初始化就绪队列 roundrobin(q,piece,ttimesum,wttimesum,pt);/可变时间片轮转进程调度，调用deal()，piece为时间片大小 cout可变时间片轮的平均周转时间为：ttimesum/pnendl; cout可变时间片轮的平均带权周转时间为：w

9、ttimesum/pnendl; input(pt,pn); initialqueue(q,pt,pn); fcfs(q,ttimesum,wttimesum,pt);/先来先服务作业调度 cout先来先服务的平均周转时间为：ttimesum/pnendl; cout先来先服务的平均带权周转时间为：wttimesum/pnendl; delete pt; return 0;void input(pcbnode* pt,int pn)file* fp;/读入进程相关内容 if(fp=fopen(input.txt,r)=null)/若无法访问input文件 coutcan not open fi

10、le!endl; exit(0); for(int i=0;ipn;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;inext=null; qnode* p; qnode* q; for(i=0;iid=pti.pid; p-next=null; if(i=0) q.head-next=p; else q-next=p; q

11、=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内，活动进程

12、为：idendl; cout进程id 现在需要的时间片为：id.rtimeendl; finish=deal(q,q,p,piece,ctime,pt);/分配时间片给q进程 coutnext=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.atimectime+piece); p=q;/若下个进程不来，则继续给当前进程分配时间片 q=q

13、-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.rtimeid.ftime=ctime+ptq-id.rtime; ptq-id.ttime+=ptq-id.rtime; ptq-id.wttime=ptq-id.ttime/ptq-id.trtime; ctime=ptq-id.f

14、time; p-next=q-next; coutendl; cout进程id完成！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

15、; ptp-id.ftime=ptp-id.atime+ptp-id.trtime; for(q=p-next;q!=null;q=q-next) if(ptq-id.atimeid.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)/计算平均周转时

16、间和平均带权周转时间 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(tid.ftime) cout时刻t：进程id活动next!=null) cout时刻t：进程id结束活动，开始下一个进程。endl; cout进程id的周转时间为：id.ttimeendl; cout进程id的带权周转时间为：id.wttimeendlendl; else cout时刻t：进程id结束活动。endlendl; cout进程id的周转时间为：id.ttimeendl; cout进程id的带权周转时间为：id.wttimeendlendl; cout所有进程