淮北师范大学计算机学院实验设计报告操作系统程序设计实验报告实验课题：高响应比调度算法所属学院：计算机科学与技术所属班级：11 级计算机非师姓名：李志国辅导老师：施汉琴2014 年 3 月 20 日精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 2 - 目录实验设计课题 第 03 页课程设计目的 第 03 页课程设计内容 第 03 页课程设计要求 第 04 页相关知识介绍 第 05 页程序功能说明 第 06 页各段程序说明 第 07 页设计的流程图 第 09 页程序执行截图 第 11 页源程序的代码 第 14 页实验小结体会 第 19 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 3 - 实验设计课题设计题目：采用高响应比算法的进程调度程序指导老师：施汉琴课程设计目的操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑， 将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。?进一步巩固和复习操作系统的基础知识。?培养学生结构化程序、模块化程序设计的方法和能力。?提高学生调试程序的技巧和软件设计的能力。?提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。课程设计内容问题分析：在批处理系统中， 短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。 于是我们想到了一种办法解决这个问题，就是引用动态优先权、 并使作业的优先级随着等待时间的增加而以速率a提高，长作业在等待一定的时间后， 必然有机会分配到处理机， 这样长作业也得到了运行。 由此可见：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 4 - （1）如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因此该算法有利于短作业。（2）当要求服务的时间相同时，作业的优先权取决与其等待的时间，等待时间越长，其优先权越高，因而它实现的是先来先服务。（3）对于长作业，作业的优先权可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可以获得处理机。设计内容：设计并实现一个采用高响应比算法的进程调度演示程序，响应比 R 定义如下：RWT/T1W/T 其中 T 为该作业估计需要的执行时间，为作业在后备状态队列中的等待时 W 间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。这样， 即使是长作业，随着它等待时间的增加， W/T 也就随着增加，也就有机会获得调度执行。这种算法是介于 FCFS 和 SJF 之间的一种折中算法。 由于长作业也有机会投入运行， 在同一时间内处理的作业数显然要少于 SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。课程设计要求1.每一个进程有一个PCB，其内容可以根据具体情况设定。2.进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定3.可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化4.可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间的同步关系，故只有两种状态）5.采用可视化界面， 可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 5 - 6.有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间7.具有一定的数据容错性相关知识介绍定义高响应比优先调度算法的基本思想是把CPU 分配给就绪队列中响应比最高的进程。基本思想短作业优先调度算法+ 动态优先权机制，既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。原理高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。该算法中的响应比是指作业等待时间与运行比值， 响应比公式定义如下： 响应比 =（等待时间 +要求服务时间）/ 要求服务时间 ,即 RR=（w+s）/s=1+w/s ，因此响应比一定是大于1 的。如实例：某系统有 3 个作业，系统确定它们在全部到达后，再开始采用响应比高者优先的调度算法，则它们的调度顺序是什么？各自的周转时间是什么？作业号 提交时间运行时间1 8.8 1.5 2 9.0 0.4 3 9.5 1.0 (1)如果都到达再算的话,等待时间 =最后一个的提交时间-该作业到达的时刻1: 9.5-8.8=0.7 2: 9.5-9=0.5 3: 0 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 6 - 所以响应比为（等待时间 +要求服务时间）要求服务时间 =等待时间 / 要求服务时间 +1 1: 0.7/1.5+1=1.47 2: 0.5/0.4+1=2.25 3:1 所以 2先运行 ,2 从 9.5开始运行到 9.9结束; 再以 9.9时刻算响应比 : 1:(9.9-8.8)/1.5+1=1.73 3:(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+1.0=11.7到 11.7结束优缺点短作业与先后次序的兼顾， 且不会使长作业长期得不到服务响应比计算系统开销，增加系统开销。适用场合批处理系统。程序功能说明程序通过定义调用函数，杜如用户从键盘输入的需要服务的进程的各项参数，并进行调度算法模拟。 首相对读入的进程各个参数进行保存，而后进行判断是否进入内存之中， 如果在内存之中则进行高响应比优先的的方式进行排队服务运行，如果没有进入内存，则进程等待。直到所有进程服务运行完毕为止。各个精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 7 - 函数都有各自的功能， 相互协调进行整体函数功能的实现。采用响应比高者优先调度算法进行调度时， 必须计算出系统中所有满足必要条件作业的响应比，从中选择响应比最高的一个作业装入主存储器分配资源。由于是实验， 所以就将作业控制块出队，并输出作业名代替装入处存储器，同时修改系统的资源数量。各段程序说明首先进行函数相关参数定义，具体函数如下：struct P char name10; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; ; 定义函数参数中进程的名字“name ” 、进程到达的时间“ arrivetime ” 、进程所需服务时间“ servicetime ” 、以及处理时间“ starttime”和完成时间“ finishtime” 。Input 函数接收用户键盘输入的进程各个参数并作为函数后期执行的引用数据，包括进程的名称、到达时间、要求服务时间。for(i=0;i=N-1;i+) printf( 请输入第 %d 个进程的进程名: n,i+1); scanf(%s,&pi.name); printf( 请输入第 %d 个进程的到达时间:n,i+1); scanf(%f,&pi.arrivetime); printf( 请输入第 %d 个进程的要求服务的时间:n,i+1); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 8 - scanf(%f,&pi.servicetime); 由此函数可实现对用户所输入的数据的接收功能。sort(P *p,int N)，run(P *p,int N)函数实现对进程响应比的计算和排序。首先利用公式“优先权 =（等待时间 +要求服务时间） / 要求服务时间 =响应时间 / 要求服务时间”计算用户输入的进程的响应比，函数实现如下：for(int i=0;iN-1;i+) for(int j=i+1;jpj.arrivetime) P temp; temp=pi; pi=pj; pj=temp; int k; for(k=0;k=N-1;k+) if(k=0) pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 9 - 计算的响应比进行比较， 结果根据需要进行排序响应比高的进程排在前面，响应比低的进程排在后面， 这样就可以使响应比搞得进程获得较高的优先权，能够先运行。最后通过函数 Grade(P *p,int N)来实现输出进程在各个时间短的运行状况，包括正在运行，正在等待和已到达状态。设计的流程图程序设计总流程图：读取进程判 断 进 程 是否进入内存对 响 应比 排序高的进程先运行等 待结 束是否开 始精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 10 - 高响应比函数执行过程流程图：开 始当前作业为依编号找到的第一个还未执行的作业当 前 作 业 是最后一个作业当前作业和下一个还没执行的作业比较当前作业在上次作业被执行完之前到达当 前 作 业取较早达到且响应比较高的一个当前作业取相应比较高的一个当前作业取较早到达的一个同时到达精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 11 - 程序执行截图用户手动输入进程的各项信息：返回 这一 次要执行的作业精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 12 - 确定后程序执行输出如下图：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 13 - 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 14 - 源程序的代码#include struct P char name10; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; ; P a100; void input(P *,int); void Traverse(P *,int); void sort(P *,int); void Grade(P *,int); void main() int N; printf(n); printf(ttt 模拟高响应比调度算法 n); printf(n); printf(NOW! 模拟开始 :n); printf(n); printf( 请输入需要服务的进程的个数:n); scanf(%d,&N); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 15 - input(a,N); Grade(a,N); void input(P *p,int N) int i; for(i=0;i=N-1;i+) printf( 请输入第 %d 个进程的进程名: n,i+1); scanf(%s,&pi.name); printf( 请输入第 %d 个进程的到达时间:n,i+1); scanf(%f,&pi.arrivetime); printf( 请输入第 %d 个进程的要求服务的时间:n,i+1); scanf(%f,&pi.servicetime); void Traverse(P *p,int N) int k; printf(n); printf(n); printf( 进程运行的顺序为 :); printf(%s,p0.name); for(k=1;k%s,pk.name); printf(n); printf(n); printf( 进程运行的详细信息如下:n); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 16 - printf(n); printf( 名称 到达时间服务时间开始时间 结束时间 n); for(k=0;k=N-1;k+) printf(%st%-.2ft%-.2ft%-.2ft%-.2ftn,pk.name,pk.arrivetime,pk.servicetime,pk.starttime,pk.finishtime); printf( 名称 周转时间带权周转时间 n); for(k=0;k=N-1;k+) printf(%st%-.2ft%-.2ftn,pk.name,pk.zztime,pk.dqzztime); void sort(P *p,int N) for(int i=0;iN-1;i+) for(int j=i+1;jpj.arrivetime) P temp; temp=pi; pi=pj; pj=temp; void run(P *p,int N) int k; for(k=0;k=N-1;k+) if(k=0) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 17 - pk.starttime=pk.arrivetime; pk.finishtime=pk.arrivetime+pk.servicetime; else pk.starttime=pk-1.finishtime; pk.finishtime=pk-1.finishtime+pk.servicetime; for(k=0;k=N-1;k+) pk.zztime=pk.finishtime-pk.arrivetime; pk.dqzztime=pk.zztime/pk.servicetime; void Grade(P *p,int N) float arrivetime=0; float servicetime=0; float starttime=0; float finishtime=0; float zztime=0; float dqzztime=0; sort(p,N); printf(n); printf(n); for(int m=0 ; mN-1 ; m+) if(m=0) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 18 - pm.finishtime=pm.arrivetime+pm.servicetime; printf( 在第%-.0f 时刻进程信息 n,pm.arrivetime); else pm.finishtime=pm-1.finishtime+pm.servicetime; printf( 在第%-.0f 时刻进程信息 n,pm-1.finishtime); int i=0,n; printf(%s 正在运行 n,pm.name); for(n=m+1;n=N-1;n+) if(pn.arrivetime=pm.finishtime) printf(%s 进程已到达 n,pn.name); i+; else printf(%s 进程未到达 n,pn.name); for(int l=0;lm;l+) printf(%s 进程已完成 n,pl.name); float max=(pm.finishtime-pm+1.arrivetime)/pm+1.servicetime; int follow=m+1; for(int k=m+1;km+i;k+) if(max=(pm.finishtime-pk+1.arrivetime)/pk+1.servicetime) max=(pm.finishtime-pk+1.arrivetime)/pk+1.servicetime; follow=k+1; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 19 页淮北师范大学11级计算机非师范程序设计实验报告- 19 - P temp; temp=pm+1; pm+1=pfollow; pfollow=temp; run(p,N); Traverse(p,N); 实验小结体会本次课程设计题目较为简单，主要是对优先级和最高响应比这两个算法的理解和对进程调度的功能以及进程调度算法有深入的理解。在这次的课程设计中，让我感觉较为不满意的地方是， 在课程设计开始之前我对于最高响应比优先法理解不熟悉， 导致了响应比的计算错误， 从而加大了完成代码的时间量。对于这次出现的这个问题， 使我有了对程序设计的严谨性， 课本基础知识的理解程度上有了更深刻的认识， 也让我明白到了基础知识的重要性。完成此次课程实际之后，我对进程调度模拟设计的各种算法有了更进一步的理解，也加深了我对于C+ 面向对象方面的掌握， 在编写程序中所遇到的问题让我有了对操作系统有了迫切要更深层次的掌握，并操作系统这门课程实在是很重要的一门课程。通过本次实验对用高响应比算法的优先调度算法有了更深入的理解和掌握，进一步巩固和复习操作系统的基础知识，更进一步的了解了结构化模块化程序设计的方法，提高了调试程序的技巧。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19 页，共 19 页