操作系统实验做到进程调度这块基本上是本科阶段最接近“操作系统到底在干嘛”的一次体验。我手头这个教学内核已经迭代到了1.2版实验一共有两个目标一是把进程调度的完整过程分析清楚二是写两个进程让它们严格交替输出不能多打也不能错序。这篇文章就是这次实验的完整记录从调度器怎么设计、上下文切换怎么实现到同步方案怎么选、坑都踩在哪儿一并交代清楚。懂行的人看到“1.2版内核”就明白这肯定不是拿来跑生产的它是一个极简教学内核能在QEMU里启动、能创建进程、能响应时钟中断就够用了。真正难的地方不是写代码而是把调度过程中那种“看起来同时发生、实际上一个时刻只有一个CPU在做一件事”的感觉挖出来再用同步手段让两个进程的输出顺序被控制住。看完这篇文章你应该能画出这条从时钟中断到上下文切换再到用户进程输出的完整链路。1. 实验背景与整体设计思路1.1 版本1.2内核的定位与结构我刚拿到实验说明的时候第一反应是版本1.2是什么鬼后来翻了实验环境才搞清楚它是我手上这个教学内核的第二个正式版本在1.0的基础上补了三样东西时间片轮转调度器、信号量、还有一套能用的串口输出驱动。整颗内核很精简大概是三层结构最底层是中断和时钟管理。定时器芯片产生时钟中断频率我设的是100Hz也就是每10ms中断一次。中间层是进程管理与调度。每个进程有一个进程控制块PCB就绪进程挂在一个双向链表上调度器在时钟中断或进程主动让出CPU时被触发。最上层是系统调用接口目前只有几个fork、exit、sleep、sem_init、sem_waitP操作、sem_postV操作。可以这样看1.2版内核其实就是一个“最小可用的多进程骨架”没有虚拟内存没有文件系统没有复杂的I/O。内存管理用的是最简单的方式——静态划分每个进程固定分一块内存区域作为它的地址空间进程表最多支持16个进程。这些限制在写实验时反而是好事因为你可以把注意力完全集中在调度和同步这两件事上不会被内存映射、缺页异常这些额外机制分散精力。1.2 为什么把调度分析和交替输出放在一起做这个实验给的题目是两部分我一开始觉得是两个独立任务后来发现设计得很聪明。交替输出看起来是用户态问题实际上是对内核能力的一次综合验收要跑两个进程必须验证PCB和就绪队列正确要让两个进程在串口上稳定交替必须保证调度器能在合适时机切入切出要控制顺序必须有能用的信号量原语而且P/V操作必须是原子的。反过来如果实验中输出偶尔乱一下问题到底出在调度上还是同步上也正好是对分析能力的考验。换一个角度说用现成的操作系统比如Linux做交替输出只需要知道信号量怎么用就行但在这颗自己写的内核上做信号量本身是不是原子的、关中断的时机对不对、切换瞬间栈指针保存得对不对这些问题全部暴露在台面上。这就是为什么实验要求同时“分析调度过程”和“实现交替输出”本质上是让你把“用户态现象”和“内核态机制”对应起来。理解了这个对应关系后面调试才不会像无头苍蝇。2. 进程调度过程的核心机制2.1 进程控制块PCB与就绪队列的设计调度过程里最重要的数据结构就是PCB我用的定义如下typedef struct pcb { uint32_t pid; uint32_t state; // 0: READY, 1: RUNNING, 2: BLOCKED, 3: ZOMBIE uint32_t stack; // 内核栈栈顶指针切换时保存 esp uint32_t context[16]; // 通用寄存器快照eax ~ edi, eip, eflags 等 uint32_t ticks_left; // 剩余时间片单位是 tick uint32_t priority; struct list_head run_list; // 挂入就绪队列的链表节点 // 信号量等待队列等其他字段省略 } pcb_t;注意到这里有一个细节context数组只用于保存通用寄存器栈指针单独放了一个字段stack。因为切换的时候需要把esp设置到目标进程的内核栈顶端而esp本身无法通过普通寄存器保存指令直接搞定所以单独留一个字段。PCB的context在我这个版本里是用内联汇编保存的核心代码就是把当前寄存器压入当前进程的内核栈再把目标进程保存在PCB里的那一份弹出来。就绪队列用双向链表而不是简单的数组。原因很简单进程会频繁地进出队列双向链表插入和删除都是O(1)而且可以很方便地在队尾追加、从队头取出。队列里还维护了一个当前运行进程的指针因为调度器要判断“是不是就该轮到当前进程继续跑”。2.2 时间片轮转怎么运作1.2版内核用的是最简单的轮转调度Round-Robin每个进程默认分4个tick也就是40毫秒。时钟中断每10ms触发一次中断处理程序里做三件事更新系统时间给当前进程的ticks_left减1如果ticks_left减到0就把当前进程重新放到就绪队列尾部然后调用schedule()。这里最需要理解的一点是进程不会自己发现自己时间片用完它是在“被动”的情况下被时钟打断的。想象一下你正在专心写作业闹钟每10分钟响一次响了4次后被人强制从书桌前赶到队伍末尾重新排队——这就是时间片轮转。进程可能正执行到任意一条指令时钟中断一来CPU就跳到中断处理程序里去当前这条用户态指令的执行就暂停了等下次轮到它再继续。时间片的取值也是有讲究的。太短会导致频繁切换系统开销大太长会让交互响应变差。40毫秒对于这个极简内核来说是一个平衡点既能保证两个进程看起来在“同时”往前推进又不会因为切换太频繁拖慢整体运行速度。实验里你也可以把时间片改成1个tick试试输出会更加“碎片化”但调度次数会明显上升。2.3 调度器的一次完整执行流程调度器的核心函数长这样伪代码风格void schedule(void) { // 进入调度器前必须已经关中断或者在这里关中断 disable_irq(); if (current-state RUNNING) { current-state READY; list_add_tail(current-run_list, ready_queue); } // 取出就绪队列队头进程 next list_first_entry(ready_queue, pcb_t, run_list); next-state RUNNING; // 切换上下文 switch_to(current, next); current next; enable_irq(); }switch_to是上下文切换的关键它要完成四步把当前进程的寄存器压栈、更新current进程的PCB里的stack字段、加载next进程的栈顶、弹栈恢复next进程的寄存器。在我这个版本里用x86汇编写比较直接switch_to: ; 1. 保存当前进程现场 pusha pushf movl %esp, %eax movl %eax, (%ebx) ; 把当前 esp 保存到 current-stack ; 2. 切换到 next 的内核栈 movl (%edx), %esp ; 从 next-stack 加载 esp ; 3. 恢复 next 进程现场 popf popa ret需要强调这一步必须关中断或者保证切换过程不会被时钟中断打断。为什么因为如果你在保存到一半的时候又来了一个时钟中断中断处理程序会再次尝试保存现场栈指针和寄存器就会乱套。更稳妥的做法是在进入schedule之前就disable_irq等切换完成、恢复现场后再enable_irq。一次完整的调度过程可以总结成五步时钟中断触发 - 保存被中断进程的现场到内核栈 - 调度器选择下一个进程 - switch_to切换栈和寄存器 - 返回到用户态继续执行下一步。搞懂这五步整个进程调度的“骨架”就清晰了。剩下的细节无非是中断入口要压哪些数据、ret/iret怎么选择以及如何保证ready_queue不出脏数据。3. 严格交替输出的三种实现方案3.1 用信号量实现严格交替拿到“两个进程严格交替输出”这个要求很多同学第一反应是让一个进程先输出然后打印完之后调用sleep/yield让出CPU等另一个进程输出完再让回来。但这个思路在抢占式调度下有一个致命问题你完全控制不了时钟中断什么时候到来。你以为A输出完yield后B会马上输出实际可能是A输出完、又连续输出好几次才轮到B。因此要严格交替必须有内核级的同步机制。我选择的方案是用两个信号量。核心思路是A和B各自拥有一个“钥匙”但是钥匙在对方手里必须拿到钥匙才能输出。初始时让A的钥匙可用B的钥匙不可用那么第一个一定是A输出A输出完释放B的钥匙然后自己等A的钥匙B拿到B的钥匙后输出再释放A的钥匙自己等B的钥匙。代码如下sem_t sem_a 1; // 控制进程A输出的信号量 sem_t sem_b 0; // 控制进程B输出的信号量 void process_a(void) { while (1) { sem_wait(sem_a); serial_print(A); sem_post(sem_b); } } void process_b(void) { while (1) { sem_wait(sem_b); serial_print(B); sem_post(sem_a); } }这段代码的效果是输出序列永远都是ABABABAB……不会出现AA或者BB。两个进程像在打乒乓球一样A发球B接住还给AA再发。只要信号量的P/V操作是原子的那么两个进程就不可能同时进入临界区。实现原子性的最直接方法就是关中断进入sem_wait之前关闭中断修改信号量计数和等待队列后再重新打开。1.2版内核就是这么实现的因为单核CPU下关中断是保证互斥最可靠的手段。3.2 用yield加标志位实现还有人可能想到不等信号量用一个全局变量flag来表示“现在该谁输出”。这种方法在理论上也能实现严格交替但实现起来并不比信号量简单。核心代码如下volatile int flag 0; // 0表示A1表示B void process_a(void) { while (1) { while (flag ! 0) { yield(); } serial_print(A); flag 1; } } void process_b(void) { while (1) { while (flag ! 1) { yield(); } serial_print(B); flag 0; } }这个方案里每个进程都要不断地检查flag如果不是自己的回合就主动让出CPU。表面上看起来可行但它有两个明显问题。第一是忙等待如果两个进程的优先级不同或者调度器不公平A可能一直检查flag而B迟迟不被调度结果就是A一直空转浪费CPU。第二是原子性问题如果flag的检查和修改之间有一个窗口期理论上可能被打断。实测下来这个方案能跑通但只要把时间片改小到1个tick输出顺序偶尔就会乱一次原因还是出在“flag修改后到yield之间”的窗口期。3.3 方案对比与选型建议除了上面两种还有人会用“单进程直接串行输出”虽然结果对但完全没达到实验考察多进程调度的目的跳过不提。我把两种能跑的方案做个对比方便选型对比项信号量方案yield标志位方案实现难度需要内核支持P/V原语只需yield系统调用是否存在忙等待否等待进程被阻塞是循环检查flag对调度器的依赖低P/V操作为内核原语高依赖yield及时让出扩展性好可推广到多进程/生产者消费者差进程多了很难维护稳定性高原子性由关中断保证较低窗口期有竞态风险实验结论很清楚在1.2版这个自制内核里信号量方案更干净、更稳也更像一个“工程师会做的事”。yield方案虽然代码少但它本质上是把同步问题推给了用户态CPU资源被大量浪费在轮询上。如果你想往深处学还可以试试把信号量换成自旋锁或者直接在调度器里做严格轮转每种方案都有各自适合的场景。4. 实测记录与问题排查4.1 实测输出结果对比我先跑了一个没加任何同步的版本两个进程各自循环输出100个字符。串口抓到的前几行AABBABABBAABABABABBAAAABBBBBAAB...完全随机中间有AA也有BB甚至有一长串A连续出现。这个现象可以反过来验证一个判断调度器的时间片是40ms但输出恰好是轻量操作几十毫秒内进程能输出好多次所以一个进程连续输出多个字符是正常的。把信号量方案加上之后同样输出100对字符串口结果变成ABABABABABABABABABABABABABABAB...严格按照ABABABAB的节奏来一个不多一个不少。我在循环里加了一个计数器跑完1000轮之后计数为2000A出现了1000次B出现了1000次顺序完全正确。从串口电平的角度看A和B的打印间隔也基本是均匀的每个字符之间的时间差大约稳定在几百微秒到几毫秒内波动这个波动主要来自调度器本身的时间片和对串口设备的连续访问。4.2 经典问题速查表实验过程中我踩了一些坑也帮同学排查了几个问题整理成表格遇到类似情况可以直接对号入座现象可能原因排查思路解决办法输出序列既是ABAB有时却出现在A之后连续打出两个Asem_wait的实现没有关中断P操作被时钟中断打断检查sem_wait入口是否使用disable_irq/enable_irq在sem_wait/sem_post里包一层关中断代码跑起来后整个系统卡死信号量顺序写反A等B释放、B等A释放死锁打印每个进程当前等待的信号量ID确认初始值是sem_a1、sem_b0检查release的是对方等待的信号量输出看起来是交替的但用工具抓到的顺序偶发错乱串口驱动或打印缓冲导致顺序被掩盖改用串口直出并关闭行缓冲不要用带缓冲的printf用printk或serial_write直接写寄存器一个进程占了绝大部分CPU另一个几乎饿死调度器没有保证轮转公平或进程在等待时仍占用CPU打印两个进程被调度次数检查当前进程睡眠时是否被放入阻塞队列而不是继续占着就绪队列把时间片改成1个tick后输出明显碎片化调度过于频繁上下文切换开销变大统计每次调度耗时调整时钟频率减少无关中断日志其中死锁那个案例最有代表性。我先写的是A等待sem_a、B等待sem_b结果两个进程都在等对方释放CPU空转到天荒地老。当时我把sem_a和sem_b的初值都设为1想着“两个都可以输出不就有交替”结果根本不是两个进程同时进入临界区输出乱成一团。后来改成sem_a1、sem_b0才稳定。这个过程的教训是信号量初值代表“初始的可并发数量”不是“你想让哪个进程先跑就给哪个信号量设1”它背后对应的是资源的许可数。4.3 调试内核的小技巧最后聊几个在实际调试中特别好用的土办法。第一个是串口日志分级。开发阶段把调度器的每条路径都打印出来比如“enter schedule”、“switch to pid2”、“pid1 ticks_left0”运行一段时间后用脚本统计这些日志就能直观看到每个进程被调度了多少次、每次状态变化是什么。等跑通后再把日志关掉否则打印本身会产生海量中断开销实验数据会失真。第二个技巧是“只留一个变量做观察”。调试交替输出的时候把注意力放在一个核心标志上这个时刻到底是哪个进程拿到了信号量、哪个进程被阻塞。把这两个数字打出来顺序对不对一目了然。我曾经为了查一个偶发错序在sem_wait入口处加了一行临时打印打印当前pid和信号量的值跑了十分钟终于抓到一次异常原因是sem_post里的等待队列唤醒逻辑在极端情况下把同一个进程唤醒了两次。定位之后把唤醒改成“只唤醒队首一个”问题消失。第三个技巧是用GDB加QEMU的remote调试。在自己写的内核里GDB可以设置断点在schedule()上然后单步看寄存器的变化。不过要小心单步跟踪会破坏时间片时序因为你在一个进程里单步时钟中断还是会一直触发。我的经验是先用日志分析整体行为再用GDB看局部切换细节两者配合效率最高。5. 一些后续扩展与个人经验实验收尾之后我又顺手做了几件事算是给后来者一点扩展思路。我把时间片从固定4个tick改成了动态计算每个进程的优先级是1到10优先级数字越小越优先高优先级进程每次分到的时间片更短但由于它在就绪队列里排得更靠前整体响应更快。实测下来高优先级进程的响应确实变快了但低优先级进程在极端情况下会偶发饥饿需要额外加一个“老化”机制才能避免。这套玩法已经超出实验要求但对理解多级反馈队列很有帮助。我个人在实验里最大的体会是调度器的本质不是“算法多高级”而是“我怎么能在任意一条指令处安全地把CPU交出去”。只要把这个保存-切换-恢复的循环想清楚信号量、自旋锁、多核调度其实都是在这个循环上套一层保护机制。最后再分享一个写这种实验的建议不要一上来就写双进程交替输出先建一个进程确认它能反复循环打印再加第二个进程不加同步看它俩怎么随机交错最后再加信号量做控制。每步都验证清楚了再往前走看起来慢其实是节省时间最多的路径。如果你也在这颗1.2版内核上踩过类似的坑或者试过别的交替方案欢迎交流。