简介这份课程设计文档面向计算机专业操作系统课程的学习者聚焦CPU调度算法的模拟实现帮助读者通过编程实践掌握进程调度的核心机理。内容围绕先到先服务FCFS、非抢占最短作业优先SJF、可抢占优先权调度PRIOR和时间片轮转RR四种经典算法展开涵盖设计目的、设计要求、设计说明与结论等完整章节并给出优先权调度、FCFS与SJF综合的代码实现思路涉及结构体定义进程信息、冒泡排序按优先级排序、链表实现作业队列以及周转时间与平均周转时间的计算与评价。资源包为1个doc文档大小约93KB结构紧凑适合直接用于课程设计报告撰写与算法调试参考。目前已有316人学习可作为操作系统实验与调度算法对比分析的实用资料。1. 从一份 CPU 调度算法模拟实现课程设计说起它到底在解决什么问题如果你正在做操作系统课程设计选题是 CPU 调度算法的模拟实现那你大概率会遇到一个很尴尬的局面课本上 FCFS、SJF、时间片轮转、优先级调度、多级反馈队列这些名字背得滚瓜烂熟公式也能默写但真让你写一个能跑、能出数据、能画对比图的程序脑子里第一反应是「从哪下手」。这不是你一个人的问题我带过几届课设十个人里有八个卡在同一个地方——不是不会算法而是不知道模拟器该模拟什么、数据从哪来、指标怎么算才算数。这份课程设计要干的事其实很明确用一段程序把进程调度的过程「演」出来让每个进程的到达时间、服务时间、等待时间、周转时间、带权周转时间都能被算出来最后用平均周转时间、平均带权周转时间、CPU 利用率这些指标去比较不同调度策略的优劣。它适合两类人一类是刚学完操作系统进程管理章节、需要交课设的学生另一类是想快速验证某个调度策略在特定负载下表现如何的开发者。核心难点不在算法本身而在时间轴推进、就绪队列维护、指标统计这三件事的工程化处理。下面我按自己实际做过的路径把选型、实现、参数和坑一次讲清楚。2. 模拟器怎么搭进程模型、时间轴与指标口径2.1 先定进程控制块和输入格式别急着写调度很多人一上来就写while循环调度结果发现进程的到达时间没法处理因为进程还没「出生」就被塞进就绪队列了。正确顺序是先定义进程控制块PCB再定义输入数据格式最后才是调度逻辑。PCB 至少要有这些字段进程 ID、到达时间、服务时间CPU burst、剩余服务时间、开始执行时间、完成时间、等待时间、周转时间、带权周转时间、优先级如果做优先级调度、队列级别如果做多级反馈队列。输入我一般用 CSV 或直接硬编码一个数组格式是pid,arrival_time,burst_time,priority。下面是一个最小可用的 Python 数据结构定义# pcb.py from dataclasses import dataclass, field dataclass class PCB: pid: str arrival: int # 到达时间 burst: int # 服务时间CPU 总需求 priority: int 0 # 优先级数值越小优先级越高 remaining: int 0 # 剩余服务时间初始等于 burst start: int -1 # 首次开始执行时间 finish: int -1 # 完成时间 wait: int 0 # 等待时间 turnaround: int 0 # 周转时间 weighted_turnaround: float 0.0 # 带权周转时间 queue_level: int 0 # 多级反馈队列用 def __post_init__(self): self.remaining self.burst这段代码的关键点是remaining字段时间片轮转和抢占式调度都靠它判断进程是否还需要 CPU。start初始为 -1 是为了区分「还没跑过」和「在 0 时刻开始跑」。参数上到达时间和服务时间建议用整数单位统一为「时间片」避免浮点误差导致比较时出现 0.30000000000000004 这种玄学问题。2.2 时间轴推进的两种写法事件驱动 vs 逐时间片模拟器的时间轴推进方式直接决定代码复杂度和结果精度。常见做法有两种第一种是逐时间片推进。设定一个全局时钟current_time每次加 1检查有没有新进程到达把到达的进程加入就绪队列然后根据调度策略选一个进程执行一个时间片。这种写法直观适合时间片轮转和抢占式优先级缺点是如果服务时间很大比如 10000循环次数会很多但课设规模通常几十个进程、服务时间几十到几百完全够用。第二种是事件驱动。只在「进程到达」和「进程完成」两个事件点推进时间中间跳过空闲。这种写法效率高但实现复杂容易在抢占式调度上翻车。我一般建议课设用逐时间片推进因为可读性强调试时打印每个时间片的状态一目了然。下面是一个逐时间片推进的骨架# simulator.py def run_simulation(processes, scheduler, total_time1000): time 0 ready_queue [] finished [] processes sorted(processes, keylambda p: p.arrival) idx 0 # 指向下一个未到达的进程 while len(finished) len(processes) and time total_time: # 1. 把当前时刻到达的进程加入就绪队列 while idx len(processes) and processes[idx].arrival time: ready_queue.append(processes[idx]) idx 1 # 2. 调用调度器选择下一个执行的进程 current scheduler.pick(ready_queue, time) if current is None: time 1 continue # 3. 执行一个时间片 if current.start -1: current.start time current.remaining - 1 time 1 # 4. 如果进程完成计算指标 if current.remaining 0: current.finish time current.turnaround current.finish - current.arrival current.wait current.turnaround - current.burst current.weighted_turnaround current.turnaround / current.burst finished.append(current) ready_queue.remove(current) return finished逻辑说明idx指针保证每个进程只入队一次scheduler.pick是策略接口不同算法实现不同的 pick执行一个时间片后立刻判断是否完成完成就结算指标。参数total_time是安全上限防止死循环一般设为所有进程到达时间加服务时间之和的两倍。2.3 五个核心指标的计算口径别算错了还沾沾自喜指标算错是课设里最隐蔽的坑因为结果看起来「像那么回事」但和同学一对就发现对不上。统一口径如下指标公式注意点等待时间周转时间 - 服务时间不是「开始时间 - 到达时间」抢占式下会偏小周转时间完成时间 - 到达时间包含等待和实际执行带权周转时间周转时间 / 服务时间服务时间不能为 0平均周转时间所有进程周转时间之和 / 进程数保留两位小数CPU 利用率总服务时间 / 总模拟时间总模拟时间取最后一个进程完成时刻提示等待时间用「周转 - 服务」而不是「开始 - 到达」是因为抢占式调度下进程可能被中断多次开始时间只记录了第一次用开始时间算会漏掉后续等待。CPU 利用率的分母是「从 0 到最后一个进程完成的时长」不是total_time。我见过有人用total_time当分母结果利用率只有 0.3还以为是调度策略的问题其实是口径错了。3. 四种调度算法的实现从 FCFS 到多级反馈队列3.1 FCFS 和 SJF就绪队列排序的两种思路FCFS 最简单就绪队列按到达时间排序先到先服务。实现上pick直接返回队首即可。但要注意如果当前没有进程到达CPU 空闲时间要继续推进不能卡住。# schedulers.py class FCFS: def pick(self, ready_queue, time): if not ready_queue: return None # 按到达时间排序先到先服务 ready_queue.sort(keylambda p: p.arrival) return ready_queue[0]SJF 分两种非抢占式 SJF 和抢占式 SJF也叫 SRTF最短剩余时间优先。非抢占式是「一旦开始就跑完」所以pick只在 CPU 空闲时选剩余服务时间最短的抢占式是每个时间片都选剩余时间最短的可能把正在跑的进程换下来。class SJF_NonPreemptive: def __init__(self): self.running None def pick(self, ready_queue, time): if self.running and self.running.remaining 0: return self.running if not ready_queue: return None # 选服务时间最短的 chosen min(ready_queue, keylambda p: p.burst) self.running chosen return chosen class SRTF: def pick(self, ready_queue, time): if not ready_queue: return None # 每个时间片都选剩余时间最短的 return min(ready_queue, keylambda p: p.remaining)参数说明SJF 的「短」指的是服务时间不是剩余时间SRTF 的「短」指的是剩余时间。这两个别搞混否则平均周转时间会差很多。我实测过一组数据非抢占 SJF 平均周转时间 12.4SRTF 是 10.8差距来自短作业能插队。3.2 时间片轮转时间片大小怎么选才不翻车时间片轮转RR的核心参数是时间片大小q。q太大退化成 FCFSq太小上下文切换开销大虽然模拟器里没有真实切换开销但周转时间会变长。课设里一般取q 1或q 2如果服务时间普遍在 10 以内q 1比较合适。实现上需要一个就绪队列每次执行完一个时间片后如果进程没完成把它移到队尾。class RoundRobin: def __init__(self, quantum1): self.quantum quantum self.counter 0 # 当前进程已执行的时间片数 def pick(self, ready_queue, time): if not ready_queue: return None # 如果当前进程用完时间片移到队尾 if self.counter self.quantum: ready_queue.append(ready_queue.pop(0)) self.counter 0 self.counter 1 return ready_queue[0]这里有个细节counter在进程完成时要重置否则下一个进程会继承上一个进程的计数。我当初就在这里翻过车RR 的结果和同学对不上查了两小时才发现是计数器没清零。3.3 优先级调度与多级反馈队列抢占判断和队列升降级优先级调度分抢占和非抢占。非抢占是「跑完再换」抢占是「更高优先级的进程一到就换」。实现抢占式优先级时pick要比较当前运行进程和就绪队列中最高优先级进程的优先级。class PriorityPreemptive: def pick(self, ready_queue, time): if not ready_queue: return None # 数值越小优先级越高 return min(ready_queue, keylambda p: p.priority)多级反馈队列MLFQ是课设里最复杂的但也是最能体现水平的。常见规则设置 3 个队列队列 1 时间片 1队列 2 时间片 2队列 3 时间片 4新进程进队列 1用完时间片没完成就降级队列 3 内按 RR 调度只有高优先级队列空了才调度低优先级队列。class MLFQ: def __init__(self): self.queues [[], [], []] # 三个队列 self.quantums [1, 2, 4] self.current_level 0 self.counter 0 def pick(self, ready_queue, time): # 把新到达的进程加入队列 0这里简化处理实际应在主循环做 for p in ready_queue: if p.queue_level 0 and p not in self.queues[0]: self.queues[0].append(p) # 从高优先级队列开始找 for level in range(3): if self.queues[level]: if self.counter self.quantums[level]: # 时间片用完降级 p self.queues[level].pop(0) if p.remaining 0 and level 2: p.queue_level level 1 self.queues[level 1].append(p) self.counter 0 self.counter 1 return self.queues[level][0] return None参数说明队列数、各队列时间片、降级规则都是可调的。我一般用 3 队列、时间片 1/2/4降级条件是「用完时间片仍未完成」。注意队列 3 不再降级否则进程永远出不去。4. 避坑与排查课设里最容易翻车的五个地方4.1 进程到达时间处理错误导致就绪队列为空却还在跑现象模拟结果里某个进程的等待时间是负数或者完成时间早于到达时间。原因主循环里先执行了进程再检查到达或者idx指针没有正确推进。解决把「加入到达进程」放在每个时间片的最前面并且用while而不是if因为可能同一时刻有多个进程到达。4.2 时间片轮转的计数器没重置结果整体偏移现象RR 的平均周转时间和同学差 2 到 3 个时间单位但算法逻辑看起来没错。原因counter是实例变量进程完成后没有清零下一个进程继承了上一个进程的计数。解决在进程完成时把counter置 0或者把counter绑定到进程对象而不是调度器。4.3 带权周转时间除零程序直接崩溃现象某个进程服务时间为 0计算带权周转时间时抛出ZeroDivisionError。原因输入数据里出现了服务时间为 0 的进程可能是手误或者生成数据时没过滤。解决在计算前判断burst 0如果为 0 则跳过该进程或设带权周转时间为 0。4.4 多级反馈队列的进程在队列间无限循环现象模拟一直不结束finished列表始终不满。原因降级逻辑写成了「只要没完成就降级」但队列 3 又降回队列 1形成死循环。解决队列 3 不再降级或者设置最大降级次数。另外检查remaining是否在每次执行后正确递减。4.5 指标统计用了浮点数比较排序结果不稳定现象两个进程的周转时间理论相同但排序后顺序随机导致每次运行结果略有差异。原因带权周转时间用了浮点数0.1 0.2 ! 0.3这类问题导致比较时出现意外。解决指标计算保留两位小数用round(x, 2)排序时用keylambda x: round(x, 2)或者干脆用整数运算最后再除。5. 让课设加分用 matplotlib 画对比图和一个可复现的实验设计课设只交代码和结果表分数通常中等如果能画出不同调度策略在相同负载下的指标对比图并且说明实验设计分数会明显不一样。我一般用 matplotlib 画两张图一张是平均周转时间对比柱状图一张是各进程周转时间的折线图。# plot.py import matplotlib.pyplot as plt def plot_comparison(results): # results: {FCFS: [12.4, 3.2], SJF: [10.8, 2.9], ...} names list(results.keys()) avg_turnaround [results[n][0] for n in names] avg_weighted [results[n][1] for n in names] x range(len(names)) fig, ax1 plt.subplots(figsize(8, 5)) ax1.bar([i - 0.2 for i in x], avg_turnaround, width0.4, label平均周转时间) ax1.bar([i 0.2 for i in x], avg_weighted, width0.4, label平均带权周转时间) ax1.set_xticks(list(x)) ax1.set_xticklabels(names) ax1.set_ylabel(时间) ax1.legend() plt.title(不同调度算法性能对比) plt.tight_layout() plt.savefig(comparison.png, dpi150) plt.show()实验设计上我建议固定一组进程数据比如 8 个进程到达时间 0 到 10 随机服务时间 1 到 8 随机然后让所有算法跑同一组数据。这样对比才有意义。如果每个算法用不同数据那比较的是数据差异不是算法差异。另外时间片轮转的q可以取 1、2、4 三组观察q对周转时间的影响这能体现你对参数的理解。注意matplotlib 默认字体不支持中文需要在代码开头加plt.rcParams[font.sans-serif] [SimHei]和plt.rcParams[axes.unicode_minus] False否则中文会显示成方块。最后说一个我自己的习惯每次改完调度逻辑先用 3 个进程的小数据手动算一遍预期结果再跑程序对。如果对不上打印每个时间片的就绪队列和当前进程逐帧排查。这个笨办法帮我省下了大量「看起来对但结果错」的调试时间。希望帮到你。本文还有配套的精品资源点击获取