Processes（六）The process list

The process list

The first example of a doubly linked list we will examine is the process list, a list that links together all existing process descriptors. Each task_struct structure includes a tasks field of type list_head whose prev and next fields point, respectively, to the previous and to the next task_struct element.

我们将要介绍的第一个双向链表是进程链表，一个将所有存在的进程描述符链接起来的链表。每个task_struct结构包含了一个类型为list_head的task成员，它的prev和next成员分别指向前一个和下一个task_struct元素的list_head成员task。

The head of the process list is the init_task task_struct descriptor; it is the process descriptor of the so-called process 0 or swapper (see the section "Kernel Threads" later in this chapter). The tasks->prev field of init_task points to the tasks field of the process descriptor inserted last in the list.

进程链表的头是init_task task_struct描述符；它是所谓的进程0也叫swapper进程的进程描述符。init_task的task->prev成员指向了最后插入链表的进程描述符的task成员。

The SET_LINKS and REMOVE_LINKS macros are used to insert and to remove a process descriptor in the process list, respectively. These macros also take care of the parenthood relationship of the process (see the section "How Processes Are Organized" later in this chapter).

SET_LINKS和REMOVE_LINKS宏分别用来插入和移除进程链表中的进程描述符。这些宏也考虑了进程之间的父子关系。

Another useful macro, called for_each_process, scans the whole process list. It is defined as:

另外一个有用的宏，叫做for_each_process，遍历了整个进程链表。它定义为：

#define for_each_process(p) \
       for (p=&init_task; (p=list_entry((p)->tasks.next, \
                                        struct task_struct, tasks) \
                                       ) != &init_task; )

The macro is the loop control statement after which the kernel programmer supplies the loop. Notice how the init_task process descriptor just plays the role of list header. The macro starts by moving past init_task to the next task and continues until it reaches init_task again (thanks to the circularity of the list). At each iteration, the variable passed as the argument of the macro contains the address of the currently scanned process descriptor, as returned by the list_entry macro.

这个宏是内核程序员提供的循环控制语句。注意到init_task进程描述符仅扮演链表头的角色。这个宏从init_task开始移动到下一个task，直到它再次到达init_task（有用这个链表是一个环）。在每次迭代中，以参数传入宏的变量包含了当前遍历的进程描述符的地址，这是由list_entry宏求得的。

The lists of TASK_RUNNING processes

When looking for a new process to run on a CPU, the kernel has to consider only the runnable processes (that is, the processes in the TASK_RUNNING state).

当寻找一个新的进程让它使用CPU时，内核不得不考虑所有可以运行的进程（也就是说，处在TASK_RUNNING状态的进程）。

Earlier Linux versions put all runnable processes in the same list called runqueue. Because it would be too costly to maintain the list ordered according to process priorities, the earlier schedulers were compelled to scan the whole list in order to select the "best" runnable process.

早期版本的Linux将所有可运行的进程放在同一个链表中，称为运行队列。因为要维护这个链表的节点按进程优先级排序的花销很大，早期的调度程序被迫遍历整个链表使得可以选出了“最佳”可运行的进程。

Linux 2.6 implements the runqueue differently. The aim is to allow the scheduler to select the best runnable process in constant time, independently of the number of runnable processes. We'll defer to Chapter 7 a detailed description of this new kind of runqueue, and we'll provide here only some basic information.

Linux2.6不再这样实现这个运行队列。目的是容许调度程序在恒定的时间内选出最佳可运行的进程，而不依赖于可运行进程的数目（复杂度为O(1)的算法）。下面只是提供一些基本的信息。

The trick used to achieve the scheduler speedup consists of splitting the runqueue in many lists of runnable processes, one list per process priority. Each task_struct descriptor includes a run_list field of type list_head. If the process priority is equal to k (a value ranging between 0 and 139), the run_list field links the process descriptor into the list of runnable processes having priority k. Furthermore, on a multiprocessor system, each CPU has its own runqueue, that is, its own set of lists of processes. This is a classic example of making a data structures more complex to improve performance: to make scheduler operations more efficient, the runqueue list has been split into 140 different lists!

加速调度程序的诀窍是将运行队列划分成很多个可运行进程的链表，每个优先级一个链表。每个task_struct结构包含了一个类型为list_head的成员run_list。如果进程的优先级等于k（介于0到139之间的值），run_list成员就链接这个进程描述符到那个可运行进程优先级为k的链表中。而且，在多处理器系统上，每个CPU有它自己的运行队列，也就是说，它自己的进程链表。这是一个经典的例子，展示了通过使数据结构变得更复杂来提升性能(空间换时间)：为了使调度程序更加有效率地执行，运行队列被分成了140个不同的链表。

As we'll see, the kernel must preserve a lot of data for every runqueue in the system; however, the main data structures of a runqueue are the lists of process descriptors belonging to the runqueue; all these lists are implemented by a single prio_array_t data structure, whose fields are shown in Table 3-2.

内核必须在系统中为每个运行队列保留大量的数据；然而，一个运行队列主要的数据结构是属于这个运行队列的进程描述符的链表；所有这些链表由一个单独的prio_array_t数据结构实现，它的成员如下：

Table 3-2. The fields of the prio_array_t data structure

Type	Field	Description
int	nr_active	The number of process descriptors linked into the lists 链接到这个链表的进程描述符的数目
unsigned long [5]	bitmap	A priority bitmap: each flag is set if and only if the corresponding priority list is not empty 优先级映射：当且仅当对应的优先级链表不为空时设置对应标志（5*32=160）
struct list_head [140]	queue	The 140 heads of the priority lists 140个优先级链表的头

The enqueue_task(p,array) function inserts a process descriptor into a runqueue list; its code is essentially equivalent to:

enqueue_task(p, array)函数将一个进程描述符插到一个运行链表中；它的代码基本上等于：

    list_add_tail(&p->run_list, &array->queue[p->prio]);
    __set_bit(p->prio, array->bitmap);
    array->nr_active++;
    p->array = array;

The prio field of the process descriptor stores the dynamic priority of the process, while the array field is a pointer to the prio_array_t data structure of its current runqueue. Similarly, the dequeue_task(p,array) function removes a process descriptor from a runqueue list.

进程描述符的prio成员存储了进程的动态优先级，而array成员是一个指向当前运行队列的prio_array_t数据结构的指针。近似地，dequeue_task(p, array)将一个进程描述符从进程队列中移除。