Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1317841
  • 博文数量: 175
  • 博客积分: 2743
  • 博客等级: 少校
  • 技术积分: 4024
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-30 01:41
文章分类

全部博文(175)

文章存档

2015年(1)

2013年(53)

2012年(71)

2011年(50)

分类: LINUX

2013-04-28 11:15:52

浅析linux内核调度器与时间系统之PID 哈希表

作者:李万鹏


首先看一下kernel中的哈希表的数据结构,哈希表头:

Cpp代码
  1. struct hlist_head {  
  2.     struct hlist_node *first;  
  3. };  
struct hlist_head { struct hlist_node *first; }; 链表头是hlist_head,注意这是一个双向链表但不循环。first字段指向第一个节点。

哈希表节点:

Cpp代码
  1. struct hlist_node {  
  2.     struct hlist_node *next, **pprev;  
  3. };  
struct hlist_node { struct hlist_node *next, **pprev; };这里的next指向下一个节点,pprev字段存放了上一个next字段的地址。即*(second->pprev) = = first->next。


内核中经常需要通过进程的PID来获得进程描述符task_struct,顺序扫描进程链表并检查进程描述符的pid字段是可行但相当低效的。为了加速查找引入4个散列表,因为进程包含了表示不同类型的PID的字段,而且每个字段需要它自己的散列表。


4个散列表和进程描述符中的相关字段:

Hash表的类型 字段名 说明

PIDTYPE_PID pid 进程的PID

PIDTYPE_TGID tgid 线程组领头进程的PID

PIDTYPE_PGID pgrp 进程组领头进程的PID

PIDTYPE_SID session 会话领头进程的PID


内核初始化期间为4个散列表分配空间,并把它们的地址存入pid_hash数组。在start_kernel函数中调用了pidhash_init:

Cpp代码
  1. void __init pidhash_init(void)  
  2. {  
  3.     int i, j, pidhash_size;  
  4.     unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT);  
  5.   
  6.     pidhash_shift = max(4, fls(megabytes * 4));  
  7.     pidhash_shift = min(12, pidhash_shift);  
  8.     pidhash_size = 1 << pidhash_shift;  
  9.   
  10.     printk("PID hash table entries: %d (order: %d, %Zd bytes)\n",  
  11.         pidhash_size, pidhash_shift,  
  12.         PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head));  
  13.   
  14.     for (i = 0; i < PIDTYPE_MAX; i++) {  
  15.         pid_hash[i] = alloc_bootmem(pidhash_size *  
  16.                     sizeof(*(pid_hash[i])));  
  17.         if (!pid_hash[i])  
  18.             panic("Could not alloc pidhash!\n");  
  19.         for (j = 0; j < pidhash_size; j++)  
  20.             INIT_HLIST_HEAD(&pid_hash[i][j]);  
  21.     }  
  22. }  
void __init pidhash_init(void) { int i, j, pidhash_size; unsigned long megabytes = nr_kernel_pages >> (20 - PAGE_SHIFT); pidhash_shift = max(4, fls(megabytes * 4)); pidhash_shift = min(12, pidhash_shift); pidhash_size = 1 << pidhash_shift; printk("PID hash table entries: %d (order: %d, %Zd bytes)\n", pidhash_size, pidhash_shift, PIDTYPE_MAX * pidhash_size * sizeof(struct hlist_head)); for (i = 0; i < PIDTYPE_MAX; i++) { pid_hash[i] = alloc_bootmem(pidhash_size * sizeof(*(pid_hash[i]))); if (!pid_hash[i]) panic("Could not alloc pidhash!\n"); for (j = 0; j < pidhash_size; j++) INIT_HLIST_HEAD(&pid_hash[i][j]); } }pidhash_shift是表索引的长度,注意这里有个printk,我系统启动的打印信息有这么一行:

Cpp代码
  1. [    0.000000] PID hash table entries: 4096 (order: 12, 16384 bytes)  
[ 0.000000] PID hash table entries: 4096 (order: 12, 16384 bytes)

说 明我系统的pidhash_shift为12,这个值依赖于系统RAM的大小。例如:一个拥有512MB的RAM,每个散列表拥有4个页框,可以拥有 2048个表项。pidhash_init函数中使用alloc_bootmem分配器为散列表分配内存(这是alloc_page,slab还未初始 化),pid_hash的第一维是散列表,第二维是每个散列表中的散列地址。每个地址会对应一个链表,所以这里初始化链表头,如下图:


PIDTYPE_MAX就是散列表的个数,在pid.h中有一个枚举:

Cpp代码
  1. enum pid_type  
  2. {  
  3.     PIDTYPE_PID,  
  4.     PIDTYPE_TGID,  
  5.     PIDTYPE_PGID,  
  6.     PIDTYPE_SID,  
  7.     PIDTYPE_MAX  
  8. };  
enum pid_type { PIDTYPE_PID, PIDTYPE_TGID, PIDTYPE_PGID, PIDTYPE_SID, PIDTYPE_MAX };

用pid_hashfn宏把PID转化为表索引,即哈希地址:

Cpp代码
  1. #define pid_hashfn(x)    hash_long((unsigned long)x, pidhash_shift)  
#define pid_hashfn(x) hash_long((unsigned long)x, pidhash_shift)在32位体系结构中hash_long等价于:
Cpp代码
  1. unsigned long hash_long(unsigned long val, unsigned int bits)  
  2. {  
  3.        unsigned long hash = val * 0x9e370001UL;  
  4.        return hash >> (32 - bits);  
  5. }  
unsigned long hash_long(unsigned long val, unsigned int bits) { unsigned long hash = val * 0x9e370001UL; return hash >> (32 - bits); }

这里我们使pidhash_shift为11,这样表索 引的范围为0~2047,hash_long相当于(pid*0x9e370001)>>21。PID从0~32767会产生冲突,这里解决 冲突的方法就是使用链表。如上图,PID号为199的和PID为29384的进程产生了冲突,被链在同一个哈希地址的链表上。

(199*0x9e370001)>>21 = 199,(29384*0x9e370001)>>21 = 199。

下面来看一下task_struct的pid字段,在task_struct中有:

Cpp代码
  1. struct pid pids[PIDTYPE_MAX];  
struct pid pids[PIDTYPE_MAX];

Cpp代码
  1. struct pid  
  2. {  
  3.     int nr;  
  4.     struct hlist_node pid_chain;  
  5.     struct list_head pid_list;  
  6. };  
struct pid { int nr; struct hlist_node pid_chain; struct list_head pid_list; };nr是进程的PID,pid_chain是将发生冲突的pid链在这个pid_chain链表上,pid_list字段是同一个线程组,会话组或进程组的链接在pid_list链表上,如下图:


这个图里,PID为246的和PID为4351的pid发成冲突,所以链接在pid_chain链表上。同一个线程组的PID为4351的三个进程链接到pid_list上。



阅读(2087) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~