操作系统——优先权算法c++实现

变量描述

测试数据

5
A 0 4 4
B 1 3 2
C 2 5 3
D 3 2 5
E 4 4 1

先来先服务算法

简述

该算法实现非常简单就是对到达时间排个序，然后依次进行即可，对结构体的sort进行了重载

代码

void FCFS() {//先来先服务算法
	std::cout<<"\n\t\t\t\t\t先来先服务算法\n\n";
	double sum_cir_time=0;//总的周转时间
	double sum_pre_cir_time=0;//总的带权周转时间
	std::sort(work+1, work +1+ N,cmp1);//来的时间排序

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		work[i].start_time = work[i - 1].finish_time;
		work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id<<"\t"<<work[i].reach_time <<"\t\t"<<work[i].start_time <<"\t\t"<<
			work[i].need_time <<"\t\t"<<work[i].finish_time <<"\t\t"<<work[i].cir_time<<
			"\t\t"<<work[i].pre_cir_time<<"\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time*1.0/N << "\n";
}

短进程优先

简述

需要注意的是不是直接按照进程时间为关键字直接排序，而是对当前时刻的最短进程

例如下面示例

A 1 5
B 2 1

时间上b最短，但是a先来的，所以b要执行，就必须等a执行完毕，实现方式进行枚举，然后每次把当前时刻的进程较短的放入优先队列，使用的是优先队列的小根堆。

代码

void SPJF() {//短进程优先
	std::cout << "\n\t\t\t\t\t短进程优先服务算法\n\n";
	double sum_cir_time = 0;//总的周转时间
	int now_time=0,new_job=0;
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	//把开始时间小于目前时间的都丢到优先队列中
	std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > >q;
	std::queue<int>order_q;//用于获取编号的
	int ok = 0;//进程结束
	while (ok < N) {
		for (int i = 1; i <= N; i++) {
			if (!work[i].isvisited) {
				if (work[i].reach_time <= now_time) {//把小于当前时间已经到达的进程排序
					work[i].isvisited = 1;
					q.push({ work[i].need_time,work[i].kth});
				}
				else {
					break;//说明后面的进程是，谁先来设服务
				}
			}
		}
		if (q.empty()) {//队列为空说明应该执行先来先服务,当前时刻最短
			for (int i = 1; i <= N; i++) {
				if (!work[i].isvisited) {
					work[i].isvisited = 1;
					new_job = work[i].kth;//获取进程编号
					break;
				}
			}
		}
		else {
			new_job = q.top().second;
			q.pop();
		}
		order_q.push(new_job);
		ok++;
		work[new_job].start_time = std::max(now_time,work[new_job].reach_time);
		now_time=work[new_job].finish_time = work[new_job].start_time + work[new_job].need_time;
		work[new_job].cir_time = work[new_job].finish_time - work[new_job].reach_time;
		sum_cir_time += work[new_job].cir_time;
		work[new_job].pre_cir_time = work[new_job].cir_time * 1.0 / work[new_job].need_time;
		sum_pre_cir_time += work[new_job].pre_cir_time;
	}

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" <<
		sum_pre_cir_time * 1.0 / N << "\n";
}

优先权算法

（1）非抢占式

        非抢占式就跟短进程实现方式一样，一样使用优先队列，关键字按照优先权大小进行排序即可，每次把当前时刻，有先权比目前更大的丢到优先队列中

代码

void HPF() {
	
	std::cout << "\n\t\t\t\t\t优先权算法(数字小优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	int now_time=0,new_job=0;
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	//把开始时间小于目前时间的都丢到优先队列中
	
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >q;

	std::queue<int>order_q;//用于获取编号的
	int ok = 0;//进程结束
	while (ok < N) {
		for (int i = 1; i <= N; i++) {
			if (!work[i].isvisited) {
				if (work[i].reach_time <= now_time) {//把小于当前时间已经到达的进程排序
					work[i].isvisited = 1;
					q.push({ work[i].pre,work[i].kth});
				}
				else {
					break;//说明后面的进程是，谁先来设服务
				}
			}
		}
		if (q.empty()) {//队列为空说明应该执行先来先服务,当前时刻最短
			for (int i = 1; i <= N; i++) {
				if (!work[i].isvisited) {
					work[i].isvisited = 1;
					new_job = work[i].kth;//获取进程编号
					break;
				}
			}
		}
		else {
			new_job = q.top().second;
			q.pop();
		}
		order_q.push(new_job);
		ok++;
		work[new_job].start_time = std::max(now_time,work[new_job].reach_time);
		now_time=work[new_job].finish_time = work[new_job].start_time + work[new_job].need_time;
		work[new_job].cir_time = work[new_job].finish_time - work[new_job].reach_time;
		sum_cir_time += work[new_job].cir_time;
		work[new_job].pre_cir_time = work[new_job].cir_time * 1.0 / work[new_job].need_time;
		sum_pre_cir_time += work[new_job].pre_cir_time;
	}

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t优先权  \t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t"<<work[i].pre<<"\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";

	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";
}

