kernel源码学习:进程

linux使用上百个双向链表来存储内核的各种数据结构, 其中包括进程描述符的task_struct结构.

cpp 代码

struct list_head {
    struct list_head *next, *prev;
};

在list.h中,形如__xxx的函数用来操作整个链表,而不是单个链表元素.


进程从pid得到进程描述符pd要一种高效的方法, 提到高效方法,那就用哈希表啦.  内核在这儿的哈希方法为一道宏, 表中有PIDHASH_SZ个元素(一般情况下PIDHASH_SZ=1024):

cpp 代码

#define pid_hashfn(x)   ((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))

哈希表解决冲突的方法以是采取双向链表. 这是数据结构中一种比较常见的手段. 因为数字比较大的pid很少用到, 这样的pid一般放在链表尾端。 而数字较小的pid经常用到, 而它们如果冲突也排在链表很前的位置, 所以采取这样的数据结构速度很快.
   内核提供了hash_pid()来加入一个元素到表中, unhash_pid()从表中删除一元素. 
   这个哈希表的主要目的是通过pid找到进程描述符, find_task_by_pid()提供了这项功能.

cpp 代码

static inline void hash_pid(struct task_struct *p)
{
    struct task_struct **htable = &pidhash[pid_hashfn(p->pid)];

    if((p->pidhash_next = *htable) != NULL)
        (*htable)->pidhash_pprev = &p->pidhash_next;
    *htable = p;
    p->pidhash_pprev = htable;
}

static inline void unhash_pid(struct task_struct *p)
{
    if(p->pidhash_next)
        p->pidhash_next->pidhash_pprev = p->pidhash_pprev;
    *p->pidhash_pprev = p->pidhash_next;
}

static inline struct task_struct *find_task_by_pid(int pid)
{
    struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

    for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
        ;

    return p;
}

分享到：

proguard解析java bytecode的常量池 | epmd源码学习

• 2007-08-09 10:19
• 浏览 2196
• 评论(0)
• 查看更多