高响应比优先算法(c++)-创新互联
操作系统基本调度算法，高响应比算法。先来先服务和短作业优先策略都很可能会引起进程的饥饿现象，而高响应比算法在每次从就绪队列选择进程执行时，会计算各个进程的响应比，选出一个响应比最高的进程执行，响应比计算如下 ：(等待时间+服务时间) / 服务时间
这样的策略兼顾提高系统吞吐率与减少进程饥饿现象，当进程等待的越久，响应比越高，被执行的概率久越大，而服务时间要求短的进程本身具有较高响应比
定义pcb，作业完成队列。
输入进程信息，将所有进程按到达时间升序排序。
设置pcb数组存放已到达进程，当前时间current_time,下一个 要运行进程的序号next_process。
循环(如果还有进程未到达或未完成)
{
循环(还有进程未到达)
{ 将当前时间到达的进程加到pcb数组
}
更新各进程响应比
遍历已到达进程，找到下一个执行的进程序号(响应比最高)
执行进程，修改信息，插入完成队列
将完成了的进程与pcb数组最后一个进程调换，到达进程数-1(相当于删除)
}
代码实现如下
#include#define N 5 //进程数
#include#includeusing namespace std;
struct pcb
{
char process_name[10]; //进程名字
int arrive_time; //到达时间
int service_time; //需要服务时间
float response; //响应比
int complete_time; //完成时间
int round_time; //周转时间
float force_round_time; //带权周转时间
char state; //进程状态
}PCB[N + 1]; //0号单元不存数据,直接用作交换
queueFinish_queue; //已完成队列
void input(int n)
{
cout<< "\n请输入各进程的信息\n"<< endl;
for (int i = 1; i<= n; i++) //输入各进程信息
{
PCB[i].state = 'c'; //coming (未到达)
cout<< "------\n请输入第"<< i<< "进程名字: ";
cin >>PCB[i].process_name;
cout<< "请输入到达时间: ";
cin >>PCB[i].arrive_time;
cout<< "请输入服务时间: ";
cin >>PCB[i].service_time;
PCB[i].response = 1;
}
}
void sort(int n)
{
int i, j;
for (i = 1; i< n; i++) //按到达时间升序
{
for (j = 1; j<= n - i; j++)
{
if (PCB[j].arrive_time >PCB[j + 1].arrive_time)
{
PCB[0] = PCB[j];
PCB[j] = PCB[j + 1];
PCB[j + 1] = PCB[0];
}
}
}
}
void high_response(int n)
{
int current_time = 0; //系统时间
int i,
next_process, //下一个要运行进程的序号
arrived_process_num = 0, //已到达进程数
wait_process_num = 0; //正在等待的进程数
pcb wait_process_array[N + 1]; //存放已到达的进程
while (arrived_process_num< n || wait_process_num >0) //还有进程未到达或未运行
{ //如果还有进程未到达，将当前时间所有到达的进程加入等待数组
while (arrived_process_num< n && current_time >= PCB[arrived_process_num + 1].arrive_time)
{
wait_process_array[++wait_process_num] = PCB[++arrived_process_num];
}
for (i = 1; i<= wait_process_num; i++)
{
wait_process_array[i].response = //更新响应比
1.0*(current_time - wait_process_array[i].arrive_time + wait_process_array[i].service_time) / wait_process_array[i].service_time;
}
next_process = 1;
for (i = 2; i<= wait_process_num; i++)
{
if (wait_process_array[i].response >wait_process_array[next_process].response)
{
next_process = i; //找到下一个运行进程的序号
}
}
{
current_time += wait_process_array[next_process].service_time; //运行结束后的时间
wait_process_array[next_process].complete_time = current_time; //进程完成时间等于现在时间
wait_process_array[next_process].round_time = current_time - wait_process_array[next_process].arrive_time; //周转时间
wait_process_array[next_process].force_round_time = 1.0*wait_process_array[next_process].round_time / wait_process_array[next_process].service_time; //带权周转时间
wait_process_array[next_process].state = 'f'; //状态改为完成
wait_process_num--; //正在等待的进程数减一
Finish_queue.push(wait_process_array[next_process]); //插入完成队列
cout<< "\n第"<< Finish_queue.size()<< "次调度进程: "<< Finish_queue.back().process_name<< endl;
}
{ //将完成了的进程换到等待进程数组的下一个位置(相当于删除)
wait_process_array[0] = wait_process_array[next_process];
wait_process_array[next_process] = wait_process_array[wait_process_num + 1];
wait_process_array[wait_process_num + 1] = wait_process_array[0];
}
}
return;
}
void print(int n)
{
int i = 1;
float sum = 0; //存放各进程的带权周转时间和
cout<< "\n 进程 |"<< "到达时间 |"<< " 服务时间 |"<< " 完成时间 |"<< " 开始运行时的响应比 | "<< " 周转时间 |"<< " 带权周转时间"<< endl;
while (Finish_queue.empty() == false)
{
cout<< Finish_queue.front().process_name
<< "\t| "<< Finish_queue.front().arrive_time
<< "\t | "<< Finish_queue.front().service_time<< " \t | "<< Finish_queue.front().complete_time
<< "\t | "<< setprecision(3)<< Finish_queue.front().response
<< "\t\t | "<< Finish_queue.front().round_time
<< "\t | "<< Finish_queue.front().force_round_time
<< endl;
sum += Finish_queue.front().force_round_time;
Finish_queue.pop();
}
cout<< "\n\n系统平均带权周转时间: "<< (sum / n)<< endl;
}
int main()
{
input(N);
sort(N);
high_response(N);
print(N);
return 0;
} 
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：高响应比优先算法(c++)-创新互联
URL分享：http://shouzuofang.com/article/pdsgs.html