进程树

返回综述: 进程管理

进程树的数据结构

在 task_struct 中, 通过以下字段构成一棵多叉双向树:

1
2
3
4
5
6
7
8
struct task_struct __rcu *real_parent; // 生物学父进程: 谁fork了我
struct task_struct __rcu *parent;     // 法律上的父进程: 谁来wait我、收我的SIGCHLD
// 通常 real_parent == parent, 仅在 ptrace 调试时不同

struct list_head children; // 作为父进程时: 子进程链表的哨兵头(入口)
struct list_head sibling;  // 作为子进程时: 挂在父进程children链表上的节点

struct task_struct *group_leader; // 线程组的主线程(和进程树无关, 是线程组维度的字段)

parent 和 real_parent, 为什么要有两个 parent?

这个场景主要是为了应对 debug 即 ptrace 场景, 在不使用调试器的时候, 两者指向的都是父进程.
但是在使用调试器的场景下, real_parent 仍然是 fork parent, 但是 parent 指向 ptrace 调试器进程, 这个 parent 会接收 wait 和 SIGCHLD 信号

children 和 sibling 是怎么构成一棵多叉树的?

这是一个经典的 Linux 内核侵入式链表设计. 逻辑上等效于 LCRS(Left-Child Right-Sibling) 树:

1
2
3
4
5
struct tree_node {
    struct tree_node *parent;
    struct tree_node *first_child;
    struct tree_node *next_sibling;
};

但 LCRS 的写法存在问题:

  1. task_struct 关联了非常多的链表关系(进程树、全局进程列表、线程组等). LCRS 的遍历逻辑是进程树专用的, 每种链表关系都要单独维护一套增删/遍历 API. 实际上链表操作是通用的, 应该和具体的使用场景解耦.
  2. LCRS 通常是单向链表, 删除需要先遍历找前驱, 时间复杂度 O(n)
  3. 不能用动态数组存 children, 因为内核关键路径上绝不能有可能失败的内存分配

因此 Linux 使用了侵入式链表: 把一个通用的链表节点(list_head)嵌入到数据结构内部:

1
2
3
struct list_head {
    struct list_head *next, *prev;
};

每个 task_struct 同时扮演两个角色:

  • 作为父进程: children 是子进程链表的哨兵头(入口, 不代表任何子进程)
  • 作为子进程: sibling 是挂在父进程 children 链表上的普通节点

children.next 指向第一个子进程的 sibling 地址, 每个子进程的 sibling.next 指向下一个兄弟的 sibling 地址, 最后一个兄弟的 sibling.next 回到父进程的 children, 形成双向循环链表:

1
父进程.children ←→ 子A.sibling ←→ 子B.sibling ←→ 子C.sibling ←→ (回到父进程.children)

fork 的时候, 怎么将新子进程挂到父进程的进程树上?

1
2
3
4
5
6
7
8
9
10
11
// kernel/fork.c
// p 是新创建的子进程, p->real_parent 是执行fork的父进程
list_add_tail(&p->sibling, &p->real_parent->children);

// 等效于(伪代码):
// 把 p->sibling 插到 real_parent->children 链表的尾部
tail = parent->children.prev;
tail->next = &p->sibling;
p->sibling.prev = tail;
p->sibling.next = &parent->children;
parent->children.prev = &p->sibling;

遍历: 怎么找到某个进程的所有子进程?

1
2
3
4
struct task_struct *child;
list_for_each_entry(child, &parent->children, sibling) {
    // child 就是每个子进程的 task_struct *
}

list_for_each_entry 展开后等效于:

1
2
3
4
5
6
struct list_head *pos = parent->children.next; // 从哨兵头的next开始
while (pos != &parent->children) {             // 走回哨兵头就停
    child = container_of(pos, struct task_struct, sibling);
    // ... 使用 child ...
    pos = pos->next;
}

container_of: 怎么从 sibling 的地址反推出 task_struct 的地址?

