C语言最高响应比算法详解（小白也能学会的作业调度实现）

C语言实现步骤

我们将按照以下步骤用 C 语言实现 HRRN 调度算法：

1. 定义作业结构体（包含到达时间、服务时间、完成时间等）
2. 输入作业信息
3. 按到达时间排序（模拟作业提交顺序）
4. 循环选择响应比最高的作业执行
5. 输出调度结果和统计信息

完整代码实现

以下是完整的 C 语言代码，包含了详细的注释：

#include <stdio.h>#include <stdlib.h>// 定义作业结构体typedef struct {    int id;          // 作业ID    int arrival;     // 到达时间    int service;     // 服务时间（CPU执行时间）    int start;       // 开始执行时间    int finish;      // 完成时间    int waiting;     // 等待时间    float ratio;     // 响应比    int executed;    // 是否已执行} Job;// 按到达时间排序（冒泡排序，简单易懂）void sortJobsByArrival(Job jobs[], int n) {    for (int i = 0; i < n - 1; i++) {        for (int j = 0; j < n - i - 1; j++) {            if (jobs[j].arrival > jobs[j + 1].arrival) {                Job temp = jobs[j];                jobs[j] = jobs[j + 1];                jobs[j + 1] = temp;            }        }    }}// 计算当前所有未执行作业的响应比void calculateRatios(Job jobs[], int n, int currentTime) {    for (int i = 0; i < n; i++) {        if (!jobs[i].executed) {            jobs[i].waiting = currentTime - jobs[i].arrival;            // 防止除零错误            if (jobs[i].service > 0) {                jobs[i].ratio = (float)(jobs[i].waiting + jobs[i].service) / jobs[i].service;            } else {                jobs[i].ratio = 0;            }        }    }}// 找到响应比最高的未执行作业int findHighestRatioJob(Job jobs[], int n) {    int index = -1;    float maxRatio = -1;    for (int i = 0; i < n; i++) {        if (!jobs[i].executed && jobs[i].ratio > maxRatio) {            maxRatio = jobs[i].ratio;            index = i;        }    }    return index;}int main() {    int n;    printf("请输入作业数量: ");    scanf("%d", &n);    Job* jobs = (Job*)malloc(n * sizeof(Job));    // 输入每个作业的信息    for (int i = 0; i < n; i++) {        jobs[i].id = i + 1;        printf("请输入作业 %d 的到达时间和服务时间: ", i + 1);        scanf("%d %d", &jobs[i].arrival, &jobs[i].service);        jobs[i].executed = 0;    }    // 按到达时间排序    sortJobsByArrival(jobs, n);    int currentTime = jobs[0].arrival; // 从第一个作业到达时间开始    printf("\n调度过程:\n");    for (int executedCount = 0; executedCount < n; executedCount++) {        // 计算当前所有未执行作业的响应比        calculateRatios(jobs, n, currentTime);        // 找到响应比最高的作业        int nextJobIndex = findHighestRatioJob(jobs, n);        if (nextJobIndex == -1) break;        // 设置开始时间（如果作业还没到达，需等待）        if (currentTime < jobs[nextJobIndex].arrival) {            currentTime = jobs[nextJobIndex].arrival;        }        jobs[nextJobIndex].start = currentTime;        jobs[nextJobIndex].finish = currentTime + jobs[nextJobIndex].service;        jobs[nextJobIndex].waiting = jobs[nextJobIndex].start - jobs[nextJobIndex].arrival;        jobs[nextJobIndex].executed = 1;        printf("执行作业 %d: 到达=%d, 服务=%d, 开始=%d, 完成=%d, 等待=%d\n",               jobs[nextJobIndex].id,               jobs[nextJobIndex].arrival,               jobs[nextJobIndex].service,               jobs[nextJobIndex].start,               jobs[nextJobIndex].finish,               jobs[nextJobIndex].waiting);        // 更新当前时间        currentTime = jobs[nextJobIndex].finish;    }    // 计算平均等待时间    float totalWaiting = 0;    for (int i = 0; i < n; i++) {        totalWaiting += jobs[i].waiting;    }    printf("\n平均等待时间: %.2f\n", totalWaiting / n);    free(jobs);    return 0;}

代码说明

这段代码实现了完整的 操作系统调度策略中的 HRRN 算法：

• Job 结构体存储每个作业的关键信息
• sortJobsByArrival 确保作业按提交顺序处理
• calculateRatios 动态计算每个作业的响应比
• findHighestRatioJob 选择最优作业执行

程序会输出每个作业的执行细节，并计算平均等待时间，帮助你理解调度效果。

运行示例

假设输入以下作业：

作业数量: 3作业1: 到达=0, 服务=5作业2: 到达=1, 服务=3作业3: 到达=2, 服务=8

程序将优先执行作业2（响应比高），再执行作业1，最后执行作业3，有效平衡了短作业和长作业的需求。

总结

通过本教程，你已经掌握了如何用 C 语言实现最高响应比调度算法。这种 C语言最高响应比算法 是学习 操作系统调度策略 的重要一环，不仅能加深对调度机制的理解，还能提升你的 C 语言编程能力。快动手试试吧！