2.6.3.1 组调度 - 数据结构

我们先将任务组的总体数据结构放在一边，再来回顾一下CFS的调度逻辑：调度是每个CPU单独进行的，每个CPU有自己的runqueue, 对CFS而言，所有的调度实体都存放在一个cfsrq中，当调度发生时，调度器从该cfsrq中选择vruntime最小的调度实体对应的任务来执行。

如果调度器选择到的调度实体表示一个任务组的话，该怎么办呢？那么调度器需要从该任务组中继续选择vruntime最小的任务来执行。

这里存在一个问题：在多核系统上，一个任务组的所有任务可以分布在多个CPU上，如下图所示：

该图只是一个示意图，用来帮助我们理解调度组的概念，请不要将图中结构与任何内核的数据结构做直接的对应。

红色的5个任务隶属于同一个调度组，其中 SE_G0, SE_G1, SE_G2 这个 sub-group 被分配到了 CPU0 上，而 SE_G3, SE_G4 这个 sub-group 被分配到了 CPU1 上，SER0 与 SE_R1 分别是用来管理两边 sub-group 的根节点，也就是说当CPU0发生调度并选择到 SE_R0 时，会发现它其实代表一个任务组，此时需要进一步从该调度组中挑出最合适的任务来执行，这里应该从 SE_G0, SE_G1, SE_G2 中再选一个出来。

这里有两个问题：

1. 如何区分一个 se 是任务还是任务组

2. 如何管理在同一个CPU上并隶属于同一个任务组的多个任务

要回答这些问题，我们又需要回到数据结构 sched_entity 中来。在讨论调度实体时我们提到， sched_entity 存在的原因就是设计者需要一个既可以表示单个任务、又可以封装一个任务组的数据结构。现在我们来看一下该结构体的完整定义：

/* file: include/linux/sched.h */
struct sched_entity {
/* For load-balancing: */
/* 权重，权重由进程的 nice 值进行计算 */
struct load_weight load;
/* 红黑树节点 */
struct rb_node run_node;
struct list_head group_node;
/* 是否在 runqueue 上，1 则表示在 rq 中 */
unsigned int on_rq;

/* 记录该进程在 CPU 上开始执行的时间 */
u64 exec_start;
/* 记录总运行时间 */
u64 sum_exec_runtime;
/* 该进程的虚拟运行时间，该值是红黑树中的key, CFS 依据该值来保证公平调度 */
u64 vruntime;
/* 截止该调度周期开始时，进程的总运行时间，在check_preempt_tick中会使用到 */
u64 prev_sum_exec_runtime;

/* scheduler 做负载均衡时，对该进程的迁移次数 */
u64 nr_migrations;

/* 统计数据 */
struct sched_statistics statistics;

#ifdef CONFIG_FAIR_GROUP_SCHED
int depth;
/* parent 如果非空的话，那么一定指向一个代表 task_group 的 sched_entity, 即
* my_q 非空 */
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
/* 用来判断该 se 是否是一个 task, 如果 my_q 为null, 则是task, 否则则表示是一个
* task_group 参考宏 entity_is_task  */
struct cfs_rq *my_q;
/* cached value of my_q->h_nr_running */
unsigned long runnable_weight;
#endif

#ifdef CONFIG_SMP
/*
* Per entity load average tracking.
*
* Put into separate cache line so it does not
* collide with read-mostly values above.
*/
struct sched_avg avg;
#endif
};

预编译指令 #ifdef CONFIG_FAIR_GROUP_SCHED 中间的几个字段都是用来封装任务组的。判断一个 se 是否是任务组的字段是 my_q: 如果该字段为 NULL, 则表示一个任务，否则就是一个任务组。而 my_q 是我们熟悉的结构体 cfs_rq, 也就是说同一个CPU上并且隶属于同一个组的任务又通过另一个cfsrq组织了起来，放在另一棵红黑树中。与之前讲解过的结构全部结合起来，单个CPU 的运行队列结构如下：

弄清楚了单个CPU上的结构之后，我们接下来看一下任务组的总体结构。系统专门定义了一个结构体来封装任务组的信息：

/* file: kernel/sched/sched.h */
struct task_group {
/* 以下字段的初始化在函数alloc_fair_sched_group()中，位于文件fair.c。在cgroup
* 初始化时调用 */
#ifdef CONFIG_FAIR_GROUP_SCHED
/* schedulable entities of this group on each CPU */
/* se[i] 表示该 task_group 中在第 i 个 CPU 上的 sched_entity, 该 se
* 代表的是一个任务组，即 sched_entity->my_q 指向该结构体的 cfs_rq[cpu] */
struct sched_entity **se;
/* cfs_rq[i] 表示该 task_group 中在第 i 个 CPU 上的 cfs_rq. 在函数
* alloc_fair_sched_group 中初始化 */
struct cfs_rq **cfs_rq;
/* 该 task_group 的 cpu.shares, 表示该 task_group 的权重 */
unsigned long shares;
#endif

struct rcu_head rcu;
struct list_head list;

struct task_group *parent;
struct list_head siblings;
struct list_head children;

struct cfs_bandwidth cfs_bandwidth;
};

这里我们暂时只关心两个字段：

• struct sched_entity **se

• struct cfs_rq **cfs_rq

通过前文我们知道，系统将一个任务组分布到各个CPU上时，同一个CPU上所分配到的所有任务会形成一个子组（sub-group）并通过一个cfsrq来管理；而CPU本身的cfsrq中会有一个代表任务组 se 指向该子组； task_group 的这两个字段分别用来保存这两方面的内容：se[i]用来保存CPU[i]队列上代表任务组的se，而cfsrq[i]用来保存CPU[i]所分配到的任务子组，其中 i 表示CPU的索引下标。总体结构的示意图如下：

除了 sched_entity 与 task_group 之外，cfs_rq与 rq 中也有与组调度相关的字段，由于并不影响我们从总体上理解任务组的结构，因此在这里不再细究。