在<调度(4)-CFS调度器和权重>介绍了CFS的核心点之一,weight.通过配置weight的数组,可以粗略的等比计算nice,而vruntime的实际步长就是通过weight来计算的.

同样的,在<调度(3)-调度器的设计>我们提到,cfs有大量的启发式计算,同样的,对于weight,为了维护cfs的公平性问题,会在enqueue/dequeue的时候,重新计算权重,也就是reweight,今天来简单了解一下cfs的reweight

# reweight的作用
reweight的作用是让sched_entity能根据本地负载动态调整权重，避免某个CPU过载而其他CPU空闲时出现不公平,其关键在于任务的enqueue和dequeue,如下
enqueue流程
```
enqueue_task_fair
  update_cfs_group
    calc_group_shares
    reweight_entity
```
dequeue流程
```
dequeue_task_fair
  update_cfs_group
    calc_group_shares
    reweight_entity
```
可以看到,这里的核心函数函数reweight_entity
# reweight_entity
```
static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                            unsigned long weight)
{
        if (se->on_rq) {
                /* commit outstanding execution time */
                if (cfs_rq->curr == se)
                        update_curr(cfs_rq);
                update_load_sub(&cfs_rq->load, se->load.weight);
        }
        dequeue_load_avg(cfs_rq, se);

        update_load_set(&se->load, weight);

#ifdef CONFIG_SMP
        do {
                u32 divider = get_pelt_divider(&se->avg);

                se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
        } while (0);
#endif

        enqueue_load_avg(cfs_rq, se);
        if (se->on_rq)
                update_load_add(&cfs_rq->load, se->load.weight);

}
```
简单分析一下其内容
* if (cfs_rq->curr == se) update_curr(cfs_rq); 如果就是当前se,则更新vruntime一次
* update_load_sub : 减去当前任务在cfs上的load
* dequeue_load_avg : 将当前se的load从cfs的load_avg中移除
* update_load_set: 设置新权重
* se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);: 用新的权重通过PELT重新计算负载
* enqueue_load_avg : 计算好了load_avg,入队
* update_load_add: 将其新的权重值加到当前总负载

