# 2.3.6 O（1）调度器 - 时间分配

每个调度周期结束后需要单独为每个任务分配时间，效率底下。为了解决这个问题，O(1)调度器为每个runqueue准备了两个任务列表，对应的字段为 `prio_array_t *active, *expired, arrays[2];` 其中 `active` 用来存放就绪任务，而 `expired` 用来存放时间片已经耗尽的任务。在调度时，调度器使用 `active` 来寻找下一个任务，这在前文中我们探讨调度逻辑时已经看到了，而当任务的运行时间被耗尽后，系统会立刻为其计算下一轮的运行时间并将其放入 `expired` 列表，这样当 `active` 为空时，调度器就不用暂停所有工作来分配时间，而是直接切换 `active` 与 `expired` 两个列表即可。该逻辑发生在调度函数 `schedule()` 中：

```
/* file: kernel/sched.c */
asmlinkage void __sched schedule(void) {
    array = rq->active;
    if (unlikely(!array->nr_active)) {
        schedstat_inc(rq, sched_switch);
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
    }
}
```

这段代码就在前面主调度逻辑之前。系统在时钟中断函数中会检查任务的运行时间，如果时间耗尽则会为其重新充值，并考虑是否放入 `expired` 列表中。这段逻辑在函数 `schedule_tick()` 中：

```
/* file: kernel/sched.c */
void scheduler_tick(void) {
    /* 拿到当前CPU, 当前CPU 的runqueue, 以及当前正在运行的任务 */
    int cpu = smp_processor_id();
    runqueue_t *rq = this_rq();
    task_t *p = current;

    /* 每个tick将任务的运行时间减1, 如果运行时间已经耗尽，则需要单独处理 */
    if (!--p->time_slice) {
        /* 从 active 列表中剔除，后面根据任务的特点看是放入 active 还是 expired */
        dequeue_task(p, rq->active);
        /* 标记该任务需要调度了 */
        set_tsk_need_resched(p);
        /* 重新计算任务的动态优先级 */
        p->prio = effective_prio(p);
        /* 分配任务下一周期的运行时间 */
        p->time_slice = task_timeslice(p);
        p->first_time_slice = 0;

        if (!rq->expired_timestamp)
            rq->expired_timestamp = jiffies;
        /* 识别任务是否是交互式任务 */
        if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
            /* 非交互式任务，或者是交互式任务，但是已经奖励过了，乖乖到expired列表中去*/
            enqueue_task(p, rq->expired);
            if (p->static_prio < rq->best_expired_prio)
                rq->best_expired_prio = p->static_prio;
        } else
            /* 交互式任务，奖励一下，继续呆在active中 */
            enqueue_task(p, rq->active);
    } else {
        /* 防止交互式任务过长时间独占CPU */
        if (TASK_INTERACTIVE(p) &&
            !((task_timeslice(p) - p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
            (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
            (p->array == rq->active)) {

            requeue_task(p, rq->active);
            set_tsk_need_resched(p);
        }
    }
}
```

如果任务被扔到expired列表，那么它在这一轮周期内就没有机会再运行了，但对于交互式任务而言可能导致响应延迟，造成不好的用户体验，因此我们希望尽可能地不要将交互式任务从active中剔除，系统通过宏 `TASK_INTERACTIVE` 来判断任务是否是交互式任务，主要判断依据是任务的平均睡眠时间。但也要避免交互式任务一直呆在active里面导致expired中的任务被饿死，所以系统会使用宏 `EXPIRED_STARVING` 来判断expired列表中的任务是否要饿死了，如果是的话，那么依然会将任务扔进expired中，乖乖地等待下一轮调度。

计算任务时间片的函数是 `task_timeslice`, O(1)计算时间片时与CPU的频率无关，只根据任务的静态优先级计算出一个确定的时间片。由于O(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-1-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.