上文介绍了cfs的几个特征点权重/vruntime/调度周期，以及说明了cfs调度的数据结构，这些信息可以宏观上看到调度器的实现方式，本文再基于调度的一个通用概念enqueue进行介绍。
什么是enqueue，简单来说就是任务到来的时候，需要选enqueue给到调度器，由调度器根据策略来选择哪个任务运行，所以enqueue是调度器的数据来源
任务创建通过fork调用，如下
SYSCALL_DEFINE0(fork) { struct kernel_clone_args args = { .exit_signal = SIGCHLD, }; return kernel_clone(&args); }
kernel_clone是一层封装，我们抓kernel_clone的实现
pid_t kernel_clone(struct kernel_clone_args *args) { wake_up_new_task(p); }
可以看到，任务fork的时候，会主动触发一次wake_up，其流程如下
void wake_up_new_task(struct task_struct *p) { p->state = TASK_RUNNING; activate_task(rq, p, ENQUEUE_NOCLOCK); check_preempt_curr(rq, p, WF_FORK); }
在activate_task里面入队
void activate_task(struct rq *rq, struct task_struct *p, int flags) { if (task_on_rq_migrating(p)) flags |= ENQUEUE_MIGRATED; enqueue_task(rq, p, flags); p->on_rq = TASK_ON_RQ_QUEUED; }
enqueue_task实际上是一个hook，调用对应的sched_class的enqueue_task回调
static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags) { if (!(flags & ENQUEUE_NOCLOCK)) update_rq_clock(rq); if (!(flags & ENQUEUE_RESTORE)) { sched_info_queued(rq, p); psi_enqueue(p, flags & ENQUEUE_WAKEUP); } uclamp_rq_inc(rq, p); trace_android_rvh_enqueue_task(rq, p, flags); p->sched_class->enqueue_task(rq, p, flags); trace_android_rvh_after_enqueue_task(rq, p); }
cfs的sched_class的结构初始化如下
const struct sched_class fair_sched_class __section("__fair_sched_class") = { .enqueue_task = enqueue_task_fair, .dequeue_task = dequeue_task_fair, .yield_task = yield_task_fair, .yield_to_task = yield_to_task_fair, .check_preempt_curr = check_preempt_wakeup, .pick_next_task = __pick_next_task_fair, .put_prev_task = put_prev_task_fair, .set_next_task = set_next_task_fair, #ifdef CONFIG_SMP .balance = balance_fair, .select_task_rq = select_task_rq_fair, .migrate_task_rq = migrate_task_rq_fair, .rq_online = rq_online_fair, .rq_offline = rq_offline_fair, .task_dead = task_dead_fair, .set_cpus_allowed = set_cpus_allowed_common, #endif .task_tick = task_tick_fair, .task_fork = task_fork_fair, .prio_changed = prio_changed_fair, .switched_from = switched_from_fair, .switched_to = switched_to_fair, .get_rr_interval = get_rr_interval_fair, .update_curr = update_curr_fair, #ifdef CONFIG_FAIR_GROUP_SCHED .task_change_group = task_change_group_fair, #endif #ifdef CONFIG_UCLAMP_TASK .uclamp_enabled = 1, #endif };
所以入队其实就是 enqueue_task_fair，抓重点，我们找enqueue做了什么
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags) { for_each_sched_entity(se) { if (se->on_rq) break; cfs_rq = cfs_rq_of(se); enqueue_entity(cfs_rq, se, flags); cfs_rq->h_nr_running++; cfs_rq->idle_h_nr_running += idle_h_nr_running; flags = ENQUEUE_WAKEUP; } }
for_each_sched_entity是遍历了task_struct的shed_entity，这里相当于遍历了cfs的每一层se
真正的enqueue的操作是将sched_entity加入到rb-tree上，所以我们查看enqueue_entity，而enqueue_entity会维护cfs的信息一致性，大概如下
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { update_curr(cfs_rq); update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH); se_update_runnable(se); update_cfs_group(se); account_entity_enqueue(cfs_rq, se); if (flags & ENQUEUE_WAKEUP) place_entity(cfs_rq, se, 0); /* Entity has migrated, no longer consider this task hot */ if (flags & ENQUEUE_MIGRATED) se->exec_start = 0; check_schedstat_required(); update_stats_enqueue(cfs_rq, se, flags); check_spread(cfs_rq, se); if (!curr) __enqueue_entity(cfs_rq, se); se->on_rq = 1; }
可以看到，enqueue_entity做了很多cfs上的状态更新，如update_load_avg更新pelt的load，se_update_runnable更新se->runnable_weight等等
最后执行enqueue的操作是__enqueue_entity
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node; struct rb_node *parent = NULL; struct sched_entity *entry; bool leftmost = true; trace_android_rvh_enqueue_entity(cfs_rq, se); /* * Find the right place in the rbtree: */ while (*link) { parent = *link; entry = rb_entry(parent, struct sched_entity, run_node); /* * We dont care about collisions. Nodes with * the same key stay together. */ if (entity_before(se, entry)) { link = &parent->rb_left; } else { link = &parent->rb_right; leftmost = false; } } rb_link_node(&se->run_node, parent, link); rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost); }
这里将一个调度实体按照其 vruntime 的大小，插入到 CFS 运行队列的红黑树中，一共两步，插入和染色。关于rb-tree的可以查看文章《rb-tree实现》
上面已经把基本流程过了，任务唤醒场景的代码调用链为
try_to_wake_up ttwu_queue ttwu_do_activate activate_task
migrate_tasks __migrate_task move_queued_task activate_task
上面介绍了CFS调度enqueue的几个大的场景，现在我们看代码的一个经典注释
/* * MIGRATION * * dequeue * update_curr() * update_min_vruntime() * vruntime -= min_vruntime * * enqueue * update_curr() * update_min_vruntime() * vruntime += min_vruntime * * this way the vruntime transition between RQs is done when both * min_vruntime are up-to-date. * * WAKEUP (remote) * * ->migrate_task_rq_fair() (p->state == TASK_WAKING) * vruntime -= min_vruntime * * enqueue * update_curr() * update_min_vruntime() * vruntime += min_vruntime * * this way we don't have the most up-to-date min_vruntime on the originating * CPU and an up-to-date min_vruntime on the destination CPU. */
根据上面的注释，我们看到，其在migration/wakeup两个场景上的入队和出队操作都自行将vruntime先减去min_vruntime后又加上min_vruntime了。
这个min_vruntime是per-cpu上遍历整个runqueue中最小的vruntime的记录值，也就是说，这个min_vruntime在每个CPU上的值并不一样，所以它有两个作用
关于上述的1，这个比较清晰明了，在讨论步幅调度的时候就提到了如果新任务的步幅是0，那么其他任务很容易饿死，所以新的任务需要带一个很小的步幅，同样对于cfs也是，这个值是min_vruntime，它记录了runqueue中最小的vruntime
而上述的2，它是怎么维护公平性的呢？ 实际上正是因为runqueue是per-cpu的，所以每个cpu上的min_vruntime是不一样的，举个例子，假设CPU0和CPU1，CPU0的min_vruntime是10，而CPU1的min_vruntime是100，当任务迁移和唤醒的时候，假设一个任务创建在CPU0，那他的min_vruntime和vruntime是10，此时被唤醒或迁移到了CPU1上，如果我们此时还是拿vruntime为10去enqueue，那么这对CPU1上runqueue的任务并不公平，因为此时这个任务vruntime最小，它因为被迁移导致优先级最高。
反之，如果CPU1的任务被迁移到CPU0上，那么被迁移的任务因为vruntime偏大的问题导致其优先级过低
所以上述又出现了局部不公平性，而为了解决这种局部不公平性的原则，做法是
本文介绍了cfs的enqueue的流程，可以知道在linux中，任务从创建开始，其是在什么时机进行入队到rb-tree的，大家可以清晰的了解到调度器入队的过程，从而理解调度器本身的运作机制。