[MIT 6.S081]操作系统-学习笔记 1

前言

最近开始学习 MIT 的 6.S081，由于讲课视频、课件以及作业都比较完善，所以学习体验也比较好。课程链接为：6.S081。由于之前已经上过一次操作系统了，所以这次学习主要是希望能通过完成作业来加深对 Linux 操作系统的理解。目前准备整理一下做作业时候遇到的一些问题和难点，主要是记录一下做作业的思路，不会涉及具体实现代码。如果后面遇到没学过的内容可能会整理听课的笔记。

Lab 1 介绍

Lab 1 主要是熟悉 xv6 以及一些常见的 system calls。实验配置以及源代码框架参考: lab tools page。用 Linux 和 MacOS 都比较简单，这里不再赘述。下面看看这次要的 5 个问题。

sleep (easy)

Implement the UNIX program sleep for xv6; your sleep should pause for a user-specified number of ticks. A tick is a notion of time defined by the xv6 kernel, namely the time between two interrupts from the timer chip. Your solution should be in the file user/sleep.c.

题目很简单，只需要了解如何使用 sleep 这个 system call 即可。对于不熟悉的 system call 可以在 https://man7.org/linux/man-pages/index.html 这里查找 linux 的类似 system call 的用法，可以帮助理解。例如 Linux 的 sleep。这样也能熟悉 Linux 常见命令的操作。之后涉及 system call 我都会放一个 linux 上的相关命令用法作为参考。

pingpong

Write a program that uses UNIX system calls to ‘‘ping-pong’’ a byte between two processes over a pair of pipes, one for each direction. The parent should send a byte to the child; the child should print “<pid>: received ping”, where <pid> is its process ID, write the byte on the pipe to the parent, and exit; the parent should read the byte from the child, print “<pid>: received pong”, and exit. Your solution should be in the file user/pingpong.c.\

这道题主要是让我们了解如何创建进程以及进行进程间通信的其中一种方法（管道）：

使用 fork() 可以创建进程，参考 fork(2)，常见用法如下：

int pid;
pid = fork();
if (pid != 0)
{
    // 主进程
}
else
{
    // 子进程
  
    // 如果 if-else 之后还有操作的话，
    // 最好在完成操作之后最好用 exit(0) 退出，不要脱离当前 else 作用范围进行和主进程一样的操作
    exit(0);
}

使用 pipe() 可以创建一个管道，每个管道有两个整型标识符，分别用于写入和读取，参考 pipe(2)，常见的用法如下：

// 存储 *一个* 管道的写入和读取标识符。
int fd[2];

// 创建管道，正常情况下创建后 fd[0] 为读取标识符， fd[1] 为写入标识符
int p = pipe(fd);

if (p == -1) {
    // 创建管道失败
}

...

{
    ...
    // 某进程中写入 1 个字节
    char buf[1];
    write(fd[1], buf, 1);
    ...

    // 在当前进程关闭写入端，不影响其他进程对于这个管道的写入端
    close(fd[1]);
}

...
{
    // 某进程中读取 1 个字节
    // 在写入管道没有关闭但是也没有写入数据时该进程会停止 `read()` 指令直到管道被写入可以读取相应字节数的数据
    char buf[1];
    read(fd[0], buf, 1);

    // 关闭读取端
    close(fd[0]);
}

这道题的具体做法思路是：通过 pipe() 创建两个管道（虽然每个管道都可以写入读取，这道题要求我们将其作为一个单向管道，其中一个管道由主进程写入，子进程读取；另一个管道则相反）。然后通过 fork() 创建子进程，然后通过这两管道进行通信即可，具体顺序是：

假设有管道 p1 p2，进程 1 和 2

1 向 p1 写入一个字节，然后等待并从 p2 读取一个字节，然后输出相应信息，退出（可以预先关闭 p1 不用的读取端，p2 不用的写入端）
2 等待并从 p1 读取一个字节，输出相应信息，然后往 p2 写入一个字节，退出

由于读取有先后顺序（2 只有在读取了字节后才会往 p2 写入数据，1 才能读取）所以输出顺序是 2 再到 1

primes

Write a concurrent version of prime sieve using pipes. This idea is due to Doug McIlroy, inventor of Unix pipes. The picture halfway down this page and the surrounding text explain how to do it. Your solution should be in the file user/primes.c.

Your goal is to use pipe and fork to set up the pipeline. The first process feeds the numbers 2 through 35 into the pipeline. For each prime number, you will arrange to create one process that reads from its left neighbor over a pipe and writes to its right neighbor over another pipe. Since xv6 has limited number of file descriptors and processes, the first process can stop at 35.

首先理解题意，这里我的理解是：

