PELT的全称为: Per-Entity Load Tracking, 根据直面意思,这是基于se的load tracking, PELT能够提供提供当前系统基于per-entity的负载情况. 具体点说就是通过用指数衰减的方式，把历史运行时间转化为当前负载预测，帮助负载均衡、CPU调频和能耗管理。
# 为什么需要 PELT 
在之前的文章<调度(10)-CFS调度reweight>中可以看到,calc_group_shares函数在实际计算的时候引用了PELT的计算值,根据此,我们可以看到如果没有PELT,可能有如下问题
1. **响应延迟**：任务负载突变时，调度器反应迟钝
2. **精度不足**：无法区分短时爆发和持续高负载

主要原因是,如果按照传统计算平均值的方式,那么只能统计过去一段时间的平均值,而PELT能够实时的了解per-entity的负载情况

PELT 于 2013 年在 Linux 3.8 内核中引入，是 Vincent Guittot 等开发者的重要贡献, 彻底改变了 CFS 的负载感知能力。 

# PELT原理
PELT使用以过去的状态统计现在的负载的思路进行设计,它通过wall clock视为1ms(1024份)为单位` 1ms (actually, 1024µs)`在每个1ms的区间内,一个se对系统的新增的负载贡献取决于se_runable在rq上的时间比例,除此之外,之前的entity对系统产生的负载也会通过指数衰减累计下来,用作每次计算负载的参数,以公式的方式记录为如下
```
L_t = l_t + (y*l_{t-1}) + (y^2*l_{t-2}) ... + (y^t*l_0)
```
这里l_x是每个period记录的负载值,L_t是t时刻下计算总负载的值,y是计算的衰减因子,其默认y的固定值为
```
y^32 = 0.5
```
这里计算y是0.9786

此时我们计算L_t-1的公式,如下
```
L_{t-1} = l_{t-1} + (y*l_{t-2}) + (y^2*l_{t-3}) ... + (y^{t-1}*l_0)
```
我们将Lt-1乘y,可以计算为
```
y*L_{t-1} = y*l_{t-1} + (y^2*l_{t-2}) + (y^3*l_{t-3}) ... + (y^{t}*l_0)
```
拿这个公式和最上面L_t计算,可以得到递归公式如下
```
L_t = l_t + y * L{t_1}
```
关于此公式,内核也提供了注释说明,如下
```
/*
 * We can represent the historical contribution to runnable average as the
 * coefficients of a geometric series.  To do this we sub-divide our runnable
 * history into segments of approximately 1ms (1024us); label the segment that
 * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
 *
 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
 *      p0            p1           p2
 *     (now)       (~1ms ago)  (~2ms ago)
 *
 * Let u_i denote the fraction of p_i that the entity was runnable.
 *
 * We then designate the fractions u_i as our co-efficients, yielding the
 * following representation of historical load:
 *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
 *
 * We choose y based on the with of a reasonably scheduling period, fixing:
 *   y^32 = 0.5
 *
 * This means that the contribution to load ~32ms ago (u_32) will be weighted
 * approximately half as much as the contribution to load within the last ms
 * (u_0).
 *
 * When a period "rolls over" and we have new u_0`, multiplying the previous
 * sum again by y is sufficient to update:
 *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
 *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
 */
```
# 数据结构
## sched_avg
```
/*
 * The load/runnable/util_avg accumulates an infinite geometric series
 * (see __update_load_avg_cfs_rq() in kernel/sched/pelt.c).
 *
 * [load_avg definition]
 *
 *   load_avg = runnable% * scale_load_down(load)
 *
 * [runnable_avg definition]
 *
 *   runnable_avg = runnable% * SCHED_CAPACITY_SCALE
 *
 * [util_avg definition]
 *
 *   util_avg = running% * SCHED_CAPACITY_SCALE
 *
 * where runnable% is the time ratio that a sched_entity is runnable and
 * running% the time ratio that a sched_entity is running.
 *
 * For cfs_rq, they are the aggregated values of all runnable and blocked
 * sched_entities.
 *
 * The load/runnable/util_avg doesn't directly factor frequency scaling and CPU
 * capacity scaling. The scaling is done through the rq_clock_pelt that is used
 * for computing those signals (see update_rq_clock_pelt())
 *
 * N.B., the above ratios (runnable% and running%) themselves are in the
 * range of [0, 1]. To do fixed point arithmetics, we therefore scale them
 * to as large a range as necessary. This is for example reflected by
 * util_avg's SCHED_CAPACITY_SCALE.
 *
 * [Overflow issue]
 *
 * The 64-bit load_sum can have 4353082796 (=2^64/47742/88761) entities
 * with the highest load (=88761), always runnable on a single cfs_rq,
 * and should not overflow as the number already hits PID_MAX_LIMIT.
 *
 * For all other cases (including 32-bit kernels), struct load_weight's
 * weight will overflow first before we do, because:
 *
 *    Max(load_avg) <= Max(load.weight)
 *
 * Then it is the load_weight's responsibility to consider overflow
 * issues.
 */
