最高响应比调度算法详解（Python实现操作系统作业调度）

什么是响应比？

响应比（Response Ratio）的计算公式如下：

响应比 = (等待时间 + 服务时间) / 服务时间

其中：

• 等待时间：作业从提交到当前时刻所等待的时间；
• 服务时间：作业所需的 CPU 执行时间（也称运行时间）。

可以看出，随着等待时间增加，响应比也会增大，因此长时间等待的作业最终会获得较高的优先级，从而被调度执行。

为什么使用最高响应比算法？

相比其他调度算法：

• 先来先服务（FCFS）：可能导致短作业等待过久；
• 短作业优先（SJF）：可能导致长作业“饥饿”；
• 最高响应比（HRRN）：动态调整优先级，兼顾公平与效率。

因此，响应比优先调度是一种更智能、更平衡的调度策略。

用 Python 实现最高响应比算法

下面我们用 Python 编写一个简单的 HRRN 调度模拟程序。假设我们有一组作业，每个作业包含：作业ID、到达时间 和 服务时间。

class Job:    def __init__(self, job_id, arrival_time, service_time):        self.job_id = job_id        self.arrival_time = arrival_time        self.service_time = service_time        self.waiting_time = 0        self.turnaround_time = 0        self.completed = Falsedef hrrn_scheduling(jobs):    current_time = 0    completed_jobs = 0    n = len(jobs)    execution_order = []    while completed_jobs < n:        # 筛选出已到达但未完成的作业        available_jobs = [            job for job in jobs             if job.arrival_time <= current_time and not job.completed        ]        if not available_jobs:            # 若无可用作业，时间推进到下一个作业到达            current_time += 1            continue        # 计算每个可用作业的响应比        for job in available_jobs:            job.waiting_time = current_time - job.arrival_time            job.response_ratio = (job.waiting_time + job.service_time) / job.service_time        # 选择响应比最高的作业        next_job = max(available_jobs, key=lambda j: j.response_ratio)                # 执行该作业        current_time += next_job.service_time        next_job.turnaround_time = current_time - next_job.arrival_time        next_job.completed = True        execution_order.append(next_job.job_id)        completed_jobs += 1    return execution_order# 示例：创建作业列表jobs = [    Job("A", 0, 3),    Job("B", 2, 6),    Job("C", 4, 4),    Job("D", 6, 5)]# 执行调度order = hrrn_scheduling(jobs)print("作业执行顺序:", order)# 输出每个作业的周转时间和等待时间for job in jobs:    print(f"作业 {job.job_id}: 等待时间={job.waiting_time}, 周转时间={job.turnaround_time}")

代码说明

上述代码实现了完整的 Python调度算法逻辑：

1. 定义 Job 类存储作业信息；
2. 在 hrrn_scheduling 函数中，循环直到所有作业完成；
3. 每次只考虑“已到达且未完成”的作业；
4. 动态计算每个作业的响应比，并选择最大者执行；
5. 更新时间、等待时间、周转时间等指标。

总结

最高响应比算法是一种优秀的非抢占式调度策略，特别适用于批处理系统。通过本教程，你已经掌握了其原理、优势以及如何用 Python 实现它。

无论是学习 操作系统作业调度，还是准备面试或课程设计，理解并实现 HRRN 算法都是非常有价值的技能。

希望这篇教程能帮助你轻松入门！