CFS（五）组调度-526互联

前言

以进程为CPU资源的分配单位在某些场景下是有缺陷的，比如容器场景需要支持按照组做资源的分配，然后组内再按照进程做细化的资源分配。组调度技术是cgroup实现的一个重要组成部分。

CFS组调度需要开启CONFIG_CGROUP_SCHED和CONFIG_FAIR_GROUP_SCHED选项。

组调度相关数据结构的组织

相比于不支持组调度的CFS主要有两点改变，一个是调度实体对应的可能不是一个task，有可能是一组task，并且这组task的管理也是使用的cfs_rq，形成一种嵌套的树状结构，这种表示一组任务的调度实体可以被称作group-se，group-se的my_q指针指向一个cfs_rq。第二点是，组调度管理的多个se可能会分布在多个cpu上，因此不同核上的se需要在每个cpu上有独立的管理，除此之外不同核上的se归根结底还是属于一个任务组需要有一个数据结构task_group归纳所有核上的数据，通过task_group可以找到每个核上的group-se与其挂载的cfs_rq。

task_group

task_group表示一个任务组，其中se和cfs_rq是per-cpu的数组。

per-cpu-cfs_rq用于管理任务组中分布在不同cpu上的调度实体。
per-cpu-se是group-se，每个核上的se[cpu]->my_q指向cfs_rq[cpu]。任务组在每一个cpu上的都有一个group-se。
parent可以找到上层task_group，se[cpu]->cfs_rq（se所处的cfs_rq）指向的就是parent->cfs_rq[cpu]。

/* Task group related information */
struct task_group {
    struct sched_entity	**se;   /* per-cpu的表示任务组调度实体 */
    struct cfs_rq		**cfs_rq;  /* per-cpu的管理每个cpu上调度实体的runq */
    struct task_group	*parent;    /* 上层的task group */
    unsigned long		shares; /* 任务组的份额 */
}

在内核初始化的时候有一个全局的struct task_group命名为root_task_group。这个root_task_group实现了任务组管理的统一，在CFS的视角初始的系统中所有的任务都属于根任务组，需要注意的根任务组具有一些特殊性，其parent = NULL并且se = {NULL, NULL, ...}，根任务组已经没有上层的任务组了，因此不需要se和parent。

cfs_rq

cfs_rq新增了rq指向当前cfs_rq所属的rq以及tg指向所属的task_group。

struct cfs_rq {
    struct rq		*rq;    /* 指向当前cfs_rq 挂载到的rq，用以区分不同cpu */
    struct task_group	*tg; /* 指向所属的task_group */
}

sched_entity

group-se需要下面会挂载一个cfs_rq，因此为了支持组调度sched_entity新增了一些变量。

depth表示层级，root_task_group的cfs_rq管理的se的depth都是0，对于其他调度实体se->depth = parent->depth + 1。
parent指向任务组在上层cfs_rq中的group-se。root_task_group中的se其parent为NULL。
cfs_rq指向管理当前se的cfs_rq
my_q可以用以区分task-se和group-se。group-se的my_q指向管理的cfs_rq。task-se的my_q为NULL。

struct sched_entity {
#ifdef CONFIG_FAIR_GROUP_SCHED
    int				depth;      /* 调度实体所处组的深度 */
    struct sched_entity		*parent;    /* 所属任务组在上一层中的调度实体 */
    struct cfs_rq			*cfs_rq;    /* 调度实体所在的任务组runq */
    struct cfs_rq			*my_q;      /* 如果是一个group-se my_q指向管理的任务组runq*/
#endif
}

一些数据结构间关系的例子

上述的内容比较抽象，这里举一个简单的例子辅助理解，假设系统初始化时系统中只有一个root_task_group。系统有两个核，核上的task数量都为3。初始的层级结构如下，系统中只有一个root_task_group，两个cfs_rq，这与不支持组调度的场景是一致的。

