操作系统课程的实验做到3.3时题目很有代表性“版本1.2内核的进程调度过程分析”再加上“两个进程的严格交替输出”。前半句要求你钻进内核代码里把调度器怎么选进程、怎么切上下文讲清楚后半句又把你拉回用户态用两个进程在终端上打出 A B A B A B 这样严格交替的输出。这两件事分开看不难放在同一个实验里却正好踩中了操作系统的核心矛盾调度器决定“谁先用 CPU”同步机制决定“谁先输出”。这篇文章把我的实操过程完整拆开包含 v1.2 教学内核的调度源码阅读思路、schedule 和 switch 两条主线的分析以及可复现的 C 语言交替输出实现适合正在做操作系统实验、或者想搞懂早期教学内核调度机制的同学参考。1. 先看清实验这个题目到底要我们做什么1.1 两个任务之间的隐含关系很多同学看到“版本1.2内核的进程调度过程分析”就一头扎进源码看到“两个进程的严格交替输出”又直接去写循环打印结果做完整个人都是懵的。我建议先停下来想清楚两件事之间的关系。“调度过程分析”的目标是理解内核在什么时机、依据什么策略、通过什么动作把 CPU 从一个进程切换到另一个进程。这个结论会直接告诉你一个事实默认的进程调度不会保证两个进程在用户态一次只打印一个字符。时间片通常远大于打印一个字符的耗时所以一个进程拿到 CPU 后完全可能连续输出一串“AAAA”直到时间片耗尽才轮到另一个进程输出“BBBB”。“严格交替输出”则是要在用户态补齐这个缺口。它本质上是一个同步问题两个进程之间需要有一个“轮流”的约束A 打印完必须等 BB 打印完必须等 A谁也不能抢跑。这个约束没法靠 sleep、while 循环、优先级这些“碰运气”的手段解决必须使用内核提供的同步原语比如信号量。换句话说这两个题目是递进关系先研究调度器的行为再基于这个行为设计进程间的协作方式。做实验的时候不要跳过第一部分直接写第二部分因为很多调试问题比如“为什么我的 A 进程一次打印了十几个字符”都能从调度过程里找到答案。1.2 我用到的实验环境与内核版本我们实验用的是课程配套的教学内核内部版本号就是 v1.2。它没有完整 Linux 那样庞大的子系统但保留了最核心的一套机制进程控制块task_struct、就绪队列、时钟中断、schedule 函数、switch_to 宏。这套代码的调度模型非常接近早期 Linux 0.12 的实现用 counter 表示时间片余量用 jiffies 记录系统时钟节拍读懂它对后面理解现代内核的 CFS 也有很大帮助。实验环境方面我是在 Ubuntu 上配合 qemu-system-i386 启动这个教学内核编译工具用 gcc 和对应的交叉链接脚本。源码结构大致是include/linux/sched.h进程控制块的定义、调度相关宏。kernel/sched.cschedule()、sleep_on()、wake_up() 等核心调度函数。kernel/system_call.s系统调用入口、中断返回路径。kernel/exit.c进程退出、wait 相关逻辑。init/main.c内核初始化创建第一个进程。我建议你把sched.h和sched.c单独打印出来先用笔圈出所有和counter、priority、TASK_RUNNING、switch_to相关的代码再开始分析。这个过程大概花半小时但比直接看别人的总结有用得多。2. 版本1.2内核的进程调度过程从schedule()到switch_to2.1 进程控制块里藏了调度需要的一切调度不是凭空发生的每个进程必须有一个“身份证”内核才能知道它现在是什么状态、还能跑多久、下次该给它多少时间片。这个身份证就是 task_struct。在 v1.2 教学内核里task_struct 的简化定义大概是这样的struct task_struct { long state; // 进程状态-1 不可运行0 可运行/正在运行0 可中断等待 long counter; // 当前时间片剩余量每次时钟中断减 1 long priority; // 静态优先级counter 耗尽后用它重置 long signal; // 待处理信号位图 int pid; // 进程号 int pgrp; // 进程组 int tty_grp; // 所属终端 struct task_struct *next; // 指向下一个进程 // ... 还有现场保存区、内核栈指针、TSS 段等 };这几个字段里调度器最关心的就是state和counter。state决定进程是否可以被调度只有state 0即TASK_RUNNING的进程才会进入调度器的“候选人名单”。counter的含义比较特殊它既是剩余时间片也是动态优先级值越大被选中的概率越大。这里有一个初学者容易忽略的点counter在每个时钟中断里都会被减 1而不是等到时间片用完才一次性归零。所以调度器看到的counter是不断变化的“余量”。当它减到 0说明当前进程这个时间片用完了调度器必须考虑换成别人。2.2 schedule() 的选人逻辑counter 既是时间片也是优先级v1.2 教学内核的调度主函数schedule()代码量不大但信息密度很高。核心逻辑可以概括成一句话在所有state 0的进程里选counter最大的那个进程去执行。下面是简化后的 schedule()void schedule(void) { int i, next, c; struct task_struct **p; while (1) { c -1; next 0; i NR_TASKS; p task[NR_TASKS]; // 扫描所有进程找出 counter 最大且处于可运行状态的进程 while (--i) { if (!*--p) continue; if ((*p)-state TASK_RUNNING (*p)-counter c) c (*p)-counter, next i; } if (c) // 如果找到 counter 0 的进程就跳出循环去切换 break; // 如果所有可运行进程的 counter 都是 0就重新给所有进程填充时间片 for (p task[NR_TASKS]; --i; ) if (*p) (*p)-counter ((*p)-counter 1) (*p)-priority; } switch_to(next); }注意那个while (1)循环。第一次扫描如果找到counter 0的可运行进程直接break去切换如果所有可运行进程的counter都是 0说明大家都把时间片用完了这时进入重新填充阶段。填充公式是counter counter / 2 priority;这个公式很巧妙。它没有把所有进程的 counter 直接设成一个固定值而是把旧的 counter 折半再加上静态优先级。这样做的效果是之前运行得比较多的进程即使重新获得时间片counter 也不会立刻超过那些等了很多轮、旧 counter 已经很小甚至归零的进程。换句话说系统会倾向于把 CPU 让给“饿得比较久”的进程降低某些进程一直抢占 CPU 的风险。这也是为什么这个调度器看起来是“时间片轮转”实际上又带有动态优先级味道的原因。理解这一点之后你再去看输出为什么不是严格交替就很好理解了调度器只保证“counter 大的人先跑”不保证“A 和 B 一定一人一次”。2.3 switch_to一场寄存器的接力赛选出下一个进程后真正的切换动作发生在switch_to(next)里。这是整个调度过程最有“操作系统感”的部分。切换的本质是保存当前进程的 CPU 现场恢复下一个进程的 CPU 现场。CPU 现场包括通用寄存器、段寄存器、指令指针 EIP、栈指针 ESP以及 EFLAGS 等。在 x86 保护模式下早期内核把这些现场保存在每个进程对应的 TSS 段里并通过一条长跳转指令完成切换。用伪代码描述一下switch_to(next) { 如果 next 当前进程直接返回 保存当前进程的寄存器到 current-tss 把 current next 加载 next-tss 里的寄存器现场 跳到 next 的代码位置继续执行 }这里有一个非常关键的理解点进程切换不是“函数调用”而是“两条执行流的交接”。调用 schedule() 时CPU 还在当前进程的内核栈上运行一旦执行 switch_toCPU 就跳到另一个进程上次被中断的位置后续的代码执行流就变成另一个进程的了。这个“跳”不是普通的函数跳转因为它同时切换了栈所以返回地址、局部变量全部都会切换成下一个进程自己的现场。v1.2 教学内核还依赖独立的“内核栈 用户栈”结构。用户态被时钟中断打断后硬件会从用户栈切到内核栈并把用户态现场压栈调度器运行时用的就是内核栈。如果切换时只改了执行流没有同步改栈指针那下一个进程一压栈就会把当前进程的栈搞坏。所以 switch_to 里一定同时处理 ESP 和 EIP这是检查和阅读源码时最该盯住的地方。2.4 调度时机在哪里触发进程调度不是 CPU 随便找一个时间点就发生它必须从“当前正在运行的代码路径”主动或被动进入。v1.2 教学内核里进入 schedule() 的主要时机有下面几类。第一类是进程主动让出 CPU。比如进程调用pause()或sleep_on()目的是等待某个事件此时它把自己的 state 改成不可运行然后主动调用 schedule()。这种调度是协作式的进程自己决定不再跑了。第二类是时钟中断驱动。每隔一个时钟节拍定时器中断触发内核进入do_timer()把当前进程的counter减 1。如果减到 0就会设置一个need_resched标志而不是立刻在中断上下文里切走。等中断返回时系统检查need_resched如果被设置才调用 schedule()。这很重要它说明时间片用尽后进程不会在中断处理函数内部瞬间切换而是要等到中断返回路径上才真正切换。如果此时内核正处在某个不能被打断的临界区调度还会继续推迟。第三类是系统调用返回路径。任何系统调用从内核态返回用户态之前都会检查是否需要进行调度这样能保证“刚处理完 I/O 的进程”有机会被重新评估。我把这些时机整理成一张表方便复习触发点触发原因说明进程主动休眠sleep_on/pause进程不再参与调度必须切换时钟中断do_timer递减 counter时间片耗尽设置 need_resched中断/系统调用返回ret_from_sys_call检查 need_resched决定是否切走理解了“什么时候触发调度”再回头看严格交替输出你会发现一个很现实的问题如果只依赖时间片切换那一个时间片内进程可以执行大量指令打印几十上百个字符都很正常。交替输出不能赌调度器恰好每打印一个字符切一次必须另想办法。3. 两个进程严格交替输出从失败到正确3.1 直接写并发输出的结果为什么不对先上一个最“本能”的写法。两个进程一个死循环打印 A一个死循环打印 B/* proc_a.c */ #include stdio.h int main(void) { while (1) printf(A); return 0; }/* proc_b.c */ #include stdio.h int main(void) { while (1) printf(B); return 0; }在 shell 里把两个程序挂到后台运行或者用一个父进程 fork 两个子进程结果大概率是屏幕上先冒出一串“AAA...”再冒出一串“BBB...”也可能中间夹杂着“ABAB”但绝对不是严格的 ABABAB。原因有两层。第一层从调度器角度解释每个进程分到的时间片是毫秒级别而printf(A)这种操作在用户态可能只需要几微秒一个时间片里能跑上千次。除非你刻意把时间片调到非常小否则进程 A 不可能只打印一个 A 就被切走。第二层是printf自己还带缓冲。标准 I/O 库默认情况下输出到终端是行缓冲输出到文件是全缓冲。字符先进入缓冲等缓冲区满或者遇到换行才真正写到底层设备。这就导致你看到的现象可能和程序实际执行顺序不一致甚至 A 进程已经执行了很多次终端上却什么都没显示。所以单纯调整调度器参数或者用 sleep 随机等一等都无法保证严格交替。这里必须上同步机制。3.2 用信号量给两个进程排队信号量是解决这类问题最直接的原语。它的核心是一个计数器加两个原子操作P 操作wait/down把计数器减 1如果小于 0 就阻塞V 操作signal/up把计数器加 1并唤醒正在等待的进程。要实现 ABAB 严格交替可以设置两个信号量sem_A初始值为 1表示允许 A 进程输出一次。sem_B初始值为 0表示 B 进程暂时不能输出。A 进程每次输出前执行P(sem_A)输出后执行V(sem_B)。B 进程每次输出前执行P(sem_B)输出后执行V(sem_A)。这样当 A 第一次执行P(sem_A)时sem_A 从 1 变成 0A 获得输出权输出 A 后V(sem_B)把 sem_B 从 0 变成 1B 被唤醒。B 执行P(sem_B)获得输出权输出 B 后再V(sem_A)把 sem_A 加回 1。于是 A 和 B 就像接力跑一样一个交棒一个接棒任何一方想连续输出第二次都会发现自己手里的信号量已经是 0只能阻塞等待。用生活里的例子理解就是只有一个接力棒棒在谁手里谁才能跑跑完必须交给另一个人。这个机制完全绕开了调度器的“脾气”不管时间片怎么分输出顺序一定是严格按照信号量的发放顺序来的。3.3 完整可运行示例代码在 Linux 用户态下最省事的做法是用 POSIX 有名信号量sem_open。它可以在任意两个不相关的进程之间共享因为我们 fork 出来的子进程能继承父进程打开的信号量描述符所以这里天然合适。我完整的测试代码如下/* alt.c: 两个进程严格交替输出 ABABAB */ #include stdio.h #include stdlib.h #include unistd.h #include fcntl.h #include sys/stat.h #include semaphore.h #include sys/wait.h #define LOOP_NUM 20 int main(void) { sem_t *sA, *sB; pid_t pa, pb; sA sem_open(/sA, O_CREAT, 0644, 1); sB sem_open(/sB, O_CREAT, 0644, 0); if (sA SEM_FAILED || sB SEM_FAILED) { perror(sem_open); exit(1); } pa fork(); if (pa 0) { /* 子进程 A */ for (int i 0; i LOOP_NUM; i) { sem_wait(sA); write(STDOUT_FILENO, A, 1); sem_post(sB); } sem_close(sA); sem_close(sB); _exit(0); } pb fork(); if (pb 0) { /* 子进程 B */ for (int i 0; i LOOP_NUM; i) { sem_wait(sB); write(STDOUT_FILENO, B, 1); sem_post(sA); } sem_close(sA); sem_close(sB); _exit(0); } waitpid(pa, NULL, 0); waitpid(pb, NULL, 0); sem_close(sA); sem_close(sB); sem_unlink(/sA); sem_unlink(/sB); write(STDOUT_FILENO, \n, 1); return 0; }编译命令是gcc -o alt alt.c -pthread运行./alt正常输出是ABABABABABABABABABABABABABABABABABABABAB几个实现细节值得说明。第一不用printf而用write是为了绕过 stdio 缓冲。write是系统调用每调用一次就往终端写一个字节不经过用户态缓冲能保证输出顺序就是程序执行顺序。如果你非要用printf也可以但要在每次输出后加fflush(stdout)否则可能看不到交替效果。第二两个子进程里_exit(0)而不是return 0是为了避免缓冲刷新问题。子进程如果走returnC 运行库会刷新 stdio 缓冲可能多出额外输出_exit直接退出不做缓冲刷新。第三父进程必须waitpid两个子进程都结束后再返回否则终端可能被子进程的输出和 shell 的提示符搅在一起。第四sem_open的名字必须以/开头这是 POSIX 的规定。用完记得sem_unlink否则信号量会一直留在系统里下次运行同名共享对象初值不会被重置。3.4 从调度器层面实现严格交替的另一种做法有些实验或课程设计要求不只是“用户态拼同步”而是“直接改内核调度让两个进程严格交替”。这种情况下信号量当然能做但如果你想体会调度器与同步的关系还可以用另一个思路让进程每次打印一个字符后主动调用sched_yield()。sched_yield()的作用是告诉调度器我当前不着急继续跑你可以把 CPU 让给其他进程。在 v1.2 教学内核里实现它核心就是把自己的状态保持不变直接调用schedule()。两个进程都这样写for (int i 0; i N; i) { write(1, A, 1); sched_yield(); }for (int i 0; i N; i) { write(1, B, 1); sched_yield(); }由于每个进程打印一个字符后立刻交还 CPU调度器只要按照就绪队列顺序切到另一个进程就能做到 ABABAB。这种方案没有“同步”语义完全是协作式地让出 CPU严格性依赖“每次调度必定切到另一个进程”的假设。如果在真实 Linux 上验证效果通常不理想因为内核可能把两个进程放在不同 CPU 上或者调度器认为当前进程的优先级太高切来切去还是它。作为实验课对比验证思路可以不能当通用方案。如果你想把这件事做进内核更“正统”的方法是在内核里维护一个全局令牌比如一个int turn 0。A 进程通过系统调用进来检查turn是不是自己的编号如果是就输出并改成 B 的编号然后唤醒 B如果不是就睡眠等待。这其实就是把信号量机制在核心里重写一遍适合时间比较充裕、想更深入理解同步原语实现的同学。4. 常见问题与排查技巧实录4.1 现象与根因速查表实际操作中我遇到过的现象和原因大概有这么几种整理出来能帮你少走弯路。现象可能原因解决办法输出全是 A完全没有 BB 进程被创建失败或 B 的信号量永远拿不到检查 fork 返回值确认 sem_B 初值是 0V 操作有没有执行输出偶尔出现 AA 或 BB终端缓冲合并了多次 write 的显示把输出重定向到文件再用od -c查看真实字节程序启动后卡住不动信号量初值设置错误导致两个进程都在等对方唤醒检查 sem_open 初值重新编译前先 sem_unlink输出顺序是 BABA不是 ABAB信号量初值给反了把 sA 初值改为 1sB 初值改为 0每次运行结果不一样没有使用同步原语完全依赖调度随机性改用信号量或条件变量qemu 里看不到输出串口或控制台没有正确初始化检查内核启动参数是否设置了 console 设备打印用 printk 测试进程明明只打印一次结果却显示很多字符stdout 缓冲没有 flush用 write或者在 printf 后 fflush(stdout)这里我要特别强调“输出重定向到文件验证”这个技巧。终端显示受各种因素影响看起来像是交替的其实可能不是严格交替用./alt out.txt把输出写到文件再用od -c out.txt查看每个字节才能确定序列是否真的是 ABABAB。之前的慢速终端或串口模拟可能掩盖问题重定向到文件可以暴露最真实的输出顺序。4.2 三个让我反复抓狂的坑第一个坑是printf缓冲。我第一次写交替输出时用了printf(A)程序在终端上等半天没有输出后来又突然一下子冒出一长串。调了很久才发现不是同步逻辑问题而是 stdout 在非终端环境下是全缓冲缓冲区没满就不会真正写到设备。后来我干脆所有调试输出都用write(STDOUT_FILENO, buf, len)彻底绕开 stdio 缓冲。这个习惯现在也一直保留。第二个坑是匿名信号量的共享问题。最开始我想用sem_init(sem, 0, 1)创建一个普通匿名信号量然后 fork。对 Linux 来说fork 后子进程复制了父进程的地址空间但复制出来的那块sem_t内存并不是父子进程共享的同一个对象。子进程 A 对信号量做的修改B 进程完全看不到。所以进程间同步要么用sem_open的有名信号量要么用mmap加pshared1再sem_init。这个知识点看起来基础但只有被坑过一次才会记得牢。第三个坑是修改内核调度器做实验时为了追求“一打印就切换”把 counter 或时钟节拍调得太小结果系统频繁调度屏幕打印巨慢甚至模拟器像死机一样。后来我学乖了先不急着动全局时间片而是在用户态用sched_yield()验证“主动让出”的效果确认链路没问题再考虑改内核。做内核实验一定要遵循“小步快跑”的原则一次只改一个参数改完立刻在快照环境里试。5. 实验之外这套调度机制还能怎么改5.1 把时间片轮转改成多级反馈队列v1.2 教学内核的调度器已经能工作但它有两个明显缺点一是所有进程的优先级调整比较粗糙二是counter的重新分配公式对实时性要求高的进程不够友好。实验做完之后可以尝试把它往多级反馈队列的方向扩展。经典多级反馈队列的要点是系统设置多个就绪队列每个队列的时间片长度不同优先级高的队列时间片更短。新进程先进入最高优先级队列如果在当前队列没有用完时间片就主动让出 CPU说明它是一个 I/O 密集型的交互进程可以保持在当前队列甚至提升优先级如果时间片用完才让出说明它是 CPU 密集型的进程会被降入时间片更长的低优先级队列。放到 v1.2 内核里改动点大概是struct task_struct { // ... int time_slice; // 每个队列不同的时间片长度 int queue_level; // 当前所在队列级别 };调度器扫描时先扫高优先级队列如果非空就不去低优先级队列找。每次时间片耗尽后根据当时进程的行为决定 queue_level 是否改变。这比单纯修改 counter 公式更接近现代内核的做法。5.2 对照真实内核看这段代码的价值读完 v1.2 的调度器再去看现代 Linux 的 CFS完全公平调度器会觉得亲切很多。CFS 不再用固定的时间片和 counter而是维护每个进程的虚拟运行时间 vruntime调度器每次选择 vruntime 最小的进程运行。设计哲学变了但基本问题没变选谁、何时选、怎么切、怎么处理优先级。理解老代码对新代码的价值在于你能抓住调度器设计的四个核心矛盾公平性、响应速度、吞吐量、实现复杂度。v1.2 用 counter 同时表达“时间片余量”和“动态优先级”对教学来说足够直观CFS 用 vruntime 实现全球时间公平工程上更优秀。从老版本出发你更容易看懂新版本为什么要做这些调整而不是被一堆红黑树、调度类、组调度概念劝退。5.3 个人实测心得做这个实验最大的收获不是“我会用信号量了”而是真正理解了调度器能保证什么、不能保证什么。调度器保证的是 CPU 资源的合理分配但不保证进程在用户态的执行序列同步机制保证的是多个进程之间的事件顺序。两者各司其职配合起来才是一个可用的系统。最后分享一个我自己的小习惯改内核代码前先用git init或者直接复制一份原始目录做一个“救生舱”。一旦改崩了几分钟就能恢复到初始状态。做实验时记录下每次修改前后的行为变化写实验报告的时候你会感谢当时多写的那几行注释。