时间片轮转调度.doc

OS实验二 (软件) 2010.11.4时间片轮转调度算法的实现数据结构：typedef struct pcb /*进程控制块定义*/char pnameN; /*进程名*/int runtime; /*服务时间*/int arrivetime; /*到达时间*/char state; /*进程状态*/struct pcb *next;/*联接指针*/PCB;实验要求：n 给出程序中使用的数据结构及符号说明n 给出程序流程图和源程序，源程序中要附有详细的注释n 输入：时间片，五个进程的进程名、到达时间、服务时间n 输出：打印程序运行时的初值和运行结果，要求如下：（1）选中运行进程的名、运行后各进程控制块状态；（2）计算平均周转时间和带权平均周转时间。n 总结收获体会及对该题解的改进意见和见解输入 时间片 1 作业号 A B C D E 到达时间 1 2 3 4 5 开始时间 1 2 3 4 5 服务时间 4 3 5 2 4输出运行时刻: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 运行进程名: A B C D E A B C D E A B C E A C E C运行后状态: R R R R R R R R C R R C R R C R C C front rear(一)分析题意得模型C 2 5 R B 1 3 RA 0 4 R head数据结构的建立可参考实验一与数据结构书（二）写主要算法时间片轮转调度算法的实现:void RR(queue *head,int q)/*进程队列不为空才可调度*/* 第一种情况： 当前运行的时间小于最后一个进程到达的时间做以下操作*/ 1. 运行时间小于0，删除队首 / 2. 运行时间大于0，向后找位置插入 （分三种情况）/*时刻变化*/* 第二种情况：当前运行的时间大于最后一个进程到达的时间做以下操作*/ 1. 运行时间小于0，删除队首 / 2. 运行时间大于0，直接插在队尾 /*时刻变化，队列为空时不做时刻变化*/详情见源代码注释（三）调试运行（多种情况都要运行）（四）体会及不足1. 加深了自己对链表中字符的处理, 以及时间片轮转第一种情况(当前运行时间小于最后一个进程的到达时间)的理解, 花了不少时间分清类并修改。逻辑思考方面，这是我需要改进的。2. 特别是调试运行阶段,一开始,有些情况能运行正确,有些不行,这就更需要我重新对时间片轮转的时间分类处理好,查看有没少情况.3. 不足是:对于第一种和第二种情况的第1种情况都类似(运行时间小于0，删除队首),觉得最好可写一个函数,就不用重写代码。最难做到的是使代码表达简明，清晰。这也是我需要改进的。源代码：/*操作系统实验二：模拟时间片轮转调度算法（头文件RR.h）*/*定义进程控制块*/typedef struct pcbchar pname5; /进程名int arrivetime; /到达时间int runtime; /运行时间char state; /运行后的状态struct pcb *next;PCB;/*封装头结点，指针分别指向队头和队尾*/typedef struct PCB *front,*rear;queue;/*进程队列置空*/queue *init()queue *head;head=(queue*)malloc(sizeof(queue);head-front=NULL;head-rear=NULL;return head;/*检验进程队列是否为空*/int empty(queue *head)return(head-front ? 0:1);/*进程队列入队，往后插入*/queue *append(queue *head,char c5,int a,int r,char s)PCB *p;p=(PCB*)malloc(sizeof(PCB);strcpy(p-pname,c);p-arrivetime=a;p-runtime=r;p-state=s;p-next=NULL;if(empty(head)head-front=head-rear=p;elsehead-rear-next=p;head-rear=p;return head;/*创建进程队列*/queue *creat(queue *head)char c5;char s=R;int a,r,i,n;printf(请输入共有几个进程:n);scanf(%d,&n);for(i=1;ifront;if(!p)printf(时间片轮转调度队列为空!n);while(p)printf(pname=%s arrivetime=%d runtime=%d state= %c,p-pname,p-arrivetime,p-runtime,p-state);printf(n);p=p-next;/*时间片轮转调度算法的实现*/void RR(queue *head,int q)int t=head-front-arrivetime,lt=head-rear-arrivetime;if(head-front-runtimefront-runtime;elset=t+q;/*进程队列不为空才可调度*/while(!empty(head)PCB *p1,*p2;/* 第一种情况： 当前运行的时间小于最后一个进程到达的时间做以下操作*/while(tfront;printf(运行的时刻为%dt运行的进程为%st,t,p1-pname);p1-runtime=p1-runtime-q;/ 1. 运行时间小于0，删除队首 /if(p1-runtimestate=C;printf(运行后的状态为%cn,p1-state);head-front=p1-next;free(p1);/ 2. 运行时间大于0，向后找位置插入 /elseprintf(运行后的状态为%cn,p1-state);p2=p1-next;while(p2-next&p2-arrivetime!=t)p2=p2-next;/此时无新进入队列的进程时,有两种情况:1.不用找位置往后插入,队首不变，不做操作 2.找位置往后插入/if(p2-arrivetime!=t) PCB *p3=p1,*p4; while(p3-next&p3-arrivetimenext;if(p3-arrivetimet)if(p4!=p1)/p1插在p4后，头为p1-nexthead-front=p1-next;p1-next=p4-next;p4-next=p1;else/不做操作/p4=p3=p2=NULL;elsep4=p3=p2=NULL;/此时有新进入队列的进程时:p1插在新进入队列的进程p2后，队首为p1-next/ elsehead-front=p1-next;p1-next=p2-next;p2-next=p1;/*时刻变化*/if(head-front-runtimefront-runtime;elset=t+q;/*第一种情况结束*/* 第二种情况：当前运行的时间大于最后一个进程到达的时间做以下操作*/while(t=lt)p1=head-front;printf(运行的时刻为%dt运行的进程为%st,t,p1-pname);p1-runtime=p1-runtime-q;/ 1. 运行时间小于0，删除队首 /if(p1-runtimestate=C;printf(运行后的状态为%cn,p1-state);head-front=p1-next;free(p1);/ 2. 运行时间大于0，直接插在队尾 /elseprintf(运行后的状态为%cn,p1-state);/若原队列只有一个进程，不必往队尾插/if(!p1-next) head-front=p1;/若原队列有多个进程/elsehead-front=p1-next;head-rear-next=p1;head-rear=p1;p1-next=NULL;/*时刻变化，队列为空时不做时刻变化*/if(empty(head) return;elseif(head-front-runtimefront-runtime;elset=t+q; /*第二种情况结束*/*操作系统实验二：模拟时间片轮转调度算法*/#include#include#include#incl