struct sched_avg {
        u64                             last_update_time;
        u64                             load_sum;
        u64                             runnable_sum;
        u32                             util_sum;
        u32                             period_contrib;
        unsigned long                   load_avg;
        unsigned long                   runnable_avg;
        unsigned long                   util_avg;
        struct util_est                 util_est;
} ____cacheline_aligned;
```
这里记录每一个period(1024us)的负载信息,分别信息解释如下
* last_update_time: 上次更新负载统计的时间戳
* load_sum: 负载的累加和（未衰减的原始值）
* runnable_sum: 可运行状态时间的累加和
* util_sum: 实际运行状态时间的累加和
* period_contrib: 当前周期内已贡献的时间比例份额
* load_avg: 平均负载
* runnable_avg: 平均runnable任务比例(1024计算)
* util_avg: 平均利用率
* util_est: 平均利用率的快速预估值

## ___update_load_sum
```
static __always_inline int
___update_load_sum(u64 now, struct sched_avg *sa,
		  unsigned long load, unsigned long runnable, int running)
{
	u64 delta;

	delta = now - sa->last_update_time;
	/*
	 * This should only happen when time goes backwards, which it
	 * unfortunately does during sched clock init when we swap over to TSC.
	 */
	if ((s64)delta < 0) {
		sa->last_update_time = now;
		return 0;
	}

	/*
	 * Use 1024ns as the unit of measurement since it's a reasonable
	 * approximation of 1us and fast to compute.
	 */
	delta >>= 10;
	if (!delta)
		return 0;

	sa->last_update_time += delta << 10;

	/*
	 * running is a subset of runnable (weight) so running can't be set if
	 * runnable is clear. But there are some corner cases where the current
	 * se has been already dequeued but cfs_rq->curr still points to it.
	 * This means that weight will be 0 but not running for a sched_entity
	 * but also for a cfs_rq if the latter becomes idle. As an example,
	 * this happens during idle_balance() which calls
	 * update_blocked_averages().
	 *
	 * Also see the comment in accumulate_sum().
	 */
	if (!load)
		runnable = running = 0;

	/*
	 * Now we know we crossed measurement unit boundaries. The *_avg
	 * accrues by two steps:
	 *
	 * Step 1: accumulate *_sum since last_update_time. If we haven't
	 * crossed period boundaries, finish.
	 */
	if (!accumulate_sum(delta, sa, load, runnable, running))
		return 0;

	return 1;
}
```
`___update_load_sum`函数将sched_avg的_sum更新,其中input的load/runnable/running对于sched_avg的load_sum/runnable_sum/util_sum,所以我们需要看函数accumulate_sum的实现
## accumulate_sum
```
/*
 * Accumulate the three separate parts of the sum; d1 the remainder
 * of the last (incomplete) period, d2 the span of full periods and d3
 * the remainder of the (incomplete) current period.
 *
 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
 *
 *                           p-1
 * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
 *                           n=1
 *
 *    = u y^p +					(Step 1)
 *
 *                     p-1
 *      d1 y^p + 1024 \Sum y^n + d3 y^0		(Step 2)
 *                     n=1
 */
static __always_inline u32
accumulate_sum(u64 delta, struct sched_avg *sa,
	       unsigned long load, unsigned long runnable, int running)
{
	u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
	u64 periods;

	delta += sa->period_contrib;
	periods = delta / 1024; /* A period is 1024us (~1ms) */

	/*
	 * Step 1: decay old *_sum if we crossed period boundaries.
	 */
	if (periods) {
		sa->load_sum = decay_load(sa->load_sum, periods);
		sa->runnable_sum =
			decay_load(sa->runnable_sum, periods);
		sa->util_sum = decay_load((u64)(sa->util_sum), periods);

		/*
		 * Step 2
		 */
		delta %= 1024;
		if (load) {
			/*
			 * This relies on the:
			 *
			 * if (!load)
			 *	runnable = running = 0;
			 *
			 * clause from ___update_load_sum(); this results in
			 * the below usage of @contrib to dissapear entirely,
			 * so no point in calculating it.
			 */
			contrib = __accumulate_pelt_segments(periods,
					1024 - sa->period_contrib, delta);
		}
	}
	sa->period_contrib = delta;

	if (load)
		sa->load_sum += load * contrib;
	if (runnable)
		sa->runnable_sum += runnable * contrib << SCHED_CAPACITY_SHIFT;
	if (running)
		sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;

	return periods;
}
```
### Step 1: 旧值衰减
通过`decay_load`函数计算`u y^p `,包含三个值
* load_sum: 负载和的衰减值
* runnable_sum: 可运行和的衰减值
* util_sum: 利用率和衰减值

### Step 2: 新值贡献
通过`__accumulate_pelt_segments`计算新值贡献`d1 y^p + 1024 \Sum y^n + d3 y^0`,然后将其相加就是负载和,如下
* load_sum: += load * contrib
* runnable_sum: += runnable * contrib
* util_sum: += contrib

### 注释解释
假设有一个se再上一个时刻的load为u,经过delta时间后,我们尝试更新load,此时怎么计算这个delta的衰减呢?之前我们讨论的公式是将load乘以一个y的衰减量,但实际的代码分成了三个步骤
* d1: 在上次计算时,还差d1时间可以凑满一个period
* d2: p_contrub --> d1 后,剩下可形成的最大整数倍period(k*period)
* d3: p_contrub --> d1 --> d2,剩下不满一周期的时间

注释配图了如下
```
 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
