M1: 打印进程树 (pstree)

计算机世界有趣的地方在于，你可以动手构建任何你认为应该可以实现的东西。我们的热身实验是一个很简单的代码练习——但我们并不是实现类似于排序、最短路径这样的算法习题，而是一个真正有意义的 “实用工具”：了解操作系统中运行的程序 (进程) 之间的层级关系，并打印进程树。

1. 背景

我们早已熟知操作系统拥有同时运行多个的应用程序的能力——我们可以同时玩游戏的时候聊 QQ、放音乐……那么，管理这些同时运行的程序就是一项 “应该可以实现” 的功能，于是我们就来实现它。今天的操作系统都提供任务管理器工具监测程序运行状态，例如显示在一段时间内，各个程序 (进程、状态机) 的活跃程度、占用的内存等等。下面的图片展示了 Plasma Desktop 的任务管理器，能够显示系统资源的使用情况和进程的信息。

2. 实验描述

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 等)。这些参数可能任意组合，但你不需要处理单字母参数合并的情况，例如 -np。

2.3 解释

以下对 pstree 总览和描述的一些解释：

1. 中括号扩起的参数是可选参数，[] 后的 … 代表参数的 0 次或多次重复。因此 -p, -n, -V 都是可选的参数。
2. 同一个选项可以有别名。在 pstree 中，-p 和 --show-pids 的含义是一样的。
3. 若不另行说明，整数范围在 32 位有符号整数范围内；但如果数值和文件大小有关，则其合法的范围是是 0 到系统最大支持的文件大小。

如果不知道这些约定，使用 Linux/Unix 的时候就会举步维艰。Unix 世界有一套自己定义的 “游戏规则”。也难怪会有笑话：

Unix is user-friendly — it's just choosy about who its friends are.

当然，在渐渐熟悉游戏规则以后就会发现，这套设计在 1970 年代有限的计算机算力和使用者的负担之间达成了优雅的平衡——Shell 总是可以帮助你用最短的时间把 quick and dirty 的事情搞定：UNIX 哲学强调 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 可能和系统输出不太一样。在线评测会容忍你输出的一些缺陷；此外，作为第一个实验，我们会手下留情，没有非常强劲的测试数据。但你仍然需要确保：

1. 正确列出系统中的进程，并正确实现参数组合的行为；
2. 编写可移植的代码。我们会同时测试 32-bit 和 64-bit 的版本。

4. 问题分析

根据《操作系统》课程重要的基本原理：合理的需求一定有合适的方法满足，操作系统一定会提供进程相关的对象和获取信息的 API。

一个可行的想法是操作系统可以提供类似迭代器的 API，可以在某个时刻对进程列表进行 “快照”，然后程序可以通过 API 迭代快照里的进程。

Snapshot *CreateProcessSnapshot(); // 迭代开始
Process *FirstProcess(Snapshot *snapshot); // 取得第一个进程
Process *NextProcess(Process *process); // 获得下一个进程
int ReleaseProcessSnapshot(Snapshot *snapshot); // 迭代结束

高级语言可以进一步封装，例如借助 WMI (Windows Management Instrumentation) 库：

import wmi
for proc in wmi.WMI().Win32_Process():
    ...

UNIX 操作系统的设计者用另一种方法使应用程序能访问进程列表：操作系统会不断更新一个对象 (文本文件) 的内容，这样应用程序就能用文件 API (open, read, close) 来获取进程列表，例如大家可以用熟悉的 C 语言 FILE * 访问。

今天我们可以考虑在系统里创建一个名为 /system/processes.json 的文本文件，每当进程创建或退出，这个文件的内容就会更新 (当然，操作系统保证更新在瞬间完成)：

[
    {
        "pid": 1,
        "parent": -1,
        "command": "/bin/init"
    },
    {
        "pid": 2,
        "parent": 1,
        "command": "/bin/bash"
    }
]

