调度算法 操作系统 c++代码

#include <iostream> #include <queue> #include <string> #include <vector> using namespace std; const int Maxnum = 101; typedef struct information { int in_time;//进入时间 int use_time;//估计花费时间 int job;//job编号 int start,finish,Ti;//开始工作时间 完成作业时间 周转时间 int flag;//优先级别 用户自己设置 double Wi;//带权周转时间 double Ri;//最高响应比 information() { start = flag = Ti = finish = 0; Ri = Wi = 0.0; } }node; struct node1//此结构体用于优先级算法的抢占式 { friend bool operator < (node1 n1, node1 n2)//优先队列中的比较规则 即由小到大 { return n1.priority > n2.priority; } int priority; int pos; }; struct node2//此结构体用于最短作业优先算法的抢占式 { friend bool operator < (node2 n1, node2 n2)//优先队列中的比较规则 即由小到大 { return n1.priority > n2.priority; } int priority; int pos; }; /*struct node3//此结构体用于最高相应比优先算法的抢占式 { friend bool operator < (node3 n1, node3 n2)//优先队列中的比较规则 即由大到小 { return n1.priority < n2.priority; } double priority; int pos; };*/ node slove_node[Maxnum]; node Main_node[Maxnum]; bool finish_flag[Maxnum];//确定一个作业是否做完 int num; string Int_to_String(int Time); void FCFS(); void Rotate(); void Priority(); void Short(); void HRN(); void print(); int cmp( const void *a ,const void *B) { return (*(information *)a).in_time >= (*(information *)B).in_time ? 1 : -1; } struct cmp1{ bool operator()(const int &i, const int &j){ return i>j; } }; int main() { int i; /*priority_queue<int,vector<int>,cmp1> pri_q; while (!pri_q.empty())//优先队列 { pri_q.pop(); } for (i = 6;i>0;i--) { pri_q.push(i); } while(!pri_q.empty()) { cout<<pri_q.top()<< ' ' ; pri_q.pop(); }*/ cout<<"请输入现在总共有多少个作业要做(n<=100)"<<endl; cin>>num; cout<<"请输入各个作业的进入工作的开始时间和估计执行完需要的时间"<<endl; string start_time; // int start_time; int Int_start_time; int need_time; for (i = 0;i<num;i++) { cin>>start_time>>need_time; int len = start_time.length(); if (len == 4) Int_start_time = (start_time[0] - '0')*60 + (start_time[2] - '0')*10 + start_time[3] - '0'; if (len == 5) Int_start_time = ((start_time[0] - '0')*10 + (start_time[1] - '0'))*60 + (start_time[3] - '0')*10 + start_time[4] - '0'; //cout<<Int_start_time<<endl; Main_node[i].job = i+1; Main_node[i].in_time = Int_start_time; Main_node[i].use_time = need_time; } qsort(Main_node,num,sizeof(Main_node[0]),cmp); while(1) { int choose; cout<<"\n\n——请输入你想进行操作的算法——"<<endl; cout<<"1： 先来先服务算法"<<endl; cout<<"2： 轮转算法"<<endl; cout<<"3： 优先级算法"<<endl; cout<<"4： 最短作业优先算法"<<endl; cout<<"5：最高响应比优先算法"<<endl; cout<<"0： 退出系统"<<endl; cout<<"————————————————\n\n"<<endl; cin>>choose; switch (choose) { case 1: FCFS();//先来先服务算法 break; case 2: Rotate();//轮转算法 break; case 3: Priority();//优先级算法 break; case 4: Short();//最短作业优先算法 break; case 5: HRN();//最高响应比优先算法 break; case 0: exit(0); break; } } return 0; } ////////////////////////////////////////////////////////////// void FCFS() { int i,j; for (j = 0;j<num;j++) {//这里对所要处理的结构体数组和main函数中输入的数据进行赋值以便后面进行处理 slove_node[j].use_time = Main_node[j].use_time; slove_node[j].job = Main_node[j].job; slove_node[j].in_time = Main_node[j].in_time; }// i = 0; int temp_time = 0;//时间流程的控制变量 while(i<num) { if(temp_time<slove_node[i].in_time)//如果做完一个作业第二个作业还没有到 { temp_time = slove_node[i].use_time+slove_node[i].in_time; slove_node[i].finish = temp_time; slove_node[i].Ti = slove_node[i].finish - slove_node[i].in_time;//计算这个作业开始的时间 slove_node[i].start = slove_node[i].finish - slove_node[i].use_time; slove_node[i].Wi = (double)slove_node[i].Ti/slove_node[i].use_time; } //这种情况除第一次外应该要避免 else { temp_time +=slove_node[i].use_time; slove_node[i].finish = temp_time; slove_node[i].start = slove_node[i].finish - slove_node[i].use_time; slove_node[i].Ti = slove_node[i].finish - slove_node[i].in_time; slove_node[i].Wi = (double)slove_node[i].Ti/slove_node[i].use_time; } i++; } print(); } ////////////////////////////////////////////////////////////// void Rotate() { memset(finish_flag,0,sizeof(finish_flag)); bool in_que_flag[Maxnum],first_out[Maxnum];//标记作业进如队列 和 标记作业第一次出队列 memset(in_que_flag,0,sizeof(in_que_flag)); memset(first_out,0,sizeof(first_out)); int use_time[Maxnum];//用临时的时间还判断作业是否做完 int rotate_time,i,j;//轮转时间 for (j = 0;j<num;j++) { use_time[j] = slove_node[j].use_time = Main_node[j].use_time; slove_node[j].job = Main_node[j].job; slove_node[j].in_time = Main_node[j].in_time; } cout<<"请设置轮转时间:"; cin>>rotate_time; queue<int> q; //队列q用于作业在等待状态 while(!q.empty()) q.pop(); int get; bool flag = true; int temp_time = 0; while(flag) { flag = false; for(i = 0;i < num; i++) { if(!finish_flag[i])//判断是否还有作业没有做的 { q.push(i); in_que_flag[i] = true; first_out[i] = true; flag = true; if (temp_time < slove_node[i].in_time)//如果当前时间比第i个作业进入时间都小 { temp_time = slove_node[i].in_time; } break; } } if (!flag) break; while (!q.empty()) { get = q.front(); for (j = 0;j<num;j++) { if (first_out[j]) { slove_node[j].start = temp_time;//计算开始做这个作业的时间 first_out[j] = false; } } q.pop();//做一个时间片出一次队列 temp_time += rotate_time; use_time[get] -= rotate_time; for (j = 0;j<num;j++) { if (!in_que_flag[j]&& temp_time >= slove_node[j].in_time)//判断还没有进入队列，并且所处的时间正好大于或者等于下一个作业开始的时间 { q.push(j); first_out[j] = true; in_que_flag[j] = true; } } if (use_time[get] <= 0)//表示已经做完一个作业 { finish_flag[get] = true; slove_node[get].finish = temp_time; slove_node[get].Ti = slove_node[get].finish - slove_node[get].in_time; slove_node[get].Wi = (double)slove_node[get].Ti/slove_node[get].use_time; } else q.push(get);//循环的进入队列，直到已经做完 } } print(); } ////////////////////////////////////////////////////////////// void Priority() { int choose;//是否选择抢占式的标记 int i,j; for (i = 0;i<num;i++) { slove_node[i].use_time = Main_node[i].use_time; slove_node[i].job = Main_node[i].job; slove_node[i].in_time = Main_node[i].in_time; } cout<<"请输入这"<<num<<"个作业的优先级"<<endl; for (i = 0;i<num;i++) { cout<<"请输入作业"<<slove_node[i].job<<"的优先级"<<endl; cin>>slove_node[i].flag;//设置作业的优先级 } cout<<"请选择是否使用抢占式（1（代表抢占）0(代表不能抢占)）"<<endl; cin>>choose; if (choose == 0)/////////////////////////////////////////////////////非抢占式 { bool flag_will[Maxnum];//判断一个作业做完之后其他有多少作业可以开始做了 memset(flag_will,0,sizeof(flag_will)); memset(finish_flag,0,sizeof(finish_flag)); bool flag = true;// while的控制变量 int temp_time = 0 ; int min_j = num; slove_node[min_j].flag = INT_MAX; while(flag) { flag = false; for(i = 0;i < num; i++) { if(!finish_flag[i])//判断是否还有作业没有做的 { // cout<<i<<endl; flag = true; if (temp_time < slove_node[i].in_time)//如果当前时间比第i个作业进入时间都小 { temp_time = slove_node[i].in_time; flag_will[i] = true; } break; } } if (!flag) break; for (j = 0;j<num;j++)