记录一下写 6.s081 Lab1 的过程，还有在这个实验中学到的新的知识。

这一次实验的内容为 Xv6 and Unix Utilities，实现一些基本 Unix 工具，通过这个过程了解 xv6 系统的结构，以及是如何运行的，建立对其的基本认识。

xv6-book Chapter 1 部分内容

一、Copy-on-Write(COW)

也可以叫做写时复制，fork 并不会复制整个父进程的内存，这样的开销很大，父子进程共享一个页，只有当要向内存中写入一些内容的时候内核才会复制那个页。

当设计并发程序时，子进程可以使用COW技术使开销较小。

二、IO重定向

比如在shell中使用 cat 命令，当需要重定向时：

cat < input.txt

shell本身需要维持自己的进程信息，如果不fork一个子进程直接使用exec来调用cat，shell本身的信息会被cat取而代之。但是shell本身应该是一个可持续的进程，fork会复制父进程的fd table因此需要fork子进程来执行其他的命令调用。

fork一个新进程

fork和exec不能合并成forkexec，会有很多弊端，这里列举出来方便理解：

1. shell先修改自己的IO，再调用forkexec： shell先把自己的输入定向到input.txt，然后等执行完后再把自己的输出修改回屏幕。

   • 尴尬之处：
     • 并发风险：对于多线程shell，一个线程修改了标准输出会影响到其他线程（造成覆盖，这样的shell用户体验会很差）。
     • 容错性差：如果forkexec失败了，shell想要恢复现场会比较困难，如果失败那么shell进程就会出现错误。

2. 给forkexec传递复杂的参数： 设计一个复杂的forkexec(program, args, input_fd, output_fd, error_fd…)

   • 尴尬之处：
     • 参数量爆炸：除了以上列出的这几个IO重定向参数，还有环境变量、信号屏蔽字、进程优先级、工作目录之类的很多参数，使用起来会很复杂。
     • 灵活性丧失：如果我没有重定向fd 0（标准输入）和fd 1（标准输出），想要重定向其他的fd（比如fd 3），这些行为不可预测，如果要实现会导致接口变得臃肿。

3. 让cat支持参数来指定输入输出： 比如cat —input=file1 —ouput=file2

   • 尴尬之处：
     • 违反了Unix哲学做一件事并把一件事做好的原则：cat只负责拼接文件，不应该去管文件是如何打开的。
     • 代码冗余：所有需要IO重定向的命令都要重复实现重定向的代码。
     • 破坏管道：管道的精髓在于程序以为自己写到了屏幕上，实际上是内核把数据传送给了另外一个程序，如果每个进程都自己管理IO那么这种无感知协作就会消失。

三、管道pipes

一个管道是一个小内核缓存，作为一对文件描述符（一个读端一个写端）暴露给进程。管道给进程提供了一种通信方式。

如果在管道没有内容被写入时，使用管道进行read会发生阻塞，只有当写端写入内容时才会被唤醒并读出内容。还有一种情况，如果所有的写端都被关闭了，那么被阻塞的read会读到EOF。

因此当使用管道时，读管道的进程一定要关闭写端，否则永远不会识别到EOF。

临时文件可以实现和管道相同的功能，不过管道有四个优势：第一，管道会自动被清理，如果使用完临时文件就要一个个小心地清理。第二，管道可以传入任意长度的数据流，数据流入流出会通过阻塞来平衡，而文件重定向需要磁盘提供足够的空闲空间存储所有的数据，做不到阅后即焚。第三，管道允许并行操作，文件大多只能等待上一个进程结束后才能继续操作（如果并行难度和开销都将非常大）。第四，管道本身带有阻塞机制，读写管道比没有阻塞语义的文件更高效。

Lab1 实现

主要实现以下的几个功能:

一、sleep (easy)

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

int
main(int argc, char *argv[])
{
  if (argc != 2) {
    fprintf(2, "Usage: sleep <ticks>\n");
    exit(1);
  }

  int ticks = atoi(argv[1]);
  if (sleep(ticks) < 0) {
    fprintf(2, "sleep: system call failed\n");
    exit(1);
  }

  exit(0);
}

主要考察对一些基本系统调用的使用，这里使用了 sleep 系统调用，传入一个参数 tick 作为 sleep 的时间，fprintf 中的第一个参数2表示在 qemu 的终端中输出错误（error），如果系统调用错误就 exit 1，否则程序将在 sleep 后退出。

二、pingpong (easy)

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

