操作系统时间片轮转算法、高响应比优先算法C++代码实现

• 问题描述及需求分析

问题描述：

设计程序模拟进程的高响应比优先调度和时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统，它们需要的服务时间分别为S1, … ,Sn。如果选择RR算法，则需要指定时间片大小q，采用时间片轮转RR进程调度算法进行调度，如果选择高响应比优先调度算法，则可以直接调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。

程序要求如下：

1）进程个数n；每个进程的到达时间T1, … ,Tn和服务时间S1, … ,Sn；如果选择时间片轮转法，则要输入时间片大小q。

2）要求高响应比优先和时间片轮转法RR调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；

3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；

4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间

• 要求

1)认真复习高响应比优先和时间片轮转RR进程调度算法，熟悉进程调度的执行过程；

2)独立编程、调试程序；

3)根据具体实验要求，完成好实验报告（包括实验的目的、内容、要求、源程序、实例运行结果截图）。

完整代码

#include 
#include 
#include 
using namespace std;

typedef struct {
    int id;
    int ArrivalTime;
    int ServiceTime;
    int StartTime;
    int LeaveTime;
    int FinishedTime;
    int WholeTime;
    double WeightWholeTime;
    float H;//响应比
    bool In;   //标记进程是否入队
}RR;

static queue  Queue;


static int q;  //时间片
static int n;  //进程的数量
static  RR RRarray[100];

static double AverageWT = 0, AverageWWT = 0;


void Input() {

    cout << "进程调度开始" << endl;
    cout << "请输入进程数 n = ";
    cin >> n;

    cout << "请输入时间片 q = ";
    cin >> q;

    for (int i = 0; i < n; i++) {
        RRarray[i].id = i;
        RRarray[i].In = false;
    }
    cout << "请分别输入这" << n << "个进程的到达时间" << endl;
    for (int i = 0; i < n; i++) {
        cin >> RRarray[i].ArrivalTime;
    }
    cout << "请分别输入这" << n << "个进程的服务时间" << endl;
    for (int i = 0; i < n; i++) {
        cin >> RRarray[i].ServiceTime;
        RRarray[i].LeaveTime = RRarray[i].ServiceTime;
    }
}

void SortArrival() {
    int temp1, temp2, temp3, temp4;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (RRarray[i].ArrivalTime > RRarray[j].ArrivalTime) {
                temp1 = RRarray[i].ArrivalTime;
                RRarray[i].ArrivalTime = RRarray[j].ArrivalTime;
                RRarray[j].ArrivalTime = temp1;
                temp2 = RRarray[i].ServiceTime;
                RRarray[i].ServiceTime = RRarray[j].ServiceTime;
                RRarray[j].ServiceTime = temp2;
                temp3 = RRarray[i].LeaveTime;
                RRarray[i].LeaveTime = RRarray[j].LeaveTime;
                RRarray[j].LeaveTime = temp3;
                temp4 = RRarray[i].id;
                RRarray[i].id = RRarray[j].id;
                RRarray[j].id = temp4;
            }
        }
    }
}


void RR1() {//时间片轮转RR算法
    SortArrival();
    int time = 0;  //时间

    int finishId[100], finishTime[100];
    int timeCnt = 0;
    int idCnt = 0;

    time = RRarray[0].ArrivalTime; //第一个进程到达，记录开始执行时间
    Queue.push(RRarray[0]);//首进程入列
    cout << "时刻" << time << "进程开始执行！" << endl;
    //初始化finishTime数组
    for (int i = 0; i < n; i++) {
        finishTime[i] = 0;
        finishId[i] = -1;
    }

    while (!Queue.empty())
    {
        //判断每次增加的时间addtime
        if (Queue.front().LeaveTime <= q)
        {
            time += Queue.front().LeaveTime;
            Queue.front().LeaveTime = 0;
        }
        else
        {
            Queue.front().LeaveTime -= q;
            time += q;
        }


        for (int j = 1; j < n; j++)   //入队
        {
            if (RRarray[j].In == false && RRarray[j].ArrivalTime <= time)
            {
                Queue.push(RRarray[j]);
                RRarray[j].In = true;
            }
        }

        if (Queue.front().LeaveTime == 0)  //把执行完的进程退出队列
        {
            finishId[idCnt] = Queue.front().id;
            idCnt += 1;
            finishTime[timeCnt] = time;
            timeCnt += 1;
            Queue.pop();   //进程已经服务完了，将其退栈
        }
        else
        {
            Queue.push(Queue.front());
            Queue.pop();
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (RRarray[i].id == finishId[j]) {
                RRarray[i].FinishedTime = finishTime[j];
                break;
            }
        }

    }
    cout << endl;
    for (int i = 0; i < n; i++) {
        cout << "进程" << RRarray[i].id << ":时刻" << RRarray[i].FinishedTime << "执行完成！" << endl;
        RRarray[i].WholeTime = RRarray[i].FinishedTime - RRarray[i].ArrivalTime;
        RRarray[i].WeightWholeTime = (double)RRarray[i].WholeTime / RRarray[i].ServiceTime;

    }

    double x = 0, y = 0;

    for (int i = 0; i < n; i++) {

        x = x + RRarray[i].WholeTime;
        y = y + RRarray[i].WeightWholeTime;
    }
    AverageWT = x / n;
    AverageWWT = y / n;
}

void HRRN(){
    int num =1;
    for(int m=0;m=RRarray[m-1].ArrivalTime){
                RRarray[m].StartTime = RRarray[m-1].FinishedTime;
            }
            else{
                RRarray[m].StartTime = RRarray[m-1].ArrivalTime;
            }
            RRarray[m].FinishedTime = RRarray[m].StartTime + RRarray[m].ServiceTime;
        }

        int i = 0;
        for(int a=m+1;amax)
            {
                max=RRarray[k+1].H;
                next=k+1;
            }

        }
        RR temp;
        temp=RRarray[m+1];
        RRarray[m+1]=RRarray[next];
        RRarray[next]=temp;
    }
}

void show() {
    cout<<"******************************************"<>a;
    if(a == 1){
        RR1();
        show();
    }else if(a == 2){
        HRRN();
    }else{
        cout<<"输入有误！"< 
 
输出：
 
RR算法
 
q=1
 
 
q=4
 
 
 
 
高响应比优先