操作系统课程设计
采用高响应比算法的进程调度程序
学 院
专 业
学 生 姓 名
学 号
指导教师姓名
2014 年 3月 18日
目 录
一、 实验题目 ........................................... 3
二、 课程设计的目的 ..................................... 3
三、 设计内容 ........................................... 3
四、 程序功能分析 ....................................... 3
五、 实验原理 ........................................... 3
六、 设计要求 ........................................... 6
七、 程序总设计流程图 ................................... 6
八、 程序运行结果及分析 ................ 错误！未定义书签。
九、 心得体会 .......................... 错误！未定义书签。
十、 源代码 ............................................. 9
十一、参考文献............................................13
一、实验题目
采用高响应比算法的进程调度程序
二、课程设计的目的：
了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。同时提高了同学的动手能力和团队合作精神，充分体现了合作的重要性。编写程序，采用高响应比作业调度算法，首先要确定作业控制块的内容和组成方式；然后完成作业调度，最后编写主函数，对所做工作进行测试。
(1)进一步巩固和复习操作系统的基础知识。
(2)培养学生结构化程序、模块化程序设计的方法和能力。
(3)提高学生调试程序的技巧和软件设计的能力.
(4)提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。操作系统课程设计是计算机专业重要的教学环节，它为学生提供
三、设计内容：
设计并实现一个采用高响应比算法的进程调度演示程序，响应比 R 定义如下:R=(W+T)/T=1+W/T,其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T 也就随着增加，也就有机会获得调度执行。 这种算法是介于 FCFS 和 SJF 之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于 SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。
四、程序功能分析
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。于是我们想到了一种办法解决这个问题，就是引用动态优先权、并使作业的优先级随着等待时间的增加而以速率a提高，长作业在等待一定的时间后，必然有机会分配到处理机，这样长作业也得到了运行。由此可见：
（1）如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因此该算法有利于短作业。
（2）当要求服务的时间相同时，作业的优先权取决与其等待的时间，等待时间越长，其优先权越高，因而它实现的是先来先服务。
（3）对于长作业，作业的优先权可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可以获得处理机。
五、实验原理
高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综
合了先来先服务和最短作业优先两种算法的特点。该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：响应比 =（等待时间+要求服务时间）/ 要求服务时间,即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
所以响应比为（等待时间+要求服务时间）\要求服务时间=等待时间/要求服务时间+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结束
高响应比函数执行过程流程图：
六、设计要求：
1. 每一个进程有一个PCB，其内容可以根据具体情况设定。
2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定
3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化
4. 可以在运行中显示各进程的状态：就绪、执行 （由于不要求设置互斥资源与进程间的同步关系，故只有两种状态）
5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列
6. 有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间
7. 具有一定的数据容错性
七、程序总设计流程图
八、程序运行结果及分析
输入两个进程a、b，在高响应比调度算法下的进程运行情况及各进程的性能分析如下：
输入四个进程Ａ、Ｂ、Ｃ、Ｄ在高响应比算法下的调度顺序，通过响应比（优先权）的比较，判断进程调度的次序，提高的进程的调度性能。且高响应比调度算法适合于批处理操作。
九、心得体会
通过这两周的课程设计实验，学到了很多很多的东西。不仅巩固了自己之前所学过的东西，而且也学到了很多书本上所没有学到过的知识。最重要的是，对高响应比算法的优先调度算法有了更深入的理解和掌握：高响应比的基本思想是把CPU分配给就绪队列中响应比最高的进程，既考虑了作业的执行时间也考虑了作业的等待时间等等。进一步巩固和复习了操作系统的基础知识，更进一步的了解了结构化模块化程序设计的方法，提高了调试程序的技巧。同时使我们对进程调度模拟设计的各种算法有了更进一步的理解，在编写程序时所遇到的问题让我有了对操作系统更深层次的理解和掌握，知道操作系统这门课程实在是很重要的一门课程。也懂得了理论与实践相结合是很重要的，只有理论知识是远远不够的，只有理论和实践相结合，才能调高自己的实际动手能力和独立思考能力。
十、源代码
#include
int e=0;
struct P
{
char name[10];
float arrtime;
float sertime;
float startime;
float finishtime;
float zztime;
float dqzztime;
float power;
};
P a[100];
void input(P *,int);
void move(P *,int);
void work(P *,int);
void Gxyb(P *,int);
void rate(P *,float);
void main()
{
int N;
printf("\t ***********欢迎进入高响应比调度算法模拟界面********** \n");
printf("请输入进程的个数:");
scanf("%d",&N);
input (a,N);
Gxyb(a,N);
}
void input(P *p,int N)
{
int i;
for(i=0;i
{
printf("\n\t请输入第%d个进程的名字，到达时间，要求服务的时间 :\n",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrtime,&p[i].sertime);
}
}
void work(P *p,int N)
{
for(int i=0;i
for(int j=i+1;j
if(p[i].arrtime>p[j].arrtime)
{
P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
else
if(p[i].arrtime==p[j].arrtime)
{ if(p[i].sertime>p[j].sertime)
{ P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
void rate(P *p,int N)
{ ++e;
for(int m=N-1;m>=e;m--)
if(p[m].arrtime
p[m].power=(p[e-1].finishtime-p[m].arrtime+p[m].sertime)/p[m].sertime;
for(int i=e;i
for(int j=i+1;j
if(p[i].power
{
P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
void move(P *p,int N)
{
int k;
printf("\n高响应比调度的顺序:");
printf("%s",p[0].name);
for(k=1;k
{
printf("->%s",p[k].name);
}
printf("\n");
printf("\n各进程运行的详细信息如下:\n");
printf("名称 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");
for(k=0;k
{
printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrtime,p[k].sertime,p[k].startime,p[k].finishtime,p[k].zztime,p[k].dqzztime); }
}
void deal(P *p,int N)
{
int k;
for(k=0;k
{
if(k==0)
{
p[k].startime=p[k].arrtime;
p[k].finishtime=p[k].arrtime+p[k].sertime;
}
else
{ if(p[k].arrtime
p[k].startime=p[k-1].finishtime;
else
p[k].startime=p[k].arrtime;
p[k].finishtime=p[k].startime+p[k].sertime;
}
}
for(k=0;k
{
p[k].zztime=p[k].finishtime-p[k].arrtime;
p[k].dqzztime=p[k].zztime/p[k].sertime;
}
}
void Gxyb(P *p,int N)
{ int i=0,n;
float arrtime=0,sertime=0,startime=0,finishtime=0,zztime=0,dqzztime=0; printf("各进程的运行情况如下:\n");
work(p,N);
for(int m=0;m
{
if(m==0)
{
p[m].finishtime=p[m].arrtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m].arrtime);
printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{ if(p[n].arrtime==p[m].arrtime)
{
printf("%s\t进程已到达\n",p[n].name); }
else
printf("%s\t进程未到达\n",p[n].name);
}
}
else
{ rate(p, N);
if(p[m].arrtime
{
p[m].finishtime=p[m-1].finishtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m-1].finishtime); printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{ if(p[n].arrtime
printf("%s\t进程已到达\n",p[n].name);
else
printf("%s\t进程未到达\n",p[n].name);
}
}
else
{ p[m].finishtime=p[m].arrtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m].arrtime); printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{
if(p[n].arrtime
{
printf("%s\t进程已到达\n",p[n].name);
}
else
printf("%s\t进程未到达\n",p[n].name);
}
}
}
for(int l=0;l
{
printf("%s\t进程已完成\n",p[l].name);
}
deal(p,N);
}
move(p,N);
}
参考文献：
C语言程序设计教程（第三版） 谭浩强 张基温 高等教育出版社
计算机操作系统（第三版） 汤小丹 梁红兵等 西安电子科技大学出版社
操作系统课程设计
采用高响应比算法的进程调度程序
学 院
专 业
学 生 姓 名
学 号
指导教师姓名
2014 年 3月 18日
目 录
一、 实验题目 ........................................... 3
二、 课程设计的目的 ..................................... 3
三、 设计内容 ........................................... 3
四、 程序功能分析 ....................................... 3
五、 实验原理 ........................................... 3
六、 设计要求 ........................................... 6
七、 程序总设计流程图 ................................... 6
八、 程序运行结果及分析 ................ 错误！未定义书签。
九、 心得体会 .......................... 错误！未定义书签。
十、 源代码 ............................................. 9
十一、参考文献............................................13
一、实验题目
采用高响应比算法的进程调度程序
二、课程设计的目的：
了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。同时提高了同学的动手能力和团队合作精神，充分体现了合作的重要性。编写程序，采用高响应比作业调度算法，首先要确定作业控制块的内容和组成方式；然后完成作业调度，最后编写主函数，对所做工作进行测试。
(1)进一步巩固和复习操作系统的基础知识。
(2)培养学生结构化程序、模块化程序设计的方法和能力。
(3)提高学生调试程序的技巧和软件设计的能力.
(4)提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。操作系统课程设计是计算机专业重要的教学环节，它为学生提供
三、设计内容：
设计并实现一个采用高响应比算法的进程调度演示程序，响应比 R 定义如下:R=(W+T)/T=1+W/T,其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。 每当要进行作业调度时，系统计算每个作业的响应比，选择其中 R 最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T 也就随着增加，也就有机会获得调度执行。 这种算法是介于 FCFS 和 SJF 之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于 SJF 法，从而采用 HRRN 方式时其吞吐量将小于采用 SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。
四、程序功能分析
在批处理系统中，短作业优先算法是一种比较好的算法，其主要的不足之处是长作业的运行得不到保证。于是我们想到了一种办法解决这个问题，就是引用动态优先权、并使作业的优先级随着等待时间的增加而以速率a提高，长作业在等待一定的时间后，必然有机会分配到处理机，这样长作业也得到了运行。由此可见：
（1）如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因此该算法有利于短作业。
（2）当要求服务的时间相同时，作业的优先权取决与其等待的时间，等待时间越长，其优先权越高，因而它实现的是先来先服务。
（3）对于长作业，作业的优先权可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可以获得处理机。
五、实验原理
高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综
合了先来先服务和最短作业优先两种算法的特点。该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：响应比 =（等待时间+要求服务时间）/ 要求服务时间,即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
所以响应比为（等待时间+要求服务时间）\要求服务时间=等待时间/要求服务时间+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结束
高响应比函数执行过程流程图：
六、设计要求：
1. 每一个进程有一个PCB，其内容可以根据具体情况设定。
2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定
3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化
4. 可以在运行中显示各进程的状态：就绪、执行 （由于不要求设置互斥资源与进程间的同步关系，故只有两种状态）
5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列
6. 有性能比较功能，可比较同一组数据在不同调度算法下的平均周转时间
7. 具有一定的数据容错性
七、程序总设计流程图
八、程序运行结果及分析
输入两个进程a、b，在高响应比调度算法下的进程运行情况及各进程的性能分析如下：
输入四个进程Ａ、Ｂ、Ｃ、Ｄ在高响应比算法下的调度顺序，通过响应比（优先权）的比较，判断进程调度的次序，提高的进程的调度性能。且高响应比调度算法适合于批处理操作。
九、心得体会
通过这两周的课程设计实验，学到了很多很多的东西。不仅巩固了自己之前所学过的东西，而且也学到了很多书本上所没有学到过的知识。最重要的是，对高响应比算法的优先调度算法有了更深入的理解和掌握：高响应比的基本思想是把CPU分配给就绪队列中响应比最高的进程，既考虑了作业的执行时间也考虑了作业的等待时间等等。进一步巩固和复习了操作系统的基础知识，更进一步的了解了结构化模块化程序设计的方法，提高了调试程序的技巧。同时使我们对进程调度模拟设计的各种算法有了更进一步的理解，在编写程序时所遇到的问题让我有了对操作系统更深层次的理解和掌握，知道操作系统这门课程实在是很重要的一门课程。也懂得了理论与实践相结合是很重要的，只有理论知识是远远不够的，只有理论和实践相结合，才能调高自己的实际动手能力和独立思考能力。
十、源代码
#include
int e=0;
struct P
{
char name[10];
float arrtime;
float sertime;
float startime;
float finishtime;
float zztime;
float dqzztime;
float power;
};
P a[100];
void input(P *,int);
void move(P *,int);
void work(P *,int);
void Gxyb(P *,int);
void rate(P *,float);
void main()
{
int N;
printf("\t ***********欢迎进入高响应比调度算法模拟界面********** \n");
printf("请输入进程的个数:");
scanf("%d",&N);
input (a,N);
Gxyb(a,N);
}
void input(P *p,int N)
{
int i;
for(i=0;i
{
printf("\n\t请输入第%d个进程的名字，到达时间，要求服务的时间 :\n",i+1);
scanf("%s%f%f",&p[i].name,&p[i].arrtime,&p[i].sertime);
}
}
void work(P *p,int N)
{
for(int i=0;i
for(int j=i+1;j
if(p[i].arrtime>p[j].arrtime)
{
P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
else
if(p[i].arrtime==p[j].arrtime)
{ if(p[i].sertime>p[j].sertime)
{ P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
void rate(P *p,int N)
{ ++e;
for(int m=N-1;m>=e;m--)
if(p[m].arrtime
p[m].power=(p[e-1].finishtime-p[m].arrtime+p[m].sertime)/p[m].sertime;
for(int i=e;i
for(int j=i+1;j
if(p[i].power
{
P temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
void move(P *p,int N)
{
int k;
printf("\n高响应比调度的顺序:");
printf("%s",p[0].name);
for(k=1;k
{
printf("->%s",p[k].name);
}
printf("\n");
printf("\n各进程运行的详细信息如下:\n");
printf("名称 到达时间 服务时间 开始时间 结束时间 周转时间 带权周转时间\n");
for(k=0;k
{
printf("%s\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t%-.2f\t\n",p[k].name,p[k].arrtime,p[k].sertime,p[k].startime,p[k].finishtime,p[k].zztime,p[k].dqzztime); }
}
void deal(P *p,int N)
{
int k;
for(k=0;k
{
if(k==0)
{
p[k].startime=p[k].arrtime;
p[k].finishtime=p[k].arrtime+p[k].sertime;
}
else
{ if(p[k].arrtime
p[k].startime=p[k-1].finishtime;
else
p[k].startime=p[k].arrtime;
p[k].finishtime=p[k].startime+p[k].sertime;
}
}
for(k=0;k
{
p[k].zztime=p[k].finishtime-p[k].arrtime;
p[k].dqzztime=p[k].zztime/p[k].sertime;
}
}
void Gxyb(P *p,int N)
{ int i=0,n;
float arrtime=0,sertime=0,startime=0,finishtime=0,zztime=0,dqzztime=0; printf("各进程的运行情况如下:\n");
work(p,N);
for(int m=0;m
{
if(m==0)
{
p[m].finishtime=p[m].arrtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m].arrtime);
printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{ if(p[n].arrtime==p[m].arrtime)
{
printf("%s\t进程已到达\n",p[n].name); }
else
printf("%s\t进程未到达\n",p[n].name);
}
}
else
{ rate(p, N);
if(p[m].arrtime
{
p[m].finishtime=p[m-1].finishtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m-1].finishtime); printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{ if(p[n].arrtime
printf("%s\t进程已到达\n",p[n].name);
else
printf("%s\t进程未到达\n",p[n].name);
}
}
else
{ p[m].finishtime=p[m].arrtime+p[m].sertime;
printf("\n在第%-.0f时刻进程信息\n",p[m].arrtime); printf("%s\t正在运行\n",p[m].name);
for(n=m+1;n
{
if(p[n].arrtime
{
printf("%s\t进程已到达\n",p[n].name);
}
else
printf("%s\t进程未到达\n",p[n].name);
}
}
}
for(int l=0;l
{
printf("%s\t进程已完成\n",p[l].name);
}
deal(p,N);
}
move(p,N);
}
参考文献：
C语言程序设计教程（第三版） 谭浩强 张基温 高等教育出版社
计算机操作系统（第三版） 汤小丹 梁红兵等 西安电子科技大学出版社