xv6操作系统实验 – 质数筛

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

预计阅读时间: 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();
}
Easton Man
Easton Man
文章: 37

4 评论

  1. 这个质数题目答案有一个问题,如果递归中出现了exit,那么编译器在预编译时会认为,递归永远无法得到结果,然后报出 无尽递归 的错误

    • 据我所知GCC12才引入了这个check,但是靠代码以外的控制流结束无穷递归这种操作在系统编程里很常见,可以使用noreturn属性或者使用编译flag禁止编译器检查

  2. 我最近也在做这个lab,这个地方如果把素数的上界改成100的话,会出现下面这种奇怪的结果,没有输出37以后的素数,然后输出了一段乱码,不知道是什么问题。

    $ primes
    prime 2
    prime 3
    prime 5
    prime 7
    prime 11
    prime 13
    prime 17
    prime 19
    prime 23
    prime 29
    prime 31
    prime 37
    )+/5;=CGIOSYaaaaaaaaaaa$

回复 Easton Man取消回复

您的电子邮箱地址不会被公开。 必填项已用*标注