C語言實現多級反饋隊列調度算法
#include <stdio.h>include <stdlib.h>
include <string.h>
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 < ReadyNum; 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 < num; 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);
}
} </pre>