UNIX 采用了 Everything is a File 的设计。换句话说，我们可以把操作系统的状态变成文件系统的一部分，从而可以使用我们熟悉的 read, write 等 API 访问操作系统中的各类信息。在这个实验中，我们学习 UNIX/Linux 是如何把操作系统的状态放在文件系统中的。虽然这个实验里你只需要读取进程列表和进程之间的父子关系，但用类似的办法，也可以从 Linux 系统中读取出 CPU 占用率、内存使用等信息——于是你也可以实现自己的任务管理器了！

5. 实验指南

如果你觉得打印进程树这个问题比较困难，我们也把问题分解一下：

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

5.1. 命令行参数

main 函数的参数是进程 “初始状态” 的一部分，它是由进程的创建者决定的，操作系统负责把它们放在内存中适当的位置；作为 C 语言的程序员，我们只要直接访问 main 函数的参数即可：

#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 程序之间的约定。getopt (man 3 getopt) 库可以处理命令行参数；当然，你也可以直接自己动手解析。

5.2. 开始做实验

回想一下大家做 OJ 题的过程。在编程的过程中，难免会经历修改代码 $\to$ 编译 $\to$ 运行 $\to$ 修改代码……这样的循环。你会选择怎么做呢？新手每次都键入命令 (或者他发现 Ctrl-p 可以重复命令)。

• 之后，有同学人发现，可以把命令写在一行里，比如 gcc a.c && ./a.out，一键就能编译运行了。
• 再之后会发现可以写个 Makefile (就像这个实验一样)，用 make test 跑完所有测试。
• 再之后会发现可以每次在文件改动以后自动运行所有测试……有个神奇的命令叫 inotifywait (我们并不推荐)。

即便现在有 IDE 和丰富的插件，UNIX 哲学依然是无处不在的 (甚至是这些 IDE 的组成基础)，说得更具体一点，“只要你敢想，就一定能做到”。是的，因为之后会反复编译运行这个程序，所以编译和测试自动化非常重要。常见的 C 项目组织是编写 Makefile，在命令行中使用 make 实现编译，make test 完成测试。我们已经为大家提供了 Makefile，欢迎大家仔细阅读 (但不是强制的)。

5.3. 得到系统中进程的编号

进程是操作系统中的对象，因此操作系统一定提供了 API 访问它们。已经剧透过，系统里的每个进程都有唯一的编号，它在 C 语言中的类型是 pid_t。不知道这是什么？当然是想办法啦！除了找人工智能 “拿来” 一个答案，在互联网上能找到更权威的定义：glibc 对它的官方文档解释。以后遇到问题要自己找答案哦！

操作系统以什么样的方式让你获取系统里的进程呢？之前也提示过：

Everything is a file.

一切皆文件，进程信息当然也可以是 “一切” 的一部分。Linux 提供了 procfs，目录是 /proc。如果你进去看一眼，就会发现除了一些比如 cpuinfo 这样的文件，还有很多以数字命名的目录——聪明的你也许已经猜到了，每个目录的名字就是进程号，目录里存储了进程相关的运行时数据。

我们鼓励大家先玩一玩 procfs，里面可有很多有趣的东西！你可以用 cat 可以打印文件的内容，对照文档 (或者 ChatGPT)，你会发现原来我们以为离我们很遥远的 “观测进程执行”，简单得只要解析文本文件就可以了！例如，每个进程的父进程也隐藏在 /proc/[pid]/ 中的某个文件里。试试 man 5 proc，里面有详细的文档。很多 Online Judge 都使用 procfs 读取进程的运行时间/内存数据。

5.4. 遍历所有进程

了解了 procfs 之后，我们的问题就变得简单一些了：只要能得到 /proc 目录下的所有以数字为开头的目录，我们就遍历了系统中的进程。因此你会去互联网上搜索如何用 C 语言遍历目录。之后，你可以用你熟悉的方式打开 procfs 里的文件：

    FILE *fp = fopen(filename, "r");
    if (!fp) goto release;

    // 用fscanf, fgets等函数读取

