多级反馈队列-实验-操作系统

1、实验名称：多级反应队列调度09091201 丁奎荣一、实验目的：1、综合应用以下知识点设计并实现操作系统的进程调度，进程状态转换，多组 级反应队列进程调度算法。2、加深理解操作系统进程调度的过程。3、加深理解多级反应队列进程调度算法。二、实验内容：1、 采用一种熟悉的语言，编制程序，最好采用C/C+，界面设计可采用其它自 己喜欢的语言。2、采用多级反应队列进程调度算法进行进程调度。3、每个进程对应一个PCB。在PCB中包括进程标识符pid、进程的状态标志status 进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life在 实际系统中不包括该项 。4、 创立进程时

2、即创立一个 PCB，各个进程的pid都是唯一的，pid时在1到100 范围的一个整数。可以创立一个下标为 1 到 100的布尔数组，“真表示下标对 应的进程号是空闲的， “假表示下标对应的进程号已分配给某个进程。5、进程状态status的取值为“就绪ready或“运行run，刚创立时，状态为“ready。 被进程调度程序选中后变为“ run。6、进程优先级 priority 是 0 到 49 范围内的一个随机整数。7、生命周期 life 是 1 到 5 范围内的一个随机整数。8、初始化时，创立一个邻接表，包含 50各就绪队列，各就绪队列的进程优先级 priority 分别是 0 到 49。9、

3、为了模拟用户动态提交任务的过程，要求动态创立进程。进入进程调度循环 后，每次按 ctrl+f 即动态创立一个过程， 然后将该 PCB 插入就绪队列中。 按 ctrl+q 退出进程调度循环。10、在进程调度循环中， 每次选择优先级最大的就绪进程来执行。 将其状态从就 绪变为运行， 通过延时一段时间来模拟该进程执行一个时间片的过程， 然后优先 级减半，生命周期减一。设计图形用户界面GUI，在窗口中显示该进程和其他所有进程的PCB内容。如果将该运行进程的生命周期不为 0,那么重新把它变为就 绪状态，插入就绪对列中；否那么该进程执行完成，撤销其 PCBo以上为一次进程调度循环四、程序主要流程图:进程调

4、度流程图实验源程序:#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <stri ng.h>typedef struct node/* 进程节点信息 */char name20; /* 进程的名字 */int prio; /* 进程的优先级 */int round;/* 分配 CPU 的时间片 */int cputime; /*CPU 执行时间 */int needtime; /* 进程执行所需要的时间 */char state;/*进程的状态，W 就绪态，R执行态，F完成态*/int count; /* 记录

5、执行的次数 */struct node *next; /* 链表指针 */PCB;typedef struct Queue /* 多级就绪队列节点信息 */PCB *LinkPCB; /*就绪队列中的进程队列指针 */int prio; /* 本就绪队列的优先级 */int round; /* 本就绪队列所分配的时间片 */struct Queue *next;/* 指向下一个就绪队列的链表指针*/ReadyQueue;PCB *run=NULL,*finish=NULL; /* 定义三个队列，就绪队列，执行队列和完成队列 */ReadyQueue *Head = NULL; /* 定义第一个

6、就绪队列 */int num; /* 进程个数 */int ReadyNum; /* 就绪队列个数 */void Output();/*进程信息输出函数 */void InsertFinish(PCB *in);/*将进程插入到完成队列尾部 */void InsertPrio(ReadyQueue *in);/* 创立就绪队列，规定优先数越小，优先级越低 */void PrioCreate();/* 创立就绪队列输入函数 */void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程 */void InsertLast(PCB *in,ReadyQu

7、eue *queue); /* 将进程插入到就绪队列尾部 */void ProcessCreate();/* 进程创立函数 */void RoundRun(ReadyQueue *timechip); /* 时间片轮转调度算法 */void MultiDispatch();/*多级调度算法，每次执行一个时间片*/int main(void)PrioCreate(); /* 创立就绪队列 */ProcessCreate();/*创立就绪进程队列*/MultiDispatch();/* 算法开始 */Output(); /*输出最终的调度序列 */return 0;void Output() /*

8、进程信息输出函数 */ReadyQueue *print = Head;PCB *p;printf(" 进程名 t 优先级 t 轮数 tcpu 时间 t 需要时间 t 进程状态 t 计数器 n");while(print)if(print ->LinkPCB != NULL)p=print ->LinkPCB;while(p)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime, p->state,p

9、->count);p = p->next;print = print->next;p = finish;while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime, p->state,p->count);p = p->next;p = run;while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p-