graph TB root_task_group(root_task_group) subgraph cfs_rq_0 rb0("tasks_timeline") end subgraph cfs_rq_1 rb1("tasks_timeline") end subgraph "cpu0 cfs_rq" t-0-0((se)) t-0-1((se)) t-0-2((se)) t-0-0 --> t-0-1 t-0-0 --> t-0-2 end subgraph "cpu1 cfs_rq" t-1-0((se)) t-1-1((se)) t-1-2((se)) t-1-0 --> t-1-1 t-1-0 --> t-1-2 end root_task_group-.->|"cfs_rq[0]"|cfs_rq_0 root_task_group-.->|"cfs_rq[1]"|cfs_rq_1 rb0-.->|rb_root|t-0-0 rb1-.->|rb_root|t-1-0

系统根任务组

此时se的状态如下。

struct task_group root_task_group {
    .parent = NULL;
    .cfs_rq = {&cfs_rq_0, &cfs_rq_1};
    .se = {NULL, NULL};
}
/* cpu0上的cfs_rq */
struct cfs_rq cfs_rq_0 {
    .nr_running = 3;
    .h_nr_running = 3;
    .tg = &root_task_group;
}
/* cpu0上的某个调度实体 */
struct sched_entity se {
    .depth = 0;
    .parent = NULL;
    .cfs_rq = &cpu0_cfs_rq;
    .my_q = NULL;
}

假设此时新建一个任务组，该任务组包含10个任务，每个cpu上分别有5个任务。需要新创建的数据结构包括两个group-se放入根任务组的cfs_rq中、两个cfs_rq分别挂到group-se下面，以及一个 struct task_group挂在root_task_group下面，需要创建的10个task-se此处先忽略。这些新建数据结构间的连接方式如下图所示。

新建task_group状态

由于结构基本对称就以cpu0的为例，此时相关数据结构的信息如下：

new_task_group能找到新建的cfs_rq以及两个group-se。parent指向root_task_group.
group_cfs_rq_0的tg指向new_task_group，nr_running和h_nr_running都是5。
group-se0要位于根任务组因此depth为0，parent为NULL。cfs_rq指针指向根任务组的cfs_rq_0。my_q指向新建的group_cfs_rq_0。
se位于group_cfs_rq_0的rb-tree中，parent指向group-se0，depth为parent->depth加1。cfs_rq指向新建的group_cfs_rq_0。因为是task-se，所以my_q为NULL.

/* 新建的任务组 */
struct task_group new_task_group {
    .cfs_rq[2] = {&group_cfs_rq_0, group_cfs_rq_1};
    .se[2] = {&group-se0, &group-se1};
    .parent = &root_task_group;
}
/* cpu0上新建的cfs_rq */
struct cfs_rq group_cfs_rq_0 {
    .nr_running = 5;
    .h_nr_running = 5;
    .tg = &new_task_group;
}
/* 位于根任务组 cpu0的cfs_rq中的group-se */
struct sched_entity group-se0 {
    .parent = NULL;
    .depth = 0;
    .cfs_rq = &cfs_rq_0;
    .my_q = &group_cfs_rq_0;
}
/* 新任务组在cpu0上的某个调度实体 */
struct sched_entity se {
    .parent = &group-se0;
    .depth = 1;
    .cfs_rq = &group_cfs_rq_0;
    .my_q = 0;
}

合入只需要将两个group-se分别挂入根任务组的对应的cpu上的cfs_rq并且调整cfs_rq的nr_running和h_nr_running，让new_task_group的parent指针指向root_task_group就可以了。

NOTE：nr_running表示本cfs_rq中的调度实体数量，h_nr_running表示本层级及以下的所有cfs_rq的调度实体数量总数。新建后的根任务组的cfs_rq的nr_running应该为4，h_nr_running应该为9。

组调度的时间分配

