先来先服务-短作业优先-时间片轮转调度算法-高响应比优先调度算法的C++实现（OS实验作业）_时间片轮转,先来先服务,短作业优先

1. 调度算法概念

1.1 先来先服务算法概念

先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。采用FCFS算法，每次从后备队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为他们分配资源，创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
题目：

1.2 短作业优先算法概念

最短作业优先（SJF）调度算法将每个进程与其下次 CPU 执行的长度关联起来。当 CPU 变为空闲时，它会被赋给具有最短 CPU执行的进程。如果两个进程具有同样长度的 CPU 执行，那么可以由 FCFS来处理。一个更为恰当的表示是最短下次CPU执行算法，这是因为调度取决于进程的下次 CPU 执行的长度，而不是其总的长度。我们使用 SJF 一词，主要由于大多数教科书和有关人员都这么称呼这种类型的调度策略。
题目：

1.3 时间片轮转调度算法概念

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间(如30 ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。在RR调度算法中，应在何时进行进程的切换，可分为两种情况：
①若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。
②在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。
题目：
时间片轮转调度算法这里的案例采用王道的题目进行测试【计算机在实际执行时间片轮转时，确实是采用这种队列的方式进行的，而不是简单的按照p1、p2、p3、p4依次循环执行的方法，这是不科学的】【这里时间片大小==2】
另外解释一下srt_t：【在我的代码中，这里的进程运行的开始时间会随着时间片的调度而改变，因为RR算法本身就是抢占式的，因此上处理机的次数也会有多次，所以不像其它非抢占式的进程执行，进程的开始时间就是他唯一的开始时间那样】

1.4 高响应比优先调度算法概念

高响应比算法，是一种动态调整优先级的算法.因为可能造成一个低优先级作业始终得不到执行。为了解决这个问题，HRRN算法每次都计算作业的优先级，随着作业等待时间的变长，优先级不断的提高，所以能够得到更快的执行。这个优先级可以描述为:

优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间
Ratio = ( Wait_t + Server_t ) / Server_t

从上式可以看到，作业的服务时间是固定的，优先级随着已等待时间的提高而变大
题目：

我来占个位

好了，话不多说，代码说话：

我也是

！结果展示！

2. 可复用的代码部分【！！！】

2.1 PCB结构体

typedef struct process{
    string name;//进程名称
    double arriveTime;//到达时间
    double startTime;//开始时间 这样比较细
    double serveTime;//服务时间
    double endTime;//结束时间
    double rt;//周转时间
    double wrt;//带权周转时间
    double rr_runTime;//RR算法实际处理机上运行的时间
}pcb;
1
2
3
4
5
6
7
8
9
10

2.2 其余可复用的重要部分

//输入
void input(vector<pcb>* p){
    for(int i=1;i<=p->size()-1;i++){
        cout<<"Please input the process name: "<<endl;
        cin>>p->at(i).name;//指针存在获得的意义
        cout<<"Please input the process arriveTime: "<<endl;
        cin>>p->at(i).arriveTime;
        cout<<"Please input the process serveTime: "<<endl;
        cin>>p->at(i).serveTime;
    }
    cout<<"Show: "<<endl;
    out(p);
    cout<<endl;
}

//输出
void out(vector<pcb>* p){
    cout<<"prcs_n\tari_t\tsrt_t\tsrv_t\tend_t\trd_t\twrd_t\t"<<endl;
    pcb temp;
    for(int i=1;i<=p->size()-1;i++){
        temp=p->at(i);
        cout<<temp.name<<'\t'
            <<temp.arriveTime<<"\t"
            <<temp.startTime<<"\t"
            <<temp.serveTime<<"\t"
            <<temp.endTime<<"\t"
            <<temp.rt<<'\t'
            <<temp.wrt<<endl;
    }
}

//计算
void comput(vector<pcb>* p){
    for(int i=1;i<=p->size()-1;i++){
        p->at(i).rt=p->at(i).endTime - p->at(i).arriveTime;
        p->at(i).wrt=p->at(i).rt / p->at(i).serveTime;
    }
}

//界面展示
void showScreen(){
    cout<<"There are four kinds of the OS of Scheduling algorithm"<<endl;
    cout<<'\t'<<"1.Fist come first serve AL (FCFS)"<<endl;
    cout<<'\t'<<"2.Shortest job first AL (SJF)"<<endl;
    cout<<'\t'<<"3.Round Robin AL (RR)"<<endl;
    cout<<'\t'<<"4.High response ratio next AL (HRRN)"<<endl;
    cout<<"Please input that you need other one of these kinds(another number is out) :"<<endl;
}

//检查 可复用
bool check(string a){
    for(int i=0;i<a.size();i++)
        if(a[i]<'0'||a[i]>'9')return false;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

3. 核心算法部分【FCFS-SJF-RR-HRRN】

3.1 FCFS核心算法

void FCFS(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    for(int i=1;i<=p->size()-1;i++){
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime+p->at(i).serveTime;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2 SJF核心算法

void SJF(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }

    for(int i=1;i<=p->size()-1;i++){
        //第一个运行时，要对同时到达的进程对服务时间从小到大进行排序，最小的放在下一个要执行的位置上
        {
            //记录i==1进程的到达时间 //不只是对于i==1时，对于每一个同时到达的进程，在到达时间相同时，都应该再排一次序【逻辑上】
            int arvt=p->at(i).arriveTime;
            int svt=p->at(i).serveTime;
            int min_dex=i;
            //直接找出到达时间一样，并且服务时间最短的进程和下一个要执行的进程互换位置【打擂台】
            for(int j=i+1;j<=(int)(p->size())-1;j++){
                if(p->at(j).arriveTime!=arvt)break;
                if(svt > p->at(j).serveTime)
                    svt=p->at(j).serveTime,min_dex=j;
            }
            swap(p->at(i),p->at(min_dex));
        }
        //对合理的进程上CPU运行
        //对于开始时间，应该选择的是上一个进程的结束时间和当前进程的到达时间之中最大的那个时间
        /*
         * 对于一件平常的规律，他是不是就是一个普遍的规律，应该如何判断：
         *  1.首先他们要有相同的规律
         *  2.其次这件事中，最简单的一件事的规律，就是这个庞大的现象的总体规律
         *      总结：这样得出的结论才是正确、科学的
         */
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime + p->at(i).serveTime;
        //在上CPU运行的这个进程的开始到结束这段时间内，到达的所有其它进程再对他们的服务时间从小到大进行排序：
        /*    两种情况：
         *      1.如果在这段时间内有其它进程进入，那么这里排完序的结果，就是下一个运行的进程
         *      2.如果在这段时间内没有其他进程进入，那么下一次的服务优先时间就不能够做到保证，
         *      但是，其实对于这种情况而言，就不需要判断后面不同时间内到达的进程的最短服务时间了，只需要对同时间到达的进程判断最短就可以
         */
        if(i+1<=p->size()-1){
            int svt=p->at(i+1).serveTime;
            int min_dex=i+1;
            //直接找出到达时间一样，并且服务时间最短的进程和下一个要执行的进程互换位置
            for(int j=i+1;j<=(int)(p->size())-1;j++){//其实就类似于在打擂台，谁赢谁上
                if(p->at(j).arriveTime > p->at(i).endTime)break;
                if(svt > p->at(j).serveTime)
                    svt=p->at(j).serveTime,min_dex=j;
            }
            swap(p->at(i+1),p->at(min_dex));
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

3.3 RR核心算法

void RR(vector<pcb>* p,int tpic){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    //counter表示下一个需要入队列的进程 Size表示所有进程数
    int Size=p->size()-1,counter=1;
    int runtime=0,//CPU上需要的运行时间
    stime=0,//时间线的基础上，对于一个上处理机的进程的开始运行的时间
    etime=0;//运行结束的时间
    queue<pcb*> q;//使用指针的队列，为了compute计算，并且保持数据的一致性
    q.push(&(p->at(counter++)));
    while(!q.empty()){
        pcb* t=q.front();q.pop();
        //一般的时间不足以运行结束的情况
        if(t->rr_runTime+tpic < t->serveTime){
            //计算进程的实际开始运行的时间【如果两个进程的结束时间和到达时间差距非常大，那么stime就会出错】
            stime= stime < t->arriveTime ? t->arriveTime : stime;//原始写法
            // stime= max(t->arriveTime , stime);//可以这么简化其实
            t->startTime=stime;
            runtime=tpic;
            etime=stime+runtime;
            //在运行的过程中让这段时间到来的进程先进入RR队列
            for(;counter<=Size && p->at(counter).arriveTime<=etime;counter++)
                q.push(&(p->at(counter)));
            t->rr_runTime+=runtime;
            q.push(t);//由于还没有运行完，因此再次回到队尾等待下次运行
            stime=etime;//先更新一次下一个进程可能的开始时间
        }
        //运行结束时候的情况
        else {
            //结束
            stime= stime < t->arriveTime ? t->arriveTime : stime;
            t->startTime=stime;
            runtime=t->serveTime - t->rr_runTime;
            etime=stime+runtime;
            for(;counter<=Size && p->at(counter).arriveTime<=etime;counter++)
                q.push(&(p->at(counter)));
            t->rr_runTime+=runtime,//runtime+t->rr_runTime==t->serveTime 结束了
            t->endTime=etime;//结束时需要更新这个进程的实际end时间

            //已经执行结束，因此不再需要继续进入队列等待下次调用了，已经解放了，自由了！

            stime=etime;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

3.4 HRRN核心算法

void HRRN(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    // out(p); //debug
    for(int i=1;i<=p->size()-1;i++){
        //第一个运行时，要对同时到达的进程对服务时间从小到大进行排序，最小的放在下一个要执行的位置上
        //HRRN中，由响应比公式可知，同时到达的进程，执行先来先服务的规则，而不是根据短作业，运行时间少的先上CPU

        //对合理的进程上CPU运行
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime+p->at(i).serveTime;
        //在开始到结束这段时间内到达的所有其它进程，再选出响应比最大的进程作为下一个上CPU运行的进程
        if(i+1<=p->size()-1){
            double max_ratio=(p->at(i+1).serveTime + (p->at(i).endTime - p->at(i+1).arriveTime)) / p->at(i+1).serveTime;//计算高响应比
            int max_dex=i+1;
            //直接找出响应比最大的进程和下一个要执行的进程互换位置 //不需要考虑是不是同时到达的进程，同时到达的话直接就先来先服务完事
            for(int j=i+1;j<=(int)(p->size())-1;j++){
                //这个地方需要去对i+1的第一个元素也判断，虽然上面已经对i+1的元素取值了，但是还并不知道第一个要判断的元素是否也满足要求【重叠性的意义】
                if(p->at(j).arriveTime > p->at(i).endTime)break;
                double tratio=(p->at(j).serveTime + (p->at(i).endTime - p->at(j).arriveTime)) / p->at(j).serveTime;
                if(max_ratio < tratio)
                    max_ratio=tratio,max_dex=j;
            }
            swap(p->at(i+1),p->at(max_dex));
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

4. 最后为各位观众老爷献上完整项目代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//PCB结构
typedef struct process{
    string name;//进程名称
    double arriveTime;//到达时间
    double startTime;//开始时间 这样比较细
    double serveTime;//服务时间
    double endTime;//结束时间
    double rt;//周转时间
    double wrt;//带权周转时间
    double rr_runTime;//RR算法实际处理机上运行的时间
}pcb;

//组件代码的声明部分
void input(vector<pcb>* p);
void out(vector<pcb>* p);
void comput(vector<pcb>* p);
void showScreen();
bool check(string a);
void FCFS(vector<pcb>* p);
void SJF(vector<pcb>* p);
void RR(vector<pcb>* p,int tpic);
void HRRN(vector<pcb>* p);
//四种调度算法整体运行的声明部分
void fcfs();
void sjf();
void rr();
void hrrn();


int main() {
    int opt=0;
    bool flag=true;
    do{
        showScreen();
        cin>>opt;
        switch (opt) {
            case 1:fcfs();break;
            case 2:sjf();break;
            case 3:rr();break;
            case 4:hrrn();break;
            default:
                flag= false;
        }
    }while(flag);
    cout<<endl;
    cout<<"Hey! Have a lucky day Guy!"<<endl;

    return 0;
}
 

//FCFS总体运行
void fcfs(){
    string N;
    cout<<"please input process number:"<<endl;
    cin>>N;
    while(!check(N)){
        cout<<"Input into PROCESS NUMBERS !!!"<<endl;
        cin>>N;
    }
    int n=atoi(N.c_str());
    vector<pcb> p(n+1);
    input(&p);
    FCFS(&p);
    comput(&p);
    cout<<"Answer:"<<endl;
    out(&p);
    cout<<endl;
}
//SJF总体运行
void sjf(){
    string N;
    cout<<"please input process number:"<<endl;
    cin>>N;
    while(!check(N)){
        cout<<"Input into PROCESS NUMBERS !!!"<<endl;
        cin>>N;
    }
    int n=atoi(N.c_str());
    vector<pcb> p(n+1);
    input(&p);
    SJF(&p);
    comput(&p);
    cout<<"Answer:"<<endl;
    out(&p);
    cout<<endl;
}
//RR总体运行
void rr(){
    string N;
    cout<<"please input process number:"<<endl;
    cin>>N;
    while(!check(N)){
        cout<<"Input into PROCESS NUMBERS !!!"<<endl;
        cin>>N;
    }
    int n=atoi(N.c_str());
    vector<pcb> p(n+1);
    cout<<"Please input time piece size: "<<endl;
    string Tpiece;
    cin>>Tpiece;
    while(!check(Tpiece)){
        cout<<"Please input TIME PIECE SIZE !!! "<<endl;
        cin>>Tpiece;
    }
    int tpiece=atoi(Tpiece.c_str());

    input(&p);
    cout<<"timePiece: "<<tpiece<<endl<<endl;
    RR(&p,tpiece);
    comput(&p);
    cout<<"Answer:"<<endl;
    out(&p);
    cout<<"timePiece: "<<tpiece<<endl;
}
//HRRN总体运行
void hrrn(){
    string N;
    cout<<"please input process number:"<<endl;
    cin>>N;
    while(!check(N)){
        cout<<"Input into PROCESS NUMBERS !!!"<<endl;
        cin>>N;
    }
    int n=atoi(N.c_str());
    vector<pcb> p(n+1);
    input(&p);
    HRRN(&p);
    comput(&p);
    cout<<"Answer:"<<endl;
    out(&p);
}

//输入 可复用
void input(vector<pcb>* p){
    for(int i=1;i<=p->size()-1;i++){
        cout<<"Please input the process name: "<<endl;
        cin>>p->at(i).name;//指针存在获得的意义
        cout<<"Please input the process arriveTime: "<<endl;
        cin>>p->at(i).arriveTime;
        cout<<"Please input the process serveTime: "<<endl;
        cin>>p->at(i).serveTime;
    }
    cout<<"Show: "<<endl;
    out(p);
    cout<<endl;
}

//输出 可复用
void out(vector<pcb>* p){
    cout<<"prcs_n\tari_t\tsrt_t\tsrv_t\tend_t\trd_t\twrd_t\t"<<endl;
    pcb temp;
    for(int i=1;i<=p->size()-1;i++){
        temp=p->at(i);
        cout<<temp.name<<'\t'
            <<temp.arriveTime<<"\t"
            <<temp.startTime<<"\t"
            <<temp.serveTime<<"\t"
            <<temp.endTime<<"\t"
            <<temp.rt<<'\t'
            <<temp.wrt<<endl;
    }
}

//计算 可复用
void comput(vector<pcb>* p){
    for(int i=1;i<=p->size()-1;i++){
        p->at(i).rt=p->at(i).endTime - p->at(i).arriveTime;
        p->at(i).wrt=p->at(i).rt / p->at(i).serveTime;
    }
}

//屏幕展示 可复用
void showScreen(){
    cout<<"There are four kinds of the OS of Scheduling algorithm"<<endl;
    cout<<'\t'<<"1.Fist come first serve AL (FCFS)"<<endl;
    cout<<'\t'<<"2.Shortest job first AL (SJF)"<<endl;
    cout<<'\t'<<"3.Round Robin AL (RR)"<<endl;
    cout<<'\t'<<"4.High response ratio next AL (HRRN)"<<endl;
    cout<<"Please input that you need other one of these kinds(another number is out) :"<<endl;
}

//检查 可复用
bool check(string a){
    for(int i=0;i<a.size();i++)
        if(a[i]<'0'||a[i]>'9')return false;
    return true;
}

//FCFS核心算法
void FCFS(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    for(int i=1;i<=p->size()-1;i++){
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime+p->at(i).serveTime;
    }
}

//SJF核心算法
void SJF(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    // out(p); //debug
    for(int i=1;i<=p->size()-1;i++){
        //第一个运行时，要对同时到达的进程对服务时间从小到大进行排序，最小的放在下一个要执行的位置上
        {
            //记录i==1进程的到达时间 //不只是对于i==1时，对于每一个同时到达的进程，在到达时间相同时，都应该再排一次序【逻辑上】
            int arvt=p->at(i).arriveTime;
            int svt=p->at(i).serveTime;
            int min_dex=i;
            //直接找出到达时间一样，并且服务时间最短的进程和下一个要执行的进程互换位置【打擂台】
            for(int j=i+1;j<=(int)(p->size())-1;j++){
                if(p->at(j).arriveTime!=arvt)break;
                if(svt > p->at(j).serveTime)
                    svt=p->at(j).serveTime,min_dex=j;
            }
            swap(p->at(i),p->at(min_dex));
        }
        //对合理的进程上CPU运行
        //对于开始时间，应该选择的是上一个进程的结束时间和当前进程的到达时间之中最大的那个时间
        /*
         * 对于一件平常的规律，他是不是就是一个普遍的规律，应该如何判断：
         *  1.首先他们要有相同的规律
         *  2.其次这件事中，最简单的一件事的规律，就是这个庞大的现象的总体规律
         *      总结：这样得出的结论才是正确、科学的
         */
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime + p->at(i).serveTime;
        //在上CPU运行的这个进程的开始到结束这段时间内，到达的所有其它进程再对他们的服务时间从小到大进行排序：
        /*    两种情况：
         *      1.如果在这段时间内有其它进程进入，那么这里排完序的结果，就是下一个运行的进程
         *      2.如果在这段时间内没有其他进程进入，那么下一次的服务优先时间就不能够做到保证，
         *      但是，其实对于这种情况而言，就不需要判断后面不同时间内到达的进程的最短服务时间了，只需要对同时间到达的进程判断最短就可以
         */
        if(i+1<=p->size()-1){
            int svt=p->at(i+1).serveTime;
            int min_dex=i+1;
            //直接找出到达时间一样，并且服务时间最短的进程和下一个要执行的进程互换位置
            for(int j=i+1;j<=(int)(p->size())-1;j++){//其实就类似于在打擂台，谁赢谁上
                if(p->at(j).arriveTime > p->at(i).endTime)break;
                if(svt > p->at(j).serveTime)
                    svt=p->at(j).serveTime,min_dex=j;
            }
            swap(p->at(i+1),p->at(min_dex));
        }
    }

}

//RR核心算法
void RR(vector<pcb>* p,int tpic){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    //counter表示下一个需要入队列的进程 Size表示所有进程数
    int Size=p->size()-1,counter=1;
    int runtime=0,//CPU上需要的运行时间
    stime=0,//时间线的基础上，对于一个上处理机的进程的开始运行的时间
    etime=0;//运行结束的时间
    queue<pcb*> q;//使用指针的队列，为了compute计算，并且保持数据的一致性
    q.push(&(p->at(counter++)));
    while(!q.empty()){
        pcb* t=q.front();q.pop();
        //一般的时间不足以运行结束的情况
        if(t->rr_runTime+tpic < t->serveTime){
            //计算进程的实际开始运行的时间【如果两个进程的结束时间和到达时间差距非常大，那么stime就会出错】
            stime= stime < t->arriveTime ? t->arriveTime : stime;//原始写法
            // stime= max(t->arriveTime , stime);//可以这么简化其实
            t->startTime=stime;
            runtime=tpic;
            etime=stime+runtime;
            //在运行的过程中让这段时间到来的进程先进入RR队列
            for(;counter<=Size && p->at(counter).arriveTime<=etime;counter++)
                q.push(&(p->at(counter)));
            t->rr_runTime+=runtime;
            q.push(t);//由于还没有运行完，因此再次回到队尾等待下次运行
            stime=etime;//先更新一次下一个进程可能的开始时间
        }
        //运行结束时候的情况
        else {
            //结束
            stime= stime < t->arriveTime ? t->arriveTime : stime;
            t->startTime=stime;
            runtime=t->serveTime - t->rr_runTime;
            etime=stime+runtime;
            for(;counter<=Size && p->at(counter).arriveTime<=etime;counter++)
                q.push(&(p->at(counter)));
            t->rr_runTime+=runtime,//runtime+t->rr_runTime==t->serveTime 结束了
            t->endTime=etime;//结束时需要更新这个进程的实际end时间

            //已经执行结束，因此不再需要继续进入队列等待下次调用了，已经解放了，自由了！

            stime=etime;
        }
    }
}

//HRRN核心算法
void HRRN(vector<pcb>* p){
    for(int j=(int)(p->size())-1;j>1;j--){
        for(int i=1;i<j;i++){
            if(p->at(i).arriveTime>p->at(i+1).arriveTime)
                swap(p->at(i),p->at(i+1));
        }
    }
    // out(p); //debug
    for(int i=1;i<=p->size()-1;i++){
        //第一个运行时，要对同时到达的进程对服务时间从小到大进行排序，最小的放在下一个要执行的位置上
        //HRRN中，由响应比公式可知，同时到达的进程，执行先来先服务的规则，而不是根据短作业，运行时间少的先上CPU

        //对合理的进程上CPU运行
        p->at(i).startTime= ( i == 1 ? p->at(i).arriveTime : max(p->at(i-1).endTime,p->at(i).arriveTime) ) ;
        // if(p->at(i).arriveTime > p->at(i).startTime) p->at(i).startTime=p->at(i).arriveTime;//原始的写法
        p->at(i).endTime=p->at(i).startTime+p->at(i).serveTime;
        //在开始到结束这段时间内到达的所有其它进程，再选出响应比最大的进程作为下一个上CPU运行的进程
        if(i+1<=p->size()-1){
            double max_ratio=(p->at(i+1).serveTime + (p->at(i).endTime - p->at(i+1).arriveTime)) / p->at(i+1).serveTime;//计算高响应比
            int max_dex=i+1;
            //直接找出响应比最大的进程和下一个要执行的进程互换位置 //不需要考虑是不是同时到达的进程，同时到达的话直接就先来先服务完事
            for(int j=i+1;j<=(int)(p->size())-1;j++){
                //这个地方需要去对i+1的第一个元素也判断，虽然上面已经对i+1的元素取值了，但是还并不知道第一个要判断的元素是否也满足要求【重叠性的意义】
                if(p->at(j).arriveTime > p->at(i).endTime)break;
                double tratio=(p->at(j).serveTime + (p->at(i).endTime - p->at(j).arriveTime)) / p->at(j).serveTime;
                if(max_ratio < tratio)
                    max_ratio=tratio,max_dex=j;
            }
            swap(p->at(i+1),p->at(max_dex));
        }
    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352