高响应比优先算法

算法思想

响应比算法：(服务时间+等待时间)/服务时间
先将作业按到达时间排序，并将条件最优的作业移动到第一位，之后每次调度作业都更新后面所有作业的响应比，并将最高的响应比往前移。

#include<iostream>
#include<iomanip>
#include<string.h>
using namespace std;
struct work{
	char name[20];//作业名 
	float arrive;//到达时间 
	float service;//服务时间 
	float finish;//完成时间 
	float T;//周转时间 
	float W;//带权周转时间 
	float waitTime;//等待时间 
	float H;//相应比 
};

int main(){
	int n;//作业数 
	struct work z[20];
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>z[i].name;	
	}
	
	for(int i=0;i<n;i++){
		cin>>z[i].arrive;
	}
	
	for(int i=0;i<n;i++){
		cin>>z[i].service;
	}
	
	struct work a=z[0];//用一个结构体存储z[0]或条件最优的作业的值 
	int min=0;//最优条件的作业的位置 
	for(int i=1;i<n;i++){
		if(a.arrive>=z[i].arrive&&a.service>z[i].service){//判断条件更小或相等的到达时间且更短的服务时间 
			a=z[i];
			min=i;
		}
	}
	swap(z[0],z[min]);//将条件最优作业换到z[0]位置 
	
	//从z[1]位置开始按到达时间从小到大排序 
	for(int i=1;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(z[i].arrive>z[j].arrive)
			swap(z[i],z[j]);
		}
	}
	
	//计算完成时间
	z[0].finish=z[0].arrive+z[0].service;
	for(int i=1;i<n-1;i++){	
		if(z[i-1].finish<z[i].arrive){//判断条件当前到达时间大于上个完成时间 
			z[i].finish=z[i].arrive+z[i].service;//改变完成时间算法 
			continue;//继续下一个循环 
		}
		
		//从i开始每次循环更新等待时间和相应比 
		for(int l=i;l<n;l++){
			z[l].waitTime=z[i-1].finish-z[l].arrive;
			z[l].H=(z[l].service+z[l].waitTime)/z[l].service;
		}
		
		//从i+1开始将更优作业往前移 
		for(int j=i+1;j<n;j++){
			if(z[j].arrive<=z[i-1].finish&&z[j].H>z[i].H){//判断条件到达时间更小或相等且响应比更大的作业
				swap(z[i],z[j]);
				for(int k=j;k>i+1;k--){
					if(z[k].arrive<z[k-1].arrive){
						swap(z[k],z[k-1]);
					}
					else{
						break;
					}
				}
			}
		}
		
		//按不同情况计算完成时间 
		if(z[i].arrive>z[i-1].finish){
			z[i].finish=z[i].arrive+z[i].service;
		}
		else{
			z[i].finish=z[i-1].finish+z[i].service;
		}
		
		//最后两个作业改变计算方式 
		if(i==n-2){
			if(z[i+1].arrive>z[i].finish){
				z[i+1].finish=z[i+1].arrive+z[i+1].service;
			}
			else{
				z[i+1].finish=z[i].finish+z[i+1].service;
			}	
		}
	} 
	
	//计算周转时间和带权周转时间 
	for(int i=0;i<n;i++){
		z[i].T=z[i].finish-z[i].arrive;
		z[i].W=z[i].T/z[i].service;
	}
	
	for(int i=1;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			if(z[i].arrive>z[j].arrive)
			swap(z[i],z[j]);
		}
	}
	
	cout<<"作 业 名：";
	for(int i=0;i<n;i++){
		cout<<z[i].name;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
		
	cout<<"到达时间：";
	for(int i=0;i<n;i++){
		cout<<z[i].arrive;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
		
	cout<<"服务时间：";
	for(int i=0;i<n;i++){
		cout<<z[i].service;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
		
	cout<<"完成时间：";
	for(int i=0;i<n;i++){
		cout<<z[i].finish;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
		
	cout<<"周转时间：";
	for(int i=0;i<n;i++){
		cout<<z[i].T;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
		
	cout<<"带权周转时间：";
	for(int i=0;i<n;i++){
		cout<<fixed<<setprecision(2)<<z[i].W;
		if(i!=n-1)
		cout<<" ";
	}
	cout<<endl;
	
	return 0;
}

最后

以上就是冷傲学姐为你收集整理的操作系统-高响应比优先调度算法高响应比优先算法的全部内容，希望文章能够帮你解决操作系统-高响应比优先调度算法高响应比优先算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。