release:
    if (fp) fclose(fp);

procfs 里的信息足够让你写一个非常不错的任务管理器。那么，“真正” 的任务管理器，例如 ps 命令，是否也是基于 procfs 实现的呢？这就是一个典型的 “好问题”：他帮助你建立你的实验作业和真实系统之间的联系。操作系统课程也给了大家足够的工具，使得同学们可以把任务管理器打开，查看它调用的操作系统 API。我们在课堂上已经演示过 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
...

5.5. 建树和打印

终于，在得到进程编号 (名字) 和父子关系的基础上，我们就有了一个 “算法题”，它输入由有向边构成的树，要求输出图形化表示的树结构：

1 2
2 3
2 4
3 5
4 6
3 7

我们不妨把有根树理解成一个 “括号序列” (前序遍历)：

1(2(3(5,7),4(6)),8)

按照从左到右的顺序，输出每一个节点的编号——需要打印多少空格呢？答案是括号嵌套的深度，我们不妨试试看：

1
  2
    3
      5
      7
    4
      6
  8

看起来挺正确的！你就得到了一个 “基本款” 的 pstree。如果你想好看一些，你只要考虑在空间里填上什么样的字符就行了——没错，我们只要 “向左走”，找到它的父亲所在的列 (边向左走边画 “-”)，最后画上垂直的线，我们就得到了树状的结构！

1
+-2
| +-3
| | +-5
| | +-7
| +-4
|   +-6
+-8

看起来不错呢！我们找到问题正确的切入点，就可以简化问题。

5.6. 写出正确的代码

虽然在这个实验里，我们的测试用例相对简单；但在未来的实验中，Online Judge 可能会在各种奇葩的条件下运行你的程序哦！除了你们做的 OJ 题中会有复杂的逻辑 (参数的组合) 导致 bug 之外，和系统打交道的编程可有更多的麻烦之处：

1. 你的程序遵守 POSIX 的返回值规定吗？如果你的 main 函数返回了非 0 的数值，我们将认为程序报告了错误——在非法的输入上返回 0，以及在合法的输入上返回非 0 都将导致 Wrong Answer。
2. 程序够 robust 吗？它会不会在一些非法的输入上 crash？如果系统里的进程很多呢？如果内存不够了呢？如果 open 或者 malloc 失败了呢？要知道，crash 一般是因为 undefined behavior (UB) 导致的——UB 没把所有的文件都删掉真是谢天谢地了。
3. 万一我得到进程号以后，进去发现文件没了 (进程终止了)，怎么办？会不会有这种情况？万一有我的程序会不会 crash……？
4. 进程的信息一直在变，文件的内容也一直在变 (两次 cat 的结果不同)。那我会不会读到不一致的信息 (前一半是旧信息、新一半是新信息)？这两个问题都是 race condition 导致的；我们将会在并发部分回到这个话题。
5. 如果我不确信这些事会不会发生，我有没有写一个程序，至少在压力环境下测试一下它们有没有可能发生？嗯，如果我同时运行很多程序，每个程序都不断扫描目录、读取文件，也观察不到这个问题，至少应该可以放点心。

随着课程的深入，这些问题都会得到解答。

当你的程序越来越复杂，这些问题也许将会成为你挥之不去的阴影。这就对了——从 Intel 的 CPU 到 Linux Kernel 都有数不清的 bug。你也许听说过 “形式化验证”，但事实也证明，经过验证正确的编译器 (CertComp) 和操作系统 (seL4, FSCQ, ...) 都依然存在 bug，尽管它们的可靠性依然比程序员手写的高得多。

写出正确的代码远比想象中困难——目前地球上还没人能保证复杂的系统没有 bug 和漏洞。我们切盼望着没有 bug 的那一天的到来——我们离这个终极的答案似乎越来越近，但依然虚无缥缈。不过也不用太绝望，这门课里会教给大家一些有关 “写代码” 的知识，更重要的是正确的解决问题的思维方式 (“世界观”)。