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

1、实验名称：多级反馈队列调度 09091201 丁奎荣一、实验目的：1、综合应用下列知识点设计并实现操作系统的进程调度，进程状态转换，多组 级反馈队列进程调度算法。2、加深理解操作系统进程调度的过程。3、加深理解多级反馈队列进程调度算法。二、实验容：1、采用一种熟悉的语言，编制程序，最好采用C/C+,界面设计可采用其它自 己喜欢的语言。2、采用多级反馈队列进程调度算法进行进程调度。3、每个进程对应一个PCBo在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 <stdio.h

4、>#include <stdlib. h>Jtinclude <string. h>typedef struct node/*进程节点信息*/char name 20 ；/*进程的名字*/int prio；/*进程的优先级*/int round；/*分配CPU的时间片*/int cputime； /*CPU 执行时间*/int needt ime；/*进程执行所需要的时怅*/char state； /*进程的状态，W就绪态，R执行态，F完成态*/int count；/*记录执行的次数*/struct node *next； /*锥表指针*/PCB；typedef

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

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

7、undRun(ReadyQueue *timechip) ；/*时间片轮转调度算法*/void MultiDispatchO；/*多级调度算法，每次执行一个时间片*/int main(void) (PrioCreate() ； /*创建就绪队列*/ProcessCreate (); /*创建就绪进程队列/MultiDispatch () ;/*算法开始*/Output ()； /*输出最终的调度序列*/return 0；)void Output() /*进程信息输出函数*/ (ReadyQueue *print = Head；PCB *p；printf ("进程名t优先级t轮数tcp

8、u时间t需要时间t进程状态t计数器n"):while(print) (if(print ->LinkPCB != NULL) (p=print ->LinkPCB； while(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； while(p!=NULL) (

9、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； while(p!=NULL) (printf(，'%st%dt%dt%dt%dtt%ctt%dnM,p->name,p->pr i o,p->round,p->cputime,p ->needt ime,p->state,p->count)；

10、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(ReadyQueue *in) /*创建就绪队列,规定优先数越小，优先级越低*/(Rea

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

12、； if(fst ->next = NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即 可*/(in ->next = fst 一next；fst ->next = in；else/*插入到队列中*/nxtinin ->next = fst；)void PrioCreate() /*创建就绪队列输入函数*/(ReadyQueue *tmp；int i；printf("输入就绪队列的个数：n")；scanf("%d",&ReadyNum)；printf ("输入每个就绪队列的CPU时间片：n&quo

13、t;);for(i = 0；i < ReadyNum； i+)(if(tmp = (ReadyQueue *)mal1oc(sizeof(ReadyQueue)=NULL)(perror(malloc")；exit (1)；scanf (-%d&(tmp->round): /*输入此就绪队列中给每个进程所分配的CPU时间片*/ tmp ->prio = 50 - tmp->round； /*设置其优先级，时间片越高，其优先级越低*/ tmp ->LinkPCB = NULL； /*初始化其连接的进程队列为空*/tmp ->next = NU

14、LL；InsertPrio(tmp)； /*按照优先级从高到低，建立多个就绪队列*/)void GetFirst (ReadyQueue *queue)/*取得某一个就绪队列中的队头进程*/(run = queue ->LinkPCB；if (queue ->LinkPCB != NULL)(run ->state = 'R'；queue ->LinkPCB = queue ->LinkPCB ->next；run ->next = NULL；)void InsertLast (PCB *in. ReadyQueue *queue) /

15、*将进程插入到就绪队列尾部*/(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 ；printf(&q

16、uot;输入进程的个数：n)；scanf(M%d".&num)；printf ("输入进程名字和进程所需时间:n")；for(i = 0；i < num； i+)(if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)(perror(malloc*)；exit (1)；scanf (飞s”, tmp->name)；getcharO ；/*吸收回车符号*/scanf ("%d”,&(tmp->needtime)；tmp ->cputime = 0；tmp ->state =1W * ；

17、tmp ->prio = 50 - tmp->needtime； /*设置其优先级，需要的时间越多，优先级越低*/ tmp ->round = Head 一round；tmp ->count = 0；InsertLast (tmp, Head) ；/*按照优先级从高到低9插入到就绪队列*/)vo id RoundRun (ReadyQueue *t imech i p)/*时间片轮转调度算法*/int flag = 1；GetFirst(timechip)；while (run != NULL)(while(flag)(run->count+；run->cp

18、utime+；run->needtime-；if(run->needtime = 0) /*进程执行完毕*/ (run ->state = 'F'；InsertFinish(run)；flag = 0； else if (run->count = timechip ->round)/*时间片用完*/ (run->state = +'；run->count = 0；/*计数器清零，为下次做准备*/InsertLast(run,timechip)；flag = 0； flag = 1；GetFirst(timechip)；)void

19、 MultiDispatchO/*多级调度算法,每次执行一个时间片*/(int flag = 1；int k = 0；ReadyQueue *point；point = Head；GetFirst(point)；while (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)(run ->round = point->next ->round；/*设置其时间片是下一个就绪队列的时间片*/ InsertLast (r