企业官网建设流程全解析

操作系统课程的进程调度模拟，几乎是每个计算机专业学生逃不掉的一关。这个题目的标题里列了五个算法，其中 MRLA 我理解应该是 MLFQ（多级反馈队列）的笔误，后面的括号也印证了这点。写这个模拟器的时候我踩了不少坑，也把课本上看似理所当然的细节抠明白了许多，整理出来给同样在赶作业、准备考试或者复习调度算法的朋友参考。

先说说这项目的直接用途：构建一组进程（到达时间 + 服务时间），用五种调度算法分别跑一遍，计算出每个进程的完成时间、周转时间、带权周转时间，再对比平均指标。听起来很简单？等真正动手写，你会发现 FCFS 和 SJF 之间差的不仅仅是一个排序函数，而是一整套调度逻辑的转换。这篇内容会从整体框架设计讲到五种算法的核心实现，再放一组实测数据做对比，最后聊聊调试过程中印象最深的几个坑。

1. 五种调度算法的定位与整体设计思路

1.1 这几种算法到底在解决什么问题

进程调度的本质，就是解决"下一个该让谁上 CPU"的问题。这五种算法代表了三种不同的决策思路：

• 先来先服务（FCFS）：按到达顺序排队，非抢占，机制最简单。
• 短作业优先（SJF）：从已到达进程中挑服务时间最短的，非抢占。
• 高响应比优先（HRRN）：给每个等待的进程计算一个响应比，综合等待时间与服务时间，属于非抢占里的折中派。
• 时间片轮转（RR）：强制每个进程最多跑一个时间片，轮到队尾，抢占式。
• 多级反馈队列（MLFQ）：用多个优先级队列，每级时间片不同，进程用完本级时间片就降级，兼顾交互性与吞吐。

写五个算法本身不难，难的是让它们跑在同一份测试数据上，输出的指标还可比。所以不能各写各的，得先设计一个统一的进程模型，再让五种算法共用这套结构。

1.2 为什么建议先把统一框架搭起来

我见过不少同学把这五个算法写成五个孤立函数，每个函数里复制粘贴一套"进程数组 + 排序 + 计算周转时间"的代码。这样做不是不行，但调试时很容易出现"同样一组数据，每个算法输出的完成时间顺序都不同，还得手工核对"的尴尬局面。更划算的做法是：

• 定义统一的 PCB 结构体，五种算法都操作同一个 vector<PCB>。
• 调度算法只负责修改每个进程的 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 初始等于 serveTime，FCFS、SJF、HRRN 这三类非抢占算法用不上它，但 RR 和 MLFQ 必须靠它记录"还剩多少没跑完"。

2.2 统一的输入输出与指标统计

输入格式约定最简单的一种：第一行是进程数 N，之后 N 行每行两个数字，分别是到达时间和服务时间。例如：

5 0 4 1 3 2 5 3 2 4 4

调度函数跑完以后，统一调用一个统计函数计算周转时间和平均指标。这里有个细节：复制进程数组再调度，还是直接在原数组上改？我的建议是在原数组上改，因为五种算法分多次运行，每次开始前用原始数据重置 remainTime 和 finishTime 即可。封装一个 reset 函数更稳妥。

由于不同算法的"选择逻辑"千差万别，最好的方式是每种算法一个独立函数，参数都是 vector<PCB>& processes，内部修改每个进程的 finishTime。这样测试代码只需要依次调用五个函数、打印表格，代码结构清晰到一眼能看懂。

3. 五种算法的实现与关键细节解析

3.1 FCFS：排序之后别忘了时间轴上的空闲段

FCFS 是最容易实现的算法，但最容易犯的错恰恰藏在"CPU 空闲"里。如果当前时间还没到某个进程的到达时间，需要先把当前时间跳到它的到达时间，否则完成时间会算错。我见过很多人直接遍历排序后的数组，从 currentTime=0 开始累加服务时间，遇到前几个进程到达时间大于 0 的数据就整段崩掉。

void FCFS(vector<PCB>& 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(vector<PCB>& processes) { vector<bool> done(processes.size(), false); double currentTime = 0; int completed = 0; while (completed < processes.size()) { int selected = -1; double minServe = numeric_limits<double>::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_limits<double>::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。

这里的核心边界条件有三个：

1. 时间片结束时，新到达的进程必须先入队，还是当前进程先入队？
2. CPU 空闲时，当前时间如何跳到下一个到达时刻？
3. 进程在时间片内提前完成，剩余时间要不要补给它？

我采用的策略是：时间片结束时，先处理所有到达时间小于等于当前时刻的新进程，再把未完成进程排到队尾。这个顺序等同模拟"时钟中断先检查新就绪进程，再做调度"。代码实现如下：

void RR(vector<PCB>& processes, double quantum) { sort(processes.begin(), processes.end(), [](const PCB& a, const PCB& b) { return a.arriveTime < b.arriveTime; }); queue<pair<int, 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(vector<PCB>& processes, const vector<double>& quantums) { int levels = quantums.size(); vector<deque<int>> 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 构造一组有代表性的进程序列

测试数据不能随便拍脑袋定，最好能覆盖各种边界情况：有最早到达的、有短服务时间的、有长服务时间的、有到达间隔不均匀的。我选了这样一组：

A 是最早到达的长进程，B 是中短进程，C 是最长的，D 是最短但稍晚到达，E 是最后到达的中等进程。这个组合可以清晰看出"哪个算法先服务谁"的策略差异。

4.2 五种算法的运行结果与指标对比

我跑完全部实现后，得到了下面这张结果表。这里的 RR 使用时间片 quantum=4，MLFQ 使用三级队列（时间片 1、2、4）。

一些值得留意的点：

• SJF 在这组数据里拿到了最优的平均周转时间，因为 D 先于 B 和 E 被调度，短作业被优先安排。
• HRRN 介于 SJF 和 FCFS 之间，和理论预期一致，它在短作业优先和避免饥饿之间找平衡。
• RR(q=4) 的平均周转时间比 FCFS 差，这并不意外。RR 从设计上就不是为了平均周转时间，而是为了响应时间。如果改小时间片，比如 quantum=2，RR 的平均周转时间会进一步恶化，因为进程被切得更碎、排队次数更多。
• 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 空闲时的推进策略。这五种算法在课本上分别讲解时个个显得干净利落，放到同一个模拟器里比对时，才体会到调度器是一个整体，每个设计细节都会牵一发而动全身。