学步园

多级反馈队列调度算法：
1、设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。
2、赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。
3、当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片
结束时尚未完成，将其转入第二队列末尾。
4、当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。
5、仅当时间片空闲时，才调度第二个队列中的进程。
(1~i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高
队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。
#include <stdio.h><br /> #include <stdlib.h><br /> #include <string.h><br /> typedef struct node /*进程节点信息*/<br /> {<br /> char name[20]; /*进程的名字*/<br /> int prio; /*进程的优先级*/<br /> int round; /*分配CPU的时间片*/<br /> int cputime; /*CPU执行时间*/<br /> int needtime; /*进程执行所需要的时间*/<br /> char state; /*进程的状态，W——就绪态，R——执行态，F——完成态*/<br /> int count; /*记录执行的次数*/<br /> struct node *next; /*链表指针*/<br /> }PCB;<br /> typedef struct Queue /*多级就绪队列节点信息*/<br /> {<br /> PCB *LinkPCB; /*就绪队列中的进程队列指针*/<br /> int prio; /*本就绪队列的优先级*/<br /> int round; /*本就绪队列所分配的时间片*/<br /> struct Queue *next; /*指向下一个就绪队列的链表指针*/<br /> }ReadyQueue;<br /> PCB *run=NULL,*finish=NULL; /*定义三个队列，就绪队列，执行队列和完成队列*/<br /> ReadyQueue *Head = NULL; /*定义第一个就绪队列*/<br /> int num; /*进程个数*/<br /> int ReadyNum; /*就绪队列个数*/<br /> void Output(); /*进程信息输出函数*/<br /> void InsertFinish(PCB *in); /*将进程插入到完成队列尾部*/<br /> void InsertPrio(ReadyQueue *in); /*创建就绪队列，规定优先数越小，优先级越低*/<br /> void PrioCreate(); /*创建就绪队列输入函数*/<br /> void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/<br /> void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/<br /> void ProcessCreate(); /*进程创建函数*/<br /> void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/<br /> void MultiDispatch(); /*多级调度算法，每次执行一个时间片*/</p> <p>int main(void)<br /> {<br /> PrioCreate(); /*创建就绪队列*/<br /> ProcessCreate();/*创建就绪进程队列*/<br /> MultiDispatch();/*算法开始*/<br /> Output(); /*输出最终的调度序列*/<br /> return 0;<br /> }<br /> void Output() /*进程信息输出函数*/<br /> {<br /> ReadyQueue *print = Head;<br /> PCB *p;<br /> printf("进程名/t优先级/t轮数/tcpu时间/t需要时间/t进程状态/t计数器/n");<br /> while(print)<br /> {<br /> if(print ->LinkPCB != NULL)<br /> {<br /> p=print ->LinkPCB;<br /> while(p)<br /> {<br /> printf("%s/t%d/t%d/t%d/t%d/t/t%c/t/t%d/n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);<br /> p = p->next;<br /> }<br /> }<br /> print = print->next;<br /> }<br /> p = finish;<br /> while(p!=NULL)<br /> {<br /> printf("%s/t%d/t%d/t%d/t%d/t/t%c/t/t%d/n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);<br /> p = p->next;<br /> }<br /> p = run;<br /> while(p!=NULL)<br /> {<br /> printf("%s/t%d/t%d/t%d/t%d/t/t%c/t/t%d/n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);<br /> p = p->next;<br /> }</p> <p>}<br /> void InsertFinish(PCB *in) /*将进程插入到完成队列尾部*/<br /> {<br /> PCB *fst;<br /> fst = finish;</p> <p>if(finish == NULL)<br /> {<br /> in->next = finish;<br /> finish = in;<br /> }<br /> else<br /> {<br /> while(fst->next != NULL)<br /> {<br /> fst = fst->next;<br /> }<br /> in ->next = fst ->next;<br /> fst ->next = in;<br /> }<br /> }<br /> void InsertPrio(ReadyQueue *in) /*创建就绪队列，规定优先数越小，优先级越低*/<br /> {<br /> ReadyQueue *fst,*nxt;<br /> fst = nxt = Head;</p> <p>if(Head == NULL) /*如果没有队列，则为第一个元素*/<br /> {<br /> in->next = Head;<br /> Head = in;<br /> }<br /> else /*查到合适的位置进行插入*/<br /> {<br /> if(in ->prio >= fst ->prio) /*比第一个还要大，则插入到队头*/<br /> {<br /> in->next = Head;<br /> Head = in;<br /> }<br /> else<br /> {<br /> while(fst->next != NULL) /*移动指针查找第一个别它小的元素的位置进行插入*/<br /> {<br /> nxt = fst;<br /> fst = fst->next;<br /> }</p> <p> if(fst ->next == NULL) /*已经搜索到队尾，则其优先级数最小，将其插入到队尾即可*/<br /> {<br /> in ->next = fst ->next;<br /> fst ->next = in;<br /> }<br /> else /*插入到队列中*/<br /> {<br /> nxt = in;<br /> in ->next = fst;<br /> }<br /> }<br /> }<br /> }<br /> void PrioCreate() /*创建就绪队列输入函数*/<br /> {<br /> ReadyQueue *tmp;<br /> int i;</p> <p>printf("输入就绪队列的个数：/n");<br /> scanf("%d",&ReadyNum);</p> <p>printf("输入每个就绪队列的CPU时间片：/n");<br /> for(i = 0;i < ReadyNum; i++)<br /> {<br /> if((tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)))==NULL)<br /> {<br /> perror("malloc");<br /> exit(1);<br /> }<br /> scanf("%d",&(tmp->round)); /*输入此就绪队列中给每个进程所分配的CPU时间片*/<br /> tmp ->prio = 50 - tmp->round; /*设置其优先级，时间片越高，其优先级越低*/<br /> tmp ->LinkPCB = NULL; /*初始化其连接的进程队列为空*/<br /> tmp ->next = NULL;<br /> InsertPrio(tmp); /*按照优先级从高到低，建立多个就绪队列*/<br /> }<br /> }<br /> void GetFirst(ReadyQueue *queue) /*取得某一个就绪队列中的队头进程*/<br /> {<br /> run = queue ->LinkPCB;</p> <p>if(queue ->LinkPCB != NULL)<br /> {<br /> run ->state = 'R';<br /> queue ->LinkPCB = queue ->LinkPCB ->next;<br /> run ->next = NULL;<br /> }<br /> }<br /> void InsertLast(PCB *in,ReadyQueue *queue) /*将进程插入到就绪队列尾部*/<br /> {<br /> PCB *fst;<br /> fst = queue->LinkPCB;</p> <p>if( queue->LinkPCB == NULL)<br /> {<br /> in->next = queue->LinkPCB;<br /> queue->LinkPCB = in;<br /> }<br /> else<br /> {<br /> while(fst->next != NULL)<br /> {<br /> fst = fst->next;<br /> }<br /> in ->next = fst ->next;<br /> fst ->next = in;<br /> }<br /> }<br /> void ProcessCreate() /*进程创建函数*/<br /> {<br /> PCB *tmp;<br /> int i;</p> <p>printf("输入进程的个数：/n");<br /> scanf("%d",&num);<br /> printf("输入进程名字和进程所需时间：/n");<br /> for(i = 0;i < num; i++)<br /> {<br /> if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)<br /> {<br /> perror("malloc");<br /> exit(1);<br /> }<br /> scanf("%s",tmp->name);<br /> getchar(); /*吸收回车符号*/<br /> scanf("%d",&(tmp->needtime));<br /> tmp ->cputime = 0;<br /> tmp ->state ='W';<br /> tmp ->prio = 50 - tmp->needtime; /*设置其优先级，需要的时间越多，优先级越低*/<br /> tmp ->round = Head ->round;<br /> tmp ->count = 0;<br /> InsertLast(tmp,Head); /*按照优先级从高到低，插入到就绪队列*/<br /> }<br /> }<br /> void RoundRun(ReadyQueue *timechip) /*时间片轮转调度算法*/<br /> {</p> <p>int flag = 1;</p> <p>GetFirst(timechip);<br /> while(run != NULL)<br /> {<br /> while(flag)<br /> {<br /> run->count++;<br /> run->cputime++;<br /> run->needtime--;<br /> if(run->needtime == 0) /*进程执行完毕*/<br /> {<br /> run ->state = 'F';<br /> InsertFinish(run);<br /> flag = 0;<br /> }<br /> else if(run->count == timechip ->round)/*时间片用完*/<br /> {<br /> run->state = 'W';<br /> run->count = 0; /*计数器清零，为下次做准备*/<br /> InsertLast(run,timechip);<br /> flag = 0;<br /> }<br /> }<br /> flag = 1;<br /> GetFirst(timechip);<br /> }<br /> }<br /> void MultiDispatch() /*多级调度算法，每次执行一个时间片*/<br /> {<br /> int flag = 1;<br /> int k = 0;</p> <p>ReadyQueue *point;<br /> point = Head;</p> <p>GetFirst(point);<br /> while(run != NULL)<br /> {<br /> Output();<br /> if(Head ->LinkPCB!=NULL)<br /> point = Head;<br /> while(flag)<br /> {<br /> run->count++;<br /> run->cputime++;<br /> run->needtime--;<br /> if(run->needtime == 0) /*进程执行完毕*/<br /> {<br /> run ->state = 'F';<br /> InsertFinish(run);<br /> flag = 0;<br /> }<br /> else if(run->count == run->round)/*时间片用完*/<br /> {<br /> run->state = 'W';<br /> run->count = 0; /*计数器清零，为下次做准备*/<br /> if(point ->next!=NULL)<br /> {<br /> run ->round = point->next ->round;/*设置其时间片是下一个就绪队列的时间片*/<br /> InsertLast(run,point->next); /*将进程插入到下一个就绪队列中*/<br /> flag = 0;<br /> }<br /> else<br /> {<br /> RoundRun(point); /*如果为最后一个就绪队列就调用时间片轮转算法*/<br /> break;<br /> }<br /> }<br /> ++k;<br /> if(k == 3)<br /> {<br /> ProcessCreate();<br /> }<br /> }<br /> flag = 1;<br /> if(point ->LinkPCB == NULL)/*就绪队列指针下移*/<br /> point =point->next;<br /> if(point ->next ==NULL)<br /> {<br /> RoundRun(point);<br /> break;<br /> }<br /> GetFirst(point);<br /> }<br /> }