2.3.5 O（1）调度器 - 调度逻辑

在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 用来标识列表是否为空。示意图如下：

RT Task Runqueue

图中展示的任务列表中，只有优先级为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 的章节单独讨论。