BOOM，困到不行，这个写完就睡觉了，今天好像有点感冒 ，翘了晚上的课一直睡到10点起来，睡不着在写代码，现在又困了
高响应比算法，是一种动态调整优先级的算法，在上面介绍的PSA算法中，给每个作业安排一个优先级后，始终这个优先级不再改变，这有些不合理。
【高响应比优先调度算法(HRRN)】因为可能造成一个低优先级作业始终得不到执行。
为了解决这个问题，HRRN算法每次都计算作业的优先级，随着作业等待时间的变长，优先级不断的提高，所以能够得到更快的执行。
这个优先级可以描述为: 优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间
从上式可以看到，作业的服务时间是固定的， 优先级随着已等待时间的提高而变大
文章图片
//main.cpp
#include "HRRN.h"int main()
{
std::vector PCBList;
//输入作业信息
InputPCB(PCBList);
//HRRN算法
HRRN(PCBList);
//显示结果
show(PCBList);
return 0;
}//HRRN.h
#ifndef HRRN_H_
#define HRRN_H_#include
#include
#include
#include //作业结构体
typedef struct PCB
{
int ID;
//标识符
double Level;
//优先级
int ComeTime;
//到达时间
int ServerTime;
//服务时间
int FinishTime;
//完成时间
int TurnoverTime;
//周转时间
double WeightedTurnoverTime;
//带权周转时间
}PCB;
/*
函数功能：输入作业信息
参数说明：
PCBListstd::vector&PCB链
*/
void InputPCB(std::vector &PCBList);
/*
函数功能：HRRN算法
参数说明：
PCBListstd::vector&PCB链
*/
void HRRN(std::vector &PCBList);
/*
函数功能：计算优先级
参数说明：
bstd::vector::iterator起始位置
estd::vector::iterator结束位置
CurTime int当前时间
*/
void CalPriority(std::vector::iterator b, std::vector::iterator e, int CurTime);
/*
函数功能：显示结果
参数说明：
PCBListstd::vector&PCB链
*/
void show(std::vector &PCBList);
/*
函数功能：比较函数，用于sort()，按ComeTime升序排列
参数说明：
p1const PCB&PCB
p2const PCB&PCB
*/
bool CmpByComeTime(const PCB &p1, const PCB &p2);
/*
函数功能：比较函数，用于sort()，按Level降序排列
参数说明：
p1const PCB&PCB
p2const PCB&PCB
*/
bool CmpByLevel(const PCB &p1, const PCB &p2);
#endif//HRRN.cpp
#include "HRRN.h"//输入作业信息
void InputPCB(std::vector &PCBList)
{
do {
PCB temp;
std::cout << "输入标识符: ";
std::cin >> temp.ID;
std::cout << "输入到达时间: ";
std::cin >> temp.ComeTime;
std::cout << "输入服务时间: ";
std::cin >> temp.ServerTime;
PCBList.push_back(temp);
std::cout << "继续输入？Y/N: ";
char ans;
std::cin >> ans;
if ('Y' == ans || 'y' == ans)
continue;
else
break;
} while (true);
}//HRRN算法
void HRRN(std::vector &PCBList)
{
std::sort(PCBList.begin(), PCBList.end(), CmpByComeTime);
//按到达时间排序 //同时到达的按优先级降序排序，决定首先运行的作业
int i = 1;
std::vector::iterator it = PCBList.begin() + 1;
while ((*it).ComeTime == (*(it - 1)).ComeTime)
{
++i;
++it;
}
CalPriority(PCBList.begin(), PCBList.begin() + i, 0);
//计算优先级
std::sort(PCBList.begin(), PCBList.begin() + i, CmpByLevel);
int FinishTime = -1;
for (it = PCBList.begin();
it < PCBList.end();
++it)
{
if ((*it).ComeTime >= FinishTime)//没有作业正在运行，取队首作业运行
(*it).FinishTime = (*it).ComeTime + (*it).ServerTime;
else//有作业正在运行，等待作业完毕，此作业再运行
(*it).FinishTime = FinishTime + (*it).ServerTime;
(*it).TurnoverTime = (*it).FinishTime - (*it).ComeTime;
(*it).WeightedTurnoverTime = (double)(*it).TurnoverTime / (*it).ServerTime;
FinishTime = (*it).FinishTime;
//在一个作业运行期间，如果有其他作业到达，将他们按照优先级降序排列
i = 1;
while ((it + i) < PCBList.end() && (*(it + i)).ComeTime <= FinishTime)
++i;
CalPriority(it + 1, it + i, FinishTime);
std::sort(it + 1, it + i, CmpByLevel);
} std::sort(PCBList.begin(), PCBList.end(), CmpByComeTime);
//重新排列，用于显示结果
}//计算优先级
void CalPriority(std::vector::iterator b, std::vector::iterator e, int CurTime)
{
while (b < e)
{
(*b).Level = (double)((*b).ServerTime + (CurTime - (*b).ComeTime)) / (*b).ServerTime;
++b;
}
}//显示结果
void show(std::vector &PCBList)
{
int SumTurnoverTime = 0;
double SumWeightedTurnoverTime = 0;
std::cout.setf(std::ios::left);
std::cout << std::setw(20) << "标识符";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
std::cout << std::setw(5) << (*it).ID;
std::cout << std::endl;
std::cout << std::setw(20) << "到达时间";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
std::cout << std::setw(5) << (*it).ComeTime;
std::cout << std::endl;
std::cout << std::setw(20) << "服务时间";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
std::cout << std::setw(5) << (*it).ServerTime;
std::cout << std::endl;
std::cout << std::setw(20) << "完成时间";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
std::cout << std::setw(5) << (*it).FinishTime;
std::cout << std::endl;
std::cout << std::setw(20) << "周转时间";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
{
std::cout << std::setw(5) << (*it).TurnoverTime;
SumTurnoverTime += (*it).TurnoverTime;
;
}
std::cout << std::endl;
std::cout << std::setw(20) << "带权周转时间";
for (std::vector::iterator it = PCBList.begin();
it < PCBList.end();
++it)
{
std::cout << std::setw(5) << (*it).WeightedTurnoverTime;
SumWeightedTurnoverTime += (*it).WeightedTurnoverTime;
;
}
std::cout << std::endl;
std::cout << "平均周转时间: " << (double)SumTurnoverTime / PCBList.size() << std::endl;
std::cout << "平均带权周转时间: " << SumWeightedTurnoverTime / PCBList.size() << std::endl;
}//比较函数，按ComeTime升序排列
bool CmpByComeTime(const PCB &p1, const PCB &p2)
{
return p1.ComeTime < p2.ComeTime;
}//比较函数，按Level降序排列
bool CmpByLevel(const PCB &p1, const PCB &p2)
{
return p1.Level > p2.Level;
} 
