进程模拟调度算法专业课程设计

一．课程概述1.1.设计构想程序能够完成以下操作：创建进程：先输入进程数目，再一次输入每个进程进程名、运行总时间和优先级，先抵达先输入；进程调度：进程创建完成后就选择进程调度算法，并单步实施，每次实施结果全部从屏幕上输出来。1.2.需求分析在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地实施，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中一个进程，使之实施。分配处理机任务是由处理机调度程序完成。因为处理机是最关键计算机资源，提升处理机利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能好坏，所以，处理机调度便成为操作系统设计中心问题之一。此次试验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。1.3.理论依据为了描述和管制进程运行，系统为每个进程定义了一个数据结构——进程控制块PCB(ProcessControlBlock),PCB中统计了操作系统所需、用于描述进程目前情况和控制进程运行全部信息，系统总是经过PCB对进程进行控制，亦即，系统是依据进程PCB而不是任何别什么而感知进程存在，PCB是进程存在惟一标志。此次课程设计用结构体Process替换PCB功效。1.4.课程任务用C语言（或C++）编程实现操作模拟操作系统进程调度子系统基础功效；利用多个算法实现对进程模拟调度。经过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多级反馈队列调度算法，使学生深入掌握进程调度概念和算法，加深对处理机分配了解。实现用户界面开发1.5.功效模块分析：进程概念：进程是被独立分配资源最小单位。进程是动态概念，必需程序运行才有进程产生。2、进程状态模型：（1）运行：进程已取得处理机，目前处于运行状态。（2）就绪：进程已经准备好，一旦有处理器就可运行。3、处理机调度：在多道程序设计系统中，内存中有多道程序运行，她们相互争夺处理机这一关键资源。处理机调度就是从就绪队列中，根据一定算法选择一个进程并将处理机分配给它运行，以实现进程并发地实施。4、进程调度算法功效：统计系统中全部进程实施情况选择占有处理机进程进行进程上下文切换5、进程调度算法：（1）先来先服务算法：假如早就绪进程排在就绪队列前面，迟就绪进程排在就绪队列后面，那么先来先服务总是把目前处于就绪队列之首那个进程调度到运行状态。（2）优先数算法：即进程实施次序由高优先级到低优先级。系统或用户按某种标准为进程指定一个优先级来表示该进程所享受确实调度优先权。该算法关键是确定进程优先级。（3）时间片轮转算法：固定时间片，每个进程在实施一个时间片后，轮到下一进程实施，知道全部进程实施完成。处理器同一个时间只能处理一个任务。处理器在处理多任务时候，就要看请求时间次序，假如时间一致，就要进行估计。挑到一个任务后，需要若干步骤才能做完，这些步骤中有些需要处理器参与，有些不需要（如磁盘控制器存放过程）。不需要处理器处理时候，这部分时间就要分配给其它进程。原来进程就要处于等候时间段上。经过周密分配时间，宏观上就象是多个任务一起运行一样，但微观上是有前后，就是时间片轮换。(4)多级反馈队列法：又称反馈循环队列或多队列策略，关键思想是将就绪进程分为两级或多级，系统对应建立两个或多个就绪进程队列，较高优先级队列通常分配给较短时间片。处理器调度先从高级就绪进程队列中选择可占有处理器进程，只有在选不到时，才从较低级就绪进程队列中选择。（5）短作业优先法：对短进程优先调度算法，它是从后备队列中选择一个或若干个进程，将处理机分配给它，使它立即实施并一直实施到完成，或发生某事件而被阻塞放弃处理机时再重新调度。二．设计方案2.1．先来先服务调度2.1.1．算法思想先来先服务调度算法思想是根据进程进入就绪队列前后次序调度并分配处理机实施。先来先服务调度算法是一个不可抢占算法，优异入就绪队列进程，先被处理机运行。一旦一个进程占有了处理机，它就一直运行下去，直到该进程完成工作或因为等候某事件而不能继续运行时才释放处理机。2.1.2．算法步骤图图1.先来先服务算法步骤图2.1.3．程序代码#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode{ charname[10];/*进程名*/ intcputime;/*占用cpu时间*/ charstarttime[5];//进程开始时间 intneedtime;/*要求运行时间*/ charstate;/*状态*/ structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish;//就绪、实施、结束指针intN;//进程数量voidprint()//输出函数{ PCB*p; printf("NAMECPUTIMESTARTTIMENEEDTIMESTATUS\n"); if(run!=NULL) printf("%-10s%-10d%-10s%-10d%c\n", run->name, run->cputime, run->starttime, run->needtime, run->state);/*输出实施进程信息*/ p=ready; while(p!=NULL) { printf("%-10s%-10d%-10s%-10d%c\n", p->name, p->cputime, p->starttime, p->needtime, p->state);/*输出就绪进程信息*/ p=p->next; } p=finish; while(p!=NULL) { printf("%-10s%-10d%-10s%-10d%c\n", p->name, p->cputime, p->starttime, p->needtime, p->state);/*输出结束队列信息*/p=p->next; } getchar();/*使用getchar()函数能够让输出时停留画面， 等候人按回车继续*/}voidinsert(PCB*q)/*插入新进程，把进程按进程到来时间大小排序*/{ PCB*p1,*s,*r; intb; s=q;/*指针s指向新要插入进程*/ p1=ready;/*指针p1指向原来进程队列队首*/ r=p1;/*使用指针r是指向p1前面进程*/ b=1; while((p1!=NULL)&&b) if(strcmp(p1->starttime,s->starttime)<0) { r=p1;p1=p1->next; }/*新进程开始时间大，则p1指向下一个进程继续比*/ else b=0; if(r!=p1) { r->next=s;s->next=p1; }/*新进程找到位置，插在r和p1之间*/ else { s->next=p1;ready=s; }/*新进程开始时间按最小，插在队首，并修改就绪队首ready指针*/}voidcreate(){ PCB*p; inti; ready=NULL; run=NULL; finish=NULL; printf("PleaseenterthenameandtimeandstarttimeofPCB:\n"); /*输入进程名、运行时间和开始时间*/ for(i=0;i<N;i++) { p=(PCB*)malloc(sizeof(PCB));/*为新进程开辟空间*/ scanf("%s",p->name);/*输入进程名*/ scanf("%d",&p->needtime);/*输入进程要求运行时间*/ scanf("%s",p->starttime);//输入进程开始时间 p->cputime=0; p->state='W';/*表示就绪队列中未在队首先实施，但也是就绪状态*/ if(ready!=NULL) insert(p);/*就绪队首不为NULL，插入新进程*/ else {/*不然先插在NULL前*/ p->next=ready; ready=p; } } printf("Displayisgoingtostart:\n"); printf("***********************************************\n"); print(); getchar(); run=ready;/*队列排好，run指向就绪队列队首*/ ready=ready->next;/*ready指向下一个进程*/ run->state='R';/*队首进程状态为就绪*/}voidFCFS(){ while(run!=NULL) { run->cputime=run->cputime+run->needtime; run->needtime=0; run->next=finish; finish=run; run->state='E'; run=NULL; if(ready!=NULL) { run=ready; run->state='R'; ready=ready->next; } print(); }}voidmain(){ printf("PleaseenterthetotalnumberofPCB:\n"); scanf("%d",&N); create();/*模拟创建进程，并输入相关信息*/ FCFS();/*先来先服务调度算法*/}2.1.4．测试结果及说明首先输入进程个数（为5个），这里命名为A,B,C,D,E，然后分别输入运行时间和开始时间全部进程全部在队列中，并全部处于等候状态其中一个进程实施完成全部进程全部实施完成2.2．优先级调度2.2进程实施次序由高优先级到低优先级，系统或用户按某种标准为进程指定一个优先级来表示该进程所享受确实调度优先权。该算法关键是确定进程优先级。2.2.2图2.优先级调度步骤图2.2#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode{charname[10];/*进程名*/intprio;/*优先数*/intcputime;/*占用cpu时间*/intneedtime;/*要求运行时间*/charstate;/*状态*/structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish;/*就绪实施结束指针*/intN;voidprt()/*输出函数，能够方便看到进程实施演示*/{PCB*p;printf("NAMECPUTIMENEEDTIMEPRIORITYSTATUS\n");if(run!=NULL)printf("%-10s%-10d%-10d%-10d%c\n",run->name,run->cputime,run->needtime,run->prio,run->state);/*输出实施进程信息*/p=ready;while(p!=NULL){printf("%-10s%-10d%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->prio,p->state);/*输出就绪进程信息*/p=p->next;}p=finish;while(p!=NULL){printf("%-10s%-10d%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->prio,p->state);/*输出结束队列信息*/p=p->next;}getchar();}/*使用getchar()函数能够让输出时停留画面，等候人按回车继续*/voidinsert(PCB*q)/*插入新进程，把进程按优先数大小排序*/{PCB*p1,*s,*r;intb;s=q;/*指针s指向新要插入进程*/p1=ready;/*指针p1指向原来进程队列队首*/r=p1;/*使用指针r是指向p1前面进程*/b=1;while((p1!=NULL)&&b)if(p1->prio>=s->prio){r=p1;p1=p1->next;}/*新进程优先数小，则p1指向下一个进程继续比*/ elseb=0;if(r!=p1){r->next=s;s->next=p1;}/*新进程找到位置，插在r和p1之间*/else{s->next=p1;ready=s;}}/*新进程优先数最大，插在队首，并 修改就绪队首ready指针*/voidcreate(){PCB*p;inti;ready=NULL;run=NULL;finish=NULL;printf("PleaseenterthenameandtimeandpriorityofPCB:\n");/*输入进程名、运行时间和优先级*/for(i=0;i<N;i++){p=(PCB*)malloc(sizeof(PCB));/*为新进程开辟空间*/scanf("%s",p->name);/*输入进程名*/scanf("%d",&p->needtime);/*输入进程要求运行时间*/scanf("%d",&p->prio);/*输入进程优先数*/p->cputime=0;p->state='W';/*表示就绪队列中未在队首先实施，但也是就绪状态*/if(ready!=NULL)insert(p);/*就绪队首不为NULL，插入新进程*/else{p->next=ready;ready=p;}}/*不然先插在NULL前*/printf("Displayisgoingtostart:\n");printf("***********************************************\n");prt();run=ready;/*队列排好，run指向就绪队列队首*/ready=ready->next;/*ready指向下一个进程，这么当进程实施时假如优先数小于其它进程，应该优异行优先数最大进程*/run->state='R';}/*队首进程状态为就绪*/voidprio(){while(run!=NULL){run->cputime=run->cputime+1;/*运行一次cpu占用时间加一*/run->needtime=run->needtime-1;/*运行一次要求运行时间减一*/run->prio=run->prio-1;/*运行一次优先数减一*/if(run->needtime==0)/*若要求运行时间为0时*/{run->next=finish;/*退出队列*/finish=run;/*finish为结束进程队列*/run->state='E';/*修改状态为结束*/run=NULL;/*释放run指针*/if(ready!=NULL)/*创建新就绪队列头指针*/{run=ready;run->state='R';ready=ready->next;}}elseif((ready!=NULL)&&(run->prio<ready->prio))/*队首进程优先数比它下一个小，且下一个进程不为NULL时实施*/{run->state='W';run->next=NULL;/*队首进程退出进程队列*/insert(run);/*在进程队列中重新插入原来队首进程*/run=ready;/*重新置就绪队列头指针*/run->state='R';ready=ready->next;}prt();}}voidmain(){printf("PleaseenterthetotalnumberofPCB:\n");scanf("%d",&N);create();/*模拟创建进程，并输入相关信息*/prio();}/*优先数调度算法*/2.2优先级调度算法运行情况图1，图2，图3，图4所表示图1.输入进程块数量图2.输入每个进程名称、时间、优先级图3.输入全部进程相关信息图4.全部进程调度算法完成2.3．时间片轮转调度2.3全部就绪进程按先来先服务标准排成一个队列，将新来进程加到就绪对列末尾，每当实施进程调度时，总是把处理机分配给队首进程，各进程占用CPU时间片相同。也就是说CPU处理时间划分成一个个相同时间片，就绪队列全部进程轮番运行一个时间片。当一个时间片结束时，假如运行进程用完它时间片后还未完成，就强迫运行进程让出CPU，就把它送回到就绪队列末尾，等候下一次调度。同时，进程调度又去选择就绪队列中队首进程，分配给它一时间片，以投入运行。直至全部进程运行完成。2.32.3#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode{ charname[10];/*进程名*/intcount;/*计数器，判定是否=时间片大小*/ intcputime;/*占用cpu时间*/ intneedtime;/*要求运行时间*/ charstate;/*状态*/ structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish,*tail;/*就绪实施结束尾指针*/intN,round;voidprt()/*输出函数，能够方便看到进程实施演示*/{ PCB*p;printf("NAMECPUTIMENEEDTIMESTATUS\n");if(run!=NULL) printf("%-10s%-10d%-10d%c\n",run->name,run->cputime,run->needtime,run->state);/*输出实施进程信息*/p=ready;while(p!=NULL){ printf("%-10s%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->state);/*输出就绪进程信息*/p=p->next; }p=finish;while(p!=NULL){ printf("%-10s%-10d%-10d%c\n",p->name,p->cputime,p->needtime,p->state);/*输出结束队列信息*/p=p->next; }getchar();}voidinsert(PCB*q)/*在队尾插入新进程*/{ PCB*p; p=ready; while(p->next!=NULL) { p=ready->next; } tail=p; tail->next=q; q->next=NULL;}voidcreate(){ PCB*p;inti; ready=NULL;run=NULL;finish=NULL; printf("PleaseenterthenameandtimeofPCB:\n");/*输入进程名、和*/ for(i=0;i<N;i++){ p=(PCB*)malloc(sizeof(PCB));/*为新进程开辟空间*/scanf("%s",p->name);/*输入进程名*/scanf("%d",&p->needtime);/*输入进程要求运行时间*/p->cputime=0;p->state='W';/*表示就绪队列中未在队首先实施，但也是就绪状态*/if(ready!=NULL)insert(p);/*就绪队首不为NULL，插入新进程*/else { p->next=ready;ready=p;tail=p; } }printf("Displayisgoingtostart:\n");printf("***********************************************\n");prt(); getchar();run=ready;/*队列排好，run指向就绪队列队首*/ready=ready->next;/*ready指向下一个进程*/run->state='R';}/*队首进程状态为就绪*/voidcount(){ while(run!=NULL) { run->cputime=run->cputime+1;/*运行一次cpu占用时间加一*/ run->needtime=run->needtime-1;/*运行一次要求运行时间减一*/ run->count=run->count+1;/*运行一次计数器加一*/ if(run->needtime==0)/*若要求运行时间为0时*/ { run->next=finish;/*退出队列*/ finish=run;/*finish为结束进程队列*/ run->state='E';/*修改状态为结束*/ run=NULL;/*释放run指针*/ if(ready!=NULL)/*创建新就绪队列头指针*/ { run=ready;run->state='R';ready=ready->next; } } else if(run->count==round)/*假如时间片到*/ { run->count=0;/*计数器置0*/ if(ready!=NULL)/*如就绪队列不空*/ { run->state='W'; insert(run);/*在进程队列中重新插入原来进程,插入队尾*/ run=ready;/*重新置就绪队列头指针*/ run->state='R'; ready=ready->next; } } prt(); }}voidmain(){ printf("PleaseenterthetotalnumberofPCB:\n"); scanf("%d",&N); create();/*模拟创建进程，并输入相关信息*/ count();/*优先数调度算法*/}2.3时间片轮转调度算法运行情况图1，图2，图3所表示图1全部进程全部在队列中图2其中一个进程实施完成图4全部进程全部实施完成2.4．多级反馈队列调度2.4.1算法思想许可进程在队列之间移动。在系统中设置多个就绪队列，每个队列对应一个优先级，第一个队列优先级最高，第二队列次之。以下各队列优先级逐步低。各就绪队列中进程运行时间片不一样，高优先级队列时间片小，低优先级队列时间片大。进程并非总是固定在某一队列中，新进程进入系统后，被存放在第一个队列末尾。假如某个进程在要求时间片内没有完成工作，则把它转入到下一个队列末尾，直至进入最终一个队列。系统先运行第一个队列中进程。当第一队列为空时，才运行第二个队列中进程。依这类推，仅目前面全部队列全部为空时，才运行最终一个队列中进程。当处理器正在第i个队列中为某个进程服务时，又有新进程进入优先级最高队列（第1—（i-1）中任何一个对列），则此新进程要抢占正在运行进程处理器，即由调度程序把正在运行进程放回第i队列末尾，把处理器分配给新到高优先级进程。除最低优先权队列外全部其它队列，均采取相同进程调度算法，即按时间片轮转FIFO（优异先出）算法。最终一个队列中进程按按时间片轮转或FCFS策略进行调度。它是综合了FIFO、RR和剥夺式HPF一个进程调度算法。2.4.2算法步骤图2.4.3程序代码#include<stdio.h>#include<stdlib.h>#include<string.h>#defineNULL0typedefstructnode{ charname[10];/*进程名*/ intnum; /*进程所在队列数,也是该队列时间片*/ intcputime;/*占用cpu时间*/ intneedtime;/*要求运行时间*/ structnode*next;/*指针*/}PCB;PCB*qf1,*ql1;PCB*qf2,*ql2;PCB*qf3,*ql3;//定义三个队列头指针和尾指针intblog1,blog2,blog3; /*分别统计队列1,、队列2、队列3中进程数*/voidinsert(PCB*q,PCB*qf,PCB*ql){ q->num++; if(qf==NULL&&ql==NULL) {//队列为空 qf=ql=q; } else {//队列不为空 ql->next=q; ql=q; } ql->next=NULL;}voidcreate(intn){//创建进程，刚来进程全部进入队列1 PCB*p; p=(PCB*)malloc(sizeof(PCB)); inti; blog1=blog2=blog3=0; //各队列中进程数均为0 printf("PleaseenterthenameandneedtimeofPCB:\n"); /*输入进程名和所需时间*/ for(i=0;i<n;i++) { //p=(PCB*)malloc(sizeof(PCB));/*为新进程开辟空间*/ scanf("%s",p->name);/*输入进程名*/ scanf("%d",&(p->needtime));/*输入进程要求运行时间*/ p->cputime=0; p->num=0; insert(p,qf1,ql1); blog1++; //队列中进程数加1 }}intrun(PCB*q,PCB*qf,PCB*ql){ PCB*p,*f,*l; /*p=(PCB*)malloc(sizeof(PCB)); f=(PCB*)malloc(sizeof(PCB)); l=(PCB*)malloc(sizeof(PCB));*/ p=q; f=qf; l=ql; if(q->needtime<=q->num)/*在时间片内完成*/ { //q->cputime+=q->needtime; q->needtime=0; free(q); return0; } else /*不能在时间片内完成*/ { //q->cputime+=q->num; q->needtime-=q->num; if(q->num<3) q->num++; insert(p,f,l); //进入下一个队列 return1; } }voidprt()/*输出函数，能够方便看到进程实施演示*/{ PCB*p; //p=(PCB*)malloc(sizeof(PCB)); inta; printf("NAMECPUTIMENEEDTIMESTATUS\n"); while(blog1>0||blog2>0||blog3>0) { if(blog1>0) /*第一个队列不为空*/ { p=qf1; qf1=qf1->next; p->next=NULL; blog1--; printf("%-10s%-10d%\n",p->name,p->needtime); a=run(p,qf2,ql2); if(a==1) blog2++; } elseif(blog2>0) /*第二个队列不为空*/ { p=qf2; qf2=qf2->next;p->next=NULL; blog2--; printf("%-10s%-10d%\n",p->name,p->needtime); a=run(p,qf3,ql3); if(a==1) blog3++; } elseif(blog3>0) /*第三个队列不为空*/ { p=qf3; qf3=qf3->next;p->next=NULL; blog3--; printf("%-10s%-10d%\n",p->name,p->needtime); a=run(p,qf3,ql3); if(a==1) blog3++; } }}/*使用getchar()函数能够让输出时停留画面，等候人按回车继续*/voidmain(){ qf1=ql1=(PCB*)malloc(sizeof(PCB)); qf2=ql2=(PCB*)malloc(sizeof(PCB)); qf2=ql2=(PCB*)malloc(sizeof(PCB)); intn; blog1=blog2=blog3=0; printf("请输入进程个数:"); scanf("%d",&n); create(n); prt();}2.42.5．短作业调度2.5.1短作业优先调度算法是指对短作业进行调度算法。它从后备队列总选择一个或若干个运行时间最短作业，将她们调入内存运行。2.5.2开始开始输入进程名输入进程名就绪队列空?就绪队列空?结束 Y结束 N按时间服务进行排序按时间服务进行排序实施程序实施程序短作业优先算法步骤图2.5#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode{ charname[10];/*进程名*/ intcputime;/*占用cpu时间*/ intneedtime;/*要求运行时间*/ charstate;/*状态*/ structnode*next;/*指针*/}PCB;PCB*ready,*run,*finish;//就绪、实施、结束指针intN;//进程数量voidprint()//输出函数{ PCB*p; printf("NAMECPUTIMENEEDTIMESTATUS\n"); if(run!=NULL) printf("%-10s%-10d%-10d%c\n", run->name, run->cputime, run->needtime, run->state);/*输出实施进程信息*/ p=ready; while(p!=NULL) { printf("%-10s%-10d%-10d%c\n", p->name, p->cputime, p->needtime, p->state);/*输出就绪进程信息*/ p=p->next; } p=finish; while(p!=NULL) { printf("%-10s%-10d%-10d%c\n", p->name, p->cputime, p->needtime, p->state);/*输出结束队列信息*/p=p->next; } getchar();/*使用getchar()函数能够让输出时停留画面， 等候人按回车继续*/}voidinsert(PCB*q)/*插入新进程，把进程按进程到来时间大小排序*/{ PCB*p1,*s,*r; intb; s=q;/*指针s指向新要插入进程*/ p1=ready;/*指针p1指向原来进程队列队首*/ r=p1;/*使用指针r是指向p1前面进程*/ b=1; while((p1!=NULL)&&b) if(p1->needtime<s->needtime) { r=p1;p1=p1->next; }/*新进程开始时间大，则p1指向下一个进程继续比*/ else b=0; if(r!=p1) { r->next=s;s->next=p1; }/*新进程找到位置，插在r和p1之间*/ else { s->next=p1;ready=s; }/*新进程开始时间按最小，插在队首，并修改就绪队首ready指针*/}voidcreate(){ PCB*p; inti; ready=NULL; run=NULL; finish=NULL; printf("PleaseenterthenameandtimeofPCB:\n"); /*输入进程名、运行时间和开始时间*/ for(i=0;i<N;i++) { p=(PCB*)malloc(sizeof(PCB));