（2）抢占式

这个比较麻烦，我的思路就是记录下当前时刻的时间，然后循环寻找到达时间小于当前时间的小的并且优先级别较大的，然后比较找到的id是不是目前执行的，如果不是，说明目前的进程会被打断，然后找出从当前时刻到他理想结束时刻的时间（只是理想，不一定会到达）在这个理想时间以内，如果这个时间内有进程来了，并且该进程的优先级更高，说明是目前需要被打段的，然后目前这个进程运行到的时间就是新进程到达的时间，如果没有优先级更高的化就把自己执行完毕

代码

void QHPF(){//优先权抢占式
	std::cout << "\n\t\t\t\t\t优先权抢占算法\n\n";
	double sum_cir_time = 0;//总的周转时间
	
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<int>order_q;
	int pre = 1e5;//记录实时的pre
	int ok = 0,now_time=0,now_id=0,lst_id=0;//当前时间，当前编号，上一次的编号
	while (ok < N) {
		pre = 1e5;
		for (int i = 1; i <= N; i++) {
			if (work[i].reach_time <= now_time) {//当前程序可以执行
				if (pre>work[i].pre&&!work[i].isvisited) {//更换优先级更高的
					pre = work[i].pre;
					now_id = work[i].kth;//当前要运行的程序
				}
			}
		}
		
		//std::cout << pre << " " << now_id << "\n";
		if (work[now_id].run_time == 0) {
				work[now_id].start_time = now_time;//该进程开始时在这时候介入
		}
		//std::cout << now_time << "\n";

		if (now_id != lst_id) {//还有进程可以执行
			int tmp_pre = pre;
			int tmp_id=now_id;
			for (int i = 1; i <= N; i++) {//从当前时刻到该作业结束，中间由优先级更高的插入
				if (now_time + work[now_id].need_time - work[now_id].run_time >= work[i].reach
					&& tmp_id != work[i].kth&&!work[i].isvisited&&tmp_pre>work[i].pre) {
					tmp_id = work[i].kth;
					tmp_pre = work[i].pre;
					break;
				}
			}
			

			if (tmp_pre != pre) {//优先级更高的插入
				
				work[now_id].run_time += work[tmp_id].reach_time-now_time;
				
				now_time = work[tmp_id].reach_time;//更新为新进程的到达时间
				lst_id = now_id;
				if (work[now_id].run_time == work[now_id].need_time) {
					work[now_id].finish_time = now_time;
					order_q.push(now_id);
					work[now_id].isvisited = 1;
					ok++;
					continue;
				}
				std::cout << "**执行" << now_id << "被" << tmp_id << "打断！  还剩" << work[now_id].need_time - work[now_id].run_time << "未执行\n";
				
			}
			else {
				lst_id = now_id;//没有优先级更高的插入
				order_q.push(now_id);
				now_time += work[now_id].need_time - work[now_id].run_time;
				work[now_id].finish_time = now_time;
				work[now_id].isvisited = 1;
				ok++;
			}
			//std::cout << now_id << "   " << tmp_id << "  " << pre<<"  "<<tmp_pre <<"  "<<now_time<<"\n";
			

		}
		else {
			now_time++;
		}
	}
	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t优先权  \t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].pre << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";

	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

时间片轮转

（1）老进程优先

        实现过程使用到了vector和一个队列，其类型为node（即存储各种时间信息），只用一个队列的话就会出现了插队的问题，实现为每次取出vector的头部，然后看他的到达时间是否小于当前时间，小于的话就可以放入队列，然后每次时间增加的时候，就遍历vector数组，如果当前有进程的到达时间小于当前时刻就把该进程塞到队列中，由于是老进程优先，所以需要先把对头放入队尾，再执行上述新进程操作。

代码

