Linux 内核进程管理之进程ID

Linux 内核使用 task_struct 数据结构来关联所有与进程有关的数据和结构，Linux 内核所有涉及到进程和程序的所有算法都是围绕该数据结构建立的，是内核中最重要的数据结构之一。该数据结构在内核文件 include/linux/sched.h 中定义，在Linux 3.8 的内核中，该数据结构足足有 380 行之多，在这里我不可能逐项去描述其表示的含义，本篇文章只关注该数据结构如何来组织和管理进程ID的。

进程ID类型

要想了解内核如何来组织和管理进程ID，先要知道进程ID的类型：

PID：这是 Linux 中在其命名空间中唯一标识进程而分配给它的一个号码，称做进程ID号，简称PID。在使用 fork 或 clone 系统调用时产生的进程均会由内核分配一个新的唯一的PID值。TGID：在一个进程中，如果以CLONE_THREAD标志来调用clone建立的进程就是该进程的一个线程，它们处于一个线程组，该线程组的ID叫做TGID。处于相同的线程组中的所有进程都有相同的TGID；线程组组长的TGID与其PID相同；一个进程没有使用线程，则其TGID与PID也相同。PGID：另外，独立的进程可以组成进程组（使用setpgrp系统调用），进程组可以简化向所有组内进程发送信号的操作，例如用管道连接的进程处在同一进程组内。进程组ID叫做PGID，进程组内的所有进程都有相同的PGID，等于该组组长的PID。SID：几个进程组可以合并成一个会话组（使用setsid系统调用），可以用于终端程序设计。会话组中所有进程都有相同的SID。

PID 命名空间

命名空间是为操作系统层面的虚拟化机制提供支撑，目前实现的有六种不同的命名空间，分别为mount命名空间、UTS命名空间、IPC命名空间、用户命名空间、PID命名空间、网络命名空间。命名空间简单来说提供的是对全局资源的一种抽象，将资源放到不同的容器中（不同的命名空间），各容器彼此隔离。命名空间有的还有层次关系，如PID命名空间，图1 为命名空间的层次关系图。

图1 命名空间的层次关系

在上图有四个命名空间，一个父命名空间衍生了两个子命名空间，其中的一个子命名空间又衍生了一个子命名空间。以PID命名空间为例，由于各个命名空间彼此隔离，所以每个命名空间都可以有 PID 号为 1 的进程；但又由于命名空间的层次性，父命名空间是知道子命名空间的存在，因此子命名空间要映射到父命名空间中去，因此上图中 level 1 中两个子命名空间的六个进程分别映射到其父命名空间的PID 号5~10。

命名空间增大了 PID 管理的复杂性，对于某些进程可能有多个PID——在其自身命名空间的PID以及其父命名空间的PID，凡能看到该进程的命名空间都会为其分配一个PID。因此就有：

全局ID：在内核本身和初始命名空间中唯一的ID，在系统启动期间开始的 init 进程即属于该初始命名空间。系统中每个进程都对应了该命名空间的一个PID，叫全局ID，保证在整个系统中唯一。局部ID：对于属于某个特定的命名空间，它在其命名空间内分配的ID为局部ID，该ID也可以出现在其他的命名空间中。

进程ID管理数据结构

Linux 内核在设计管理ID的数据结构时，要充分考虑以下因素：

如何快速地根据进程的 task_struct、ID类型、命名空间找到局部ID如何快速地根据局部ID、命名空间、ID类型找到对应进程的 task_struct如何快速地给新进程在可见的命名空间内分配一个唯一的 PID

如果将所有因素考虑到一起，将会很复杂，下面将会由简到繁设计该结构。

一个PID对应一个task_struct

如果先不考虑进程之间的关系，不考虑命名空间，仅仅是一个PID号对应一个task_struct，那么我们可以设计这样的数据结构：

