xv6 primes

primes

比较容易想到的是递归的做法：主进程生产2~280这些自然数通过管道传输给子进程，子进程读取并将第一个数作为素数输出，剩下的数用该素数作为筛子来筛选，没有被筛除的数就输入管道，输入给下一个子进程，下一个子进程重复上述步骤。

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

void sieve(int in_fds[2]) __attribute__((noreturn));

int main(int argc, char *argv[]) {
  int fds[2];
  pipe(fds);
  if (!fork()) {
    sieve(fds);
  }
  close(fds[0]);

  for (int i = 2; i <= 280; i++) {
    write(fds[1], &i, sizeof(int));
  }
  close(fds[1]);
  wait(0);
  exit(0);
}

void sieve(int in_fds[2]) {
  close(in_fds[1]);
  int p, num;
  int fds[2];
  // read base
  if (!read(in_fds[0], &p, sizeof(int))) {
    exit(0);
  }

  // create next sieve
  printf("prime %d\n", p);
  pipe(fds);
  if (!fork()) {
    sieve(fds);
  }

  // output to next sieve
  close(fds[0]);
  while (read(in_fds[0], &num, sizeof(int))) {
    if (num % p == 0) continue;
    write(fds[1], &num, sizeof(int));
  }
  close(in_fds[0]);
  close(fds[1]);
  wait(0);
  exit(0);
}

但是我这边输出显示乱码：

调试发现是sieve中创建管道的时候失败，进一步发现是将文件描述符消耗完了（xv6中限制文件描述符最大大概为14、15这样）。为什么会消耗完呢：

结合图示，每个进程创建两个文件描述符，关闭其中一个（读管道fds[0]），fork一个新的sieve子进程，开始处理数据，并且只有处理完数据之后才会关闭另一个（写管道fds[1]），当创建新进程的速度大于进程处理数据的速度时，即打开文件的速度大于关闭的速度，迟早会超出文件描述符数量限制，新的进程就无法再创建管道，因此程序跑不下去。

解决方法是用主进程来管理这些管道文件描述符，因为主进程只关注两两进程之间通信使用到的管道，其它管道一律关闭，因此限制了打开文件描述符的数量，具体方式是将递归变更为迭代的方式来创建子进程：

主进程先创建一个生产自然数的进程以及管道，用于生产自然数，其对外暴露一个读管道rfd。随后，主进程创建工作进程以及管道fds，将读管道rfd和写管道fds[1]交给该子进程，子进程从rfd读入数据、筛选数据、数据写入fds[1]。在主进程中将会关闭rfd和fds[1]，将fds[0]作为下一个进程的rfd，创建下一个工作子进程….重复上述步骤。

可以看到由主进程来管理文件描述符的话，每次创建子进程时一样会创建一对文件描述符（fds[0]和fds[1]），但是它同时也会关闭一对文件描述符（rfd和fds[1]）。这样就不会使得文件描述符超出限制：

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

int natural_proc();
int sieve_proc(int rfd, int prime);

int main(int argc, char *argv[]) {
  int rfd = natural_proc();
  int prime;
  while (read(rfd, &prime, sizeof(int))) {
    printf("prime %d\n", prime);
    rfd = sieve_proc(rfd, prime);
  }
  exit(0);
}

int natural_proc() {
  int fds[2];
  pipe(fds);
  if (!fork()) {
    close(fds[0]);
    for (int i = 2; i <= 280; i++) {
      write(fds[1], &i, sizeof(int));
    }
    close(fds[1]);
    exit(0);
  }

  close(fds[1]);
  return fds[0];
}

int sieve_proc(int rfd, int prime) {
  int fds[2];
  int num;
  pipe(fds);
  if (!fork()) {
    close(fds[0]);
    while (read(rfd, &num, sizeof(int))) {
      if (num % prime != 0) {
        write(fds[1], &num, sizeof(int));
      }
    }
    close(fds[1]);
    exit(0);
  }

  close(rfd);
  close(fds[1]);
  return fds[0];
}

虽然这个代码能通过测试，但我觉得最好还是需要在主进程exit(0)之前加一句while (wait(0) >= 0)来等待所有子进程退出。

参考

https://blog.eastonman.com/blog/2020/11/xv6-primes/