多级反馈队列调度算法C++

下面是一个简单的多级反馈队列调度算法的C++实现：

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

using namespace std;

// 进程结构体
struct Process {
    int id;  // 进程标识符
    int arrival_time;  // 到达时间
    int burst_time;  // 执行时间
    int priority;  // 优先级
    int remaining_time;  // 剩余执行时间
    int wait_time;  // 等待时间
    int response_time;  // 响应时间
};

// 多级反馈队列调度算法
void MFQS(vector<Process>& processes, int quantum, int max_priority) {
    int current_time = 0;  // 当前时间
    int n = processes.size();  // 进程数量
    int completed = 0;  // 已完成的进程数
    vector<queue<Process>> queues(max_priority + 1);  // 多个队列
    vector<int> quantum_left(max_priority + 1);  // 每个队列的时间片

    // 先按到达时间排序
    sort(processes.begin(), processes.end(), [](const Process& a, const Process& b) {
        return a.arrival_time < b.arrival_time;
    });

    // 将所有进程加入第一级队列
    for (int i = 0; i < n; i++) {
        queues[0].push(processes[i]);
    }

    // 循环执行进程
    while (completed < n) {
        bool found = false;  // 是否找到可以执行的进程

        // 从高优先级队列开始查找
        for (int i = max_priority; i >= 0; i--) {
            if (!queues[i].empty()) {
                Process& p = queues[i].front();
                found = true;

                // 计算响应时间
                if (p.response_time == -1) {
                    p.response_time = current_time - p.arrival_time;
                }

                // 执行进程
                if (p.remaining_time <= quantum_left[i]) {
                    current_time += p.remaining_time;
                    p.wait_time = current_time - p.arrival_time - p.burst_time;
                    p.remaining_time = 0;
                    completed++;
                } else {
                    current_time += quantum_left[i];
                    p.remaining_time -= quantum_left[i];
                    queues[i + 1].push(p);
                }

                // 重置时间片
                quantum_left[i] = quantum;

                // 从队列中移除进程
                queues[i].pop();
                break;
            }
        }

        // 如果没有可以执行的进程，则时间加1
        if (!found) {
            current_time++;
        }
    }

    // 计算平均等待时间和平均响应时间
    double total_wait_time = 0;
    double total_response_time = 0;
    for (int i = 0; i < n; i++) {
        total_wait_time += processes[i].wait_time;
        total_response_time += processes[i].response_time;
    }
    double avg_wait_time = total_wait_time / n;
    double avg_response_time = total_response_time / n;

    // 输出结果
    printf("Average Wait Time: %.2f\n", avg_wait_time);
    printf("Average Response Time: %.2f\n", avg_response_time);
}

int main() {
    // 测试数据
    vector<Process> processes = {
        {1, 0, 10, 2, -1, 0, -1},
        {2, 1, 5, 1, -1, 0, -1},
        {3, 2, 3, 3, -1, 0, -1},
        {4, 3, 2, 4, -1, 0, -1},
        {5, 4, 5, 2, -1, 0, -1}
    };
    int quantum = 2;
    int max_priority = 4;

    // 执行多级反馈队列调度算法
    MFQS(processes, quantum, max_priority);

    return 0;
}

在上面的实现中，我们使用了一个`vector`来存储多个队列，每个队列表示一个优先级。我们还使用了一个`vector`来存储每个队列的时间片。在循环执行进程时，我们从高优先级队列开始查找，如果找到可以执行的进程，则执行该进程，否则时间加1。当一个进程完成时，我们将其等待时间设置为当前时间减去到达时间减去执行时间，并将其从队列中移除。最后，我们计算所有进程的平均等待时间和平均响应时间，并输出结果。