# reweight_task
除了enqueue和dequeue,其他所有场景设置权重可以通过对外api,reweight_task完成,reweight_task是 reweight_entity 的封装,如下
```
void reweight_task(struct task_struct *p, const struct load_weight *lw)
{
        struct sched_entity *se = &p->se;
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        struct load_weight *load = &se->load;

        reweight_entity(cfs_rq, se, lw->weight);
        load->inv_weight = lw->inv_weight;
}
```
其流程如下
```
sched_fork # fork时 
set_user_nice # set nice时
__setscheduler_params # posix api时 
  set_load_weight
    scale_load
    reweight_task
```
# calc_group_shares
我们留意到update_cfs_group会调用calc_group_shares,它的作用是真正的计算权重的地方,值得注意的是,这里权重在计算的时候叫做shares,其代码如下
```
/*
 * All this does is approximate the hierarchical proportion which includes that
 * global sum we all love to hate.
 *
 * That is, the weight of a group entity, is the proportional share of the
 * group weight based on the group runqueue weights. That is:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (1)
 *                       \Sum grq->load.weight
 *
 * Now, because computing that sum is prohibitively expensive to compute (been
 * there, done that) we approximate it with this average stuff. The average
 * moves slower and therefore the approximation is cheaper and more stable.
 *
 * So instead of the above, we substitute:
 *
 *   grq->load.weight -> grq->avg.load_avg                         (2)
 *
 * which yields the following:
 *
 *                     tg->weight * grq->avg.load_avg
 *   ge->load.weight = ------------------------------              (3)
 *                             tg->load_avg
 *
 * Where: tg->load_avg ~= \Sum grq->avg.load_avg
 *
 * That is shares_avg, and it is right (given the approximation (2)).
 *
 * The problem with it is that because the average is slow -- it was designed
 * to be exactly that of course -- this leads to transients in boundary
 * conditions. In specific, the case where the group was idle and we start the
 * one task. It takes time for our CPU's grq->avg.load_avg to build up,
 * yielding bad latency etc..
 *
 * Now, in that special case (1) reduces to:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = ----------------------------- = tg->weight   (4)
 *                         grp->load.weight
 *
 * That is, the sum collapses because all other CPUs are idle; the UP scenario.
 *
 * So what we do is modify our approximation (3) to approach (4) in the (near)
 * UP case, like:
 *
 *   ge->load.weight =
 *
 *              tg->weight * grq->load.weight
 *     ---------------------------------------------------         (5)
 *     tg->load_avg - grq->avg.load_avg + grq->load.weight
 *
 * But because grq->load.weight can drop to 0, resulting in a divide by zero,
 * we need to use grq->avg.load_avg as its lower bound, which then gives:
 *
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (6)
 *                             tg_load_avg'
 *
 * Where:
 *
 *   tg_load_avg' = tg->load_avg - grq->avg.load_avg +
 *                  max(grq->load.weight, grq->avg.load_avg)
 *
 * And that is shares_weight and is icky. In the (near) UP case it approaches
 * (4) while in the normal case it approaches (3). It consistently
 * overestimates the ge->load.weight and therefore:
 *
 *   \Sum ge->load.weight >= tg->weight
 *
 * hence icky!
 */
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 = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

        tg_weight = atomic_long_read(&tg->load_avg);

        /* Ensure tg_weight >= load */
        tg_weight -= cfs_rq->tg_load_avg_contrib;
        tg_weight += load;

        shares = (tg_shares * load);
        if (tg_weight)
                shares /= tg_weight;

        /*
         * MIN_SHARES has to be unscaled here to support per-CPU partitioning
         * of a group with small tg->shares value. It is a floor value which is
         * assigned as a minimum load.weight to the sched_entity representing
         * the group on a CPU.
         *
         * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
         * on an 8-core system with 8 tasks each runnable on one CPU shares has
         * to be 15*1024*1/8=1920 instead of scale_load(MIN_SHARES)=2*1024. In
         * case no task is runnable on a CPU MIN_SHARES=2 should be returned
         * instead of 0.
         */
        return clamp_t(long, shares, MIN_SHARES, tg_shares);
}
```
首先,我们知道task_group记录了组的本身权重shares,如下
```
struct task_group {
        unsigned long           shares;
}
```
按组分配的所有任务会按照比例分配这个shares值,举个例子
* 两个CPU,每个CPU有自己的se,分别是se0,se1
* CPU0上有两个任务,权重分别是1024,2048
* CPU1上有一个任务,权重是1024

那么se0上分配的比例是`(1024+2048)/((1024+2048)+1024)`,而se1上分配的比例是`1024/((1024+2048)+1024)`

![image.png](/static/img/75caa880452365c32c932c749d2488e0.image.webp)

对于代码,分析如下
* max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);  取当前瞬时权重和PELT的平均权重的较大的那个
* tg_weight -= cfs_rq->tg_load_avg_contrib; 将当前组的权重减去本CPU之前贡献的旧值
* tg_weight += load; 再加上上述的max值
* shares = (tg_shares * load); 总份额是share值乘以上述的max
* shares /= tg_weight; 然后除以计算后的权重

可以看到,这其实是一个这样的公式
```
load = max(grq->load.weight, grq->avg.load_avg)
tg_weight = tg->load_avg - grq->tg_load_avg_contrib + load;
shares = tg->shares * load / tg_weight 
```
整合一下
```
shares = tg->shares * max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
其实就是注释的最后公式

![image.png](/static/img/19337ad3721770e9550ff030e4ebbc72.image.webp)

## 回顾注释
### Step 1: 理想公式
```
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (1)
 *                       \Sum grq->load.weight
