[xv6]Lab1-Utilities

开始6.S081的学习了，在这里记录下我对xv6的理解以及我的题解，这里我会尽可能详细的写。
我写了我的代码实现，但是肯定是不完善的，所以你最好都自己写，你如果实在写不出来，可以评论一句 “看看代码”。

环境安装

这个照着官网的 教程 来就行，注意一下自己的linux版本（ubuntu20.04）。

sleep (easy)

因为不知道该怎么开始，所以这个我是直接看写好的，知道了怎么开始才能继续下边的任务对吧。就是调用提供的sleep接口就行。

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

int main(int argc, char *argv[2])
{
    if (argc < 2)
    {
        fprintf(2, "usage sleep <ticks>\n");
        exit(1);
    }
    sleep(atoi(argv[1]));
    exit(0);
}

pingpong (easy)

这个任务要求我们利用管道在两个进程之间通信，最后实现这样的效果：

$ make qemu
...
init: starting sh
$ pingpong
4: received ping
3: received pong
$

xv6中我们可以使用pipe()函数创建管道，提到这个我们要先了解一下文件描述符。

具体请自行查阅xv6文档，简单来说就是在一个进程中一些读写等操作需要文件描述符来确定，比如read(0, buf,sizeof buf);这里的0就是代表从这个“0”处读取，或者说输入端是0绑定的文件（注意这个0是文件索引）。我们创建一个管道之后，这个管道也有他的文件描述符。例如

int p[2];
pipe(p);

这个管道的文件描述符就被保存在了p数组中。p[0]是管道的读端口，p[1]是管道的写端口，有了管道的文件操作符我们就可以操作管道了。

这个任务既可以用一个管道也可以用两个管道，两个管道更容易理清关系，记得关闭无用描述符，比如p1在process1只写那么就close(p1[1])等等，双管道双进程关系如图：

一个管道也可以做，我就是一个管道做的，这样做有没有什么风险我不知道，但是确实可以用。在我的理解中单管道是这样工作的：
首先在process1中fork出process2。process2在read时如果p[0]没有接收到数据并且process1的p[1]也没有关闭，所以无论怎样process2都会等待接收process1的数据，process1传输ping之后close(p[1])，process2接收ping再输出，此时process1也会被read阻塞，直到process2传入pong，这样就保证了顺序即使只有一个管道也不会乱。

primes (moderate)/(hard)

这个任务是让我们写出素数筛，具体实现请思考这张图：

思考完了吗？那我来讲讲实现吧。
首先呢一个进程只会输出一个数，之后他会接收上一个进程中已经筛过数继续筛，上图的drop就是被筛掉的数，我们可以看到在输出2的进程中4、6、8...等所有2的倍数都被drop了，通过筛选的第一个数也就是3会进入新进程并输出，第二个数5因为不被3整除且是输出3的进程的第一个通过筛选的数所以他又进入了一个新进程并被输出...以此类推，就完成了素数筛选。
然后讲讲我的实现方法，我使用了一个id作为一个进程的标识，这个id代表通过了上一个进程筛选的第一个数也就是确认的素数。首先这个进程输出这个id，或者输出之后再创建进程随你，之后它接收通过了上一个进程的筛选的数并使用自己来筛选，比如2筛选4、6、8，3筛选9这些，如果这个数通过，那么就传给下一个进程，如果它是第一个通过的，那么优先为它创建新进程并以它命名id，这样的工作持续到上一个进程的管道的写端口关闭，那么我们就关闭进程，上边的进程wait之后也相继关闭。
这方面请了解read，write，wait等系统调用。
我的文字描述可能有点不清晰，那请看图，相信你可以看懂的（我是做的时候为了自己能理清所以画了这张图，第一次觉得流程图这么有用）

find (moderate)

find 需要我们实现查找文件功能，但是会遍历给定文件夹的所有子孙文件夹（我自己起的名字），接着输出所有名称与给定名称的一样的文件。
这个函数给出的提示是让我们看ls的实现源码，接下来我们就好好分析一下ls部分的源码。

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

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

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

  switch(st.type){
  case T_DEVICE:
  case T_FILE:
    printf("%s %d %d %l\n", fmtname(path), st.type, st.ino, st.size);
    break;

  case T_DIR:
    if(strlen(path) + 1 + DIRSIZ + 1 > sizeof buf){
      printf("ls: 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;
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        printf("ls: cannot stat %s\n", buf);
        continue;
      }
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}

这个是主体两个if里就是给文件描述符赋值并将文件的信息保存在stat中，在switch中如果给出的path不是文件夹那么就输出当前文件的一些信息，重点是在T_DIR中，while这里就是遍历了所有子文件。

//通过while循环不断读取数据，我们可以看dirent的解释： Directory is a file containing a sequence of dirent structures.

while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;
      if(stat(buf, &st) < 0){
        printf("ls: cannot stat %s\n", buf);
        continue;
      }
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size);
}

知道了怎么遍历文件，剩下的就好做了，我们在遍历时候判断name是不是等于给定filename就行，当然如果是文件夹，那么我们进入这个文件夹再遍历，就是遇到文件就判断，遇到文件夹就递归，就完成了。

xargs (moderate)

这个我感觉比素数筛难，但是居然不带hard。
首先呢，xargs就是执行它后边的程序也就是 xargs echo hello这样的，它接收管道的数据并加到hello之后，不过呢如果遇到换行\n，那就输出一行并继续执行相同操作，我这里描述的不太清晰，看个例子就明白了:
echo hello\nworld | xargs echo say 这个不是很准确，因为\n会被识别成两个字符，但是我们假设这就是一个。程序是这样执行的：

• xargs echo say hello

• xargs echo say world
  看明白了吗？我们需要写一个字符串处理，就是把\n前和\n后的字符串分开，再用exec执行就行。
  通过分析，xargs的argv参数是这样的

  argv[0] = "xargs"
  argv[1] = "echo"
  argv[2] = "say"

  没有argv[3]，也就是说我们要使用read对文件操作符0进行读取，注意read读取一次只读取一个单词，所以我们还需要能读一整行的函数，不然还没读到\n就输出了不是？因为没有意识到read只读一个单词（或者说一直读到空格和换行）我这个做了很长时间但是找不到问题在哪，还有根据xv6book的描述，参数argv是根据argv==0结束的，在传参时候我们要注意这点。