M1: 打印进程树 (pstree)

1. 背景

因为程序可以看成状态机，操作系统能 “同时运行多个程序” 的能力就是状态机管理的能力。自然，操作系统也应该提供 “监测状态机状态” 的功能，例如显示在一段时间内，各个程序 (进程、状态机) 的活跃程度。

UNIX 采用了 Everything is a File 的设计，把操作系统的状态变成文件系统的一部分：

操作系统会不断更新一个对象 (文本文件) 的内容，这样应用程序就能用文件 API (open, read, close) 来获取进程列表；

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}
        ...

2.1 总览

提供的命令形式如下：pstree [OPTION]…

把系统中的进程按照父亲-孩子的树状结构打印到终端。

-p 或 --show-pids: 打印每个进程的进程号。
-n 或 --numeric-sort: 按照pid的数值从小到大顺序输出一个进程的直接孩子。
-V 或 --version: 打印版本信息。

你可以在命令行中观察系统的 pstree 的执行行为 (如执行 pstree -V、pstree --show-pids 等)。这些参数可能任意组合，但你不需要处理单字母参数合并的情况，例如 -np。

3. 正确性标准

可以任意选择树的形态，以下输出都是合法的：

$ ./pstree-64
systemd─┬─accounts-daemon─┬─
        │
        ...

$ ./pstree-64
systemd
 |
 +--accounts-daemon-
 |
 ...

$ ./pstree-64
systemd
  accounts-daemon
    ...

只要输出系统中的进程即可；此外，允许进程列表有轻微出入。

3.1 注意事项

试一试 pstree -V > /dev/null，你会发现输出并没有到 /dev/null。我们希望你的行为和系统中的 pstree -V 基本一致：输出到正确的输出流、包含 pstree 的基本信息，但版本描述可以不同。

pstree -V是将信息输出到错误流（文件描述符2），而不是输出流（文件描述符1）；

4. 实验指南

打印进程树的问题分解：

得到命令行的参数，根据要求设置标志变量的数值；
得到系统中所有进程的编号 (每个进程都会有唯一的编号) 保存到列表里；
对列表里的每个编号，得到它的的父亲是谁；
在内存中把树建好，按命令行参数要求排序；
把树打印到终端上。

4.1 命令行参数

main函数的签名包含了命令行的参数： ./a.out hello world

argv[0] 是可执行文件名 "./a.out"，后面跟的是参数（空白符作为分隔符）；

int main(int argc, char *argv[])

getopt(man 3 getopt)库可以处理命令行参数，当然也可以自己解析；

4.2 获取所有的进程

ps 命令也是通过 procfs 实现，可以通过 strace ps查看系统调用证明。

openat(AT_FDCWD, "/proc/1/stat", O_RDONLY)

Linux 提供了 procfs，目录是 /proc。

以数字命名的目录，每个目录的名字就是进程号，目录里存储了进程相关的运行时数据。
/proc/[pid]/stat 文件中包含了其父进程的 pid；

4.3 建树和打印

试着定义一个递归函数\(f(T)=[s_1,s_2,…,s_n]\)把 \(T\)打印成多行文本 (第 \(i\)行是字符串 \(s_i\))。

对于叶子节点，直接输出一个格式化字符串 (例如使用 asprintf)；
如果不是叶子节点，对它所有子树\(T_1,T_2,...,T_k\) 分别求\(f_i(T_i)\)，得到 \(k\) 个多行的文本；
把这些字符串拼到适当的位置，加上一些连接线：

(root)─+─T1(line 1)
       | T1(line 2)
       | T1(line 3)
       +─T2(1)
       |
...

然后你会发现你并不需要真的实现 \(f(T)\)，而是一遍递归一边打印就行。

4.4 编译

比较常见的项目组织是编写 Makefile，在命令行中使用 make 实现编译，make test 完成测试。

4.5 测试

程序够 roubust 吗？它会不会在一些非法的输入上 crash？如果系统里的进程很多呢？如果内存不够了呢？如果 open 或者 malloc 失败了呢？要知道，crash 一般是因为 undefined behavior (UB) 导致的——UB 没把所有的文件都删掉真是谢天谢地了。
万一我得到进程号以后，进去发现文件没了 (进程终止了)，怎么办？会不会有这种情况？万一有我的程序会不会 crash……？
进程的信息一直在变，文件的内容也一直在变 (两次 cat 的结果不同)。那我会不会读到不一致的信息(前一半是旧信息、新一半是新信息)？
如果我不确信这些事会不会发生，我有没有写一个程序，至少在压力环境下测试一下它们有没有可能发生？嗯，如果我同时运行很多程序，每个程序都不断扫描目录、读取文件，也观察不到这个问题，至少应该可以放点心。