```
首先,我们分配一个实际任务的weight理论上是这个组的shares,也就是tg->shares,但是如果直接设置这个值,那么实际上并不公平.

为了维护公平性原则,我们为一个任务分配的weight应该将shares值按照实际负载来估计,所以理论想法是
```
weight = shares * (当前CPU负载 / 组内所有CPU负载)
```
这相当于维护了任务的局部公平性原则, 也就是按照当前真实负载比例来切分shares,而不是直接用shares
### Step 2: 平均负载替换瞬时负载
```
 *                     tg->weight * grq->avg.load_avg
 *   ge->load.weight = ------------------------------              (3)
 *                             tg->load_avg
```
但是计算组内所有的CPU负载的代价比较高,我们需要一定的启发式计算,方法是将PELT计算的平均负载来替代CPU负载,也就是如下
```
grq->load.weight -> grq->avg.load_avg
```
这样就不需要反复计算组内任务的CPU负载,而是直接从PELT中取平均负载,那么对于当前CPU的平均负载为grq->avg.load_avg,而组内所有CPU的平均负载是tg->load_avg

那么这次等效替换的计算公式变更为
```
weight = shares * (当前CPU平均负载 / 组内所有CPU平均负载)
```
这样近似计算在负载比较平稳的时候效果很好，且计算成本很低。
### Step 3: 取平均负载和瞬时负载最大值
```
 *              tg->weight * grq->load.weight
 *     ---------------------------------------------------         (5)
 *     tg->load_avg - grq->avg.load_avg + grq->load.weight
```
我们看看这个将瞬时负载到平均负载的等效计算带来的负面效果:假设当前CPU下比较空闲的时候,一个新的任务诞生,那么平均负载会变化的很慢,所以Step 2的公式近似为
```
weight = shares * (当前CPU平均负载(趋于0) / 组内所有CPU平均负载(较大值))
```
那么此时这个新的任务分到的weight远比预设的shares值小. 这是问题1

再假设另一种情况,当前CPU有负载,其他任务全部空闲,那么Step 2的公式近似为
```
weight = shares * (当前CPU平均负载(较大值) / 组内所有CPU平均负载(趋于0))
```
这种情况下,任务分到的weight又因为组内所有CPU平均负载趋于0,导致远远大于shares.这是问题2

为了解决上面问题,需要为公式计算一次当前CPU上的瞬时负载,然后拿这个瞬时负载和当前CPU的平均负载取较大值,也就是`max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);`我们把这个值记作当前CPU的负载:`cfs_rq->load.weight = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg)`

我们拿cfs_rq->load.weight作为分子,而总负载拿所有CPU平均负载减去当前CPU的平均负载,再加上cfs_rq->load.weight,此时公式为
```
weight = shares * ((当前CPU平均负载和瞬时负载的最大值) / (组内所有CPU平均负载 - 当前CPU平均负载 + 当前CPU瞬时负载))
```
到这里,计算一个任务的reweight的公式完成了.
# 总结
本文介绍了reweight的作用,其也是cfs为了维护局部公平性的一种手段,当任务入队出队以及其他场景中,都需要重新计算权重,而权重的公式是将预设的shares值,按照理论想法根据负载比例分配.

最后计算方式实际上是按照平均负载的方式计算,我们回顾此公式
```
shares = tg->shares * max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
这里稍微留意一下这个比例
```
max(grq->load.weight, grq->avg.load_avg) / (tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg))
```
因为一个瞬态负载的值往往大于平均值,也就意味着这个比值是大于1的,也就是如下
```
shares = tg->shares * (>1)
```
也就是
```
shares > tg->shares
```
也就是一个任务reweight的时候,往往比预设的组的shares更大,在<调度(4)-CFS调度器和权重>的计算公式`vruntime += delta * nice0 / weight`,weight越大则vruntime变化越小,那么长期来看任务的reweight,它其实获得的时间片反而越多,但其响应越快