回想一下不支持组调度的场景，一个se在调度周期内分配的时间总量为其权重占cfs_rq的比例。而组调度实现了一种树状的嵌套结构，每一个任务组能够得到的总时间需要看其group-se在上层队列中的权重占比，确认了分配时间总量后，再进一步将时间分配到任务组内的调度实体上，这个过程会持续到本组内全部都是task-se为止。比如在根任务组有两个se，权重值为1:2，分别占有占有33.3%和66.6%的cpu时间，第一个se是group-se，其my_q指向的cfs_rq又包含两个se权重值相同，则每个se能够得到16.6%的时间。

计算某个se的在调度周期内应得的时间片的函数为sched_slice，逻辑是上面的这个逻辑，但是实现上sched_slice是自低向上计算的（结果是一致），计算顺序自左向右为slice * 1/2 * 1/3。

#define for_each_sched_entity(se) \
        for (; se; se = se->parent)
        
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load;

        slice = __calc_delta(slice, se->load.weight, load);
    }
    return slice;
}

组调度的任务选择

组调度在选择任务时自顶向下搜索vruntime最小的se，如果在某一层找到的vruntime最小的se是group-se则继续寻找，直到遇到一个se的my_q为NULL时停止，即遇到一个task-se。

NOTE：group_cfs_rq返回se->my_q

static 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;
    struct sched_entity *se;
    struct task_struct *p;
    put_prev_task(rq, prev);

    do {
        /* 获取cfs_rq中vruntime最小的se */
        se = pick_next_entity(cfs_rq, NULL);
        set_next_entity(cfs_rq, se);
        /* 获取se的my_q */
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);
}

组调度的权重

我们知道权重会影响cpu的时间分配比例，但是一个任务组的多个任务会分多个cpu上去执行，每个cpu上的group_cfs_rq管理的任务数量和任务权重是不一样的，因此任务组的权重应该按照比例分配到每个cpu的group-se上这样才是合理的，因此group-se.load.weight = tg->shares * ratio得来，总量由tg->shares决定，分配比例ratio由每个group-se下面的se的权重之和的分布。

但是上述是理论上的计算方法，实际上的由于计算tg->load.weight需要对cfs_rq->load.weight的权重求和，需要访问多个核上的数据会产生锁竞争，因此并没有使用load.weight的占比求ratio，load.weight的替代品是load_avg，因此load_avg更新时就需要对应的更新group-se的权重，具体的更新点会发生在四处位置：

entity_tick时钟tick
enqueue_entity任务组加入新任务
dequeue_entity任务组移除任务
sched_group_set_shares任务组设置可分配的总权重

在这里先不考虑是如何设定任务组的总权重shares的，只关注如何权重shaers是如何分配到每个group-se上的。在每次shares变化或者某个cfs_rq或者se的load_avg变化时调用update_cfs_group更新该cpu上group-se的load.weight，这个过程可能是递归的，因为本层的load_avg改变了会导致上层任务组的总负载也会发生改变，所以需要自底向上每一层都调用update_cfs_group来进行更新。就像这样：

for_each_sched_entity(se) {
    cfs_rq = cfs_rq_of(se);
    update_load_avg(cfs_rq, se, UPDATE_TG);
    update_cfs_group(se);
}

update_load_avg会重新计算load_avg，具体算法我们先不关注，假设load_avg已计算好，在update_cfs_group内会调用calc_group_shares计算group-se应该从task_group的shares中得到多少的权重，具体的份额与其my_q指向的cfs_rq的负载有关。

通过看注释以及一些其他的相关文章，该部分计算公式存在多次迭代，最初想法也是按照cfs_rq->load.weight的比例计算，但是这种方式性能开销比较大所以转而使用load_avg平均负载的比例来替代load.weight权重。load_avg由于变化缓慢这个特点（优点也是缺点），在某些边界条件时表现的就不够好，比如某个核上空闲，但是其他核上有同组的任务在运行，在该核上突然启动一个任务执行时，该核的cfs_rq->load_avg需要一定的时间才能达到正常水平，为了处理这些问题算法做了一些近似调整以满足边界情况最终得到了下述的公式。有兴趣的可以深究一下，我是真的看不太懂，简单理解就是按照权重比例计算的一种更快的近似算法。

                             tg->shares * load
