xv6操作系统实验 – 质数筛

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

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

管道概念

管道是类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
文章: 30

一条评论

留下评论