Linux进程PID散列表

linux系统中每个进程由一个进程id标识,在内核中对应一个task_struct结构的进程描述符,系统中所有进程的task_struct通过链表链接在一起,在内核中,经常需要通过进程id来获取进程描述符,最简单的方法可以通过遍历task_struct链表并对比id的值来获取,但这样效率太低,尤其当系统中运行很多个进程的时候。

 

linux内核通过PID散列表来解决这一问题,能快速的通过进程ID获取到进程描述符。

 

PID散列表包含4个表,因为进程描述符包含了表示不同类型PID的字段,每种类型的PID需要自己的散列表。

 

enum pid_type

{

        PIDTYPE_PID,  // 进程的PID

        PIDTYPE_TGID, // 线程组领头进程的PID

        PIDTYPE_PGID, // 进程组领头进程的PID

PIDTYPE_SID,  // 会话领头进程的PID

        PIDTYPE_MAX   // 类型个数

};

 

内核定义了4个全局的hash表,分别对应4种类型

static struct hlist_head *pid_hash[PIDTYPE_MAX];


内核通过一个struct pid的结构来链接各个进程,其定义如下:

struct pid

{

        int nr;

        struct hlist_node pid_chain;

        struct list_head pid_list;

};

 

其中nr代表id号,pid_chain用于链接冲突元素。对于PGIDTGID来说,对于同一进程组的多个进程来说,所有进程的PGID是相同的,内核中很多操作是针对进程组进行的操作,通过pid_list字段,可以将所有相同id的进程链接在一起。

 

task_struct结构中拥有一个pids字段,它是包含PIDTYPE_MAX个元素的pid结构数组,hash表的链接关系由pid结构完成,通过pid结构可获取包含该结构的task_struct描述符。

 

struct task_struct {   

    struct pid pids[PIDTYPE_MAX];

};

 

pid散列表的链接关系如下图所示,本图中描述了以TGID为关键字建立的hash表。

 《Linux进程PID散列表》


通过id获取进程描述符由find_task_by_pid_type函数完成,代码如下,其首先根据指定id的类型,获取对应散列表的表头,然后计算id所对应的hash slot并遍历获取到对应的pid结构,然后调用pid_task获取到包含该pid结构的task_struct描述符。

 

注:本文的代码来自2.6.11版本内核,后因命名空间扩展等原因,PID散列表的实现已经发生了改变,但原理上应该是相同的。

 

task_t *find_task_by_pid_type(int type, int nr)

{

        struct pid *pid;

 

        pid = find_pid(type, nr);

        if (!pid)

                return NULL;

 

        return pid_task(&pid->pid_list, type);

}

 

struct pid * fastcall find_pid(enum pid_type type, int nr)

{

        struct hlist_node *elem;

         struct pid *pid;

        hlist_for_each_entry(pid, elem,

                        &pid_hash[type][pid_hashfn(nr)], pid_chain) {

                if (pid->nr == nr)

                         return pid;

        }

        return NULL;

}

 

#define pid_task(elem, type) \

          list_entry(elem, struct task_struct, pids[type].pid_list)

 

    原文作者:ydzhang
    原文地址: https://www.cnblogs.com/yunnotes/archive/2013/04/19/3032397.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