M1: 打印进程树 (pstree)
注意事项
请特别注意 academic integrity：“看见” 他人的代码、使用他人测试用例都是不道德的行为。只有遵守 academic integrity 才会使你受到真正的训练。在这个实验中，你应当主动地避免阅读任何人 (包括互联网) 上打印进程树或进程列表的代码，但可以查看 API (如 readdir 等) 的使用方法和例程。遇到问题时尽量自己调试解决，但可以向他人请教调试的技巧。
关于实验环境设置、提交方法、评分规则等，请阅读实验须知。获取代码后，在
os-workbench中执行git pull origin M1下载代码。
Soft Deadline: 2020 年 3 月 28 日 23:59:59。
1. 背景
操作系统能同时运行多个程序。大家都用过任务管理器——能够显示当前系统运行的状态、进程、处理器占用等等。
上图是一个典型的 “任务管理器” (来自 Deepin)。用户友好的界面显示了系统资源的使用情况和进程的信息。当然，“友好地显示” 并不是这门课的主题。作为操作系统课，我们更关注的问题其实是任务管理器也是操作系统上的应用程序。从应用程序的视角看，操作系统就是 “一组对象和操作它们的 API 规约” (例如在 x86-64 系统上，应用程序通过 syscall 指令调用操作系统 API)。
那么应该用什么样的 API 获取系统中有哪些正在运行的进程？在过去学习编程的过程中，相信大家已经使用过很多 API，例如：
- 打开文件会涉及到
open系统调用 (打开一个操作系统中的文件)； printf最终会调用write系统调用，向编号为 1 的文件描述 (操作系统中的对象) 符写入数据……
这些操作系统 API 对我们来说都是自然而然的——但操作系统上并不是所有程序都那么 “简单”，操作系统 API 可以用来实现任何应用软件，包括任务管理器这样的 “系统软件”。我们不妨站在操作系统设计者的角度上，考虑应该提供什么样的 API 来获取操作系统中运行的程序。
你可能会很自然地想到，操作系统可以提供一个类似迭代器的 API，可以在某个时刻对进程列表进行 “快照”，然后程序可以通过 API 迭代快照里的进程。
Snapshot *CreateProcessSnapshot(); // 迭代开始
Process *FirstProcess(Snapshot *snapshot); // 取得第一个进程
Process *NextProcess(Process *process); // 获得下一个进程
int ReleaseProcessSnapshot(Snapshot *snapshot); // 迭代结束
Windows API 就是这么设计的——没毛病。不过这么做也会使操作系统 API 的数量暴涨，因为所有事情都要通过特定的 API 完成——如果考虑 Windows API 动态链接库导出的符号，那么仅 Kernel 和 GDI 的 Windows API 就在 1,000 个以上。
UNIX 操作系统的设计者用另一种方法使应用程序能访问进程列表：提供一个操作系统的对象 (文本文件)，这样应用程序就能用文件 API (open, read, close) 来获取进程列表。例如，创建一个名为 /system/processes.yaml 的文件:
- pid: 1
parent: -1
command: /bin/init
- pid: 2
parent: 1
command: /bin/bash
这就是 everything is a file 的设计。换句话说，我们可以把操作系统的状态变成文件系统的一部分——这么做在文件系统里添加了很多对象，但 API 却没有变化 (当然这么做有好有坏)。在这个实验中，我们学习 UNIX/Linux 是如何把操作系统的状态放在文件系统中的。虽然这个实验里你只需要读取进程列表和进程之间的父子关系，但用类似的办法，也可以从 Linux 系统中读取出 CPU 占用率、内存使用等信息——于是你也可以实现自己的任务管理器了！
2. 实验描述
实验要求：实现
pstree，打印进程之间的树状的父子关系Linux 系统中可以同时运行多个程序。运行的程序称为进程。除了所有进程的根之外，每个进程都有它唯一的父进程，你的任务就是把这棵树在命令行中输出。你可以自由选择展示树的方式 (例如使用缩进表示父子关系，这是最容易的)。
Linux 系统自带了 pstree 命令，进程树会以非常漂亮的格式排版 (每个进程的第一个孩子都与它处在同一行，之后的孩子保持相同的缩进)：
systemd─┬─accounts-daemon─┬─{gdbus}
│ └─{gmain}
├─acpid
├─agetty
├─atd
├─cron
├─dbus-daemon
├─dhclient
├─2*[iscsid]
├─lvmetad
├─lxcfs───10*[{lxcfs}]
├─mdadm
├─polkitd─┬─{gdbus}
│ └─{gmain}
├─rsyslogd─┬─{in:imklog}
│ ├─{in:imuxsock}
│ └─{rs:main Q:Reg}
...
Linux 的 psmisc 中 pstree 的实现大约有 1,300 行，支持多种命令行参数。这个实验里实现最简单的就行。大家可以先玩一下 Linux 的 pstree，使用 man 命令查看 pstree 支持的功能，并试一试。在这个实验中，我们需要实现它的简化版：
2.1 总览
2.2 描述
把系统中的进程按照父亲-孩子的树状结构打印到终端。
-p,--show-pids: 打印每个进程的进程号。-n--numeric-sort: 按照pid的数值从小到大顺序输出一个进程的直接孩子。-V--version: 打印版本信息。
你可以在命令行中观察系统的 pstree 的执行行为 (如执行 pstree -V、pstree --show-pids 等)。这些参数可能任意组合。
2.3 解释
上述实验要求描述是参照 man page 的格式写出的，其中有很多 UNIX 命令行工具遵守的共同约定 (UNIX 的资深用户对此了如指掌；但对给初学者，尤其是从出生以来就生活在 GUI 环境中而不是遇事就读手册的大家造成了很大的困扰)，例如 POSIX 对命令行参数有一定的约定，从中摘抄一些约定如下：
- 中括号扩起的参数是可选参数，
[]后的…代表参数的 0 次或多次重复。因此-p,-n,-V都是可选的参数。 - 同一个选项可以有不同的名字。在
pstree中，-p和--show-pids的含义是一样的。 - 若不另行说明，整数范围在 32 位有符号整数范围内；但如果数值和文件大小有关，则其合法的范围是是 0 到系统最大支持的文件大小 (以后会遇到有数值的参数)。
此外，main 函数的返回值代表了命令执行的状态，其中 EXIT_SUCCESS 表示命令执行成功，EXIT_FAILURE 表示执行失败。对于 POSIX 来说，0 代表成功，非 0 代表失败：例如 diff 返回 1 表示比较的文件不同，返回 2 表示读取文件失败 (cmp 的行为也类似)。UNIX Shell 对返回值有额外的处理。这解释了为什么一些 OJ 会明确要求 main 函数返回值为 0，当返回非 0 时将被认为是 Runtime Error。
Online Judge 的要求
main函数返回非 0 将在 Online Judge 中被判定为 Runtime Error。
如果不知道这些约定，使用 Linux/Unix 的时候就会举步维艰。Unix 世界有一套自己定义的 “游戏规则”。也难怪会有笑话：
Unix is user-friendly — it's just choosy about who its friends are.
当然，在渐渐熟悉游戏规则以后就会发现，这套设计简洁好用 (但也有很多人批评它不够优雅、不够严谨)。如果你的目标是用最短的时间把事情搞定，用 Shell 和各种命令行工具的组合一定是你的第一选择，记住：Keep it simple, stupid 和 Everything is a file.
3. 正确性标准
你可以任意选择树的形态，以下输出都是合法的：
$ ./pstree-64
systemd─┬─accounts-daemon─┬─
│
...
$ ./pstree-64
systemd
|
+--accounts-daemon-
|
...
$ ./pstree-64
systemd
accounts-daemon
...
只要输出系统中的进程即可；此外，允许进程列表有轻微出入。细心的同学可能发现你第一个版本的 pstree 可能和系统输出不太一样。在线评测会容忍你输出的一些缺陷；此外，作为第一个实验，我们会手下留情，没有非常强劲的测试数据。但你仍然需要确保：
- 正确列出系统中的进程，并正确实现参数组合的行为；
- 编写可移植的代码。我们会同时测试 32-bit 和 64-bit 的版本。
在 Hard Test 上 Wrong Answer？
试一试
pstree -V | less，你会发现小惊喜。我们希望你的行为和系统中的pstree -V基本一致：输出到正确的输出流、包含pstree的基本信息，但版本描述可以不同。
4. 实验指南：把大象装进冰箱
想自己尝试？
鼓励大家忽略下面的教程，自己动手搞定，遇到不明白的地方可以求助 Google (Bing, Stackoverflow, ...)。完成之后可以看一下实验指南，看自己的理解是否有可以改进的空间。
- “把大象放进冰箱总共分几步？” “三步，第一步把冰箱门打开；第二步把大象放进去，第三步把冰箱门带上。” — 赵本山、宋丹丹《钟点工》
如果你觉得打印进程树这个问题比较困难，我们也把问题分解一下：
- 得到命令行的参数，根据要求设置标志变量的数值；
- 得到系统中所有进程的编号 (每个进程都会有唯一的编号) 保存到列表里；
- 对列表里的每个编号，得到它的的父亲是谁；
- 在内存中把树建好，按命令行参数要求排序；
- 把树打印到终端上。
因为人的脑容量有限，通常解决问题的办法就是把比较复杂的问题分解成小问题，再把小问题继续分解下去。而在学校里所做的训练就是建立问题分解的思路和培养解决问题的能力。
4.1. 命令行参数
获取命令行参数的一小段代码：
#include <stdio.h>
#include <assert.h>
int main(int argc, char *argv[]) {
for (int i = 0; i < argc; i++) {
assert(argv[i]); // C 标准保证
printf("argv[%d] = %s\n", i, argv[i]);
}
assert(!argv[argc]); // C 标准保证
return 0;
}
可以在终端里试试给这个程序传入不同的参数会输出什么，获取命令行参数的。这个问题就算是很好地解决啦：argv[0], ..., argv[argc-1] 就是所有命令行的参数，这是操作系统与 C 程序之间的约定。在 ICS PA 中我们已经知道 getopt (man 3 getopt) 可以处理命令行参数，不过如果你想实际体验一下编程，你也可以自己动手实现 getopt 的功能。
之后会反复编译运行这个程序，所以编译和测试自动化非常重要。比较常见的项目组织是编写 Makefile，在命令行中使用 make 实现编译，make test 完成测试。我们已经为大家提供了 Makefile，欢迎大家仔细阅读。IDE 或流行的编辑器 (例如 vscode) 支持使用自定义的 Makefile。
提示
回想一下大家做 OJ 题的过程。在编程的过程中，难免会经历修改代码 $\to$ 编译 $\to$ 运行 $\to$ 修改代码……这样的循环。你会选择怎么做呢？新手每次都键入命令 (或者他发现 Ctrl-p 可以重复命令)。
- 之后，有同学人发现，可以把命令写在一行里，比如
gcc a.c && ./a.out，一键就能编译运行了。- 再之后会发现可以写个 Makefile (就像这个实验一样)，用
make test跑完所有测试。- 再之后会发现可以每次在文件改动以后自动运行所有测试……有个神奇的命令叫
inotifywait。即便现在有 IDE 和丰富的插件，UNIX 哲学依然是无处不在的 (甚至是这些 IDE 的组成基础)，说得更具体一点，“只要你敢想，就一定能做到”。祝大家编程愉快。
最后，以下两点有助于调试时放平心态：(1) 机器永远是对的；(2) 未测代码永远是错的。
4.2. 得到系统中进程的编号
进程是操作系统中的对象，因此操作系统一定提供了 API 访问它们。已经剧透过，系统里的每个进程都有唯一的编号，它在 C 语言中的类型是 pid_t。不知道这是什么？Google 一把就知道啦。你能找到 glibc 对它的官方文档解释。以后遇到问题要自己找答案哦！
操作系统以什么样的方式让你获取系统里的进程呢？之前也提示过：
Everything is a file.
一切皆文件，进程信息当然也可以是 “一切” 的一部分。Linux 提供了 procfs，目录是 /proc。如果你进去看一眼，就会发现除了一些比如 cpuinfo 这样的文件，还有很多以数字命名的目录——聪明的你也许已经猜到了，每个目录的名字就是进程号，目录里存储了进程相关的运行时数据。
可以先玩一会儿，用 cat 可以打印文件的值，可以把文件的内容打出来看看，再对照文档。
现在的问题就变成：怎样得到 /proc 目录下的所有以数字为开头的目录。如果你找对关键字，会发现有很多种方法，一定要自己试一试哦。
4.3. 得到进程之间的关系
procfs 里还有很多有趣的东西，每个进程的父进程也隐藏在 /proc/[pid]/ 中的某个文件里。试试 man 5 proc，里面有详细的文档。还有，很多 Online Judge 都使用 procfs 读取进程的运行时间/内存数据。
就像一个普通的文件一样，你可以用你熟悉的方式打开 procfs 里的文件：
FILE *fp = fopen(filename, "r");
if (fp) {
// 用fscanf, fgets等函数读取
fclose(fp);
} else {
// 错误处理
}
procfs 里的信息足够让你写一个非常不错的任务管理器。也许有同学在实验开始的时候就已经想到——如果你想实现一个任务管理器并且不太会的话，我们可以看一看系统的任务管理器是怎么实现的嘛！我们在课堂上已经演示过 gcc 和 xedit 的例子，就用 strace 工具就能查看进程运行时的系统调用序列：
$ strace ps
...
openat(AT_FDCWD, "/proc/1/stat", O_RDONLY) = 6
read(6, "1 (systemd) S 0 1 1 0 -1 4194560"..., 1024) = 190
close(6) = 0
...
4.4. 建树和打印
这是数据结构方面的内容，这门课不会涉及啦。把它当一个 OJ 题就好了——互联网公司很可能会用类似的题目来考察面试者的基本能力。如果你没有头绪，试着定义一个递归函数 $f(T) = [s_1,s_2,\ldots,s_n]$ 把 $T$ 打印成多行文本 (第 $i$ 行是字符串 $s_i$)。
- 对于叶子节点，直接输出一个格式化字符串 (例如使用
asprintf)； - 如果不是叶子节点，对它所有子树 $T_1, T_2, \ldots T_k$ 分别求 $f_i(T_i)$，得到 $k$ 个多行的文本；
- 把这些字符串拼到适当的位置，加上一些连接线：
(root)─+─T1(line 1)
| T1(line 2)
| T1(line 3)
+─T2(1)
|
...
然后你会发现你并不需要真的实现 $f(T)$，而是一遍递归一边打印就行。
4.5. 写出正确的代码
完成了？
是时候问问自己：我的程序对吗？
虽然在这个实验里，我们的测试用例相对简单；但在未来的实验中，Online Judge 可能会在各种奇葩的条件下运行你的程序哦！除了你们做的 OJ 题中会有复杂的逻辑 (参数的组合) 导致 bug 之外，和系统打交道的编程可有更多的麻烦之处：
- 你的程序遵守 POSIX 的返回值规定吗？如果你的 main 函数返回了非 0 的数值，我们将认为程序报告了错误——在非法的输入上返回 0，以及在合法的输入上返回非 0 都将导致 Wrong Answer。
- 程序够 roubust 吗？它会不会在一些非法的输入上 crash？如果系统里的进程很多呢？如果内存不够了呢？如果
open或者malloc失败了呢？要知道，crash 一般是因为 undefined behavior (UB) 导致的——UB 没把所有的文件都删掉真是谢天谢地了。 - 万一我得到进程号以后，进去发现文件没了 (进程终止了)，怎么办？会不会有这种情况？万一有我的程序会不会 crash……？
- 进程的信息一直在变，文件的内容也一直在变 (两次
cat的结果不同)。那我会不会读到不一致的信息(前一半是旧信息、新一半是新信息)？这两个问题都是 race condition 导致的；我们将会在并发部分回到这个话题。 - 如果我不确信这些事会不会发生，我有没有写一个程序，至少在压力环境下测试一下它们有没有可能发生？嗯，如果我同时运行很多程序，每个程序都不断扫描目录、读取文件，也观察不到这个问题，至少应该可以放点心。
随着课程的深入，这些问题都会得到解答。
当你的程序越来越复杂，这些问题也许将会成为你挥之不去的阴影。这就对了——从 Intel 的 CPU 到 Linux Kernel 都有数不清的 bug。你也许听说过 “形式化验证”，但事实也证明，经过验证正确的编译器 (CertComp) 和文件系统 (FSCQ) 都依然存在 bug。
写出正确的代码远比想象中困难——目前地球上还没人能保证复杂的系统没有 bug 和漏洞。我个人热切盼望着没有 bug 的那一天的到来，不过似乎遥不可及。不过也不用太绝望，这门课里会教给大家一些有关 “写代码” 的知识，更重要的是正确的思维方式 (“世界观”)：操作系统会提供什么、该提供什么、不该提供什么、应该怎么提供。
