多级反馈队列调度算法_C语言模拟实现

多级反馈队列调度算法 C语言模拟实现 收藏

多级反馈队列调度算法：

1、设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。

2、赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。

3、当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片

结束时尚未完成，将其转入第二队列末尾。

4、当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。

5、仅当时间片空闲时，才调度第二个队列中的进程。

(1~i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高 队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。 view plaincopy to clipboardprint?

#include

#include

#include

typedef struct node /*进程节点信息*/

{

char name[20]; /*进程的名字*/

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; /*就绪队列中的进程队列指针*/

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); /*将进程插入到完成队列尾部*/

void InsertPrio(ReadyQueue *in); /*创建就绪队列，规定优先数越小，优先级越低*/ void PrioCreate(); /*创建就绪队列输入函数*/

void GetFirst(ReadyQueue *queue); /*取得某一个就绪队列中的队头进程*/

void InsertLast(PCB *in,ReadyQueue *queue); /*将进程插入到就绪队列尾部*/

void ProcessCreate(); /*进程创建函数*/

void RoundRun(ReadyQueue *timechip); /*时间片轮转调度算法*/

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 ->LinkPCB != NULL)

{

p=print ->LinkPCB;

while(p)

{

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);

p = p->next;

}

}

print = print->next;

}

p = finish;

while(p!=NULL)

{

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);

p = p->next;

}

p = run;

while(p!=NULL)

{

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);

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 = fst ->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 != 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("输入每个就绪队列的CPU时间片：\n");

for(i = 0;i

{

if((tmp = (ReadyQueue *)malloc(sizeof(ReadyQueue)))==NULL)

{

perror("malloc");

exit(1);

}

scanf("%d",&(tmp->round)); /*输入此就绪队列中给每个进程所分配的CPU时间片*/ tmp ->prio = 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 = 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 ->next = fst ->next;

fst ->next = in;

}

}

void ProcessCreate() /*进程创建函数*/

{

PCB *tmp;

int i;

printf("输入进程的个数：\n");

scanf("%d",&num);

printf("输入进程名字和进程所需时间：\n");

for(i = 0;i

{

if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)

{

perror("malloc");

exit(1);

}

scanf("%s",tmp->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 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';

InsertFinish(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(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(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);

}

}

本文来自CSDN博客，转载请标http://blog.csdn.net/eaglewood2005/archive/2009/07/24/4377875.aspx 出处明：