4. 5.2双向循环链表

哈希表的主要作用是根据进程的pid可以快速地找到对应的进程，但它没有反映进程创建的顺序，也无法反映进程之间的亲属关系，因此引入双向循环链表。每个进程task_struct 结构中的prev_task和next_task域用来实现这种链表，如图4.4所示

图4.4 双向循环链表

宏SET_LINK用来在该链表中插入一个元素：

#define SET_LINKS(p) do { \

(p)->next_task = &init_task; \

(p)->prev_task = init_task.prev_task; \

init_task.prev_task->next_task = (p); \

init_task.prev_task = (p); \

(p)->p_ysptr = NULL; \

if (((p)->p_osptr = (p)->p_pptr->p_cptr) != NULL) \

(p)->p_osptr->p_ysptr = p; \

(p)->p_pptr->p_cptr = p; \

} while (0)

从这段代码可以看出，链表的头和尾都为init_task，它对应的是进程0（pid为0），也就是所谓的空进程，它是所有进程的祖先。这个宏把进程之间的亲属关系也链接起来。另外，还有一个宏for_each_task()：

#define for_each_task(p) \

for (p = &init_task ; (p = p->next_task) != &init_task ; )

这个宏是循环控制语句,注意init_task的作用,因为空进程是一个永远不存在的进程,因此用它做链表的头和尾是安全的。

因为进程的双向循环链表是一个临界资源,因此在使用这个宏时一定要加锁,使用完后开锁。