int
main(int argc, char *argv[])
{
  int p0[2];
  int p1[2];
  char buf;

  if (pipe(p0) < 0 || pipe(p1) < 0) {
      fprintf(2, "pipe: system call failed\n");
      exit(1);
  }

  int pid = fork();

  if (pid < 0) {
    fprintf(2, "fork: system call failed\n");
    exit(1);
  }

  if (pid == 0) {
    int read_fd = dup(p0[0]);
    int write_fd = dup(p1[1]);
    close(p0[0]);
    close(p0[1]);
    close(p1[0]);
    close(p1[1]);

    if (read(read_fd, &buf, 1) < 0) {
      fprintf(2, "read: system call failed\n");
      exit(1);
    }
    fprintf(1, "%d: received ping\n", getpid());

    if (write(write_fd, "x", 1) != 1) {
      fprintf(2, "write: system call failed\n");
      exit(1);
    }

    close(read_fd);
    close(write_fd);

    exit(0);
  } else {
    int write_fd = dup(p0[1]);
    int read_fd = dup(p1[0]);
    close(p0[0]);
    close(p0[1]);
    close(p1[0]);
    close(p1[1]);

    if (write(write_fd, "x", 1) != 1) {
      fprintf(2, "write: system call failed\n");
      exit(1);
    }

    if (read(read_fd, &buf, 1) < 0) {
      fprintf(2, "read: system call failed\n");
      exit(1);
    }

    fprintf(1, "%d: received pong\n", getpid());

    close(write_fd);
    close(read_fd);
  }

  exit(0);
}

考察对pipe以及fork的使用。

pipe系统调用创建一个管道，参数为长度为2的数组，数组下标0为管道读端，下标1为管道写端。创建后可以使用write和read进行进程间通信。

fork系统调用创建一个和当前进程（几乎）完全相同的子进程，并且子进程有自己的内存空间，内存变量不共享，而是复制了一份，但文件描述项目表中的指针是共享的，比如这里的管道。创建的新进程同样会有fork的返回值fork函数在不同进程的返回值不同，在父进程中返回值为新创建的子进程的pid ，而在新创建的子进程中返回0，这可以作为区分两个进程的方法。

也讲一下read和write系统调用的使用,read接收3个参数，分别为读取文件的描述符fd、有效的内存地址用于存储读取到的内容、希望读取的长度（以字节为单位），同理write是将内存地址中向文件描述符指向的文件中写入，它们的返回值有三种:

1. > 0: 成功，返回读取到的字节数。
2. = 0: EOF，表示文件读完了，也可能是在读管道时发现管道中已经没有数据，这是循环读取时的退出标志。
3. -1: 出错，比如fd无效，或传入了非法地址。

**注意：**write系统调用很少返回0，只有当write(fd, &buf, 0)才可能返回0。如果在写管道时发现读端被关闭了，那么会触发SIGPIPE，通常导致进程直接被杀死。如果忽略信号，则返回-1，在xv6中这种情况会直接返回 -1。

三、primes (moderate)/(hard)

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

void
sieve(int read_fd)
{
  int p[2];
  int prime, buf;

  if (read(read_fd, &prime, sizeof(int)) == sizeof(int)) {
    fprintf(1, "prime %d\n", prime);
  } else {
    exit(0);
  }

  if (pipe(p) < 0) {
    fprintf(2, "pipe: system call failed\n");
    exit(1);
  }

  if (fork() == 0) {
    close(p[1]);

    sieve(p[0]);
  } else {
    int write_fd = dup(p[1]);
    close(p[0]);
    close(p[1]);

    while (read(read_fd, &buf, sizeof(int)) == sizeof(int)) {
      if (buf % prime == 0) {
        continue;
      }

      if (write(write_fd, &buf, sizeof(int)) != sizeof(int)) {
        fprintf(2, "primes: write error\n");
        exit(1);
      }
    }

    close(write_fd);
    wait(0);
  }

  exit(0);
}

int
main(int argc, char *argv[])
{
  int p[2];
  if (pipe(p) < 0) {
    fprintf(2, "pipe: system call failed\n");
    exit(1);
  }

  if (fork() == 0) {
    int read_fd = dup(p[0]);
    close(p[0]);
    close(p[1]);

    sieve(read_fd);
  } else {
    int write_fd = dup(p[1]);
    close(p[0]);
    close(p[1]);

    for (int i = 2; i <= 35; i++) {
      if (write(write_fd, &i, sizeof(int)) != sizeof(int)) {
        fprintf(2, "primes: write error\n");
        exit(1);
      }
    }

    close(write_fd);

    wait(0);
  }

  exit(0);
}