```
如果我们计算这次经过了多少个period,那么我们可以先加上d1前的那个周期剩余值,也就是`1024 - d1`,那么计算p个period的公式为
```
p = (1024 - d1 + (d1 + d2 + d3)) / 1024
```
因为d3不满一个周期,所以没必要减掉一个d3再去除,默认除法取整了

所以带入原公式的p值
```
u' = (u + d1) × y^p + 1024 × y^(p-1) + 1024 × y^(p-2) + ... + 1024 × y^1 + d3 × y^0
```
展开第一个括号为
```
u' = u × y^p + d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0
```
回到代码上,可以看到
1. sa->period_contrib 为 1024 - d1
2. delta 从 d1+d2+d3 更新为 1024 - d1 + (delta)
3. period 为 p,通过(1024 - d1 + (d1 + d2 + d3)) / 1024 计算
4. decay_load 为 u × y^p 的计算,后面详细介绍
5. __accumulate_pelt_segments  为d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0 的计算值,后面详细介绍
6. d3 为 delta % 1024

# 总结
本文从宏观上介绍了PETL的结构体sched_avg和sum值计算,也简单说明了PELT的公式计算,但是遗留了decay_load 和 __accumulate_pelt_segments 的详细计算的介绍.

总体而言,PELT是linux负载均衡的核心,也是cfs中不可或缺的统计信息方式,深入了解PELT对理解CFS调度精髓而言至关重要

# 参考
> https://lwn.net/Articles/531853/

调度(12)-CFS调度PELT(1)

本文介绍一下CFS的另一个关键行为,选中下一个任务运行,当任务schedule的时候,会主动调用pick_next_task函数选出下一个需要调度的进程的任务

# 代码流程
```
__schedule
  pick_next_task
    __pick_next_task_fair
      pick_next_task_fair
        pick_next_entity
        set_next_entity
  context_switch
```
# pick_next_task
函数原型如下
```
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        const struct sched_class *class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in the fair class we can
         * call that function directly, but only if the @prev task wasn't of a
         * higher scheduling class, because otherwise those loose the
         * opportunity to pull in more work from other CPUs.
         */
        if (likely(prev->sched_class <= &fair_sched_class &&
                   rq->nr_running == rq->cfs.h_nr_running)) {

                p = pick_next_task_fair(rq, prev, rf);
                if (unlikely(p == RETRY_TASK))
                        goto restart;

                /* Assumes fair_sched_class->next == idle_sched_class */
                if (!p) {
                        put_prev_task(rq, prev);
                        p = pick_next_task_idle(rq);
                }

                return p;
        }

restart:
        put_prev_task_balance(rq, prev, rf);

        for_each_class(class) {
                p = class->pick_next_task(rq);
                if (p)
                        return p;
        }

        /* The idle class should always have a runnable task: */
        BUG();
}
```
根据代码,这里实际上有两个路径.区分代码为
```
if (likely(prev->sched_class <= &fair_sched_class &&
                   rq->nr_running == rq->cfs.h_nr_running))
