xv6操作系统实验 – 质数筛

预计阅读时间： 5 分钟

哈工大深圳2020年秋季操作系统实验课，利用管道实现质数筛的思路分析和ANSI C实现。

Update 2022-09-07: xv6-2020及以后的xv6操作系统系统调用参数有小幅修改，因此本文中的代码并不能直接使用，仅作为思路的参考。

管道概念

管道是类Unix系统中重要的概念，它允许进程间的同步通信，是操作系统组成中必不可少的一部分。

简单的管道用法

此处参考一段维基百科的示例。

ls -l | less

在这个例子中，ls用于在Unix下列出目录内容，less是一个有搜索功能的交互式的文本分页器。这个管线使得用户可以在列出的目录内容比屏幕长时目录上下翻页。

以less结束的管道（或more，这是个相似的标签页工具）是最常被使用的。这让用户可以阅览尚未显示的大量文字（受可用缓存限制，控制台的屏幕大小、屏幕缓存大小往往有限，不足以一次先输出所有输出内容，也不能自由滚动内容），若少了这工具则这些文字将会卷过终端而无法阅读到。换句话说，他们将程序员从为自己的软件开发分页器的负担中解放了出来：他们只需要把他们的输出用过“管道”导入到less程序中即可，甚至也可以完全不顾分页问题，去假定他们的用户会在需要将输出分页的时候自己去这样做。

在POSIX程序中使用管道

使用C语言在UNIX中使用pipe(2)系统调用时，这个函数会让系统构建一个匿名管道，这样在进程中就打开了两个新的文件描述符：一个只读端和一个只写端。管道的两端是两个普通的文件描述符，它们是匿名的，只能够通过参数传递或使用dup系统调用复制，这就让其他进程无法连接该管道。 为了避免死锁，并充分利用进程的并行化，有一个或多个管道的UNIX进程通常会调用fork(2)产生新进程。并且每个子进程在开始读或写管道之前都会关掉不会用到的管道端。或者进程会产生一个子线程并使用管道来让线程进行数据交换。

注意：关闭不需要使用的管道端口不是必须的，但是是建议的，因为未关闭的管道可能会带来意想不到的问题。

xv6中的管道

xv6中的shell支持类似bash的管道，通过|传递字节流。系统调用与POSIX类似，我们很快可以看到，xv6系统也使用int类型作为文件描述符。

打开管道的代码就像这样。

int p[2];
pipe(p);

然后我们就可以对这个管道进行读写了，像这样。

char buff;
write(p[1], "a", 1);
read(p[0], &buff, 1);

特别注意，写入管道是非阻塞的，读取管道是阻塞的，一直到有数据到来或者管道被关闭。

质数筛原理

我们在此使用的是埃氏筛，而不是高斯筛。埃氏筛的介绍我搬运一段维基百科的GIF。

简单的来说就是从头开始选取未被筛去的数，将它的倍数筛去，不断重复。

利用管道的质数筛

从主进程开始，不断新建子进程，每个子进程执行一次筛选，并将使用的基（base）认为是质数（这是正确的，请思考为什么），并返回，直到全部的数都被筛去或被返回。

各个进程之间的通讯将会使用到管道。

详细的设计思路

实现源码

Let’s start coding!

#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"

void prime(int input_fd);

int main(int argc, char const *argv[])
{
    int parent_fd[2];
    pipe(parent_fd);
    if (fork())
    {
        close(parent_fd[0]);
        int i;
        for (i = 2; i < 36; i++)
        {
            write(parent_fd[1], &i, sizeof(int));
        }
        close(parent_fd[1]);
    }
    else
    {
        close(parent_fd[1]);
        prime(parent_fd[0]);
    }
    wait();
    exit();
}

void prime(int input_fd)
{
    int base;
    /* Exit if last child */
    if (read(input_fd, &base, sizeof(int)) == 0)
    {
        exit();
    }
    printf("prime %d\n", base);

    /* Create new child if not last */
    int p[2];
    pipe(p);
    if (fork() == 0)
    {
        close(p[1]);
        prime(p[0]);
    }
    else
    {
        close(p[0]);
        int n;
        int eof;
        do
        {
            eof = read(input_fd, &n, sizeof(int));
            if (n % base != 0)
            {
                write(p[1], &n, sizeof(int));
            }
        } while (eof);

        close(p[1]);
    }
    wait();
    exit();
}