用管道写一个并发的埃拉托斯特尼筛（sieve of Eratosthenes），用来筛出35以内的所有质数 参考文章，思想就是每个进程从左边接收一些数，输出第一个数（此数必为质数），然后将剩下的接收到的所有不能被该质数整除的数依次发送给下一个进程，直至结束。

这里用到了一个sieve递归函数，首先处理一下管道，输出第一个接收到的数，同时也是递归出口，如果read管道读端返回0的话就代表着所有的数已经处理完毕，直接退出。否则就使用fork调用创建一个新进程，当前进程把剩下的不能被质数整除的数通过管道发送给子进程，然后等待子进程结束。子进程递归调用sieve函数…

其中 main 函数作为入口，初始化一个管道后把所有的数全部发送给子进程，子进程开始调用sieve。为了保证获得所有输出，主进程需要等待整个管道关闭才应该退出，否则会出现：某个进程还没输出主进程已经结束，shell提示符$ 已经出现，但是子进程们还在继续输出，控制台会很混乱。

四、find (moderate)

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

char*
getname(char *path)
{
  static char buf[DIRSIZ+1];
  char *p;

  // Find first character after last slash.
  for(p=path+strlen(path); p >= path && *p != '/'; p--)
    ;
  p++;

  if(strlen(p) >= DIRSIZ)
    return p;
  memmove(buf, p, strlen(p));
  buf[strlen(p)] = 0;
  return buf;
}

void
find(char *path, char *target)
{
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;

  if ((fd = open(path, 0)) < 0) {
    fprintf(2, "find: cannot open %s\n", path);
    return;
  }

  if(fstat(fd, &st) < 0){
    fprintf(2, "find: cannot stat %s\n", path);
    close(fd);
    return;
  }

  switch (st.type) {
  case T_FILE:
    if (strcmp(getname(path), target) == 0) {
      printf("%s\n", path);
    }
    break;
  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("find: path too long\n");
      break;
    }
    strcpy(buf, path);
    p = buf + strlen(buf);
    *p++ = '/';
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      if (strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) {
          continue;
      }
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      find(buf, target);
    }
  }

  close(fd);
}

int
main(int argc, char *argv[])
{
  if (argc != 3) {
    fprintf(2, "Usage: find <path> <name>\n");
    exit(1);
  }
  find(argv[1], argv[2]);
  exit(0);
}

find 的实现可以参考 ls 的实现，主要难点就是处理字符串获取文件名，剩下的只要递归调用一下 find 函数就可以了。

五、xargs (moderate)

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

int
main(int argc, char *argv[])
{
  char buf[512];
  char *x_argv[MAXARG];
  int x_argc = 0;

  if (argc < 2) {
    fprintf(2, "Usage: xargs command [args...]\n");
    exit(1);
  }

  for (int i = 1; i < argc; i++) {
    x_argv[x_argc] = argv[i];
    x_argc++;
  }

  int n = 0;
  char c;

  while (read(0, &c, 1) > 0) {
    if (c == '\n') {
      buf[n] = 0;

      if (fork() == 0) {
        x_argv[x_argc] = buf;
        x_argv[x_argc + 1] = 0;

        exec(x_argv[0], x_argv);
      } else {
        wait(0);
      }

      n = 0;
    } else {
      if (n < sizeof(buf) - 1) {
        buf[n++] = c;
      }
    }
  }

  exit(0);
}

xargs 的作用就是将管道左边命令的输出作为管道右边命令的参数，比如：

find . b | grep hello

这条命令只会将 find . b 的结果作为文本传给右边的 grep hello 命令,即在查找到的 b 文件的路径中去寻找是否有 hello 这个单词，再看下面使用 xargs 的命令

find . b | xargs grep hello

这相当于将find . b的结果作为 grep hello 的参数，即在找到的 b 文件中去查找是否有 hello 这个单词。

---

以上就是第一个 Lab: Xv6 and Unix utilities 的完成方案，最简单的 Boot xv6 我在此省略了，就是配一下环境什么的，稍微改了点东西去兼容一下我的系统，配环境网上有很多教程，我的系统也不是大家最常用的 Windows 系统，所以这里就省略了。

总体来说这个 Lab 还是十分简单，只需要阅读一下xv6 教程，并了解一些系统调用的具体使用就可以比较轻松地写出来。