list_head 内部没有 data 字段, 它不知道自己属于哪个 task_struct. 但因为 sibling 是嵌在 task_struct 内部的, 它在结构体中的偏移量是编译时确定的常量, 所以: sibling 的地址 - 偏移量 = task_struct 的起始地址

1
2
3
4
5
6
7
8
// include/linux/container_of.h
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

// 用法:
container_of(&某子进程.sibling, struct task_struct, sibling)
// = &某子进程.sibling 的地址 - sibling在task_struct中的偏移
// = 某子进程 task_struct 的起始地址

这就是侵入式链表的核心: 不是链表节点包含数据, 而是数据结构包含链表节点, 通过地址减偏移反推出数据结构地址.

进程树为什么存在

为什么内核必须记录 parent、children、sibling, 而不是只维护一个 PID 列表?

只维护了 PID 列表, 相当于对于内核来说只知道有哪些进程, 而不知道这些进程之间的关系, 则需要亲缘关系的时候(如 wait(), 托孤, 信号传播), 都需要遍历 PID 列表来拿到亲缘关系, 时间复杂度 O(n), 但是维护了亲缘关系以后, 就只用遍历子进程, 变成了 O(子进程数)

这些关系分别支撑了哪些操作: wait、发送信号、回收退出状态、托孤?

  • 托孤: 父进程退出的时候, 在 exit 路径中通过 forget_original_parent() → find_new_reaper() 将自己所有的子进程的 real_parent 改成 init/subreaper. 由 init 进程来调用 wait()/waitpid() 来完成 task_struct 最后的 PID 资源的回收和 exit_state 的回收. 这个机制依赖于父进程通过 children 链表遍历所有子进程
  • 信号传播:
    1. kill(-pgid, sig) 向整个进程组发信号
    2. 会话断开的时候, 会话 leader(常常是 bash/zsh…) 进程退出, 发送 SIGHUP 信号, 沿进程树传播要通知所有的前台进程/子进程, 子进程收到后退出, 如果没有树结构, 就只能全局扫描
    3. parent 支撑 SIGCHLD: 子进程退出的时候(do_exit() → exit_notify()), 内核通过 parent 指针找到父进程, 向他发送 SIGCHLD 信号, 通知父进程有个进程退出了, 调用 wait() 回收资源
  • 回收状态/wait(): do_wait() 的实现就是遍历 current->children 链表, 逐个检查子进程的 exit_state, 找到 EXIT_ZOMBIE 的子进程回收, 没有 children 链表, 就无法找到自己的子进程, 可能会产生永久僵尸

进程树和任务控制的关系

进程树、进程组、Session 之间是什么关系?

三者是不同维度的组织方式, 层层嵌套但不相同:

  • 进程组 (Process Group): 由 PGID(Process Group ID) 标识, 通过 task_pgrp() 获取. 同一条管道里的进程共享同一个 PGID. 进程组 leader 的 PID == PGID. 注意 PGID 和 TGID(Thread Group ID, 线程组ID) 是两个完全不同的概念.
  • 进程树 (Process Tree): 维护所有进程之间的亲缘关系, 是 fork() 的产物. fork() 创建的子进程会继承父进程的 SID 和 PGID. execve() 不创建新进程, 只替换程序映像, PID/PGID/SID 保持不变. 进程树关系是自动的、不可变的; 进程组关系是 shell 按作业逻辑主动设置的、可变的.
  • Session (会话): 一次终端连接, 是最外层的容器, 包含一个或多个进程组. 通过 setsid() 能让一个非 leader 的进程创建一个新的 Session, 并成为这个 Session/Group 的 leader. 这也是为什么守护进程要执行 fork() → setsid(): 如果调用者的 PID == PGID(即它是进程组 leader), setsid() 会失败, 所以先 fork 出子进程(子进程 PID ≠ 父进程 PGID), 再在子进程中 setsid(). 如果一个 Session leader 终止了, 会发送 SIGHUP 信号到前台进程组.
