操作系统调度算法–高响应比优先调度算法解析

  高响应比优先调度算法（Highest Response Radio Next，HRRN）是一种对CPU中央控制器响应比的分配的算法。HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法。FCFS算法所考虑的只是作业等待时间，而忽视了作业的运行时间（类似我们在生活中排队买东西）。而SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。

  而高响应比优先算法，则是考虑了作业的等待时间，又考虑了作业运行时间的调度算法，因此照顾了短作业，又不致使长作业等待时间过长，从而改善了处理机的调度的性能。

  这个算法相当于给与每个作业一个动态的优先级，这个优先级是随着时间变化的变化的，等待时间不断地增加，这将让长作业的优先级在等待期间不断地增大，等待足够的时间，必然会得到处理机。该优先级的变化规则可以描述为：

优先级 = （等待时间+要求服务时间）/要求服务时间。又因为，等待时间与要求服务时间之和为系统对作业的响应时间，所以优先级 = 响应时间/要求服务时间。

规律：1.作业的等待时间相同，则要求服务的越短，优先级越高，类似于SJF算法。2.当要求服务的时间相同时，等得越久优先级越高，类似于FCFS算法。3.对于长作业来说，该算法实现了较好的折中。

优点：算法折中，长短作业兼顾，时间分配较为均匀。

缺点：每次计算响应比都会花费一定时间，即时间开销，其性能比SJF算法略差。

下面有道例题，可参考：

算法代码：

#include

#define N 10

typedef struct {

int hour;

int min;

}time;

typedef struct hrrf{

char hrrf_id[20];

double hrrf_run;  //运行时间

time hrrf_entertime; //进入时间

int enter;

time hrrf_needtime;  //调度时间

int needtime;

time hrrf_endtime;   //结束时间

int endtime;

int hrrf_longtime;  //周转时间

int hrrf_waittime;   //等待时间

double hrrf_pjlongtime; //平均周转时间

double hrrf_rate;       //响应比

struct hrrf* next;

}HRRF;

//输入作业信息

void hrrfinput(HRRF s[N],int k)

{

printf(“\t请输入第%d个作业名：”,k+1);

scanf(“%s”,&s[k].hrrf_id);

printf(“\t请输入%s作业进入时间:”,s[k].hrrf_id);

scanf(“%d:%d”,&s[k].hrrf_entertime.hour,&s[k].hrrf_entertime.min);

s[k].enter=s[k].hrrf_entertime.hour*60+s[k].hrrf_entertime.min;

printf(“\t请输入%s作业运行时间：”,s[k].hrrf_id);

scanf(“%lf”,&s[k].hrrf_run);

}

//计算作业的响应比

void rate(HRRF s[N],int k,int m)

{

double ratenum;

ratenum = (s[k].hrrf_run+(double)(s[m].endtime-s[k].enter))/(s[k].hrrf_run);

s[k].hrrf_rate=ratenum;

printf(“\n\t每次算响应比：%s—%f\n”,s[k].hrrf_id,s[k].hrrf_rate);

}

//按响应比对作业进行排序（降序排序）

void ratesort(HRRF s[N],int k,int m)

{

int maxratenum;

HRRF temp;

int i,j;

for(i=k;i<m;i++)         //简单选择排序

{

maxratenum=i;

for(j=i+1;j<m;j++)

if(s[j].hrrf_rate>s[maxratenum].hrrf_rate)

maxratenum=j;

if(maxratenum!=i)

{

temp=s[i];

s[i]=s[maxratenum];

s[maxratenum]=temp;

}

}

}

//打印表单

void print(HRRF s[N],int k)

{

printf(“\t序号\t作业名\t进入时间\t调度时间\t结束时间\t运行时间\t等待时间\t周转时间\n”);

int i,j;

for(i=0;i<k;i++)

printf(“\t%d\t%s\t%d:%d\t\t%d:%d\t\t%d:%d\t\t%.0f min\t\t%d\t\t%d min\n”,i+1,s[i].hrrf_id,(s[i].enter/60),(s[i].enter%60), (s[i].needtime/60),(s[i].needtime%60),(s[i].endtime/60),(s[i].endtime%60),s[i].hrrf_run,s[i].hrrf_waittime,s[i].hrrf_longtime);

}

//hrrf算法

void HRRF_run(HRRF s[N],int k)

{

int i,j=k,n;

double sum;

HRRF temp;

//按到达时间进行排序

while(j>1)

{

for(i=0;i<j-1;i++)

{

if(s[i+1].enter<s[i].enter)

{

temp=s[i];

s[i]=s[i+1];

s[i+1]=temp;

}

}

j–;

}

printf(“\n\t——————————————–初始状态————————————————\n”);

print(s,k);

j=0;

//执行

do{

if(j==0)

{

s[j].needtime=s[j].enter;

s[j].hrrf_waittime=0;

s[j].endtime=s[j].enter+s[j].hrrf_waittime+(int)(s[j].hrrf_run);

s[j].hrrf_longtime=s[j].endtime-s[j].enter;

}

else

{

s[j].needtime=s[j-1].endtime;

s[j].hrrf_waittime=s[j-1].endtime-s[j].enter;

s[j].endtime=s[j].needtime+(int)(s[j].hrrf_run);

s[j].hrrf_longtime=s[j].endtime-s[j].enter;

}

j++;  //到了第几个作业

//计算响应比

n=j-1;  //此次已经执行完的作业序号-1，因为数组从0开始

for(i=j;i<k;i++)

{

rate(s,i,n);    //计算响应比

}

ratesort(s,j,k);    //按响应比由大到小排序

printf(“\n\t—————————————–每次响应比排序———————————————\n”);            print(s,k);

}while(j<k);

printf(“\n\t——————————————–作业调度————————————————\n”);

print(s,k);

for(i=0;i<k;i++)

{

sum+=(double)(s[i].hrrf_longtime);

}

printf(“\n\t平均周转时间为：%.2f\n”,sum/k);

}

int main()

{

HRRF a[N]={0};

int i,j;

printf(“请输入创建作业数为：”);

scanf(“%d”,&i);

for(j=0;j<i;j++)  //输入作业信息

hrrfinput(a,j);

//HRRF算法

HRRF_run(a,j);

return 0;

}