《响应比最高者优先算法.docx》由会员分享，可在线阅读，更多相关《响应比最高者优先算法.docx（8页珍藏版）》请在三一办公上搜索。
1、响应比最高者优先算法实验题目:响应比最高者优先算法 一、 实验目的 熟悉操作系统作业管理步骤，用C语言编程模拟实现响应比最高者优先算法。 二、 实验环境及仪器设备 硬件环境：IBM-PC或兼容机 软件环境：C语言编程环境 三、 实验算法思想 最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，
2、从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加 (1)等待时间相等时。则服务时间越
3、短，优先级越高，符合SJF思想。 (2)服务时间相等时，则等待时间越长，优先级越高，符合FCFS思想。 (3)对于长作业，只要其等待时间足够长，也能获得处理机。 四、 实验步骤 实验中，作业控制块及队列的数据结构定义如下： struct task string name; /*作业号*/ int arrTime; /* 作业到达时间*/ int serTime; /*作业要求服务时间*/ int waiTime; /*等待时间*/ int begTime; /*开始运行时间*/ int finTime; /*结束运行时间*/ int turTime; /*周转时间*/ int wTuTime;
4、 /*带权周转时间*/ int priority;/*优先权*/ int finish;/*是否已经完成*/ JCB10; 存放作业控制块的区域： #define n 10 JCB jobtable10; int jobcount; 将作业控制块组织成一个队列，实验中采用静态链表的方式模拟作业的后备队列，作业队列头指针定义为：int *head; 实验中，内存采用可移动的动态分区管理方法，即只要内存空闲区总和作业大就可以满足作业对内存的需求；对打印机和磁带机这两种独占设备采用静态分配法，即作业执行前必须获得所需资源，并且执行完才归还。 采用响应比高者优先调度算法进行调度时，必须计算出系统中所有
5、满足必要条件作业的响应比，从中选择响应比最高的一个作业装入主存储器分配资源。由于是实验，所以就将作业控制块出队，并输出作业名代替装入处存储器，同时修改系统的资源数量。 HRN开始当前作业为依编号找到第一个还没执行的作业Y当前作业是最后一个作业N和下一个还没执行的作业比较N当前在上次作业被执行完之前到达YY同时到达N当前作业取较早到达且相应比较高的一个当前作业取相应比较高的一个当前作业取较早到达的一个返回这一次要执行的作业五、 实验清单 #include #include #include #include #include #include typedef char string10; /*
6、/定义string为含有10个字符元素的字符数组类型*/ struct task string name; /*作业号*/ int arrTime; /* 作业到达时间*/ int serTime; /*作业要求服务时间*/ int waiTime; /*等待时间*/ int begTime; /*开始运行时间*/ int finTime; /*结束运行时间*/ int turTime; /*周转时间*/ int wTuTime; /*带权周转时间*/ int priority;/*优先权*/ int finish;/*是否已经完成*/ JCB10; int num; void input i
7、nt i; system(cls); printf(n请输入作业数量: ); scanf(%d, &num); for(i=0;inum;i+) printf(n请输入作业 NO.%d:n,i); printf( 作业名称: ); scanf(%s,JCBi.name); printf( 到达时间: ); scanf(%d,&JCBi.arrTime); printf( 服务时间: ); scanf(%d,&JCBi.serTime); JCBi.priority = 0; JCBi.finish =0; int HRN(int pre) int current=1,i,j;/* 优先权 =(
8、等待时间+服务时间)/服务时间*/ for(i=0; inum; i+) JCBi.waiTime=JCBpre.finTime-JCBi.arrTime; /*等待时间 =上一个业的完成时间-到达时间*/ JCBi.priority=(JCBi.waiTime+JCBi.serTime)/JCBi.serTime; for(i=0; inum; i+) if(!JCBi.finish) current=i; /*找到第一个还没完成的作业*/ break; for( j=i; jnum; j+) /*和后面的作业比较*/ if( !JCBj.finish) /* 还没完成(运行)*/ if(J
9、CBcurrent.arrTime=JCBpre.finTime) /*如果作业在上一个作业完成之前到达*/ if(JCBj.arrTimeJCBcurrent.priority ) current=j;/* 找出到达时间在上一个作业完成之前，优先权高的作业*/ else /* 如果作业是在上一个作业完成之后到达*/ if(JCBj.arrTimeJCBcurrent.priority) current=j; /*找出服务时间比较短的一个*/ return current;/*返回当前作业*/ void runing(int i, int times, int pre, int staTime
10、, int endTime) if(times=0) JCBi.begTime=JCBi.arrTime; JCBi.finTime=JCBi.begTime+JCBi.serTime; JCBi.turTime=JCBi.serTime; JCBi.wTuTime=1.0; staTime=JCBi.begTime; else if(JCBi.arrTimeJCBpre.finTime) JCBi.begTime=JCBi.arrTime; else JCBi.begTime=JCBpre.finTime; JCBi.finTime=JCBi.begTime+JCBi.serTime; JC
11、Bi.turTime=JCBi.finTime-JCBi.arrTime; JCBi.wTuTime=JCBi.turTime/JCBi.serTime; if(times=num-1) endTime=JCBi.finTime; JCBi.finish=1; void print(int i,int times) if(times=0) printf( 名称 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间n); printf(%9s%9d%9d%9d%9d%9d%9dn, JCBi.name,JCBi.arrTime,JCBi.serTime, JCBi.begTime,JC
12、Bi.finTime,JCBi.turTime,JCBi.wTuTime); void check( ) int i; int staTime, endTime, sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime; int current=0, times=0, pre=0; JCBpre.finTime=0; for(i=0; inum; i+) JCBi.finish=0; staTime, endTime,sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime; curren
13、t=0; times=0; pre=0; JCBpre.finTime=0; printf(-n); for(i=0; inum; i+) JCBi.finish=0; staTime, endTime,sumTurTime=0.0, sumWTuTime=0.0, aveTurTime, aveWTuTime; current=0; times=0; pre=0; JCBpre.finTime=0; printf(n- HRRN -n); for(times=0; timesnum; times+) current=HRN(pre); runing(current, times, pre,
14、staTime, endTime); print(current, times); pre=current; for(i=0; inum; i+) sumTurTime+=JCBi.turTime; sumWTuTime+=JCBi.wTuTime; aveTurTime=sumTurTime/num; aveWTuTime=sumWTuTime/num; printf(计与平均值) %9d%9d%9d%9dn,NULL,sumTurTime,aveTurTime,aveWTuTime); printf(-n); void main char again; do system(cls); /*
15、清屏*/ printf(please input 4 groups of datas:n); input; check; printf(Continue.(Y/N): ); do again = getch; while(again!=Y & again!=y & again!=N & again!=n); while(again=Y | again=y); 六、 实验结果 七、 实验分析及心得体会 从运行结果得到调度序列结果为： X1X2X3 X1到达时间最早，服务时间也最短，其响应比最高； X2到达时间为22，但因X1早到达，所以开始时间为22，其服务时间为12，所以响应比X1小； X3到
16、达时间最迟，其响应比最小，所以在最后。 本次课程设计题目较为简单，主要是对优先级和最高响应比这两个算法的理解和对进程调度的功能以及进程调度算法有深入的理解。 在这次的课程设计中，让我感觉较为不满意的地方是，在课程设计开始之前我对于最高响应比优先法理解不熟悉，导致了响应比的计算错误，从而加大了完成代码的时间量。 对于这次出现的这个问题，使我有了对程序设计的严谨性，课本基础知识的理解程度上有了更深刻的认识，也让我明白到了基础知识的重要性。 完成此次课程实际之后，我对进程调度模拟设计的各种算法有了更进一步的理解，也加深了我对于C+面向对象方面的掌握，在编写程序中所遇到的问题让我有了对操作系统有了迫切要更深层次的掌握，并操作系统这门课程实在是很重要的一门课程。
