本文共 5078 字，大约阅读时间需要 16 分钟。
进程调度的基本数据结构运行队列，数据结构是struct runqueue定义在<kernel/sched.c>。
struct runqueue变量，是定义成PER_CPU类型的，一个CPU的核心对应一个运行队列。每个进程在同一时刻只能处于一个运行队列里。static DEFINE_PER_CPU(struct runqueue, runqueues);
有时候必须对运行队列中的信息进行更改，因此必须对其进行加锁，确保在同一时间不会有不同的修改操作，已造成不可预知的后果。当前CPU的核企图给其他CPU核的运行队列上锁的情况偶尔也会发生，这在以后会看到。最通常的给运行队列上锁的技术是task_rq_lock()和task_rq_unlock()函数。
struct runqueue结构的定义如下:198 struct runqueue { 199 spinlock_t lock; 200 201 /* 202 * nr_running and cpu_load should be in the same cacheline because 203 * remote CPUs use both these fields when doing load calculation. 204 */ 205 unsigned long nr_running; 206 #ifdef CONFIG_SMP 207 unsigned long cpu_load; 208 #endif 209 unsigned long long nr_switches; 210 211 /* 212 * This is part of a global counter where only the total sum 213 * over all CPUs matters. A task can increase this counter on 214 * one CPU and if it got migrated afterwards it may decrease 215 * it on another CPU. Always updated under the runqueue lock: 216 */ 217 unsigned long nr_uninterruptible; 218 219 unsigned long expired_timestamp; 220 unsigned long long timestamp_last_tick; 221 task_t *curr, *idle; 222 struct mm_struct *prev_mm; 223 prio_array_t *active, *expired, arrays[2]; 224 int best_expired_prio; 225 atomic_t nr_iowait; } 在runqueue结构的定义中，有这么两个prio_array_t结构指针，分别是活动队列(active)和过气队列(expired)。
定义如下:prio_array_t *active, *expired, arrays[2]; 390 typedef struct prio_array prio_array_t; 185 struct prio_array { 186 unsigned int nr_active; 187 unsigned long bitmap[BITMAP_SIZE]; 188 struct list_head queue[MAX_PRIO]; 189 }; nr_active是当前优先队列中可运行的进程数。MAX_PROI的值为140,用于表示系统中的每个优先级(因为两个Linux使用的优先级映射后的值正好是[0,140])。BITMAP_SIZE的值是5，因为我们用bitmap中的每一位来对应一个系统优先级，共140个优先级所以需要140位来表示。考虑到unsigned long通常为32位长，所以需要5个这样的数据才足够140位(实际上为5 * 32 = 160 位)。到这里我们能看出明显的对应关系，bitmap和queue的容量刚好都能对应于每个优先级。这样的对应关系的作用是什么？
初始化时，bitmap中的每一位都置位0，当某进程变可运行的时候(也就是说它的状态变成TASK_RUNNING)，其优先级对应于bitmap中的位置1。这样就简化了搜寻的工作量——要找到当前可运行的最高优先级的进程，只需要找到bitmap中第一个为1的位。因为优先级数目是固定的，所以搜寻工作的时间复杂度不会受到当前进程数目的影响。在enqueue_task函数中，会设置活动队列和过气队列的中成员。
574 static void enqueue_task(struct task_struct *p, prio_array_t *array) 575 { 576 sched_info_queued(p); 577 list_add_tail(&p->run_list, array->queue + p->prio); 578 __set_bit(p->prio, array->bitmap); 579 array->nr_active++; 580 p->array = array; 581 } 主要做了如下动作：
1)在576行， 通过sched_info_queued函数设置进程的时间片。 2)在577行，把struct task中的run_list加入到prio_array_t活动队列或者过期队列的queue中。 3)在578行，设置bitmap中对应的bit，比如第2个队列，则bitmap中第2个bit。 4)在579行，给nr_active加1，因为加入了1个task到队列中 5)在580行，把struct task中的array指向当前rq中的array指向active或者expired。问题：
1）在prio_array结构中,queue[0]中，是不是只挂一个进程？ 2）在enqueue_task函数中，在578行调用__set_bit(p->prio, array->bitmap);没看到清bitmap位，在进程运行完成后，应该要清除bitmap位。回头再跟代码。转载地址：http://uofab.baihongyu.com/