实验四 带优先级的时间片轮换的进程调度算法的实现

1、实验四 带优先级的时间片轮换的进程调度算法的实现实验学时：4实验类型：设计实验要求：必修一、实验目的（1）掌握进程状态转换过程（2）掌握时间片轮转的进程调度算法；（3）掌握带优先级的进程调度算法；二、实验内容（1）自定义PCB的数据结构；（2）使用带优先级的时间片轮转法调度进程，每运行一个时间片，优先级减半。（3）命令集A）create 随机创建进程，进程的优先级与所需要的时间片随机决定；B）round 执行1次时间片轮转操作，其方法为运行高优先级队列的第1个，再降低其优先级，插入到相应的队列中。C）ps 查看当前进程状态D）sleep 命令将进程挂起E）awake 命令唤醒1个被挂起的进程F

2、）kill 命令杀死进程G）quit命令退出（4）选用面向对象的编程方法。三、实验原理或算法本实验结合了进程状态转换、优先级调度、时间片轮转调度三方面的内容，根据进程状态转换图，设置SLEEP命令，将1个进程挂起，AWAKE命令唤醒1个被挂起的进程（从阻塞状态到就绪状态）。1) 优先级优先级体现了进程的重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。优先级从小到大（如 0-127） 优先级最高，127 最低。在本实验中按数值大小决定优先级，数值大的优先级高。2) 基于时间片调度将所有的就绪进程按照先来先服务的原则，排成一个队列，每次调度时，将 cpu 分配给队首进程，并令其

3、执行一个时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。在该实验中，时间片以 100ms 为单位（实际的要小得多）。在调度过程中，需要通过时间函数检测进程的执行时间，当该进程执行时间时间片大小时，进行调度。3) 高优先级调度优先级高的进程优先得到 cpu，等该进程执行完毕后，另外的进程才能执行。4) 基于时间片的高优先级调度在调度算法中，只有处于就绪状态的进程才能被调度，调度算法结合了优先级调度和时间片轮转调度算法，约定：从最高优先级队列取第1个就绪状态的进程进行调度，时间片到后降低其优先级（降低一半），然后插入到低优先级队列的尾部，每次调度后，显

4、示进程的状态。四、程序清单#include <stdlib.h>#include <stdio.h>#include <time.h>/#include <dos.h>#include <string.h>/定义进程数#define LEN 10/定义最高优先级 #define MAXPIOR 3/ 定义时间片#define QUANTUM 2#define PCB sizeof(struct pcb)struct pcb /PCBint ident;/标识符 int state;/状态 0-就绪，1运行，2堵塞 int pior;/

5、优先级,MAXPIOR为最高优先级*/ int life;/生命期*/ struct pcb *next;/*指针*/ *arrayMAXPIOR;static int idlistLEN;/*标识符表*/int life=0;/*总生命期初始化为0*/char str20;char command710;int killtest=0;void init();int create();void kill(int x);void process();void routine();void ps();void init() int i=0; for (i=0;i<MAXPIOR;i+) ar

6、rayi=NULL; sprintf(command0,"quit"); sprintf(command1,"ps"); sprintf(command2,"create"); sprintf(command3,"kill"); sprintf(command4,"round"); sprintf(command5,"sleep"); sprintf(command6,"awake");int create() int i=0,pior=0; struct

7、 pcb *p,*q,*s; while (idlisti!=0&&i<=LEN-1) i+; if (i=LEN) return -1; idlisti=1; srand(unsigned)time(NULL); pior=rand()%MAXPIOR; /最大优先级设定为02的整数 /printf("pior=%dn",pior); s=(struct pcb *)malloc(PCB);/create a node to keep the process messege s->ident=i; s->state=0; s->pi

8、or=pior; s->life=1+rand()%20;/进程有生命期假设为120 s->next=NULL; life=life+(s->life); p=arraypior;/建立同优先级队列（链表） if (p=NULL) arraypior=s; else while(p!=NULL) q=p; p=p->next; q->next=s; printf("success create process id=%d, current process state disp below:n",s->ident); ps(); /prin

9、tf("end displayn"); return 1;void ps()int i=0; struct pcb *p; for (i=0;i<MAXPIOR;i+) p=arrayi; while (p!=NULL) printf("id:%d,state:%d,pior:%d,life:%dn",p->ident,p->state,p->pior,p->life); p=p->next; void sleep(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL; wh

10、ile(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break; else q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p->state=2) printf("the

11、process %d has blocked,cannot sleep again!",p->ident); else p->state=2; ps();void awake(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL; while(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break; e

12、lse q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p->state=0) printf("the process %d is ready state,cannot awake again!",p->ident); else p->state=0; ps();void kill(int x)int i=0,test=0; struct pcb *p=NULL,*q=NULL

13、; while(test=0&&i!=MAXPIOR) p=arrayi; if (i!=MAXPIOR && p=NULL) i+;continue; while(p!=NULL) if (p->ident=x) test=1;killtest=1;break; else q=p;p=p->next; if (test=0) i+; /*找到X所在指针*/ if (i=MAXPIOR) printf("Invaild process number."); else if (p=arrayi) arrayi=arrayi->

14、next; idlistx=0; free(p); else q->next=p->next; idlistx=0; life=life-(p->life); free(p); void process()/对输入命令的处理int i=0,ii=0; for (i=0;i<7;i+) if (stricmp(str,commandi)=0) break; switch(i) case 0:printf("thank you for using the program!n");exit(0); break; case 1:ps(); break; ca

15、se 2:create(); break; case 3:printf("Which process you want to kill?n"); scanf("%d",&ii); kill(ii);break; case 4:routine();break;case 5:printf("Which process you want to sleep?n"); scanf("%d",&ii); sleep(ii);break;case 6:printf("Which process you

16、want to awake?n"); scanf("%d",&ii); awake(ii);break;default: printf("Error command.Please input create, ps, kill,sleep,awake,quitn"); void routine()/执行一次调度运行，将最高优先级队列的进程运行1个时间片，并降低其优先级 int i=MAXPIOR-1,pior=0,t; struct pcb *pp,*qq,*pr,*r; do while (i>=0 && arra

17、yi=NULL) i=i-; if (i<0) printf("NO process,please create it! n"); return ; pr=r=arrayi; while (r!=NULL && r->state!=0) pr=r;r=r->next; i-; while(r=NULL);/从高优先队列中寻找就绪进程以调度它 printf("The one in the hightest piror process will execute 1 quantum.n"); r->state=1; /进

18、程处于运行状态 printf("process id=%d is running.",r->ident); for (int k=1;k<600000;k+) for(int k1=1;k1<1000;k1+); /延时 printf("end,change to ready staten"); r->pior=(r->pior)/2; r->state=0; /进程处于就绪状态 if(r->life-QUANTUM>0) r->life=r->life-QUANTUM; /时间减少QUANTU

19、M life=life-QUANTUM; else life=life-r->life; r->life=0; if (r->life=0)/进程运行完成，KILL它 printf("the process %d is successful run,and release it!n",r->ident); kill(r->ident); else if (pr=r) /将r结点从原队列中删除 arrayi+1=r->next; else pr->next=r->next; t=r->pior; /将r进程加入到相应低优先级队列中的最后 pp=arrayt; qq=NU