# 2.3.2 O（n）调度器 - 时间分配

对普通任务而言，为了保证系统在时间分配上的公平性，O(n)调度器按照“轮”来计量调度周期，在每轮调度中，调度器根据各个任务的优先级为其分配时间，当所有任务的时间片都消耗完了之后，本轮度结束，系统开启下一轮调度。在 `goodness()` 中我们可以看到，如果一个普通任务已经没有了剩余时间，则会直接被忽略。

> 实时任务不受调度周期的限制，因为实时任务的高优先级最高，调度器要确保只要实时任务处于Ready状态，那么就立刻被调度到，本质上不存在预先分配时间的必须性。
>
> 调度器只是用运行时间来完成对 `SCHED_RR` 任务的轮询控制，函数 `schedule()` 在遍历就绪队列之前存在如下逻辑：
>
> ```
> asmlinkage void schedule(void) {
>     if (unlikely(prev->policy == SCHED_RR))
>         if (!prev->counter) {
>             prev->counter = NICE_TO_TICKS(prev->nice);
>             move_last_runqueue(prev);
>         }
>     ｝
> ```
>
> 如果当前 `SCHED_RR` 任务的运行时间已经耗尽，则重新通过 `NICE_TO_TICKS(prev->nice)` 重新为其分配时间，并将其移动到队列尾部，这样如果队列中有相同优先级的 `SCHED_RR` 任务的话，本次就会被选中，从而达到轮询的目的。

如果在遍历队列时没有找到合适的任务，那么说明所有任务的运行时间都已经耗尽，本次调度周期已经结束了，调度器需要为任务分配时间、开启新的一轮调度周期。处理该逻辑的代码如下：

```
/* file: kernel/sched.c */

asmlinkage void schedule(void) {
    /* 删除前面的代码 */

    /* 1. 遍历队列 */
repeat_schedule:
    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;
        }
    }

    /* 2. 通过 c 判断是否有合适的任务被选中 */
    if (unlikely(!c)) {
        struct task_struct *p;

        spin_unlock_irq(&runqueue_lock);
        read_lock(&tasklist_lock);
        /* 遍历系统的所有任务，并为其分配运行时间 */
        for_each_task(p) p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
        read_unlock(&tasklist_lock);
        spin_lock_irq(&runqueue_lock);
        /* 分配完运行时间后重新调度 */
        goto repeat_schedule;
    }
}

/* 删除后面的代码 */
```

在下一轮调度周期中，任务的运行时间为 `(p->counter >> 1) + NICE_TO_TICKS(p->nice);`, 这里涉及两个方面：

1. p->counter >> 1 \
   上面遍历时不是没有找到合适的任务吗，那这里为何还要关心 p->counter 呢？因为上面遍历的是就绪队列（`runqueue_head`），所以调度器只是没有找到合适的就绪任务，而这里为任务分配时间片时，针对的是系统所有的任务。 此时系统中处于睡眠状态的任务就可能还有剩余时间，因此我们需要对这些任务的运行时间进行累积，让他们醒过来之后能够有更多的机会运行。为了避免此类任务的运行时间无限累积下去，每次都只累计一半的剩余时间。
2. `NICE_TO_TICKS`(p->nice) \
   ticks 就代表着运行时间，宏 `NICE_TO_TICKS` 根据任务的静态优先级（nice）为其分配运行时间。O(n)调度器的时间分配与CPU 频率也有关，具体逻辑如下：

   ```
   /* file: kernel/sched.c */

   #if HZ < 200
   #define TICK_SCALE(x) ((x) >> 2)
   #elif HZ < 400
   #define TICK_SCALE(x) ((x) >> 1)
   #elif HZ < 800
   #define TICK_SCALE(x) (x)
   #elif HZ < 1600
   #define TICK_SCALE(x) ((x) << 1)
   #else
   #define TICK_SCALE(x) ((x) << 2)
   #endif

   #define NICE_TO_TICKS(nice) (TICK_SCALE(20 - (nice)) + 1)
   ```

   从直觉上来说，给任务分配时间应该只与优先级相关，与CPU的频率无关。系统做这种处理的目的是为了将运行时间根据CPU的频率做一个伸缩(scale), 否则如果一个低频CPU给每个任务分配的运行时间很长的话，就会导致一次调度周期很久都不会结束。