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

发布于：2024-04-29 ⋅ 阅读:(35) ⋅ 点赞:(0)

变量描述

测试数据

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;
}

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布