# 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`, 我们在[核心概念](/linux-sched/concepts.md)一章中讨论运行队列时已经提及过了。队列的申明如下：

```
/* 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](/files/2R7OLIHcRavVwCOP6Jt5)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/history/o-1-logic.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.