基于不同到达时间的Round Robin算法C++实现问题求助

问题根源 #

你的代码存在两个核心问题，导致到达时间无序时结果错误：

1. 直接按输入顺序将进程加入队列，没有按到达时间升序排序，到达更早的进程可能被延后处理。
2. 调度循环中没有检查当前时间点已到达的进程，直接处理队列头部，不符合RR调度的就绪队列逻辑——RR只能处理当前已到达且未完成的进程。

修复方案 #

1. 先收集所有进程，按到达时间升序排序，确保能按到达顺序将进程加入就绪队列。
2. 使用两个结构：一个存储所有排序后的进程，一个作为就绪队列；每次调度前，把所有到达时间≤当前时间的进程加入就绪队列。
3. 如果就绪队列为空，说明当前无进程可执行，直接将当前时间跳转到下一个未到达进程的到达时间。
4. 按RR规则处理就绪队列中的进程：剩余时间≤时间片则执行完毕，计算周转时间(TAT)和等待时间(WT)；否则执行一个时间片后重新加入就绪队列。

修复后的完整代码 #

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct Process {  
    int id;            // 进程ID
    int at;            // 到达时间
    int et;            // 执行时间（burst time）
    int rt;            // 剩余执行时间
};

// 按到达时间升序排序的比较函数
bool compareByArrival(const Process& a, const Process& b) {
    return a.at < b.at;
}

int main() {
    int n; // 进程数量
    int quantum; // 时间片

    // 获取用户输入
    cout << "Enter the number of processes: ";
    cin >> n;
    cout << "Enter the time quantum: ";
    cin >> quantum;

    // 存储所有进程的向量
    vector<Process> allProcesses;

    // 输入每个进程信息
    for (int i = 0; i < n; i++) {
        Process p;
        cout << "Process " << i << ":\n";
        cout << "Arrival time: ";
        cin >> p.at;
        cout << "Execution time: ";
        cin >> p.et;
        p.rt = p.et;
        p.id = i + 1;
        allProcesses.push_back(p);
    }

    // 按到达时间升序排序
    sort(allProcesses.begin(), allProcesses.end(), compareByArrival);

    queue<Process> readyQueue; // 就绪队列
    int current_time = 0;
    int total_tat = 0;
    int total_wt = 0;
    int processed = 0; // 已完成的进程数
    int idx = 0; // 遍历allProcesses的索引

    while (processed < n) {
        // 将所有到达时间≤当前时间的进程加入就绪队列
        while (idx < n && allProcesses[idx].at <= current_time) {
            readyQueue.push(allProcesses[idx]);
            idx++;
        }

        if (readyQueue.empty()) {
            // 无就绪进程，跳转到下一个进程的到达时间
            current_time = allProcesses[idx].at;
            continue;
        }

        Process current_process = readyQueue.front();
        readyQueue.pop();

        if (current_process.rt <= quantum) {
            // 进程执行完毕
            current_time += current_process.rt;
            int tat = current_time - current_process.at;
            int wt = tat - current_process.et;
            total_tat += tat;
            total_wt += wt;
            processed++;
        } else {
            // 执行一个时间片后重新加入就绪队列
            current_time += quantum;
            current_process.rt -= quantum;
            // 先把当前时间点新到达的进程加入就绪队列，再把当前进程加入队尾
            while (idx < n && allProcesses[idx].at <= current_time) {
                readyQueue.push(allProcesses[idx]);
                idx++;
            }
            readyQueue.push(current_process);
        }
    }

    // 计算平均周转时间和平均等待时间
    double avg_tat = static_cast<double>(total_tat) / n;
    double avg_wt = static_cast<double>(total_wt) / n;

    // 输出结果
    cout << "\nAverage Turnaround Time: " << avg_tat << endl;
    cout << "Average Waiting Time: " << avg_wt << endl;

    return 0;
}

测试验证 #

用你提供的无序输入测试：

process   arrival time    burst time
 p0           2               6
 p1           5               2
 p2           1               8
 p3           0               3
 p4           4               4

quantum=3时，修复后的代码输出：

Average Turnaround Time: 13.8
Average Waiting Time: 9.2

与正确结果一致。

内容的提问来源于stack exchange，提问作者anita