质数发生器和校验器_labview求100以内素数[通俗易懂]

1.题目描述：在xv6上使用管道实现“质数筛选”, 输出2~35之间的而所有质数。请将代码写在user/primes.c文件中。运行效果应该如下：

2. 实验原理：

先附上参考链接。

（1）官方网址：https://pdos.csail.mit.edu/6.828/2020/index.html

（2）xv6 book：https://pdos.csail.mit.edu/6.828/2020/xv6/book-riscv-rev1.pdf

（3）原理概念：

管道（pipe）是一种最基本的进程间通信机制。管道分为 读出端 和 写入端 两个部分，进程可以向写端写入数据，也可以从读端读出数据。通过pipe系统调用，内核会为用户进程创建管道，同时返回两个文件描述符，用以描述管道的读写端，例如：

int p[2];
int ret;
ret = pipe(p); /*正常创建后，p[1]为管道写入端，p[0]为管道读出端*/ 

 通过文件描述符，程序可以按读写文件的形式读写管道，例如：

int write = write(p[1], buffer, n);
int read = read(p[0], buffer, n);

 进程通常只持有某个管道的读出端或者写入端，因此使用的时候需要将另一端关闭，例如(一般通过fork()开启一个新的进程，父进程和子进程分别实现对管道流的读和写)：

/* 子进程读管道，父进程写管道 */
int ret = fork();
if (ret == 0) { 
    /* 子进程 */
    close(p[1]); // 关闭写端
    ...
    read(...);
    ...
    close(p[0]); // 读取完成，关闭读端
} else if (ret>0) { 
    /* 父进程 */
    close(p[0]); // 关闭读端
    ...
    write(...);
    ...
    close(p[1]); // 写入完成，关闭写端
}

（注意：为什么要专门提及管道和父子进程的概念呢？？因为质数筛选过程中，筛选后的数字由上一级流向下一级的操作是通过：父进程通过管道写筛选后的数据，子进程从管道读筛选后的数据实现的！） 

质数筛选的思想：

使用系统调用pipe创建管道，使用系统调用fork创建子进程。主进程将所有数据（例2~11）输入到管道的左侧，第一个子进程从管道读出并筛选出2，排除掉2的倍数，其他数字再写入下一管道；第二个子进程读出并筛选出3，排除掉3的倍数，其他数字写入到下一管道；第三个子进程读出筛选出5，依次类推……如下图所示：

即每一次筛选，从当前未被筛选的第一个数字开始，排除掉它的倍数，再将剩余的数字写入管道。

（4）实现思路： 

1.设置一个长度为 36 的数组 nums（0~35），并对其进行初始化。 其中 nums[i]=’1’表示已经对数 i 进行判断其是否为质数；对于 nums[i]=’0’，反之。

2.main 函数中，父进程向下一级传递 nums 数组，子进程调用 prime 函数继续对传入的 nums 数组进行筛选。wait()保证数据传输的顺序不会混乱。（最终在 primes 函数中 exit(0)结束）

 3.primes质数筛选函数过程中，做了三件事：找出当前nums数组中的第一质数（未被判断即nums[i]==’0’的数）；筛去该质数的倍数；通过进程，将筛选后的数组传入下一级。

（注意：primes利用了递归的思想。代码段if(target==0){exit(0)}处可以视为递归函数退出的条件，可以理解为：如果当前nums数组均筛选完毕，则target不会变化仍为0，此时质数筛选过程完毕，退出。

代码实现：

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

#define MAXNUM 36

void prime(int read_p,int write_p){
    char nums[MAXNUM];
    read(read_p,nums,MAXNUM);//读取上一级传过来的数组
    int target = 0;
    for(int i=0;i<MAXNUM;i++){
        //不断对数字进行判断，找出当前第一个质数
        if(nums[i]=='0'){
            target = i;
            break;//跳出循环
        }
    }
    if(target==0){
        exit(0);
    }
    printf("prime %d\n",target);
    nums[target]='1';
    //筛去当前质数的公倍数
    for(int i=0;i<MAXNUM;i++){
        if(i%target==0 ){
            nums[i] = '1';
        }
    }
    

    //创建子进程，进行流水
    int pid  = fork();
    if(pid>0){
        //当前进程
        write(write_p,nums,MAXNUM);
        wait(0);
    }
    if(pid==0){
        //当前进程的子进程
        prime(read_p,write_p);
        wait(0);
    }
}

int
main(int argc,int *argv[]){
    //创建一个数组，用于判断质数
    //下标i表示要判断的数字，num[i]=1表示已经判断,num[i]=0表示未判断
    char nums[MAXNUM];
    //数组的初始化
    memset(nums,'0',sizeof(nums));

    //管道的创建
    int p[2];
    pipe(p);

    int pid = fork();
    //父进程写nums数组
    if(pid>0){
        nums[0] = '1';
        nums[1] = '1';//0,1已经判断
        write(p[1],nums,MAXNUM);
        wait(0);
    }
    //子进程调用prime函数进行下一级的判断
    if(pid==0){
        prime(p[0],p[1]);//递归地使用相同的管道，减少内存损耗，通过wait()实现父子进程顺序执行
        wait(0);
    }
    exit(0);
}

今天的文章质数发生器和校验器_labview求100以内素数[通俗易懂]分享到此就结束了，感谢您的阅读。