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

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，则重新把它变为就绪状态，插入就绪对列中；否则该进程执行完成，撤销其PCB。以上为一次进程调度循环。四、程序主要流程图：实验源程序：#include #include #include typedef struct

4、 node /*进程节点信息*/ char name20; /*进程的名字*/ int prio; /*进程的优先级*/ int round; /*分配CPU的时间片*/ int cputime; /*CPU执行时间*/ int needtime; /*进程执行所需要的时间*/ char state; /*进程的状态，W就绪态，R执行态，F完成态*/ int count; /*记录执行的次数*/ struct node *next; /*链表指针*/ PCB; typedef struct Queue /*多级就绪队列节点信息*/ PCB *LinkPCB; /*就绪队列中的进程队列指针*/

5、int prio; /*本就绪队列的优先级*/ int round; /*本就绪队列所分配的时间片*/ struct Queue *next; /*指向下一个就绪队列的链表指针*/ ReadyQueue; PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/ ReadyQueue *Head = NULL; /*定义第一个就绪队列*/ int num; /*进程个数*/ int ReadyNum; /*就绪队列个数*/ void Output(); /*进程信息输出函数*/ void InsertFinish(PCB *in); /*将进程

6、插入到完成队列尾部*/ void InsertPrio(ReadyQueue *in); /*创建就绪队列，规定优先数越小，优先级越低*/ void PrioCreate(); /*创建就绪队列输入函数*/ void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/ void ProcessCreate(); /*进程创建函数*/ void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法

7、*/ void MultiDispatch(); /*多级调度算法，每次执行一个时间片*/ int main(void) PrioCreate(); /*创建就绪队列*/ ProcessCreate();/*创建就绪进程队列*/ MultiDispatch();/*算法开始*/ Output(); /*输出最终的调度序列*/ return 0; void Output() /*进程信息输出函数*/ ReadyQueue *print = Head; PCB *p; printf(进程名t优先级t轮数tcpu时间t需要时间t进程状态t计数器n); while(print) if(print -L

8、inkPCB != 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-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

9、= run; 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; void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/ PCB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else while(fst-next != NULL) fst = fst-next; in -next = f

10、st -next; fst -next = 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; else while(fst-next !=

11、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); scanf(%d,&ReadyNum); printf(输入

12、每个就绪队列的CPU时间片：n); for(i = 0;i round); /*输入此就绪队列中给每个进程所分配的CPU时间片*/ tmp -prio = 50 - tmp-round; /*设置其优先级，时间片越高，其优先级越低*/ tmp -LinkPCB = NULL; /*初始化其连接的进程队列为空*/ tmp -next = NULL; InsertPrio(tmp); /*按照优先级从高到低，建立多个就绪队列*/ void GetFirst(ReadyQueue *queue) /*取得某一个就绪队列中的队头进程*/ run = queue -LinkPCB; if(queue -

13、LinkPCB != NULL) run -state = R; queue -LinkPCB = queue -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; else while(fst-next != NULL) fst = fst-next; in

14、-next = fst -next; fst -next = in; void ProcessCreate() /*进程创建函数*/ PCB *tmp; int i; printf(输入进程的个数：n); scanf(%d,&num); printf(输入进程名字和进程所需时间：n); for(i = 0;i name); getchar(); /*吸收回车符号*/ scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; /*设置其优先级，需要的时间越多，优先级越低*/

15、tmp -round = Head -round; tmp -count = 0; InsertLast(tmp,Head); /*按照优先级从高到低，插入到就绪队列*/ void RoundRun(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; InsertFini

16、sh(run); flag = 0; else if(run-count = timechip -round)/*时间片用完*/ 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

17、(run != NULL) Output(); if(Head -LinkPCB!=NULL) 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)

18、 run -round = point-next -round;/*设置其时间片是下一个就绪队列的时间片*/ InsertLast(run,point-next); /*将进程插入到下一个就绪队列中*/ flag = 0; else RoundRun(point); /*如果为最后一个就绪队列就调用时间片轮转算法*/ break; +k; if(k = 3) ProcessCreate(); flag = 1; if(point -LinkPCB = NULL)/*就绪队列指针下移*/ point =point-next; if(point -next =NULL) RoundRun(point); break; GetFirst(point); 五、实验中遇到的问题和实验中的重点1.使用C+对于多级反馈模拟过程进行描述，需要对计数器KillTimer();ONTIMER();进行设计。通过在计数器中对函数run(