网络操作系统课程设计之多级反馈队列算法

typedef struct pcb{ int id;//进程号 int intime;//提交时间 int priority;//优先级 int starttime;//开始执行时间 int length;//进程长度大小 int endtime;//结束时间 char state;//状态 int ptime;//时间片 struct pcb *next; }*PCB,pcb;//进程控制块

PCB CreatReady(PCB R,int i){ R=(PCB)malloc(sizeof(pcb)); R->id=i+1; R->priority=5-i; R->ptime=i+1; R->state='R'; R->next=NULL; printf(\"第%d级：\%d\%d\\n\ return R; }

PCB CreatWait(PCB W){ int i; pcb *p,*q; q=W; printf(\"给进程初始化如下(tab键隔开)：\\n\"); printf(\"进程\in时间\优先级\长度\\n\"); for(i=0;inext=NULL; p->id=i+1; printf(\"P%d\\ scanf(\"%d\%d\%d\ q->next=p; q=p; } return W;

}

void Insert(PCB R,pcb *cp){ pcb *tail; tail=R; while(tail->next){ tail=tail->next; } tail->next=cp; cp->next=NULL; }

int FindQuery(PCB R[M]){ int i,j; for(i=0;inext){ j=i;break; } else printf(\"第%d级就绪队列为空\\n\ } return j; }

int Dispatch(PCB R,pcb *cp,PCB W,int time,pcb *tp){ int s; pcb *p,*phead; phead=W; p=W->next; cp->starttime=time; cp->length-=R->ptime; cp->endtime=cp->starttime+R->ptime; if(cp->length<=0){ s=1;//表示完成 cp->endtime+=cp->length;//当进程在时间片内就完成，则应减去cp-length多减的部分 } else{ if(p){ while(p){ if((p->intimeendtime)&&(p->priority>cp->priority)){ tp->id=p->id; tp->intime=p->intime; tp->length=p->length;

tp->priority=p->priority; tp->state=p->state; //将抢占进程p备份到tp中 phead->next=p->next;//从后备队列中删除抢占的进程 cp->length +=cp->endtime-tp->intime; cp->endtime-=cp->endtime-tp->intime; s=-1;//表示被抢占 break; } else if(p->intime>=cp->endtime){ s=0;//在后备队列中没有可以抢占的进程时 break; } p=p->next;phead=phead->next; }//查找可以抢占cpu的优先级高的进程tp } else s=0;//在后备队列没有进程时 } return s; }

void Print(PCB F){ pcb *p; p=F->next; while(p){ printf(\"P%d\结束时间：%d\\n\ p=p->next; } }

PCB MFQ(PCB W,PCB R[M],PCB F){ pcb *cp;//当前系统操作的进程 pcb *tp;//抢占cpu的进程 tp=(PCB)malloc(sizeof(pcb)); tp->priority=0; tp->next=NULL; int time=0;//time表示系统当前时间 int Finish=0; int i,have,j;//i表示就绪队列的级数，time表示系统当前时间，have表示有进程提交， int s;//s表示cpu执行进程调度的三种结果状态,0表示时间片耗尽进入下级队列，1表示进程完成，-1表示进程被抢占 while(Finishcp=W->next; if(cp&&cp->intime<=time){ have=1; } else have=0; //判断当前时刻有无进程被提交 if(have){ i=0; W->next=cp->next;//从后备队列中删除cp Insert(R[0],cp); cp->priority=R[0]->priority; cp->state=R[0]->state; cp=R[0]->next; printf(\"%d时,P%d被提交入就绪队列%d\\n\ }//将新进程入第一级就绪队列 else{ i=FindQuery(R);//循环查找不为空的就绪队列 cp=R[i]->next; printf(\"%d时,无可以提交的进程，因此转到就绪队列%d执行P%d\\n\ } s=Dispatch(R[i],cp,W,time,tp);//cpu执行进程，并生成三种结果 if(s==1){ R[i]->next=cp->next;//从就绪队列中删除已完成的进程 Insert(F,cp); Finish++; printf(\"%d时，P%d处理完成！\\n\ } if(s==0){ if(i<2) j=i+1; else j=i; R[i]->next=cp->next;//从就绪队列中删除时间片耗尽的进程 Insert(R[j],cp); cp->priority=R[j]->priority; printf(\"%d时，P%d因时间片耗尽进入下一级就绪队列%d！\\n\ } if(s==-1){ R[i]->next=cp->next; Insert(R[i],cp); tp->next=R[0]->next;R[0]->next=tp; tp->priority=R[0]->priority;tp->state=R[0]->state; //将抢占cpu的进程进入第一级就绪队列并首先执行

printf(\"%d时，P%d被P%d抢占cpu并转入就绪队列%d队尾！\\n\ } time=cp->endtime; } return F; }

void main (){ PCB W;//后备队列 PCB R[M];//就绪队列 PCB F;//完成队列 int i; printf(\"就绪队\优先级\时间片\\n\"); for(i=0;istate='W'; W->next=NULL; W=CreatWait(W); //创建后备队列 F=(PCB)malloc(sizeof(pcb)); F->state='F'; F->next=NULL;//创建完成队列 F=MFQ(W,R,F);//MFQ算法调度 printf(\"完成队列如下：\\n\"); Print(F); }