# 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给每个任务分配的运行时间很长的话，就会导致一次调度周期很久都不会结束。


---

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