操作系统--最高响应比优先调度算法实验报告(广

1、操作系统一最高响应比优先调度算法实验报告（广西民大）进程调度模拟设计最高响应比优先调度算法实验报告一、实验题目与要求1、实验题目：加深对作业概念的理解。深入了解批处理系统如何组织作业、管理作业和调度作业。2、实验要求：编写程序完成批处理系统中的作业调度，要求采用响应比高者优先的作业调度算法。实现具体包括：首先确定作业控制块的内容和组成方式；然后完成作业调度；最后编写主函数，对所做工作进行测试。二、总的设计思想及语言环境、工具1、总的设计思想：最高响应比优先法(HRRN)是对FCFS方式和SJF方式的一种综合平衡。HRRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响

2、应比最高的作业投入执行。响应比R定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法,从而采用HRRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。2、语言环境：计算机基本配置要求：操作系统：WIN98/20

3、00/XP/2003等Windows平台内存：256MB及以上主存64KB（Memory）（以KB为单位分配）开发语言：VisualC+6.03、工具：Windows平台+VisualC+6.0三、数据结构与模块说明（功能与框图）作业调度的实现主要有两个问题：一个是如何将系统中的作业组织起来；另一个是如何进行作业调度。为了将系统中的作业组织起来，需要为每个进入系统的作业建立档案以记录和作业相关的信息，例如，作业名、作业所需资源、作业执行时间、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。这个记录作业相关信息的数据块称为作业控制块（JCB），并将系统中等待作业调

4、度的作业控制块组织成一个队列，这个队列称为后备队列。当进行作业调度时，从后备队列中查找选择作业。由于实验中没有实际作业，作业控制块中的信息内容只使用了实验中需要的数据。作业控制块中首先应该包括作业名；其次是作业所需资源（内存大小、打印机的数量和磁带机的数量）；采用响应比高者优先作业调度算法，为了计算响应比，还需要有作业的估计执行时间、作业在系统中的等待时间；另外，指向下一个作业控制块的指针必不可少。实验中，作业控制块及队列的数据结构定义如下：structtaskstringname;/*作业号*/intarrTime;/*作业到达时间*/intserTime;/*作业要求服务时间*/intwa

5、iTime;/*等待时间*/intbegTime;/*开始运行时间*/intfinTime;/*结束运行时间*/intturTime;/*周转时间*/intwTuTime;/*带权周转时间*/intpriority;/*优先权*/intfinish;/*是否已经完成*/JCB10;存放作业控制块的区域：#definen10JCBjobtable10;intjobcount;将作业控制块组织成一个队列，实验中采用静态链表的方式模拟作业的后备队列，作业队列头指针定义为：int*head;实验中，内存采用可移动的动态分区管理方法，即只要内存空闲区总和比作业大就可以满足作业对内存的需求；对打印机和磁带

6、机这两种独占设备采用静态分配法，即作业执行前必须获得所需资源，并且执行完才归还。采用响应比高者优先调度算法进行调度时，必须计算出系统中所有满足必要条件作业的响应比，从中选择响应比最高的一个作业装入主存储器分配资源。由于是实验，所以就将作业控制块出队，并输出作业名代替装入处存储器，同时修改系统的资源数量。最高响应比优先调度算法的作业调度程序流程图（如下）HRN四、参考源程序：#includevdosh>#include<time.h>#includevstdlib.h>#includevstdio.h>#includevconio.h>#includevstr

7、ing.h>typedefcharstring10;/*定义string为含有10个字符元素的字符数组类型*/structtaskstringname;/*作业号*/intarrTime;/*作业到达时间*/intserTime;/*作业要求服务时间*/intwaiTime;/*等待时间*/intbegTime;/*开始运行时间*/intfinTime;/*结束运行时间*/intturTime;/*周转时间*/intwTuTime;/*带权周转时间*/intpriority;/*优先权*/intfinish;/*是否已经完成*/JCB10;intnum;voidinput()inti;s

8、ystem("cls");printf("n请输入作业数量:");scanf("%d",&num);f0r(i=0;ivnum;i+)printf("n请输入作业NOd:n"j);printf("作业名称:");scanf("%s"JCBiname);printf("到达时间：");scanf("%d",&JCBi.arrTime);printf("服务时间:");scanf("%d&quo

9、t;,&JCBiserTime);JCBipriority=0;JCBifinish=0;intHRN(intpre)intcurrent=1,i,j;/*优先权=(等待时间+服务时间)/服务时间*/for(i=0;ivnum;i+)JCBiwaiTime=JCBprefinTime-JCBiarrTime;/*等待时间=上一个作业的完成时间-到达时间*/JCBi.priority=(JCBi.waiTime+JCBi.serTime)/JCBi.serTime;for(i=0;ivnum;i+)if(!JCBi.finish)current=i;/*找到第一个还没完成的作业*/bre

10、ak;for(j=i;jvnum;j+)/*和后面的作业比较*/if(!JCBj.finish)/*还没完成(运行)*/if(JCBcurrent.arrTime<=JCBpre.finTime)/*如果作业在上一个作业完成之前到达*/if(JCBj.arrTime<=JCBpre.finTime&&JCBj.priority>JCBcurrent.priority)current=j;/*找出到达时间在上一个作业完成之前，优先权高的作业*/else/*如果作业是在上一个作业完成之后到达*/if(JCBj.arrTime<JCBcurrent.arrTi

11、me)current=j;/*找出比较早到达的一个*/if(JCBj.arrTime=JCBcurrent.arrTime)/*如果同时到达*/if(JCBj.priority>JCBcurrent.priority)current=j;/*找出服务时间比较短的一个*/returncurrent;/*返回当前作业*/voidruning(inti,inttimes,intpre,intstaTime,intendTime)if(times=0)JCBi.begTime=JCBi.arrTime;JCBi.finTime=JCBi.begTime+JCBi.serTime;JCBi.tur

12、Time=JCBi.serTime;JCBiwTuTime=10;staTime=JCBi.begTime;elseif(JCBiarrTime>JCBprefinTime)JCBi.begTime=JCBi.arrTime;elseJCBi.begTime=JCBpre.finTime;JCBi.finTime=JCBi.begTime+JCBi.serTime;JCBi.turTime=JCBi.finTime-JCBi.arrTime;JCBi.wTuTime=JCBi.turTime/JCBi.serTime;if(times=num-1)endTime=JCBi.finTime

13、;JCBi.finish=1;voidprint(inti,inttimes)if(times=0)printf("名称到达时间服务时间开始时间完成时间周转时间带权周转时间匕")；printf("%9s%9d%9d%9d%9d%9d%9dn",JCBinameJCBiarrTimeJCBiserTime,JCBibegTimeJCBifinTimeJCBi.turTimeJCBiwTuTime);voidcheck()inti;intstaTime,endTime,sumTurTime=00,sumWTuTime=00,aveTurTime,aveWTu

14、Time;intcurrent=0,times=0,pre=0;JCBprefinTime=0;for(i=0;i<num;i+)JCBifinish=0;staTime,endTime,sumTurTime=0.0,sumWTuTime=0.0,aveTurTime,aveWTuTime;current=0;times=0;pre=0;JCBpre.finTime=0;printf("-n");for(i=0;ivnum;i+)JCBi.finish=0;staTime,endTime,sumTurTime=0.0,sumWTuTime=0.0,aveTurTime

15、,aveWTuTime;current=0;times=0;pre=0;JCBpre.finTime=0;printf("n-HRRN-n");for(times=0;times<num;times+)current=HRN(pre);runing(current,times,pre,staTime,endTime);print(current,times);pre=current;for(i=0;i<num;i+)sumTurTime+=JCBi.turTime;sumWTuTime+=JCBi.wTuTime;aveTurTime=sumTurTime/nu

16、m;aveWTuTime=sumWTuTime/num;printf("(计与平均值)%9d%9d%9d%9dn",NULL,sumTurTime,aveTurTime,aveWTuTime);printf("-n");voidmain()charagain;dosystem("cls");/*清屏*/printf("pleaseinput4groupsofdatas:n");input();check();printf("Continue.(Y/N):");doagain=getch();wh

17、ile(again!='Y'&&again!='y'&&again!='N'&&again!='n');while(again='Y'|again='y');五、运行结果与运行情况I'icro5ci卄VisualStudioCOMM0NMSDe¥9inDebugCpp2.exe"请输入作业数量：3作入业达务聘到服110XII作入业达务聘到册请入业达务第到服请-3820X23NHRBN名称至滋时间11222Sxix2（计勻平身值）服务时间101232开始时间ii22340完成时间21346660周转时间带权周转时间10123B20Cantinu.e-.-<¥/N>:六、运行结果分析：从运行结果得到调度序列结果为:X19X29X3X1到达时间最早，服务时间也最短，其响应比最高；X2到达时间为22，但因X1早到达，所以开始时间为22,其服务时间为12，所以响应比X1小；X3到达时间最迟，其响应比最小，所以在最后。七、自我评价与总结：本次课程设计题目较为简单，主要是对优先级和最高响应比