C++实现FCFS与SJF进程调度算法：课程设计实战与避坑指南

简介这份资源面向计算机相关专业学生与操作系统课程学习者提供C实现的进程调度模拟程序重点解决先来先服务FCFS与短作业优先SJF两种算法的对比实验需求。程序支持输入n个进程的到达时间与服务时间分别按两种算法调度计算每个进程的完成时间、周转时间、带权周转时间和等待时间并统计平均周转时间、平均带权周转时间与平均等待时间最后对两算法做出比较评价适合课程设计、期末大作业或算法验证场景。压缩包共3个文件包含1个cpp源码、1个md说明文档和1个exe可执行程序整体约36KB源码便于阅读修改文档辅助理解设计思路exe可直接运行查看调度结果。目前已有2851人学习下载说明该实现具有较好的参考价值。读者可据此快速完成算法编码、结果验证与实验报告撰写并在此基础上扩展优先级调度等更多策略。1. 从一份课程设计说起FCFS 和 SJF 到底在调度什么很多人第一次接触操作系统进程调度是在课程设计大作业里拿到一个题目用 C 模拟 FCFS 和 SJF 两种调度算法。看起来只是写两个排序加一个循环但真正动手才会发现调度不是「谁先来谁先跑」这么简单它牵扯到到达时间、服务时间、等待时间、周转时间、带权周转时间这一整套指标体系还要处理同一时刻多个进程同时到达、服务时间相同、进程编号顺序等边界情况。这份课程设计之所以经典是因为它用最小的代码量把操作系统最核心的调度思想摊开给你看FCFS 先来先服务公平但容易出现「护航效应」一个长作业堵在前面后面一堆短作业全在等SJF 短作业优先平均等待时间理论上最优但必须知道每个进程的服务时间而且长作业可能被无限推迟产生饥饿。如果你正在做这个课程设计或者想用 C 把调度算法跑通、跑对、跑出可对比的数据这篇文章就是按一线实操的路径来写的。我会先讲清楚 FCFS 和 SJF 的选型理由和指标定义再给出可以直接编译运行的源码结构然后重点讲参数怎么设、边界怎么处理、结果怎么验证最后把我自己踩过的坑一条条列出来。适合两类人一类是刚学 C、需要交课程设计的新手跟着步骤能跑通另一类是想复习操作系统调度、需要一份可靠参考实现的熟手能看到非抢占 SJF 和抢占式 SRTF 的区别、以及指标计算里那些容易翻车的地方。2. 先把指标和算法逻辑立住FCFS 与 SJF 的判定标准2.1 四个核心指标等待时间、周转时间、带权周转时间调度算法好不好不能靠感觉要靠指标说话。课程设计里最常要求计算的是四个量完成时间、周转时间、等待时间、带权周转时间。它们的定义必须先在代码里统一否则后面算出来的数对不上。完成时间就是进程执行完毕的时刻。周转时间等于完成时间减去到达时间衡量一个进程从到达到结束总共花了多久。等待时间等于周转时间减去服务时间也就是进程在就绪队列里干等的总时长。带权周转时间等于周转时间除以服务时间这个指标很关键它把长作业和短作业放在同一个尺度上比较短作业如果等太久带权周转时间会非常大能直接暴露调度策略的不合理。我一般会在代码里用一个结构体把进程的所有属性装在一起包括到达时间、服务时间、完成时间、周转时间、等待时间、带权周转时间再加一个是否已完成的标记。这样不管是 FCFS 还是 SJF都操作同一套数据结构最后统一输出表格方便对比。提示带权周转时间是浮点数计算时要用 double不要用 int 截断否则短作业的指标会失真。2.2 FCFS 的判定逻辑按到达时间排队非抢占FCFS 的规则非常直白所有进程按到达时间先后排成一个就绪队列CPU 一旦分配给队首进程就一直执行到它完成中途不被打断。这就是「非抢占」的含义。实现上先把进程按到达时间升序排序然后维护一个当前时间变量 currentTime初始为 0。依次取出每个进程如果它的到达时间大于 currentTime说明 CPU 空闲currentTime 直接跳到它的到达时间否则 currentTime 不变。然后 currentTime 加上它的服务时间得到完成时间再反推周转时间和等待时间。这里有一个容易忽略的点FCFS 的「先来」是按到达时间排但如果两个进程到达时间相同谁先执行常见做法是按进程编号或者输入顺序决定这个规则要在代码里写死并说明否则结果不可复现。另外FCFS 对长作业有利对短作业不利如果第一个进程服务时间是 100后面九个进程服务时间都是 1那后面九个的平均等待时间会非常难看这就是护航效应。2.3 SJF 的判定逻辑每次选服务时间最短的分抢占和非抢占SJF 的核心是「短作业优先」但必须区分两种版本。非抢占式 SJF每次 CPU 空闲时从所有已到达且未完成的进程里选服务时间最短的那个执行一旦开始就不打断。抢占式 SJF 又叫 SRTF最短剩余时间优先每来一个新进程就比较它的服务时间和当前进程的剩余时间如果新进程更短就抢占 CPU。课程设计大作业里绝大多数要求实现的是非抢占式 SJF因为实现简单、结果稳定。但如果你只写非抢占遇到「新进程到达时当前进程还没跑完」的情况就要决定是继续跑完还是重新选。非抢占的规则是继续跑完抢占的规则是重新选。这个区别直接决定最终指标写之前一定要跟题目要求对齐。非抢占 SJF 的实现思路维护一个当前时间每一轮从「已到达且未完成」的进程集合里挑服务时间最小的如果服务时间相同按到达时间早的优先再相同按编号小的优先。选中后执行完更新 currentTime 和各项指标标记完成进入下一轮。循环直到所有进程完成。注意SJF 需要预先知道服务时间这在真实系统里很难做到所以它更多是理论最优的参照实际系统常用的是基于历史估计的近似 SJF。3. 用 C 把两种调度算法跑通源码结构与关键函数3.1 进程结构体与输入约定先定义数据结构。我用一个 PCB 结构体字段覆盖调度和指标计算所需的全部信息。输入格式我一般约定为第一行进程数量 n接下来 n 行每行三个整数分别是进程编号、到达时间、服务时间。这个格式简单、好解析也方便用重定向从文件读入测试数据。#include iostream #include vector #include algorithm #include iomanip using namespace std; struct PCB { int pid; // 进程编号 int arriveTime; // 到达时间 int serviceTime; // 服务时间 int finishTime; // 完成时间 int turnAround; // 周转时间 int waitTime; // 等待时间 double weightedTurnAround; // 带权周转时间 bool finished; // 是否已完成 }; // 按到达时间升序到达时间相同按 pid 升序 bool cmpByArrive(const PCB a, const PCB b) { if (a.arriveTime ! b.arriveTime) return a.arriveTime b.arriveTime; return a.pid b.pid; }这段代码定义了 PCB 和排序规则。finished 字段在 FCFS 里其实用不到但在 SJF 里必须用因为要反复从「未完成」集合里挑。cmpByArrive 保证了 FCFS 的排队顺序可复现到达时间相同时按 pid 排避免结果随机。3.2 FCFS 实现一个循环加当前时间推进FCFS 的实现非常短核心就是按到达时间排序后顺序执行用 currentTime 推进时间轴。void FCFS(vectorPCB procs) { sort(procs.begin(), procs.end(), cmpByArrive); int currentTime 0; for (auto p : procs) { // CPU 空闲则跳到到达时间 if (currentTime p.arriveTime) currentTime p.arriveTime; p.finishTime currentTime p.serviceTime; p.turnAround p.finishTime - p.arriveTime; p.waitTime p.turnAround - p.serviceTime; p.weightedTurnAround (double)p.turnAround / p.serviceTime; currentTime p.finishTime; } }逻辑说明排序后依次处理每个进程。如果当前时间小于进程到达时间说明 CPU 之前空闲直接把 currentTime 拉到到达时间。然后完成时间等于当前时间加服务时间周转时间等于完成时间减到达时间等待时间等于周转时间减服务时间带权周转时间用 double 除法。最后把 currentTime 更新为完成时间供下一个进程使用。参数说明currentTime 是唯一的状态变量初始为 0。如果你的测试数据里第一个进程到达时间不是 0currentTime 会在第一次循环时被拉到它的到达时间这是正确的。不要手动把 currentTime 初始化成第一个进程的到达时间那样逻辑会重复。3.3 非抢占 SJF 实现每轮选最短注意到达时间约束SJF 比 FCFS 多一层选择逻辑。每一轮都要从「已到达且未完成」的进程里挑服务时间最短的而不是简单地按顺序取。void SJF_NonPreemptive(vectorPCB procs) { int n procs.size(); int currentTime 0; int completed 0; while (completed n) { int idx -1; int minService 1e9; // 在已到达且未完成的进程里选服务时间最短的 for (int i 0; i n; i) { if (!procs[i].finished procs[i].arriveTime currentTime) { if (procs[i].serviceTime minService || (procs[i].serviceTime minService procs[i].arriveTime procs[idx].arriveTime)) { minService procs[i].serviceTime; idx i; } } } if (idx -1) { // 当前没有已到达进程时间推进到下一个最早到达的进程 int nextArrive 1e9; for (int i 0; i n; i) { if (!procs[i].finished procs[i].arriveTime nextArrive) nextArrive procs[i].arriveTime; } currentTime nextArrive; continue; } PCB p procs[idx]; p.finishTime currentTime p.serviceTime; p.turnAround p.finishTime - p.arriveTime; p.waitTime p.turnAround - p.serviceTime; p.weightedTurnAround (double)p.turnAround / p.serviceTime; p.finished true; currentTime p.finishTime; completed; } }逻辑说明外层 while 循环直到所有进程完成。内层 for 循环扫描所有未完成且已到达的进程选服务时间最小的。如果服务时间相同用到达时间更早的优先这里用了一个短路条件注意 idx 初始为 -1 时不能直接访问 procs[idx]所以实际写的时候要把相同服务时间的比较单独处理或者先判断 idx 是否为 -1。上面这段为了展示逻辑把相同服务时间的分支写得比较紧凑真正编译时建议拆开写避免越界。参数说明minService 初始化为一个很大的数代表当前最小值。currentTime 在没有已到达进程时推进到下一个最早到达时间这一步不能省否则会死循环。completed 计数器保证循环终止。提示SJF 里「服务时间相同按到达时间优先」这条规则很多课程设计题目没有明说但如果不写结果可能和参考答案不一致。建议在报告里注明你的优先级规则。3.4 输出表格与平均指标计算两种算法跑完后都要输出每个进程的明细和平均周转时间、平均等待时间、平均带权周转时间。表格用 iomanip 控制格式保证对齐。void printResult(const vectorPCB procs, const string algoName) { cout algoName endl; cout left setw(6) PID setw(8) 到达 setw(8) 服务 setw(8) 完成 setw(8) 周转 setw(8) 等待 setw(12) 带权周转 endl; double sumTurn 0, sumWait 0, sumWeighted 0; for (const auto p : procs) { cout left setw(6) p.pid setw(8) p.arriveTime setw(8) p.serviceTime setw(8) p.finishTime setw(8) p.turnAround setw(8) p.waitTime setw(12) fixed setprecision(2) p.weightedTurnAround endl; sumTurn p.turnAround; sumWait p.waitTime; sumWeighted p.weightedTurnAround; } int n procs.size(); cout 平均周转时间: sumTurn / n endl; cout 平均等待时间: sumWait / n endl; cout 平均带权周转时间: sumWeighted / n endl; }逻辑说明遍历进程输出明细同时累加三个指标。最后除以进程数得到平均值。setw 控制列宽fixed 和 setprecision 控制小数位。注意 sumTurn 和 sumWait 用 double 累加避免整数除法丢精度。参数说明setw 的宽度根据你的数据范围调整如果进程编号是两位数PID 列宽要相应加大。setprecision(2) 表示保留两位小数课程设计一般够用如果要求更高可以改成 3。4. 参数怎么设、结果怎么验测试数据与对比方法4.1 三组典型测试数据覆盖护航效应和饥饿场景光跑一组数据看不出算法差异我一般准备三组测试数据分别覆盖不同场景。第一组是常规数据到达时间和服务时间都比较均匀用来验证基本逻辑。第二组是护航效应数据第一个进程服务时间特别长后面全是短作业用来观察 FCFS 的平均等待时间如何被拉高。第三组是饥饿场景数据一个长作业到达很早但服务时间很长后面不断有短作业到达用来观察 SJF 下长作业的等待时间。数据集进程数特点观察重点常规数据5到达时间 0-4服务时间 1-5两种算法结果接近护航效应5首个进程服务时间 20其余为 1FCFS 平均等待时间飙升饥饿场景6长作业服务时间 15短作业持续到达SJF 下长作业等待时间极长这三组数据不需要很复杂手工构造即可。关键是每组跑完后把两种算法的平均周转时间、平均等待时间、平均带权周转时间列在一起对比看趋势是否符合理论预期。如果 FCFS 在护航效应数据下平均等待时间没有明显高于 SJF那大概率是代码逻辑有问题。4.2 手工验算用甘特图核对完成时间代码跑出来的结果不能全信尤其是第一次写的时候。我一般会手工画一个简单的甘特图把每个进程的执行区间标出来然后核对完成时间。比如 FCFS 下进程到达时间分别是 0、1、2服务时间分别是 3、2、1那执行顺序就是 P1 从 0 到 3P2 从 3 到 5P3 从 5 到 6。完成时间分别是 3、5、6。周转时间分别是 3、4、4。等待时间分别是 0、2、3。带权周转时间分别是 1.0、2.0、4.0。手工算一遍再和程序输出对能快速定位是排序错了还是时间推进错了。注意如果程序输出的完成时间小于到达时间加服务时间那一定是 currentTime 的更新逻辑写错了最常见的是忘记在 CPU 空闲时把 currentTime 拉到到达时间。4.3 用随机数据做批量验证手工数据只能覆盖少数情况要验证代码的鲁棒性可以用 C 随机数生成一批测试数据批量跑两种算法检查是否有负数指标、是否有进程未完成、平均指标是否在合理范围内。随机数用 mt19937 配合 uniform_int_distribution比 rand() 更均匀。#include random vectorPCB generateRandom(int n, int maxArrive, int maxService) { random_device rd; mt19937 gen(rd()); uniform_int_distribution arriveDist(0, maxArrive); uniform_int_distribution serviceDist(1, maxService); vectorPCB procs; for (int i 0; i n; i) { PCB p; p.pid i 1; p.arriveTime arriveDist(gen); p.serviceTime serviceDist(gen); p.finished false; procs.push_back(p); } return procs; }逻辑说明用 random_device 做种子mt19937 做引擎两个均匀分布分别生成到达时间和服务时间。服务时间最小值设为 1避免出现 0 导致除零错误。生成后返回进程数组可以直接喂给 FCFS 和 SJF 函数。参数说明n 是进程数量maxArrive 控制到达时间范围maxService 控制服务时间范围。批量测试时可以把 n 设成 10 到 20maxArrive 设成 10maxService 设成 10跑几百次检查有没有异常输出。5. 避坑与排查课程设计里最容易翻车的五个地方5.1 现象SJF 结果和参考答案不一致平均等待时间偏大原因最常见的是把非抢占 SJF 写成了「按服务时间全局排序后顺序执行」忽略了到达时间约束。比如一个服务时间很短的进程到达时间很晚全局排序会把它排到前面但它在当前时刻根本没到达不能执行。另一个原因是相同服务时间时的优先级规则和参考答案不同。解决SJF 每一轮选择前必须先过滤「已到达且未完成」的进程再在其中选服务时间最短的。相同服务时间时明确按到达时间早优先再按 pid 小优先并在报告里写明规则。可以用手工数据验算一轮确认选择逻辑正确。5.2 现象程序输出完成时间小于到达时间加服务时间原因currentTime 没有在 CPU 空闲时正确推进。FCFS 里如果第一个进程到达时间是 5currentTime 初始为 0不处理的话完成时间会算成 0 加服务时间明显错误。SJF 里如果没有已到达进程currentTime 没有跳到下一个到达时间也会出问题。解决FCFS 里每次循环先判断 currentTime 是否小于到达时间是则拉到到达时间。SJF 里如果本轮没有选出进程就把 currentTime 推进到下一个最早到达时间然后 continue。这两个判断是必须的不能省。5.3 现象带权周转时间输出为整数短作业指标失真原因周转时间和服务时间都是 int直接相除会做整数除法结果被截断。比如周转时间 7服务时间 2整数除法结果是 3实际应该是 3.5。解决计算带权周转时间时把其中一个操作数强制转成 double或者把结果字段定义成 double。输出时用 fixed 和 setprecision 控制小数位。这个问题很隐蔽因为平均等待时间可能看起来正常但带权周转时间会整体偏小。5.4 现象多个进程同时到达时执行顺序随机每次运行结果不同原因排序函数没有处理到达时间相同的情况或者用了不稳定的排序。std::sort 是不稳定排序如果比较函数只比较到达时间相同到达时间的进程相对顺序可能变化。解决在比较函数里增加第二级和第三级排序规则比如到达时间相同按 pid 升序。这样每次运行结果都一致。如果题目要求按输入顺序那就用 stable_sort或者在结构体里加一个输入序号字段参与比较。5.5 现象SJF 下长作业一直不执行程序陷入死循环原因如果长作业到达时间很早但服务时间很长而短作业不断到达非抢占 SJF 会在每轮都选短作业长作业一直排在后面。如果代码里没有正确处理「所有已到达进程都完成后的时间推进」可能在某轮选不出进程时死循环。解决确保 while 循环里有 completed 计数器每执行完一个进程就加一循环条件是 completed 小于 n。选不出进程时currentTime 必须推进到下一个最早到达时间不能原地不动。另外非抢占 SJF 虽然会让长作业等待很久但只要短作业有穷尽长作业最终会被执行不会真正饥饿。如果测试数据里短作业无限多那是数据问题不是代码问题。6. 进阶技巧把两种算法封装成可切换的调度器并输出对比报告把 FCFS 和 SJF 写完之后如果只是各跑各的报告里对比起来很麻烦。我一般会做一层轻封装定义一个调度器接口把两种算法注册进去用同一个输入数据集跑两遍自动输出对比表格。这样不仅报告好看也方便你加第三种算法比如时间片轮转或者优先级调度。具体做法是定义一个函数指针类型或者用 std::function把 FCFS 和 SJF 都包装成void(vectorPCB)的形式然后写一个 runAndCompare 函数接收原始进程列表和算法列表每个算法用一份拷贝跑完后收集平均指标。#include functional void runAndCompare(const vectorPCB original, const vectorpairstring, functionvoid(vectorPCB) algos) { cout left setw(16) 算法 setw(16) 平均周转 setw(16) 平均等待 setw(16) 平均带权周转 endl; for (const auto algo : algos) { vectorPCB procs original; // 每个算法用独立拷贝 algo.second(procs); double sumTurn 0, sumWait 0, sumWeighted 0; for (const auto p : procs) { sumTurn p.turnAround; sumWait p.waitTime; sumWeighted p.weightedTurnAround; } int n procs.size(); cout left setw(16) algo.first setw(16) fixed setprecision(2) sumTurn / n setw(16) sumWait / n setw(16) sumWeighted / n endl; } }逻辑说明runAndCompare 接收原始进程列表和算法列表。每个算法执行前把原始列表拷贝一份避免上一个算法修改了 finished 和指标字段影响下一个算法。然后调用算法函数累加指标输出一行对比。这样你只需要在 main 里构造一次数据注册 FCFS 和 SJF就能得到一张对比表。参数说明algos 是一个 vector元素是「算法名 函数对象」的 pair。函数对象用 std::function 包装可以接收普通函数、lambda 或者函数指针。注意每个算法必须用独立的进程拷贝否则 finished 字段会被污染第二个算法跑出来的结果是错的。这个坑我在第一次写对比工具时就踩过排查了半天才发现是数据没隔离。除了对比表我还会加一个简单的验证函数检查每个进程的完成时间是否大于等于到达时间加服务时间等待时间是否非负带权周转时间是否大于等于 1。这些不变量一旦被破坏说明调度逻辑有 bug。验证函数不需要很复杂几行判断就够但能帮你快速定位问题。bool validate(const vectorPCB procs) { for (const auto p : procs) { if (p.finishTime p.arriveTime p.serviceTime) return false; if (p.waitTime 0) return false; if (p.weightedTurnAround 1.0 - 1e-9) return false; } return true; }逻辑说明遍历所有进程检查三个不变量。完成时间不能小于到达时间加服务时间等待时间不能为负带权周转时间不能小于 1。浮点数比较用 1e-9 的容差避免精度问题误报。参数说明这个函数在每次调度后调用一次返回 false 就打印错误信息并退出。它不能保证结果一定正确但能挡住大部分低级错误。最后说一个我自己的习惯课程设计的代码不要写完就交一定要用随机数据跑几百轮每轮都调用 validate确认没有异常。我当年第一次做这个课设手工数据全对随机数据跑到第 37 轮就出现了负数等待时间查了半天发现是 SJF 里相同服务时间的比较分支写错了idx 为 -1 时访问了数组越界。这种问题手工数据很难触发只有批量随机测试才能暴露。把验证做在前面比交上去被打回来再改要省事得多。希望帮到你。本文还有配套的精品资源点击获取