|
使用管道将2至35中的素数筛选出来，这个想法归功于 Unix 管道的发明者 Doug McIlroy 。链接(https:///~rsc/thread/)中间的图片和周围的文字解释了如何操作。最后的解决方案应该放在 user/primes.c 文件中。你的目标是使用 pipe 和 fork 来创建管道。第一个进程将数字 2 到 35 送入管道中。对于每个素数，你要安排创建一个进程，从其左邻通过管道读取，并在另一条管道上写给右邻。由于 xv6 的文件描述符和进程数量有限，第一个进程可以停止在 35 。 - 请关闭进程不需要的文件描述符，否则程序将在第一个进程到达 35 之前耗尽 xv6 资源。
- 一旦第一个进程到达 35 ，它应该等到整个管道终止，包括所有的子进程，孙子进程等。因此，主进程只有在打印完所有输出后才能退出，即所有其他进程已退出后主进程才能退出。
- 当管道的写入端关闭时， read 函数返回 0 。
- 最简单的方式是直接将 32 位（4 字节）的整型写到管道中，而不是使用格式化的 ASCII I/O 。
- 将程序添加到 Makefile 中的 UPROGS 。
- 首先打开提示给出的链接，阅读并观察上面给出的图。由图可见，首先将数字全部输入到最左边的管道，然后第一个进程打印出输入管道的第一个数 2 ，并将管道中所有 2 的倍数的数剔除。接着把剔除后的所有数字输入到右边的管道，然后第二个进程打印出从第一个进程中传入管道的第一个数 3 ，并将管道中所有 3 的倍数的数剔除。接着重复以上过程，最终打印出来的数都为素数。
- 参考 xv6 手册第一章的 Pipes 部分，其中的例子演示了运行程序 wc ，由此受到启发，可以使用文件描述符重定向技巧，避免 xv6 的文件描述符限制所带来的影响。所以，学习示例代码，先写一个重定向函数 mapping ，虽然叫重定向，但感觉还是称为映射比较好，原理就是关闭当前进程的某个文件描述符，把管道的读端或者写端的描述符通过 dup 函数复制给刚刚关闭的文件描述符，再把管道描述符关闭，节约了资源。
- 编写 main 函数，首先创建文件描述符和创建一个管道，再创建一个子进程，子进程把管道的写端口描述符映射到原来的描述符标准输出 1 上。循环通过 write 系统调用把 2 到 35 写入管道。父进程等待子进程把数据写入完毕后，父进程把管道的读端口描述符映射到原来的描述符标准输入 0 上。在编写一个 primes 函数，调用此函数实现递归筛选的过程。
- 编写 primes 函数。定义两个整型变量，存放从管道获取的数，定义管道描述符数组。从管道中读取数据，第一个数一定是素数，直接打印出来，然后创建另一个管道和子进程，子进程通过管道描述符映射，关闭不必要的文件描述符节约资源。再循环读取原管道中的数据，如果该数和原管道的第一个取模后不为 0 ，则再次写入刚刚创建的管道。父进程等待此子进程执行完毕，再次调用重定向函数关闭不必要的文件描述符，再递归调用 primes 函数重复以上筛选过程，即可将管道中所有素数打印出来。
// Lab Xv6 and Unix utilities
// primes.c
#include "kernel/types.h"
#include "user/user.h"
#include "stddef.h"
// 文件描述符重定向(讲成映射比较好)
void
mapping(int n, int pd[])
{
// 关闭文件描述符 n
close(n);
// 将管道的 读或写 端口复制到描述符 n 上
// 即产生一个 n 到 pd[n] 的映射
dup(pd[n]);
// 关闭管道中的描述符
close(pd[0]);
close(pd[1]);
}
// 求素数
void
primes()
{
// 定义变量获取管道中的数
int previous, next;
// 定义管道描述符数组
int fd[2];
// 从管道读取数据
if (read(0, &previous, sizeof(int)))
{
// 第一个一定是素数，直接打印
printf("prime %d\n", previous);
// 创建管道
pipe(fd);
// 创建子进程
if (fork() == 0)
{
// 子进程
// 子进程将管道的写端口映射到描述符 1 上
mapping(1, fd);
// 循环读取管道中的数据
while (read(0, &next, sizeof(int)))
{
// 如果该数不是管道中第一个数的倍数
if (next % previous != 0)
{
// 写入管道
write(1, &next, sizeof(int));
}
}
}
else
{
// 父进程
// 等待子进程把数据全部写入管道
wait(NULL);
// 父进程将管道的读端口映射到描述符 0 上
mapping(0, fd);
// 递归执行此过程
primes();
}
}
}
int
main(int argc, char *argv[])
{
// 定义描述符
int fd[2];
// 创建管道
pipe(fd);
// 创建进程
if (fork() == 0)
{
// 子进程
// 子进程将管道的写端口映射到描述符 1 上
mapping(1, fd);
// 循环获取 2 至 35
for (int i = 2; i < 36; i++)
{
// 将其写入管道
write(1, &i, sizeof(int));
}
}
else
{
// 父进程
// 等待子进程把数据全部写入管道
wait(NULL);
// 父进程将管道的读端口映射到描述符 0 上
mapping(0, fd);
// 调用 primes() 函数求素数
primes();
}
// 正常退出
exit(0);
}
在 Makefile 文件中， UPROGS 项追加一行 $U/_primes\ 。编译并运行 xv6 进行测试。 $ make qemu
...
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
$
退出 xv6 ，运行单元测试检查结果是否正确。 ./grade-lab-util primes
通过测试样例。 make: 'kernel/kernel' is up to date.
== Test primes == primes: OK (1.4s)
|
