> 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-1-timing.md).

# 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)在调度时已经奖励过交互式任务，因此这里的逻辑就简单了，这里不再深入讨论。