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

### HRRN 调度算法在 Linux 下的 C++ 实现

HRRN（High Response Ratio Next）是一种基于优先级的调度算法，旨在平衡短作业和长作业之间的执行顺序。该算法通过计算每个进程的响应比率来决定下一个要运行的进程。响应比率定义为：

\[ \text{Response Ratio} = \frac{\text{Waiting Time} + \text{Service Time}}{\text{Service Time}} \]

当一个新进程到达或当前进程完成时，操作系统会重新评估所有等待队列中的进程并选择具有最高响应比率的进程。

#### 代码实现

以下是 HRRN 算法的一个简单 C++ 实现在 Linux 环境下的例子[^2]：

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

using namespace std;

struct Process {
    int id;
    int burstTime;     // 执行时间
    int arrivalTime;   // 到达时间
    int waitingTime;   // 等待时间
};

bool compare(Process p1, Process p2) {
    double ratio1 = (double)(p1.waitingTime + p1.burstTime) / p1.burstTime;
    double ratio2 = (double)(p2.waitingTime + p2.burstTime) / p2.burstTime;
    
    return ratio1 > ratio2 || (ratio1 == ratio2 && p1.arrivalTime < p2.arrivalTime);
}

void hrrnScheduling(vector<Process>& processes) {
    vector<Process> readyQueue(processes); // 创建就绪队列副本
    
    sort(readyQueue.begin(), readyQueue.end(), [](const Process& a, const Process& b){
        return a.arrivalTime < b.arrivalTime;
    });

    int currentTime = 0;
    while (!readyQueue.empty()) {
        for (auto &process : readyQueue) {
            if (process.arrivalTime <= currentTime) {
                process.waitingTime = max(currentTime - process.arrivalTime, 0);
            }
        }

        stable_sort(readyQueue.begin(), readyQueue.end(), compare);

        auto it = remove_if(readyQueue.begin(), readyQueue.end(),
                            [&currentTime](const Process& p){return p.arrivalTime > currentTime;});
        
        if(it != readyQueue.end()){
            Process currentProcess = *it;
            
            cout << "Executing P" << currentProcess.id << endl;
            currentTime += currentProcess.burstTime;
            readyQueue.erase(remove(readyQueue.begin(), readyQueue.end(), currentProcess), readyQueue.end());
        }else{
            ++currentTime;
        }
    }
}

int main() {
    vector<Process> processes = {{1, 10, 0}, {2, 5, 1}, {3, 8, 2}};
    
    hrrnScheduling(processes);

    return 0;
}

此程序模拟了一个简单的 HRRN 调度器工作流程，在每次循环迭代中更新各个进程的状态，并按照响应比例最高的原则挑选下一次应该被执行的任务。