维度 进程树 进程组 会话
组织依据 谁 fork 了谁 谁在做同一个 job 谁共享同一个终端
标识符 无(通过 parent/children 指针) PGID SID
建立时机 fork 时自动建立 shell 启动 job 时 setpgid() 登录时 setsid()
可否改变 不可(除 ptrace/托孤) 可以 setpgid() 可以 setsid()
包含关系 无层级嵌套 一个会话包含多个进程组 最外层容器

为什么 Ctrl+C (SIGINT)、Ctrl+Z (SIGTSTP) 往往不是只作用在单个进程上?

实际上是作用在一整个前台进程组上的. 在最经典的管道场景中, cat file | grep foo | wc -l, 如果只发给一个前台的进程, 就会导致 cat 被终止了, 但是 grep/wc 还在运行, 还在往管道里面写数据, 行为就乱了

这和 shell、前台任务、后台任务有什么关系?

  • shell: 是作业控制的实现者, 通过进程组和会话机制来管理前台/后台任务, 启动时会通过 setsid() 成为 Session leader / 进程组 leader
  • 前台任务: 是会接受终端输入的一组进程. 如 cat file | grep foo, shell 首先通过 fork() 创建出两个子进程, 然后调用 setpgid() 将这两个进程放到一个进程组里面, 调用 tcsetpgrp() 将这个进程组变成前台进程组. 终端的键盘信号都会发送给前台进程组, shell 自己调用 waitpid() 阻塞等待前台任务完成
  • 后台任务: 没有调用 tcsetpgrp() 这一个设置成前台进程组的步骤, 后台进程组不持有前台, 所以 Ctrl+C 不影响它
操作 本质
Ctrl+Z 终端驱动向前台进程组发 SIGTSTP → 整组暂停
jobs shell 遍历自己管理的进程组列表, 显示状态
fg %1 shell 调用 tcsetpgrp() 把目标进程组设为前台 + 发 SIGCONT 恢复
bg %1 shell 向目标进程组发 SIGCONT, 但不设为前台 → 后台继续运行
kill %1 shell 向目标进程组发 SIGTERM

总结

  • 进程树: linux kernel里面为进程之间的亲子关系维护的一颗双向多叉树, 使用linux侵入式链表设计, 进程树对于托孤机制(僵尸清理), 沿亲缘关系的传播的信号来说是不可获取的机制, 比如wait()操作本身就是遍历进程的所有的children, 挨个回收PID和退出状态.
  • shell任务控制: 任务分成前台任务和后台任务, 拿管道的运用举例子, 创建任务的步骤是shell fork出来一系列的子进程, 然后setpgid(), 将这些进程放到一个进程组里面. 对于前台进程(比如我们输入的命令), 还有一个额外的设置成前台进程的步骤(tcsetpgrp()), 前台进程会接受键盘信号(Ctrl + C / Ctrl +Z). 这些信号传播的最小单元是一个进程组. 无论是前台任务还是后台任务, 都会共享一个session id来代表他们是经由这个session代表的shell进程创建的. shell会执行waitpid()来阻塞式等待, 并且完成最后的资源的清理. shell退出的时候, 会沿进程树的所有子进程的所在的进程组发送SIGHUP.
  • 守护进程: daemon进程就是一个后台进程, 创建的核心就是要和原来的session解绑(创立新的pgid, sid), 然后不再是shell进程的子进程, 所有流程是fork(leader进程不能setsid) - 父进程不wait(成为孤儿进程, 挂在init下面) - setsid(重制pgid/sid) - fork
  • 僵尸进程: 由父进程不wait()/waitpid(), 导致没有执行进程的最后的PID/exit_state的回收导致的中间态死亡进程, 大量的僵尸进程会导致PID空间不足
  • 孤儿进程: 父进程死亡, 子进程就变成了孤儿进程. 父进程exit的时候会调用exit() -> forget_original_parent() -> find_new_reaper()流程将子进程托孤给init/subreaper, 这两类进程会定期执行wait()清理僵尸进程.