se->load.weight = -------------------------------------------------		  
                  tg->load_avg - cfs_rq->tg_load_avg_contrib + load
                  
load = max(cfs_rq->load.weight, cfs_rq->avg.load_avg)

公式中相关的参数含义如下：

tg->load_avg: 所有核上的总负载
cfs_rq->avg.load_avg: cfs_rq的当前负载
cfs_rq->load.weight: cfs_rq的当前权重（所有se的权重之和）
cfs_rq->tg_load_avg_contrib: cfs_rq已贡献给tg->load_avg的负载，因为cfs_rq->load_avg是波动的，当波动幅度不大时没有必要产生更新操作。只有当cfs_rq->load_avg的波动幅度（不管是上涨还是下跌）达到了cfs_rq->tg_load_avg_contrib的1/64时才会更新tg->load_avg和cfs_rq->tg_load_avg_contrib。

calc_group_shares函数是公式对应的代码实现。

static long calc_group_shares(struct cfs_rq *cfs_rq)
{
    long tg_weight, tg_shares, load, shares;
    struct task_group *tg = cfs_rq->tg;

    tg_shares = READ_ONCE(tg->shares);
    /* load = cfs_rq->load.weight */
    load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

    /* 计算分母 */
    tg_weight = atomic_long_read(&tg->load_avg);
    tg_weight -= cfs_rq->tg_load_avg_contrib;
    tg_weight += load;
    /* 计算分子 */
    shares = (tg_shares * load);
    /* 计算权重 */
    if (tg_weight)
        shares /= tg_weight;

    /* 返回一个值在 MIN_SHARES 和 tg_shares之前，如果超过返回最大值 如果小于最小值 返回最小值*/
    return clamp_t(long, shares, MIN_SHARES, tg_shares);
}

组调度的tick抢占

举例，一些状态描述如下

当前在cpu0上，根任务组有cfs_rq3个se分别是A、B、C，该cfs_rq称作root_cfs_rq.
A是一个group-se，下面的cfs_rq有D、E两个task-se,该cfs_rq称作child_cfs_rq。
child_cfs_rq->curr是D
root_cfs_rq->curr是A

此时发生tick抢占检查，检查会自低向上进行，首先检查child_cfs_rq能否发生抢占D，如果抢占成功则标记TIF_NEED_RESCHED，然后上层依然要检查B（假设B是vruntime最小的）能否抢占A。逐层的检查中只要有一层抢占成功了就需要重新调度。

Note：entity_tick不止做抢占检查，还有一些周期性tick的数据更新，因此即使抢占已经给current标记了TIF_NEED_RESCHED依然需要向上执行。

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;
    /* 逐层向上检查 */
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        /* 检查每一层能否抢占成功 */
        entity_tick(cfs_rq, se, queued);
    }

    if (static_branch_unlikely(&sched_numa_balancing))
        task_tick_numa(rq, curr);
}

总结

组调度的实现的关键在于group-se和task_group，这两个数据结构建立起了层级的可嵌套的调度队列。这种复杂的数据结构也带了一些问题，不管是出队、入队、tick等操作，原本对se的操作都需要转成迭代的操作，因为上层的调度信息（权重、负载、统计信息等）都依赖于底层，会触发连锁的更新。除此之外，组调度的核心在于cpu时间的按组分配，而任务组有在每个cpu上都有一个化身group-se，因此组的权重需要在group-se间分配，因此在本文中介绍了task_group->shares是如何分配到每个核上的group-se上的，分配算法依赖于cfs_rq的负载信息，但是本文没有详细介绍负载是如何更新和统计的，这部分内容与PELT（per-entity load tracking）相关。