task_struct结构体中的run_list和array域

他们的定义分别是：

struct list_head run_list;
    prio_array_t *array;

其中，想必struct list_head这个结构体大家很熟悉了

struct list_head {
    struct list_head *next, *prev;
};

然而，prio_array_t的定义又如何呢：

typedef struct prio_array prio_array_t;

struct prio_array {
    unsigned int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];
};

在prio_array结构体中有三个成员：

nr_active ：链表中进程描述符的个数

bitmap[BITMAP_SIZE] ：经过计算BITMAP_SIZE的值就是5，代表的是权限位示图，当相应的权限的进程链表不为空的时候甚至相应的位，long占4个字节，因为4*5*8=160 > 140（所有的权限）。从此可以看出5个已经足够了。

queue[MAX_PRIO] ：其实MAX_PRIO的大小就是140，保存的是每一个权限进程的链表表头。

同时从上面对结构中可以看出，采用数组可以提高检索速度，每一个权限级别维护者一个运行链表，但问题是各级运行链表通过什么来形成，那么此时run_list指针就发挥出了自己的作用了。

光空谈毫无意义，还是用代码说话才更有说服力

static void enqueue_task(struct task_struct *p, prio_array_t *array)
{
    sched_info_queued(p);
    list_add_tail(&p->run_list, array->queue + p->prio);
    __set_bit(p->prio, array->bitmap);
    array->nr_active++;
    p->array = array;
}

通过上面的代码应该就能够说明问题了，list_add_tail宏的作用：将第一个参数插入到第二个参数的链表的前面，因为是双向循环链表，可想而知，如果将参数2设置成为头指针，则参数1所指加入到链表尾中。同时，通过对这段代码的分析，我们可以得到一个如下的简略图

大致的情况如上图所示。

同时，我们可以看出这个链表非常复杂，进程描述符为了减少体积，则在结构体中保留的是prio_array_t类型的指针，可以节约很多的内存，因为一般的指针的大小在32位机中都是4个字节。

再者，prio_array_t类型的指针所指向的区域为所有处在run_list中的所有的进程arrayt区域共享，这也方便了通过任意一个进程就可以很方便访问其他运行队列的进程。