# 2.3.1 O（n）调度器 - 调度逻辑

[O(n) 调度器](https://en.wikipedia.org/wiki/O\(n\)_scheduler)是 Linux 在 2.4 版的内核中引入的，由于调度器算法的时间复杂度为 O(n), 该调度器的名字也由此而来；本节我们基于 [linux-2.4.18](https://cdn.kernel.org/pub/linux/kernel/v2.4/linux-2.4.18.tar.gz) 来了解一下该调度器的实现逻辑。

整个O(n)调度器的实现都在文件 `kernel/sched.c` 中，总共只有1300行左右的代码，整个调度逻辑的代码量远少于当前版本中的任何一个调度器（例如 dl 与 rt 调度器都有接近3000行代码），因此其实现思路非常简单。

我们先来看一下O(n)调度器如何管理任务。O(n)调度器采用一个全局的运行队列来管理任务，该队列的表头保存在全局变量 `runqueue_head` 中。所有的就绪任务都会被放入该队列中，每次调度时，系统会遍历整个队列然后挑出最适合的任务，即优先级最高的任务来执行，因此该调度算法的时间复杂度为O(n), 这也是该调度器被叫着O(n)调度器的原因。

函数 `schedule()` 是调度逻辑的入口，其中选取任务的逻辑如下：

```
asmlinkage void schedule(void) {
    next = idle_task(this_cpu);
    c = -1000;
    list_for_each(tmp, &runqueue_head) {
        p = list_entry(tmp, struct task_struct, run_list);
        if (can_schedule(p, this_cpu)) { /* 判断 p 是否可以在 this_cpu 上运行 */
            int weight = goodness(p, this_cpu, prev->active_mm);
            if (weight > c)
                c = weight, next = p;
        }
    }
}
```

调度器通过一次遍历选取了优先级最高的任务，如果队列为空，则系统将在该CPU上运行idle task。任务的优先级通过函数 `goodness()` 来判断。

注意在该版本中，调度器仅支持实时任务与普通任务，实时进程的调度策略包含 `SCHED_FIFO` 与 `SCHED_RR`, 普通进程的调度策略叫 `SCHED_NORMAL`, 相当于现在的 `SCHED_NORMAL`, 实时进程的优先级高于普通进程，需要优先保证其时间供给。

`goodness()` 在计算任务优先级时会综合考虑各种因素，以确保系统在时间分配上是公平的。 `struct task_struct` 中与优先级计算有关的字段包含如下几个：

```
/* file: include/linux/sched.h */

struct task_struct {
    /* 任务当前剩余的运行时间，以时钟嘀嗒（tick）为单位 */
    long counter;
    /* 普通任务的优先级，即用户设置的进程 nice 值 */
    long nice;
    /* 任务的调度策略 */
    unsigned long policy;
    /* 任务的内存地址空间，由同一个进程的不同线程共享 */
    struct mm_struct *mm;
    /* 实时任务的优先级 */
    unsigned long rt_priority;
}
```

我们将 `nice` 与 `rt_priority` 叫着静态优先级，因为他们是用户设置的，并且在任务运行过程中不会改变。函数 `goodness()` 的返回结果我们叫着动态优先级，动态优先级是基于静态优先级计算出来的，并且综合考虑了其它各种情况。其完整代码如下：

```
static inline int goodness(struct task_struct *p, int this_cpu,
                           struct mm_struct *this_mm) {
    int weight;

    weight = -1;
    if (p->policy & SCHED_YIELD)
        goto out;

    /* 普通任务，静态有限级为 nice */
    if (p->policy == SCHED_OTHER) {
        /* 根据任务剩余的时间对任务进行奖励 */
        weight = p->counter;

        /* 如果该任务已经没有剩余时间，则直接忽略 */
        if (!weight)
            goto out;

#ifdef CONFIG_SMP
        /* 根据 CPU 对任务权重进行奖励 */
        if (p->processor == this_cpu)
            weight += PROC_CHANGE_PENALTY;
#endif

        /* 根据内存空间对任务权重进行奖励 */
        if (p->mm == this_mm || !p->mm)
            weight += 1;
        weight += 20 - p->nice;
        goto out;
    }

    /* 实时任务，静态优先级为 rt_priority */
    weight = 1000 + p->rt_priority;
out:
    return weight;
}
```

对于实时任务，系统将其静态优先级（`rt_priority`）加上1000然后返回，这样能够确保所有实时任务的动态优先级都高于普通进程。而对于普通进程，系统除了考虑静态优先级（nice）之外，还会如下几个方面对优先级进行调整：

1. 根据任务的剩余时间进行调整 如果一个任务剩余的CPU时间很多，就说明该任务之前得到的运行机会很少，可能是任务在等待某个外部事件（例如IO事件），也可能是一直被高优先级的任务排挤。为了更加公平，系统在每次调度时会将任务的剩余时间作为权重的奖励，这样越到调度后期，剩余时间更多的任务就越有机会被调度。
2. 根据CPU进行调整 在 SMP 架构中，如果将任务 p 继续运行在其上次运行的 CPU 上的话，可能能够提升 CPU 缓存与 TLB 的命中率。
3. 根据任务的内存空间进行调整 代码中 `p->mm == this_mm` 用来判断任务p与当前任务的内存地址空间是否一样，如果等式成立，则说明两个任务是同一个进程中的两个线程；而 `!p->mm` 用来判断任务 p 是否是内核线程，所有的内核线程都共享一个内存空间。在这两种情况下切换任务的话运行效率会更高，因为进程切换时不用切换地址空间，所以调度器会为权重+1作为奖励。


---

# 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-n-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.