对于进程，我们并不陌生。进程具有父子关系、兄弟关系等等。本文我们就深入探讨它们之间的关系。在阅读本文之前，应该熟读《Linux内核10-list_head和hlist_head的理解》这一篇文章，因为这对理解本文有很大帮助。
1 进程之间关系
我们已经或多或少知道，进程具有父子关系，不仅如此，还有兄弟关系。所以，进程描述符中必须有几个成员是记录这种关系的（P是创建的进程），具体可以参考下表。进程0和1是由内核创建的，后面我们会看到，进程1（init）是所有其它进程的祖先。
表3-3 进程中用来表述父子、兄弟关系的成员
| 成员名称 | 描述 |
| real_parent | 指向创建P，如果不存在指向进程1。（比如，在shell中 启动了一个后台进程，然后退出shell，则后台进程的 父进程就是init）。 |
| parent | 指向P的当前父进程。（当子进程结束时，必须发送信号 通知的那个进程）；通常等于real_parent。偶尔会有 不同的时候，比如当另一个进程发送ptrace()系统调用 去监控进程P时。 |
| children | 包含P创建的所有子进程的列表的表头。 |
| sibling | 包含指向兄弟关系的进程链表中的下一个元素和 前一个元素的指针，这些进程的父进程都是P。 |
图3-4 阐述了进程的父子、兄弟关系。进程P0依次创建了P1、P2和P3。继而，进程P3创建了P4。
更进一步讲，进程之间还有其它关系：一个进程可以是进程组的组长或者login会话的组长，还可以是线程组的组长，还可以追踪其它进程的执行。表3-4列出了描述进程P和其它进程之间关系的数据成员。
表3-4 进程描述符中建立非父子兄弟关系的数据成员
| 成员名称 | 描述 |
| group_leader | 进程P的进程组组长的进程描述符 |
| signal->pgrp | 进程P的进程组组长的PID |
| tgid | 进程P的线程组组长的PID |
| signal->session | 进程P的login会话组组长的PID |
| ptrace_children | 正在被调试器追踪的进程P的所有 子进程的列表的表头 |
| ptrace_list | 包含指向正在被调试器追踪所有 进程的real_parent列表中的元素 的指针，分别指向下一个或者前一个 元素。当追踪进程P时使用。 |
2 PID哈希表和链表
在多种情况下，内核必须能够根据PID得到进程描述符的指针。比如，kill()系统调用，假设进程P1想要发送给进程P2一个信号，它指定P2进程的PID作为参数调用kill()。内核能够根据PID溯源到进程描述符的指针，然后从P2的进程描述符记录待处理（也就是挂起-pending）信号的数据结构的指针。
顺序扫描进程列表，逐个检查进程描述符的pid成员，这当然是可行的，但却不是最有效的。为了加速查找过程，内核引入了4个哈希表。为什么是4个哈希表呢？这当然是因为进程描述符的PID有4类，如表3-5所示，每一种PID对应一个哈希表。
表3-5 进程描述符中的四种哈希表以及对应的数据结构
| 哈希表类型 | 成员名称 | 描述 |
| PIDTYPE_PID | pid | 进程PID |
| PIDTYPE_TGID | tgid | 线程组组长的PID |
| PIDTYPE_PGID | pgrp | 进程组组长的PID |
| PIDTYPE_SID | session | session组长的PID |
4个哈希表都是在内核初始化阶段动态分配，它们的地址存储在pid_hash的数组中。哈希表的大小依赖于RAM的数量。比如，系统的RAM为512M，每一个哈希表被存储在4个页帧中，大约是2048项（441024/4/2=2048）。
使用pid_hashfn宏将PID值转换成哈希表的索引值，其定义为：
#define pid_hashfn(x) hash_long((unsigned long) x, pidhash_shift)
其中，pidhash_shift参数是哈希表索引所占的位数，在我们的例子中需要2048项，也就是2^11，所以pidhash_shift=11。hash_long()函数被许多哈希函数使用；对于32位架构等于：
unsigned long hash_long(unsigned long val, unsigned int bits) { unsigned long hash = val * 0x9e370001UL; return hash >> (32 - bits); }
因为在我们的示例中，pidhash_shift等于11，所以pid_hashfn宏产生的值永远落在0-2047这个区间内。
魔幻常数
在上面的代码中，你肯定会想0x9e370001UL这个值是如何得来的。hash函数通常是索引值乘以一个合适的大数，因此，结果会溢出，将其余下的值存入32位的变量，这个变量可以看做是求模运算的结果。Knuth认为，选取一段数值范围中黄金比例的质数为这个大数是最合适的。所以，0-2^23之间的黄金比例附近最合适的质数，我们选取0x9e370001UL，它还可以方便地被加、减法，还有移位实现。因为它等于
2^31 + 2^29 - 2^25 + 2^22 - 2^19 – 2^16 + 1。
正如计算机科学课程中所讲的，哈希函数是无法保证PID和哈希表索引之间的一对一关系的。两个PID对应哈希表中的同一个索引，就成为 冲突。
为了解决这个冲突问题，Linux决定使用一个双向链表存储这些冲突的PID，把这个双向链表的表头存入哈希表中，通过这种方法，完美地解决了这个冲突。图3-5，展示了一个带有两个双向链表的PID哈希表：PID为2890和29384的进程都被存入到哈希表的第200个元素处的双向链表中，而PID为29385的进程被装入到了哈希表的第1466个元素里。
这种带链表的哈希表优于从PID到表索引的线性转换，这是因为，对于任何给定的32位系统中，进程的数量通常远少于32768个（最大允许进程数）。如果定义一个32768项的表，这对于内存空间都是一种浪费，因为大部分项根本没用。
当然了，实际用在PID哈希表中的数据结构非常复杂，因为它们要跟踪进程之间的各种关系。比如，假设内核需要检索属于某个线程组的所有进程，也就是所有的进程其tgid成员都等于某个相同的进程ID。如果根据这个给定的线程组ID，也就是线程组组长的PID，遍历整个PID哈希表，仅是返回一个进程描述符，也就是线程组组长的进程描述符。那为了快速检索整个线程组的所有进程，内核就需要为每个线程组维护一个进程表。对于寻找一个给定的login会话组或者进程组中的所有进程，道理是一样的。
图3-5. 一个简单的PID哈希表和链表
PID哈希表的数据结构就解决了这所有的问题，因为它允许给包含在哈希表中的任何一个PID定义一个进程表。核心数据结构就是在进程描述符的pids成员中嵌入4个pid成员结构，组成一个数组，数组每个成员对应一种哈希表。每个pid成员的数据成员如表3-6所示：
表3-6 pid数据结构的各个成员
| 类型 | 名称 | 描述 |
| int | nr | PID值 |
| struct hlist_node | pid_chain | 用于hash表中的链表结构中， 用于指向下一个和前一个元素 |
| struct list_head | pid_list | 每个PID表的头 |
我们用下面的图3-6，展示一个类型为PIDTYPE_TGID的哈希表。pid_hash数组的第二项存储着哈希表的地址，也就是由hlist_head结构的组成的一个数组，这个数组存储着链表的表头。开始于哈希表第71项的链表，存储着2个进程描述符，其PID分别是246和4351，使用双向链表表示。这些PID值存储在进程描述符的pid结构成员的nr成员中（顺便说一下，因为线程组的ID和它的组长的PID相同，所以这些值也是线程组的ID）。接下来，我们看一个线程组4351，它对应着一组链表：链表的头被存储在进程描述符的pid_list结构成员中，通过pid_list结构的next和prev指针分别指向该链表的下一个和前一个元素。通过这种方式，我们就实现了检索某个线程组中的所有进程。其它3类哈希表的检索与此类似，就不再一一展开了。
图3-6展示了一个基于PIDTYPE_TGID类型的哈希表的示例。pid_hash数组中的第2项存储着该哈希表的地址，也就是hlist_head类型的数组结构，用于保存具有相同tpid值的链表的表头。tgid哈希表的第71项出来的分链表中，有PID分别为246和4351的进程描述符。
图3-6 PID哈希表
下面的函数和宏用来处理PID哈希表：
- do_each_task_pid(nr, type, task)
- while_each_task_pid(nr, type, task)
遍历与nr指定的PID相关的每一个PID列表，type是哈希表类型，task指向当前刚被遍历过的进程描述符。 - find_task_by_pid_type(type, nr)
type类型的哈希表中查找PID等于nr的进程。函数返回匹配的进程描述符指针，如果不匹配返回NULL。 - find_task_by_pid(nr)
作用等同于find_task_by_pid_type(PIDTYPE_PID, nr)。 - attach_pid(task, type, nr)
往类型为type的PID哈希表中插入进程描述符，task指向要插入的进程描述符，nr是PID哈希表的索引。如果已经有一个PID等于nr的进程描述符在哈希表中了，则将task插入到该PID对应的链表中。 - detach_pid(task, type)
从类型为type的PID列表中删除task指向的进程描述符。执行完删除操作后，如果PID链表没有变为空，则函数执行中止；否则，该函数还会从类型为type的哈希表中删除对应的进程描述符。 - next_thread(task)
返回类型为PIDTYPE_TGID的哈希表中紧跟在task之后的轻进程的进程描述符地址。因为链表是环形的，如果是作用到常规进程上，该宏返回进程本身的描述符地址。
