进程调度算法的模拟实现

操作系统课程设计报告题目：进程调度算法的模拟实现_专业计算机科学与技术学生姓名班级学号指导教师发放日期2015.1.30信息工程学院目录1概述.......................................................................12设计原理...................................................................12.1先来先服务算法...........................................................13详细设计与编码.............................................................23.1模块设计.................................................................23.2系统流程图...............................................................23.3系统详细设计.............................................................24结果与分析.................................................................64.1测试方案.................................................................64.2测试结果.................................................................64.3测试结果分析.............................................................95设计小结..................................................................106参考文献..................................................................10附录程序代码...............................................................12进程调度算法的模拟实现1进程调度算法的模拟实现1概述选择一个调度算法，实现处理机调度，进程调度算法包括：先来先服务算法，短进程优先算法，时间片轮转算法，动态优先级算法。可选择进程数量，本程序包括四种算法，用C或C++语言实现，执行时在主界面选择算法（可用函数实现），进入子页面后输入进程数，（运行时间，优先数由随机函数产生），执行，显示结果。2设计原理2.1先来先服务(FCFS)算法每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源创建进程，然后放入就绪队列2.2时间片轮转法(RR)算法系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。2.3短作业优先(SJF)算法短作业优先调度算法是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。2.4最高优先权优先(HRRN)算法优先权调度算法是为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入最高优先权优先调度算法。动态优先权是指在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。操作系统课程设计（2015）23详细设计与编码3.1模块设计(1)进入系统模块，进入登陆界面。(3)菜单选择模块。选择相应的进程调度方式，选择相应的数字，进入相应的功能。(4)算法模块。选择相应的进程调度算法。(5)显现输出模块。显示每种进程调度算法情况。(6)平均周转时间与平均带权周转时间的计算结果。(7)退出系统模块。3.2系统流程图3.3系统详细设计(1)系统主界面设计（包含登陆模块设计）首先将各种进程调度算法放入不同的头文件，在主函数引用，是系统结构更加清晰。设置一个mean()方法，让用户选择不同的进程调度算法，mean()方法返回一个char类型开始FCFS算法，对于先到达的进程优先分配CPUSJF算法，每次都从未完成的队列中选取服务时间最短的作业进行调度RR算法，每次调度时将CPU分派给队首进程，按照时间片依次执行进程HRRN算法，考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。结束进程调度算法的模拟实现3字符，以便在主函数的switch语句中选择调用不同的进程调度方法。(2)系统模块1.先来先服务算法对于先到达的进程优先分配CPU，按照先来先服务的原则依次执行各进程。算法：voidFCFS(fcfs*p,intN){floatsumzztime=0,sumdqzztime=0,avzztime,avdqzztime;floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;sort(p,N);deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N);for(intk=0;k=N-1;k++){sumzztime=sumzztime+p[k].zztime;sumdqzztime=sumdqzztime+p[k].dqzztime;}avzztime=sumzztime/N;printf(\n该算法的平均周转时间为:%-.2f\t,avzztime);avdqzztime=sumdqzztime/N;printf(该算法的平均带权周转时间为:%-.2f\t\n\n,avdqzztime);}2.短进程优先算法先找到运行时间最短的程序，然后执行，再从剩余的程序中找到运行时间最短的在执行，依次每次都执行运行时间最短的，直到程序执行完毕。算法：voidsjff(sjf*p,intN1){floatsumzztime=0,sumdqzztime=0,avzztime,avdqzztime;floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0;deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N1);Print(p,arrivetime,servicetime,starttime,finishtime,N1);for(intk=0;k=N1-1;k++){操作系统课程设计（2015）4sumzztime=sumzztime+p[k].zztime;sumdqzztime=sumdqzztime+p[k].dqzztime;}avzztime=sumzztime/N1;printf(\n该算法的平均周转时间为:%-.2f\t,avzztime);avdqzztime=sumdqzztime/N1;printf(该算法的平均带权周转时间为:%-.2f\t\n\n,avdqzztime);}3.时间片轮转算法按照轮转的次序分配给每个程序一定的时间执行，执行完成后执行后面的进程，依次循环执行直到所有进程执行完成。算法：voidtt(rr*p,intN2){floatsumzztime=0,sumdqzztime=0,avzztime=0,avdqzztime=0;inttimeprice=0;floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0,dqzztime=0,lefttime=0;ptt(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,avzztime,avdqzztime,lefttime,timeprice,N2);printf(\n综合信息为：\n);Print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N2);for(intk=0;k=N2-1;k++){sumzztime=sumzztime+p[k].zztime;sumdqzztime=sumdqzztime+p[k].dqzztime;}avzztime=sumzztime/N2;printf(\n该算法的平均周转时间为:%-.2f\t,avzztime);avdqzztime=sumdqzztime/N2;进程调度算法的模拟实现5printf(该算法的平均带权周转时间为:%-.2f\t\n,avdqzztime);getchar();}4.最高响应比优先算法按照优先级从高到低依次执行程序。算法：intHRN(intpre){intcurrent=1,i,j;/*优先权=(等待时间+服务时间)/服务时间*/for(i=0;iN4;i++){JCB[i].waiTime=JCB[pre].finTime-JCB[i].arrTime;/*等待时间=上一个作业的完成时间-到达时间*/JCB[i].priority=(JCB[i].waiTime+JCB[i].serTime)/JCB[i].serTime;}for(i=0;iN4;i++){if(!JCB[i].finish){current=i;/*找到第一个还没完成的作业*/break;}}for(j=i;jN4;j++)/*和后面的作业比较*/{if(!JCB[j].finish)/*还没完成(运行)*/{if(JCB[current].arrTime=JCB[pre].finTime)/*如果作业在上一个作业完成之前到达*/{if(JCB[j].arrTime=JCB[pre].finTime&&JCB[j].priorityJCB[current].priority)current=j;/*找出到达时间在上一个作业完成之前，优先权高的作业*/操作系统课程设计（2015）6}else/*如果作业是在上一个作业完成之后到达*/{if(JCB[j].arrTimeJCB[current].arrTime)current=j;/*找出比较早到达的一个*/if(JCB[j].arrTime==JCB[current].arrTime)/*如果同时到达*/if(JCB[j].priorityJCB[current].priority)current=j;/*找出服务时间比较短的一个*/}}}returncurrent;/*返回当前作业*/}4结果与分析4.1测试方案(1)测试方案(一)在主界面输入1，选择先来先服务调度算法，然后输入进程数目5，然后输入各个进程信息，观察测试结果。(2)测试方案（二)在主界面输入2，选择最短进程优先调度算法，然后输入进程数目5，然后输入各个进程信息,进程信息与测试方案(一)保持一致，观察测试结果