10、>prio,p->round,p->cputime,p->needtime, p->state,p->count);p = p->next;void InsertFinish(PCB *in) /* 将进程插入到完成队列尾部 */ PCB *fst;fst = finish;if(finish = NULL)in->next = finish;finish = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst ->next;fst ->nex

11、t = in;void InsertPrio(ReadyQueue *in) /* 创立就绪队列，规定优先数越小，优先级越低 */ReadyQueue *fst,*nxt;fst = nxt = Head;if(Head = NULL)/*如果没有队列，那么为第一个元素 */in->next = Head;Head = in;else /* 查到适宜的位置进行插入 */if(in ->prio >= fst ->prio)/* 比第一个还要大，那么插入到队头 */in->next = Head;Head = in;elsewhile(fst->next !=

12、 NULL) /* 移动指针查找第一个别它小的元素的位置进行插入 */ nxt = fst; fst = fst->next;if(fst ->next = NULL)/* 已经搜索到队尾，那么其优先级数最小，将其插入到队尾即可 */in ->next = fst ->next;fst ->next = in;else/* 插入到队列中 */nxt = in; in ->next = fst;void PrioCreate() /* 创立就绪队列输入函数 */ReadyQueue *tmp;int i;printf(" 输入就绪队列的个数： n&q

13、uot;); scanf("%d",&ReadyNum);printf(" 输入每个就绪队列的 CPU 时间片： n");for(i = 0;i < ReadyNum; i+)if(tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)=NULL)perror("malloc");exit(1);scanf("%d",&(tmp->round); /* 输入此就绪队列中给每个进程所分配的CPU 时间片 */tmp ->prio = 50 - tm

14、p->round; /* 设置其优先级，时间片越高，其优先级越低*/tmp ->LinkPCB = NULL; /*初始化其连接的进程队列为空 */ tmp ->next = NULL;InsertPrio(tmp);/* 按照优先级从高到低，建立多个就绪队列*/void GetFirst(ReadyQueue *queue)/* 取得某一个就绪队列中的队头进程 */run = queue ->LinkPCB;if(queue ->LinkPCB != NULL)run ->state = 'R'queue ->LinkPCB = qu

15、eue ->LinkPCB ->next;run ->next = NULL;void InsertLast(PCB *in,ReadyQueue *queue) /* 将进程插入到就绪队列尾部 */PCB *fst;fst = queue->LinkPCB;if( queue->LinkPCB = NULL) in->next = queue->LinkPCB; queue->LinkPCB = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst -&g

16、t;next;fst ->next = in;void ProcessCreate() /* 进程创立函数 */PCB *tmp;int i;printf(" 输入进程的个数： n");scanf("%d",&num);printf(" 输入进程名字和进程所需时间： n"); for(i = 0;i < num; i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);scanf("%s",tmp

17、->name);getchar();/* 吸收回车符号 */scanf("%d",&(tmp->needtime);tmp ->cputime = 0;tmp ->state ='W'tmp ->prio = 50 - tmp->needtime; /* 设置其优先级，需要的时间越多，优先级越低 */ tmp ->round = Head ->round;tmp ->count = 0;InsertLast(tmp,Head);/* 按照优先级从高到低，插入到就绪队列 */void RoundRu

18、n(ReadyQueue *timechip)/* 时间片轮转调度算法 */int flag = 1;GetFirst(timechip); while(run != NULL) while(flag) run->count+; run->cputime+; run->needtime-; if(run->needtime = 0) /* 进程执行完毕 */ run ->state = 'F' InsertFinish(run); flag = 0;else if(run->count = timechip ->round)/* 时间片

19、用完 */run->state = 'W'run->count = 0; /* 计数器清零，为下次做准备 */ InsertLast(run,timechip);flag = 0;flag = 1;GetFirst(timechip);void MultiDispatch() /* 多级调度算法，每次执行一个时间片 */ int flag = 1;int k = 0;ReadyQueue *point; point = Head;GetFirst(point);while(run != NULL) Output();if(Head ->LinkPCB!=NUL

20、L)point = Head;while(flag) run->count+; run->cputime+;run->needtime-;if(run->needtime = 0) /* 进程执行完毕 */run ->state = 'F'InsertFinish(run);flag = 0;else if(run->count = run->round)/* 时间片用完 */run->state = 'W'run->count = 0; /* 计数器清零，为下次做准备 */if(point ->next!=NULL)run ->round = point->next ->round;/* 设置其时间片是下一个就绪队列的时间片 */ InsertLast(run,point-&