假设要从 2 ~ 35 中输出所有质数，操作如下：
主进程首先创建子进程 1 以及和子进程 t1 沟通的管道 p1，并且在 p1 中写入 2 ~ 35
子进程 t1 从 p1 中依次读取数字，将第一个读取到的数字 2 作为质数，创建子进程 t2 以及相应的沟通管道 p2，将 2 ~ 35 中不能被 2 整除的数字写入 p2，这样就筛掉一部分非质数
子进程 t2 从 p2 中依次读取数字，将第一个读取到的数字 3 作为质数，创建子进程 t3 以及相应的沟通管道 p3，接下来如此类推，直到某个被创建的子进程读不到数据为止。

理清了逻辑之后，写代码思路就比较清晰了，对每一个进程，逻辑大概如下：

// 接受与左侧（父进程）沟通的管道 id
void prime(left_write_id, right_write_id)
{

// 关闭左侧写入管道（不需要向父进程发送数据）

// 创建右侧管道并关闭读取端（向子进程写入数据）

// 传建子进程

/*
 * 子进程逻辑（递归调用 prime）：
 * prime(右侧管道 id)
 * 当前进程逻辑：
 * 1. 从左侧管道读取数据
 * 2. 第一个数据输出作为质数
 * 3. 剩余数据判断能否被第一个数整除，不能则向右侧管道写入
 */
}

find

Write a simple version of the UNIX find program: find all the files in a directory tree with a specific name. Your solution should be in the file user/find.c.

这道题要求我们实现 Unix 中的 find 命令，不需要提供选项，只要求在给定搜索范围以及文件名的情况输出所有符合该文件名的文件路径（相对于搜索路径）即可，主要涉及以下两个问题：

给的一个文件（文件路径）怎么判断文件名是要搜索的文件名？
怎么（递归地）读取一个路径中的所有文件？

下面一个个来看：

给的一个文件（文件路径）怎么判断文件名是要搜索的文件名？

文件路径是以 / 进行分割的，由于这里不考虑后缀，所以给定一个 char* 文件路径只需要从往前遍历找到第一个 / 的位置，返回该位置往后偏置一位的地址即可（char* 类型）。对比两个 char* 使用 strcmp()；

给定一个路径，怎么（递归地）读取一个路径中的所有文件？

首先，通过 kernel/fs.h 中的 fstat 可以读取路径信息，具体包括：

#define T_DIR     1   // Directory
#define T_FILE    2   // File
#define T_DEVICE  3   // Device

struct stat {
  int dev;     // File system's disk device
  uint ino;    // Inode number
  short type;  // Type of file      -- 我们要关注的
  short nlink; // Number of links to file
  uint64 size; // Size of file in bytes
};

这里我们主要用来判断该路径是文件还是文件夹，用法如下：

int fd = open(path, 0);     // fd 作为文件标识符
struct stat st;             // st 用来存储文件信息
fstat(fd, &st);             // 读取文件信息存入 st

if (st.type == T_FILE) {}   // 打开的是文件（按第一部操作使用当前路径判断）
if (st.type == T_DIR)  {}   // 打开的是文件夹

题目中提示有让我们参考 user/ls.c 来进行文件夹信息的读取，user/ls.c 的函数实现如下，其中用到的 struct dirent 如下：

// 见 kernel/fs.h

struct dirent {
  ushort inum;
  char name[DIRSIZ];
};

user/ls.c 相关函数如下：

void
ls(char *path)
{
  // buf 用来存储路径
  char buf[512], *p;
  int fd;
  struct dirent de;
  struct stat st;
  
  // 打开文件路径，并判断是否成功
  if((fd = open(path, 0)) < 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_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;
    }

    // 将当前路径存入 buf 中，并在最后加入 '/' 为重复构建子路径作准备
    // 注意，完成该操作后， buf 包括：当前路径 + '/'，p 指向 '/' 的下一位
    strcpy(buf, path);
    p = buf+strlen(buf);
    *p++ = '/';

    // 依次读取 struct dirent, 每一个 de 代表文件夹下的一个文件，直到读不了为止
    while(read(fd, &de, sizeof(de)) == sizeof(de)){
      if(de.inum == 0)
        continue;
      /*
       * de.name 表示该文件的文件名（可能是 "."（当前目录）， ".."（上层目录））
       * 这里主要是将 de 的 name 复制到 p 指向的位置，与当前路径合并作为该文件的完整路径，并在最后加 '0' 构建字符串
       * 注意由于这里 p 的位置没有发现，所以下一次循环重复复制后就可以保持当前路径只更新文件名了
       * 这也是为什么末尾要补 '0' 提示字符串终止位置的原因之一。
       */
      memmove(p, de.name, DIRSIZ);
      p[DIRSIZ] = 0;

      if(stat(buf, &st) < 0){
        printf("ls: cannot stat %s\n", buf);
        continue;
      }

      /* ls 只用打印出来即可，这里我们要递归地对 buf 存储的路径（当前路径 + '/' + 文件名）进行 `find()` 操作
       * 这里我们可以不用进行文件类型判断操作，只需要在 下一次 find 中判断即可，但是需要判断文件名是否为 "." 或
       * 者 "." 如果是的话不用进行 find 否则会进入死循环
       */
      printf("%s %d %d %d\n", fmtname(buf), st.type, st.ino, st.size);
    }
    break;
  }
  close(fd);
}

