操作系统课程的进程调度模拟几乎是每个计算机专业学生逃不掉的一关。这个题目的标题里列了五个算法其中 MRLA 我理解应该是 MLFQ多级反馈队列的笔误后面的括号也印证了这点。写这个模拟器的时候我踩了不少坑也把课本上看似理所当然的细节抠明白了许多整理出来给同样在赶作业、准备考试或者复习调度算法的朋友参考。先说说这项目的直接用途构建一组进程到达时间 服务时间用五种调度算法分别跑一遍计算出每个进程的完成时间、周转时间、带权周转时间再对比平均指标。听起来很简单等真正动手写你会发现 FCFS 和 SJF 之间差的不仅仅是一个排序函数而是一整套调度逻辑的转换。这篇内容会从整体框架设计讲到五种算法的核心实现再放一组实测数据做对比最后聊聊调试过程中印象最深的几个坑。1. 五种调度算法的定位与整体设计思路1.1 这几种算法到底在解决什么问题进程调度的本质就是解决下一个该让谁上 CPU的问题。这五种算法代表了三种不同的决策思路先来先服务FCFS按到达顺序排队非抢占机制最简单。短作业优先SJF从已到达进程中挑服务时间最短的非抢占。高响应比优先HRRN给每个等待的进程计算一个响应比综合等待时间与服务时间属于非抢占里的折中派。时间片轮转RR强制每个进程最多跑一个时间片轮到队尾抢占式。多级反馈队列MLFQ用多个优先级队列每级时间片不同进程用完本级时间片就降级兼顾交互性与吞吐。写五个算法本身不难难的是让它们跑在同一份测试数据上输出的指标还可比。所以不能各写各的得先设计一个统一的进程模型再让五种算法共用这套结构。1.2 为什么建议先把统一框架搭起来我见过不少同学把这五个算法写成五个孤立函数每个函数里复制粘贴一套进程数组 排序 计算周转时间的代码。这样做不是不行但调试时很容易出现同样一组数据每个算法输出的完成时间顺序都不同还得手工核对的尴尬局面。更划算的做法是定义统一的 PCB 结构体五种算法都操作同一个 vectorPCB。调度算法只负责修改每个进程的 finishTime。计算周转时间、带权周转时间、平均值的函数完全复用。这样写完一个算法后面的算法只需要改选择下一个进程这几十行逻辑其他模板代码直接复用。整个工程从零到跑通最耗时的其实是第一版框架。2. 数据结构与核心框架先把地基铺好2.1 进程控制块的结构设计PCB 是整套模拟的中枢。刚开始我偷懒直接在结构体里放五个进程的数组结果每种算法都得单独处理代码非常冗余。换成提炼一个统一 PCB 之后瞬间清爽多了。struct PCB { int id; // 进程编号 double arriveTime; // 到达时间 double serveTime; // 需要占用的 CPU 总时间 double remainTime; // 剩余服务时间RR / MLFQ 会用到 double finishTime; // 完成时刻 double turnAroundTime; // 周转时间 finishTime - arriveTime double weightedTurnAroundTime; // 带权周转时间 周转 / 服务时间 PCB(int _id, double _arrive, double _serve) : id(_id), arriveTime(_arrive), serveTime(_serve), remainTime(_serve), finishTime(0), turnAroundTime(0), weightedTurnAroundTime(0) {} };到达时间和服务时间用 double 是考虑到后续扩展——万一测试数据里有小数时间片整数类型直接抓瞎。remainTime 初始等于 serveTimeFCFS、SJF、HRRN 这三类非抢占算法用不上它但 RR 和 MLFQ 必须靠它记录还剩多少没跑完。2.2 统一的输入输出与指标统计输入格式约定最简单的一种第一行是进程数 N之后 N 行每行两个数字分别是到达时间和服务时间。例如5 0 4 1 3 2 5 3 2 4 4调度函数跑完以后统一调用一个统计函数计算周转时间和平均指标。这里有个细节复制进程数组再调度还是直接在原数组上改我的建议是在原数组上改因为五种算法分多次运行每次开始前用原始数据重置 remainTime 和 finishTime 即可。封装一个 reset 函数更稳妥。由于不同算法的选择逻辑千差万别最好的方式是每种算法一个独立函数参数都是 vectorPCB processes内部修改每个进程的 finishTime。这样测试代码只需要依次调用五个函数、打印表格代码结构清晰到一眼能看懂。3. 五种算法的实现与关键细节解析3.1 FCFS排序之后别忘了时间轴上的空闲段FCFS 是最容易实现的算法但最容易犯的错恰恰藏在CPU 空闲里。如果当前时间还没到某个进程的到达时间需要先把当前时间跳到它的到达时间否则完成时间会算错。我见过很多人直接遍历排序后的数组从 currentTime0 开始累加服务时间遇到前几个进程到达时间大于 0 的数据就整段崩掉。void FCFS(vectorPCB processes) { sort(processes.begin(), processes.end(), [](const PCB a, const PCB b) { return a.arriveTime b.arriveTime; }); double currentTime 0; for (auto p : processes) { if (currentTime p.arriveTime) { currentTime p.arriveTime; // CPU 空闲跳到下一个到达时刻 } p.finishTime currentTime p.serveTime; p.turnAroundTime p.finishTime - p.arriveTime; p.weightedTurnAroundTime p.turnAroundTime / p.serveTime; currentTime p.finishTime; } }FCFS 不需要队列模拟因为它是非抢占的且顺序完全由到达时间决定。排序 遍历就是最简实现。这个算法的核心价值在于给其他四个算法当对照组——任何调度算法的优化效果最终都要在平均周转时间上优于 FCFS才算有意义。3.2 SJF短作业优先难点在已到达三个字SJF 对排序这件事的理解很容易出偏差。很多人第一反应是把所有进程按服务时间从小到大排序然后直接跑。但仔细一想就发现不对如果一个短作业在第 10 秒才到达而当前时间是第 2 秒你不可能让它在第 2 秒就开始执行。正确做法是每一轮都扫描所有未完成的进程从当前时间已经到达的进程中挑选服务时间最短的。如果当前没有进程到达就跳到下一个到达时刻避免死循环。void SJF(vectorPCB processes) { vectorbool done(processes.size(), false); double currentTime 0; int completed 0; while (completed processes.size()) { int selected -1; double minServe numeric_limitsdouble::max(); for (int i 0; i processes.size(); i) { if (!done[i] processes[i].arriveTime currentTime processes[i].serveTime minServe) { minServe processes[i].serveTime; selected i; } } if (selected -1) { // 当前没有进程可运行跳到下一个到达时间 double nextArrive numeric_limitsdouble::max(); for (int i 0; i processes.size(); i) { if (!done[i] processes[i].arriveTime nextArrive) { nextArrive processes[i].arriveTime; } } currentTime nextArrive; continue; } double finish processes[selected].finishTime; finish currentTime processes[selected].serveTime; processes[selected].turnAroundTime finish - processes[selected].arriveTime; processes[selected].weightedTurnAroundTime processes[selected].turnAroundTime / processes[selected].serveTime; currentTime finish; done[selected] true; completed; } }这段代码的骨架非常通用后面 HRRN 只需要把选最短服务时间改成选最大响应比其他逻辑完全复用。这也是我为什么强调先把框架写好的原因。SJF 有个著名的副作用饥饿。如果短作业源源不断到达长作业可能永远等不到 CPU。所以教材里通常会在讲完 SJF 后立刻引入 HRRN用响应比公式把长作业的等待痛苦量化避免饿死。3.3 HRRN把等待的代价换算成数字响应比HRRN 的选择标准是响应比最大计算公式为响应比 (等待时间 服务时间) / 服务时间 1 等待时间 / 服务时间服务时间短的进程分母小天然容易获得高响应比而等待时间长的进程分子增大响应比也会逐渐上升避免了长作业被饿死。这个公式把短作业优先和防饥饿两件事统一成了一个数值指标设计得非常巧妙。在代码层面只需从 SJF 的框架中改一行筛选逻辑double responseRatio(const PCB p, double currentTime) { return (currentTime - p.arriveTime p.serveTime) / p.serveTime; } // 选 responseRatio 最大而不是 serveTime 最小然后把 SJF 函数里的 minServe 判断改成当前响应比最大。由于响应比会随着 currentTime 增大而动态变化所以不能提前排序必须每轮重新扫描计算。这也是 HRRN 相比于 FCFS 最耗 CPU 的地方但在模拟器中完全不是问题。实践中很多同学会把响应比算错尤其是等待时间那一项总是忘记用 currentTime 减去 arriveTime而是直接拿 currentTime 当等待时间。只要记住等待时间指的是进程从到达那一刻起到当前时刻为止等了多久就不会犯错了。3.4 RR时间片轮转边界条件是全部细节RR 终于从选一个进程跑到底进入了抢占的世界。实现上用队列模拟就绪队列每个进程最多连续运行一个时间片。如果时间片结束还没做完就排到队尾如果提前做完立即让出 CPU。这里的核心边界条件有三个时间片结束时新到达的进程必须先入队还是当前进程先入队CPU 空闲时当前时间如何跳到下一个到达时刻进程在时间片内提前完成剩余时间要不要补给它我采用的策略是时间片结束时先处理所有到达时间小于等于当前时刻的新进程再把未完成进程排到队尾。这个顺序等同模拟时钟中断先检查新就绪进程再做调度。代码实现如下void RR(vectorPCB processes, double quantum) { sort(processes.begin(), processes.end(), [](const PCB a, const PCB b) { return a.arriveTime b.arriveTime; }); queuepairint, double readyQueue; // 进程索引 剩余服务时间 int idx 0, completed 0; double currentTime 0; while (completed processes.size()) { while (idx processes.size() processes[idx].arriveTime currentTime) { readyQueue.push({idx, processes[idx].remainTime}); idx; } if (readyQueue.empty()) { currentTime processes[idx].arriveTime; continue; } auto [pid, remain] readyQueue.front(); readyQueue.pop(); double runTime min(remain, quantum); currentTime runTime; processes[pid].remainTime - runTime; // 时间片到时先让新到达进程入队 while (idx processes.size() processes[idx].arriveTime currentTime) { readyQueue.push({idx, processes[idx].remainTime}); idx; } if (processes[pid].remainTime 0) { readyQueue.push({pid, processes[pid].remainTime}); } else { processes[pid].finishTime currentTime; processes[pid].turnAroundTime currentTime - processes[pid].arriveTime; processes[pid].weightedTurnAroundTime processes[pid].turnAroundTime / processes[pid].serveTime; completed; } } }时间片的大小对 RR 影响极其明显。时间片太小上下文切换开销被放大实际吞吐率严重受损时间片太大RR 会退化成 FCFS。这个值怎么选是操作系统教材里一个经典讨论点后面测试部分我会用数据说话。3.5 MLFQ多级反馈队列级别与时间片怎么设计MLFQ 是这五个算法里实现复杂度最高的一个但也是最有现实意义的一个——现代操作系统普遍采用的就是改进版的多级反馈队列调度。它的核心思想是用多个优先级队列每个队列时间片不同进程用完当前队列的时间片还没结束就降级。这样新到达的短进程能在高优先级队列快速完成长进程慢慢降到低优先级队列减少频繁抢占带来的切换开销。我实现的 MLFQ 配置为三级队列时间片分别为 1、2、4。新到达进程一律进入 Q0时间片用完未完成就依次降级最低级队列Q2时间片用完后不再降级而是排到队尾继续轮转。void MLFQ(vectorPCB processes, const vectordouble quantums) { int levels quantums.size(); vectordequeint queues(levels); sort(processes.begin(), processes.end(), [](const PCB a, const PCB b) { return a.arriveTime b.arriveTime; }); int idx 0, completed 0; double currentTime 0; while (completed processes.size()) { // 新到达进程优先进入最高优先级队列 while (idx processes.size() processes[idx].arriveTime currentTime) { queues[0].push_back(idx); idx; } int selected -1, level -1; for (int l 0; l levels; l) { if (!queues[l].empty()) { selected queues[l].front(); queues[l].pop_front(); level l; break; } } if (selected -1) { if (idx processes.size()) { currentTime processes[idx].arriveTime; } continue; } double quantum quantums[level]; double runTime min(quantum, processes[selected].remainTime); currentTime runTime; processes[selected].remainTime - runTime; // 时间片结束时先接收新到达进程 while (idx processes.size() processes[idx].arriveTime currentTime) { queues[0].push_back(idx); idx; } if (processes[selected].remainTime 0) { int newLevel (level 1 levels) ? level 1 : level; queues[newLevel].push_back(selected); } else { processes[selected].finishTime currentTime; processes[selected].turnAroundTime currentTime - processes[selected].arriveTime; processes[selected].weightedTurnAroundTime processes[selected].turnAroundTime / processes[selected].serveTime; completed; } } }MLFQ 有一个工程实践中极易被忽略的问题饥饿。长作业在最低级队列也可能长时间得不到调度。标准解法是为最低级队列设置定期提升机制比如每运行 N 个时间片就把所有低于 Q0 的进程提升回 Q0。这个机制我在课程设计里作为扩展项做了效果确实立竿见影只是会让代码复杂不少。如果只是应付基础实验先实现简单的降级模型就够。4. 测试用例设计与运行结果对比4.1 构造一组有代表性的进程序列测试数据不能随便拍脑袋定最好能覆盖各种边界情况有最早到达的、有短服务时间的、有长服务时间的、有到达间隔不均匀的。我选了这样一组进程到达时间服务时间A04B13C25D32E44A 是最早到达的长进程B 是中短进程C 是最长的D 是最短但稍晚到达E 是最后到达的中等进程。这个组合可以清晰看出哪个算法先服务谁的策略差异。4.2 五种算法的运行结果与指标对比我跑完全部实现后得到了下面这张结果表。这里的 RR 使用时间片 quantum4MLFQ 使用三级队列时间片 1、2、4。算法完成顺序平均周转时间平均带权周转时间FCFSA(4) → B(7) → C(12) → D(14) → E(18)9.002.80SJFA(4) → D(6) → B(9) → E(13) → C(18)8.002.12HRRNA(4) → B(7) → D(9) → C(14) → E(18)8.402.38RR(q4)A(4) → B(7) → D(13) → E(17) → C(18)9.802.89MLFQ(1,2,4)B(9) → D(12) → A(15) → C(17) → E(18)12.203.48一些值得留意的点SJF 在这组数据里拿到了最优的平均周转时间因为 D 先于 B 和 E 被调度短作业被优先安排。HRRN 介于 SJF 和 FCFS 之间和理论预期一致它在短作业优先和避免饥饿之间找平衡。RR(q4) 的平均周转时间比 FCFS 差这并不意外。RR 从设计上就不是为了平均周转时间而是为了响应时间。如果改小时间片比如 quantum2RR 的平均周转时间会进一步恶化因为进程被切得更碎、排队次数更多。MLFQ 在纯批处理场景下表现最差平均带权周转时间高达 3.48。原因也好理解每个新进程都从 Q0 开始短进程虽然能快速完成但像 A 这种长进程被反复降级每次抢占都被重新排到低优先级队列的队尾等待时间比较长。MLFQ 的优势还是在混合负载长进程 大量短交互进程的场景下用这批数据看不出来需要在实验报告中专门说明。如果你做完实验发现 RR 和 MLFQ 数据不好看千万别觉得是自己写错了。调度算法的评价维度不止平均周转时间一个响应时间、带权周转时间、吞吐率、CPU 利用率都可能互相矛盾。实验报告里把这些指标分开讨论才有点意思。5. 调试过程踩过的坑与扩展建议5.1 最容易翻车的三类问题第一类是精度问题。用 double 算完周转时间后直接做p.turnAroundTime / p.serveTime可能得到无限小数。打印的时候需要设置保留两位小数比如printf(%.2f, ...)或用fixed setprecision(2)。如果全程用整数运算遇到服务时间 3完成时间 4这样的数据带权周转时间 4/3 直接变整数 1指标全错。第二类是当前时间推进问题。SJF、HRRN、RR、MLFQ 这四种算法都要求 CPU 空闲时跳到下一个进程到达时刻。新手最容易在这里写死循环当前进程时间没到循环里又找不到可运行的进程currentTime 永远不变。解决办法就是每轮循环检测一次如果没有任何进程在就绪队列中就把 currentTime 更新为所有未到达进程的最早到达时间。第三类是同时刻事件顺序问题。进程到达时间完全相同或者时间片结束时刻正好有进程到达进队列的顺序会直接影响后续调度结果。我的统一策略是先处理到达再处理时间片用完的进程这样至少整个工程内部是自洽的。如果你调试时发现结果和手算对不上先检查是不是这个顺序与你的手算假设不一致。5.2 可以做的几个扩展方向如果你学有余力这几个方向能显著提升项目深度实现抢占式 SJF也叫 SRTN最短剩余时间优先新进程到达时如果它的服务时间小于当前进程的剩余时间就立即抢占 CPU。这个扩展需要把选择进程逻辑改为运行过程中动态切换对理解抢占概念非常有帮助。为 MLFQ 增加优先级提升机制每运行 N 个时间片把所有进程提升到最高优先级队列消除长作业饥饿问题。模拟上下文切换开销每次进程切换花费固定时间 overhead然后重新统计指标。这样你会发现时间片太小的 RR 会显得很蠢反而能加深对时间片设置的理解。加入 I/O 交互模拟进程需要释放 CPU 去执行一段 I/O。MLFQ 的威力在这种混合负载下才能真正体现出来算出来不至于像纯批处理数据那么难看。5.3 给正在写这份作业的朋友几点建议先写 FCFS因为它最简单可以顺便把整个框架跑通。然后写 SJF把动态选择的循环逻辑吃透HRRN 几乎就是改一行筛选条件。RR 单独写重点理解队列和边界处理。MLFQ 放最后因为它是前几种思想和数据结构的综合。调试时准备一组非常简单的数据比如 3 个进程、到达时间从 0 开始、服务时间分别是 2、3、4。手算一遍每种算法的完成顺序和时间再对比程序输出。手算如果和程序对不上多半是某个边界顺序和你脑补的不一样。确认你的假设和实现策略一致再去接着查循环和指针。最后分享一个我实际调试时的小技巧在 RR 和 MLFQ 的时间片切换处加一行调试输出打印出当前进程、运行了多久、剩余多少、当前就绪队列顺序。这个输出只要开着一眼就能定位到队列顺序错在哪。等所有算法都跑通后再把这行注释掉方便得很。整套代码调试完之后最大的感受是调度算法表面上是比较这几个谁先谁后的选择规则但真正决定代码复杂度的其实是那些通用机制——就绪队列的组织、时间片中断时刻的处理、CPU 空闲时的推进策略。这五种算法在课本上分别讲解时个个显得干净利落放到同一个模拟器里比对时才体会到调度器是一个整体每个设计细节都会牵一发而动全身。