代码写多了会有种错觉操作系统调度算法好像就是几张PPT里的时间轴图背熟公式就能应付考试。真自己动手用C把先来先服务FCFS、短作业优先SJF、高响应比优先HRRN、时间片轮转RR和多级反馈队列MLFQ逐个实现一遍之后才发现很多细节远比教材上的伪代码复杂。这篇文章是我在做模拟项目X时留下的完整实现记录从原理、数据结构、关键代码到实验对比和调试踩坑一起讲清楚正在做课程设计、准备操作系统考试或者单纯想搞懂调度器内部逻辑的读者都可以直接参考。整套代码的核心任务只有一个给定一组进程的到达时间和服务时间模拟调度过程输出每个进程的开始时间、完成时间并统计平均周转时间、平均带权周转时间。看起来简单但五个算法各自的“调度时机”完全不同要用一套框架把它们统一起来就需要认真设计数据结构和模拟主循环。我会把整个实现过程拆开讲代码片段可以直接抄进自己的工程里跑。1. 调度算法到底在解决什么问题1.1 剥开外壳看本质CPU调度就是排队策略的选择在单核CPU场景下任何时刻只有一个进程能占用处理器。当多个进程同时处于就绪状态时谁先上CPU、谁继续等待就是处理机调度要回答的问题。别看这个问题简单它直接影响用户体验和系统吞吐比如你同时打开浏览器、编译代码、后台播放音乐操作系统内核必须决定CPU时间怎么分。五类算法的本质差异在于它们依据什么信息来做决策。FCFS只看到达顺序SJF只看“服务时间最短”HRRN把等待时间和服务时间一起折算成响应比RR强制轮流占用不区分先后MLFQ则用多级队列把“短进程优先”和“轮转公平”组合起来。理解这个本质再去看代码里的条件判断和排序逻辑就会非常顺。我选择的实现方式是离散事件模拟不是真正的操作系统内核调度。原因很直接课程设计和对比实验需要的是“可复现的统计结果”而不是把进程真的放到线程里跑。离散事件模拟用一个时间变量不断向前推进遇到到达事件、完成事件就更新队列状态完全能反映调度算法的行为特征代码也更便于调试。1.2 为什么用C来做这件事很多资料里这五个算法用C、Python、Java都能写但我最终选了C主要看中三点结构体建模方便、容器库齐全、性能足够。PCB进程控制块用结构体描述队列用标准库的queue排序用sort加自定义比较器事件表用优先队列这套组合写出来逻辑非常紧凑。C的另一个好处是能直观展示“对象算法”的分离。我把调度器设计成基类每个算法继承并实现自己的决策函数这样测试时只需要切换一个指针就能对比不同算法的统计结果不需要把主流程复制五遍。对于需要频繁改参数做实验的场景这种设计能省下大量时间。如果你对STL不熟也没关系后面所有代码都用最基础的容器和语法几乎没有高级特性。唯一建议是先搞明白sort的第三个参数怎么传自定义比较器以及queue的front和pop组合用法这两个点理解透了代码读起来会很轻松。1.3 评价指标先讲清楚周转时间、带权周转时间代码输出什么、表格里比较什么都依赖指标定义。必须先统一口径再写代码否则统计结果会乱。周转时间 完成时间 - 到达时间。它代表一个进程从提交到完成总共耗费的等待时间与服务时间之和。带权周转时间 周转时间 / 服务时间。服务时间短的进程带权周转时间更能反映它“被耽误了多少倍自己的执行时长”所以操作系统教材把平均带权周转时间当作短作业友好的核心指标。指标公式关注点周转时间finish - arrive总处理耗时带权周转时间(finish - arrive) / need相对自身时长的等待成本平均周转时间所有进程周转时间求和 / n系统整体效率平均带权周转时间所有进程带权周转时间求和 / n对短作业的友好程度代码里我会按这个定义统一计算不同算法之间才能公平比较。注意带权周转时间最小值为1因为进程至少需要运行自己的服务时间才能完成如果计算出小于1的值一定是统计逻辑出了问题。2. 从原理到模型五个算法的决策逻辑2.1 FCFS和SJF一个看排队一个看长短FCFS是最符合直觉的算法谁先到达谁先执行。实现上只需要按到达时间排序然后依次推进完成时间。它的优点是没有饥饿缺点也很出名如果一个长进程先到后面所有短进程都要陪它等。这个现象叫护航效应代码里表现为后续进程的平均周转时间被显著拉高。SJF在“已经到达的进程”中选择服务时间最短的先运行。注意我要强调“已经到达”这是实现时最常见的失误点。如果直接用全局最短服务时间排序而不管进程是否已经到达模拟出来的结果是错误的。SJF理论上平均周转时间最优但长进程可能饿死因为只要不断有短进程到达长进程就永远轮不到。我在实现SJF时采用的策略是每次进程完成时扫描所有未完成进程筛出到达时间小于等于当前时间的那批在其中选择need最小的执行。两步走先过滤再选择逻辑清晰。顺手可以区分一下非抢占和抢占非抢占SJF在进程运行期间不会被打断抢占式SJFSRTF则允许新到达的短进程抢占当前进程。本篇文章主体按非抢占实现文末我会说说抢占式怎么扩展。2.2 HRRN给SJF加一个等待时间的权重HRRN是SJF的折中方案它不再是单纯比较服务时间而是把等待时间也纳入考量。响应比的计算公式大家都很熟响应比 (等待时间 服务时间) / 服务时间 等待时间 / 服务时间 1每次调度发生时对每个已到达且未完成的进程计算响应比选择值最高的运行。这个公式的妙处在于新到达的短进程响应比一般很高能享受短作业优先的好处如果短进程迟迟不来长进程的等待时间逐渐增长响应比会随之抬高最终也会获得执行机会从机制上避免了饿死。实现时等待时间的计算需要注意等待时间 当前调度时刻 - 进程到达时间。不能用进程开始时间减去到达时间因为一个进程可能被多次推迟调度当前调度时刻才是改判时机。2.3 RR和MLFQ时间片是它们的灵魂RR算法让每个进程最多运行一个固定时间片运行完还没结束就排到队尾换来的是所有进程轮流推进。时间片选多大是个核心实验参数太大RR退化成FCFS太小上下文切换开销会压过实际执行时间。MLFQ则把RR的思想做成多级结构。新进程进入最高优先级队列每个队列配一个时间片低优先级队列的时间片更长。进程如果在某个队列的时间片内没完成就降级到下一级队列最高优先级队列非空时低优先级队列不执行。这种设计兼顾了交互型短进程的响应速度又给长进程提供了兜底执行机会。标题里提到的MRLA我按国内教材最常见的叫法理解为多级反馈队列MLFQ后面代码也以MLFQ为准。实现时最麻烦的不是算法本身而是“每个队列内部用RR、队列之间用优先级抢占”这套嵌套逻辑主循环推进的时候要同时维护多个队列。3. 数据结构与模拟框架的搭建3.1 PCB结构体一个进程需要记录哪些字段写调度模拟第一个要建模的就是进程控制块。字段不能只放到达时间和服务时间因为统计阶段需要知道每个进程的首次开始时间、完成时间、剩余时间MLFQ还需要记录当前所在队列级别。struct PCB { int pid; string name; double arrive; double need; double remain; double start; double finish; int level; bool done; };start记录第一次开始执行的时间它在统计响应时间时要用而且只允许写一次之后就不能覆盖。remain表示剩余服务时间FCFS和SJF这类非抢占算法里它等于need但RR和MLFQ每执行一个时间片都要扣减。level只在MLFQ里使用其他算法里保持默认值即可。进程完成后finish被设置done置为true。这个done标志在SJF和HRRN里特别重要因为我们要反复扫描所有进程找“未完成且已到达”的候选如果没有done标志很容易把一个已经跑完的进程再次选进调度。3.2 离散事件驱动用一个时间变量驱动全局调度算法的模拟需要谨慎处理“时间如何推进”。常见做法有两种时间步进法每单位时间推进一格事件驱动法直接跳转到下一个有意义的时刻。我选择的是增量推进维护一个全局cur每次进程完成时让cur等于当前进程的完成时间再进入下一轮调度。关键点在于进程可能在cur之前就已经到达只是还没轮到运行。所以每轮调度开始都要把所有arrive cur且未完成的进程加入就绪池。下面这段代码是所有算法统一的预处理逻辑void collectReady(vectorPCB procs, int cur, vectorint ready) { ready.clear(); for (int i 0; i procs.size(); i) { if (!procs[i].done procs[i].arrive cur) { ready.push_back(i); } } }RR和MLFQ的推进方式略有不同因为它们在一个进程运行期间可能遇到新的到达事件例如时间片没结束就有新进程到达严格来说应该立即触发调度不过非抢占式的简化处理是“当前时间片跑完再检查新到达”这样既保留了算法特征又降低了实现复杂度。我在代码里采用的就是这种简化实验结论不受影响。3.3 统一调度接口把公共逻辑抽出来为了让五个算法共用一套输入输出统计代码我设计了调度器基类class Scheduler { public: virtual void run(vectorPCB procs) 0; void printStats(const vectorPCB procs); };run函数负责填充每个进程的start和finishprintStats负责计算各种平均值。这样每个算法只需要专注实现run内部的核心决策统计逻辑不用重复写代码可读性和维护性都高很多。实际工程里我还会把输入数据固定成结构体数组而不是从文件读取这样不同算法在完全相同的输入上对比结果才没有变量干扰。实验时改输入只需要改进程表非常方便。4. 五个算法的C实现与关键代码4.1 FCFS按到达时间排一次队就够了FCFS是五个算法里最简洁的。先按到达时间排序然后维护一个cur变量依次让每个进程从cur和到达时间中取较大值开始运行。这里有个细节如果当前cur比下一个进程的到达时间早说明CPU空闲了一段start必须取到达时间不能直接取cur。void FCFS(vectorPCB procs) { sort(procs.begin(), procs.end(), [](const PCB a, const PCB b) { if (a.arrive ! b.arrive) return a.arrive b.arrive; return a.pid b.pid; }); double cur 0; for (int i 0; i procs.size(); i) { if (cur procs[i].arrive) cur procs[i].arrive; procs[i].start cur; procs[i].finish cur procs[i].need; cur procs[i].finish; } }排序时加上pid作为第二关键字是为了保证相同到达时间时顺序稳定否则不同编译环境下sort结果可能不同直接导致实验结果无法复现。这一点后面我会再强调。FCFS的代码虽然短但它是其他算法的基础框架。理解了cur的推进方式再看SJF和HRRN就只需要在“选择下一个进程”这一步换成自定义逻辑。4.2 SJF和HRRN每次调度都重新挑人SJF用collectReady把可运行进程收集起来然后选择need最小的那个。注意collectReady要在cur更新后再调用也就是TopCur等于当前完成时间时那些最新到达的进程已经可以参与竞争。void SJF(vectorPCB procs) { double cur 0; int completed 0; while (completed procs.size()) { int sel -1; double minNeed 1e18; for (int i 0; i procs.size(); i) { if (procs[i].done || procs[i].arrive cur) continue; if (procs[i].need minNeed) { minNeed procs[i].need; sel i; } } // 当前时刻没有进程已到达让CPU空转到下一个到达时间 if (sel -1) { double nextArrive 1e18; for (int i 0; i procs.size(); i) if (!procs[i].done) nextArrive min(nextArrive, procs[i].arrive); cur nextArrive; continue; } selected sel; if (cur procs[selected].arrive) cur procs[selected].arrive; procs[selected].start cur; procs[selected].finish cur procs[selected].need; procs[selected].done true; cur procs[selected].finish; completed; } }空转处理的逻辑看着繁琐但非常必要。如果所有未完成进程都还没到达cur不能原地不动否则永远不会进入下一轮循环。直接跳到下一个到达时间点能跳过CPU空闲区间。HRRN的代码几乎一样只是选择条件从“need最小”改成“响应比最大”double calcRP(const PCB p, double cur) { double wait cur - p.arrive; return (wait p.need) / p.need; } // 选择响应比最大的进程 double maxRP -1; for (int i 0; i procs.size(); i) { if (procs[i].done || procs[i].arrive cur) continue; double rp calcRP(procs[i], cur); if (rp maxRP) { maxRP rp; sel i; } }个别教材把响应比写成 wait/need 1其实就是同一个公式写代码时用分数形式更不容易丢精度。4.3 RR队列轮转和时间片扣减RR要维护一个就绪队列队列元素是进程在procs数组里的下标。每次出队一个进程让它运行量子和时间片中的较小值更新remain然后决定是完成还是重新入队。void RR(vectorPCB procs, double quantum) { queueint ready; double cur 0; int completed 0; int n procs.size(); while (completed n) { // 把当前时刻之前的到达进程全部入队 for (int i 0; i n; i) if (!procs[i].done procs[i].arrive cur) ready.push(i); if (ready.empty()) { // CPU空闲跳到下一个到达时间 double nextArrive 1e18; for (int i 0; i n; i) if (!procs[i].done) nextArrive min(nextArrive, procs[i].arrive); cur nextArrive; continue; } int idx ready.front(); ready.pop(); if (procs[idx].start 0) // 首次运行 procs[idx].start cur; double slice min(quantum, procs[idx].remain); cur slice; procs[idx].remain - slice; // 运行期间可能有新进程到达要补入队 for (int i 0; i n; i) if (!procs[i].done procs[i].arrive cur - slice procs[i].arrive cur) ready.push(i); if (procs[idx].remain 0) { procs[idx].finish cur; procs[idx].done true; completed; } else { ready.push(idx); // 未完成重新排队尾 } } }这里很容易犯的一个错误是只在新一轮循环开头入队忽略了进程运行期间也有新进程到达导致那些进程要白白多等一个时间片周期。我在循环体内补了一次入队操作代码略显重复但结果准确得多。时间片quantum是实验参数我建议做成函数参数而不是写死在函数里这样跑对比实验时只需要换一个数字不用复制整段代码。4.4 MLFQ多队列嵌套轮转是重头戏MLFQ实现时最稳妥的做法是准备一个vectorqueue 下标对应优先级0是最高级。新进程一律进第0级用完时间片就降级。调度时从最高级出发找到第一个非空队列执行。void MLFQ(vectorPCB procs, const vectordouble quanta) { int levels quanta.size(); vectorqueueint q(levels); double cur 0; int completed 0; int n procs.size(); // 所有新进程进入最高级这里简化成一次性入队 for (int i 0; i n; i) q[0].push(i); while (completed n) { int selLevel -1; for (int l 0; l levels; l) { if (!q[l].empty()) { selLevel l; break; } } if (selLevel -1) { // 所有队列空跳到下一个到达时间 double nextArrive 1e18; for (int i 0; i n; i) if (!procs[i].done) nextArrive min(nextArrive, procs[i].arrive); cur nextArrive; for (int i 0; i n; i) if (!procs[i].done procs[i].arrive cur) q[0].push(i); continue; } int idx q[selLevel].front(); q[selLevel].pop(); if (procs[idx].start 0) procs[idx].start cur; double slice min(quanta[selLevel], procs[idx].remain); cur slice; procs[idx].remain - slice; // 运行期间到达的进程进入最高级 for (int i 0; i n; i) if (!procs[i].done procs[i].arrive cur - slice procs[i].arrive cur) q[0].push(i); if (procs[idx].remain 0) { procs[idx].finish cur; procs[idx].done true; completed; } else if (selLevel levels - 1) { q[selLevel 1].push(idx); // 降级 } else { q[selLevel].push(idx); // 已在最低级继续轮转 } } }这段代码的主体思路是优先级选择和解队列分离。运行时新进程进入第0级后理论上是应该抢占当前进程的但非抢占式简化可以写成“等当前时间片用完再调度”这样实现起来好控制实验结果也能体现MLFQ的队列迁移特征。如果需要严格抢占可以在每次cur推进后都重新选择最高优先级进程代码会多一层判断。最低级队列的处理也是容易踩坑的地方如果最低级也用完时间片不能无限制降级应该重新入队继续轮转。否则最后一个队列里的进程会越积越多甚至出现永远无法调度的情况。5. 实验对比与结果分析5.1 测试用例与统计输出我用一组不复杂但有区分度的输入来跑对比进程到达时间服务时间A02B13C35D42RR的时间片取2MLFQ用三级队列时间片分别取1、2、4。所有算法在相同输入下运行只输出每个进程的开始时间、完成时间再统一计算统计指标。我把关键统计做成一张总表算法平均周转时间平均带权周转时间FCFS5.251.93SJF4.501.41HRRN4.501.41RRq25.501.83MLFQ1,2,46.002.08从这个结果能看到几个关键现象。第一SJF和HRRN在这组样例上表现一致不是巧合而是进程到达顺序恰好让两个算法的选择策略没有冲突更多进程交叠到达时HRRN会通过响应比机制修正长进程的延迟。第二FCFS因为B、C连续排队平均周转时间明显变差。第三RR和MLFQ反而输给FCFS原因在于短进程D和C被时间片分割多了一次排队和切换等待。这组数据最大的价值是打破“轮转算法一定更好”的直觉。时间片轮转擅长的是提升响应性不是优化平均周转时间尤其是进程服务时间普遍较短时固定时间片会把一个本来能一次跑完的进程拆成两段甚至三段。5.2 逐个进程看调度时间轴只给平均值会掩盖很多细节。我手动推演一遍RR的时序能清楚看到时间片分割的影响t0到t2运行AA完成。 t2到t4运行BB剩余1重新排队。 t3时刻C到达入队t4时刻D到达入队。 t4到t6运行CC剩余3重新排队。 t6到t7运行BB完成。 t7到t9运行DD完成。 t9到t11运行CC剩余1重新排队。 t11到t12运行CC完成。D到t9才完成而如果按SJFD在t5就能跑完。这就是时间片机制付出的“响应性税”。回头看MLFQ时序短进程D虽然一开始在最高级队列运行了一个时间片但紧接着降级到次级队列反而比RR里等一轮更晚完成。这提醒我们MLFQ的队列参数设计直接影响短进程体验级别时间片增长过快或过慢都会产生偏斜。如果你要写实验报告不要只贴一张平均值表至少挑一个有代表性的算法手写或打印出完整调度时间轴。老师或者读者能直接看到进程在哪个区间运行再结合平均值解释比单纯摆数字有说服力得多。5.3 算法的适用场景差异把实验结果放回现实场景会得到更清晰的结论。FCFS适合交互少、进程执行时长差别不大的批处理系统简单可靠但没有优先级区分能力。SJF适合能预先估计运行时间的批处理场景比如科学计算任务但必须接受长任务饥饿的风险。HRRN是两者的折中实现成本不高适合任务到达相对稳定、又需要避免饿死的场景。RR适合交互式系统比如分时操作系统用户需要公平响应哪怕整体吞吐下降也要保证每个任务都能推进。MLFQ则被现代操作系统广泛采用因为它不需要预先知道进程运行时间而是用队列反馈动态调整优先级短进程自动浮在高级长进程沉到低级兼顾响应性和吞吐。实验里MLFQ单个样例表现不好不完全代表它弱因为经典参数q01对短进程其实很苛刻。如果把样例中D的服务时间改成5MLFQ就会明显优于普通RR。做实验时一定要多跑几组数据才能看清算法在不同负载结构下的真实差异。6. 实现过程中的坑与排查建议6.1 时间推进不当导致“进程永远进不了队列”新手写SJF最容易犯一个错误主循环只处理当前已经到达的进程一旦所有未完成进程尚未到达循环就卡在原地出现死循环或输出全为空。解决办法就是前面代码里用nextArrive变量调度不到任何进程时直接把cur跳到下一个到达时间。排查方法也很简单打印每个调度轮次选中的进程、当前cur和候选进程列表。看到连续几轮选中同一个进程或者cur长时间不增长基本就是没有处理空闲区间。6.2 规定答案剩余时间的更新时机RR和MLFQ里进程运行slice时间后remain要减去slice这个操作只能在进程真正获得CPU之后做。有次我在入队阶段就提前减了remain导致进程还没运行就“消耗”了时间片统计出来的完成时间全部偏早还出现过完成时间小于开始时间这种明显反常的数据。正确顺序是出队、记录start、计算slice、推进cur、扣减remain、判断完成或重排。每一步之间的顺序都不可颠倒尤其是cur和remain必须同步更新。建议每行代码都保留注释调试时对照注释检查。6.3 相同到达时间的排序稳定性FCFS排序时如果不加第二关键字相同到达时间的进程顺序可能不稳定实验结果会有波动。我用pid作为第二关键字既保证确定性也让不同算法版本之间能对比。如果你从文件读入测试数据建议每个进程带上自增序号模拟和统计阶段都保留这个序号。遇到排名波动先查是不是排序稳定性问题而不是怀疑算法本身。6.4 注意区分首次开始时间的初始化统计响应时间或绘制时间轴时start字段只应该记录首次运行的时间。RR里一个进程可能多次被调度第二次调度时不能覆盖start。我用start小于0表示“还没运行过”比用bool标志更简洁。同样的逻辑也适用于finish进程完成一次就会被置为done后续不会再参与调度。在MLFQ里进程降级时done一直是false只有remain减到0才会置为true这个判断条件不能写反。6.5 继续扩展的方向做完这套非抢占版本的实现后你可以继续挑战几个变体抢占式SJFSRTF需要每到达一个进程就检查是否需要中断当前进程MLFQ加入“优先级提升”机制防止长进程饥饿把上下文切换开销建模成一个固定时间常量观察它对短时间片算法的影响。每加一个机制模拟器的复杂度和统计指标的可分析性都会上一层楼。我自己实现时最后悔的一件事就是一开始没有抽象出统一的调度器接口导致五个算法的代码各写各的统计逻辑复制了五遍。后面重构时虽然花了不少时间但实验结果的可信度和代码的可读性立刻上来了。你在动手时可以直接从接口设计开始把调度决策和统计输出彻底分开后面无论换算法还是加参数都会轻松很多。