| layout | title | category | description | tags |
|---|---|---|---|---|
post |
进程链表 |
进程 |
进程链表... |
进程链表 run_list |
进程链表是一种双向链表数据结构（list_head），简单的说一下双向链表。每一个双向链表，都有一组操作，插入和删除一个元素，扫描链表等等。双向链表和链表相同，但双向链表除了有指向下一个元素的指针，还有指向上一个元素的指针，所以被称为双向连表。
进程链表
Linux内核提供了list_head数据结构，字段next和prev分表标识链表向后和向前的指针元素。list_head字段的指针中存的是另一个list_head字段的地址。新链表使用宏LIST_HEAD(list_name)创建。
进程链表是一个双向链表，进程链表把所有进程的描述符链接起来。每个task_struct 结构都包含一个list_head类型的tasks字段，这个类型的orev和next字段分别指向前面和后面的task_struct元素。
进程链表的表头是init_task描述符，就是0进程（process 0）或swapper进程的进程描述符。init_task的tasks.prev字段指向链表中最后插入的进程描述符的tasks字段。SET_LINKS和REMOVE_LINKS宏分别用于从进程链表中插入和删除一个进程描述符。另外for_each_process宏用来扫描整个进程链表。
当内核寻找一个在CPU上运行的进程，必须值考虑可运行的进程。早先的Linux把所有可运行的进程都放在一个叫做运行队列（runqueue）的链表中，由于维持连表中的进程优先级排序开销过大，因此早起的调度程序不得不为了某些特殊的功能扫描整个链表。在Linux 2.6实现的运行队列则有所不同。其目的是让调度程序能在固定的时间内选出『最佳』可运行进程，与队列中可运行的进程数无关。
提高调度程序运行速度的诀窍是建立多个可运行进程链表，每种进程优先级对应一个不同的链表。
每个task_struct描述符包含一个list_head类型的字段run_list。如果进程的优先级等于k1，run_list字段把该进程加入优先权为k的可允许进程连表中。在多CPU系统中，每个CPU都有自己的运行队列，这是一个通过使数据结构更复杂来改善性能的典型例子。
进程描述符的prio字段存放进程的动态优先级，而array字段是一个指针，指向当前运行队列的prio_array_t的数据结构。
Footnotes
-
其取值范围从0到139。 ↩