高响应比优先调度算法c++
时间: 2023-10-18 08:01:18 浏览: 44
下面是一个简单的高响应比优先调度算法的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;
}
```
上述代码实现了一个简单的高响应比优先调度算法,其中使用了一个优先队列来按照响应比排序。在每个时间片中,将所有到达时间小于等于当前时间的进程加入优先队列中,然后取出响应比最高的进程执行。在执行完一个进程后,将到达时间小于等于当前时间的进程再次加入优先队列中,并将当前进程放回队列等待下一次执行。最后,计算平均响应时间和平均周转时间并输出结果。