操作系统实验做到3.3的时候要求把Linux 1.2内核的进程调度过程完整分析一遍再写代码实现两个进程的严格交替输出。刚看到题目我第一反应是为什么不直接分析最新内核的调度器但做完这轮实验才明白版本1.2这个选择非常巧妙——调度器核心代码只有几十行没有CFS红黑树没有组调度没有调度域和负载均衡一个下午就能从入口看到上下文切换的底部。这篇文章把我实验里完整做过的三件事记录了下来把1.2内核在QEMU里跑起来、在schedule()函数里插桩观察每次调度决策、最后用两种方式实现两个进程的交替输出并对比两者差异。操作系统课程正在做类似实验的同学或者想从源码角度真正看懂进程调度原理的开发者都可以拿这篇作为参照。1. 为什么这个实验要挑1.2内核而不是新内核1.1 现代内核调度器对初学者并不友好现在主线内核的调度器已经进化到了一个相当复杂的程度。CFS完全公平调度器用红黑树维护进程的虚拟运行时间每个调度实体带一堆负载跟踪信息RT调度器和deadline调度器分别服务实时任务此外还有组调度、带宽控制、NUMA感知、EAS能耗调度。哪怕只是想读懂__schedule()和pick_next_task_fair()也要先弄清楚vruntime、cfs_rq、sched_entity、RCU锁保护这些概念。一个操作系统实验如果要求分析进程调度过程学生很容易被这些细节淹没最后只能对着源码念注释。1.2内核的调度模型则直白得多。每个进程对应全局task数组里的一个task_struct里面有三个关键字段直接参与调度state表示进程状态counter表示当前剩余时间片priority表示进程优先级。调度器做的事情本质上就是遍历这个数组找出一个剩余时间片最多的就绪进程然后切过去运行。整个过程没有任何花哨的数据结构一段几十行的C代码就把调度的核心逻辑讲透了。1.2 小内核反而把概念讲得更完整选择1.2内核并不意味着阉割版恰恰相反调度器必须回答的几个核心问题一个都不少什么时候切换——调度时机包括时钟中断、进程阻塞、系统调用返回检查切换到谁——选择算法基于counter和priority的决策怎么切换——上下文切换保存当前进程现场、恢复目标进程现场这些问题在现代内核里同样存在只是被层层封装掩盖了。1.2内核把每个问题都摆在明面上非常适合建立心智模型。这个实验的具体目标也围绕这三件事展开先搭一个能运行1.2内核的环境然后给schedule()函数加日志观察两次进程切换之间的决策依据最后写两个进程实现严格交替输出验证仅靠调度器能做到什么、做不到什么。2. 让1.2内核在QEMU里动起来2.1 编译环境的兼容性处理Linux 1.2内核发布于1995年直接拿2025年的gcc编译大概率会卡在兼容性问题上。我实测遇到的主要有这几类老代码里大量void*隐式转换新版gcc默认警告升级会把编译中断内嵌汇编的某些约束写法在新版gcc里不再被接受老汇编语法在最新binutils里也会报错。这些问题属于机械性修改报一个改一个就行但来回折腾比较烦人。我实际用的方案是gcc-8加上少量代码修正。Makefile里需要加上-fno-stack-protector -fno-PIE -marchi386把现代编译器默认开启但老内核根本不需要的防御特性关掉。如果你不想耗在这上面另一个务实路线是直接找网上的linux-1.2可编译补丁包打上补丁再编。命令本身就很简单wget https://cdn.kernel.org/pub/linux/kernel/v1.2/linux-1.2.0.tar.gz tar xf linux-1.2.0.tar.gz cd linux make zImage -j4 CCgcc-8编出来的内核在arch/i386/boot/zImage后面QEMU会用到。2.2 做一块极简根文件系统内核能启动还不够实验程序得跑在用户态。为了让事情尽量简单我没有去折腾完整发行版的根文件系统而是写了一个极简init程序直接把它静态编译后放进磁盘镜像。这个init进程做的事很纯粹fork出两个子进程每个子进程循环输出一个字符然后等待子进程结束。下面是第一个版本不加任何同步用来观察纯时间片轮转下的输出形态#include sys/types.h #include sys/wait.h #include unistd.h #include stdio.h int main(void) { int i; printf(init: kernel alive, pid%d\n, getpid()); if (fork() 0) { for (i 0; i 200; i) write(1, A, 1); _exit(0); } if (fork() 0) { for (i 0; i 200; i) write(1, B, 1); _exit(0); } for (i 0; i 2; i) wait(NULL); printf(\ninit: done\n); for (;;) pause(); return 0; }编译并制作镜像gcc-8 -static -o init init.c dd if/dev/zero ofrootfs.img bs1k count4096 mkfs.ext2 rootfs.img mkdir /tmp/rootfs mount rootfs.img /tmp/rootfs cp init /tmp/rootfs/init umount /tmp/rootfs注意我把这个静态程序命名为init放在文件系统根目录而不是/sbin/init这类标准路径。1.2内核启动时会直接执行根文件系统上的/init少掉很多不必要的初始化逻辑。2.3 QEMU启动参数与观测方式启动命令是实验里最常用的那套qemu-system-i386 -m 64 -kernel linux/arch/i386/boot/zImage \ -hda rootfs.img -append root/dev/hda1 consolettyS0 \ -nographic -no-reboot -cpu qemu32这里有两个参数值得解释。-nographic把串口接到当前终端内核的printk日志和用户态程序往/dev/console的输出都会直接出现在屏幕上这是观察调度行为的主要入口。-cpu qemu32则是为了规避老内核与现代CPU特性之间的兼容性问题指定一个保守的CPU型号能减少很多莫名其妙的启动故障。3. schedule()源码级拆解调度决策到底怎么发生的3.1 调度时机全景在给schedule()插桩之前得先搞清楚它会在哪些路径上被调用。1.2内核的调度发生点主要有三个时钟中断路径系统每个tick1.2内核默认HZ100即10ms都会对当前进程的counter做减一操作。如果减到0就把need_resched标志置位。中断返回时ret_from_sys_call检查这个标志一旦发现就调用schedule()。进程主动睡眠进程在内核态调用read、wait、sleep这类会阻塞的操作时内核会直接把进程状态改成TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE然后调用schedule()切换到其他进程。进程唤醒被信号或事件唤醒的进程只是被重新放回就绪队列并不会立即抢占正在运行的进程。真正执行切换要等当前进程让出CPU。这里有一个很重要的特性1.2内核不是一个完全可抢占内核。进程在内核态执行时除非主动调用schedule()或进入阻塞否则不会被打断。这给实验分析带来了极大的便利——调度点是相对固定的不像现代内核那样在内核态任意位置都可能被抢占排查起来路径很清晰。3.2 schedule()核心循环逐段拆解我把1.2内核kernel/sched.c里schedule()的核心逻辑整理成了下面这段去掉了与教学无关的细节保留的每一行都对应真实存在的机制void schedule(void) { int c, i, next; struct task_struct **p; /* 1. 唤醒收到信号的TASK_INTERRUPTIBLE进程 */ for (p LAST_TASK; p FIRST_TASK; --p) { if (!*p) continue; if ((*p)-state TASK_INTERRUPTIBLE ((*p)-signal ~(*p)-blocked)) (*p)-state TASK_RUNNING; } /* 2. 主循环选择counter最大的就绪进程 */ while (1) { c -1; next 0; for (i 0; i NR_TASKS; i) { if (!task[i]) continue; if (task[i]-state TASK_RUNNING task[i]-counter c) { c task[i]-counter; next i; } } if (c) break; /* 3. 所有进程counter都为0统一补充 */ for (i 0; i NR_TASKS; i) if (task[i]) task[i]-counter (task[i]-counter 1) task[i]-priority; } /* 4. 切换到选中的进程 */ switch_to(task[next]); }第一段的作用很有意思。TASK_INTERRUPTIBLE状态表示进程正在等待某个事件但它可以被信号唤醒。如果有信号到来调度器会把它的状态改回TASK_RUNNING让它参与本轮调度竞争。而TASK_UNINTERRUPTIBLE状态的进程即使收到信号也不会被唤醒实验里如果看到进程长时间处于D状态多半就是在内核里等待某种不可中断的资源。第二段是调度器的主循环逻辑非常朴素遍历整个task数组找到状态为TASK_RUNNING且counter最大的进程。这里没有按照入队顺序也没有复杂的权重计算谁的时间片剩余多就选谁。c的初始值是-1即使所有就绪进程的counter都为0循环结束后c仍然等于0就会进入第三段。第三段的补充公式是整段代码最值得琢磨的地方counter (counter 1) priority而不是简单重置为priority。这个右移操作隐含了睡眠补偿的思想。举个例子进程A的priority是15它一直阻塞等待I/Ocounter从来没有被消耗过还是15进程B是纯CPU进程一直在跑counter已经被减到0。此时两个进程都需要补充时间片A的新counter变为15 / 2 15 22B的新counter变为0 / 2 15 15。A的优先级在重算后反而比B高了。这个设计的本意是照顾那些经常睡眠的I/O密集进程避免它们被纯计算进程饿死。理解了这个公式后面第5章出现的输出偶尔冒出AA现象也就有了答案。3.3 上下文切换到底做了什么选中next之后真正执行切换动作的是switch_to这个宏。1.2内核没有使用x86 CPU的硬件任务切换也就是通过ljmp到TSS段而是走软件切换路线。大致流程是把当前进程的通用寄存器压入当前进程的内核栈再把当前进程的内核栈指针写回它自己的task_struct然后加载目标进程的内核栈指针把它之前压栈的寄存器全部弹出来CPU就接着目标进程的现场继续执行了。用生活化的比喻来说每个进程就像一个正在写作业的学生作业本寄存器、栈指针摊在桌上。schedule()要做的事情是先把A同学的作业本原封不动收进他的书包保存现场再把B同学的书包打开、把作业本摊到桌上恢复现场让B同学接着写。硬件任务切换相当于连书桌一起换代价高得多所以Linux很早就放弃了那条路线。3.4 插桩观察让调度决策原形毕露源码读得再多不如亲眼看一次调度决策过程。我给schedule()加了一行printk在每轮主循环选出进程之后打印信息。为了保证日志可读我只在选中的进程名与实验程序相关时才输出否则系统里那些内核线程会瞬间把日志淹没。/* 在 if (c) break; 之后追加 */ printk([sched] pick pid%d name%s counter%d\n, task[next]-pid, task[next]-comm, c);重新编译启动之后终端上会刷出类似下面的日志[sched] pick pid2 nameinit counter15 [sched] pick pid3 nameinit counter15 [sched] pick pid4 nameinit counter15这里pid3和pid4就是init fork出来的两个子进程。它们名字还叫init因为fork继承父进程的comm字段。从日志可以清楚看到调度器每次选中的进程counter都是当前就绪进程里最大的而且只有当某个进程counter降为0后调度才会转向另一个进程。这为后面分析交替输出打下了直接的观测基础。4. 两个进程交替输出从纯轮转到管道令牌的完整实验4.1 严格交替到底难在哪里先明确一下严格交替的定义。进程A和进程B各自负责输出一个字符用户态最终看到的结果必须是ABABABAB...或者BABABABA...连续出现两个相同字符就算失败。这个要求非常苛刻因为这意味着每次某个进程输出一个字符之后必须立刻让另一个进程获得CPU继续输出两者必须严格互相对齐。先跑一下第2章那个不加任何同步的init程序看看纯调度器能做到什么程度。实际输出是类似这样的形态AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB也可能交错出现几次但整体上总是大段大段地连续输出。原因很简单在没有阻塞的情况下一个进程会一直占用CPU直到时间片耗尽。1.2内核里priority默认是15也就是15个tick每个tick 10ms一个时间片长达150ms。在150ms里哪怕每次write系统调用都有固定开销也足够打印出几千个字符了。所以分时调度只保证宏观上的公平不保证微观上的交替。4.2 用管道作为令牌实现严格交替要严格交替就必须引入同步原语让进程主动放弃CPU。我采用的方案是用两个管道传递一个令牌。持有令牌的进程有资格输出输出完通过管道把令牌交给对方然后自己在管道上阻塞等待令牌回来。管道初始状态是A管道的读端有一个字节的令牌。进程A先阻塞在p2上等令牌进程B阻塞在p1上等令牌。初始时把令牌放入p1所以进程B会先拿到令牌吗这里取决于读写端设置。我实际采用的是下面这种设计创建p1和p2两个管道初始令牌放入p1。进程A负责从p2读令牌、向p1写令牌进程B负责从p1读令牌、向p2写令牌。这样令牌始终在两个进程之间单向流转绝不会出现自己读到自己写的数据。#include sys/types.h #include sys/wait.h #include unistd.h #include stdio.h #include stdlib.h int main(void) { int p1[2], p2[2]; char token T; pid_t a, b; pipe(p1); pipe(p2); if (write(p1[1], token, 1) ! 1) { perror(write); exit(1); } if ((a fork()) 0) { close(p1[0]); close(p2[1]); for (int i 0; i 50; i) { read(p2[0], token, 1); write(1, A, 1); fflush(stdout); write(p1[1], token, 1); } _exit(0); } if ((b fork()) 0) { close(p1[1]); close(p2[0]); for (int i 0; i 50; i) { read(p1[0], token, 1); write(1, B, 1); fflush(stdout); write(p2[1], token, 1); } _exit(0); } close(p1[0]); close(p1[1]); close(p2[0]); close(p2[1]); waitpid(a, NULL, 0); waitpid(b, NULL, 0); printf(\ndone\n); return 0; }这段代码有几个细节需要解释。首先是关闭多余的文件描述符。每个进程只应该持有自己需要的管道端否则会出现自己写的数据被自己读走或者对方写入的数据被自己这边多余的读端卡住这类经典问题。其次是read在没有数据时的行为当前进程会进入TASK_INTERRUPTIBLE睡眠状态调度器立刻切换到另一个进程。这正是我们需要的主动让出CPU机制。运行结果会稳定输出ABABABABABABABABABABABABABABABABABABABABABAB done严格交替实现了。背后的原因也不难理解进程A输出一个字符后会在write(p1[1], ...)之后立即尝试read(p2[0], ...)。这时候管道里没有令牌read阻塞进程A主动让出CPU进程B被调度执行从p1读到令牌、输出字符然后在read(p1[0], ...)处再次阻塞。如此往复每个进程每次只运行到输出一个字符并交还令牌的位置自然就形成了严格的交替序列。4.3 对比两种方式下的调度行为把两种实验的printk日志放到一起差异非常明显。纯时间片轮转版本中schedule()调用间隔大约稳定在15个tick也就是150ms左右管道令牌版本中schedule()调用的频率显著变高因为这些调用不是来自时钟中断而是来自read主动睡眠。有趣的是管道版本中schedule()打印出来的prev进程状态几乎总是TASK_INTERRUPTIBLE而纯轮转版本中prev进程状态始终是TASK_RUNNING。这个状态差异本身就是同步原语影响调度行为的最直观证据实验版本输出形态切换触发原因prev进程状态能否严格交替纯时间片轮转A...A B...B时钟中断、时间片耗尽TASK_RUNNING否管道令牌同步ABABAB...read调用主动睡眠TASK_INTERRUPTIBLE是从实验角度可以得出一个结论调度器本身不关心进程在用户态打印了什么它只认进程状态和counter同步机制的作用是让进程在指定位置主动进入睡眠从而把调度点安排到我们期望的顺序上。这个结论也是在进程同步与调度之间建立连接的关键。5. 踩坑记录老内核实验里的四个典型案例5.1 编译旧内核的连环坑编译1.2内核最容易卡住的地方不是C代码本身而是新旧编译器之间的代沟。我遇到的报错包括隐式函数声明在默认-Werror下变成错误、老式内嵌汇编操作数约束不被新汇编器接受、某些内核头文件使用了已被废弃的关键字。解决思路是用gcc-8或更早版本编译然后逐条处理报错。另外Makefile里一定要手动加-fno-stack-protector否则现代编译器生成的栈保护代码会访问老内核不存在的gs段机制运行阶段才崩溃排查起来非常痛苦。5.2 printk刷屏导致假死机给schedule()插桩打印日志之后启动阶段会疯狂刷屏。QEMU的-nographic模式把串口输出直接映射到终端但串口速度有限日志生成速度远超输出速度现象就是看起来整个系统卡住了。实际上内核还在运行只是大部分时间都花在排队打印日志上。解决办法是给打印条件加过滤。我只在目标进程被选中时才打印if (task[next]-pid 3 || task[next]-pid 4) printk([sched] pick pid%d counter%d\n, task[next]-pid, c);这样既保留了完整的调度决策信息又不会让无关进程的日志淹没观测窗口。5.3 stdio缓冲让交替输出失真管道令牌版本刚跑起来的时候我一度以为代码写错了因为输出仍然是一段段地出现而不是严格的ABABAB。排查了半天才发现问题不在同步逻辑而在printf的缓冲行为。printf输出到stdout默认情况下如果输出目标是终端就是行缓冲如果被重定向到文件或者管道就是全缓冲。实验里输出被串口捕获实际上是全缓冲缓冲区攒够一批才刷出去看起来自然就不是交替了。解决办法是直接使用write(1, buf, 1)每个字符都是独立的系统调用立刻离开用户态缓冲区。这也是为什么我在第2章的init程序里就直接用了write而不是printf。5.4 睡眠补偿导致的counter虚高现象管道令牌版本运行时间长了之后日志里偶尔能看到短暂的连续两个A或两个B。这个现象一开始让我很困惑因为从逻辑上令牌机制应该保证严格交替。后来看schedule()日志才意识到问题出在第3章讲过的睡眠补偿公式上。假设进程A在某一轮中因为某种原因多阻塞了一段时间比如B进程被时钟中断打断还没来得及从管道取令牌A的counter在这段睡眠期间没有被消耗数值一直维持在较高水平。唤醒后重算时间片A的新counter可能比B高出不少。调度器按counter大小选进程A自然就获得了更长的一轮运行时间。在这轮里A可能连续两次拿到令牌并输出两次A中间虽然B也被唤醒了但B因为counter不够高没有被立即调度。这个现象不是bug是sleep bonus机制的副作用它再次验证了counter在调度决策中的决定性作用。实验里如果想降低这种虚高效应可以把两个进程的priority都调低比如改成5。重算后的补偿比例会变小交替的稳定性会好一些。但完全消除也不太容易因为这正是1.2内核调度器的固有行为。这轮实验做下来给我留下最深印象的不是schedule()函数本身而是调度决策的数据来源这件事。进程状态、counter、priority这些用户态完全看不到的内核字段最终都会以运行速度、响应速度、输出顺序的方式体现在应用层。建议后面做这个实验的同学务必亲手跑一遍管道令牌版本只有亲眼看到调度日志从每150ms一次变成每次read都触发一次才能真正理解同步原语和调度器之间是怎么配合的。老内核虽然代码简单但该讲清楚的道理一个都没少。