时间片轮转算法

《操作系统A》课程综合性实验报告开课实验室：基础七 2011年5月29日实验题目| 进程调度算法程序设计一、 实验目的通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。二、 设备与环境硬件设备：PC机一台软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C\C++\Java等编程语言环境。三、 实验内容（1） 用C语言（或其它语言，如Java）实现对N个进程采用某种进程调度算法（如动态优先权调度）的调度。（2） 每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：进程标识数ID。进程优先数PRIORITY，并规定优先数越大的进程，其优先权越高。进程已占用CPU时间CPUTIME。进程还需占用的CPU时间ALLTIME。当进程运行完毕时，ALLTIME变为0。进程的阻塞时间STARTBLOCK ，表示当进程再运行STARTBLOCK 个时间片后，进程将进入阻塞状态。进程被阻塞的时间BLOCKTIME，表示已阻塞的进程再等待BLOCKTIME 个时间片后，将转换成就绪状态。进程状态STATE。队列指针NEXT，用来将PCB排成队列。（3） 优先数改变的原则：进程在就绪队列中呆一个时间片，优先数增加1。进程每运行一个时间片，优先数减3。（4） 为了清楚地观察每个进程的调度过程，程序应将每个时间片内的进程的情况显示出来，包括正在运行的进程，处于就绪队列中的进程和处于阻塞队列中的进程。（5） 分析程序运行的结果，谈一下自己的认识。四、实验结果及分析实验设计说明用时间片轮转算法模拟单处理机调度。（1） 建立一个进程控制块PCB来代表。PCB包括：进程名、到达时间、运行时间和进程后的状态。进程状态分为就绪（R）和删除（C）。（2） 为每个进程任意确定一个要求运行时间和到达时间。（3） 按照进程到达的先后顺序排成一个队列。再设一个指针指向队首和队尾。（4） 执行处理机调度时，开始选择对首的第一个进程运行。（5） 执行：a）输出当前运行进程的名字；b）运行时间减去时间片的大小。（6） 进程执行一次后，若该进程的剩余运行时间为零，则删除队首，并将该进程的状态置为C；若不为空，则将向后找位置插入。继续在运行队首的进程。（7） 若进程队列不空，则重复上述的（5）和（6）步骤直到所有进程都运行完为止。在所设计的调度程序中，要求包含显示或打印语句。以便显示或打印每次选中进程的名称及运行一次后队列的变化情况。实验代码/****************沏寸间片轮转调度算法*******************/#include<stdio.h>#include<string.h>#include<stdlib.h>typedefstruct?定义进程控制块{charpname[5];/进程名intarrivetim（/到达时间intruntime;/运行时间charstate; /运行后的状态structpcb*next;}PCB;typedefstruck装头结点，指针分别指向队头和队尾{PCB*front,*rear;}queue;queue*init（进程队列置空{queue*head;head=（queue*）malloc（sizeof（queue））;head->front=NULL;head->rear=NULL;returnhead;}intempty(queue*head检验进程队列是否为空{return(head->front?0:1);}queue*append(queue*head,charc[5],inta,int进^程队列入队/往后插入{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;else{head->rear->next=p;head->rear=p;}returnhead;}queue*creat(queue*hea创建进程队列{charc[5];chars='R';inta,r,i,n;printf请输入进程的数量:")；scanf("%d”,&n);for(i=1;i<=n;i++){ printf请输入第%d个进程的进程名:〃，i);getchar();gets(c);printf(f输入第%d个进程的到达时间:〃，i);scanf("%d”,&a);printf请输入第%d个进程的服务时间:〃，i);scanf("%d”,&r);head=append(head,c,a,r,s);}returnhead;}voidprint(queue*hea输出创J建的进程队列{PCB*p;p=head->front;if(!p)printf("间片轮转调度队列为空!\n”);while(p){printf("pname=%s arrivetime=%d runtime=%dstate=%c",p->pname,p->arrivetime,p->runtime,p->state);printf(〃\n〃)；p=p->next;}}voidRR(queue*head,int时间片轮转调度算法的实现{intt=head-〉front-〉arrivetime,lt=head-〉rear-〉arrivetime;if(head->front->runtime<q=t+head->front->runtime;elset=t+q;while(!empty(head)进程队列不为空才可调度{PCB*p1,*p2;printf("远行的时刻运行的进程运行后的状态\n");while(t<lt第一种情况:当前运行的时间小于最后一个进程到达的时间做以下操作{p1=head->front;printf("%2d %s”,t,p1->pname);p1->runtime=p1->runtime-q;if(p1->runtime<=0)运行时间小于0，删除队首{p1->state='C';printf("%c\n”,p1->state);head->front=p1->next;free(p1);}else/运.行时间大于0，向后找位置插入{printf("%c\n”,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->arrivetime<t){ p4=p3;p3=p3->next;}if(p3->arrivetime>t){ if(p4!=p1)/插在p4后，头为p1->next{head->front=p1->next;p1->next=p4->next;p4->next=p1;}else不|故操作p4=p3=p2=NULL;}elsep4=p3=p2=NULL;}/此时有新进入队列的进程时:P1插在新进入队列的进程P2后，队首为p1->nextelse{head->front=p1->next;p1->next=p2->next;p2->next=p1;}}if(head->front->runtime<0J^燎化t=t+head->front->runtime;elset=t+q;}while(t>=lt第二种情况：当前运行的时间大于最后一个进程到达的时间做以下操作{p1=head->front;printf("%2d %s”,t,p1->pname);p1->runtime=p1->runtime-q;if(p1->runtime<=0)运行时间小于0，删除队首{p1->state='C';printf("%c\n”,p1->state);head->front=p1->next;free(p1);}else/运行时间大于0，直接插在队尾{printf("%c\n”,p1->state);if(!p1->next若原队列只有一个进程，不必往队尾插head->front=p1;else若原队列有多个进程{head->front=p1->next;head->rear->next=p1;head->rear=p1;p1->next=NULL;}}if(empty(head))/时刻变化，队列为空时不做时刻变化return;else{if(head->front->runtime<q=t+head->front->runtime;elset=t+q;}}}}voidmain(){queue*head;intq;head=init();head=creat(head);printf(〃您输入的时间片轮转进程队列为:\n〃)；print(head);printf("请输入时间片轮转调度的时间片为:")；scanf("%d”,&q);RR(head,q);时间片轮转调度}

