高响应比优先算法(c++)-创新互联

操作系统基本调度算法,高响应比算法。先来先服务和短作业优先策略都很可能会引起进程的饥饿现象,而高响应比算法在每次从就绪队列选择进程执行时,会计算各个进程的响应比,选出一个响应比最高的进程执行,响应比计算如下 :(等待时间+服务时间) / 服务时间

创新互联公司主要从事成都网站制作、成都网站建设、网页设计、企业做网站、公司建网站等业务。立足成都服务调兵山,十余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:028-86922220

这样的策略兼顾提高系统吞吐率与减少进程饥饿现象,当进程等待的越久,响应比越高,被执行的概率久越大,而服务时间要求短的进程本身具有较高响应比

定义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://scyanting.com/article/pdsgs.html