1. 基本概念
每個進程控制塊都有4個有關ID、含義不同的值，內核根據它們組成了4個全局的2維的HASH表，每個進程都要鏈接到這四個不同含義的Hash表當中。
/* 4種類型的值*/
enum pid_type
{
PIDTYPE_PID, 進程的PID
PIDTYPE_TGID, 線程組ID
PIDTYPE_PGID, 進程組ID
PIDTYPE_SID, 會話ID
PIDTYPE_MAX
};
struct task_struct {
......
/* PID/PID hash table linkage. */
struct pid pids[PIDTYPE_MAX];
......
}
2. Hash表的數組
四個全局的Hash表頭位於： static struct hlist_head *pid_hash[PIDTYPE_MAX];
每一個Hash表都是一個數組，每一個元素是一個Hash值的鏈表頭。默認有2048個元素
-----------------------------------------------------------------------------
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |...|2047| |
-----------------------------------------------------------------------------
3. Hash表數組元素的鏈表
我們拿進程的進程組ID（PIDTYPE_PGID）來舉例，假如有3個進程組，分別是：
GROUP1：
PID PGIP HASH_PGID (根據進程組ID[PGIP]得到的Hash值)
10 10 hash(10)=88 (進程組領頭)
11 10 hash(10)=88
12 10 hash(10)=88
GROUP2：
PID PGIP HASH_PGID (根據進程組ID[PGIP]得到的Hash值)
100 100 hash(100)=99 (進程組領頭)
101 100 hash(100)=99
102 100 hash(100)=99
GROUP3：
PID PGIP HASH_PGID (根據進程組ID[PGIP]得到的Hash值)
550 550 hash(550)=88 (進程組領頭)
551 550 hash(550)=88
552 550 hash(550)=88
struct pid
{
/* Try to keep pid_chain in the same cacheline as nr for find_pid */
/* 值 */
int nr;
/* HASH_PGID 值相同、且為進程組領頭的進程鏈在這裡，如PID值為10和550的兩個進程會通過這個字段鏈接，這裡可以認為是1個維度鏈，非進程組的進程的這個域為NULL(這裡不考慮其它3種類型的值) */
struct hlist_node pid_chain;
/* PGID 值相同的進程鏈在這裡，如上3個進程組，分別各自通過這個域鏈接起來，這裡可以認為是第2個維度鏈 */
/* list of pids with the same nr, only one of them is in the hash */
struct list_head pid_list;
};
PGID的Hash表（即全局的pid_hash[PIDTYPE_PGID]）
----
0
----
1
----
2
----
88 ---> 10 ---> 11 ---> 12 通過pid_list域鏈接
---- |
... | 通過pid_chain域鏈接
---- |
90 550 ---> 551 ---> 552 通過pid_list域鏈接
----
..
----
99 ---> 100 ---> 101 ---> 102 通過pid_list域鏈接
----
2047
文章出處：http://www.diybl.com/course/6_system/linux/Linuxjs/200888/135051.html
