最高响应比调度算法代码.doc

实验四 模拟处理机HRRN调度算法

一、实验目的：用c++设计HRRN调度算法程序。
二、实验内容：本实验随机输入的进程个数、进程名称、进程提交到系统的时间、进程运行所需时间。通过模拟程序。显示以下信息：
1）处理机对进程的调度过程。
2）计算这N个进程的平均周转时间。
三、HRRN（最高响应比调度算法）原理
最高响应比调度：在每次调度作业时，先计算后备队中每个作业的响应比，然后挑选响应比高者投入运行。
响应比R定义：
R＝(w＋S)/S
(R:响应比,W＝等待时间,S＝运行时间)
响应比R= 周转时间 / 运行时间
=（运行时间 + 等待时间）/ 运行时间
= 1 +（等待时间 / 运行时间）

四、示例

如：输入
进程个数：5

进程名称 到达系统时间 所需服务时间
A 0 3
B 2 6
C 4 4
D 6 5
E 8 2

显示运行结果：
进程名称 到达系统时间 所需服务时间 开始时间 结束时间
A 0 3 0 3
B 2 6 3 9
C 4 4 9 13
E 8 2 13 15
D 6 5 15 20
5个进程的平均周转时间：（3+7+9+7+14）/5=8

五、运行结果

六、代码
#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
char name[10];
int into;
int runtime;
int start;
int finish;
int status;
int hrrn;
int sum;
}Node;

int select(Node node[],int n)
{
int i,flag=0;
for(i=0;i<n;i++)
{
if(0==node[i].status)
{
flag=1;
break;
}
}
if(1==flag)
return i;
else
return -1;
}

int compute(Node node,int t)
{
return (node.runtime+t-node.into)/node.runtime;
}

int main()
{
int n,i,j,max,t=0;
Node node[100];
printf("输入处理进程的个数：\n");
scanf("%d",&n);
getchar();
printf("进程名称 到达系统时间 所需服务时间\n");
for(i=0;i<n;i++)
{
scanf("%s",node[i].name);
scanf("%d",&node[i].into);
scanf("%d",&node[i].runtime);
getchar();
node[i].status=0;
if(0==i)
node[i].hrrn=0;
}
while(1)
{
int index;
index=select(node,n);
int flag=0;
if(index==-1)
break;
max=0;
for(i=0;i<n;i++)
{
if(node[i].into<=t&&0==node[i].status)
{
node[i].hrrn=compute(node[i],t);
if(0==i)
node[i].hrrn=0;
if(node[i].hrrn>node[max].hrrn)
max=i;
flag=1;
}
}
if(1==flag)
{
node[max].start=t;
t+=node[max].runtime;
node[max].status=1;
node[max].finish=t;
node[max].sum=node[max].finish-node[max].into;
}
else
{
t++;
}
}
for(i=0;i<n-1;i++)
{
for(j=i;j<n-1;j++)
{
if(node[j].finish>node[j+1].finish)
{
Node temp=node[j];
node[j]=node[j+1];
node[j+1]=temp;
}
}
}
printf("进程名称 到达系统时间 所需服务时间 开始时间 结束时间\n");
double sum=0;
for(i=0;i<n;i++)
{
printf("%s%12d%16d%12d%12d\n",node[i].name,node[i].into,node[i].runtime,node[i].start,node[i].finish);
sum+=node[i].sum;
}

printf("平均周转时间:%.2lf\n",sum/n);
return 0;
}