使用管道编写prime的并发版本。这个想法源于Unix管道的发明者道格·麦克洛伊。下面说明了如何实现。您的解决方案应该在文件user/primes.c中。
您的目标是使用pipe和fork来设置管道。第一个过程将数字2到35送入管道。对于每个素数,您将创建一个进程,该进程通过一个管道从其左侧邻居读取数据,并通过另一个管道向其右侧邻居写入数据。由于xv6具有有限数量的文件描述符和进程,因此第一个进程可以在35停止。
代码如下(示例):
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
void primes(int p[])
{
int res;
if (!read(p[0], &res, 4)) {
// fprintf(2, "End not in main pid:%d.\n", getpid());
exit(0);
}
fprintf(2, "prime %d\n", res);
int c[2];
pipe(c);
if (fork() == 0) {
close(p[0]);
close(c[1]);
primes(c);
} else {
close(c[0]);
int tmp;
while(read(p[0], &tmp, 4)) {
if (tmp % res != 0) {
write(c[1], &tmp, 4);
}
}
close(p[0]);
close(c[1]);
wait((int *) 0);
}
}
int
main(int argc, char *argv[])
{
int p0[2];
pipe(p0);
for (int i = 2; i <= 35; i++) {
write(p0[1], &i, 4);
}
close(p0[1]);
primes(p0);
// fprintf(2, "End in main pid:%d.\n", getpid());
exit(0);
}
结果
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
本题非常精妙,作为初学者进一步加深了对fork,pipe,read,write的理解。
程序流程示意,其重点并不在筛去合数的过程,而在于进程间通信的方式
线程1 | 从父管线p0读队头print2 | 起动线程2创建管线c1(此时为空) | 筛掉2的倍数剩余塞入管线c1 | ||||||
---|---|---|---|---|---|---|---|---|---|
线程2 | 从父管线c1读(等待父进程塞入数据) | print 3 | 起动线程3创建管线c2(此时为空) | 筛掉3的倍数剩余塞入管线c2 | |||||
线程3 | 从父管线c2读(等待父进程塞入数据) | print 5 | 起动线程4创建管线c3(此时为空) | 筛掉5的倍数剩余塞入管线c3 | |||||
… … | … … |
个人对于题目的疑惑和理解
$ primes
prime 2
prime 3
prime 5
prime 7
prime $ 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
可以看到结果是大致正确的,主进程提前结束导致程序提前回到了命令行$
init: starting sh
$ primes
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19
prime 23
prime 29
prime 31
End not in main pid:14.
End in main pid:13.
End in main pid:12.
End in main pid:11.
End in main pid:10.
End in main pid:9.
End in main pid:8.
End in main pid:7.
End in main pid:6.
End in main pid:5.
End in main pid:4.
End in main pid:3.