也就是说,虽然reweight为了局部的公平性设计了这个公式,但实际上仔细分析此公式也是存在不公平的,一个任务不断的reweight,那么其weight越大,weight越大,那么它的vruntime变化越小,vruntime预估变化小,那么其任务获得的时间片越多,也就导致了任务被偏心的分配了更多的时间来运行,加强了其响应能力,但是局部的不公平还是存在的.

举个生活的例子,生日了分蛋糕,作为家长,最初的愿望是想平分蛋糕,但是有些小孩是饿哭来要蛋糕的,有些小孩是后面才来要蛋糕的,此时分配的蛋糕默认给饿哭的孩子多分了一点,为了不让饿哭的小孩吃了还饿,主观性的多分了一点蛋糕,那么实际上对其他小孩而言是少了蛋糕, 但是其他小孩并不会因为少一点蛋糕而饿哭,虽然这种微小局部的不公平仍然存在,但是我们没必要追求这个颗粒度上的完全公平了.


因为"满足爱哭小孩有糖吃"定理更重要


调度(10)-CFS调度reweight

上文介绍了cfs的enqueue操作,那对应的,就需要dequeue,dequeue就是在rb-tree中删除一个任务
# schedule dequeue
以schedule为例,其流程为
```
schedule
  _schedule
    pick_next_task
      pick_next_task_fair
        set_next_entity
          __dequeue_entity
            rb_erase_cached
```
我们可以看到dequeue的核心函数是`__dequeue_entity`, 根据上述流程可以知道,当任务被选中执行的时候,会选中rb-tree最小的任务后,主动调用`__dequeue_entity`来pop queue
# other dequeue
其他非标准场景例如
* blocking,sleep
* migration
* exit
* hotplug
* resched
* reweight
* cgroups change

这些场景上单独封装了和enqueue_task成对的函数,如下
```
static inline void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
	if (!(flags & DEQUEUE_NOCLOCK))
		update_rq_clock(rq);

	if (!(flags & DEQUEUE_SAVE)) {
		sched_info_dequeued(rq, p);
		psi_dequeue(p, flags & DEQUEUE_SLEEP);
	}

	uclamp_rq_dec(rq, p);
	p->sched_class->dequeue_task(rq, p, flags);
}
```
同样的也有成对的deactivative_task
```
void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
	enqueue_task(rq, p, flags);

	p->on_rq = TASK_ON_RQ_QUEUED;
}

void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
{
	p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;

	dequeue_task(rq, p, flags);
}
```
值得注意的是,deactivate_task和dequeue_task有一些额外的flag判断,简单解析一下
1. p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;

说明这次deactivate_task大概率是因为睡眠或者迁移导致的dequeue,分别为sleep和migration设置了on_rq标志位

2. DEQUEUE_NOCLOCK

如果设计到睡眠,迁移,那么入队出队需要更新时间,但是如果是直接schedule,那么这个会默认带上,也就意味着没必要重复的更新时间

3. DEQUEUE_SAVE

它和ENQUEUE_RESTORE成对,通过记录enqueue和dequeue的sched_info,然后在dequeue的时候故意不去将sched_info dequeue,这样可以在例如负载均衡的场景上获取sched_info信息统计负载,当然也可以调试.sched_info会更新enqueue和dequeue的时间戳

总结dequeue的大概流程为
```
deactivate_task
  dequeue_task
    dequeue_task_fair
      dequeue_entity 
        __dequeue_entity
          rb_erase_cached
```

值得注意的是,我们在enqueue提到了为了维护公平性需要单独加上当前cpu的min_vruntime,那对应的就要在dequeue上单独减去当前cpu的min_vruntime,这个代码就藏在dequeue_entity中
```
	if (!(flags & DEQUEUE_SLEEP))
		se->vruntime -= cfs_rq->min_vruntime;
```
注意的是,如果不是SLEEP,那假设是MIDRATION,那是通过 update_curr() ->  update_min_vruntime() 更新的,所以这里就不需要再多减一次了.

