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

embedded/2024/9/20 7:08:46/ 标签: 算法, c++, java

变量描述

测试数据

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


http://www.ppmy.cn/embedded/22444.html

相关文章

灌溉排涝乙级资质升级甲级,这些材料你准备好了吗?

在灌溉排涝行业&#xff0c;资质的升级不仅是企业实力的一种体现&#xff0c;更是开拓新市场、参与更多大型项目的必要条件。从乙级资质升级到甲级&#xff0c;企业需要跨越一个较高的门槛&#xff0c;准备一系列详尽而严谨的材料。以下就是你需要准备的关键材料清单&#xff0…

Cocos Creator 3D物理引擎的物理参数控制详解

前言 Cocos Creator是一款基于JavaScript和TypeScript的开源游戏引擎&#xff0c;它提供了强大的3D物理引擎&#xff0c;可以帮助开发者实现各种物理效果。在Cocos Creator中&#xff0c;我们可以通过控制物理参数来实现不同的物理效果&#xff0c;比如重力、碰撞检测、摩擦力…

后端学习记录~~JavaSE篇(Module08-异常 上 )

总览&#xff1a; Java概述&#xff1a; 思维导图文件在本人个人主页上-----资源模块 资源详情&#xff08;免费下载&#xff09;&#xff1a;Java学习思维导图异常篇资源-CSDN文库https://download.csdn.net/download/m0_61589682/89238330 整体展示&#xff1a;

动手学深度学习——矩阵

1. 基本概念 1.1 标量 标量由只有一个元素的张量表示。 所以标量计算与程度开发中的普通变量计算没有差异。 import torchx torch.tensor(3.0) y torch.tensor(2.0)x y, x * y, x / y, x**y(tensor(5.), tensor(6.), tensor(1.5000), tensor(9.))1.2 向量 向量泛化自标量…

水稻病害检测(YOLO数据集,多分类,稻瘟病、纹枯病、褐斑病、枯心病、霜霉病、水稻细菌性条纹斑病、稻苞虫)

是自己利用LabelImg工具进行手工标注&#xff0c;数据集制作不易&#xff0c;请尊重版权&#xff08;稻瘟病、纹枯病、褐斑病、枯心病、霜霉病、水稻细菌性条纹斑病、稻苞虫&#xff09; 如果需要yolv8检测模型和数据集放在一起的压缩包&#xff0c;可以关注&#xff1a;最新最…

什么是跨域? 出现原因及解决方法

什么是跨域? 出现原因及解决方法 什么是跨域 跨域&#xff1a;浏览器对于javascript的同源策略的限制 。 同源政策的目的&#xff0c;是为了保证用户信息的安全&#xff0c;防止恶意的网站窃取数据。 设想这样一种情况&#xff1a;A 网站是一家银行&#xff0c;用户登录以后…

迭代器iterator是C++中用于遍历容器中元素的对象

C中的迭代器是一种对象&#xff0c;用于在容器中遍历元素。它提供了一种抽象的方式来访问容器中的元素&#xff0c;而不暴露底层数据结构的细节。通过迭代器&#xff0c;可以遍历顺序容器&#xff08;如vector、list、deque等&#xff09;、关联容器&#xff08;如map、set等&a…

【调研分析】目标在不同焦距和距离下与画面的比例(2.8-3.6-4.0)

之前在做项目中需要极度优化效果和代码运行速度 为此测试了同一个目标在不同焦距和距离下与画面的比例&#xff0c;从而可以方便在指定大小情况下搜索目标 NOTE: 这是早期滑窗检测做目标检测下的工作

java项目:微信小程序基于SSM框架小说阅读器小程序【源码+数据库+毕业论文+PPT】

一、项目简介 本项目是一套基于SSM框架小说阅读器小程序 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、功能齐全、…

python代码实现支持向量机对鸢尾花分类

1、导入支持向量机模型&#xff0c;划分数据集 from sklearn import datasets from sklearn import svmirisdatasets.load_iris() iris_xiris.data iris_yiris.target indices np.random.permutation(len(iris_x)) iris_x_train iris_x[indices[:-10]] iris_y_train iris_y…

