进程调度算法

实验项目名称：进程调度算法一、实验目的编程实现FIFO和SPF调度算法二、实验内容1、综合运用相关知识，仿真实现进程调度算法（1）操作系统基本原理（2）软件工程中涉及软件分析、设计、实现和测试能力（3）数据结构与算法中的栈、队列、链表等的遍历方法（4）C++或java语言编程（5）Linux系统的安装、配置与使用2、学习先来先服务算法、最短作业优先算法。3、计算出不同时间片是多进程调度的完成时间、周转时间。给定进程A,B,C,D,E，每个进程的运转时间4,3,4,2,4,每个进程的到达时间1,2,3,4,5;（1）进行时间片轮转调度算法的模拟；（2）时间片q=1，轮转调度算法的模拟并计算周转时间、平均周转时间、带权周转时间。（3）时间片q=4，轮转调度算法的模拟并计算周转时间、平均周转时间、带权周转时间。4、按照一定的算法选取进程；5个进程各自运行所需要的时间及存储空间，即A、B、C、D、E，它们到达的时间分别是0、1、2、3、4，所要求的服务时间分别是4、3、5、2、4。（1）进行进程调度算法的模拟；（2）按的原则进行调度；根据运行情况计算周转时间、平均周转时间、带权周转时间。（3）按的原则进行调度；根据运行情况计算周转时间、平均周转时间、带权周转时间。5、画出调度图或表。三、实验用设备仪器及材料计算机，实验室电力、实验报告用纸、电脑键盘、鼠标等。四、实验原理及接线1.先来先服务算法先来先服务(FCFS:firstcomefirstservice)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。2.最短作业优先算法该算法从就绪队列中选出下一个“CPU执行期最短”的进程，为之分配处理机五、实验步骤1.程序流图（1）先来先服务算法（2）最短作业优先算法2.程序代码（1）先来先服务算法#includestdio.h#includestring.h#includestdlib.h#includevectorusingnamespacestd;structfcfs{charname[10];floatdaodatime;floatfuwutime;floatkaishitime;floatwanchengtime;floatzhouzhuangtime;floatdaiquantime;};voidinput(fcfs*p,intN){inti;for(i=0;i=N-1;i++){scanf(%s%f%f,p[i].name,&p[i].daodatime,&p[i].fuwutime);p[i].kaishitime=0;p[i].wanchengtime=0;p[i].zhouzhuangtime=0;p[i].daiquantime=0;}}voidprint(fcfs*p,intN){intk;printf(进程到达时间服务时间开始时间完成时间周转时间带权周转时间\n);for(k=0;kN;k++){printf(%4s,p[k].name);printf(%8.0f,p[k].daodatime);printf(%8.0f,p[k].fuwutime);printf(%8.0f,p[k].kaishitime);printf(%8.0f,p[k].wanchengtime);printf(%8.0f,p[k].zhouzhuangtime);printf(%12.2lf,p[k].daiquantime);printf(\n);}}voidsort(fcfs*p,intN){inti,j;for(i=1;iN;i++){fcfst=p[i];for(j=i-1;j=0&&t.daodatimep[j].daodatime;j--)p[j+1]=p[j];p[j+1]=t;}}voidrun(fcfs*p,intN){intk;for(k=0;kN;k++){if(k==0){p[k].kaishitime=p[k].daodatime;p[k].wanchengtime=p[k].daodatime+p[k].fuwutime;}else{p[k].kaishitime=p[k-1].wanchengtime;p[k].wanchengtime=p[k].kaishitime+p[k].fuwutime;}}for(k=0;kN;k++){p[k].zhouzhuangtime=p[k].wanchengtime-p[k].daodatime;p[k].daiquantime=p[k].zhouzhuangtime/p[k].fuwutime;}}voidFCFS_MAIN(){intN;printf(请输入进程的数量:\n);scanf(%d,&N);fcfs*p=newfcfs[N];input(p,N);sort(p,N);run(p,N);print(p,N);delete[]p;}intmain(){FCFS_MAIN();return0;}（2）最短作业优先算法#includestdio.h#includestdlib.h#defineINF1000000.0structPCB{charid[10];doublereachTime;doubleneedTime;doublestartTime;doublefinishTime;doublecTime;doublewcTime;charstate;};intfindNext(structPCBarr[],intlength,doublelastTime){inti,p,q;doubleminNeedTime,minReachTime;p=q=-1;minNeedTime=minReachTime=INF;for(i=0;ilength;i++){if(arr[i].state=='R'){if(arr[i].reachTime=lastTime&&arr[i].needTimeminNeedTime){p=i;minNeedTime=arr[i].needTime;}if(arr[i].reachTimelastTime&&arr[i].reachTimeminReachTime){q=i;minReachTime=arr[i].reachTime;}}}if(p!=-1)returnp;returnq;}intmain(){intnum,i;doublelastTime;structPCB*arr;printf(请输入进程数:);scanf(%d,&num);arr=(structPCB*)malloc(num*sizeof(structPCB));lastTime=INF;for(i=0;inum;i++){scanf(%s%lf%lf,arr[i].id,&arr[i].reachTime,&arr[i].needTime);arr[i].state='R';if(lastTimearr[i].reachTime)lastTime=arr[i].reachTime;}doublesum1=0.0,sum2=0.0;for(i=0;inum;i++){intp=findNext(arr,num,lastTime);if(arr[p].reachTime=lastTime)arr[p].startTime=lastTime;elsearr[p].startTime=arr[p].reachTime;arr[p].finishTime=arr[p].startTime+arr[p].needTime;arr[p].cTime=arr[p].finishTime-arr[p].reachTime;arr[p].wcTime=arr[p].cTime/arr[p].needTime;arr[p].state='F';sum1+=arr[p].cTime;sum2+=arr[p].wcTime;lastTime=arr[p].finishTime;}printf(\n进程到达时间运行时间开始时间完成时间周转时间带权周转时间\n);for(i=0;inum;i++){printf(%4s%8.0lf%8.0lf,arr[i].id,arr[i].reachTime,arr[i].needTime);printf(%8.0lf%8.0lf,arr[i].startTime,arr[i].finishTime);printf(%8.0lf%12.2lf\n,arr[i].cTime,arr[i].wcTime);}return0;}六、实验结果分析程序运行图：（1）先来先服务算法（2）短程序优先算法