本文主要是介绍操作系统——优先权算法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;//记录实时的preint 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;//记录实时的preint 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;
}这篇关于操作系统——优先权算法c++实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
