当前位置：首页 > news >正文

Linux进程管理中的hash

news 来源：原创 2024/4/29 8:44:54

Linux内核必须能够根据进程的PID找出对应的PCB。顺序扫描进程链表并检查PCB的PID域是可行但效率相当低的。为了加速查找，引入了哈希表，于是建立了一个pid_hash的结构。

1、pid_hash的声明（kernel/pid.c）：

static struct hlist_head *pid_hash;

pid的初始化是在内核初始化(即start_kernel函数中)的时候完成的。由pidhash_init完成：

/*
 * The pid hash table is scaled according to the amount of memory in the
 * machine.  From a minimum of 16 slots up to 4096 slots at one gigabyte or
 * more.
 */
void __init pidhash_init(void)
{
	int i, pidhash_size;
        //为数组开辟空间
	pid_hash = alloc_large_system_hash("PID", sizeof(*pid_hash), 0, 18,
					   HASH_EARLY | HASH_SMALL,
					   &pidhash_shift, NULL, 4096);
	pidhash_size = 1 << pidhash_shift;//数组的长度

	for (i = 0; i < pidhash_size; i++)
		INIT_HLIST_HEAD(&pid_hash[i]);//将数组中的指针都初始化为NULL
}

alloc_large_system_hash是专门用于为hash表分配一块连续的内存的，参数4096意味着最多4k个项，也就是最多占用1页的内存。哈希数组大小实际上由pidhash_shift决定，默认取4，直接影响了pidhash_size取的大小为4096。
pidhash_init 函数通过宏INIT_HLIST_HEAD把pid_hash数组的每个元素（struct hlist_head类型的变量）都初始化为空指针。

2、hash函数的建立

Linux用一个叫做pid_hashfn的宏来建立（kernel/pid.c文件中）

/*linux-2.6.32.63/kernel/pid.c*/
#define pid_hashfn(nr, ns)	\
	hash_long((unsigned long)nr + (unsigned long)ns, pidhash_shift)
	
/*linux-2.6.32.63/include/linux/hash.h  分析32bits*/
#define hash_long(val, bits) hash_32(val, bits)

/* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

static inline u32 hash_32(u32 val, unsigned int bits)
{
	/* On some cpus multiply is faster, on others gcc will do shifts */
	u32 hash = val * GOLDEN_RATIO_PRIME_32;

	/* High bits are more random, so use them. */
	return hash >> (32 - bits);
}

其中，nr是pid的值，而ns表示的是pid的命名空间（这个是为了支持轻量级虚拟化而引入的新概念）。散列函数pid_hashfn先使关键字（nr和ns的和）乘以0x9e370001UL，然后取乘积的低pidhash_shift位。

仔细分析一下上面的函数：

首先，hash的方式是，让key乘以一个大数，于是结果溢出，就把留在32/64位变量中的值作为hash值，又由于散列表的索引长度有限，我们就取这hash值的高几为作为索引值，之所以取高几位，是因为高位的数更具有随机性，能够减少所谓“冲突”。

那么，乘以的这个大数应该是多少呢？从上面的代码来看，32位系统中这个数是0x9e370001UL。这个数是怎么得到的呢？
“Knuth建议，要得到满意的结果，对于32位机器，2^32做黄金分割，这个大数是最接近黄金分割点的素数，0x9e370001UL就是接近 2^32*(sqrt(5)-1)/2 的一个素数，且这个数可以很方便地通过加运算和位移运算得到，因为它等于2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1。

3、处理冲突

Linux利用链地址法来处理冲突的PID，也就是说，每一个表项是由冲突的PID组成的双向链表，task_struct结构中由两个域pidhash_next和pidhash_prev来实现这个链表，同一个链表中pid由小到大排列。

学习博客：

Linux内核中的PID散列表实例http://blog.csdn.net/npy_lp/article/details/7331245

Linux内核中hash函数的实现http://blog.csdn.net/gaopenghigh/article/details/8831312

linux内核PID管理http://blog.csdn.net/zhanglei4214/article/details/6765913（本文更加深入）