Linux 内核调度器源码解析：从调度入口到挑选下一个进程
在linux内核中，调度器（scheduler）扮演着至关重要的角色，决定了哪个进程将获得CPU的执行时间。本文将深入剖析内核中调度器的代码实现，从入口函数开始，一步步分析如何选择下一个要执行的进程。让我们一同揭开这个内核之谜。
调度器入口
Linux调度器入口函数定义在kernel/sched/core.c中：
asmlinkage __visible void __sched schedule(void)
{
// 获取当前任务结构体的指针
struct task_struct *tsk = current;
// 将任务提交到调度工作队列中
sched_submit_work(tsk);
// 进入调度循环，直到没有需要被调度的任务
do {
// 禁用抢占
preempt_disable();
// 调用实际的调度函数 __schedule，并传入调度策略参数 SM_NONE
__schedule(SM_NONE);
// 启用抢占，但不进行重新调度
sched_preempt_enable_no_resched();
} while (need_resched()); // 循环直到没有需要重新调度的任务
// 更新工作队列中的任务状态
sched_update_worker(tsk);
}
EXPORT_SYMBOL(schedule);
调度器的入口函数是schedule，首先获取当前任务结构体的指针，然后将任务提交到调度工作队列中，接着进入一个循环，该循环会禁用抢占，调用实际的调度函数__schedule，并在循环结束后启用抢占。循环会一直执行，直到没有需要重新调度的任务为止。最后，函数会更新工作队列中任务的状态。函数最后export导出schedule函数以供其他部分使用。
static void __sched __schedule(bool preempt)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
prev = current;
rq = this_rq();
switch_count = &prev->nivcsw;
// 获取下一个要运行的进程
next = pick_next_task(rq);
// 切换到下一个进程
context_switch(rq, prev, next, switch_count);
// 如果需要抢占，启用抢占
if (preempt)
need_resched();
}
} 这里，__schedule函数负责实际的调度操作。首先，它获取了当前任务结构体的指针（prev）、运行队列（rq）以及切换计数器（switch_count）。然后，通过调用pick_next_task函数，它选择下一个要运行的进程（next）。最后，通过context_switch函数，它进行进程切换，将CPU控制权移交给下一个进程。
具体如何挑选下一个需要运行的进程，就要扒开pick_next_task函数。
pick_next_task
/*
* 选择下一个要运行的任务。
*/
static inline struct task_struct *
__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
const struct sched_class *class; // 定义调度类指针
struct task_struct *p; // 定义任务结构体指针
// 优化：如果前一个任务是公平调度类中的任务，且运行队列中的任务数与CFS队列中的任务数相等，
// 则可以直接选择下一个公平类任务，因为其他调度类的任务无法抢占CPU。
if (likely(!sched_class_above(prev->sched_class, &fAIr_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = pick_next_task_fair(rq, prev, rf); // 选择下一个公平调度类任务
if (unlikely(p == RETRY_TASK)) // 如果选择任务失败，需要重新尝试
goto restart;
if (!p) {
put_prev_task(rq, prev);
p = pick_next_task_idle(rq); // 如果没有可运行任务，则选择下一个空转调度类任务
}
return p;
}
restart:
put_prev_task_balance(rq, prev, rf); // 将前一个任务放回队列，进行重新平衡
// 遍历所有调度类
for_each_class(class) {
p = class->pick_next_task(rq); // 选择下一个任务
if (p)
return p;
}
BUG(); // 如果没有可运行任务，引发BUG。空转类应该始终有可运行的任务。
}
这段代码是用于选择下一个要运行的任务的函数。首先，它检查是否可以优化选择下一个任务，如果前一个任务是公平调度类中的任务，并且运行队列中的任务数与CFS队列中的任务数相等，就可以直接选择下一个公平调度类任务。如果选择任务失败，会重新尝试，然后如果没有可运行任务，将选择下一个空转调度类任务。如果不满足优化条件，将会重新平衡队列，然后遍历所有的调度类，选择下一个任务。如果没有可运行任务，将引发BUG，因为空转类应该始终有可运行的任务。
struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
struct cfs_rq *cfs_rq = &rq->cfs; // 获取CFS队列
struct sched_entity *se; // 定义调度实体指针
struct task_struct *p; // 定义任务结构体指针
int new_tasks;
again:
// 如果没有可运行的公平调度任务，跳转到idle标签
if (!sched_fair_runnable(rq))
goto idle;
#ifdef CONFIG_FAIR_GROUP_SCHED
// 如果没有前一个任务，或者前一个任务不属于公平调度类，跳转到simple标签
if (!prev || prev->sched_class != &fair_sched_class)
goto simple;
do {
struct sched_entity *curr = cfs_rq->curr;
// 如果当前任务存在
if (curr) {
// 如果当前任务在队列上，则更新其运行时间
if (curr->on_rq)
update_curr(cfs_rq);
else
curr = NULL;
// 如果CFS队列的运行时间不正常，跳转到idle标签
if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
cfs_rq = &rq->cfs;
// 如果没有可运行任务，跳转到idle标签
if (!cfs_rq->nr_running)
goto idle;
goto simple;
}
}
// 选择下一个调度实体，并切换到相应的CFS队列
se = pick_next_entity(cfs_rq, curr);
cfs_rq = group_cfs_rq(se);
} while (cfs_rq);
// 获取与选定实体关联的任务结构体
p = task_of(se);
// 如果前一个任务不等于选定任务，进行任务切换
if (prev != p) {
struct sched_entity *pse = &prev->se;
while (!(cfs_rq = is_same_group(se, pse))) {
int se_depth = se->depth;
int pse_depth = pse->depth;
if (se_depth <= pse_depth) {
put_prev_entity(cfs_rq_of(pse), pse);
pse = parent_entity(pse);
}
if (se_depth >= pse_depth) {
set_next_entity(cfs_rq_of(se), se);
se = parent_entity(se);
}
}
put_prev_entity(cfs_rq, pse);
set_next_entity(cfs_rq, se);
}
goto done;
simple:
#endif
// 如果有前一个任务，将其放回队列
if (prev)
put_prev_task(rq, prev);
do {
// 选择下一个调度实体，并切换到相应的CFS队列
se = pick_next_entity(cfs_rq, NULL);
set_next_entity(cfs_rq, se);
cfs_rq = group_cfs_rq(se);
} while (cfs_rq);
// 获取与选定实体关联的任务结构体
p = task_of(se);
done: __maybe_unused;
#ifdef CONFIG_SMP
// 将下一个正在运行的任务移动到队列的前面
list_move(&p->se.group_node, &rq->cfs_tasks);
#endif
// 如果启用高精度定时器，开始高精度定时
if (hrtick_enabled_fair(rq))
hrtick_start_fair(rq, p);
// 更新不适合运行的任务状态
update_misfit_status(p, rq);
return p;
idle:
// 如果没有rf标志，返回NULL
if (!rf)
return NULL;
// 尝试进行新的空闲平衡操作
new_tasks = newidle_balance(rq, rf);
// 如果新的平衡操作失败，返回RETRY_TASK标志
if (new_tasks < 0)
return RETRY_TASK;
// 如果有新的可运行任务，回到again标签重新选择
if (new_tasks > 0)
goto again;
// 如果队列即将变为空闲状态，检查是否需要更新时钟pelt的lost_idle_time
update_idle_rq_clock_pelt(rq);
return NULL;
}
这个函数用于选择下一个要在公平调度类中运行的任务。函数中包含了条件判断和循环，以确保选择最适合的任务。
/*
* 选择下一个调度实体，考虑以下因素，按照顺序：
* 1) 在进程/任务组之间保持公平性
* 2) 选择“下一个”进程，因为某个进程确实希望运行
* 3) 选择“上一个”进程，以提高缓存局部性
* 4) 如果其他任务可用，则不运行“跳过”的进程
*/
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
struct sched_entity *left = __pick_first_entity(cfs_rq); // 获取最左边的实体
struct sched_entity *se;
/*
* 如果 curr 被设置，我们必须查看它是否位于树中最左边的实体的左侧，
* 前提是树中确实有实体存在。
*/
if (!left || (curr && entity_before(curr, left)))
left = curr;
se = left; /* 理想情况下，我们运行最左边的实体 */
/*
* 避免运行跳过的实体，如果可以不运行其他实体而不会太不公平。
*/
if (cfs_rq->skip && cfs_rq->skip == se) {
struct sched_entity *second;
if (se == curr) {
second = __pick_first_entity(cfs_rq); // 获取最左边的实体
} else {
second = __pick_next_entity(se); // 获取下一个实体
if (!second || (curr && entity_before(curr, second)))
second = curr;
}
if (second && wakeup_preempt_entity(second, left) < 1)
se = second;
}
if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1) {
/*
* 有人确实希望运行这个实体。如果不不公平，就运行它。
*/
se = cfs_rq->next;
} else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1) {
/*
* 更倾向于运行最后一个实体，尝试将 CPU 返回到一个被抢占的任务。
*/
se = cfs_rq->last;
}
return se;
}
if (se == curr) {
second = __pick_first_entity(cfs_rq); // 获取最左边的实体
} else {
second = __pick_next_entity(se); // 获取下一个实体
if (!second || (curr && entity_before(curr, second)))
second = curr;
}
if (second && wakeup_preempt_entity(second, left) < 1)
se = second;
return se; } 函数pick_next_entity的作用是选择下一个要运行的调度实体，它根据一系列因素来决定选择哪个实体，以确保公平性、满足任务需求，并尽量提高缓存局部性。
总结
通过深入分析Linux内核调度器的代码实现，我们了解了调度器的入口函数和选择下一个执行进程的过程。这个过程是内核多任务处理的核心，确保了系统资源的合理分配。深入理解调度器的工作原理将有助于我们更好地优化系统性能，提高响应速度。
