> For the complete documentation index, see [llms.txt](https://s3.shizhz.me/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://s3.shizhz.me/linux-sched/history/o-n-logic.md).

# 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作为奖励。