(word完整版)高响应比调度算法

1、淮北师范大学计算机学院实验设计报告操作系统程序设计实验报告实验课题：高响应比调度算法所属学院：计算机科学与技术所属班级：11级计算机非师姓名：李志国辅导老师：施汉琴2014年3月20日淮北师范大学11级计算机非师范程序设计实验报告- -目录实验设计课题第03页课程设计目的第03页课程设计内容第03页课程设计要求第04页相关知识介绍第05页程序功能说明第06页各段程序说明第07页设计的流程图第09页程序执行截图第11页源程序的代码第14页实验小结体会第19页实验设计课题设计题目：采用高响应比算法的进程调度程序指导老师：施汉琴课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一

2、个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。课程设计内容问题分析：在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。于是我们想到了一种办法解决这个问题，就是引用动态优先权、并使作业的优先级随着等待时间的增加而以速率a提高，长作业在等待一定的时间后，必然有机会分配到处理机，这样长作业也得到了运行。由此可见：（1）如果作业的等待时

3、间相同，则要求服务的时间越短，其优先权越高，因此该算法有利于短作业。（2）当要求服务的时间相同时，作业的优先权取决与其等待的时间，等待时间越长，其优先权越高，因而它实现的是先来先服务。（3）对于长作业，作业的优先权可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可以获得处理机。设计内容：设计并实现一个采用高响应比算法的进程调度演示程序，响应比R定义如下：RWT/T1W/T其中T为该作业估计需要的执行时间，为作业在后备状态队列中的等待时W间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加,W/T也就

4、随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。课程设计要求每一个进程有一个PCB，其内容可以根据具体情况设定。进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同步关系，故只有两种状态）采用可视

5、化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间具有一定的数据容错性相关知识介绍定义高响应比优先调度算法的基本思想是把CPU分配给就绪队列中响应比最高的进程。基本思想短作业优先调度算法+动态优先权机制，既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。原理高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：响应比=（等待时间+要求服务时间）/要求服务

6、时间，即RR二（w+s）/s=1+w/s,因此响应比一定是大于1的。如实例：某系统有3个作业,系统确定它们在全部到达后,再开始采用响应比高者优先的调度算法,则它们的调度顺序是什么？各自的周转时间是什么？作业号提交时间运行时间（1）如果都到达再算的话,等待时间=最后一个的提交时间-该作业到达的时刻1:9.5-8.8=0.72:9.5-9=0.53:0所以响应比为（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+11:0.7/1.5+1=1.472:0.5/0.4+1=2.253:1所以2先运行,2从9.5开始运行到9.9结束;再以9.9时刻算响应

7、比:1:（9.9-8.8）/1.5+1=1.733:（9.9-9.5）/1+1=1.4所以2执行完后1开始执行,从9.9执行到11.4结束最后一个是3:从11.4开始执行到12.4结束（2）如果不是都到达后才运行，那么在8.8时只有作业1到达，所以先运行作业18.8+1.5（运行时间）=10.3到10.3的时候作业1完成，此时作业2和3都已到达所以计算其响应比（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1作业2：（10.3-9.0）/0.4+1=4.325作业3：（10.3-9.5）/1.0+1=1.8所以先运行作业210.3+0.4=10.7到10.7运行作业310.7+

8、1.0=11.7到11.7结束优缺点短作业与先后次序的兼顾，且不会使长作业长期得不到服务响应比计算系统开销，增加系统开销。适用场合批处理系统。程序功能说明程序通过定义调用函数，杜如用户从键盘输入的需要服务的进程的各项参数，并进行调度算法模拟。首相对读入的进程各个参数进行保存，而后进行判断是否进入内存之中，如果在内存之中则进行高响应比优先的的方式进行排队服务运行，如果没有进入内存，则进程等待。直到所有进程服务运行完毕为止。各个函数都有各自的功能，相互协调进行整体函数功能的实现。采用响应比高者优先调度算法进行调度时，必须计算出系统中所有满足必要条件作业的响应比，从中选择响应比最高的一个作业装入主存

9、储器分配资源。由于是实验，所以就将作业控制块出队，并输出作业名代替装入处存储器，同时修改系统的资源数量。各段程序说明首先进行函数相关参数定义，具体函数如下：structPcharname10;floatarrivetime;floatservicetime;floatstarttime;floatfinishtime;floatzztime;floatdqzztime;定义函数参数中进程的名字“name”、进程到达的时间“arrivetime”、进程所需服务时间“servicetime”、以及处理时间“starttime”和完成时间“finishtime”。Input函数接收用户键盘输入的进程