实验结果输入进程的数量，每个进程的名称、到达时间和服务时间，以及时间片：函 -|口|-Istate=Rstate=Rstate=Rstate=Rstate=R44

■■■■:E^J^名其名曹名曹名甚客甜程达塞达塞达畚达塞达务5进船进能进能进重进船:勺勺勺.勺勺.勺勺.勺勺.勺勺.勺勺.勺勺•state=Rstate=Rstate=Rstate=Rstate=R44

■■■■:E^J^名其名曹名曹名甚客甜程达塞达塞达畚达塞达务5进船进能进能进重进船:勺勺勺.勺勺.勺勺.勺勺.勺勺.勺勺.勺勺•3B---1,-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--1■-■--ij—二..1二..1二..1二r二..1二..1二..1二..1二..1二..1二..1二..1二r二..1二..1建进进进进进进进进进进进进进进进射个个个个个个个个个个个个个个个■屯111222333444555进WWWWWWWWW1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A1A请请请请请请请请请请请请请请请请04132532■■■■■■■■■■■■■■■■A可司•B可可•C可可•D司.可您输入的时间片轮转进程队烫为:runtime=4runtime=3runtime=5runtime=2runtime=4arriuetime=0arriuetime=1arriuetime=2arriuetime=3arriuetime=4pname=Apname=Bpname=Cpname=Dpname=E的时间片为H请输入时恒得到的结果为:实验结果分析RR算法：每次调度时，把CPU分配给队首进程，并且令其执行一个时间片，时间片的大小从几个ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便依据此信号来停止该进程的执行；并且把它送往就绪队列的队尾；然后，再把处理剂分配给就绪队列中的新队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一个给定时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内相应所有用户的请求。成功实现了RR轮转调度算法，验证了算法实现程序的正确性。完成了实验要求的输入。5.实验心得通过这次课程设计，我的收获颇丰。课程设计之初我对时间片轮转法基本上没有什么深入的研究，只是通过课堂的讲解大致了解其思想。经过这将近两周的学习后，我对时间片轮转算法的理解有了更进一步的提高，并通过自己设计程序，自己试验，自己调试对算法的内容更进一步的深刻认识。老师让我们去图书馆自行查阅资料。在这期间，我不还在图书馆找到一些别