操作系统实验课：进程调度模拟从入门到精通

1. 操作系统实验课到底在折腾什么1.1 从“背概念”到“真动手”的认知转变很多人对操作系统这门课的印象停留在“背概念”进程、线程、死锁、虚拟内存、文件系统考试前突击两天考完就还给老师。但操作系统实验课完全是另一回事——它逼着你把这些抽象概念变成能跑起来的代码。你不再是被动接受“进程调度有先来先服务、短作业优先、时间片轮转”这些结论而是要亲手实现一个调度器看着不同算法下进程的周转时间、等待时间、响应时间真实地变化。这个专题的核心目标很明确把操作系统实验课里最基础、也最容易让人懵圈的第一类实验——进程管理与调度模拟——从头到尾讲透。适合谁看适合刚接触操作系统实验、对着实验指导书不知道从哪下手的同学也适合已经写过一版但跑出来结果不对劲、想搞清楚每一步到底在干什么的人。我当年第一次做这个实验的时候对着“PCB”“时间片”“上下文切换”这些词发愣后来踩了不少坑才把整个流程理顺。这篇内容就是把我踩过的坑、想明白的道理、以及那些实验指导书上不会写的细节全部摊开来聊。1.2 实验课和理论课的根本区别理论课上老师讲“进程是资源分配的基本单位”你点头记下。实验课上你要定义一个结构体来表示进程控制块里面放进程ID、状态、优先级、已运行时间、还需运行时间、等待时间、指向父进程的指针……然后你要写代码去操作这个结构体让它从“就绪”变成“运行”再变成“阻塞”最后“终止”。这个过程里你会遇到很多理论课上不会提的问题进程ID怎么分配时间片用完了怎么处理多个进程同时就绪时按什么顺序排队这些问题的答案不是唯一的但每一种选择都会影响最终结果。我个人的体会是操作系统实验课真正锻炼的是系统思维你要同时考虑数据结构的设计、算法的实现、以及最终输出结果的正确性。这三者环环相扣任何一个环节出问题跑出来的结果就是错的。而且这种错误往往不是语法错误编译器不会报错你得自己对着输出结果一行一行分析才能找到逻辑漏洞。1.3 专题一在整个实验课里的位置专题一通常对应“进程调度”或“进程管理”模块是整个操作系统实验课的地基。后面的内存管理、文件系统、设备管理实验都会用到专题一里建立的进程模型和调度框架。如果专题一没搞扎实后面做页面置换算法模拟的时候你连“进程”这个对象都定义不清楚更别提给它分配内存页了。所以我的建议是专题一不要图快不要想着抄一份代码交差。花时间把调度算法的每一个步骤都理解透把代码的每一个函数都写清楚注释后面你会感谢现在的自己。我见过太多人专题一糊弄过去到专题二做银行家算法的时候完全不知道进程和资源怎么关联只能回头重做。2. 进程调度模拟的核心设计思路2.1 为什么选择“模拟”而不是“真实”操作系统实验课里的进程调度实验绝大多数学校采用的都是模拟实现而不是真的去写一个内核调度器。原因很简单真实的内核调度涉及硬件中断、时钟芯片、特权级切换、内存保护等底层机制在用户态下根本没法直接操作。而且真实环境里进程的创建和销毁涉及大量系统调用调试起来极其困难。模拟实现的好处是你可以把注意力集中在调度算法本身而不用操心底层硬件细节。你用C语言或者Python定义一个进程结构体用一个循环来模拟时间流逝每个时间单位检查一次是否需要切换进程。这样整个调度过程完全在你的掌控之中想打印什么信息就打印什么信息想在哪一步暂停就在哪一步暂停。注意模拟实现虽然简化了底层细节但调度算法的逻辑必须和真实系统保持一致。不能因为“反正是模拟”就随便简化算法步骤否则实验就失去了意义。2.2 进程控制块的设计取舍进程控制块是调度模拟的核心数据结构。设计得好后面写调度逻辑顺风顺水设计得不好写到一半发现缺字段回头改结构体所有相关代码都要跟着改。我建议一开始就把字段设计完整宁可多留几个暂时用不上的字段也不要后面临时加。一个典型的PCB至少需要这些字段字段名类型用途说明pidint进程唯一标识通常从1开始递增stateenum进程状态就绪、运行、阻塞、终止priorityint优先级数值越小优先级越高或反之看约定arrive_timeint进程到达就绪队列的时间need_timeint进程总共需要运行的时间run_timeint进程已经运行的时间wait_timeint进程在就绪队列中等待的总时间start_timeint进程第一次被调度执行的时间finish_timeint进程完成的时间time_sliceint当前时间片剩余量时间片轮转用这里有几个设计细节值得展开说。arrive_time和need_time是输入数据通常由实验指导书给出或者你自己随机生成。run_time和wait_time是运行时累加的每次调度循环都要更新。start_time和finish_time用于计算周转时间和带权周转时间。关于priority不同教材的约定不一样。有的教材规定数值越大优先级越高有的规定数值越小优先级越高。这个一定要在代码开头用注释写清楚否则后面写比较逻辑的时候极容易搞反。我就犯过这个错误按照“数值小优先级高”写的比较函数但输入数据是按“数值大优先级高”生成的结果跑出来的调度顺序完全不对排查了半天才发现是约定不一致。2.3 时间推进模型的选择调度模拟的核心是一个时间推进循环。常见的有两种模型离散事件驱动和固定时间步长。离散事件驱动是指只在“有事件发生”的时间点推进时间比如进程到达、进程完成、时间片用完。这种模型效率高但实现起来复杂需要维护一个事件队列。固定时间步长是指每次循环时间加1检查当前时刻有没有新进程到达、当前运行进程是否完成、时间片是否用完。这种模型实现简单逻辑清晰适合初学者。缺点是如果时间单位很小、进程运行时间很长循环次数会很多但在这个实验的规模下完全不是问题。我推荐用固定时间步长因为它的执行过程和真实操作系统的时钟中断非常相似——每个时钟滴答操作系统就检查一次是否需要调度。这样你写出来的代码逻辑和真实系统是对应的理解起来更直观。2.4 调度算法的选择与组合专题一通常要求实现至少两种调度算法常见组合是先来先服务按到达时间排队非抢占式短作业优先按需要运行时间排序非抢占式时间片轮转按到达时间排队每个进程运行一个时间片抢占式优先级调度按优先级排序可以是抢占式或非抢占式高响应比优先综合等待时间和运行时间计算响应比我建议至少实现FCFS、SJF和RR三种。FCFS最简单用来验证基本框架SJF用来理解“非抢占式调度”和“排序”的关系RR用来理解“抢占式调度”和“时间片”的概念。这三种覆盖了调度算法的基本分类后面的优先级调度和HRRN只是在排序键上做文章。提示不要一开始就想着把所有算法都实现。先把FCFS跑通确保进程状态转换、时间统计、结果输出都正确然后再加SJF和RR。每加一个算法只改调度选择部分的逻辑其他部分保持不变。这样出问题的时候容易定位。3. 核心细节解析与实操要点3.1 进程状态转换的完整逻辑进程状态转换是调度模拟的骨架。一个进程从创建到终止会经历就绪、运行、阻塞、终止等状态。在专题一的调度模拟里通常简化掉阻塞状态因为没有I/O操作只保留就绪、运行、终止三个状态。状态转换的触发条件就绪→运行调度器选中该进程运行→就绪时间片用完RR或被更高优先级进程抢占抢占式优先级运行→终止进程运行时间达到需要时间新进程→就绪进程到达时间等于当前时间每次状态转换都要更新相应的统计信息。比如从运行变成就绪时要累加已运行时间从就绪变成运行时要记录开始时间如果是第一次运行从运行变成终止时要记录完成时间。这里有一个容易忽略的细节等待时间的累加。进程在就绪队列里每等待一个时间单位wait_time就要加1。这个累加应该发生在每个时间步长的末尾对所有处于就绪状态的进程执行。我见过有人在进程被调度时才更新等待时间结果漏掉了那些一直在等待但还没被调度的进程。3.2 时间片轮转的边界条件处理时间片轮转是专题一里最容易出bug的算法。核心逻辑是每个进程被调度后最多运行一个时间片的时间如果时间片用完还没完成就放回就绪队列末尾调度下一个进程。边界条件一进程在时间片内完成。比如时间片是4进程还需要运行2个时间单位那么它运行2个单位后完成剩余的时间片不会分配给其他进程而是直接进入下一次调度。边界条件二新进程到达与时间片用完同时发生。比如当前时间片用完的时刻正好有一个新进程到达。这时候应该先把当前进程放回就绪队列再把新进程加入就绪队列然后从就绪队列头部取下一个进程。顺序不能乱否则就绪队列的顺序会出错。边界条件三就绪队列为空。如果当前没有就绪进程但还有进程没到达时间直接推进到下一个进程到达的时刻。如果所有进程都完成了循环结束。边界条件四多个进程同时到达。按进程ID顺序加入就绪队列保证结果可复现。注意时间片大小的选择会影响调度结果。时间片太大RR退化成FCFS时间片太小上下文切换开销占比过高。在模拟实验里时间片通常取1到4个时间单位具体看实验指导书的要求。3.3 周转时间和带权周转时间的计算周转时间 完成时间 - 到达时间。它衡量的是一个进程从提交到完成总共花了多长时间。带权周转时间 周转时间 / 实际运行时间。它衡量的是进程在系统里停留的时间相对于它实际需要运行的时间的倍数。带权周转时间越接近1说明进程等待的时间越少。这两个指标是评价调度算法优劣的核心依据。FCFS的平均周转时间通常较长因为长作业先到会阻塞后面的短作业。SJF的平均周转时间最短但可能导致长作业饥饿。RR的响应时间较好但周转时间不一定最优。计算的时候要注意实际运行时间就是need_time不是run_time。因为run_time在调度过程中是动态变化的而need_time是进程的固有属性。3.4 输出格式的规范化实验指导书通常对输出格式有明确要求。常见的输出包括调度顺序每次调度时打印当前运行的进程ID和时间区间进程信息表每个进程的到达时间、需要时间、开始时间、完成时间、周转时间、带权周转时间统计汇总平均周转时间、平均带权周转时间输出格式不规范是很多同学被扣分的原因。比如要求保留两位小数你输出了一位要求按进程ID排序你按完成时间排序了。这些细节看似不重要但助教批改的时候一眼就能看出来。我建议在代码里把输出部分单独写成一个函数所有格式化逻辑集中管理。这样调整格式的时候只需要改一个地方不用满代码找printf。4. 实操过程与核心环节实现4.1 数据结构定义与初始化先定义进程结构体和状态枚举。用C语言举例typedef enum { STATE_READY, STATE_RUNNING, STATE_TERMINATED } ProcessState; typedef struct { int pid; ProcessState state; int priority; int arrive_time; int need_time; int run_time; int wait_time; int start_time; int finish_time; int time_slice; } PCB;初始化的时候把所有进程的state设为STATE_READYrun_time、wait_time设为0start_time和finish_time设为-1表示尚未设置。time_slice根据算法设置FCFS和SJF不需要时间片RR需要。输入数据可以硬编码在数组里也可以从文件读取。我建议硬编码因为实验数据通常就几个进程硬编码更直观也方便调试。等框架跑通了再改成文件读取也不迟。4.2 先来先服务调度的实现FCFS的逻辑最简单每次从就绪队列里取到达时间最早的进程运行直到它完成。void fcfs(PCB processes[], int n) { int current_time 0; int completed 0; int running_pid -1; while (completed n) { // 检查是否有新进程到达 for (int i 0; i n; i) { if (processes[i].arrive_time current_time processes[i].state STATE_READY) { // 加入就绪队列这里用数组模拟实际可以用链表 } } // 如果没有正在运行的进程从就绪队列取一个 if (running_pid -1) { // 选择到达时间最早的进程 // 设置running_pid更新state为RUNNING // 如果是第一次运行记录start_time } // 运行一个时间单位 if (running_pid ! -1) { processes[running_pid].run_time; current_time; // 检查是否完成 if (processes[running_pid].run_time processes[running_pid].need_time) { processes[running_pid].state STATE_TERMINATED; processes[running_pid].finish_time current_time; completed; running_pid -1; } } else { current_time; } // 更新所有就绪进程的等待时间 for (int i 0; i n; i) { if (processes[i].state STATE_READY) { processes[i].wait_time; } } } }这段代码里有一个关键点等待时间的更新放在时间推进之后。因为当前时间单位里就绪进程确实在等待所以等待时间要加1。如果放在时间推进之前就会多算一个单位。4.3 短作业优先调度的实现SJF和FCFS的区别只在选择进程的逻辑FCFS选到达时间最早的SJF选需要运行时间最短的。其他部分完全一样。// 在就绪队列中选择need_time最小的进程 int select_sjf(PCB processes[], int n, int current_time) { int selected -1; int min_need 999999; for (int i 0; i n; i) { if (processes[i].state STATE_READY processes[i].arrive_time current_time) { if (processes[i].need_time min_need) { min_need processes[i].need_time; selected i; } } } return selected; }注意条件arrive_time current_time只有已经到达的进程才能被调度。如果所有已到达的进程都完成了但还有进程没到达就绪队列为空时间直接推进。SJF有一个变种叫最短剩余时间优先是抢占式的。区别在于每当有新进程到达时比较新进程的need_time和当前运行进程的剩余时间如果新进程更短就抢占。专题一通常只要求非抢占式SJF但了解SRTF有助于理解抢占式调度的概念。4.4 时间片轮转调度的实现RR的实现比FCFS和SJF复杂因为涉及时间片管理和就绪队列的循环使用。void rr(PCB processes[], int n, int time_slice) { int current_time 0; int completed 0; int running_pid -1; int slice_used 0; int queue[MAX]; // 就绪队列存进程索引 int front 0, rear 0; while (completed n) { // 新到达的进程加入队尾 for (int i 0; i n; i) { if (processes[i].arrive_time current_time processes[i].state STATE_READY) { queue[rear] i; } } // 如果没有运行进程从队头取一个 if (running_pid -1 front rear) { running_pid queue[front]; processes[running_pid].state STATE_RUNNING; slice_used 0; if (processes[running_pid].start_time -1) { processes[running_pid].start_time current_time; } } // 运行一个时间单位 if (running_pid ! -1) { processes[running_pid].run_time; slice_used; current_time; // 检查是否完成 if (processes[running_pid].run_time processes[running_pid].need_time) { processes[running_pid].state STATE_TERMINATED; processes[running_pid].finish_time current_time; completed; running_pid -1; } // 检查时间片是否用完 else if (slice_used time_slice) { processes[running_pid].state STATE_READY; queue[rear] running_pid; running_pid -1; } } else { current_time; } // 更新等待时间 for (int i 0; i n; i) { if (processes[i].state STATE_READY) { processes[i].wait_time; } } } }RR里最容易出错的地方是就绪队列的管理。新到达的进程要加入队尾时间片用完的进程也要加入队尾。如果顺序搞反了调度结果就会不对。另外当running_pid为-1且队列为空时时间推进但不能更新等待时间因为没有就绪进程这个逻辑要单独处理。4.5 结果输出与统计计算所有算法跑完之后统一输出结果。我习惯把输出分成三部分调度过程、进程信息表、统计汇总。调度过程就是每次切换进程时打印一行比如[时间 0-4] 进程 P1 运行 [时间 4-6] 进程 P2 运行 [时间 6-8] 进程 P1 运行进程信息表用表格形式输出PID到达时间需要时间开始时间完成时间周转时间带权周转时间P108012121.50P2144871.75统计汇总计算平均值double avg_turnaround 0; double avg_weighted 0; for (int i 0; i n; i) { int turnaround processes[i].finish_time - processes[i].arrive_time; double weighted (double)turnaround / processes[i].need_time; avg_turnaround turnaround; avg_weighted weighted; } avg_turnaround / n; avg_weighted / n; printf(平均周转时间: %.2f\n, avg_turnaround); printf(平均带权周转时间: %.2f\n, avg_weighted);提示带权周转时间要用浮点数计算不要用整数除法。整数除法会截断小数部分导致结果偏差很大。我见过有人用turnaround / need_time两个int相除结果全是整数统计出来的平均值完全不对。5. 常见问题与排查技巧实录5.1 调度顺序不对的排查思路调度顺序不对是最常见的问题。排查的时候按以下顺序检查第一检查进程到达时间的处理。新进程到达时是否正确地加入了就绪队列加入的时机是在时间推进之前还是之后如果加入时机不对可能导致进程晚一个时间单位才被调度。第二检查选择逻辑。FCFS选到达时间最早的SJF选需要时间最短的RR从队头取。确认比较条件写对了特别是和的区别。如果有多个进程满足条件按什么规则打破平局通常是按进程ID。第三检查时间片逻辑。RR里时间片用完的进程是否正确放回队尾如果放回队头就变成了FCFS如果忘记放回进程就丢了。第四打印中间状态。在每个时间单位打印就绪队列的内容、当前运行进程、各进程的run_time和wait_time。这样能直观地看到每一步的状态快速定位问题出在哪一步。5.2 统计结果偏差的常见原因统计结果偏差通常有这几个原因等待时间多算或少算检查等待时间的更新时机。应该在每个时间单位结束时对所有就绪进程加1。如果放在时间单位开始时会多算一个单位。开始时间记录错误进程第一次被调度时记录start_time。如果每次被调度都记录start_time会被覆盖成最后一次调度的时间。完成时间记录错误进程完成时记录finish_time。注意是在run_time达到need_time的那个时间单位结束时记录不是开始时。带权周转时间用了整数除法前面提过必须用浮点数。平均值计算时漏除了进程数累加之后忘记除以n。5.3 就绪队列管理的典型bug就绪队列用数组模拟的时候front和rear的管理容易出问题。常见bug包括队列溢出数组大小不够rear超出边界。解决办法是把数组开大一点或者用循环队列。队列为空时仍取元素front rear时还执行front导致取到无效数据。每次取元素前必须检查front rear。新进程到达时队列已满如果队列满了新进程无法加入。在实验规模下不太可能但养成检查的习惯。时间片用完的进程加入队列时顺序错误应该加入队尾不是队头。5.4 常见问题速查表问题现象可能原因排查方法调度顺序与预期不符选择逻辑错误或到达时间处理错误打印每步的就绪队列和选择结果平均周转时间偏大等待时间多算或完成时间记录错误检查wait_time和finish_time的更新时机带权周转时间全是整数整数除法改用浮点数计算进程丢失就绪队列管理错误检查front/rear的更新逻辑时间片轮转退化成FCFS时间片用完的进程放回队头改为放回队尾新进程晚一个单位被调度到达时间处理时机错误在时间推进前处理新到达进程5.5 实操心得与避坑建议做了这么多遍调度模拟实验我总结了几条实验指导书上不会写的经验第一先用小数据验证。不要一上来就用十几个进程跑。先用3个进程、运行时间都是个位数的小数据手动推演一遍预期结果然后跑代码对比。小数据下容易定位问题大数据下错误会被掩盖。第二把调度过程打印出来。不要只输出最终结果。在每个时间单位打印当前时间、运行进程、就绪队列、各进程状态。这样即使结果不对你也能看到是从哪一步开始不对的。第三不同算法共用框架。FCFS、SJF、RR的框架是一样的区别只在选择逻辑和时间片处理。把公共部分抽成函数算法部分单独实现。这样加新算法的时候只需要写选择逻辑不用重写整个循环。第四注意边界条件。就绪队列为空、所有进程同时到达、进程在时间片最后时刻完成、新进程到达与时间片用完同时发生——这些边界条件最容易出bug写代码的时候要专门考虑。第五结果要可复现。相同输入必须得到相同输出。如果有随机因素比如随机生成进程要固定随机种子。否则每次跑结果不一样没法验证正确性。第六注释要写清楚。特别是状态转换的条件、时间更新的时机、队列操作的逻辑。过两天回头看代码没有注释你根本想不起来当时为什么这么写。5.6 从专题一延伸到后续实验专题一跑通之后后面的实验就有了基础。专题二做内存管理的时候可以把专题一的进程结构体扩展一下加上页表指针、内存起始地址等字段。专题三做文件系统的时候可以把进程和打开文件表关联起来。专题四做设备管理的时候可以把进程和I/O请求队列关联起来。所以专题一里定义的PCB结构体不要写得太死。留一些扩展字段或者用结构体嵌套的方式组织方便后面加功能。我当年就是PCB写得太简单后面做内存管理的时候不得不重构浪费了不少时间。另外专题一里实现的调度框架后面做银行家算法的时候可以复用。银行家算法需要检查系统是否处于安全状态本质上也是一个状态推进的过程和调度模拟的循环结构很像。把专题一的框架理解透后面很多实验都能套用。最后说一个我踩过的坑不要用全局变量。我一开始图省事把进程数组、当前时间、就绪队列都定义成全局变量结果调试的时候发现一个算法的修改影响了另一个算法的结果。后来改成把状态封装在结构体里通过参数传递问题就消失了。全局变量在单算法实验里可能没问题但多算法对比的时候一定会出乱子。