# 总结
与enqueue成对的,本文介绍了cfs的dequeue,简单理解就是cfs的dequeue就是在rb-tree上删掉成员,所以有两个路径
* 路径1: pick_next_task上,直接删掉节点就行
* 路径2: 其他场景,调用成对的api,dequeue_task,它会更新和维护好vruntime,以及调度时钟信息














调度(9)-CFS调度任务出队

上文介绍了cfs的几个特征点权重/vruntime/调度周期，以及说明了cfs调度的数据结构，这些信息可以宏观上看到调度器的实现方式，本文再基于调度的一个通用概念enqueue进行介绍。

什么是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实现》
# 任务唤醒enqueue
上面已经把基本流程过了，任务唤醒场景的代码调用链为
```
try_to_wake_up
  ttwu_queue
    ttwu_do_activate
      activate_task
```
# 任务迁移enqueue
```
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上的值并不一样，所以它有两个作用
* 为新创建的进程提供最小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偏大的问题导致其优先级过低

所以上述又出现了局部不公平性，而为了解决这种局部不公平性的原则，做法是
* 当dequeue/migration 出队时减去源 min_vruntime，在 enqueue 时加上目标 min_vruntime，从而防止迁移或唤醒的任务因为不同 CPU 时间推进速度不同而获得不公平的调度优势。也就是跨CPU的公平性维护

# 总结
本文介绍了cfs的enqueue的流程，可以知道在linux中，任务从创建开始，其是在什么时机进行入队到rb-tree的，大家可以清晰的了解到调度器入队的过程，从而理解调度器本身的运作机制。











调度(8)-CFS调度任务入队

上文聊到了CFS的一个特性，调度周期，本文梳理一下cfs调度器的基本数据结构
# task_struct
在linux系统中，所有的任务都是一个task_struct，所以我们从这里作为起点
```
struct task_struct {
        volatile long                   state;  # 状态
        int                             on_cpu;  # 是否当前CPU 
        unsigned int                    cpu;  # CPU ID
        int                             on_rq;  # 是否在rq
        int                             prio;  # 优先级
        int                             static_prio;  # nice 优先级
        int                             normal_prio;  # 正常优先级
        unsigned int                    rt_priority;  # 实时优先级
        const struct sched_class        *sched_class;  # 调度类
        struct sched_entity             se;  # 调度实体
        struct sched_rt_entity          rt;  # rt的调度实体
        struct task_group               *sched_task_group;  # cgroup任务组
        struct sched_dl_entity          dl;  # dl的调度实体
        unsigned int                    policy;  # 策略
        int                             nr_cpus_allowed;  # 最大cpu值
        const cpumask_t                 *cpus_ptr;  # cpu_mask结构体
        cpumask_t                       cpus_mask;  # mask掩码
......
}
```
任务结构体管理调度实体，所以我们查看调度实体se
# sched_entity
```
struct sched_entity {
        /* For load-balancing: */
        struct load_weight              load; # 权重
        struct rb_node                  run_node; # rb-tree
        struct list_head                group_node; # cgroup任务组
        unsigned int                    on_rq; # 是否在rq

        u64                             exec_start; # 执行时间
        u64                             sum_exec_runtime; # 累计时间
        u64                             vruntime; # 运行时间
        u64                             prev_sum_exec_runtime; # 上次累计时间

        u64                             nr_migrations; # 迁移次数

        struct sched_statistics         statistics; # 统计信息

        int                             depth; # 深度，cgroup使用
        struct sched_entity             *parent; # 父节点，cgroup使用
        /* rq on which this entity is (to be) queued: */
        struct cfs_rq                   *cfs_rq; # cfs rq
        /* rq "owned" by this entity/group: */
        struct cfs_rq                   *my_q; # cgroup下的cfs rq
        /* cached value of my_q->h_nr_running */ 
        unsigned long                   runnable_weight; # h_nr_running 