```
也就是上一个任务是cfs调度,且所有任务都在cfs调度类中
## 路径1: 所有任务都在cfs调度类中
直接调用pick_next_task_fair,如果没有任务了,运行idle任务.如果有任务,则将上一个任务put_prev_task放回本地队列
## 路径2: 如果有rt类型的任务
因为有rt相关的实时任务,所以先put_prev_task_balance将其负载均衡检查,让rt任务拥有更高优先级权限,降低此任务因为负载均衡导致put_prev_task的时候响应时间增加.

然后遍历所有的调度器,运行pick_next_task_fair.
# pick_next_task_fair
函数简要实现如下
```
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
again:
        if (!sched_fair_runnable(rq))
                goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
        if (!prev || prev->sched_class != &fair_sched_class)
                goto simple;

        do {
                se = pick_next_entity(cfs_rq, curr);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);

        p = task_of(se);
        /*
         * Since we haven't yet done put_prev_entity and if the selected task
         * is a different task than we started out with, try and touch the
         * least amount of cfs_rqs.
         */
        if (prev != p) {
                struct sched_entity *pse = &prev->se;

                while (!(cfs_rq = is_same_group(se, pse))) {
                        int se_depth = se->depth;
                        int pse_depth = pse->depth;

                        if (se_depth <= pse_depth) {
                                put_prev_entity(cfs_rq_of(pse), pse);
                                pse = parent_entity(pse);
                        }
                        if (se_depth >= pse_depth) {
                                set_next_entity(cfs_rq_of(se), se);
                                se = parent_entity(se);
                        }
                }

                put_prev_entity(cfs_rq, pse);
                set_next_entity(cfs_rq, se);
        }

        goto done;
simple:
#endif
        if (prev)
                put_prev_task(rq, prev);

        if (repick) {
                for_each_sched_entity(se)
                        set_next_entity(cfs_rq_of(se), se);
                goto done;
        }

        do {
                se = pick_next_entity(cfs_rq, NULL);
                set_next_entity(cfs_rq, se);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);

        p = task_of(se);

idle:
        new_tasks = newidle_balance(rq, rf);

        /*
         * Because newidle_balance() releases (and re-acquires) rq->lock, it is
         * possible for any higher priority task to appear. In that case we
         * must re-start the pick_next_entity() loop.
         */
        if (new_tasks < 0)
                return RETRY_TASK;

        if (new_tasks > 0)
                goto again;

        /*
         * rq is about to be idle, check if we need to update the
         * lost_idle_time of clock_pelt
         */
        update_idle_rq_clock_pelt(rq);

        return NULL;
}
```
## 检查是否有任务
先用sched_fair_runnable检查是否有任务,如果没任务,调用 newidle_balance,此函数会`Attempts to pull tasks from other CPUs`尝试从其他cpu上拉一个任务来运行,所以有三种情况
* newidle_balance 返回负数,但是因为newidle_balance持有锁,持锁期间担心有高优先级任务出现,所以重试 if (unlikely(p == RETRY_TASK)) goto restart;
* newidle_balance 拉到任务了,跳转again
* newidle_balance 拉不到任务,让pelt计算rq->lost_idle_time

## 检查上一个任务不为cfs
`if (!prev || prev->sched_class != &fair_sched_class)`会判断没有prev或prev不是cfs,如果不是,那么走simple路径,simple路径为
* put_prev_task 将其放回本地队列
* 如果repick为1,则遍历所有se,调用set_next_entity重新选一个
* 否则逐步按组往下遍历,选择最优的se

## 如果上一个任务是cfs,且选中的任务不是prev
如果有prev,且prev是cfs中,那么任务走主路径,也叫做优化路径,其流程为
* 用pick_next_entity选中最优的se
* 用task_of拿到se的task_struct
* 如果获取的se和prev不是同一个进程
* put_prev_entity将其放回rb-tree
* 将当前se作为即将运行的se

## 如果选中的任务不是prev,且它们不在同一个组
如果它们不在一个组,那么走优化代码,最小化需要更新的层级数量,通过对于选中se的depth和prev的se的depth. 这里depth是从root开始到se所属的组的深度

举个例子
```
task_a: root-->group_a-->se_a
task_b: root-->se_a
```
那么 depth_a = 2,depth_b = 1,所以depth_a > depth_b

回到代码,两种情况
* 如果当前选中的se depth <= prev se depth,将prev放回rb-tree,然后找prev se的parent
* 如果当前选中的se depth >= prev se depth,将se放回rb-tree,然后找se的parent

可以看到,其思路是通过depth来逐步上移,直到他们depth相等,且,当depth相等的时候,se和prev se都上移一层,这样能够更新组调度下他们共属组的se
# 总结
本文介绍了pick_next_task的核心行为,如果从简单理解来看,就是单纯的找到rb-tree的最左节点,但是实际上,我们需要考虑调度组,需要考虑idle任务的场景,需要考虑遍历调度域的代码性能,需要考虑遍历组的代码性能,所以在pick_next_task中有上述的额外考虑代码.不过这些细节不用太过慌张

我们仍可以简单的认为pick_next_task找到了红黑树的最小实体.





调度(11)-CFS调度pick_next_task

在<调度(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的，大家可以清晰的了解到调度器入队的过程，从而理解调度器本身的运作机制。









