多级反馈队列调度与生产者消费者同步实验思路与实现

简介重庆大学操作系统实验四是面向计算机科学与技术专业的进程线程管理实验资料基于VS2013开发环境由洪明尖老师指导适合校内同学对照实验要求梳理代码实现与调试思路。资源压缩包体积约509KB包内文件总数与类型清单暂未标注。内容围绕Windows平台下C系统编程展开覆盖进程与线程基础概念、CreateProcess与CreateThread等系统调用、进程间通信与线程同步机制涵盖互斥量、信号量、事件对象等常见同步工具也包含多线程编程、调度算法原理、异常安全与资源管理以及基于VS2013的性能分析思路。通过实际编写和调试代码读者可以体验从创建进程到处理线程同步的完整流程理解不同调度策略对程序行为的影响为后续并发编程、服务器端开发等方向打好基础。目前已有649人学习或下载适合需要快速把握实验重点、理解Windows进程线程管理要点的本科阶段学生。 每学期操作系统实验一开到第四个教室里的叹气声总会比前几次明显很多。前面几个实验顶多摸摸环境、写点系统调用到了实验四就要正面碰进程调度和同步互斥代码量上去了概念也突然抽象了。重庆大学的操作系统实验四这几年基本稳定在进程管理这个方向上常见的题目包括模拟实现某种调度算法、用信号量解决经典同步问题或者两者结合做一个小型综合实验。我这次拿到的题目就是“多级反馈队列调度算法模拟 生产者消费者同步验证”的组合型实验正好把操作系统的两大核心模块串在了一起。这篇文章把我从拆题到写完报告的完整过程整理出来重点是思路和踩坑代码只贴关键片段希望能帮后面做同一类实验的同学少走几步弯路。1. 实验四到底在考什么拆题目是第一步1.1 我拿到的题目与关键点提取先看我当时拿到的题目原文简化后设计一个模拟程序实现多级反馈队列MLFQ调度算法要求支持进程的动态到达、时间片轮转、优先级降级和老化机制在此基础上增加一组生产者消费者线程验证信号量同步的正确性并统计进程的平均周转时间、平均等待时间。这道题表面上是两个独立任务实际上是一道很典型的“组合拳”调度部分考的是你对多级反馈队列的理解深度。它不像先来先服务那样无脑排队也不像时间片轮转那样一视同仁MLFQ的核心思想是“用历史表现动态调整优先级”——一个进程如果在当前队列的时间片内频繁用满说明它可能是CPU密集型的就把它降级到更低优先级、更大时间片的队列如果它经常主动让出CPU比如等待I/O说明它是交互型的就让它留在高优先级队列保证响应速度。同步部分考的是信号量P/V操作的熟练度。生产者消费者是最经典的同步互斥模型三个信号量互斥锁、空槽位、满槽位的初值和顺序稍有不慎就会死锁或忙等。隐藏考点是数据结构和日志设计。你需要设计PCB进程控制块、就绪队列、时间片计数、到达时间/完成时间的记录这些直接决定了统计指标能不能算对。拆完题目之后我第一反应是这题不能一上来就写代码得先把PCB结构和队列模型画清楚否则后面改起来非常痛苦。1.2 方案选型为什么用纯软件模拟而不是写内核模块做这类实验有三种常见的技术路线直接改真实内核比如给Linux内核添加一个新的调度策略然后在QEMU虚拟机里跑。这个方案最“硬核”但调试周期长一个指针错误就可能导致内核崩溃而且实验环境不统一答辩时出问题的概率很高。用系统调用接口获取真实进程然后通过nice值或cgroup限制来观察调度效果。这个方案的问题在于你无法精确控制“进程什么时候到达”也很难复现多个进程在同一时刻竞争CPU的场景实验数据不可控。在应用层写一个调度模拟器用结构体模拟PCB用队列模拟就绪队列用随机数或预置脚本模拟进程到达把所有调度逻辑显式写出来。这是大多数同学包括我最终选择的路线。我选第三种原因很实际模拟器能把调度算法本身从操作系统实现细节中剥离开让你把100%的注意力放在算法逻辑上。而且模拟器可以打印非常详细的日志——每个时间片结束后的队列状态、每个进程的运行历史这对验证正确性和答辩展示都有巨大帮助。你甚至可以做一个简单的可视化面板我用的是终端字符画把队列变化过程动态打出来效果比干巴巴的数字好太多。需要提醒的是选模拟器方案不代表可以忽视真实内核的知识。实验报告里一定要写清楚“本模拟器如何映射到真实内核的调度流程”比如模拟器中的“当前运行进程”对应真实内核的current指针“优先级降级”对应真实内核中交互型进程与CPU型进程的动态区分。把映射关系讲明白老师一眼就知道你是真懂而不是只会调库。2. 先吃透原理调度与同步背后的设计逻辑2.1 多级反馈队列为什么是“集大成者”多级反馈队列不是凭空设计出来的它是对前几种经典调度算法缺点的折中。先来先服务FCFS实现简单但对短作业不友好一个长作业堵在前面后面所有短作业的平均等待时间都会被拉高短作业优先SJF理论最优但你没法预知每个进程还要跑多久时间片轮转RR对所有进程一视同仁交互型进程的响应时间却可能因为时间片过长而变差。MLFQ的聪明之处在于它不预知进程行为而是通过“反馈”来动态调整。它维护多条优先级不同的就绪队列规则通常是这样新进程进入最高优先级队列Q0Q0的时间片最短比如1个时间单位。进程在Q0用完时间片还没执行完降级到Q1Q1的时间片是Q0的两倍。以此类推越低优先级的队列时间片越长。只有高优先级队列为空时才执行低优先级队列。每隔一段时间或每次调度时把所有进程重新提升到最高优先级队列防止低优先级进程饥饿。这套规则在真实Linux中并不完全等价Linux用的是CFS完全公平调度但在教学层面是理解“动态优先级”的最佳模型。我写代码的时候发现一个容易忽略的点老化机制规则5不是可选的如果没有它一个长时间运行的CPU密集型进程可能永远得不到CPU实验结果会明显异常。我的做法是设置一个全局的“老化计时器”每10个时间单位触发一次把所有队列中的进程全部移到Q0然后重新参与调度。2.2 生产者消费者的信号量模型为什么是“三个”生产者消费者的经典版本有两个角色的线程和一个固定大小的缓冲区理论上只需要两个信号量一个表示空槽位数一个表示满槽位数。但为了确保对缓冲区本身的互斥访问还需要一个互斥锁信号量初值为1。所以一共是三个信号量这个数量不要随意减少——在实践中很多人试图把空槽位信号量和互斥锁合并成一个结果就会出现两个生产者同时写入缓冲区的竞态问题。信号量P/V操作的正确顺序也很关键。生产者必须先P(空槽位)再P(互斥锁)消费者必须先P(满槽位)再P(互斥锁)。如果把P(互斥锁)放在最前面缓冲区满时生产者会持锁等待空槽位而消费者又因为拿不到锁无法消费于是死锁。这个顺序问题在实验报告里是必考考点建议用文字把死锁场景描述清楚老师很看重这个。我还做了个小扩展把生产者消费者的缓冲区大小设置成与MLFQ最高优先级队列的长度一致比如8这样它既是同步问题的缓冲区又像极了真实系统中“高优先级队列满时新进程先去哪里等待”的问题——这种跨模块的类比在答辩时能加分。3. 代码实现从数据结构到完整模拟器3.1 数据结构设计PCB和就绪队列怎么定义我用的语言是C主要因为它既有面向对象的封装能力又能直接操作指针非常贴合“模拟操作系统内部数据结构”的感觉。定义如下struct PCB { int pid; // 进程ID int arrive_time; // 到达时间 int total_time; // 总共需要的CPU时间 int remaining_time; // 剩余CPU时间 int priority; // 当前所在队列索引0最高 int wait_time; // 累计等待时间 int finish_time; // 完成时间 std::string status; // READY, RUNNING, FINISHED, BLOCKED }; // 就绪队列组vector索引越大优先级越低 std::vectorstd::queuePCB* ready_queues;这里有个重要的工程细节队列中存的是指针而不是对象副本。原因很简单——一个进程在调度过程中会反复进出队列如果存对象副本每次入队出队都要拷贝整个结构体而且指针不变的情况下你可以在任意位置直接修改remaining_time等字段不需要回写。如果存副本改完还得重新入队麻烦且容易漏。时间片长度我用了一个数组来定义方便调参// 每个优先级队列对应的时间片长度 int time_slice[3] {1, 2, 4}; // Q01, Q12, Q24这个设计对应“低优先级队列时间片更长”的经典策略。你完全可以把时间片改成{2,4,8}或者{1,3,5}调度结果的差异可以在实验报告里作为参数分析的一部分。3.2 调度器核心流程一个循环走完所有时间片调度器主体的思路很直接模拟一个全局时钟每个时间单位我把它当作一个“tick”检查一次所有进程的状态然后从最高优先级的非空队列中取出一个进程运行一个时间片。void simulate() { int current_time 0; int running_pid -1; int time_in_slice 0; while (finished_count process_count) { // 1. 新进程到达放入Q0 for (auto p : processes) { if (p.arrive_time current_time) { ready_queues[0].push(p); p.status READY; } } // 2. 老化每10个tick把所有进程提升到Q0 if (current_time % AGING_PERIOD 0 current_time 0) { boost_all_to_q0(); } // 3. 如果当前进程未结束且时间片未用完继续运行 if (running_pid ! -1) { PCB* running find_pcb(running_pid); running-remaining_time--; time_in_slice; if (running-remaining_time 0) { running-finish_time current_time 1; running-status FINISHED; finished_count; running_pid -1; time_in_slice 0; } else if (time_in_slice time_slice[running-priority]) { // 时间片用完降级或放回队尾 demote_or_enqueue(running); running_pid -1; time_in_slice 0; } } // 4. 选择一个新进程运行 if (running_pid -1) { running_pid pick_next_process(); if (running_pid ! -1) { time_in_slice 0; } } current_time; } }这段代码有两点需要注意。第一点是finish_time为什么是current_time 1而不是current_time因为我在一个tick开始时就先执行了remaining_time--进程在第n个tick消耗了最后一个时间片它的完成时刻应该是n1这在计算周转时间时非常关键差一个单位会导致所有统计指标都偏小。第二点是demote_or_enqueue的逻辑如果进程当前在Q0或Q1降级到下一队列如果在最低队列Q2不再降级直接放回Q2队尾继续用Q2的时间片轮转。这个“最低队列不退让”的设计让算法确保不会出现无限循环。3.3 同步部分实现三个信号量 两个线程同步部分我用了C的std::thread和std::counting_semaphoreC20这样不需要额外引入POSIX库就能在跨平台环境下编译。std::counting_semaphore empty_slots(BUFFER_SIZE); std::counting_semaphore full_slots(0); std::mutex buffer_lock; // 或者用二元信号量模拟互斥锁 void producer(int id) { while (true) { int item produce_item(); empty_slots.acquire(); buffer_lock.lock(); buffer[write_pos] item; write_pos (write_pos 1) % BUFFER_SIZE; std::cout Producer id produced item std::endl; buffer_lock.unlock(); full_slots.release(); std::this_thread::sleep_for(std::chrono::milliseconds(200)); } } void consumer(int id) { while (true) { full_slots.acquire(); buffer_lock.lock(); int item buffer[read_pos]; read_pos (read_pos 1) % BUFFER_SIZE; std::cout Consumer id consumed item std::endl; buffer_lock.unlock(); empty_slots.release(); consume_item(item); std::this_thread::sleep_for(std::chrono::milliseconds(400)); } }有个容易被忽略的细节在打印日志时std::cout本身在多线程环境下也需要加锁否则两条输出会交错在一起。我直接用buffer_lock来保护打印虽然让互斥锁的临界区变大了但对于实验来说完全可接受还可以在实验报告里讨论“为什么打印也需要互斥”。如果你用的编译器版本不支持C20的counting_semaphore也可以用POSIX的sem_tsem_wait/sem_post逻辑完全一样只是API名不同。3.4 实验数据设计让随机性可控为了让实验结果可复现我没有用随机数生成进程到达时间而是写死了一组有代表性的进程数据PID到达时间所需CPU时间106213321445552这组数据包含了短进程P3、P5、中长进程P2、P4和一个长进程P1能明显看出MLFQ对短进程的响应优势。跑完之后我再补充一组随机生成的数据用来展示算法在不同负载下的稳定性。写报告时固定数据和随机数据一起呈现比单纯一组随机结果更有说服力。4. 实验结果与参数分析4.1 运行结果从日志中看到调度过程跑完程序后我打印了每个进程的完整时间线。下面是我固定数据的部分输出简化[Tick 0] P1 到达进入 Q0 [Tick 1] P1 在 Q0 运行剩余 5P2 到达进入 Q0 [Tick 2] P1 在 Q0 用满时间片降级到 Q1切换到 P2 [Tick 3] P2 在 Q0 运行剩余 2P3 到达进入 Q0 [Tick 4] P2 在 Q0 用满时间片降级到 Q1切换到 P3 [Tick 5] P3 在 Q0 运行剩余 0完工 ...从日志里能直观看到几个关键行为P3短作业到达后只需要1个时间片它在Q0直接跑完周转时间极短这体现了MLFQ对短作业的快速响应。P1长作业在Q0跑完1个时间片后降级到Q1随后又降级到Q2体现了“CPU密集型进程逐渐失宠”的反馈机制。由于老化机制低优先级队列中的P1在后期被提升回Q0避免了饥饿。计算下来的统计结果是平均周转时间 (65385)/5 5.4平均等待时间 (02233)/5 2.0。作为对比我同样实现了FCFS和RRFCFS的平均周转时间是6.6RR时间片2的是6.2MLFQ在这组数据上优势明显。这个对比结果建议实验报告里一定要放它是“算法效果”最直观的证明。4.2 参数扰动时间片和老化周期怎么影响结果我额外做了两组参数实验一组把时间片改为{2,4,8}另一组把老化周期从10改为20。结果是时间片加大后短作业P3、P5的平均响应时间变差但长作业P1的周转时间变小因为它在Q0能跑更长时间才被降级减少了下队列切换的次数老化周期拉长后Q2中的P1等待时间明显增加但整体公平性下降。这说明MLFQ的参数需要针对工作负载调优没有“万能参数”。这部分分析放在实验报告里属于“加分项”的深度内容一般同学只贴实验结果你贴了参数影响分析老师会觉得你做了额外思考。5. 常见问题与避坑记录5.1 死循环进程永远跑不完我第一次跑程序时发现循环一直不结束排查发现是最低优先级的demote_or_enqueue实现写错了——我把降级逻辑写成了“无论当前在哪一级都升到下一级”导致进程在Q2和Q0之间反复横跳。正确逻辑是只在Q0、Q1时降级到了最低队列Q2就原地放回队尾。另一个常见死循环原因是老化机制的boost_all_to_q0遍历队列时把正在运行的进程也移走了导致running_pid对应的进程不在任何队列中后续调度找不到它。解决办法是在提升操作中跳过running_pid或者先记录再统一处理。5.2 信号量死锁顺序错了就是死锁生产者消费者的死锁排查比较隐蔽因为程序表现为“卡住不动”而不是崩溃。我当时用了一个简单方法在每个线程的关键操作前后打印一条日志比如“Producer 1 trying to acquire empty_slots”“Producer 1 acquired empty_slots”。如果发现某个线程停在acquire之前另一线程也停在acquire之前就基本能断定是顺序问题。死锁的本质是循环等待你把那个循环画出来一眼就能看到是谁在等谁。5.3 “claude.exe无法运行”这类可执行文件兼容问题这个热词虽然看着和实验本身无关但实验过程中我还真遇到过类似的“可执行文件不是有效的应用程序”提示。原因是在Windows上编译时生成了32位可执行文件放到64位环境跑时报这个错或者反过来说交叉编译时架构不匹配。解决办法是在编译命令里明确指定平台比如用g -m64强制生成64位程序或者在项目配置里检查目标平台。还有一个常见情况是编译机器和运行机器操作系统版本差异过大比如在Win10上编译的程序放到Win11上跑虽然大多数情况没问题但涉及特定API时可能抛兼容性错误。实验室电脑环境五花八门写实验报告之前最好先在目标机器上重新编译一次。5.4 队列状态可视化调试和答辩的利器我花了大概半小时写了一个print_queues()函数在每个tick结束时把所有队列的进程号打印成类似下面的格式[Q0] - 3 [Q1] - 1 2 [Q2] - 4这个输出简直是调试神器——进程调度对错的判断不再靠猜而是直接看队列变化是否符合预期。比如P3在Q0跑完消失、P1从Q0降到Q1都能从逐tick的输出里确认。到了答辩时这个动态输出的截图可以直接放进PPT比一堆干巴巴的数字表格生动得多。5.5 实验报告与答辩的准备心得最后说点实验之外的事。操作系统实验四的报告不要只贴代码和结果务必包含题目需求分析、算法流程图手画或工具画都行、关键数据结构说明、核心代码讲解、运行结果与对比分析、遇到的问题与解决方案。答辩时老师最爱问的问题有三个一是“你这个模拟器和真实操作系统的调度有什么区别”二是“为什么用这几个信号量能不能少用一个”三是“如果进程数量翻十倍你的算法性能会怎样”。提前把这三个问题的答案想清楚答辩基本不会慌。我自己在准备时画了一张完整的流程图把进程从到达、入队、运行、降级、老化到完成的整个生命周期串起来写报告的时候对着流程图讲逻辑非常顺。强烈建议你也画一张哪怕是用PPT里最简单的方框和箭头效果也远好于纯文字。本文还有配套的精品资源点击获取