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

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。以上为一次进程调度 循环。四.程序主要流程图:进程调度流程图实验源程序:#inelude #include #inelude type

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

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

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

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

8、p)pr i nt f(n%st%dt%dt%dt%dtt%ctt%dnM.p-name.p-pr i o,p-round,p-cputime,p -needtime,p-state,p-count)；p = p-next；print = print-next；p = finish；wh订e(p!=NULL)printf(，%st%dt%dt%dt%dtt%ctt%dn,p-name.p-prio,p-round p-cputimetp -needt ime,p-state,p-count)；p = p-next；p = run；wh订e(p!=NULL)(printf(，%st%dt%dt%

9、dt%dtt%ctt%dnM,p-name,p-pr i o,p-round,p-cputime,p -needt ime,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 -next = in；void InsertPrio(Ready

10、Queue *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 != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/nxt = fst；fst = fst-next；if(

11、fst -next = NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即 可*/in -next = fst 一next；fst -next = in；else/*插入到队列中*/nxt = in；in -next = fst；void PrioCreate() /创建就绪队列输入函数*/ReadyQueue *tmp；int i;printfC输入就绪队列的个数：n)；scanf(n%d,&ReadyNum);printf (输入每个就绪队列的CPU时间片：n)；for(i = 0；i round):/*输入此就绪队列中给每个进程所分配的CPU时间片*/tmp -prio

12、= 50 - tmp-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 = queue -LinkPCB -next；run -next = N

13、ULL；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 -next = fst -next；fst -next = in；void ProcessCreate () /水进程创建函数*/PCB *tmp；int i:printfC输入进程的

14、个数:n);scanf(M%d&num)；printfC输入进程名字和进程所需时间:n)；for(i = 0；i name)；getcharO ；/*吸收回车符号*/scanf (%d.&(tmp-needtime)；tmp -cputime = 0；tmp -state =1W * ；tmp -prio = 50 - tmp-needtime； /*设置其优先级，需要的时间越多，优先级越低*/tmp -round = Head 一)round；tmp -count = 0；InsertLast (tmp, Head) ；/*按照优先级从高到低，插入到就绪队列*/vo id RoundRun

15、(ReadyQueue *t imech i p)/*时间片轮转调度算法*/int flag = 1;GetFirst(timechip)；wh订e(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)/*时间片用完*/run-state = W；run-count = 0；/*计数器清零，为下次做准备*/Insert

16、Last(run,timechip)；flag = 0；flag = 1;GetFirst(timechip):void MultiDispatchO/*多级调度算法，每次执行一个时间片*/int flag = 1;int k = 0；ReadyQueue *point；point = Head；GetFirst(point)；wh订e(run != NULL)Output()；if(Head -LinkPCB!二NULL)point = Head:while(flag)run-count+；run-cputime+；run-needtime；if (run-needt ime = 0) /*

17、进程执行完毕*/run -state = F；InsertFinish(run)；flag = 0；else if(run-count = run-round)/*时间片用完*/run-state = * Wf；run-count = 0；/*计数器清零，为下次做准备*/if(point -next!二NULL)run -round = point-next -round； /设置其时间片是下一个就绪队列的时间片*/InsertLast (run, point-next) ； /*将进程插入到下一个就绪队列中*/flag = 0；elseRoundRun (point)；/*如果为最后一个就绪队列就调用时间片轮转算法*/break；+k；if(k = 3)ProcessCreateO ；flag = 1;if(point -LinkPCB = NULL)/*就绪队列指针下移*/point =point-next；if(point -next =NULL)RoundRun(point)；break；GetFirst(point)；五、实验中遇到的问題和实验中的重点1使用C+对于多级反馈模拟过程进行描述，需要对计数器 KillTimer()；ONTIMER();进行设计。通过在计数器中对函数run()设计并在 ONTIMER(