M2: 打印进程树 (pstree)

1. 背景

操作系统为应用程序提供了 “一组对象” 和访问它们的 API。将各种类型的对象和 API 组合使用，造就了我们丰富多彩的应用程序世界。今天的操作系统都提供任务管理器工具监测程序运行状态，例如显示在一段时间内，各个程序 (进程、状态机) 的活跃程度、占用的内存等等。下面的图片展示了 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}
        ...

pstree 来自 psmisc，它是一个开源软件——pstree 的实现有 1600 行 (43 KB)；让我们看看大语言模型在几秒内帮我们生成的总结 (当然，在这个实验中，我们希望大家避免不必要的麻烦，只需要实现它的简化版)：

2.1 总览

pstree [OPTION]…

2.2 描述

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

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

只要输出系统中的进程即可；此外，允许进程列表有轻微出入。细心的同学可能发现你第一个版本的 pstree 可能和系统输出不太一样，但不用担心：在线评测会容忍你输出的一些缺陷，只要关注于问题的解决即可。

4. 实验指南

如果你觉得打印进程树这个问题比较困难，可以让 AI 给你做老师：

可以对比一下，我觉得 AIGC 甚至比我更懂这个实验。

4.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) 库可以处理命令行参数；当然，你也可以直接自己动手解析。

4.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，欢迎大家仔细阅读 (但不是强制的)。

4.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 读取进程的运行时间/内存数据。

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

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

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

4.6 思考

根据《操作系统》课程重要的基本原理：合理的需求一定有合适的方法满足，操作系统一定会提供进程相关的对象和获取信息的 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 占用率、内存使用等信息——于是你也可以实现自己的任务管理器了！