在O(n)调度器中，“运行队列”实际上只是个逻辑概念，内核只是用一个列表将就绪任务串起来了而已，并没有单独定义一个数据结构。O(1)调度器的实现中专门定义了结构体 struct runqueue 来对各种信息进行封装：
/* file: kernel/sched.c */
struct runqueue {
spinlock_t lock;
unsigned long nr_running;
#ifdef CONFIG_SMP
unsigned long cpu_load;
#endif
unsigned long long nr_switches;
unsigned long nr_uninterruptible;
unsigned long expired_timestamp;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int best_expired_prio;
atomic_t nr_iowait;
#ifdef CONFIG_SMP
/* SMP 下用于负载均衡的字段 */
struct sched_domain *sd;
/* For active balancing */
int active_balance;
int push_cpu;
task_t *migration_thread;
struct list_head migration_queue;
#endif
#ifdef CONFIG_SCHEDSTATS
/* 删掉调度器的信息统计字段*/
#endif
};
为了解决全局运行队列额问题，O(1)调度器为每个CPU单独维护了一个运行队列（runqueue），这种变量叫着 per cpu variable, 我们在核心概念一章中讨论运行队列时已经提及过了。队列的申明如下：
/* file: kernel/sched.c */
static DEFINE_PER_CPU(struct runqueue, runqueues);
这样CPU在调度时，会首先拿到与自己绑定的运行队列在进行各种操作，不会影响其他CPU的工作。
为了降低时间复杂度，调度器在runqueue中又为每个优先级单独维护了一个任务列表，这部分信息封装在数据结构 struct prio_array 中：
/* file: kernel/sched.c */
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
其中数组 queue 中的每个元素都是一个任务列表，位图 bitmap 用来标识列表是否为空。示意图如下：
图中展示的任务列表中，只有优先级为1与4的列表非空。有了 prio_array 的支持，调度器在寻找下一个任务时的时间复杂度就变为了O(1): 先找到bitmap中的第一个非0的位置，然后将其作为索引从queue中取出任务列表，再取出第一个任务即可。核心调度逻辑如下：
asmlinkage void __sched schedule(void) {
task_t *prev, *next;
runqueue_t *rq;
prio_array_t *array;
struct list_head *queue;
unsigned long long now;
unsigned long run_time;
int cpu, idx;
/* 拿到当前CPU的runqueue */
rq = this_rq();
/* 拿到队列中的任务列表，为prio_array_t类型，实际上就是上面讨论过的
* prio_array */
array = rq->active;
/* 从prio_array中找到下一个进程，O(1)复杂度 */
idx = sched_find_first_bit(array->bitmap); /* 找到目标优先级队列的索引 */
/* 通过索引拿到对应的runqueue, 该队列即是当前优先级最高的任务队列 */
queue = array->queue + idx;
/* 从runqueue中取出第一个task, 该task即是下一个应该扔CPU上运行的task */
next = list_entry(queue->next, task_t, run_list);
}
调度器从 rq->active 列表中挑选出下一个任务，在新的数据结构的支持下，总体的时间复杂度为 O(1), 这也是该调度器被叫着O(1)的原因。
当然，由于每个CPU现在都有自己的runqueue, 因此调度器还需要对各个CPU做负载均衡，这个主题我们会在后面 sched_domain 的章节单独讨论。