10、各个参数并作为函数后期执行的引用数据，包括进程的名称、到达时间、要求服务时间。for(i=0;i=N-1;i+)printf(请输入第d个进程的进程名：n,i+1);scanf(%s,&);printf(请输入第d个进程的到达时间:n,i+1);scanf(%f,&pi.arrivetime);printf(请输入第d个进程的要求服务的时间:n,i+1);scanf(%f,&pi.servicetime);由此函数可实现对用户所输入的数据的接收功能。sort(P*p,intN),run(P*p,intN)函数实现对进程响应比的计算和排序。首先利用公式“优先权=(等待时间+要求服务

11、时间)/要求服务时间=响应时间/要求服务时间”计算用户输入的进程的响应比,函数实现如下：for(inti=0;iN-1;i+)for(intj=i+1;jpj.arrivetime)Ptemp;temp=pi;pi=pj;pj=temp;intk;for(k=0;k=N-1;k+)if(k=0)pk.starttime=pk.arrivetime;pk.finishtime=pk.arrivetime+pk.servicetime;elsepk.starttime=pk-1.finishtime;pk.finishtime=pk-1.finishtime+pk.servicetime;for(

12、k=0;kFilesXBicrosoftVisualStudioMyPrjectsfgdDeliugfgd5*恒输入幕个进程的进程名：扁入第彳个进程的到达吋间=質输入第昇进程的芟求服务的时间=质输入第4个进程的进程名:质输入第4个进程的到达时间:鷺输入第4个进程的爰求略的时间:恒输入第弓个进程的进程名：肯输入第5个进程的到达时间=11眉输人第5个逬程的要求服务的时间:賃输入第6个进程的进程名:萝输/个进程的到达吋间:陰输入第百个进程的要求服务的吋间=确定后程序执行输出如下图：处】D:FrograaFilesMicrosoftVisualStudioMyFrojectsfgdDebug：.fgd

13、當坦傩傩皆的脅背W达达达达达进达达达达癘达达达成霾达达刻行行兀誓行g兀萍运已_K_K天天时运己己己未已璃运己己未已已止进进进进进瑁正进进进进进睜正进进进进进dlabCJIBEt-MlablcilJEd圣btjledla-行运己己正进进心B：PrograFilesIicrosoftVisualStu.d_iolyPr&jec-tsVfgd.DebugXffi达达达成施达达成成壷达成成成成行亠兀據一仃iass兀轄行到asss兀潼己已希已己讷运己己己己已四国己己已已已正逬进进进进筠正进进逬逬进磅止进进进进磁匚GE書dFlf-ld-Qh-hvEfdahC进程运行的顺序为:a-a-h-c-e-进程运行的

14、详细信息如下：D:PrograiFilesVIicrosoftVisualSudiolyProjectsfgdDebuged”进槿己完成惟程运行的顺序Sj：d-a-b-c-e-F怙程运行的详细信息如下：讷称到达时间服务时间开始时间结東时间d3.004.003.007.00a石005.097.30b8.092.0012.0014.00c9.095.0914.9019.90e11.806.0019.0025.00f15阿033.90宙称周转吋间带权周转时间d4-091-09a6-001-20h氣师3眄0c10-392-03e14-392-33f18-992-25Pressanpkeytoconti

15、nue源程序的代码#includestructPcharname10;floatarrivetime;floatservicetime;floatstarttime;floatfinishtime;floatzztime;floatdqzztime;Pa100;voidinput(P*,int);voidTraverse(P*,int);voidsort(P*,int);voidGrade(P*,int);voidmain()intN;printf(n);printf(ttt模拟高响应比调度算法n);printf(n);printf(NOW!模拟开始:n);printf(n);printf(请

16、输入需要服务的进程的个数:n);scanf(%d,&N);input(a,N);Grade(a,N);voidinput(P*p,intN)inti;for(i=0;i=N-1;i+)printf(请输入第d个进程的进程名：n,i+1);scanf(%s,&);printf(请输入第d个进程的到达时间:n,i+1);scanf(%f,&pi.arrivetime);printf(请输入第d个进程的要求服务的时间:n,i+1);scanf(%f,&pi.servicetime);voidTraverse(P*p,intN)intk;printf(n);printf(n);print

17、f(进程运行的顺序为:)；printf(%s,);for(k=1;k%s,);printf(n);printf(n);printf(进程运行的详细信息如下:n);printf(n);prinf(名称到达时间服务时间开始时间结束时间n);for(k=0;k=N-1;k+)printf(%st%-.2ft%-.2ft%-.2ft%-.2ftn,,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime);prinf(名称周转时间带权周转时间n);for(k=0;k=N-1;k+)printf(%st%-

18、.2ft%-.2ftn,,pk.zztime,pk.dqzztime);voidsort(P*p,intN)for(inti=0;iN-1;i+)for(intj=i+1;jpj.arrivetime)Ptemp;temp=pi;pi=pj;pj=temp;voidrun(P*p,intN)intk;for(k=0;k=N-1;k+)if(k=0)pk.starttime=pk.arrivetime;pk.finishtime=pk.arrivetime+pk.servicetime;elsepk.starttime=pk-1.finishtime;pk.finishtime=p

19、k-1.finishtime+pk.servicetime;for(k=0;k=N-1;k+)pk.zztime=pk.finishtime-pk.arrivetime;pk.dqzztime=pk.zztime/pk.servicetime;voidGrade(P*p,intN)floatarrivetime=0;floatservicetime=0;floatstarttime=0;floatfinishtime=0;floatzztime=0;floatdqzztime=0;sort(p,N);printf(n);printf(n);for(intm=0;mN-1;m+)if(m=0)p

20、m.finishtime=pm.arrivetime+pm.servicetime;printf(”在第%-.0f时刻进程信息n,pm.arrivetime);elsepm.finishtime=pm-1.finishtime+pm.servicetime;printf(在第%-.0f时刻进程信息n,pm-1.finishtime);inti=0,n;printf(%s正在运行n,);for(n=m+1;n=N-1;n+)if(pn.arrivetime=pm.finishtime)printf(%s进程已到达n,);i+;elseprintf(%s进程未到达n,);for(intl=0;lm;l+)printf(%s进程已完成n,);flo