计算机网络之传输层TCP\UDP协议

UDP协议 用户数据报协议UDP概述 UDP只在IP数据报服务之上增加了很少功能&#xff0c;即复用分用和差错检测功能 UDP的主要特点&#xff1a; UDP是无连接的&#xff0c;减少开销和发送数据之前的时延 UDP使用最大努力交付&#xff0c;即不保证可靠交付&#xff0c;可靠性由U…

linux权限的概念

目录 shell命令以及运行原理 Linux权限的概念 Linux权限管理 文件类型和访问权限&#xff08;事物属性&#xff09; 快速修改权限的做法&#xff1a; 一个文件的权限谁能修改&#xff1f; 对比权限的有无&#xff0c;表现&#xff1a; 修改权限的第二套方法&#xff1…

「布道师系列文章」小红书黄章衡:AutoMQ Serverless 基石-秒级分区迁移

作者&#xff5c;黄章衡&#xff0c;小红书消息引擎研发专家 01 引言 Apache Kafka 因存算一体化架构&#xff0c;分区迁移依赖大量数据同步的完成&#xff0c;以一个 100MB/s 流量的 Kafka 分区为例&#xff0c;运行一天产生的数据量约为 8.2T&#xff0c;如果此时需要将该分…

访问控制列表配置实验

ACL&#xff0c;全称 Access Control List&#xff08;访问控制列表&#xff09;&#xff0c;是一种实现访问控制的机制&#xff0c;用于规定哪些主体&#xff08;如用户、设备、IP地址、进程等&#xff09;可以对哪些资源&#xff08;如网络服务、文件、系统对象等&#xff09…

xml,json和protobuffer

数据组织格式 xmljsonprotobuffer小结 xml 是以成对的方式,来表示"键值对"的信息,同时标签支持嵌套,可以构成更复杂的树形结构数据. 请求: <request> // 开始标签<username>zhangsan</username> // 表示的是键值对 key:username value: zhangsan&l…

NURBS样条曲线学习

搞3D几何内核算法研究&#xff0c;必须学习NURBS样条曲线曲面。 看《非均匀有理B样条 第2版》这本书&#xff0c;学习起来&#xff0c;事半功倍。 在《插件化算法研究平台》上&#xff0c;做了一个样条曲线研究功能&#xff0c;可以分析Bezier曲线、BSpline、NURBS曲线的各种…

Python常见的第三方库[详细解析]

Python是通过模块来体现库&#xff0c;常见的有标准库和第三方库。标准库是Python自带的库&#xff0c;在官方文档中可以查看&#xff0c;第三方库是其他大佬做出来的。 库它的优点有:1.降低程序员的学习成本 2.提高程序的开发效率 。 第1个常见的库为datetime&#xff0c;我们…

吉时利2450源表如何调整电流精度?

吉时利2450源表是一款高精度的电流源表&#xff0c;可用于精确控制和测量电流。调整电流精度是确保吉时利2450源表准确输出所需电流的关键步骤。本文将介绍吉时利2450源表如何调整电流精度的方法和注意事项。 准备工作 在开始调整电流精度之前&#xff0c;确保吉时利2450源表…

ArcGIS小技巧—基于DEM的河网提取

1、使用DEM数据提取河流水系网络 原始DEM数据中存在误差&#xff0c;或喀斯特地貌等真实地形情况&#xff0c;将引起DEM数据中存在凹陷区域。 在进行水流方向的计算上&#xff0c;如果有洼地会造成错误&#xff0c;因此我们需要进行填洼处理&#xff0c;获得相对准确的DEM数据…

手机测试之-adb

一、Android Debug Bridge 1.1 Android系统主要的目录 1.2 ADB工具介绍 ADB的全称为Android Debug Bridge,就是起到调试桥的作用,是Android SDK里面一个多用途调试工具,通过它可以和Android设备或模拟器通信,借助adb工具,我们可以管理设备或手机模拟器的状态。还可以进行很多…