        struct sched_avg                avg; # 负载均衡
};
```
调度实体管理运行队列，所以接下来看cfs_rq
# cfs rq
```
struct cfs_rq {
        struct load_weight      load; # 权重
        unsigned int            nr_running; # 调度实体数量

        u64                     exec_clock; # 累计时钟
        u64                     min_vruntime; # 最小运行时间

        struct rb_root_cached   tasks_timeline; # rb-tree 根

        /*
         * 'curr' points to currently running entity on this cfs_rq.
         * It is set to NULL otherwise (i.e when none are currently running).
         */
        struct sched_entity     *curr; # 当前se指针
        struct sched_entity     *next; # 下个se指针
        struct sched_entity     *last; # 上个se指针
        struct sched_entity     *skip; # 需要跳过的se指针
......
}
```
runqueue管理的是rb-tree，所以接下来看rb-tree结构 tasks_timeline
# tasks_timeline
```
struct rb_root_cached {
        struct rb_root rb_root; # rb-tree 根
        struct rb_node *rb_leftmost; # rb-tree 最左节点
};
```
到这里，cfs的基本结构大致为`task_struct->sched_entity->runqueue->rb-tree`   
但是还有一个不应该忽视的，就是cgroup下的组调度
# task_group
```
struct task_group {
        struct cgroup_subsys_state css; # cgourp状态

#ifdef CONFIG_FAIR_GROUP_SCHED
        /* schedulable entities of this group on each CPU */
        struct sched_entity     **se; # 调度实体
        /* runqueue "owned" by this group on each CPU */
        struct cfs_rq           **cfs_rq; # runqueue
        unsigned long           shares; # cgoup 份额
#ifdef CONFIG_RT_GROUP_SCHED
        struct sched_rt_entity  **rt_se; # rt的调度实体
        struct rt_rq            **rt_rq; # rt的runqueue

        struct rt_bandwidth     rt_bandwidth; # rt带宽控制
        struct cfs_bandwidth    cfs_bandwidth; # cfs带宽控制
#endif
......
}
```
task_group 中有两个重要的成员：其一是sched_entity 指针的数组，将其插入到其父 cfs_rq 的红黑树中，实现组级公平竞争，另一个则是 cfs_rq，用于管理该组内任务的调度队列。我们可以看到重点在task_group的分组行为。   

默认情况下，可以按照上面描述的流程管理`task_struct->sched_entity->runqueue->rb-tree`，但实际上，可以通过cgroup分组，那么其流程管理为`task_struct->task_group->sched_entity->runqueue->rb-tree`    
通过添加这么一个组的概念，借助my_q就可以使得cpu上的任务可以按组来管理了。

# 总结
本文将调度大的框架上的基本数据结构的交互进行了一个说明，可能很轻松的了解到调度在数据结构上是如何实现or流转的，同样的，我也整理了图示，如下

![image.png](/static/img/80281b3f5e19cf6539a6a12cb39ff81a.image.webp)

可以看到，所谓调度，就是从task_struct中，找到group/task内的se，通过se下的runqueue找到rb-tree，然后通过rb-tree进行任务管理，简单明了。

更详细一点的图片如下，摘自网络，意思一致

![image.png](/static/img/9f620d420a11c6d0d48f002dc1dc0991.image.webp)


# 参考
> https://blogs.oracle.com/linux/cfs-group-scheduling



调度(7)-CFS基本数据结构

CFS为了局部的公平性， 引入了一个概念叫做调度周期，什么是调度周期，就是每个进程在一个周期内至少运行一次。本文说明一下CFS的调度周期

# 调度周期的实现
调度周期是为了保证CFS调度器上的进程在一个周期内至少运行一次，那么怎么保证的呢？我们跟踪一下代码
```
        if (td->mode == TICKDEV_MODE_PERIODIC)
                tick_setup_periodic(newdev, 0);
```
这里调度周期来自timer的periodic模式
```
tick_setup_periodic
  tick_set_periodic_handler
    dev->event_handler = tick_handle_periodic
