C++写一个高响应比优先调度算法

高响应比优先调度算法，又称为高响应比法（Highest Response Ratio Next, HRRN），是一种实时调度算法。该算法依据等待时间和运行时间对进程进行排序，以提高响应速度和系统吞吐量。具体实现可以使用公式：响应比 = （等待时间 + 运行时间）/ 运行时间，选择响应比最高的进程运行。这种算法的优点在于对长作业和短作业都有较好的响应时间，缺点在于容易产生优先反转，需要设计好锁机制防止出现这种情况。

相关问题

用C++语言编程实现最高响应比优先调度算法

最高响应比优先调度算法是一种常用的进程调度算法，其核心思想是根据进程的响应比来确定下一个要执行的进程。具体实现可以参考以下代码：

#include <stdio.h>

struct process {
    int pid;  // 进程ID
    int burst_time;  // 进程执行时间
    int arrival_time;  // 进程到达时间
    int waiting_time;  // 进程等待时间
    int turnaround_time;  // 进程周转时间
    float response_ratio;  // 进程响应比
};

// 计算进程的等待时间、周转时间和响应比
void calculate_time(struct process *p, int n) {
    int i;
    float sum_waiting_time = 0, sum_turnaround_time = 0;
    for (i = 0; i < n; i++) {
        p[i].turnaround_time = p[i].burst_time + p[i].waiting_time;
        p[i].response_ratio = (float)p[i].turnaround_time / p[i].burst_time;
        sum_waiting_time += p[i].waiting_time;
        sum_turnaround_time += p[i].turnaround_time;
    }
    printf("平均等待时间：%.2f\n", sum_waiting_time / n);
    printf("平均周转时间：%.2f\n", sum_turnaround_time / n);
}

// 最高响应比优先调度算法
void hrn_scheduling(struct process *p, int n) {
    int i, j, current_time = 0, total_burst_time = 0;
    float max_response_ratio;
    struct process *current_process;
    // 计算总的执行时间
    for (i = 0; i < n; i++) {
        total_burst_time += p[i].burst_time;
    }
    // 按照到达时间排序
    for (i = 0; i < n - 1; i++) {
        for (j = i + 1; j < n; j++) {
            if (p[i].arrival_time > p[j].arrival_time) {
                struct process temp = p[i];
                p[i] = p[j];
                p[j] = temp;
            }
        }
    }
    // 执行进程
    while (current_time < total_burst_time) {
        max_response_ratio = -1;
        current_process = NULL;
        // 找到响应比最高的进程
        for (i = 0; i < n; i++) {
            if (p[i].burst_time > 0 && p[i].arrival_time <= current_time) {
                if (p[i].response_ratio > max_response_ratio) {
                    max_response_ratio = p[i].response_ratio;
                    current_process = &p[i];
                }
            }
        }
        // 执行进程
        if (current_process != NULL) {
            current_process->burst_time--;
            current_time++;
            // 更新等待时间
            for (i = 0; i < n; i++) {
                if (p[i].burst_time > 0 && p[i].arrival_time <= current_time && &p[i] != current_process) {
                    p[i].waiting_time++;
                }
            }
        } else {
            current_time++;
        }
    }
    // 计算进程的等待时间、周转时间和响应比
    calculate_time(p, n);
}

int main() {
    int i, n;
    struct process p[10];
    printf("请输入进程数：");
    scanf("%d", &n);
    printf("请输入每个进程的执行时间和到达时间：\n");
    for (i = 0; i < n; i++) {
        printf("进程%d：", i + 1);
        scanf("%d %d", &p[i].burst_time, &p[i].arrival_time);
        p[i].pid = i + 1;
        p[i].waiting_time = 0;
    }
    hrn_scheduling(p, n);
    return 0;
}

以上代码实现了最高响应比优先调度算法，可以根据输入的进程执行时间和到达时间计算出每个进程的等待时间、周转时间和响应比，并输出平均等待时间和平均周转时间。

高响应比优先调度算法c++

下面是一个简单的高响应比优先调度算法的C++代码示例：

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

// 进程结构体
struct Process {
    int pid;       // 进程ID
    int priority;  // 优先级
    int arrival;   // 到达时间
    int burst;     // 执行时间
    int response;  // 响应时间
    int turnaround; // 周转时间
};

// 定义一个比较器，用于将优先级高的进程排在队列前面
struct Compare {
    bool operator()(const Process& p1, const Process& p2) {
        double r1 = 1.0 * (p1.burst + p1.response) / p1.burst;
        double r2 = 1.0 * (p2.burst + p2.response) / p2.burst;
        return r1 < r2;
    }
};

// 高响应比优先调度算法
void HRRN(Process processes[], int n) {
    // 按照到达时间排序
    sort(processes, processes + n, [](Process p1, Process p2) {
        return p1.arrival < p2.arrival;
    });

    // 创建一个优先队列，按照响应比排序
    priority_queue<Process, vector<Process>, Compare> pq;
    int time = 0; // 当前时间
    int sum_response_time = 0; // 总响应时间
    int sum_turnaround_time = 0; // 总周转时间

    for (int i = 0; i < n; i++) {
        // 将到达时间小于等于当前时间的进程加入队列
        while (i < n && processes[i].arrival <= time) {
            processes[i].response = time - processes[i].arrival;
            pq.push(processes[i]);
            i++;
        }

        // 如果队列为空，说明当前时间没有进程需要执行，时间加1
        if (pq.empty()) {
            time++;
            i--;
            continue;
        }

        // 取出一个响应比最高的进程执行
        Process p = pq.top();
        pq.pop();

        // 更新响应时间和周转时间
        sum_response_time += p.response;
        sum_turnaround_time += time + p.burst - p.arrival;

        // 执行进程
        time += p.burst;

        // 将到达时间小于等于当前时间的进程加入队列
        while (i < n && processes[i].arrival <= time) {
            processes[i].response = time - processes[i].arrival;
            pq.push(processes[i]);
            i++;
        }

        // 将该进程放回队列，等待下一次执行
        p.burst = 0;
        pq.push(p);
    }

    // 计算平均响应时间和平均周转时间
    double avg_response_time = 1.0 * sum_response_time / n;
    double avg_turnaround_time = 1.0 * sum_turnaround_time / n;

    // 输出结果
    cout << "平均响应时间: " << avg_response_time << endl;
    cout << "平均周转时间: " << avg_turnaround_time << endl;
}

int main() {
    // 创建进程数组
    Process processes[] = {
        {1, 3, 0, 8},
        {2, 1, 1, 4},
        {3, 4, 2, 9},
        {4, 5, 3, 5},
        {5, 2, 4, 6}
    };
    int n = sizeof(processes) / sizeof(Process);

    // 调用高响应比优先调度算法
    HRRN(processes, n);

    return 0;
}

上述代码实现了一个简单的高响应比优先调度算法，其中使用了一个优先队列来按照响应比排序。在每个时间片中，将所有到达时间小于等于当前时间的进程加入优先队列中，然后取出响应比最高的进程执行。在执行完一个进程后，将到达时间小于等于当前时间的进程再次加入优先队列中，并将当前进程放回队列等待下一次执行。最后，计算平均响应时间和平均周转时间并输出结果。