用Python模拟FCFS、SJF、RR调度算法：可视化进程周转时间与饥饿现象

用Python模拟FCFS、SJF、RR调度算法可视化进程周转时间与饥饿现象操作系统中的进程调度算法是计算机科学中的核心概念之一。对于初学者来说单纯的理论学习往往难以深入理解这些抽象算法的实际行为和影响。本文将带领读者通过Python代码实现三种经典调度算法——先来先服务(FCFS)、短作业优先(SJF)和时间片轮转(RR)并通过可视化手段直观展示它们的运行效果、计算关键性能指标以及揭示可能存在的问题如饥饿现象。1. 环境准备与基础概念在开始编码之前我们需要搭建基本的Python环境并理解几个关键术语。本项目主要依赖以下库import matplotlib.pyplot as plt import numpy as np from collections import deque import random周转时间是指从进程提交到完成所用的总时间计算公式为完成时间 - 到达时间。而等待时间则是进程在就绪队列中等待的总时间不包含实际执行时间。调度算法的核心目标是优化系统整体性能常用评估指标包括平均周转时间平均等待时间CPU利用率响应时间提示在交互式环境中开发时建议使用Jupyter Notebook可以实时查看可视化结果并调整参数。2. 先来先服务(FCFS)算法实现FCFS是最简单的调度算法按照进程到达的顺序依次执行。让我们首先定义一个进程类class Process: def __init__(self, pid, arrival_time, burst_time): self.pid pid # 进程ID self.arrival arrival_time # 到达时间 self.burst burst_time # 执行时间 self.remaining burst_time # 剩余执行时间 self.start_time -1 # 开始时间 self.finish_time -1 # 完成时间FCFS调度器的核心逻辑如下def fcfs_scheduler(processes): current_time 0 for p in sorted(processes, keylambda x: x.arrival): if current_time p.arrival: current_time p.arrival p.start_time current_time p.finish_time current_time p.burst current_time p.finish_time通过以下示例数据可以观察FCFS的特点进程ID到达时间执行时间P105P213P328可视化结果将清晰展示FCFS的先到先得特性但也可能造成短进程等待时间过长的问题。3. 短作业优先(SJF)算法实现SJF算法选择估计执行时间最短的进程优先执行理论上可以获得最小的平均等待时间。实现时需要区分抢占和非抢占两种模式。非抢占式SJF的实现def sjf_nonpreemptive(processes): current_time 0 ready_queue [] completed [] while len(completed) len(processes): # 将已到达的进程加入就绪队列 for p in processes: if p.arrival current_time and p not in ready_queue and p not in completed: ready_queue.append(p) if ready_queue: # 选择执行时间最短的进程 ready_queue.sort(keylambda x: x.burst) current ready_queue.pop(0) current.start_time current_time current.finish_time current_time current.burst current_time current.finish_time completed.append(current) else: current_time 1SJF算法虽然优化了平均等待时间但可能导致长进程饥饿——如果不断有短进程到达长进程可能长期得不到执行。我们可以通过以下代码模拟这种情况# 模拟饥饿场景 processes [ Process(1, 0, 10), # 长进程 Process(2, 1, 2), Process(3, 2, 2), Process(4, 3, 2), # 可以继续添加更多短进程... ]4. 时间片轮转(RR)算法实现RR算法为每个进程分配固定长度的时间片是分时系统的典型调度方式。其核心是维护一个就绪队列def rr_scheduler(processes, time_quantum): current_time 0 ready_queue deque() completed [] remaining_processes processes.copy() while remaining_processes or ready_queue: # 将到达的进程加入队列 for p in remaining_processes[:]: if p.arrival current_time: ready_queue.append(p) remaining_processes.remove(p) if ready_queue: current ready_queue.popleft() if current.start_time -1: current.start_time current_time # 执行一个时间片或剩余时间 exec_time min(time_quantum, current.remaining) current.remaining - exec_time current_time exec_time if current.remaining 0: current.finish_time current_time completed.append(current) else: ready_queue.append(current) else: current_time 1时间片大小的选择对系统性能有显著影响。我们可以比较不同时间片下的表现时间片大小平均周转时间平均等待时间115.610.2214.39.1413.88.6816.210.45. 可视化分析与比较使用matplotlib可以直观比较不同算法的表现。以下是一个绘制甘特图的函数示例def plot_gantt(processes, title): fig, ax plt.subplots(figsize(10, 5)) for i, p in enumerate(processes): ax.broken_barh([(p.start_time, p.burst)], (i*10, 9), facecolors(tab:blue)) ax.text(p.start_time p.burst/2, i*10 4.5, fP{p.pid}, hacenter, vacenter, colorwhite) ax.set_yticks([i*10 5 for i in range(len(processes))]) ax.set_yticklabels([fP{p.pid} for p in processes]) ax.set_xlabel(时间) ax.set_title(title) plt.show()通过综合比较三种算法的关键指标我们可以得出以下观察结果FCFS实现简单但可能导致护航效应短进程可能等待很长时间SJF优化了平均等待时间但可能导致长进程饥饿RR提供了公平性但时间片选择不当会增加上下文切换开销在实际项目中我经常遇到需要平衡响应时间和吞吐量的场景。例如在开发一个后台任务处理系统时我们最终采用了多级反馈队列结合了RR和优先级调度的优点。这种实践经验让我深刻理解到没有完美的调度算法只有最适合特定场景的选择。