void OLD_RR() {//时间片轮转老进程优先
	std::cout << "\n\t\t\t\t\t时间片轮转算法(老进程优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<node>q;//用于进程
	std::vector<node>v;//存放每一个进程的就绪
	for (int i = 1; i <= N; i++)
		v.push_back(work[i]);//放入队列中
	q.push(*v.begin());
	int now_time = (*v.begin()).reach_time;
	work[(*v.begin()).kth].start_time = now_time;
	v.erase(v.begin());
	int ok = 0;
	while (q.size() || v.size()) {
		while (v.size() && (*v.begin()).reach_time <= now_time) {
			q.push(*v.begin());
			v.erase(v.begin());
		}
		//std::cout << now_time << "\n";
		if (q.front().run_time < q.front().need_time) {//时间片还未用完加入队尾
			std::cout << q.front().id << " ";
			int t = q.front().kth;
			//std::cout << t << "\n";
			now_time++;
			if (work[t].run_time == 0)
				work[t].start_time = now_time;
			work[t].run_time++;
			//std::cout << work[t].run_time <<"  "<<now_time<< "\n";
			if (work[t].run_time == work[t].need_time) {
				work[t].finish_time = now_time;
			}
			
			q.front().run_time++;
			
			q.push(q.front());
			q.pop();
			while (v.size() && (*v.begin()).reach_time <= now_time) {//有新作业到达，加入队列
				q.push(*v.begin());
				v.erase(v.begin());
			}
		}
		else {
			q.pop();
		}
	}
	work[1].start_time = work[1].reach_time;
	std::cout << "\n进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		//work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

（2）新进程优先

       跟上述一样实现差不多，主要改动是，上述是时间不变然后塞到队列，现在由于是新进程优先，所以时间得跟着变化，由于是储存到队列中还得取出来，所以不能真正的改变，需要用一个临时变量来进行时间增加加新进程

代码

void NEW_RR() {
	std::cout << "\n\t\t\t\t\t时间片轮转算法(新进程优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<node>q;//用于进程
	std::vector<node>v;//存放每一个进程的就绪
	for (int i = 1; i <= N; i++)
		v.push_back(work[i]);//放入队列中
	q.push(*v.begin());
	int now_time = (*v.begin()).reach_time;
	work[(*v.begin()).kth].start_time = now_time;
	v.erase(v.begin());
	int ok = 0;
	while (q.size() || v.size()) {
		while (v.size() && (*v.begin()).reach_time <= now_time) {
			q.push(*v.begin());
			v.erase(v.begin());
		}
		//std::cout << now_time << "\n";
		if (q.front().run_time < q.front().need_time) {//时间片还未用完加入队尾
			std::cout << q.front().id << " ";
			int t = q.front().kth;
			//std::cout << t << "\n";
			now_time++;
			if (work[t].run_time == 0)
				work[t].start_time = now_time;
			work[t].run_time++;
			//std::cout << work[t].run_time << "  " << now_time << "\n";
			if (work[t].run_time == work[t].need_time) {
				work[t].finish_time = now_time;
			}

			q.front().run_time++;
			int x = now_time;
			for (;; x++) {
				int f = 0;
				while (v.size() && (*v.begin()).reach_time <= x) {//有新作业到达，加入队列
					q.push(*v.begin());
					v.erase(v.begin());
					f=1;
				}
				if (!f) {
					break;
				}
			}
		
			q.push(q.front());
			q.pop();
		}
		else {
			q.pop();
		}
	}
	work[1].start_time = work[1].reach_time;
	std::cout << "\n进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		//work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

完整代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
const int MAX_N=10;
int N;//最大作业数量
struct node {
	char id;//编号
	int kth;//第几个，标识符
	int reach_time;//到达时间
	int need_time;//需要时间
	int wait_time;//等待时间
	int start_time;//开始时间
	int cir_time;//周转时间
	double pre_cir_time;//带权周转时间
	int run_time;//作业执行时间,执行抢占
	int pre;//优先权
	double reply_rate;//响应比
	bool isvisited;//是否进行过这个作业
	int finish_time;//完成时间
	bool reach;//是否到达
}work[MAX_N];


bool cmp1(node &a,node &b) {//先来先服务
	return a.reach_time < b.reach_time;
}

bool cmp2(node& a, node& b) {//数字小的优先权大
	return a.pre < b.pre;
}

bool cmp3(node& a, node& b) {
	return a.pre > b.pre;
}

void ouputinit() {
	std::cout << "进程名\t 到达时间\t服务时间\t优先权\n";
	for (int i = 1; i <= N; i++) {
		std::cout << work[i].id <<"\t  "<< work[i].reach_time << "  \t\t" << work[i].need_time << "\t\t  " << work[i].pre << "\n";
	}
}

void input() {
	std::cout << "请输入进程的数量：\n";
	std::cin >> N;
	std::cout << "请输入各作业的进程名，到达时间，服务时间以及优先权:\n";
	for (int i = 1; i <= N; i++) {
		work[i].kth = i;
		std::cin >> work[i].id >> work[i].reach_time >> work[i].need_time >> work[i].pre;
	}
}

void init() {
	for (int i = 0; i <= N; i++) {
		work[i].id = ' ';
		work[i].reach_time = 0;
		work[i].need_time = 0;
		work[i].wait_time = 0;
		work[i].start_time = 0;
		work[i].cir_time = 0;
		work[i].pre_cir_time = 0;
		work[i].run_time = 0;
		work[i].pre = 0;
		work[i].reply_rate = 0;
		work[i].isvisited = 0;
		work[i].finish_time = 0;
		work[i].reach = 0;
	}
}

void FCFS() {//先来先服务算法
	std::cout<<"\n\t\t\t\t\t先来先服务算法\n\n";
	double sum_cir_time=0;//总的周转时间
	double sum_pre_cir_time=0;//总的带权周转时间
	std::sort(work+1, work +1+ N,cmp1);//来的时间排序

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		work[i].start_time = work[i - 1].finish_time;
		work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id<<"\t"<<work[i].reach_time <<"\t\t"<<work[i].start_time <<"\t\t"<<
			work[i].need_time <<"\t\t"<<work[i].finish_time <<"\t\t"<<work[i].cir_time<<
			"\t\t"<<work[i].pre_cir_time<<"\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time*1.0/N << "\n";
}


void SPJF() {//短进程优先
	std::cout << "\n\t\t\t\t\t短进程优先服务算法\n\n";
	double sum_cir_time = 0;//总的周转时间
	int now_time=0,new_job=0;
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	//把开始时间小于目前时间的都丢到优先队列中
	std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int> >,std::greater<std::pair<int,int> > >q;
	std::queue<int>order_q;//用于获取编号的
	int ok = 0;//进程结束
	while (ok < N) {
		for (int i = 1; i <= N; i++) {
			if (!work[i].isvisited) {
				if (work[i].reach_time <= now_time) {//把小于当前时间已经到达的进程排序
					work[i].isvisited = 1;
					q.push({ work[i].need_time,work[i].kth});
				}
				else {
					break;//说明后面的进程是，谁先来设服务
				}
			}
		}
		if (q.empty()) {//队列为空说明应该执行先来先服务,当前时刻最短
			for (int i = 1; i <= N; i++) {
				if (!work[i].isvisited) {
					work[i].isvisited = 1;
					new_job = work[i].kth;//获取进程编号
					break;
				}
			}
		}
		else {
			new_job = q.top().second;
			q.pop();
		}
		order_q.push(new_job);
		ok++;
		work[new_job].start_time = std::max(now_time,work[new_job].reach_time);
		now_time=work[new_job].finish_time = work[new_job].start_time + work[new_job].need_time;
		work[new_job].cir_time = work[new_job].finish_time - work[new_job].reach_time;
		sum_cir_time += work[new_job].cir_time;
		work[new_job].pre_cir_time = work[new_job].cir_time * 1.0 / work[new_job].need_time;
		sum_pre_cir_time += work[new_job].pre_cir_time;
	}

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" <<
		sum_pre_cir_time * 1.0 / N << "\n";
}

void HPF() {
	
	std::cout << "\n\t\t\t\t\t优先权算法(数字小优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	int now_time=0,new_job=0;
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	//把开始时间小于目前时间的都丢到优先队列中
	
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >q;

	std::queue<int>order_q;//用于获取编号的
	int ok = 0;//进程结束
	while (ok < N) {
		for (int i = 1; i <= N; i++) {
			if (!work[i].isvisited) {
				if (work[i].reach_time <= now_time) {//把小于当前时间已经到达的进程排序
					work[i].isvisited = 1;
					q.push({ work[i].pre,work[i].kth});
				}
				else {
					break;//说明后面的进程是，谁先来设服务
				}
			}
		}
		if (q.empty()) {//队列为空说明应该执行先来先服务,当前时刻最短
			for (int i = 1; i <= N; i++) {
				if (!work[i].isvisited) {
					work[i].isvisited = 1;
					new_job = work[i].kth;//获取进程编号
					break;
				}
			}
		}
		else {
			new_job = q.top().second;
			q.pop();
		}
		order_q.push(new_job);
		ok++;
		work[new_job].start_time = std::max(now_time,work[new_job].reach_time);
		now_time=work[new_job].finish_time = work[new_job].start_time + work[new_job].need_time;
		work[new_job].cir_time = work[new_job].finish_time - work[new_job].reach_time;
		sum_cir_time += work[new_job].cir_time;
		work[new_job].pre_cir_time = work[new_job].cir_time * 1.0 / work[new_job].need_time;
		sum_pre_cir_time += work[new_job].pre_cir_time;
	}

	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t优先权  \t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t"<<work[i].pre<<"\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";

	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";
}


void QHPF(){//优先权抢占式
	std::cout << "\n\t\t\t\t\t优先权抢占算法\n\n";
	double sum_cir_time = 0;//总的周转时间
	
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<int>order_q;
	int pre = 1e5;//记录实时的pre
	int ok = 0,now_time=0,now_id=0,lst_id=0;//当前时间，当前编号，上一次的编号
	while (ok < N) {
		pre = 1e5;
		for (int i = 1; i <= N; i++) {
			if (work[i].reach_time <= now_time) {//当前程序可以执行
				if (pre>work[i].pre&&!work[i].isvisited) {//更换优先级更高的
					pre = work[i].pre;
					now_id = work[i].kth;//当前要运行的程序
				}
			}
		}
		
		//std::cout << pre << " " << now_id << "\n";
		if (work[now_id].run_time == 0) {
				work[now_id].start_time = now_time;//该进程开始时在这时候介入
		}
		//std::cout << now_time << "\n";

		if (now_id != lst_id) {//还有进程可以执行
			int tmp_pre = pre;
			int tmp_id=now_id;
			for (int i = 1; i <= N; i++) {//从当前时刻到该作业结束，中间由优先级更高的插入
				if (now_time + work[now_id].need_time - work[now_id].run_time >= work[i].reach
					&& tmp_id != work[i].kth&&!work[i].isvisited&&tmp_pre>work[i].pre) {
					tmp_id = work[i].kth;
					tmp_pre = work[i].pre;
					break;
				}
			}
			

			if (tmp_pre != pre) {//优先级更高的插入
				
				work[now_id].run_time += work[tmp_id].reach_time-now_time;
				
				now_time = work[tmp_id].reach_time;//更新为新进程的到达时间
				lst_id = now_id;
				if (work[now_id].run_time == work[now_id].need_time) {
					work[now_id].finish_time = now_time;
					order_q.push(now_id);
					work[now_id].isvisited = 1;
					ok++;
					continue;
				}
				std::cout << "**执行" << now_id << "被" << tmp_id << "打断！  还剩" << work[now_id].need_time - work[now_id].run_time << "未执行\n";
				
			}
			else {
				lst_id = now_id;//没有优先级更高的插入
				order_q.push(now_id);
				now_time += work[now_id].need_time - work[now_id].run_time;
				work[now_id].finish_time = now_time;
				work[now_id].isvisited = 1;
				ok++;
			}
			//std::cout << now_id << "   " << tmp_id << "  " << pre<<"  "<<tmp_pre <<"  "<<now_time<<"\n";
			

		}
		else {
			now_time++;
		}
	}
	std::cout << "进程名\t 到达时间\t开始时间\t服务时间\t优先权  \t结束时间\t周转时间\t带权周转时间\n";
	while (!order_q.empty()) {
		int i = order_q.front(); order_q.pop();
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].pre << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";

	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

void OLD_RR() {//时间片轮转老进程优先
	std::cout << "\n\t\t\t\t\t时间片轮转算法(老进程优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<node>q;//用于进程
	std::vector<node>v;//存放每一个进程的就绪
	for (int i = 1; i <= N; i++)
		v.push_back(work[i]);//放入队列中
	q.push(*v.begin());
	int now_time = (*v.begin()).reach_time;
	work[(*v.begin()).kth].start_time = now_time;
	v.erase(v.begin());
	int ok = 0;
	while (q.size() || v.size()) {
		while (v.size() && (*v.begin()).reach_time <= now_time) {
			q.push(*v.begin());
			v.erase(v.begin());
		}
		//std::cout << now_time << "\n";
		if (q.front().run_time < q.front().need_time) {//时间片还未用完加入队尾
			std::cout << q.front().id << " ";
			int t = q.front().kth;
			//std::cout << t << "\n";
			now_time++;
			if (work[t].run_time == 0)
				work[t].start_time = now_time;
			work[t].run_time++;
			//std::cout << work[t].run_time <<"  "<<now_time<< "\n";
			if (work[t].run_time == work[t].need_time) {
				work[t].finish_time = now_time;
			}
			
			q.front().run_time++;
			
			q.push(q.front());
			q.pop();
			while (v.size() && (*v.begin()).reach_time <= now_time) {//有新作业到达，加入队列
				q.push(*v.begin());
				v.erase(v.begin());
			}
		}
		else {
			q.pop();
		}
	}
	work[1].start_time = work[1].reach_time;
	std::cout << "\n进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		//work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

void NEW_RR() {
	std::cout << "\n\t\t\t\t\t时间片轮转算法(新进程优先)\n\n";
	double sum_cir_time = 0;//总的周转时间
	double sum_pre_cir_time = 0;//总的带权周转时间
	std::sort(work + 1, work + 1 + N, cmp1);//来的时间排序
	std::queue<node>q;//用于进程
	std::vector<node>v;//存放每一个进程的就绪
	for (int i = 1; i <= N; i++)
		v.push_back(work[i]);//放入队列中
	q.push(*v.begin());
	int now_time = (*v.begin()).reach_time;
	work[(*v.begin()).kth].start_time = now_time;
	v.erase(v.begin());
	int ok = 0;
	while (q.size() || v.size()) {
		while (v.size() && (*v.begin()).reach_time <= now_time) {
			q.push(*v.begin());
			v.erase(v.begin());
		}
		//std::cout << now_time << "\n";
		if (q.front().run_time < q.front().need_time) {//时间片还未用完加入队尾
			std::cout << q.front().id << " ";
			int t = q.front().kth;
			//std::cout << t << "\n";
			now_time++;
			if (work[t].run_time == 0)
				work[t].start_time = now_time;
			work[t].run_time++;
			//std::cout << work[t].run_time << "  " << now_time << "\n";
			if (work[t].run_time == work[t].need_time) {
				work[t].finish_time = now_time;
			}

			q.front().run_time++;
			int x = now_time;
			for (;; x++) {
				int f = 0;
				while (v.size() && (*v.begin()).reach_time <= x) {//有新作业到达，加入队列
					q.push(*v.begin());
					v.erase(v.begin());
					f=1;
				}
				if (!f) {
					break;
				}
			}
		
			q.push(q.front());
			q.pop();
		}
		else {
			q.pop();
		}
	}
	work[1].start_time = work[1].reach_time;
	std::cout << "\n进程名\t 到达时间\t开始时间\t服务时间\t结束时间\t周转时间\t带权周转时间\n";
	for (int i = 1; i <= N; i++) {
		//work[i].finish_time = work[i].start_time + work[i].need_time;
		work[i].cir_time = work[i].finish_time - work[i].reach_time;
		sum_cir_time += work[i].cir_time;
		work[i].pre_cir_time = work[i].cir_time * 1.0 / work[i].need_time;
		sum_pre_cir_time += work[i].pre_cir_time;
		std::cout << work[i].id << "\t" << work[i].reach_time << "\t\t" << work[i].start_time << "\t\t" <<
			work[i].need_time << "\t\t" << work[i].finish_time << "\t\t" << work[i].cir_time <<
			"\t\t" << work[i].pre_cir_time << "\n";
	}
	std::cout << "平均" << "\t\t\t\t\t\t\t\t\t" << sum_cir_time * 1.0 / N << "\t\t" << sum_pre_cir_time * 1.0 / N << "\n";

}

/*
A 0 4 4
B 1 3 2
C 2 5 3
D 3 2 5
E 4 4 1
*/

int main() {
	input();
	ouputinit();
	std::cout << "请输入要选择的优先权算法:\n(1)先来先服务(FCFS)\n(2)短进程优先(SPJF)\n(3)优先权算法\n(4)时间片轮转\n";
	int chose;
	std::cin >> chose;
	if (chose == 1) {
		FCFS();
	}
	else if (chose == 2) {
		SPJF();
	}
	else if (chose == 3) {
		std::cout << "  优先权是否抢占(是(1)/否(0))";
		int q;
		std::cin >> q;
		if (q == 0) {
			HPF();
		}
		else {
			QHPF();
		}
	}
	else if (chose == 4) {
		std::cout << "  时间片进程优先选择(老进程(1)/新进程(0))";
		int q;
		std::cin >> q;
		if (q == 1) {
			OLD_RR();
		}
		else {
			NEW_RR();
		}
	}
	//QHPF();
	//NEW_RR();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/581984.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

字典及GitHub字典爬取工具

字典及GitHub字典爬取工具

红队API接口Fuzz字典可以用于WEB安全&#xff0c;渗透测试&#xff0c;SRC等场景 完整文件已上传知识星球&#xff0c;需要的朋友可加入查看。
阅读更多...
STM32应用开发教程进阶--Wi-Fi通信（ESP8266模块：STA、AP、STA+AP）

STM32应用开发教程进阶--Wi-Fi通信（ESP8266模块：STA、AP、STA+AP）

实现目标 1、熟悉Wi-F、ESP8266模块 2、掌握ESP8266模块共3种工作模式&#xff1a;STA、AP、STAAP的配置 3、具体实现目标&#xff1a;&#xff08;1&#xff09;AT固件烧录&#xff1b;&#xff08;2&#xff09;ESP8266模块STA、AP、STAAP的配置 一、Wi-Fi概述 1、Wi-Fi定…
阅读更多...
OpenCV-Python: 强大的计算机视觉库

OpenCV-Python: 强大的计算机视觉库

文章目录 OpenCV-Python: 强大的计算机视觉库背景OpenCV-Python是什么&#xff1f;安装简单的库函数使用方法场景示例人脸检测和识别图像分割目标跟踪 常见问题和解决方案总结 OpenCV-Python: 强大的计算机视觉库 背景 OpenCV (Open Source Computer Vision Library) 是一个开…
阅读更多...
OceanBase 助力同方智慧能源，打造安全可靠、高性能的能源数据架构

OceanBase 助力同方智慧能源，打造安全可靠、高性能的能源数据架构

本文作者&#xff1a;丁泽斌&#xff0c;同方智慧能源数据库工程师 业务背景 作为同方股份有限公司旗下的领军企业&#xff0c;同方智慧能源集团矢志成为全球领先的综合智慧能源解决方案提供商。凭借中核集团和清华大学的科技实力&#xff0c;专注于向建筑、交通、工业、北方供…
阅读更多...
Altair® HPCWorks™——高性能计算（HPC）和云平台

Altair® HPCWorks™——高性能计算（HPC）和云平台

Altair HPCWorks™——高性能计算&#xff08;HPC&#xff09;和云平台 强大的计算助力研发增速&#xff0c;Altair HPCWorks™ 使高性能和云计算变得快速、高效和提高有效产出 - 无论您的资源是在本地、云端还是混合环境中。专业地管理 IT 复杂性并支持最新的 AI 工作负载。使…
阅读更多...
《QT实用小工具·四十五》可以在界面上游泳的小鱼

《QT实用小工具·四十五》可以在界面上游泳的小鱼

1、概述 源码放在文章末尾 该项目实现了灵动的小鱼&#xff0c;可以在界面上跟随鼠标点击自由的游泳&#xff0c;项目demo演示如下所示&#xff1a; 项目部分代码如下所示&#xff1a; #include "magicfish.h" #include <QtMath> #include <QPainter>…
阅读更多...
CentOS7安装和升级nginx

CentOS7安装和升级nginx

文章目录 一 环境准备二 安装nginx三 升级nginx四 注意事项 一 环境准备 公司等保要求修复nginx的应用漏洞&#xff0c;从1.12.2升级到1.20.2版本。 本机操作系统是CentOS7.9&#xff0c;主机IP是192.168.0.201&#xff0c;nginx是在服务器部署而非容器部署。 下列安装和升级…
阅读更多...
Springboot + MySQL + html 实现文件的上传、存储、下载、删除

Springboot + MySQL + html 实现文件的上传、存储、下载、删除

实现步骤及效果呈现如下&#xff1a; 1.创建数据库表&#xff1a; 表名&#xff1a;file_test 存储后的数据&#xff1a; 2.创建数据库表对应映射的实体类&#xff1a; import com.baomidou.mybatisplus.annotation.IdType;import com.baomidou.mybatisplus.annotation.Table…
阅读更多...
《R语言与农业数据统计分析及建模》学习——回归分析

《R语言与农业数据统计分析及建模》学习——回归分析

一、线性回归 线性回归是一种广泛用于数据分析、预测和建模的技术&#xff0c;可以帮助我们理解变量之间的关系&#xff0c;并进行预测和推断。 1、简单线性回归 简单线性回归是线性回归的一种特殊情况&#xff0c;适用于只有一个自变量和一个因变量的情况。 在R语言中&#x…
阅读更多...
QT c++ 代码布局原则 简单例子

QT c++ 代码布局原则 简单例子

本文描述QT c widget代码布局遵循的原则&#xff1a;实中套虚&#xff0c;虚中套实。 本文最后列出了代码下载链接。 在QT6.2.4 msvc2019编译通过。 所谓实是实体组件&#xff1a;比如界面框、文本标签、组合框、文本框、按钮、表格、图片框等。 所谓虚是Layout组件&#x…
阅读更多...
IT廉连看——UniApp——样式绑定

IT廉连看——UniApp——样式绑定

IT廉连看——UniApp——样式绑定 一、样式绑定 两种添加样式的方法&#xff1a; 1、第一种写法 写一个class属性&#xff0c;然后将css样式写在style中。 2、第二种写法 直接把style写在class后面 添加一些效果&#xff1a;字体大小 查看效果 证明这样添加样式是没有问题的…
阅读更多...
WPF —— MVVM 指令执行不同的任务实例

WPF —— MVVM 指令执行不同的任务实例

标签页 设置两个按钮&#xff0c; <Button Content"修改状态" Width"100" Height"40" Background"red"Click"Button_Click"></Button><Button Content"测试"Width"100"Height"40&…
阅读更多...
clickhous学习之旅二

clickhous学习之旅二

接上回继续鼓捣clickhouse 1.常用数据类型 1.1整型 固定长度的整型&#xff0c;包括有符号整型或无符号整型。整型范围(-2n-1~2n-1-1): Int8 - [-128 :127] -->相当于java中的byte Int16-[-32768 :32767] -->相当于java中的short Int32-[-2147483648 :2147483647] -…
阅读更多...
最新官方破解版会声会影2024永久序列号和激活码

最新官方破解版会声会影2024永久序列号和激活码

会声会影2024是一款功能强大的视频编辑软件&#xff0c;它集合了视频剪辑、音频调整、特效添加等多项功能于一身&#xff0c;为用户提供了一个全面且易用的视频制作平台。无论是初学者还是专业视频编辑人员&#xff0c;都能在这款软件中找到满足自己创作需求的工具。 会声会影最…
阅读更多...
基于残差神经网络的汉字识别系统+pyqt前段界面设计

基于残差神经网络的汉字识别系统+pyqt前段界面设计

研究内容: 中文汉字识别是一项具有挑战性的任务&#xff0c;涉及到对中文字符的准确分类。在这个项目中&#xff0c;目标是构建一个能够准确识别中文汉字的系统。这个任务涉及到数据集的收集、预处理、模型训练和评估等步骤。尝试了使用残差神经网络&#xff08;ResNet&#x…
阅读更多...
windows电脑改造为linux

windows电脑改造为linux

有个大学用的旧笔记本电脑没啥用了&#xff0c;决定把它改成linux搭一个服务器&#xff1b; 一、linux安装盘制作 首先要有一个大于8G的U盘&#xff0c;然后去下载需要的linux系统镜像&#xff0c;我下的是ubuntu&#xff0c;这里自选版本 https://cn.ubuntu.com/download/d…
阅读更多...
中国移动旋转验证码的识别过程

中国移动旋转验证码的识别过程

一、前言 今天有空研究了一下这个移动的登录&#xff0c;发现获取手机验证码的时候会弹出一种旋转验证码。这种验证码确实挺头疼。所以顺便研究了一下如何识别。 验证码的样子大家先看一下。看看大家有没有什么更好是思路。 二、验证码识别 我这里就直接上代码。我这里是使用…
阅读更多...
SpringMVC基础篇（四）

SpringMVC基础篇（四）

文章目录 1.视图1.基本介绍1.视图介绍2.为什么需要自定义视图 2.自定义视图实例1.思路分析2.代码实例1.view.jsp2.接口3.配置自定义视图解析器springDispatcherServlet-servlet.xml4.自定义视图MyView.java5.view_result.jsp6.结果展示 3.自定义视图执行流程4.自定义视图执行流…
阅读更多...
web安全---xss漏洞/beef-xss基本使用

web安全---xss漏洞/beef-xss基本使用

what xss漏洞----跨站脚本攻击&#xff08;Cross Site Scripting&#xff09;&#xff0c;攻击者在网页中注入恶意脚本代码&#xff0c;使受害者在浏览器中运行该脚本&#xff0c;从而达到攻击目的。 分类 反射型---最常见&#xff0c;最广泛 用户将带有恶意代码的url打开&a…
阅读更多...
E-MapReduce极客挑战赛季军方案

E-MapReduce极客挑战赛季军方案

前一段时间我参加了E-MapReduce极客挑战赛&#xff0c;很幸运的获得了季军。在这把我的比赛攻略给大家分享一下&#xff0c;希望可以抛砖引玉。 赛题分析与理解 赛题背景&#xff1a; 大数据时代&#xff0c;上云已成为越来越多终端客户大数据方案的落地选择&#xff0c;阿里…
阅读更多...
最新文章

Copyright @ 2022~2023