xargs

Write a simple version of the UNIX xargs program: read lines from the standard input and run a command for each line, supplying the line as arguments to the command. Your solution should be in the file user/xargs.c.

这一题要求我们实现 UNIX 的 xargs 命令。其基本用法是将标准输入流中按行读取字符串作为 xargs 后命令的参数，如：

echo "1\n2" | xargs -n 1 echo line

echo "1\n2" | 将 echo 的输出重定向至标准输入流中，再通过 xargs 后的命令 echo 执行，这里这里用两行，因此执行两次，每次都将字符串插入到 echo line 后面，因此输出为：

$ echo "1\n2" | xargs -n 1 echo line
    line 1
    line 2

题目中主要涉及：

怎么提取要执行的命令以及已有参数
怎么从标准输入流中按行逐个读取参数
给定命令和参数后怎么执行该命令且不妨碍后续操作

下面分别看一下：

第一步提取已有参数很简单，直接从 main() 入口中的 argv 从 argv[1] 获取至最后即可，可以存在另一个 char* [] 变量中。
我们可以初始化一个 char buf[MAX_SIZE] 数组用来存放输入流读取的数据，执行以下步骤：
- 使用 int n = read(0, buf, sizeof(buf) - 1) 函数可以进行读取，第一个 0 表示从标准输入流中提取，这里我们由于不知道每个参数有多擦汗那个，所以每次读取都尽可能填满 buf，最后空一位是为了填充 '\0' 使其变成一个字符串，这样我们才能用字符串相关函数，并且只有第一次读取才是从 buf 起始位置开始填充，之后读取要考虑 buf 中剩余已有的数据（read() 返回的 n 表示这次实际读取了多少个字节）
- 读取完之后使用 int q = strchr(buf, '\n') 可以找到第一个 \n 从而获取一行参数（即 buf 到 q 之间的字符，以空格分隔），同样在该段字符串循环查找 ' ' 即可获取一行中的各个参数，填充进参数列表数组即可。填充完后继续在 buf 中继续往后查找 \n 进行类似操作
- 当查找不到 \n 时，将剩余的字节复制到 buf 起始位置，重新从标准输入流中读取数组填充 buf，直到实际读取字节数为 0 为止
- 这些操作中间要注意的地方是时刻关注要操作的指针位置，具体包括以下几个：
  - 从标准输入流中读取数据：假设上一次操作后最后剩下 m 个字节，那么读取数据的起始填充位置位置应该是 buf + m，最大读取个数是 sizeof(buf) - m - 1
  - 查找 \n 的位置：假设上一步中提取到了 n 个字节，那么查找的位置应该按以下规律变化：
    - 第一次查找： p = buf，查找到位置在 q
    - 第二次查找： p = q + 1，以此类推
  - 查找 ' ' 的位置：和前一步类似
获取了每一次参数列表后，可以用 exec() 来进行，exec() 接收两个参数，一个为执行的系统调用，另一个为参数列表，执行 exec() 时会覆盖当前进程，因此我们需要使用 fork() 来传建子进程调用 exec()，主进程（使用 exit(0)）等待 exec() 完后进行执行下一步即可。

其他

fprintf 的用法：

作业代码中经常见到 fprintf(2, "ls: cannot open %s\n", path);，这里后面两个参数是输出内容，第一个数字表示输出位置的标识符，例如：

// 将 "We are in 2014" 写入 file.txt 中
FILE * fp;

fp = fopen ("file.txt", "w+");
fprintf(fp, "%s %s %s %d", "We", "are", "in", 2014);

C 中有一些常见的标识符为： 0 - 标准输入流，1 - 标准输出流，2 - 标准错误流

exit 和 return 的区别

return 是函数返回，exit() 是结束当前进程，exit() 可以可以返回不同值表示不同结束状态，例如：exit(0) - 程序正常退出；exit(1) - 程序非正常退出。

假如有两个进程， p1 和 p2, p1 为父进程，在父进程中调用 wait(s) (int* s)，可以等待 p2 退出再进行往之后，p2 退出之后 p1 中的 s 指向的空间会存有 p2 退出的返回值。

在 main() 中 return 0 和 exit(0) 作用一样。