Python实现CPU调度算法详解（从零开始掌握操作系统进程调度）

什么是CPU调度？

当多个进程同时等待CPU执行时，操作系统必须决定谁先运行、谁后运行。这个决策过程就叫CPU调度。合理的调度能提高系统效率、减少等待时间。

1. 先来先服务调度算法（FCFS）

这是最简单的调度算法：按照进程到达的顺序依次执行。虽然公平，但可能导致“长作业阻塞短作业”的问题。

下面用Python实现一个简单的FCFS调度器：

def fcfs_scheduling(processes):    """    先来先服务调度算法    processes: 列表，每个元素为 (进程名, 到达时间, 执行时间)    """    # 按到达时间排序    processes.sort(key=lambda x: x[1])        current_time = 0    waiting_times = []    turnaround_times = []        print("进程执行顺序：")    for name, arrival, burst in processes:        if current_time < arrival:            current_time = arrival                waiting_time = current_time - arrival        turnaround_time = waiting_time + burst                waiting_times.append(waiting_time)        turnaround_times.append(turnaround_time)                print(f"{name}: 等待时间={waiting_time}, 周转时间={turnaround_time}")        current_time += burst        avg_wait = sum(waiting_times) / len(waiting_times)    avg_turn = sum(turnaround_times) / len(turnaround_times)        print(f"\n平均等待时间: {avg_wait:.2f}")    print(f"平均周转时间: {avg_turn:.2f}")# 示例数据：(进程名, 到达时间, 执行时间)processes = [('P1', 0, 5), ('P2', 1, 3), ('P3', 2, 8), ('P4', 3, 6)]fcfs_scheduling(processes)

2. 最短作业优先调度（SJF）

该算法总是选择剩余执行时间最短的进程优先执行，能有效减少平均等待时间。我们这里实现非抢占式版本（一旦开始执行就不会被中断）。

import heapqdef sjf_scheduling(processes):    """    非抢占式最短作业优先调度    processes: [(name, arrival, burst)]    """    processes.sort(key=lambda x: x[1])  # 按到达时间排序    ready_queue = []  # 小顶堆，存储 (burst_time, arrival, name)    current_time = 0    completed = 0    n = len(processes)    i = 0        waiting_times = {}    turnaround_times = {}        while completed < n:        # 将当前时间已到达的进程加入就绪队列        while i < n and processes[i][1] <= current_time:            name, arrival, burst = processes[i]            heapq.heappush(ready_queue, (burst, arrival, name))            i += 1                if ready_queue:            burst, arrival, name = heapq.heappop(ready_queue)            waiting_time = current_time - arrival            turnaround_time = waiting_time + burst                        waiting_times[name] = waiting_time            turnaround_times[name] = turnaround_time                        print(f"{name}: 等待时间={waiting_time}, 周转时间={turnaround_time}")                        current_time += burst            completed += 1        else:            # 如果没有就绪进程，跳到下一个进程到达时间            if i < n:                current_time = processes[i][1]        avg_wait = sum(waiting_times.values()) / n    avg_turn = sum(turnaround_times.values()) / n        print(f"\n平均等待时间: {avg_wait:.2f}")    print(f"平均周转时间: {avg_turn:.2f}")# 示例processes = [('P1', 0, 6), ('P2', 1, 8), ('P3', 2, 7), ('P4', 3, 3)]sjf_scheduling(processes)

为什么学习Python CPU调度算法很重要？

掌握操作系统进程调度原理，不仅有助于你理解计算机底层工作机制，还能在面试中脱颖而出。使用Python模拟调度算法，可以直观看到不同策略对系统性能的影响，是理论与实践结合的绝佳方式。

小结

本文介绍了两种基础的Python CPU调度算法：FCFS 和 SJF，并提供了完整的可运行代码。你可以在此基础上扩展实现优先级调度、时间片轮转（RR）等更复杂的算法。记住，动手实践是掌握知识的最佳途径！

希望这篇教程能帮助你入门先来先服务调度及其他CPU调度策略。如果你有任何问题，欢迎在评论区留言交流！