最短作业优先算法详解（Python实现操作系统作业调度）

SJF 算法的核心逻辑

假设我们有一组作业，每个作业包含两个信息：

• arrival_time：作业到达系统的时间
• burst_time：作业需要的 CPU 执行时间（即运行时间）

SJF 的执行步骤如下：

1. 按到达时间排序所有作业。
2. 选择第一个到达的作业作为当前时间起点。
3. 在当前时间点，找出所有已到达但未执行的作业中 burst_time 最短的那个。
4. 执行该作业，并更新当前时间 = 当前时间 + 该作业的 burst_time。
5. 重复步骤 3-4，直到所有作业执行完毕。

Python 实现 SJF 算法

下面是一个完整的 Python 代码示例，实现了非抢占式 SJF 算法，并计算了每个作业的等待时间和周转时间。

def sjf_scheduling(processes):    """    非抢占式最短作业优先调度算法    processes: 列表，每个元素为字典 {'name': str, 'arrival': int, 'burst': int}    """    # 按到达时间排序    processes = sorted(processes, key=lambda x: x['arrival'])        n = len(processes)    completed = [False] * n    current_time = 0    total_waiting_time = 0    total_turnaround_time = 0        print("执行顺序：")        for _ in range(n):        # 找出已到达且未完成的作业中 burst_time 最短的        available = []        for i in range(n):            if not completed[i] and processes[i]['arrival'] <= current_time:                available.append((processes[i]['burst'], i))                if not available:            # 如果没有可用作业，跳到下一个作业的到达时间            next_arrival = min(p['arrival'] for i, p in enumerate(processes) if not completed[i])            current_time = next_arrival            # 再次查找可用作业            for i in range(n):                if not completed[i] and processes[i]['arrival'] <= current_time:                    available.append((processes[i]['burst'], i))                # 选择 burst_time 最短的作业        available.sort()        _, idx = available[0]                # 执行该作业        p = processes[idx]        waiting_time = current_time - p['arrival']        turnaround_time = waiting_time + p['burst']                total_waiting_time += waiting_time        total_turnaround_time += turnaround_time                print(f"  {p['name']} (到达时间: {p['arrival']}, 运行时间: {p['burst']})")                current_time += p['burst']        completed[idx] = True        avg_waiting = total_waiting_time / n    avg_turnaround = total_turnaround_time / n        print(f"\n平均等待时间: {avg_waiting:.2f}")    print(f"平均周转时间: {avg_turnaround:.2f}")# 测试示例if __name__ == "__main__":    jobs = [        {'name': 'P1', 'arrival': 0, 'burst': 6},        {'name': 'P2', 'arrival': 1, 'burst': 8},        {'name': 'P3', 'arrival': 2, 'burst': 7},        {'name': 'P4', 'arrival': 3, 'burst': 3}    ]        sjf_scheduling(jobs)

代码说明

这段代码做了以下几件事：

• 首先按 arrival（到达时间）对作业排序。
• 使用 completed 列表记录哪些作业已完成。
• 在每一步中，筛选出“已到达且未完成”的作业，并从中选择 burst 最小的。
• 如果当前没有可执行作业（比如系统空闲），就跳到下一个最早到达的作业时间。
• 最后输出执行顺序、平均等待时间和平均周转时间。

运行结果示例

运行上述代码，你将看到类似以下输出：

执行顺序：  P1 (到达时间: 0, 运行时间: 6)  P4 (到达时间: 3, 运行时间: 3)  P3 (到达时间: 2, 运行时间: 7)  P2 (到达时间: 1, 运行时间: 8)平均等待时间: 4.75平均周转时间: 11.75

总结

通过本教程，你已经掌握了如何用 Python 实现最短作业优先算法。SJF 是一种高效的操作系统作业调度策略，能显著降低系统的平均等待时间。虽然它在实际系统中难以预测作业的精确运行时间，但在理论学习和模拟环境中非常有价值。

希望这篇教程对你理解 Python调度算法有所帮助！你可以尝试修改作业列表，观察不同输入下的调度结果，加深理解。

关键词回顾：最短作业优先算法、Python调度算法、操作系统作业调度、Python实现SJF。