# 2.6.3.1 组调度 - 数据结构

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

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

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

![](/files/R2Bw1lOSNGSLarVD8LVn)

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

红色的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 的运行队列结构如下：

![](/files/tWcPSe3dNltZ8qeoOCvg)

弄清楚了单个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的索引下标。总体结构的示意图如下： 

![](/files/FoaSpMkua3vKd7ZxN7n8)

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/cfs-sched/group-data-structure.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.