struct //...    struct //...struct struct struct *struct struct //指回 pid_link 的 node    int //PID    struct //pid hash 散列表结点
图2 一个task_struct对应一个PID
图中还有两个结构上面未提及：
pid_hash[]: 这是一个hash表的结构，根据 pid 的 nr 值哈希到其某个表项，若有多个 pid 结构对应到同一个表项，这里解决冲突使用的是散列表法。这样，就能解决开始提出的第2个问题了，根据PID值怎样快速地找到task_struct结构体：
首先通过 PID 计算 pid 挂接到哈希表 pid_hash[] 的表项遍历该表项，找到 pid 结构体中 nr 值与 PID 值相同的那个 pid再通过该 pid 结构体的 tasks 指针找到 node最后根据内核的 container_of 机制就能找到 task_struct 结构体pid_map：这是一个位图，用来唯一分配PID值的结构，图中灰色表示已经分配过的值，在新建一个进程时，只需在其中找到一个为分配过的值赋给 pid 结构体的 nr，再将pid_map 中该值设为已分配标志。这也就解决了上面的第3个问题——如何快速地分配一个全局的PID。
至于上面的第1个问题就更加简单，已知 task_struct 结构体，根据其 pid_link 的 pid 指针找到 pid 结构体，取出其 nr 即为 PID 号。
进程ID有类型之分
如果考虑进程之间有复杂的关系，如线程组、进程组、会话组，这些组均有组ID，分别为 TGID、PGID、SID，所以原来的 task_struct 中pid_link 指向一个 pid 结构体需要增加几项，用来指向到其组长的 pid 结构体，相应的 struct pid 原本只需要指回其 PID 所属进程的task_struct，现在要增加几项，用来链接那些以该 pid 为组长的所有进程组内进程。数据结构如下：
enum struct //...    pid_t //PID    pid_t //thread group id    struct *// threadgroup leader    struct //...struct struct struct *struct struct int //PID    struct // pid hash 散列表结点
图3 增加ID类型的结构
关于上图有几点需要说明：
图中省去了 pid_hash 以及 pid_map 结构，因为第一种情况类似；进程B和C的进程组组长为A，那么 pids[PIDTYPE_PGID] 的 pid 指针指向进程A的 pid 结构体；进程A是进程B和C的组长，进程A的 pid 结构体的 tasks[PIDTYPE_PGID] 是一个散列表的头，它将所有以该pid 为组长的进程链接起来。
再次回顾本节的三个基本问题，在此结构上也很好去实现。
增加进程PID命名空间
若在第二种情形下再增加PID命名空间，一个进程就可能有多个PID值了，因为在每一个可见的命名空间内都会分配一个PID，这样就需要改变 pid 的结构了，如下：
struct unsigned int /* lists of tasks that use this pid */    struct struct 1struct int struct *struct 
图4 增加PID命名空间之后的结构图
图中关于如果分配唯一的 PID 没有画出，但也是比较简单，与前面两种情形不同的是，这里分配唯一的 PID 是有命名空间的容器的，在PID命名空间内必须唯一，但各个命名空间之间不需要唯一。
至此，已经与 Linux 内核中数据结构相差不多了。
进程ID管理函数
有了上面的复杂的数据结构，再加上散列表等数据结构的操作，就可以写出我们前面所提到的三个问题的函数了：
获得局部ID
根据进程的 task_struct、ID类型、命名空间，可以很容易获得其在命名空间内的局部ID：
获得与task_struct 关联的pid结构体。辅助函数有 task_pid、task_tgid、task_pgrp和task_session，分别用来获取不同类型的ID的pid 实例，如获取 PID 的实例：
static inline struct *task_pidstruct *return ->
static inline struct *task_tgidstruct *return ->->
static inline struct *task_pgrpstruct *return ->->static inline struct *task_sessionstruct *return ->->
pid_t pid_nr_nsstruct *struct *struct *pid_t = 0if && -><= ->= &->->if ->== = ->return 
pid_t task_pid_nr_nsstruct *struct *pid_t task_tgid_nr_nsstruct *struct *pid_t task_pigd_nr_nsstruct *struct *pid_t task_session_nr_nsstruct *struct *
struct *find_pid_nsint struct *struct *struct *//遍历散列表    &//pid_hashfn() 获得hash的索引        if ->== && ->== //比较 nr 与 ns 是否都相同            return struct //根据container_of机制取得pid 实体                    ->return NULL
struct *pid_taskstruct *enum struct *= NULLif struct *= &->if = struct return 
struct *find_task_by_pid_nspid_t struct *struct *find_task_by_vpidpid_t struct *find_task_by_pidpid_t 
static int alloc_pidmapstruct *static void free_pidmapstruct *
struct *alloc_pidstruct *struct *enum int struct *struct *= ->= ->// 初始化 pid->numbers[] 结构体    for = ->>= 0--= //分配一个局部ID        ->= ->= = ->// 初始化 pid->task[] 结构体    for = 0< ++&->// 将每个命名空间经过哈希之后加入到散列表中    = ->+ ->for >= ->--&->&->->->->++return pid;}
参考资料
深入Linux 内核架构（以前不觉得这本书写得多好，现在倒发现还不错，本文很多都是照抄上面的）周徐达师弟的PPT（让我受益匪浅的一次讨论，周由浅入深告诉我们该数据结构是如何设计出来的，本文主思路就是按照该PPT，在此 特别感谢！）