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