```
这里tick_handle_periodic的流程
```
tick_handle_periodic
  tick_periodic
    update_process_times
      scheduler_tick
        curr->sched_class->task_tick(rq, curr, 0);
          task_tick_fair
            entity_tick
              check_preempt_tick
                sched_slice
                  __sched_period
```
这里`__sched_period`是最终的实现，其返回了调度周期，实现如下
```
/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
        if (unlikely(nr_running > sched_nr_latency))
                return nr_running * sysctl_sched_min_granularity;
        else
                return sysctl_sched_latency;
}
```
我们查看这三个值
* sched_nr_latency
* sysctl_sched_latency
* sysctl_sched_min_granularity


```
static unsigned int sched_nr_latency = 8;
unsigned int sysctl_sched_latency                       = 6000000ULL;
unsigned int sysctl_sched_min_granularity                       = 750000ULL;
```
这代表什么意思呢？
1. 核心上的任务临界值是8（经验值）
2. 少于等于8个任务的时候按照6ms周期
3. 大于8个任务的时候按照0.75ms * 任务数量作为周期

值得注意的是，这个计算公式是纯经验值，任何人都可以手动sysctl修改看看效果。

# 怎么保证周期性
上面知道了调度周期的计算方式，实际上就是在进行抢占来实现的，简单来说就是通过update_curr计算好vruntime，然后用 check_preempt_tick 判断是否超周期了，如果超周期了，那么就实施抢占。我们看看check_preempt_tick的策略
```
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
        unsigned long ideal_runtime, delta_exec;
        struct sched_entity *se;
        s64 delta;
        bool skip_preempt = false;

        ideal_runtime = sched_slice(cfs_rq, curr);
        delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
        trace_android_rvh_check_preempt_tick(current, &ideal_runtime, &skip_preempt,
                        delta_exec, cfs_rq, curr, sysctl_sched_min_granularity);
        if (skip_preempt)
                return;
        if (delta_exec > ideal_runtime) {
                resched_curr(rq_of(cfs_rq));
                /*
                 * The current task ran long enough, ensure it doesn't get
                 * re-elected due to buddy favours.
                 */
                clear_buddies(cfs_rq, curr);
                return;
        }

        /*
         * Ensure that a task that missed wakeup preemption by a
         * narrow margin doesn't have to wait for a full slice.
         * This also mitigates buddy induced latencies under load.
         */
        if (delta_exec < sysctl_sched_min_granularity)
                return;

        se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;

        if (delta < 0)
                return;

        if (delta > ideal_runtime)
                resched_curr(rq_of(cfs_rq));
}
```
首先我们知道resched_curr就是抢占操作，那么代码有两个点是运行抢占的，如下
## 抢占点1
```
 if (delta_exec > ideal_runtime)
```
如果任务跑的时机大于理想认为的周期时间了，那么抢占
## 抢占点2
```
if (delta > ideal_runtime)
```
这段逻辑需要结合一下上下文代码，如下
```
 se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;
```
因为cfs是利用rb-tree构建，rb-tree可以查看我之前的文章。所以这里se就是最小vruntime的调度实体。   
那么delta就是当前时间减去最应该被调度的任务,如果大于周期，那么强行抢占。

可以看到，抢占点2其实就是一段客制化代码，其用于避免cfs的starvation问题（饿死问题）
## 注意点1
除了两个抢占点，check_preempt_tick还有一个特殊return，那就是
```
if (delta_exec < sysctl_sched_min_granularity)
                return;
```
这里意思也很明确，就是当前任务如果运行时间太短，那就不抢占了。这笔内容其实就是缓解调度的高开销。
# 总结
本文详细的介绍了CFS的另一个重要概念就是调度周期，CFS为了维持局部的公平性，专门引入的调度周期，这样使得任务不会被饿死。而实现所谓的调度周期的办法就是增加抢占点，让满足调度周期的任务强行被抢占了。

