CPU调度算法

一、设计目的通过CPU调度相关算法的实现，了解CPU调度的相关知识，通过实现CPU调度算法，理解CPU的管理，以及不同的CPU调度算法实现过程。体会算法的重要性。二、设计要求1、编写算法，实现FCFS、非抢占SJF、可抢占优先权调度2、针对模拟进程，利用CPU调度算法进行调度3、进行算法评估，计算平均周转时间和平均等待时间4、调度所需的进程参数由输入产生（手工输入或者随机数产生）5、输出调度结果6、输出算法评价指标三、设计说明1、采用数组、指针2、FCFS先来先服务调度算法是一种最简单的调度算法，当作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个最先进入该队列的作业3、非抢占SJF短作业优先调度算法，是指对短作业有限调度算法。是从后备队列中选择一个估计运行时间最短的作业将他们调入内存。4、可抢占优先权调度在这种方式下，系统把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要出现另一个其优先权更高的进程，进程调度程序就立即停止当前进程（原优先权最高的进程）的执行，重新将处理及分配给新到的优先权最高的进程。四、程序流程图。1、可抢占优先权调度算法开始当前作业为按编号找到第一个还没有执行的作业当前作业是最后一个作业和下一个还没有执行的作业比较当前在上次作业被执行之前到达当前作业取较早到达且相应比更高的一个同时到达当前作业取较早到达的一个当前作业取响应比更高的一个返回这一次要执行的作业YNNYNNY2、FCFS3、非抢占SJF一次比较相邻两个进程的优先级前者优先级是小于还是等于后者比较两个进程所需占用的CPU时间前者后者？交换位置依次执行位于前面的进程改变进程的相关数值的大小判断Alltime是否为0结束YYN=开始初始化进程判断运行队列是否为空开始对运行队列中的进程时间做减一判断正在运行进程所需时间是否为0将完成进程放入完成队列判断等待队列是否为空将等待队列中最早到的进程放入运行队列是否否是否是结束五、程序部分1、FCFS#includestdio.h#includestdlib.htypedefstructPCB{charname[10];charstate;intarrivetime;intstarttime;intfinishtime;intservicetime;floatturnaroundtime;floatweightedturnaroundtime;structPCB*next;}pcb;inttime;intn;pcb*head=NULL,*p,*q;voidrun_fcfs(pcb*p1){time=p1-arrivetimetime?p1-arrivetime:time;p1-starttime=time;printf(\n现在时间是%d,开始运行作业%s\n,time,p1-name);time+=p1-servicetime;p1-state=T;p1-finishtime=time;p1-turnaroundtime=p1-finishtime-p1-arrivetime;p1-weightedturnaroundtime=p1-turnaroundtime/p1-servicetime;printf(到达时间开始时间服务时间完成时间周转时间带权周转时间\n);printf(%6d%10d%10d%8d%10.1f%10.2f\n,p1-arrivetime,p1-starttime,p1-servicetime,p1-finishtime,p1-turnaroundtime,p1-weightedturnaroundtime);}voidfcfs(){inti,j;p=head;for(i=0;in;i++){if(p-state=='F'){q=p;run_fcfs(q);}p=p-next;}}voidgetInfo(){intnum;printf(\n作业个数:);scanf(%d,&n);for(num=0;numn;num++){p=(pcb*)malloc(sizeof(pcb));printf(依次输入:进程名到达时间服务时间\n);scanf(%s%d%d,&p-name,&p-arrivetime,&p-servicetime);if(head==NULL){head=p;q=p;time=p-arrivetime;}if(p-arrivetimetime)time=p-arrivetime;q-next=p;p-starttime=0;p-finishtime=0;p-turnaroundtime=0;p-weightedturnaroundtime=0;p-next=NULL;p-state='F';q=p;}}voidmain(){system(graftabl936);printf(先来先服务算法模拟);getInfo();p=head;fcfs();getch();}2、非抢占SJF#includestdio.h#includeconio.h#defineMAX100structjcb{charname[10];floatarrivetime;floatstarttime;floatfinishtime;floatservicetime;floatzztime;floatavezztime;};structjcba[MAX];voidinput(jcb*p,intN){inti;printf(请分别输入\n\t进程名到达时间服务时间\n\n);for(i=0;i=N-1;i++){printf(请输入第%d个进程信息:,i+1);scanf(%s%f%f,&p[i].name,&p[i].arrivetime,&p[i].servicetime);printf(\n);}}voidPrint(jcb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatavezztime,intN){intk;printf(调度顺序:);printf(%s,p[0].name);for(k=1;kN;k++){printf(--%s,p[k].name);}printf(\n\n);printf(\t\t\t进程信息:\n);printf(\nname\tarrive\tservice\tstart\tfinish\tzz\tavezz\n);for(k=0;k=N-1;k++){printf(%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n,p[k].name,p[k].arrivetime,p[k].servicetime,p[k].starttime,p[k].finishtime,p[k].zztime,p[k].avezztime);}}voidsort(jcb*p,intN){inti,j;for(i=0;i=N-1;i++)for(j=0;j=i;j++)if(p[i].arrivetimep[j].arrivetime){jcbtemp;temp=p[i];p[i]=p[j];p[j]=temp;}}voiddeal(jcb*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,float&zztime,float&avezztime,intN){intk;for(k=0;k=N-1;k++){if(k==0){p[k].starttime=p[k].arrivetime;p[k].finishtime=p[k].arrivetime+p[k].servicetime;}else{p[k].starttime=p[k-1].finishtime;p[k].finishtime=p[k-1].finishtime+p[k].servicetime;}}for(k=0;k=N-1;k++){p[k].zztime=p[k].finishtime-p[k].arrivetime;p[k].avezztime=p[k].zztime/p[k].servicetime;}}voidjcbf(jcb*p,intN){floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,avezztime=0;intm,n,next,k,i=0;floatmin;sort(p,N);for(m=0;mN-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;for(n=m+1;n=N-1;n++){if(p[n].arrivetime=p[m].finishtime)i++;}min=p[m+1].servicetime;next=m+1;for(k=0;km+i;k++){if(p[k+1].servicetimemin){min=p[k+1].servicetime;next=k+1;}}{jcbtemp;temp=p[m+1];p[m+1]=p[next];p[next]=temp;}deal(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,avezztime,N);}}intmain(){intN,*b;charch;while(1){system(CLS);system(graftabl936);printf(\t\t\t------短作业优先调度算法------\n);printf(输入进程个数:);scanf(%d,&N);if(NMAX){printf(\t!!输入的作业数目太大，请输入不大于%d的整数\n,MAX);printf(按Q或者q退出程序,按其他任意键继续测试...);ch=getch();if(ch=='Q'||ch=='q'){break;}elsecontinue;}input(a,N);jcb*b=a;jcbf(b,N);printf(按Q或者q退出程序,按其他任意键继续测试...);ch=getch();if(ch=='Q'||ch=='q'){break;}}return0;getch();}3、可抢占优先权调度算法#includedos.h#includetime.h#includestdlib.h#includestdio.h#includeconio.h#includestring.htypedefcharstring[10];structtask{stringname;intarrTime;intserTime;intwaiTime;intbegTime;intfinTime;intturTime;intwTuTime;intpriority;intfinish;}JCB[10];intnum;voidinput(){inti;system(cls);printf(\n请输入作业数量:);scanf(%d,&num);for(i=0;inum;i++){printf(\n请输入作业NO.%d:\n,i);printf(作业名称:);scanf(%s,JCB[i].name);printf(到达时间:);scanf(%d,&JCB[i].arrTime);printf(服务时间:);