primes (moderate/hard)实验目标primes 是 util 实验里真正把pipefork组合成一条进程流水线的一关难度比 pingpong 高一档。它要我们用并发的方式实现「素数筛」——这是 Unix 管道发明者 Doug McIlroy 提出的经典并发思想不靠任何共享内存只用一串进程 一串管道就把 2~35 里的素数全部筛出来。具体要做的事用pipefork搭起一条进程流水线第一个进程把2~35依次喂进流水线。每遇到一个素数就新建一个进程它从左邻居的管道读、向右邻居的另一个管道写。每个进程的规则都一样从左边读到的第一个数一定是素数打印它然后把后面所有「不是它倍数」的数传给右邻居。因为 xv6 的文件描述符和进程数量都有限流水线喂到35就可以停。官方 lab 里给的正确输出如下prime 2到prime 31共 11 个素数$ primes prime 2 prime 3 prime 5 prime 7 prime 11 prime 13 prime 17 prime 19 prime 23 prime 29 prime 31 $前置知识1. 进程与 fork 基础本关多了一个「递归 进程链」pingpong 里fork()只 fork 一次、父子各干各的primes 里每个进程都会再 fork 一个右邻居形成一条不断变长的进程链。但底层规则没变fork之后子进程拿到父进程文件描述符表的副本指向同一批内核文件对象所以父子能看到同一条管道——这正是左邻居能写、右邻居能读的根基。2. 管道pipe是什么——结合 xv6 手册xv6 handoutChapter 1: PipesA pipe is a small kernel buffer that is exposed to processes as a pair of file descriptors, one for reading and one for writing.pipe§ creates a new pipe, records the read and write file descriptors in p[0] and p[1], and returns 0 or -1.After fork(), the parent and the child have file descriptors referring to the same pipe.If no data is available, a read on a pipe waits for data to be written; … if all file descriptors referring to the write end of a pipe are closed, a read returns end-of-file (0).提炼成要点管道 内核里一小块缓冲区对进程暴露为一对 fdp[0]是读端p[1]是写端。pipe(p)把读/写 fd 分别填进p[0]、p[1]。写入p[1]的数据可以从p[0]读出FIFO 先进先出。fork之后父子持有指向同一管道的 fd因此能通过它通信——这是整条素数筛流水线能跑起来的前提。管道缓冲区大小有限xv6 里PIPESIZE 512字节不过本实验只传几十个 4 字节int缓冲区不是瓶颈。3. 为什么必须 close 不用的端本关是「不关必死」“if all file descriptors referring to the write end of a pipe are closed, a read returns end-of-file (0)”pingpong 只传 1 字节不关写端也未必立刻死锁但 primes 是多进程、多轮、依赖数据结束来收尾的任何一处忘了关掉用不到的写端对端的read就永远等不到 EOF整条流水线直接卡死。而且 xv6 的资源很紧每个进程最多打开 16 个文件描述符kernel/param.h里NOFILE 16全系统最多 64 个进程NPROC 64、全系统最多 100 个打开的文件NFILE 100。流水线每多一个进程都要占 fd泄漏一个写端就可能在对端阻塞泄漏多了还没筛到 35 就先把资源耗光了。所以官方 hint 第一条就是“关掉你用不到的 fd”——本关里这不是好习惯而是能不能跑完的硬条件。4. 本实验的通信模型——Doug McIlroy 的并发素数筛官方 lab 里the picture halfway down this page指向 Russ Cox 的Bell Labs and CSP Threads一文Hoare 把这种写法归功于 Unix 管道发明者 Doug McIlroy。用管道串起一条流水线每个进程只做三件事p get a number from left neighbor print p loop: n get a number from left neighbor if (p does not divide n) send n to right neighbor对应的进程链画出来是这样2,3,4,5,...35 3,5,7,9,...35 5,7,11,13,...35 feeder ────────────────► 筛掉 2 的倍数 ─────────► 筛掉 3 的倍数 ─────────► ... (prime 2) (prime 3) (prime 5)一个生成进程把2, 3, 4, ..., 1000灌进流水线左端第 1 个进程筛掉 2 的倍数、第 2 个筛掉 3 的倍数、第 3 个筛掉 5 的倍数依此类推。关键问题是为什么从左边读到的第一个数一定是素数因为它已经躲过了前面所有进程的筛选——它既不是 2 的倍数、也不是 3 的倍数、也不是 5 的倍数……那它只能是一个新的素数。于是每个进程读第一个数 → 打印 → 用它的倍数往下筛就构成了完整的埃拉托斯特尼筛Sieve of Eratosthenes。实现思路顺着「建初始管道 → 递归地 fork 出进程链 → 每个进程筛一次 → 用-1当 EOF 哨兵 → 逐级wait收尾」的思路main建一条初始管道input_pipefork出一个子进程。父进程关掉读端把2~35写进管道最后写一个-1作为结束哨兵再wait(0)等整条链结束。子进程关掉写端进入sieve(input_pipe)递归。sieve(pleft)里从pleft读第一个数p——它一定是素数打印prime p若读到-1说明前面已经筛完直接exit(0)建新管道prightfork右邻居子进程关掉用不到的端、递归sieve(pright)当前进程继续从pleft读后续数字把「不是p的倍数」的数写进pright读完收到-1后把-1也传给右邻居然后wait(0)等子进程、exit(0)。几个要点用-1这个显式哨兵标记数据结束。为什么需要它因为每个进程在筛选期间必须保持写端打开边读边写下游无法靠所有写端关闭 →read返回 0来判断结束所以用-1显式地在链上一级一级传下去。代码里while (read(...) buf ! -1)同时兼容了read返回 0EOF的情况是双保险。直接写 4 字节int不做 ASCII 格式化官方 hint 也建议这样做代码里write(..., i, sizeof(i))就是这么写的。每个进程都wait自己的子进程这样 main 进程只有在整条流水线含孙进程、曾孙……全部输出并退出之后才退出——这正是官方 hint 里 “wait until the entire pipeline terminates” 的要求。进程是按需创建的不是一开始就建满一条链而是每筛出一个素数才 fork 一个新的右邻居hintcreate the processes in the pipeline only as they are needed。代码实现user/primes.c—— 递归进程链 管道素数筛// primes.c#includekernel/types.h#includekernel/stat.h#includeuser/user.h#defineRD0#defineWR1// 筛选质数的函数, 传入一个管道voidsieve(intpleft[2]){// 传入 pleft 前所在进程就已经关闭了管道 pleft 的写端, 后面无需重复关闭// 读入第一个数字: 从管道中读取的第一个数字一定是质数intp;read(pleft[RD],p,sizeof(p));if(p-1){// 如果已经读到了末尾exit(0);}printf(prime %d\n,p);// 否则输出该质数// 创建一个新的管道, 向下一个进程传入筛选后的数字(递归调用)intpright[2];pipe(pright);if(fork()0){// 右邻居(下一个进程)close(pright[WR]);// 该进程不会用到 prihgt 的写端close(pleft[RD]);// 该进程不会用到 pleft 的读端// close(pleft[WR]); 每次递归调用 sieve() 前就已经 close 掉了sieve(pright);// 递归调用exit(0);}else{// 当前进程close(pright[RD]);// 当前进程不会用到 pright 的读端// 读入第一个数字之后的所有数字// 并将不是第一个数字的倍数的数传给下一个进程intbuf;while(read(pleft[RD],buf,sizeof(buf))buf!-1){if(buf%p!0){write(pright[WR],buf,sizeof(buf));}}// 循环结束 buf -1 , 将结束标记也传给下一个进程write(pright[WR],buf,sizeof(buf));// 等待当前子进程的结束wait(0);exit(0);}}intmain(){// 创建初始管道intinput_pipe[2];pipe(input_pipe);if(fork()0){// 右邻居close(input_pipe[WR]);// 右邻居用不到该管道的写端sieve(input_pipe);exit(0);}else{close(input_pipe[RD]);// 当前进程用不到管道的读端// 向管道的写端传入数字inti;for(i2;i35;i){write(input_pipe[WR],i,sizeof(i));}// 传入结束标记i-1;write(input_pipe[WR],i,sizeof(i));// 等待当前子进程的结束wait(0);exit(0);}}几点说明RD0、WR1对应pipe()返回的读/写端下标和 pingpong 里一样用宏让语义更清楚。递归 fork 是本程序的核心结构sieve()每被调用一次就筛掉一个素数、再造一个右邻居直到读到-1递归终止。整条进程链不是预先建好的而是筛出一个素数、长出下一段。read(pleft[RD], p, sizeof(p))读第一个数代码里没有检查返回值因为左邻居要么会写数据、要么会写-1哨兵read一定能读到 4 字节不会返回 0 或小于 4 的情况。while (read(...) buf ! -1)的循环条件是双保险既处理了显式-1哨兵也处理了写端全关、read返回 0EOF的情况两者任一满足都会退出循环。每个进程wait(0)等自己的右邻居结束配合最外层 main 的wait(0)保证main 在整条链全部输出、全部退出后才退出。Makefile—— 把程序编进内核镜像和 pingpong 一样新写的用户程序需要在Makefile的UPROGS里注册UPROGS\ $U/_cat\ $U/_echo\ ... $U/_sleep\ $U/_pingpong\ $U/_primes\ # 添加 $U/_primes加上这一行后make qemu才会把primes编进fs.img你才能在 xv6 shell 里运行它。验证方式一手动在 xv6 里测makecleanmakeqemu# 启动 xv6进入 shell 后执行primes预期输出顺序固定、从prime 2到prime 31共 11 个素数prime 2 prime 3 prime 5 prime 7 prime 11 prime 13 prime 17 prime 19 prime 23 prime 29 prime 31方式二用评分脚本测在 Linux 终端运行./grade-lab-util primes应看到测试通过末尾的(Xs)是耗时视机器而定 Test primes primes: OK (2.9s)评分脚本里的判定逻辑grade-lab-util就是匹配这 11 个prime %d输出test(20,primes)deftest_primes():r.run_qemu(shell_script([primes,echo OK]))args[prime %d%iforiin[2,3,5,7,11,13,17,19,23,29,31]]args.append(^OK$)r.match(*args)复盘本实验解决了什么表面是用并发筛素数实则把 pingpong 里立起来的 IPC 骨架从一条线扩展成了一棵链第一次把 pipe fork 组合成进程流水线——理解了每级进程 一个过滤器filter的并发范式这正是 Unix 哲学里filter-and-pipeline的原型。第一次用递归 fork 动态构造进程拓扑——进程不是预先建好的而是筛出一个素数、再 fork 下一段即官方 hint 说的 “create the processes only as they are needed”。第一次直面 EOF / 结束标记的多进程语义——pingpong 只传 1 字节可以蒙混过关primes 逼你搞清楚数据到底什么时候算结束于是引入了显式的-1哨兵。为什么 close 是铁律primes 是最典型的反例结合手册的 EOF 规则只有当所有写端 fd 都关闭read才会返回 0EOF。pingpong 里单次传 1 字节不 close 未必立刻死锁但 primes 是多进程 多轮 依赖结束信号收尾的任何一个进程忘了关掉自己用不到的写端它的下游read就永远等不到 EOF → 那个下游进程永远阻塞 → 它又wait着自己的子进程 →整条链从中间开始冻住main 进程的wait()也永远不返回程序不死也不退。而且 xv6 的NOFILE16、NPROC64、NFILE100都很紧泄漏的 fd 会直接耗光资源还没筛到 35 就先filealloc失败甚至 panic。所以官方 hint 把关掉用不到的 fd放在第一位。把用完即关变成肌肉记忆比事后用 gdb 追一条多进程死锁划算得多。收获并发素数筛Doug McIlroy / CSP能用进程链 管道解释埃拉托斯特尼筛的并发版本说清每级进程读到的第一个数一定是素数的原因这也是 Go 语言 channel、CSP 并发模型的源头之一。递归 fork 构造进程拓扑能写出每个进程 fork 一个子进程、递归下去的代码并理解它与一次性 fork 一批子进程的区别按需创建省资源。EOF vs 显式哨兵理解read返回 0所有写端关闭和自己定义一个-1结束标记是两套不同的结束机制当进程必须边读边写、不能提前关写端时就得靠显式哨兵。wait的级联回收每个进程wait自己的直接子进程逐级向上最终 main 等完整条链结束后才退出——这正是官方 hint 强调的 “wait until the entire pipeline terminates”。