热身运动，实现一些 shell 命令。
Boot xv6
首先去 lab tool page 把实验所需工具都给装上，然后查看一下各个工具的版本，检查是否安装成功。
1$ tool --version
获取代码，切换到实验对应分支，准备开撸。
1$ git clone git://g.csail.mit.edu/xv6-labs-2021
2$ cd xv6-labs-2021
3$ git checkout util
输入
make qemu可以编译所有代码并模拟内核环境，输入ctrl+a x以退出环境。
Task1: sleep
该任务要求实现 sleep 命令，模式为
1$ sleep 时间值
这个任务就是帮助我们熟悉整个代码框架，以及一些头文件。
比如框架为我们提供了系统调用，位于头文件 user/user.h 中，以及 kernel/types.h 为我们提供了类型定义。这两个头文件在后面都是需要 include 的。
在 user/ 文件夹下 touch 一个新文件，然后写入代码：
1#include "kernel/types.h"
2#include "user/user.h"
3
4int
5main(int argc, char *argv[])
6{
7 if (argc < 2) {
8 fprintf(2, "Usage: sleep seconds...\n");
9 exit(1);
10 }
11
12 int ticks = atoi(argv[1]); // 自带的库函数，定义位于 user/ulib.c
13 sleep(ticks); // user.h 中的系统调用
14 exit(0); // 每个进程都要调用 exit(0) 正常退出
15}
与此同时，还要修改 Makefile 里头 UPROGS 变量，在后面加上 $U/_sleep\ 即可正确编译。编译后，我们可以进入 qemu 并调用 sleep 看看效果：
1$ make qemu
2$ sleep 10
3(nothing happens for a little while)
也可以用 lab 自带的 python 脚本 grade-lab-util [test-name]
1$ ./grade-lab-util sleep
2...
3== Test sleep, no arguments == sleep, no arguments: OK (3.6s)
4== Test sleep, returns == sleep, returns: OK (0.6s)
5== Test sleep, makes syscall == sleep, makes syscall: OK (1.0s)
Task2: pingpong
该任务要求我们利用 pipe() 和 fork() 两大系统调用进行父子进程间的同步：
- 父进程通过管道发送一个字节给子进程；
- 子进程收到后，打印一条消息，然后将该字节返回给父进程，退出；
- 父进程等待子进程运行完毕，再进行读取，这样做是防止读到自己已经写入的内容。收到后，打印一条消息，然后退出；
首先是管道的创建。int pipe(int *fd) 会将 fd[0] 设置为读端，fd[1] 设置为写端，并返回调用是否成功（返回 -1 表示创建管道失败）
再是进程的创建。int fork() 会在当前进程 parent 的基础上创建一个新进程 child，child 相当于是 parent 的副本——拷贝了所有内容，唯一的区别在于这俩进程不共享地址空间，也就是说在 child 中修改全局变量并不会影响到 parent 里的全局变量，毕竟只是副本。对于父进程，fork 会返回子进程的 pid；而对于子进程则返回 0。
最后等待子进程运行完毕需要用到 wait(int *)，传入的是子进程 pid 的指针，如果传入 0 意为等待所有子进程结束。
有了这些预备知识，代码就很好编写了：
1#include "kernel/types.h"
2#include "user/user.h"
3
4#define ONEBYTE sizeof(char)
5
6int
7main(int argc, char *argv[])
8{
9 int fd[2]; // fd[0] 为读端, fd[1] 为写端
10 if (pipe(fd) < 0) {
11 fprintf(2, "pingpong: pipe failed\n");
12 exit(1);
13 }
14
15 // 1. The parent should send a byte to the child;
16 // 2. the child should print "<pid>: received ping", where <pid> is its process ID,
17 // and write the byte on the pipe to the parent, and exit;
18 // 3. the parent should read the byte from the child, print "<pid>: received pong", and exit.
19 int pid = fork();
20 if (pid > 0) { // parent
21 char *buf = (char*)malloc(ONEBYTE); // an one-byte memory
22 if (write(fd[1], buf, ONEBYTE) != ONEBYTE) {
23 fprintf(2, "pingpong: proc %d write failed\n", getpid());
24 free(buf);
25 exit(1);
26 }
27
28 wait(&pid); // 如果不加这步，则下面的 read 可能会抢先拿出自己 write 的数据
29
30 if (read(fd[0], buf, ONEBYTE) < 0) {
31 fprintf(2, "pingpong: proc %d read failed\n", getpid());
32 free(buf);
33 exit(1);
34 }
35
36 printf("%d: received pong\n", getpid());
37 free(buf); // malloc 后跟 free 防止内存泄漏
38 } else if (pid == 0) { // child
39 char* buf = (char*)malloc(ONEBYTE);
40 if (read(fd[0], buf, ONEBYTE) < 0) {
41 fprintf(2, "pingpong: proc %d read failed\n", getpid());
42 free(buf);
43 exit(1);
44 }
45
46 printf("%d: received ping\n", getpid());
47
48 if (write(fd[1], buf, ONEBYTE) != ONEBYTE) {
49 fprintf(2, "pingpong: proc %d write failed\n", getpid());
50 free(buf);
51 exit(1);
52 }
53 free(buf);
54 } else {
55 fprintf(2, "pingpong: fork failed\n");
56 exit(1);
57 }
58
59 exit(0);
60}
修改完 Makefile 后进行测试，结果如下：
1$ ./grade-lab-util pingpong
2...
3== Test pingpong == pingpong: OK (1.3s)
Task3: primes
该任务是上一个任务的 plus 版本，编写一个并发输出 2~35 之间所有素数的程序，算法思想见这个网页。
在这里，就是对于每一个进程 p，不断接收其父进程 parent 写入管道的数据。对于第一个收到的数据 n，直接打印，对于后续的数据 data，如果满足 data % p != 0，说明该数可能是个素数，通过管道交给子进程 child。
由于所有的管道都是单向的，即从 parent 流向 child，故每个进程需关闭左侧（与 parent 交互）管道的写端与右侧（与 child 交互）的读端，防止文件描述符不够用的情况。
注意到，由于范围内的最后一个素数是 31，所以收到并打印 31 以后就不用再进一步创建子进程，反之，打印完素数后进一步 fork()，这也指明了递归终止的条件（创建子进程相当于一个递归的过程）。同时，最左侧进程（也就是主进程）只能写不能读，那就干脆不让他打印了，只往管道写数据好了。
代码如下：
1#include "kernel/types.h"
2#include "user/user.h"
3
4void
5createNewProc(int p, int *left)
6{
7 int right[2];
8 if (pipe(right) < 0) {
9 fprintf(2, "primes: pipe failed\n");
10 exit(1);
11 }
12
13 int pid = fork();
14 if (pid > 0) {
15 close(right[0]);
16 int n;
17 while (read(left[0], &n, sizeof(int)) == sizeof(int)) {
18 if (n % p != 0) {
19 if (write(right[1], &n, sizeof(int)) != sizeof(int)) {
20 fprintf(2, "primes: proc %d write failed\n", getpid());
21 exit(1);
22 }
23 }
24 }
25 close(right[1]);
26 wait((int*)0);
27 } else if (pid == 0) {
28 close(right[1]);
29
30 int p;
31 read(right[0], &p, sizeof(int));
32 printf("prime %d\n", p);
33
34 if (p != 31) {
35 createNewProc(p, right);
36 }
37 } else {
38 fprintf(2, "primes: fork failed\n");
39 exit(1);
40 }
41}
42
43int
44main(int argc, char *argv[])
45{
46 int fd[2];
47 if (pipe(fd) < 0) {
48 fprintf(2, "primes: pipe failed\n");
49 exit(1);
50 }
51
52 int pid = fork();
53 if (pid > 0) {
54 close(fd[0]); // 关闭用不到的
55 for (int i = 2; i <= 35; i++) {
56 if (write(fd[1], &i, sizeof(int)) != sizeof(int)) {
57 fprintf(2, "primes: proc %d write failed\n", getpid());
58 exit(1);
59 }
60 }
61 close(fd[1]); // 写完了就关掉，防止不够用
62 wait((int*)0);
63 } else if (pid == 0) {
64 close(fd[1]); // 关闭用不到的
65 int p;
66 read(fd[0], &p, sizeof(int));
67 printf("prime %d\n", p);
68
69 createNewProc(p, fd); // 第一个打印数据的进程，递归创建子进程进行打印数据
70 } else {
71 fprintf(2, "primes: fork failed\n");
72 exit(1);
73 }
74
75 exit(0);
76}
修改完 Makefile 后进行测试，结果如下：
1$ ./grade-lab-util primes
2...
3== Test primes == primes: OK (0.7s)
Task4: find
该任务要求我们实现一个简单版本的 find 命令。其模式为
1$ find 目录 文件名
user/ls.c 里有读取目录的样例实现。熟悉文件系统的应该知道，目录也是「文件」，也具有 inode 号和相应的磁盘空间，只不过其磁盘块上的内容是若干文件条目，在 lab 中用数据结构 dirent 表示，其内容为 {inode, name}，其中 name 既可以是文件名，也可以是目录名。
所以思路就清晰了：
- 对于每个当前目录
dir，遍历其dirent并利用stat()获取该条目对应的类型； - 如果是文件类型，则判断其
name与待查找的文件名target是否一致，若一致则输出路径； - 如果是目录类型，递归查找，跳过当前目录
.与父目录..；
代码如下：
1#include "kernel/types.h"
2#include "kernel/stat.h"
3#include "user/user.h"
4#include "kernel/fs.h"
5#include "kernel/param.h"
6
7#define BUFSIZE 512
8
9void
10searchFile(char *dir, char *file)
11{
12 int fd; // 指向目录 dir
13 if ((fd = open(dir, 0)) < 0){
14 fprintf(STDERR, "find: cannot open %s\n", dir);
15 exit(1);
16 }
17
18 if (strlen(dir) + 1 + DIRSIZ + 1 > BUFSIZE){ // path + '/' + name + '\0'
19 fprintf(STDERR, "find: path too long\n");
20 exit(1);
21 }
22
23 // 构建路径名
24 char buf[BUFSIZE], *p;
25 strcpy(buf, dir);
26 p = buf+strlen(buf);
27 *p++ = '/'; // buf 当前为 "${dir}/"
28
29 // 遍历目录下所有条目
30 struct dirent de;
31 struct stat st;
32 while (read(fd, &de, sizeof(de)) == sizeof(de)) { // 每次读一整个 dirent 大小
33 if (de.inum == 0 || strcmp(de.name, ".") == 0 || strcmp(de.name, "..") == 0) { // 跳过无效项
34 continue;
35 }
36
37 // 构建文件路径名
38 memmove(p, de.name, DIRSIZ);
39 p[DIRSIZ] = 0;
40 if (stat(buf, &st) < 0) {
41 fprintf(STDERR, "find: cannot stat %s\n", buf);
42 continue;
43 }
44
45 switch (st.type) {
46 case T_FILE: // 检查文件名是否一致
47 if (strcmp(file, de.name) == 0) {
48 printf("%s\n", buf);
49 }
50 break;
51 case T_DIR: // 递归查找子目录
52 searchFile(buf, file);
53 break;
54 }
55 }
56}
57
58int
59main(int argc, char *argv[])
60{
61 if (argc <= 2) {
62 fprintf(2, "Usage: find dir files...");
63 exit(1);
64 }
65
66 for (int i = 2; i < argc; i++) { // 支持同一目录下多文件查找
67 searchFile(argv[1], argv[i]);
68 }
69 exit(0);
70}
修改完 Makefile 后进行测试，结果如下：
1$ ./grade-lab-util find
2...
3== Test find, in current directory == find, in current directory: OK (0.8s)
4== Test find, recursive == find, recursive: OK (1.1s)
Task5: xargs
最后一个任务是实现 xargs 命令。该命令一般配合管道使用，将前一个命令输出，作为后面命令的额外参数，比如
1$ echo hello too | xargs echo bye
2bye hello too
就是将 echo hello too 的输出 hello too 作为 echo bye 的额外参数并附加到末尾，相当于执行了命令 echo bye hello too。这里我们只需实现 -n 1 的版本，即每 1 行输出作为一组额外参数。
1$ echo -e "1\n2" | xargs -n 1 echo line
2line 1
3line 2
4## 前面理论上输出为
5## 1
6## 2
7## 整行命令相当于依次执行了
8## echo line 1
9## echo line 2
对于 xargs 而言，必然前面是出现管道符 | 的，也就意味着有额外参数被写入到标准输出(fd=1)中，那就要从标准输入(fd=0)中读取了。思路很明确了：不断从标准输入中读字符直到 '\n'，意味着完整的参数已被读取，那就调用 exec() 执行命令。
注意到 exec() 会将当前进程替换为新进程，原来那个进程后面就不继续了，所以每次 exec() 都要由主进程 fork() 一个子进程去执行
1#include "kernel/types.h"
2#include "kernel/param.h"
3#include "user/user.h"
4
5int
6main(int argc, char *argv[])
7{
8 // eg: find . b | xargs grep hello
9 char *cmd = argv[1];
10 char *new_args[MAXARG];
11
12 // 先把原本的参数加进去
13 int k;
14 for (k = 0; k < argc-1; k++) {
15 new_args[k] = argv[k+1];
16 }
17
18 char extra_arg[32];
19 int p = 0;
20 // 逐行读取，再把新参数 append 到 new_args 里去
21 while (read(STDIN, extra_arg+p, 1) > 0) {
22 if (extra_arg[p] == '\n') {
23 extra_arg[p] = '\0';
24
25 // 遇到 '\n' 就意味着准备好 exec 了，立马 fork 一个子进程去做。
26 // 记得用 wait 来进行同步
27 int pid;
28 pid = fork();
29 if (pid > 0) {
30 wait(&pid);
31 } else if (pid == 0) {
32 new_args[k] = extra_arg;
33 exec(cmd, new_args);
34
35 // 如果 exec 调用失败才会到这一行
36 fprintf(2, "exec %s failed\n", cmd);
37 exit(1);
38 } else {
39 fprintf(2, "xargs: fork failed\n");
40 exit(1);
41 }
42 p = 0;
43 } else {
44 p++;
45 }
46 }
47 exit(0);
48}
修改完 Makefile 后进行测试，结果如下：
1$ ./grade-lab-util xargs
2...
3== Test xargs == xargs: OK (1.9s)
最后的工作
- 新建一个
time.txt文件，写上总共花了多少小时，然后git commit -am ""将所有修改提交到本地。 - 去网页用邮箱注册，然后收到一封邮件，点击邮件链接会收到一个 key，妥善保管；
- 执行
make handin，输入刚才得到的那个 key，就成功提交了，并且显示当前的课程进度；
可选的挑战再说吧，没有什么想做的欲望。