简介一份面向操作系统课程设计的两道批处理系统两级调度模拟实现方案专为需要完成作业调度与进程调度实验的学生准备。内容围绕内存最多容纳两道作业的约束实现了先来先服务的作业调度与可抢占优先级的进程调度并附有测试数据可对比不同算法下作业选中次序与平均周转时间帮助理解两级调度模型和实现过程。资源包共171个文件约78.6MB以cpp源文件、vcxproj工程配置、exe可执行程序和pdb调试信息为主同时包含tlog编译日志、txt说明文档、py辅助脚本等便于直接编译运行和二次修改动态可视化界面也降低了课设验收展示门槛。已有832人学习下载包内除主体调度模拟外还赠送多道批处理、可变式分区、轮转法等关联实验以及完整工程目录与调试记录可作为操作系统课设的参考模板也能为理解进程管理、内存分区等知识点提供代码级素材。1. 两级调度实验先想明白“两级”管什么代码才不会写成单队列批处理系统的两级调度几乎是每个操作系统实验的标配但很多同学交上去的版本其实是“单队列 单调度”的简化模型作业来了就创建进程进程跑完就算结束。这种做法在功能演示上能跑通可一旦老师追问“你的作业调度在哪一步触发的调度时机是什么内存够不够你怎么判断的”就容易露馅。两级调度的本质是两件不同粒度的事宏观调度作业调度负责从外存后备队列选作业调入内存微观调度进程调度负责从内存的就绪队列选进程占用 CPU。前者管的是“谁能进内存”后者管的是“谁用 CPU”两者通过进程的创建和终止联动。这篇笔记以实验场景为例从原理、数据结构、算法选型到联动逻辑逐一拆开给出可直接改用的实现路径。2. 两级调度的核心模型宏观选作业微观选进程2.1 为什么必须是“两级”吞吐量与响应时间的解耦批处理系统的特点是作业成批到达、成批处理早期系统没有交互需求目标很单纯尽量让 CPU 别闲着、让内存别空着。如果只用一级调度进程调度那么所有到达的作业都直接创建进程、全部进内存内存会被瞬时占满如果只做作业调度不做进程调度作业进了内存却没人分配 CPU系统又跑不动。两级调度就是把“选谁进内存”和“选谁用 CPU”切开每级各管一段各自可以独立调整策略。这种拆分带来的直接收益是吞吐量和响应时间能被单独调优。作业调度管的是长周期行为单位是秒甚至分钟级它关心的是整体吞吐量——一个作业从提交到完成的平均周转时间进程调度管的是短周期行为单位是毫秒级它关心的是 CPU 利用率和响应时间。举个具体例子假设内存上限 4 个进程作业调度每次只放 1 个作业进来那内存永远不会打满但吞吐量上不去如果作业调度一口气放 4 个内存满了后续到达的作业就只能排队等着作业调度又退化成 FCFS。两级调度的存在意义就是让这两件事各自有独立的调参空间。实验里最常见的误区是“作业调度 进程调度的前置步骤执行一次就结束”。实际上作业调度是一个持续运行的过程每当一个作业完成并释放内存内存占用就出现了空位这时候作业调度就应该从后备队列再选一个作业补进来。这个“补位”动作和进程调度一直交替发生直到所有作业处理完。2.2 数据结构的骨架JCB 与 PCB 的字段设计两级调度最少需要两类控制块作业控制块JCB和进程控制块PCB。JCB 对应宏观层描述的是“一个作业从提交到完成”的全过程信息PCB 对应微观层描述的是“一个可被调度执行的进程实例”的信息。两者之间的桥梁是作业 ID——一个作业被调度进入内存后会创建一个 PCBPCB 里必须能溯源到它对应的作业 ID。JCB 的字段设计我一般按下面这个最小集合来定义够用且不冗余typedef struct jcb { int job_id; // 作业编号全局唯一 int arrive_time; // 到达时间相对时间从0开始 int need_time; // 作业需要的总CPU时间服务时间 int mem_size; // 作业需要的内存大小单位自定义 int status; // 0-后备 1-就绪(已调入内存) 2-运行 3-完成 struct jcb *next; // 队列指针用于挂入后备队列和完成队列 } JCB;字段上有一个容易被低估的坑status必须保留“后备”和“就绪”的区分。很多实验里作业调度和进程调度共用同一个状态枚举导致作业一被调入内存就变 Running后面进程调度根本没法标记“就绪但不运行”的中间态。我在做的时候把状态拆成两层含义JCB 的 status 描述宏观状态是否已获准进入内存PCB 的 status 描述微观状态是否占用 CPU。两层状态不要合并。PCB 的最小字段设计如下typedef struct pcb { int job_id; // 溯源到作业 int need_time; // 该进程还需要多少CPU时间初始等于JCB的need_time int used_time; // 累计占用CPU时间用于计算周转时间 int status; // 0-就绪 1-运行 2-等待(本实验通常无) 3-完成 struct pcb *next; } PCB;注意need_time在 JCB 和 PCB 里各存了一份这不是拷贝浪费而是必要的冗余。作业调度做决策时要用 JCB 里的总服务时间进程调度每次选进程时要用 PCB 里的剩余时间。如果 PCB 没有剩余时间字段进程调度每次都要跨表查 JCB一是慢二是逻辑容易串。2.3 队列的组织方式后备队列与就绪队列的设计队列组织决定了调度器的实现复杂度。最简单但足够清晰的方案是两条单向链表——后备队列hold_queue和就绪队列ready_queue另外可以有完成队列finish_queue用来按序输出结果。后备队列按到达时间排序作业调度每次从队头开始遍历选一个满足内存条件的作业出队入内存。就绪队列按调度算法动态排序——用 FCFS 就按入队顺序排用 SJF 就按剩余时间排用优先级就按优先级排排序时机放在每次调度之前而不是插入时排序这样算法切换只需要改排序函数不需要改动队列维护逻辑。内存管理在实验里通常简化为“总容量 已占用”的计数模型不涉及具体地址分配。我在实现时用了一个全局变量mem_used每次作业调入内存时mem_used jcb-mem_size进程完成时mem_used - jcb-mem_size。这种模型能应付大多数实验要求但如果你的题目要求展示内存碎片或需要按分区分配就得用空闲链表或位图。多数本科实验不要求到那一层计数模型是性价比最高的选择。两级调度器的主循环可以抽象成下面的骨架while (未处理完所有作业) { // 1. 作业调度检查内存尝试调入新作业 schedule_job(); // 2. 进程调度从就绪队列选一个进程运行 schedule_proc(); }这个循环里有个关键细节schedule_job()和schedule_proc()的执行顺序不能反过来。如果先做进程调度再做作业调度可能出现 CPU 已经空转了一个时间片新调进来的作业才刚创建 PCB白白浪费一个单位时间。反过来先做作业调度新作业的 PCB 进入就绪队列进程调度立刻就能从中选择效率更高。提示主循环的“一个时间片”单位要统一。作业调度和进程调度共用一个时间源通常以 1 个时间单位可映射为 1ms 或 1s为步长每步先作业调度再进程调度。3. 作业调度宏观调度实现算法选型与参数设计3.1 作业调度的触发时机不是“有作业就调”而是“有位置才调”作业调度的触发条件不是新作业到达而是内存有空位 后备队列非空。这两个条件必须同时满足。只满足前者表示没有候选作业可调只满足后者表示内存没有空间接收新作业。很多实现写的是“每时间单位检查一次只要后备队列非空就调”结果刚调一个作业进内存还没来得及创建 PCB下一次循环又尝试调入下一个内存瞬间被占满。正确的触发逻辑应该是每时间单位先检查“内存剩余空间 一个作业的内存需求”如果满足就从后备队列里按策略选一个作业调入如果不满足则等待下一个时间单位。为了稳定起见我在实现里把内存检查放在外层作业选择放在内层void schedule_job() { if (hold_queue NULL) return; // 后备队列空无事可做 if (mem_used mem_total) return; // 内存满了不能调入 JCB *candidate NULL; int min_service 999999; for (JCB *q hold_queue; q; q q-next) { // 按SJF选找服务时间最短且内存能容下的作业 if (q-mem_size (mem_total - mem_used) q-need_time min_service) { candidate q; min_service q-need_time; } } if (candidate NULL) return; // 剩余作业都放不下等到有作业完成再说 // 从后备队列摘除candidate dequeue_hold(candidate); // 创建PCB并挂入就绪队列 PCB *proc (PCB *)malloc(sizeof(PCB)); proc-job_id candidate-job_id; proc-need_time candidate-need_time; proc-used_time 0; proc-status 0; // 0-就绪 enqueue_ready(proc); // 更新内存占用 mem_used candidate-mem_size; candidate-status 1; // 已调入内存 }这段代码选的是 SJF短作业优先示例。外层条件是内存余量内层条件是服务时间最短。注意候选作业的选择条件是“能放得下”的作业里挑最短的而不是全局最短的作业——如果全局最短的作业内存需求超过当前剩余空间它只能继续等次短的反而先进。这也符合实际批处理系统的约束内存优先保证能装下算法保证公平或效率。参数说明这里有三个需要调的地方。第一个是mem_total这个值决定了同时驻留内存的进程数量上限一般设为“最大作业内存需求的 2~3 倍”否则所有作业会被卡在内存口。第二是调度算法的选择。FCFS 最简单按后备队列顺序取队头代码更短但平均周转时间会高SJF 能显著降低平均周转时间但可能导致长作业饥饿。实验要求不指定算法时我用 SJF 跑默认数据 预留算法参数答辩时说清楚“如果换成 FCFS平均周转时间会增加多少”这是加分点。还有一个容易忽略的细节作业调度要把“调入”和“创建进程”做成原子操作。不要先更新内存计数再分配 PCB也不要先创建 PCB 再更新内存中间如果有异常分支跳出内存计数和 PCB 数量就会失配。上面代码里先摘队列、再创建 PCB、最后更新内存任何一个步骤失败都可以回调或直接报错退出状态可回溯。3.2 调度算法的选型依据看你的实验数据长什么样作业调度算法的选型不是随机的它应该跟着实验给的作业数据走。如果作业的服务时间分布很均匀SJF 和 FCFS 差异不大如果作业的服务时间两极分化严重比如一个 1 分钟、一个 30 分钟SJF 的优势会非常明显但长作业的等待时间也会很难看。实验数据通常在题目里已给定我的建议是先用 FCFS 跑一遍拿基准数据再看长作业是否饥饿如果饥饿明显换 HRRN最高响应比优先作为补充。HRRN 的计算公式是响应比 (等待时间 服务时间) / 服务时间每次作业调度时对所有后备作业计算并选最大值。它比 SJF 温和不会让长作业一直等到天荒地老。在一个实验里同时实现 FCFS 和 SJF 并不难关键是抽象出一个调度策略函数JCB *select_from_hold(int mode) { JCB *ans NULL; if (mode 0) { // FCFS直接取队头 ans hold_queue; } else if (mode 1) { // SJF for (JCB *q hold_queue; q; q q-next) { if (ans NULL || q-need_time ans-need_time) ans q; } } else if (mode 2) { // HRRN for (JCB *q hold_queue; q; q q-next) { double ratio_cur (cur_time - q-arrive_time q-need_time) / (double)q-need_time; double ratio_ans (ans NULL) ? -1.0 : (cur_time - ans-arrive_time ans-need_time) / (double)ans-need_time; if (ratio_cur ratio_ans) ans q; } } return ans; }注意 HRRN 里用到了cur_time当前时间和arrive_time的差值来计算等待时间。这个cur_time必须由主循环的步进时间累加器来维护不能用操作系统实时时钟否则数据不可复现。实验报告里的每个数值都需要能解释清楚来源这是和实际生产代码不一样的地方——生产系统要求效率实验要求可解释所以时间源要统一。3.3 作业调度的输出设计让每个时间片都有迹可循很多实现最后的输出只有“每个作业的到达时间、完成时间、周转时间”三列老师很难看出两级调度的过程。我的做法是开启一个 trace 模式每个时间单位的调度决策都打印一行格式如下时间 事件 作业ID 当前内存占用 0 作业到达 1 0 0 作业调度作业1调入内存 1 8 0 进程调度进程1占用CPU 1 8 2 作业调度内存无空位跳过 - 8 4 作业完成内存释放 1 0这种输出在调试时帮助极大。翻车时看 trace 比看最终数据高效得多比如“作业调度内存无空位跳过”反复出现且作业一直没有完成说明进程调度可能卡死或时间片没推进问题一目了然。4. 进程调度微观调度实现与作业调度的联动4.1 时间片轮转与优先级实验里怎么选才合理进程调度层面本科实验最常用的是时间片轮转RR和动态优先级抢占。RR 实现简单、公平性好适合展示“时间片”概念优先级抢占适合展示“作业完成后的联动”因为有抢占就有进程切换切换的输出更丰富。时间片轮转有两个隐性问题。第一个是时间片的长度设定。如果时间片远小于作业的服务时间上下文切换开销占比会很高周转时间会被切换成本拉长如果时间片远大于最长的作业服务时间大部分作业在一个时间片内就跑完了RR 退化成近似 FCFS。经验法则是把时间片设为“最短作业服务时间的 1/3 到 1/2”比如实验数据里最短作业需要 3 个时间单位时间片给 1 或 2 个单位比较合适。第二个问题是时间片用尽的判定。每走一个时间单位当前进程的need_time - 1当它减到 0 时进程完成要立刻释放内存并触发作业调度补位不是等到下一个时间片开始再处理。优先级抢占的策略相对灵活。每次进程调度时从就绪队列里选优先级最高的进程如果抢占了被抢占的进程要回到就绪队列头部或按原优先级重新排队。我建议优先级调度和时间片轮转结合每个优先级内部用 RR 轮转不同优先级之间用抢占。这样既展示了抢占机制又不至于让低优先级进程彻底饿死。4.2 进程调度的核心代码状态推进与时间片管理void schedule_proc() { if (ready_queue NULL) return; // 就绪队列空CPU空闲 PCB *run pick_next_proc(); // 按当前算法选一个进程 run-status 1; // 置为运行态 run-need_time - time_slice; // 消耗一个时间片 run-used_time time_slice; printf(时间 %d: 进程 %d 运行剩余 %d\n, cur_time, run-job_id, run-need_time); if (run-need_time 0) { // 进程完成释放内存、回收PCB、提示作业调度可以补充 JCB *jcb find_jcb(run-job_id); mem_used - jcb-mem_size; jcb-status 3; // 完成 finish_jobs 1; // 从就绪队列摘除run标记PCB为完成态 dequeue_ready(run); run-status 3; } else { // 时间片未用完放回就绪队列尾部RR模式 run-status 0; requeue_ready(run); } }这段代码里最关键的是run-need_time - time_slice被放在进程调度的内部而不是主循环里。如果主循环每次调用schedule_proc()只负责“选一个进程”然后外部再扣减时间那就把“选进程”和“推进执行”拆成了两步中间如果有其他函数插入执行时间的推进就变得不可控。我最初的实现也走过这种弯路结果作业调度的“每时间单位补位”和进程调度的“每时间单位推进”发生在不同的函数里输出对不上。参数说明上time_slice是在初始化阶段设置的全局常量。需要留意它和主循环步长的关系如果主循环每单位时间调用一次schedule_proc()变量名time_slice不能和步长冲突它们一个是调度间隔一个是分配给进程的 CPU 时间额度实验里通常相等但概念上要分开。我习惯设置如下#define TIME_SLICE 1 // 每个进程每次调度至多运行的CPU时间 #define STEP_UNIT 1 // 主循环每次前进的时间单位两者相等的时候整个系统看起来像一个时钟驱动的模拟器。如果题目要求可变时间片再拆开即可。顺序上作业调度先走、进程调度后走已经在前一节说明了原因。4.3 两级联动的关键作业完成后的内存释放与补位两级调度最容易翻车的地方是作业完成后内存释放了但作业调度不知道这件事后备队列里的作业一直等。根源是进程调度在 PCB 完成时只做了 PCB 层面的清理没有去更新 JCB 状态和mem_used。解决方法是把内存释放的动作写进进程完成的分支里并且要找到对应的 JCB 来更新状态。联动逻辑的完整顺序应该是进程运行时间片消耗完 - need_time 0 - 从就绪队列移除PCB - 释放内存mem_used - jcb-mem_size - 更新JCB状态为完成 - 更新完成作业计数 - 回到主循环作业调度检查内存空位并调入新作业这里的顺序错位会有明显症状。如果先更新 JCB 完成状态但没减内存作业调度永远等到内存满的信号后续作业全部滞留如果先减内存但没更新 JCB 状态完成队列的数据统计会缺字段。我把这个顺序抽成了一个名为finish_proc(PCB *proc)的函数进程调度只需要调用它避免在任何地方随手改mem_used。下面是一个可供直接参考的finish_proc实现void finish_proc(PCB *proc) { JCB *job find_jcb(proc-job_id); if (job NULL) { error(JCB not found); return; } job-status 3; // 作业完成 job-finish_time cur_time; mem_used - job-mem_size; // 释放内存可能触发补位 dequeue_ready(proc); // 从就绪队列摘除 free(proc); // 释放PCB资源 finish_count; // 完成计数1 }写mem_used - job-mem_size时我用的是job-mem_size不是proc里的某个字段。因为 PCB 里没有存内存需求如果直接写mem_used - something你会发现自己并不知道这个进程占了多少内存还得去查 JCB。这也是为什么之前强调 PCB 不需要冗余存储内存大小——通过job_id溯源即可避免同一份数据在两个结构体里被改到不一致。5. 实验中的高频踩坑与排查清单5.1 现象CPU 空转但内存还有空位后备队列里的作业就是不进原因多半是作业调度在某个时间单位内没有找到“内存能装下”且“算法选中”的作业。排查优先看mem_used是否被错误地多加了一次。常见翻车点在进程完成时只把 PCB 置为完成态忘了更新mem_used内存占用虚高新作业永远进不来。解决办法是在finish_proc里打个日志打印mem_used的变化对照作业分配时mem_used的增长看是否成对出现。5.2 现象作业调度不触发状态一直停在“后备”原因是主循环里schedule_job()和schedule_proc()的执行顺序或触发条件写错。如果作业调度只在“新作业到达”时调用那么当内存空位出现时旧作业完成没有新作业到达调度器就没有机会补位。正确逻辑是主循环每走一个时间单位在不管有没有新作业的情况下都检查一次作业调度条件。这是我的血泪经验把schedule_job()从到达事件里拆出来放回主循环的固定位置后问题直接消失。5.3 现象进程调度顺序与预期不符总是先跑后到的作业原因可能是就绪队列的插入位置有问题。SJF 算法下新到达的短作业应该插入到就绪队列的特定位置而不是直接挂队尾。如果插入函数只是append到链表末尾那么即使调度算法选的是“剩余时间最短”队列里也可能因为插入顺序不对而选了次优项。排查方式是在schedule_proc()前打印整个就绪队列的job_id need_time人工核对每次选出的进程是否确实是剩余时间最短的那个。5.4 现象内存释放后计数变负数或明显不对常见原因是同一作业被释放了两次。比如在进程调度need_time 0时free(PCB)后又调用了finish_proc(PCB)而finish_proc内部再次执行dequeue_ready和free双重释放引发不可预期的内存状态。我的排查手法是不再纠结valgrind在模拟程序里的输出直接在所有会改mem_used的入口处打一行日志日志格式统一为“时间 函数名 作业ID 变更前/后内存值”跑一遍几秒钟的模拟就能反推出哪一步重复扣减。5.5 现象程序正常运行但最后完成时间比预期大得多这通常是时间片太短或作业调度时机太密集导致的“假死节奏”。时间片为 1 时一个服务时间 100 的作业需要 100 次调度循环每次循环还伴随作业调度检查、就绪队列排序、日志打印执行速度会变慢如果时间片太小还会造成大量作业在就绪队列和 CPU 之间来回换。排查办法是把时间片调到 2 或 3 再跑一遍对比周转时间指标的变化幅度。如果时间片 1 和 2 的结果差异巨大说明系统实际上是在用高频切换换公平而不是在处理作业。提示以上五个问题如果一小时内排查无果强烈建议把代码的模拟主循环改为“单步执行模式”——每按一次时间单位只走一步并打印所有调度决策。多花的半小时换来的是定位问题的高效和答辩时逐帧讲解的素材。6. 实验报告与争优把可视化输出做成答辩的加分项基础功能跑通以后从“通过”到“争优”的距离通常不在算法本身而在呈现。我见过不少代码实现和策略都正确的作业因为输出只有一行行密密麻麻的日志老师完全没法快速看出两级调度的联动过程分数就卡在中等水平。建议把轨迹数据整理成一个时间线表格行是每个时间单位列是“后备队列状态、内存占用、就绪队列状态、运行进程、完成事件”在报告里贴 3 到 4 个有代表性的时间段比如一次完整的内存补位周期。输出格式用 CSV 或能直接贴进 Excel 的文本不要手工整理。答辩时最能拉开差距的一个动作是主动说明“两级调度的效率边界”。你可以提前跑一组不同mem_total的对比实验内存上限从“每作业独立内存”到“可同时容纳 2 个、3 个作业”观察平均周转时间的变化曲线。一般情况下内存容量从 1 提升到 2 时周转时间改善最明显再往上增速放缓这就是两级调度里的资源瓶颈现象。能讲出这层规律的比只背算法优劣的同学高出一截。另一个争优细节是公平性与效率的取舍书面化。比如你选了 SJF 做作业调度一定要亲手跑一遍长作业的等待时间如果超过其他作业总服务时间就在报告里写“长作业存在饥饿风险实验规模下可接受若数据规模扩大应启用 HRRN”。同样地进程调度选 RR 时把时间片对周转时间的影响做一个小表格证明时间片不是随便拍的。如果你想让输出更直观可以做一个极简的甘特图式时间轴——用文本字符画代替图形库每一行代表一个时间单位|A|A|B|B|的格式表示两个进程交替运行再配上内存占用曲线。这类 ASCII 图在报告里可读性极高而且不需要装任何绘图依赖。配合前面说的单步模式实际上你已经在答辩前把所有可能的追问都预演了一遍。这套方案跑通之后最直观的收获是你不再只是“写了一个能出结果的程序”而是对整个操作系统资源调度的运行方式有了框架级认知。我在做离线批处理实验时养成的习惯——所有状态用日志串起来、每个调度决策能解释为什么是这个选择——后来做并发编程时依然适用。排查逻辑别靠猜先打日志再下结论。希望这个思路能帮你在实验里少踩几个坑把更多时间花在吃透调度本质上。本文还有配套的精品资源点击获取
两级调度实验详解：作业调度与进程调度如何联动
简介一份面向操作系统课程设计的两道批处理系统两级调度模拟实现方案专为需要完成作业调度与进程调度实验的学生准备。内容围绕内存最多容纳两道作业的约束实现了先来先服务的作业调度与可抢占优先级的进程调度并附有测试数据可对比不同算法下作业选中次序与平均周转时间帮助理解两级调度模型和实现过程。资源包共171个文件约78.6MB以cpp源文件、vcxproj工程配置、exe可执行程序和pdb调试信息为主同时包含tlog编译日志、txt说明文档、py辅助脚本等便于直接编译运行和二次修改动态可视化界面也降低了课设验收展示门槛。已有832人学习下载包内除主体调度模拟外还赠送多道批处理、可变式分区、轮转法等关联实验以及完整工程目录与调试记录可作为操作系统课设的参考模板也能为理解进程管理、内存分区等知识点提供代码级素材。1. 两级调度实验先想明白“两级”管什么代码才不会写成单队列批处理系统的两级调度几乎是每个操作系统实验的标配但很多同学交上去的版本其实是“单队列 单调度”的简化模型作业来了就创建进程进程跑完就算结束。这种做法在功能演示上能跑通可一旦老师追问“你的作业调度在哪一步触发的调度时机是什么内存够不够你怎么判断的”就容易露馅。两级调度的本质是两件不同粒度的事宏观调度作业调度负责从外存后备队列选作业调入内存微观调度进程调度负责从内存的就绪队列选进程占用 CPU。前者管的是“谁能进内存”后者管的是“谁用 CPU”两者通过进程的创建和终止联动。这篇笔记以实验场景为例从原理、数据结构、算法选型到联动逻辑逐一拆开给出可直接改用的实现路径。2. 两级调度的核心模型宏观选作业微观选进程2.1 为什么必须是“两级”吞吐量与响应时间的解耦批处理系统的特点是作业成批到达、成批处理早期系统没有交互需求目标很单纯尽量让 CPU 别闲着、让内存别空着。如果只用一级调度进程调度那么所有到达的作业都直接创建进程、全部进内存内存会被瞬时占满如果只做作业调度不做进程调度作业进了内存却没人分配 CPU系统又跑不动。两级调度就是把“选谁进内存”和“选谁用 CPU”切开每级各管一段各自可以独立调整策略。这种拆分带来的直接收益是吞吐量和响应时间能被单独调优。作业调度管的是长周期行为单位是秒甚至分钟级它关心的是整体吞吐量——一个作业从提交到完成的平均周转时间进程调度管的是短周期行为单位是毫秒级它关心的是 CPU 利用率和响应时间。举个具体例子假设内存上限 4 个进程作业调度每次只放 1 个作业进来那内存永远不会打满但吞吐量上不去如果作业调度一口气放 4 个内存满了后续到达的作业就只能排队等着作业调度又退化成 FCFS。两级调度的存在意义就是让这两件事各自有独立的调参空间。实验里最常见的误区是“作业调度 进程调度的前置步骤执行一次就结束”。实际上作业调度是一个持续运行的过程每当一个作业完成并释放内存内存占用就出现了空位这时候作业调度就应该从后备队列再选一个作业补进来。这个“补位”动作和进程调度一直交替发生直到所有作业处理完。2.2 数据结构的骨架JCB 与 PCB 的字段设计两级调度最少需要两类控制块作业控制块JCB和进程控制块PCB。JCB 对应宏观层描述的是“一个作业从提交到完成”的全过程信息PCB 对应微观层描述的是“一个可被调度执行的进程实例”的信息。两者之间的桥梁是作业 ID——一个作业被调度进入内存后会创建一个 PCBPCB 里必须能溯源到它对应的作业 ID。JCB 的字段设计我一般按下面这个最小集合来定义够用且不冗余typedef struct jcb { int job_id; // 作业编号全局唯一 int arrive_time; // 到达时间相对时间从0开始 int need_time; // 作业需要的总CPU时间服务时间 int mem_size; // 作业需要的内存大小单位自定义 int status; // 0-后备 1-就绪(已调入内存) 2-运行 3-完成 struct jcb *next; // 队列指针用于挂入后备队列和完成队列 } JCB;字段上有一个容易被低估的坑status必须保留“后备”和“就绪”的区分。很多实验里作业调度和进程调度共用同一个状态枚举导致作业一被调入内存就变 Running后面进程调度根本没法标记“就绪但不运行”的中间态。我在做的时候把状态拆成两层含义JCB 的 status 描述宏观状态是否已获准进入内存PCB 的 status 描述微观状态是否占用 CPU。两层状态不要合并。PCB 的最小字段设计如下typedef struct pcb { int job_id; // 溯源到作业 int need_time; // 该进程还需要多少CPU时间初始等于JCB的need_time int used_time; // 累计占用CPU时间用于计算周转时间 int status; // 0-就绪 1-运行 2-等待(本实验通常无) 3-完成 struct pcb *next; } PCB;注意need_time在 JCB 和 PCB 里各存了一份这不是拷贝浪费而是必要的冗余。作业调度做决策时要用 JCB 里的总服务时间进程调度每次选进程时要用 PCB 里的剩余时间。如果 PCB 没有剩余时间字段进程调度每次都要跨表查 JCB一是慢二是逻辑容易串。2.3 队列的组织方式后备队列与就绪队列的设计队列组织决定了调度器的实现复杂度。最简单但足够清晰的方案是两条单向链表——后备队列hold_queue和就绪队列ready_queue另外可以有完成队列finish_queue用来按序输出结果。后备队列按到达时间排序作业调度每次从队头开始遍历选一个满足内存条件的作业出队入内存。就绪队列按调度算法动态排序——用 FCFS 就按入队顺序排用 SJF 就按剩余时间排用优先级就按优先级排排序时机放在每次调度之前而不是插入时排序这样算法切换只需要改排序函数不需要改动队列维护逻辑。内存管理在实验里通常简化为“总容量 已占用”的计数模型不涉及具体地址分配。我在实现时用了一个全局变量mem_used每次作业调入内存时mem_used jcb-mem_size进程完成时mem_used - jcb-mem_size。这种模型能应付大多数实验要求但如果你的题目要求展示内存碎片或需要按分区分配就得用空闲链表或位图。多数本科实验不要求到那一层计数模型是性价比最高的选择。两级调度器的主循环可以抽象成下面的骨架while (未处理完所有作业) { // 1. 作业调度检查内存尝试调入新作业 schedule_job(); // 2. 进程调度从就绪队列选一个进程运行 schedule_proc(); }这个循环里有个关键细节schedule_job()和schedule_proc()的执行顺序不能反过来。如果先做进程调度再做作业调度可能出现 CPU 已经空转了一个时间片新调进来的作业才刚创建 PCB白白浪费一个单位时间。反过来先做作业调度新作业的 PCB 进入就绪队列进程调度立刻就能从中选择效率更高。提示主循环的“一个时间片”单位要统一。作业调度和进程调度共用一个时间源通常以 1 个时间单位可映射为 1ms 或 1s为步长每步先作业调度再进程调度。3. 作业调度宏观调度实现算法选型与参数设计3.1 作业调度的触发时机不是“有作业就调”而是“有位置才调”作业调度的触发条件不是新作业到达而是内存有空位 后备队列非空。这两个条件必须同时满足。只满足前者表示没有候选作业可调只满足后者表示内存没有空间接收新作业。很多实现写的是“每时间单位检查一次只要后备队列非空就调”结果刚调一个作业进内存还没来得及创建 PCB下一次循环又尝试调入下一个内存瞬间被占满。正确的触发逻辑应该是每时间单位先检查“内存剩余空间 一个作业的内存需求”如果满足就从后备队列里按策略选一个作业调入如果不满足则等待下一个时间单位。为了稳定起见我在实现里把内存检查放在外层作业选择放在内层void schedule_job() { if (hold_queue NULL) return; // 后备队列空无事可做 if (mem_used mem_total) return; // 内存满了不能调入 JCB *candidate NULL; int min_service 999999; for (JCB *q hold_queue; q; q q-next) { // 按SJF选找服务时间最短且内存能容下的作业 if (q-mem_size (mem_total - mem_used) q-need_time min_service) { candidate q; min_service q-need_time; } } if (candidate NULL) return; // 剩余作业都放不下等到有作业完成再说 // 从后备队列摘除candidate dequeue_hold(candidate); // 创建PCB并挂入就绪队列 PCB *proc (PCB *)malloc(sizeof(PCB)); proc-job_id candidate-job_id; proc-need_time candidate-need_time; proc-used_time 0; proc-status 0; // 0-就绪 enqueue_ready(proc); // 更新内存占用 mem_used candidate-mem_size; candidate-status 1; // 已调入内存 }这段代码选的是 SJF短作业优先示例。外层条件是内存余量内层条件是服务时间最短。注意候选作业的选择条件是“能放得下”的作业里挑最短的而不是全局最短的作业——如果全局最短的作业内存需求超过当前剩余空间它只能继续等次短的反而先进。这也符合实际批处理系统的约束内存优先保证能装下算法保证公平或效率。参数说明这里有三个需要调的地方。第一个是mem_total这个值决定了同时驻留内存的进程数量上限一般设为“最大作业内存需求的 2~3 倍”否则所有作业会被卡在内存口。第二是调度算法的选择。FCFS 最简单按后备队列顺序取队头代码更短但平均周转时间会高SJF 能显著降低平均周转时间但可能导致长作业饥饿。实验要求不指定算法时我用 SJF 跑默认数据 预留算法参数答辩时说清楚“如果换成 FCFS平均周转时间会增加多少”这是加分点。还有一个容易忽略的细节作业调度要把“调入”和“创建进程”做成原子操作。不要先更新内存计数再分配 PCB也不要先创建 PCB 再更新内存中间如果有异常分支跳出内存计数和 PCB 数量就会失配。上面代码里先摘队列、再创建 PCB、最后更新内存任何一个步骤失败都可以回调或直接报错退出状态可回溯。3.2 调度算法的选型依据看你的实验数据长什么样作业调度算法的选型不是随机的它应该跟着实验给的作业数据走。如果作业的服务时间分布很均匀SJF 和 FCFS 差异不大如果作业的服务时间两极分化严重比如一个 1 分钟、一个 30 分钟SJF 的优势会非常明显但长作业的等待时间也会很难看。实验数据通常在题目里已给定我的建议是先用 FCFS 跑一遍拿基准数据再看长作业是否饥饿如果饥饿明显换 HRRN最高响应比优先作为补充。HRRN 的计算公式是响应比 (等待时间 服务时间) / 服务时间每次作业调度时对所有后备作业计算并选最大值。它比 SJF 温和不会让长作业一直等到天荒地老。在一个实验里同时实现 FCFS 和 SJF 并不难关键是抽象出一个调度策略函数JCB *select_from_hold(int mode) { JCB *ans NULL; if (mode 0) { // FCFS直接取队头 ans hold_queue; } else if (mode 1) { // SJF for (JCB *q hold_queue; q; q q-next) { if (ans NULL || q-need_time ans-need_time) ans q; } } else if (mode 2) { // HRRN for (JCB *q hold_queue; q; q q-next) { double ratio_cur (cur_time - q-arrive_time q-need_time) / (double)q-need_time; double ratio_ans (ans NULL) ? -1.0 : (cur_time - ans-arrive_time ans-need_time) / (double)ans-need_time; if (ratio_cur ratio_ans) ans q; } } return ans; }注意 HRRN 里用到了cur_time当前时间和arrive_time的差值来计算等待时间。这个cur_time必须由主循环的步进时间累加器来维护不能用操作系统实时时钟否则数据不可复现。实验报告里的每个数值都需要能解释清楚来源这是和实际生产代码不一样的地方——生产系统要求效率实验要求可解释所以时间源要统一。3.3 作业调度的输出设计让每个时间片都有迹可循很多实现最后的输出只有“每个作业的到达时间、完成时间、周转时间”三列老师很难看出两级调度的过程。我的做法是开启一个 trace 模式每个时间单位的调度决策都打印一行格式如下时间 事件 作业ID 当前内存占用 0 作业到达 1 0 0 作业调度作业1调入内存 1 8 0 进程调度进程1占用CPU 1 8 2 作业调度内存无空位跳过 - 8 4 作业完成内存释放 1 0这种输出在调试时帮助极大。翻车时看 trace 比看最终数据高效得多比如“作业调度内存无空位跳过”反复出现且作业一直没有完成说明进程调度可能卡死或时间片没推进问题一目了然。4. 进程调度微观调度实现与作业调度的联动4.1 时间片轮转与优先级实验里怎么选才合理进程调度层面本科实验最常用的是时间片轮转RR和动态优先级抢占。RR 实现简单、公平性好适合展示“时间片”概念优先级抢占适合展示“作业完成后的联动”因为有抢占就有进程切换切换的输出更丰富。时间片轮转有两个隐性问题。第一个是时间片的长度设定。如果时间片远小于作业的服务时间上下文切换开销占比会很高周转时间会被切换成本拉长如果时间片远大于最长的作业服务时间大部分作业在一个时间片内就跑完了RR 退化成近似 FCFS。经验法则是把时间片设为“最短作业服务时间的 1/3 到 1/2”比如实验数据里最短作业需要 3 个时间单位时间片给 1 或 2 个单位比较合适。第二个问题是时间片用尽的判定。每走一个时间单位当前进程的need_time - 1当它减到 0 时进程完成要立刻释放内存并触发作业调度补位不是等到下一个时间片开始再处理。优先级抢占的策略相对灵活。每次进程调度时从就绪队列里选优先级最高的进程如果抢占了被抢占的进程要回到就绪队列头部或按原优先级重新排队。我建议优先级调度和时间片轮转结合每个优先级内部用 RR 轮转不同优先级之间用抢占。这样既展示了抢占机制又不至于让低优先级进程彻底饿死。4.2 进程调度的核心代码状态推进与时间片管理void schedule_proc() { if (ready_queue NULL) return; // 就绪队列空CPU空闲 PCB *run pick_next_proc(); // 按当前算法选一个进程 run-status 1; // 置为运行态 run-need_time - time_slice; // 消耗一个时间片 run-used_time time_slice; printf(时间 %d: 进程 %d 运行剩余 %d\n, cur_time, run-job_id, run-need_time); if (run-need_time 0) { // 进程完成释放内存、回收PCB、提示作业调度可以补充 JCB *jcb find_jcb(run-job_id); mem_used - jcb-mem_size; jcb-status 3; // 完成 finish_jobs 1; // 从就绪队列摘除run标记PCB为完成态 dequeue_ready(run); run-status 3; } else { // 时间片未用完放回就绪队列尾部RR模式 run-status 0; requeue_ready(run); } }这段代码里最关键的是run-need_time - time_slice被放在进程调度的内部而不是主循环里。如果主循环每次调用schedule_proc()只负责“选一个进程”然后外部再扣减时间那就把“选进程”和“推进执行”拆成了两步中间如果有其他函数插入执行时间的推进就变得不可控。我最初的实现也走过这种弯路结果作业调度的“每时间单位补位”和进程调度的“每时间单位推进”发生在不同的函数里输出对不上。参数说明上time_slice是在初始化阶段设置的全局常量。需要留意它和主循环步长的关系如果主循环每单位时间调用一次schedule_proc()变量名time_slice不能和步长冲突它们一个是调度间隔一个是分配给进程的 CPU 时间额度实验里通常相等但概念上要分开。我习惯设置如下#define TIME_SLICE 1 // 每个进程每次调度至多运行的CPU时间 #define STEP_UNIT 1 // 主循环每次前进的时间单位两者相等的时候整个系统看起来像一个时钟驱动的模拟器。如果题目要求可变时间片再拆开即可。顺序上作业调度先走、进程调度后走已经在前一节说明了原因。4.3 两级联动的关键作业完成后的内存释放与补位两级调度最容易翻车的地方是作业完成后内存释放了但作业调度不知道这件事后备队列里的作业一直等。根源是进程调度在 PCB 完成时只做了 PCB 层面的清理没有去更新 JCB 状态和mem_used。解决方法是把内存释放的动作写进进程完成的分支里并且要找到对应的 JCB 来更新状态。联动逻辑的完整顺序应该是进程运行时间片消耗完 - need_time 0 - 从就绪队列移除PCB - 释放内存mem_used - jcb-mem_size - 更新JCB状态为完成 - 更新完成作业计数 - 回到主循环作业调度检查内存空位并调入新作业这里的顺序错位会有明显症状。如果先更新 JCB 完成状态但没减内存作业调度永远等到内存满的信号后续作业全部滞留如果先减内存但没更新 JCB 状态完成队列的数据统计会缺字段。我把这个顺序抽成了一个名为finish_proc(PCB *proc)的函数进程调度只需要调用它避免在任何地方随手改mem_used。下面是一个可供直接参考的finish_proc实现void finish_proc(PCB *proc) { JCB *job find_jcb(proc-job_id); if (job NULL) { error(JCB not found); return; } job-status 3; // 作业完成 job-finish_time cur_time; mem_used - job-mem_size; // 释放内存可能触发补位 dequeue_ready(proc); // 从就绪队列摘除 free(proc); // 释放PCB资源 finish_count; // 完成计数1 }写mem_used - job-mem_size时我用的是job-mem_size不是proc里的某个字段。因为 PCB 里没有存内存需求如果直接写mem_used - something你会发现自己并不知道这个进程占了多少内存还得去查 JCB。这也是为什么之前强调 PCB 不需要冗余存储内存大小——通过job_id溯源即可避免同一份数据在两个结构体里被改到不一致。5. 实验中的高频踩坑与排查清单5.1 现象CPU 空转但内存还有空位后备队列里的作业就是不进原因多半是作业调度在某个时间单位内没有找到“内存能装下”且“算法选中”的作业。排查优先看mem_used是否被错误地多加了一次。常见翻车点在进程完成时只把 PCB 置为完成态忘了更新mem_used内存占用虚高新作业永远进不来。解决办法是在finish_proc里打个日志打印mem_used的变化对照作业分配时mem_used的增长看是否成对出现。5.2 现象作业调度不触发状态一直停在“后备”原因是主循环里schedule_job()和schedule_proc()的执行顺序或触发条件写错。如果作业调度只在“新作业到达”时调用那么当内存空位出现时旧作业完成没有新作业到达调度器就没有机会补位。正确逻辑是主循环每走一个时间单位在不管有没有新作业的情况下都检查一次作业调度条件。这是我的血泪经验把schedule_job()从到达事件里拆出来放回主循环的固定位置后问题直接消失。5.3 现象进程调度顺序与预期不符总是先跑后到的作业原因可能是就绪队列的插入位置有问题。SJF 算法下新到达的短作业应该插入到就绪队列的特定位置而不是直接挂队尾。如果插入函数只是append到链表末尾那么即使调度算法选的是“剩余时间最短”队列里也可能因为插入顺序不对而选了次优项。排查方式是在schedule_proc()前打印整个就绪队列的job_id need_time人工核对每次选出的进程是否确实是剩余时间最短的那个。5.4 现象内存释放后计数变负数或明显不对常见原因是同一作业被释放了两次。比如在进程调度need_time 0时free(PCB)后又调用了finish_proc(PCB)而finish_proc内部再次执行dequeue_ready和free双重释放引发不可预期的内存状态。我的排查手法是不再纠结valgrind在模拟程序里的输出直接在所有会改mem_used的入口处打一行日志日志格式统一为“时间 函数名 作业ID 变更前/后内存值”跑一遍几秒钟的模拟就能反推出哪一步重复扣减。5.5 现象程序正常运行但最后完成时间比预期大得多这通常是时间片太短或作业调度时机太密集导致的“假死节奏”。时间片为 1 时一个服务时间 100 的作业需要 100 次调度循环每次循环还伴随作业调度检查、就绪队列排序、日志打印执行速度会变慢如果时间片太小还会造成大量作业在就绪队列和 CPU 之间来回换。排查办法是把时间片调到 2 或 3 再跑一遍对比周转时间指标的变化幅度。如果时间片 1 和 2 的结果差异巨大说明系统实际上是在用高频切换换公平而不是在处理作业。提示以上五个问题如果一小时内排查无果强烈建议把代码的模拟主循环改为“单步执行模式”——每按一次时间单位只走一步并打印所有调度决策。多花的半小时换来的是定位问题的高效和答辩时逐帧讲解的素材。6. 实验报告与争优把可视化输出做成答辩的加分项基础功能跑通以后从“通过”到“争优”的距离通常不在算法本身而在呈现。我见过不少代码实现和策略都正确的作业因为输出只有一行行密密麻麻的日志老师完全没法快速看出两级调度的联动过程分数就卡在中等水平。建议把轨迹数据整理成一个时间线表格行是每个时间单位列是“后备队列状态、内存占用、就绪队列状态、运行进程、完成事件”在报告里贴 3 到 4 个有代表性的时间段比如一次完整的内存补位周期。输出格式用 CSV 或能直接贴进 Excel 的文本不要手工整理。答辩时最能拉开差距的一个动作是主动说明“两级调度的效率边界”。你可以提前跑一组不同mem_total的对比实验内存上限从“每作业独立内存”到“可同时容纳 2 个、3 个作业”观察平均周转时间的变化曲线。一般情况下内存容量从 1 提升到 2 时周转时间改善最明显再往上增速放缓这就是两级调度里的资源瓶颈现象。能讲出这层规律的比只背算法优劣的同学高出一截。另一个争优细节是公平性与效率的取舍书面化。比如你选了 SJF 做作业调度一定要亲手跑一遍长作业的等待时间如果超过其他作业总服务时间就在报告里写“长作业存在饥饿风险实验规模下可接受若数据规模扩大应启用 HRRN”。同样地进程调度选 RR 时把时间片对周转时间的影响做一个小表格证明时间片不是随便拍的。如果你想让输出更直观可以做一个极简的甘特图式时间轴——用文本字符画代替图形库每一行代表一个时间单位|A|A|B|B|的格式表示两个进程交替运行再配上内存占用曲线。这类 ASCII 图在报告里可读性极高而且不需要装任何绘图依赖。配合前面说的单步模式实际上你已经在答辩前把所有可能的追问都预演了一遍。这套方案跑通之后最直观的收获是你不再只是“写了一个能出结果的程序”而是对整个操作系统资源调度的运行方式有了框架级认知。我在做离线批处理实验时养成的习惯——所有状态用日志串起来、每个调度决策能解释为什么是这个选择——后来做并发编程时依然适用。排查逻辑别靠猜先打日志再下结论。希望这个思路能帮你在实验里少踩几个坑把更多时间花在吃透调度本质上。本文还有配套的精品资源点击获取
