简介这是一份面向操作系统课程设计与期末复习的文档资料围绕 CPU 调度核心知识点完整模拟了先到先服务 FCFS、非抢占最短作业优先 SJF、可抢占优先权调度 PRIOR、时间片轮转 RR 四种经典算法。内容从设计目的、设计要求到具体实现与结论层层展开既包含结构体定义、链表队列、冒泡排序等关键程序片段也提供平均周转时间、带权平均周转时间等评价指标的计算思路适合计算机相关专业学生对照实验任务理解调度原理、完成课程设计或进行代码调试。资源包共 1 个文件均为 doc 格式文档大小仅 93KB轻量易用可直接查阅与二次整理。目前已有 315 人浏览学习可作为操作系统实践环节的参考素材。文档中针对优先权调度和 FCFS、SJF 综合算法分别给出了 C 语言示例代码便于读者在理解算法流程的同时快速迁移到自己的程序中提升课程设计的完成效率与规范性。1. 调度算法模拟难的不是算法而是数据结构把 FCFS、SJF、PRIOR、RR 这四种 CPU 调度算法用 C 语言完整跑通很多人的第一反应是写选择排序再套个循环。真正动手才发现卡住自己的不是排序逻辑而是进程控制块PCB怎么组织、就绪队列怎么维护、时间片轮转时指针怎么移动。这份课程设计给出的做法很有意思优先权调度用结构体数组加选择排序实现FCFS 和 SJF 用带头结点的链表管理作业控制块RR 算法则直接在一个环形队列里反复移动队首指针。三种数据组织方式对应四种调度策略这本身就是理解调度器内核结构的一条捷径。适合正在做操作系统课程设计的本科生、准备复试的考研党以及想快速补一轮调度器到底怎么把进程换进换出的应用层开发。2. 四种调度算法的适用边界与 PCB 建模2.1 算法各自成立的场景假设FCFS、SJF、PRIOR、RR 这四种算法表面上只是从就绪队列选下一个进程的规则不同本质上是对进程到达模式和执行时间分布的不同假设。FCFS 假设所有进程最终都会执行完毕且中途不阻塞哪个先到就先把 CPU 给谁。它的优点是公平且实现成本极低缺点也很明显一个执行时间 100ms 的长作业先到后面 5 个 1ms 的短作业全部排后面平均周转时间被拉得极高。SJF 把选择条件改成执行时间最短的先跑在批处理场景下能显著降低平均周转时间但对长作业可能造成无限期饥饿。PRIOR 则更极端完全按优先级调度适合有明确任务紧急程度的实时或交互系统。RR 用时间片强制轮转每个进程最多连续占有一个时间片属于分时系统的基础方案它牺牲了一部分吞吐量换来了响应时间上限。四种算法的调度依据和执行特征整理如下算法选择依据抢占性主要适用场景典型风险FCFS到达时间最早非抢占批处理、无实时要求护长抑短SJF执行时间最短非抢占批处理、短任务为主长作业饥饿PRIOR优先级最高可抢占或非抢占实时系统、优先级分层低优先级饥饿RR时间片轮转抢占按时间片分时系统、交互式负载时间片选择敏感这段设计说明里没有体现到达时间这个维度对 FCFS 的影响。严格说非抢占式调度要走得通必须先把进程按到达时间排序否则第一个到达的进程可能被排到后面。写代码时要额外加一步按ts提交时间的预排序或每次调度时扫描就绪状态中ts time的进程如原文档给出的fcfs()循环里p-ts time的判断。2.2 进程控制块PCB的字段设计与队列选型四种算法要统一跑PCB 至少要能同时支撑按时间排序、按执行时间排序、按优先级排序、按轮转次序移动四种操作。原文档里struct jcb的字段设计是够用的struct jcb { char name[10]; /* 作业名 */ char state; /* 作业状态W 就绪、R 运行、F 完成 */ int ts; /* 提交时间 */ float super; /* 优先权 */ int tb; /* 开始运行时间 */ int tc; /* 完成时间 */ float ti; /* 周转时间 */ float wi; /* 带权周转时间 */ int ntime; /* 作业所需运行时间 */ struct jcb *link; /* 指向下一个作业 */ };字段含义并不复杂tb是实际开始运行时间tc是完成时间ti tc - ts是周转时间wi ti / ntime是带权周转时间。这五个字段是后面算评价指标的唯一数据来源。数据组织的选型上原文档给了两种路线。优先权调度用的是结构体数组加选择排序因为该场景默认所有进程同时就绪不需要动态插入数组足够。FCFS 和 SJF 用单向链表是为了承载进程按到达时间逐步进入就绪状态的动态过程——每次从队头扫描找到满足state W ts time的最短作业或最早作业。RR 算法把链表头尾相连用front和rear两个指针模拟环形队列每次时间片结束把当前进程摘下来挂到队尾。这个选型逻辑是对的数组适合静态排序链表适合动态挑选环形队列适合周期性轮转。一个值得注意的实现细节优先权调度版本用选择排序对p[i]指针数组排序而不是搬移整个结构体。这种指针排序的做法省去了结构体复制开销在N 10的场景下没差别但写大规模模拟器时能省下大量内存拷贝时间。FCFS/SJF 版本则通过链表节点的link字段重新连接不搬数据同样是这个思路。3. 核心代码拆解从排序到调度主循环3.1 FCFS 与 SJF 的链表扫描与空闲等待处理FCFS 和 SJF 的公共框架是同一个区别只在于fcfs()和sjf()函数里选进程的条件——一个找最早到达一个找最短执行。先看sjf()的选择逻辑void sjf(int m) { JCB *min; int i, iden; for (i 0; i n; i) { p min head; iden 1; do { if (p-state W p-ts time) { if (iden) { min p; iden 0; } else if (p-ntime min-ntime) { min p; } } p p-link; } while (p ! NULL); if (iden) { i--; printf(\ntime%d:\tno JCB submib...wait..., time); time; } else { running(min, m); } } }逻辑说明外层for循环本意是执行 n 次每个进程一次。内层do...while从链表头开始扫描state W表示就绪ts time表示进程已经到达。iden作为一个标志位1表示还没找到第一个可运行进程0表示已经找到过候选后续只更新更短者。如果一轮扫描下来iden仍为1说明当前时刻没有已到达的就绪进程这时time模拟 CPU 空闲一个单位时间再用i--抵消本次循环计数重新扫描。这个处理是模拟调度器必须写的否则到达时间晚于 0 的进程会被直接跳过。fcfs()的思路类似但去掉了最短时间比较只在扫描时记录第一个满足ts time且状态为W的节点。这里有个隐蔽的问题原代码用p-ts time作为到达判断隐含假设所有进程在时间 0 前提交。如果测试数据里第一个进程到达时间是 5while 循环会把time一路加到 5这段空转在输出里表现为一行行的 no JCB submib...wait...。我一般会在inital()里先统计最小ts把time初始化成这个值能省掉一大段无意义输出。3.2 优先权调度的选择排序与指标累计优先权调度的实现直接了当先按优先级降序排好然后逐个累加执行时间。核心排序段for (j 0; j n - 1; j) { temp j; for (i j 1; i n; i) { if (p[i]-priority p[temp]-priority) temp i; } q p[j]; p[j] p[temp]; p[temp] q; } for (i 0; i n; i) { time p[i]-zhixing; p[i]-zhouzhuan time; p[i]-dq_zhouzhuan p[i]-zhouzhuan / p[i]-zhixing; }排序段是标准的选择排序比较的是priority交换的是指针。交换后p[0]指向优先级最高的进程p[n-1]指向最低的。调度段用一个共享的time变量模拟CPU累计运行时间第 i 个进程的完成时间等于前 i 个进程执行时间之和这正好是周转时间因为默认所有进程同时到达。dq_zhouzhuan是带权周转时间即周转时间除以执行时间。最后对zhouzhuan和dq_zhouzhuan求和取平均得到平均周转时间和平均带权周转时间。参数说明priority数值越大优先级越高这是设计约定。若想改成值小优先把比较符号从换成即可。zhixing是浮点类型输入时用%f读取排序时比较的是priority整型字段两者互不干扰。如果换一种写法在插入排序中同时兼顾到达时间与优先级就变成了可抢占优先权调度——需要每次运行一个时间单位后重新检查是否有更高优先级进程到达原文档没有做这一步属于非抢占版本。3.3 RR 环形队列的指针重连与完成退出RR 算法的关键不在选择排序而在当前进程时间片用完被挪到队尾的指针操作。看这段移动逻辑while (front) { printf(Running Time : %d\n, time); if (front-rtime time) { front-state R; front-ntime--; printf(\n *** 当前正在运行的进程%s\n, front-name); if (front-ntime 0) { p front; if (front-link ! NULL) front front-link; else { printf(\n finished\n); break; } p-link NULL; destroy(); } else { rear-link front; /* 未完成进程挂到队尾 */ p front; if (front-link ! NULL) front front-link; else { printf(\n finished\n); break; } p-link NULL; } check(); } }逻辑说明front始终指向当前运行进程rear指向队尾。当进程需要继续运行时先把rear-link指向front把当前进程接到队尾然后将front后移一位把原front的link置空。这样原队首进程就被摘下并挂到队尾完成了轮转的核心动作。当所有进程都执行完且队列只剩最后一个节点时front-link为 NULL进入else分支直接 break。这段实现有个值得商榷的地方每次循环front-ntime--只减 1且time也是每次加 1相当于时间片 q 1 的特殊情况。如果想把时间片改成 3需要在ntime减去一个变量片长而不是固定 1同时要在一个时间片内循环执行ntime--直到片长耗尽或进程完成。原代码隐含的时间片为 1作为课程设计是合格的但报告中如果写时间片可配置就名不副实。我一般会加一个q参数实现通用版本。4. 平均周转时间与平均带权周转时间的统计口径4.1 两个评价指标的公式与算例对照课程设计要求计算平均周转时间和平均等待时间文档正文里实际算的是平均周转时间和平均带权周转时间。这几个量要先分清周转时间ti tc - ts即完成时刻减提交时刻表示一个作业从进入系统到完成所花的总时间包含等待、执行和可能的中断。带权周转时间wi ti / ntime即周转时间除以执行时间衡量每单位执行时间摊到多少周转开销越接近 1 越好。平均周转时间Σti / n是所有作业周转时间的算术平均。平均带权周转时间Σwi / n。注意平均等待时间没有在文档代码里直接算但可以由平均周转时间 - 平均执行时间推算。SJF 之所以常被作为最优非抢占算法举例正是因为它在所有作业同时到达时能使平均等待时间最小。拿一个三进程例子手算验证。假设 A、B、C 同时到达执行时间分别为 5、2、3。FCFS 按 A-B-C 顺序执行完成时间分别为 5、7、10周转时间也是 5、7、10平均 7.33带权周转时间分别为 1、3.5、3.33平均 2.61。SJF 按 B-C-A 顺序执行完成时间分别为 2、5、10平均周转时间 5.67比 FCFS 明显更优。写程序时可以用这组数据直接验证输出。4.2 从输出反查调度逻辑的检查清单程序跑完不能只看平均指标就交差要按以下顺序核对输出合理性调度顺序是否符合算法定义。FCFS 按提交时间递增SJF 按执行时间递增PRIOR 按优先级降序RR 按时间片轮转。顺序错了后面所有指标都白算。第一个进程的tb是否等于它的ts。如果第一个进程到达时间晚于 0而输出显示它一开始就在运行说明时间推进逻辑漏了空闲等待处理。每个进程的ti是否等于tc - ts。如果完成时间算错周转时间必然出错。当多个进程执行时间相同时SJF 的次序是否稳定。代码里用的是严格小于相同执行时间时保留先扫描到的节点链表顺序即输入顺序结果应与输入顺序一致。eti 0; ewi 0; for (i 0; i n; i) { ti tc - ts; wi (float)ti / ntime; eti ti; ewi wi; printf(job %s: tb%d tc%d ti%.2f wi%.2f\n, name, tb, tc, ti, wi); } printf(average ti%.3f average wi%.3f\n, eti / n, ewi / n);这段代码把每个作业的周转时间和带权周转时间打印出来再输出全局均值。eti和ewi是全局累加器在running()里被累加等到last()里除以作业数 n 得到平均值。注意eti和ewi是 float 类型累加时不会因为多个进程产生精度灾难但 n 较大时建议用 double。当碰到输出里wi特别大的进程时优先检查它的ts是不是很小但ntime更小。比如提交时间 0、执行时间 1 的进程在优先级最低时可能等了几十个时间片才被调度wi可能到几十这提示优先级算法存在饥饿问题。对课程设计报告来说这恰恰是分析算法优劣的素材。5. 一条技巧用固定样例做回归验证文件重定向批量跑测调试这套调度模拟程序最实用的一条技巧是构造一个固定三进程样例作为基准配合文件重定向批量验证四种算法的输出。准备一个os2.txt格式保持与fileinput()的读取方式一致3 P1 0 5 CPU P2 1 2 CPU P3 2 3 CPU分别对 FCFS、SJF、PRIOR手工把三种优先级设为 3、1、2 后跑一遍用一张纸手算出预期调度顺序和平均周转时间再对比程序输出。这个做法的价值在于把程序是否写对和算法是否理解对分开验证——如果手算和程序结果一致说明代码逻辑正确接下来换随机数据才敢信任结果。运行命令在 Windows 控制台下可以这样写os2.exe os2.txt原代码里的freopen(in.txt, r, stdin)也是同类用法。这样做的好处是每次调试不需要重新手工敲入进程参数改输入直接编辑文本文件即可。改动参数后重定向一次几十秒内能跑完一组实验。用同样的输入文件跑1FCFS和2SJF对比输出里两个指标的变化——SJF 的平均周转时间应小于 FCFS这是验证算法实现是否正确的另一个标志。最后补一个调试细节代码中有几处getch()等待按键在自动化批量跑测试时会被卡住。调试阶段把这些调用注释掉或者用#ifdef DEBUG包起来只在手动演示时保留。本文还有配套的精品资源点击获取