负载跟踪之（二）：pelt算法

Li*y^i

L = L0 + L1*y + L2*y^2 + L3*y^3 + ... + Ln*y^n

y^32= 0.5, y = 0.97857206

1023us: L0 = 1023

2047us: L1 = 1023 + 1024 * y

= 1023 + (L0 + 1) * y = 2025

3071us: L2 = 1023 + 1024 * y + 1024 * y^2

= 1023 + (L1 + 1) * y = 3005

4095us: L3 = 1023 + 1024 * y + 1024 * y^2 + 1024 * y^3

= 1023 + (L2 + 1) * y = 3963

5119us: L4 = 0 + 1024 * y + 1024 * y^2 + 1024 * y^3 + 1024 * y^4

= 0 + (L3 + 1) * y = 3877

6143us: L5 = 0 + 0 * y + 1024 * y^2 + 1024 * y^3 + 1024 * y^4 + 1024 * y^5

= 0 + L4 * y = 3792

7167us: L6 = 0 + L5 * y = L4 * y^2 = 3709

8191us: L7 = 0 + L6 * y = L5 * y^2 = L4 * y^3 = 3627

L = 上一个周期对系统的总的负载贡献*y + 本周期的系统负载

(A+B)y + C = [1022 + (1024 - 1022)]y + [10 - (1024 - 1022)] = 1022y + 2y + 8 = 1010

1010*y^2 + (1024 - 8)*y^2 + 1024*y + [2124 - 1024 - (1024 - 8)]

= 1010*y^2 + 1016*y^2 + 1024*y + 84 = 3024

p = 1 + (d2/1024)

L = u*y^p + d1*y^p + [1024*y^(p-1) + 1024*y^(p-2) + ... + 1024*y] + d3

= u*y^p + d1*y^p + 1024*[y^(p-1) + y^(p-2) + ... + y] + d3

p-1

= u*y^p + d1*y^p + 1024*\Sum y^i + d3

i=1

/*

* 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 {

    //上一次负载更新的时间戳，以ns为单位的时间戳，这个时间一定是1024边界对齐的，

    //注意：初始化和线程迁移时，该标记会被清零

    u64 last_update_time;

    //整个生命周期负载总和

    u64 load_sum;

    u64 runnable_sum;

    u32 util_sum;

    //上次更新时，未满一个pelt周期的部分，单位us

    u32 period_contrib;

    //整个生命周期，平均每个ns负载的值

    unsigned long load_avg;            //running+runnable状态，向权重做归一化

    unsigned long runnable_avg;        //running+runnable状态，向1024做归一化，不考虑权重

    unsigned long util_avg;            //仅running状态，向1024做归一化，不考虑权重

    //保存cfs线程上一次在睡眠时的util值（这个值是经过滑动平均后的值）

    struct util_est util_est;

} ____cacheline_aligned;

struct sched_entity {

    /* For load-balancing: */

    //这个se的权重

    struct load_weight load;

    struct rb_node run_node;

    struct list_head group_node;

    unsigned int on_rq;

    u64 exec_start;

    u64 sum_exec_runtime;

    u64 vruntime;

    u64 prev_sum_exec_runtime;

    u64 nr_migrations;

    struct sched_statistics statistics;

#ifdef CONFIG_FAIR_GROUP_SCHED

    int depth;

    struct sched_entity *parent;

    /* rq on which this entity is (to be) queued: */

    struct cfs_rq *cfs_rq;

    /* rq "owned" by this entity/group: */

    struct cfs_rq *my_q;

    //runnable_weight称作可运行权重，该概念主要针对group se提出

    //对于task se来说，runnable_weight的值就是和进程权重weight相等

    //对于group se来说，runnable_weight的值h_nr_running

    /* 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.

     */

    //记录当前se的负载信息

    struct sched_avg avg;

#endif

};

struct load_weight {

    unsigned long weight;            //权重

    u32 inv_weight;                //inv_weight等于2^32/weight，为了方便后面的计算

};

L = L0 + L1*y + L2*y^2 + L3*y^3 + ... + Ln*y^n

float f_table[] = {

    y^0, y^1, y^2, y^3, y^4, y^5,

    ...

    ...

    y^30, y^31

} = {

    0.999, 0.978, 0.957, 0.937, 0.917, 0.897,

    ...

    ...

    0.522, 0.510

};

y^35 = y^32 * y^3 = 0.5 * y^3

y^77 = y^32 * y^32 * y^13 = 0.5 * 0.5 * y^13

u32 runnable_avg_yN_inv[i] = f_table[i] * (2^32) = {

    0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,

    0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,

    0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,

    0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,

    0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,

    0x85aac367, 0x82cd8698,

};

L = L0 + L1*y + L2*y^2 + L3*y^3 + ... + Ln*y^n

= (L0*runnable_avg_yN_inv[0] + L1*runnable_avg_yN_inv[1]

         + ... + Ln*runnable_avg_yN_inv[n]) >> 32

void calc_converged_max(void)

{

    int n = -1;

    long max = 1024;

    long last = 0, y_inv = ((1UL << 32) - 1) * y;

    for (; ; n++) {

        if (n > -1)

            max = ((max * y_inv) >> 32) + 1024;

        /*

        * This is the same as:

        * max = max*y + 1024;

        */

        if (last == max)

            break;

        last = max;

    }

    printf("#define LOAD_AVG_MAX %ld\n", max);

}

L = L0 + L1*y + L2*y^2 + L3*y^3 + ... + Ln*y^n

decay_load(val, n) = [val * (y^n * 2^32)] >> 32

= (val * runnable_avg_yN_inv[n]) >> 32

/*

* Approximate:

* val * y^n, where y^32 ~= 0.5 (~1 scheduling period)

*/

static u64 decay_load(u64 val, u64 n)

{

    unsigned int local_n;

    //1.经过2016个周期后，负载的影响衰减为0

    // 其中：#define LOAD_AVG_PERIOD 32

    if (unlikely(n > LOAD_AVG_PERIOD * 63))

        return 0;

    /* after bounds checking we can collapse to 32-bit */

    local_n = n;

    /*

     * As y^PERIOD = 1/2, we can combine

     * y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)

     * With a look-up table which covers y^n (n<PERIOD)

     *

     * To achieve constant time decay_load.

     */

    //2.每经过32个周期，负载的影响衰减一半，牛逼的逻辑啊

    if (unlikely(local_n >= LOAD_AVG_PERIOD)) {

        val >>= local_n / LOAD_AVG_PERIOD;

        local_n %= LOAD_AVG_PERIOD;

    }

    //3.通过查表，计算在n个周期前负载的值val，对当前负载的贡献

    // 这里只计算了一个任务的指定周期，（即n个周期之前，所有周期需要累加）

    val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);

    return val;

}

static u32 __accumulate_pelt_segments(

            u64 periods,                    //d2阶段，占几个pelt周期

            u32 d1,                            //对应上图d1阶段，单位us

            u32 d3)                            //对应上图d3阶段，单位us

{

    u32 c1, c2, c3 = d3; /* y^0 == 1 */

    /*

     * c1 = d1 y^p

     */

    //1.完成第一步d1*y^p的计算

    c1 = decay_load((u64)d1, periods);

    /*

     * p-1

     * c2 = 1024 \Sum y^n

     * n=1

     *

     * inf inf

     * = 1024 ( \Sum y^n - \Sum y^n - y^0 )

     * n=0 n=p

     */

    //2.完成上面式5的计算

    c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;

    //3.三个部分相加，得到式3

    return c1 + c2 + c3;

}

/*

* 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,                    //在now到上一次更新时刻之间的时间差，单位us

            struct sched_avg *sa,        //要更新的负载的数据结构

            unsigned long load,        //这三个参数暂且理解有下面两个含义，具体后面分析：

            unsigned long runnable,    // a) 相当于一个开关

            int running)                // b) 作为一个缩放系数

{

    u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */

    u64 periods;

    //注意，这里的delta来源于rq->clock_pelt，已经是向最大核的最高频做scale处理后的值

    //1.加上上一次计算负载的时候不足一个pelt周期的时间

    // 加完后的delta就不再是上图中的delta了，而是delta+A部分

    delta += sa->period_contrib;

    //2.结合上一步的加操作，这里得到的periods实际上是d2之间有多少个完整的pelt周期

    periods = delta / 1024; /* A period is 1024us (~1ms) */

    /*

     * Step 1: decay old *_sum if we crossed period boundaries.

     */

    //3.若periods不为0，表示距离上一次更新的时间已经过去了好几个完整的周期，

    // 这时候需要对"上一次"统计出来的负载做衰减

    if (periods) {

        //3.1 对历史负载进行衰减

        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

         */

        //3.2 计算d1到d3之间新增负载

        // 下面的delta值对应上图中的d3

        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);

        }

    }

    //4.更新period_contrib为本次不足pelt周期的部分，

    // 此时的delta实际上是上面d3所表示的部分

    sa->period_contrib = delta;

    //5.下面逻辑决定向谁做归一化

    // load_avg: task的负载，是向权重做归一化，一个task的load_avg不会超过其权

    // 重，这里传入的load一般为task的权重，cfs_rq时，传入的表示整个

    // cfs_rq的权重

    // runnable_sum: task的负载贡献，可理解为过去总共已经运行了多长时间了，当然，

    // 这个时间是经过衰减后的值，左移表示向1024做归一化；这里乘以

    // 系数，task为1，cfs_rq表示task的个数，具体参见后面分析

    // util_sum: task的负载，这个值是向1024做归一化后的值

    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;

    //6.返回d2之间占用几个完整的pelt周期，也就是完整的窗口的个数，

    // 用于指示后续的操作：只要存在完整pelt周期，就需要对过去的时间执行衰减操作

    return periods;

}

/*

* 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}]

*/

static __always_inline int ___update_load_sum(

            u64 now,                    //当前时刻的时间戳，单位ns，不一定是1024ns边界对齐

            struct sched_avg *sa,        //要更新的负载的数据结构

            unsigned long load,        //这三个参数暂且理解有下面两个含义，具体后面分析：

            unsigned long runnable,    // a) 相当于一个开关

            int running)                // b) 作为一个缩放系数

{

    u64 delta;

    //注意：这里的now来源于rq->clock_pelt，也就是向最大核最高频做scale后的时间

    //1.首先计算距上一次负载更新，已经过去了多少ns

    // 注意sa->last_update_time是1024ns边界对齐的，

    // 这一点可以从本函数下面的第4点看出

    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.

     */

    //2.该分支考虑了ns时钟溢出的情况，如果恰好溢出，我们不做更新

    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.

     */

    //3.单位转换，ns -> us，不足一个1us不更新

    // 如果距离上一次更新不足1us，则没必要进行负载更新，直接返回0

    // 注意：这里先将单位转为us，在__update_load_avg的地方又转化回ns了

    delta >>= 10;

    if (!delta)

        return 0;

    //4.记录上一次更新的时间戳

    // 因为sa->last_update_time的初值为0，因此该值一定是1024ns边界对齐的

    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().

     */

    //5.下面这个处理表示，如果load=0，那么runnable/running也设置为0，

    // 即，若不统计load_sum，则其他两个值{runnable|util}_sum也都不统计

    // load_sum被load控制，用于统计进程处于running+runnable状态时的负载

    // runnable_sum被runnable控制，用于统计进程处于running+runnable状态的负载

    // util_sum被running控制，用于统计进程处于running状态的负载

    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.

     */

    //6.更新{load|runnable|util}_sum

    // __update_load_sum和__update_load_avg总是成对出现，前者用于更新*_sum，

    // 后者用于更新*_avg，为了防止频繁更新带来的开销，我们这里需要一个返回值来控

    // 制是否需要更新*_avg，accumlate_sum返回0表示sched_avg距离上一次更新不

    // 足一个pelt周期，这时候函数返回0，表示这里我们只更新*_sum，*_avg暂时不

    // 需要更新，也就是说，*_avg更新的最小粒度为1ms

    if (!accumulate_sum(delta, sa, load, runnable, running))

        return 0;

    //7.*_sum更新成功返回1，之后需要更新*_avg

    return 1;

}

/*

* When syncing *_avg with *_sum, we must take into account the current

* position in the PELT segment otherwise the remaining part of the segment

* will be considered as idle time whereas it's not yet elapsed and this will

* generate unwanted oscillation in the range [1002..1024[.

*

* The max value of *_sum varies with the position in the time segment and is

* equals to :

*

* LOAD_AVG_MAX*y + sa->period_contrib

*

* which can be simplified into:

*

* LOAD_AVG_MAX - 1024 + sa->period_contrib

*

* because LOAD_AVG_MAX*y == LOAD_AVG_MAX-1024

*

* The same care must be taken when a sched entity is added, updated or

* removed from a cfs_rq and we need to update sched_avg. Scheduler entities

* and the cfs rq, to which they are attached, have the same position in the

* time segment because they use the same clock. This means that we can use

* the period_contrib of cfs_rq when updating the sched_avg of a sched_entity

* if it's more convenient.

*/

static __always_inline void ___update_load_avg(

            struct sched_avg *sa,

            unsigned long load)            //调度实体se的权重weight

{

    //1.求负载贡献的极值

    // 一个task连续运行无数个pelt周期，他的负载贡献都不会超过这个极限值

    u32 divider = get_pelt_divider(sa);

    /*

     * Step 2: update *_avg.

     */

    //2.更新{load|runnable|util}_avg

    sa->load_avg = div_u64(load * sa->load_sum, divider);

    sa->runnable_avg = div_u64(sa->runnable_sum, divider);

    WRITE_ONCE(sa->util_avg, sa->util_sum / divider);

}

divider = LOAD_AVG_MAX - (1024 - sa->period_contrib)

static inline u32 get_pelt_divider(struct sched_avg *avg)

{

    //计算等比数列极值，不管一个task运行了少个pelt周期，其负载贡献都不可能超过这个值

    return LOAD_AVG_MAX - 1024 + avg->period_contrib;

}

void update_rq_clock(struct rq *rq)

{

    s64 delta;

    lockdep_assert_held(&rq->lock);

    if (rq->clock_update_flags & RQCF_ACT_SKIP)

        return;

#ifdef CONFIG_SCHED_DEBUG

    if (sched_feat(WARN_DOUBLE_CLOCK))

        SCHED_WARN_ON(rq->clock_update_flags & RQCF_UPDATED);

    rq->clock_update_flags |= RQCF_UPDATED;

#endif

    //1.rq->clock基于sched_clock

    delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;

    if (delta < 0)

        return;

    rq->clock += delta;

    //2.更新clock_task

    update_rq_clock_task(rq, delta);

}

static void update_rq_clock_task(

            struct rq *rq,

            s64 delta)                //这个时间来源于rq->clock，未向最大核最高频做scale处理

{

/*

* In theory, the compile should just see 0 here, and optimize out the call

* to sched_rt_avg_update. But I don't trust it...

*/

    s64 __maybe_unused steal = 0, irq_delta = 0;

#ifdef CONFIG_IRQ_TIME_ACCOUNTING

    //1.得到在中断中的耗时

    irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;

    /*

     * Since irq_time is only updated on {soft,}irq_exit, we might run into

     * this case when a previous update_rq_clock() happened inside a

     * {soft,}irq region.

     *

     * When this happens, we stop ->clock_task and only update the

     * prev_irq_time stamp to account for the part that fit, so that a next

     * update will consume the rest. This ensures ->clock_task is

     * monotonic.

     *

     * It does however cause some slight miss-attribution of {soft,}irq

     * time, a more accurate solution would be to update the irq_time using

     * the current rq->clock timestamp, except that would require using

     * atomic ops.

     */

    if (irq_delta > delta)

        irq_delta = delta;

    rq->prev_irq_time += irq_delta;

    //2.减去在中断中的耗时

    delta -= irq_delta;

#endif

#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING

    if (static_key_false((&paravirt_steal_rq_enabled))) {

        steal = paravirt_steal_clock(cpu_of(rq));

        steal -= rq->prev_steal_time_rq;

        if (unlikely(steal > delta))

            steal = delta;

        rq->prev_steal_time_rq += steal;

        delta -= steal;

    }

#endif

    //3.注意，rq->clock_task这个时间来源于rq->clock，不包括中断处理的时间

    // 也就是说只有在有task运行时才会向前走，并且没有向最大核最高频做归一化

    rq->clock_task += delta;

#ifdef CONFIG_HAVE_SCHED_AVG_IRQ

    if ((irq_delta + steal) && sched_feat(NONTASK_CAPACITY))

        update_irq_load_avg(rq, irq_delta + steal);

#endif

    //4.更新clock_pelt

    update_rq_clock_pelt(rq, delta);

}

/*

* The clock_pelt scales the time to reflect the effective amount of

* computation done during the running delta time but then sync back to

* clock_task when rq is idle.

*

*

* absolute time | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16

* @ max capacity ------******---------------******---------------

* @ half capacity ------************---------************---------

* clock pelt | 1| 2| 3| 4| 7| 8| 9| 10| 11|14|15|16

*

*/

static inline void update_rq_clock_pelt(

            struct rq *rq,

            s64 delta)            //这里的delta来源于rq->clock_task

{                                //已经扣除了在中断中的时间

    //1.如果当前cpu进入idle，可以将clock_pelt同步到clock_task

    if (unlikely(is_idle_task(rq->curr))) {

        /* The rq is idle, we can sync to clock_task */

        rq->clock_pelt = rq_clock_task(rq);

        return;

    }

    /*

     * When a rq runs at a lower compute capacity, it will need

     * more time to do the same amount of work than at max

     * capacity. In order to be invariant, we scale the delta to

     * reflect how much work has been really done.

     * Running longer results in stealing idle time that will

     * disturb the load signal compared to max capacity. This

     * stolen idle time will be automatically reflected when the

     * rq will be idle and the clock will be synced with

     * rq_clock_task.

     */

    /*

     * Scale the elapsed time to reflect the real amount of

     * computation

     */

    //2.向最大核的最高频做归一化处理

    // 第一步是向这个cpu的最高频做归一化处理

    // 第二步是向最大核的最高频做归一化处理

    delta = cap_scale(delta, arch_scale_cpu_capacity(cpu_of(rq)));

    delta = cap_scale(delta, arch_scale_freq_capacity(cpu_of(rq)));

    //3.得到对齐后的时间

    rq->clock_pelt += delta;

}

/*

* When rq becomes idle, we have to check if it has lost idle time

* because it was fully busy. A rq is fully used when the /Sum util_sum

* is greater or equal to:

* (LOAD_AVG_MAX - 1024 + rq->cfs.avg.period_contrib) << SCHED_CAPACITY_SHIFT;

* For optimization and computing rounding purpose, we don't take into account

* the position in the current window (period_contrib) and we use the higher

* bound of util_sum to decide.

*/

static inline void update_idle_rq_clock_pelt(struct rq *rq)

{

    u32 divider = ((LOAD_AVG_MAX - 1024) << SCHED_CAPACITY_SHIFT) - LOAD_AVG_MAX;

    //1.sum包括在运行cfs,rt,dl线程所消耗的时间

    u32 util_sum = rq->cfs.avg.util_sum;

    util_sum += rq->avg_rt.util_sum;

    util_sum += rq->avg_dl.util_sum;

    /*

     * Reflecting stolen time makes sense only if the idle

     * phase would be present at max capacity. As soon as the

     * utilization of a rq has reached the maximum value, it is

     * considered as an always runnig rq without idle time to

     * steal. This potential idle time is considered as lost in

     * this case. We keep track of this lost idle time compare to

     * rq's clock_task.

     */

    //2.rq->clock_task只有在这个rq上有task在运行时，才会累加

    if (util_sum >= divider)

        rq->lost_idle_time += rq_clock_task(rq) - rq->clock_pelt;

}

static inline u64 rq_clock_pelt(struct rq *rq)

{

    lockdep_assert_held(&rq->lock);

    assert_clock_updated(rq);

    return rq->clock_pelt - rq->lost_idle_time;

}

static void account_entity_dequeue (

            struct cfs_rq *cfs_rq,

            struct sched_entity *se)

{

    //1.将se的权重从cfs_rq中移除

    update_load_sub(&cfs_rq->load, se->load.weight);

#ifdef CONFIG_SMP

    if (entity_is_task(se)) {

        account_numa_dequeue(rq_of(cfs_rq), task_of(se));

        list_del_init(&se->group_node);

    }

#endif

    //2.计数减1

    cfs_rq->nr_running--;

}

static void account_entity_enqueue (

            struct cfs_rq *cfs_rq,

            struct sched_entity *se)

{

    //1.将se的权重累加进cfs_rq

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

#ifdef CONFIG_SMP

    if (entity_is_task(se)) {

        struct rq *rq = rq_of(cfs_rq);

        account_numa_enqueue(rq, task_of(se));

        list_add(&se->group_node, &rq->cfs_tasks);

    }

#endif

    //2.计数加1

    cfs_rq->nr_running++;

}

static inline void update_load_add(struct load_weight *lw, unsigned long inc)

{

    lw->weight += inc;

    lw->inv_weight = 0;

}

static inline void update_load_sub(struct load_weight *lw, unsigned long dec)

{

    lw->weight -= dec;

    lw->inv_weight = 0;

}

static inline void update_load_set(struct load_weight *lw, unsigned long w)

{

    lw->weight = w;

    lw->inv_weight = 0;

}

int __update_load_avg_se(

            u64 now,            //时间来源于rq->clock_pelt，也就是向最大核最高频做scale后的值

            struct cfs_rq *cfs_rq,

            struct sched_entity *se)

{

    //1.更新{load|runnable|util}_sum

    if (___update_load_sum(now, &se->avg,

                !!se->on_rq,

                se_runnable(se),

                cfs_rq->curr == se)) {

        //2.更新{load|runnable|util}_avg

        ___update_load_avg(&se->avg, se_weight(se));

        //3.与sa->util_est成员有关，和cfs进程的利用率相关，暂不讨论

        cfs_se_util_change(&se->avg);

        //4.打印trace信息

        trace_pelt_se_tp(se);

        //5.成功更新负载返回1，未更新返回0

        return 1;

    }

    return 0;

}

contrib

load_avg = --------------------------------------------- * se_weight(se)

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (se->on_rq)

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (se->on_rq)

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib = decay(history_contrib) + new_contrib * h_nr_running

因为：

contrib = decay(history_contrib) + new_contrib * h_nr_running

<= (decay(history_contrib) + new_contrib) * h_nr_running

所以

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

(decay(history_contrib) + new_contrib) * h_nr_running

<= ---------------------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib

util_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (cfs_rq->curr == se)

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

static inline unsigned long task_util(struct task_struct *p)

{

    return READ_ONCE(p->se.avg.util_avg);

}

#ifdef CONFIG_SMP

/* Give new sched_entity start runnable values to heavy its load in infant time */

void init_entity_runnable_average(struct sched_entity *se)

{

    struct sched_avg *sa = &se->avg;

    //1.注意，这里将所有成员清零，所有gse的所有负载信息全部清零

    memset(sa, 0, sizeof(*sa));

    /*

     * Tasks are initialized with full load to be seen as heavy tasks until

     * they get a chance to stabilize to their real load level.

     * Group entities are initialized with zero load to reflect the fact that

     * nothing has been attached to the task group yet.

     */

    //2.当调度实体是一个task时，执行下面的if分支

    // 侧面也说明，当se是一个group时，初始化的load_avg为0

    // 如果这个se表示一个task，则load_avg被初始化为se的权重，

    // 这表示这个task被认为是一个重载task，（因为load_avg的最大值

    // 就是se的权重），这样，进程被创建后就能立刻被调度到

    // 如果这个se表示一个group，则load_avg初始化的值为0，

    // 这意味着这个group中没有任何task需要调度

    if (entity_is_task(se))

        sa->load_avg = scale_load_down(se->load.weight);

    /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */

}

#else /* !CONFIG_SMP */

void init_entity_runnable_average(struct sched_entity *se)

{

}

#endif

OP5285:/ $ cat /proc/3808/task/3808/sched

ndroid.launcher (3808, #threads: 66)

-------------------------------------------------------------------

se.exec_start : 11632575.807018

se.vruntime : 20469.807223

se.sum_exec_runtime : 6715.492754

se.nr_migrations : 6017

se.statistics.sum_sleep_runtime : 11612296.141359

se.statistics.wait_start : 0.000000

se.statistics.sleep_start : 11642677.835913

se.statistics.block_start : 0.000000

se.statistics.sleep_max : 60050.469245

se.statistics.block_max : 33.051510

se.statistics.exec_max : 4.662500

se.statistics.slice_max : 2.255209

se.statistics.wait_max : 74.996094

se.statistics.wait_sum : 5056.303100

se.statistics.wait_count : 16167

se.statistics.iowait_sum : 115.568020

se.statistics.iowait_count : 88

se.statistics.nr_migrations_cold : 0

se.statistics.nr_failed_migrations_affine : 0

se.statistics.nr_failed_migrations_running : 9

se.statistics.nr_failed_migrations_hot : 5

se.statistics.nr_forced_migrations : 0

se.statistics.nr_wakeups : 9988

se.statistics.nr_wakeups_sync : 953

se.statistics.nr_wakeups_migrate : 3622

se.statistics.nr_wakeups_local : 1097

se.statistics.nr_wakeups_remote : 8891

se.statistics.nr_wakeups_affine : 0

se.statistics.nr_wakeups_affine_attempts : 0

se.statistics.nr_wakeups_passive : 0

se.statistics.nr_wakeups_idle : 0

avg_atom : 0.418567

avg_per_cpu : 1.116086

nr_switches : 16044

nr_voluntary_switches : 9987

nr_involuntary_switches : 6057

se.load.weight : 1048576

se.avg.load_sum : 601

se.avg.runnable_sum : 615844

se.avg.util_sum : 191530

se.avg.load_avg : 10

se.avg.runnable_avg : 10

se.avg.util_avg : 1

se.avg.last_update_time : 11627031569424

se.avg.util_est.ewma : 17

se.avg.util_est.enqueued : 4

uclamp.min : 0

uclamp.max : 1024

effective uclamp.min : 0

effective uclamp.max : 1024

policy : 0

prio : 120

clock-delta : 105

OP5285:/ $

int __update_load_avg_blocked_se(u64 now, struct sched_entity *se)

{

    //1.更新{load|runnable|util}_sum

    // 对已经block的se，仅对历史负载进行衰减，不记录新增的时间内产生

    // 的负载贡献。因为此时task都已经进入D状态，不运行啦

    if (___update_load_sum(now, &se->avg, 0, 0, 0)) {

        //2.更新{load|runnable|util}_avg

        // 在计算load_avg的时候，需要对新增的负载贡献乘以权重

        ___update_load_avg(&se->avg, se_weight(se));

        //3.打印trace信息

        trace_pelt_se_tp(se);

        //4.成功更新返回1，未更新返回0

        return 1;

    }

    return 0;

}

contrib

load_avg = --------------------------------------------- * se_weight(se)

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib = decay(history_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib = decay(history_contrib)

contrib

util_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib = decay(history_contrib)

int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)

{

    //1.更新{load|runnable|util}_sum

    if (___update_load_sum(now, &cfs_rq->avg,

                scale_load_down(cfs_rq->load.weight),

                cfs_rq->h_nr_running,

                cfs_rq->curr != NULL)) {

        //2.更新{load|runnable|util}_avg，注意传入的参数为1

        ___update_load_avg(&cfs_rq->avg, 1);

        //3.打印trace信息

        trace_pelt_cfs_tp(cfs_rq);

        //4.成功更新返回1，未更新返回0

        return 1;

    }

    return 0;

}

/**

* update_cfs_rq_load_avg - update the cfs_rq's load/util averages

* @now: current time, as per cfs_rq_clock_pelt()

* @cfs_rq: cfs_rq to update

*

* The cfs_rq avg is the direct sum of all its entities (blocked and runnable)

* avg. The immediate corollary is that all (fair) tasks must be attached, see

* post_init_entity_util_avg().

*

* cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.

*

* Returns true if the load decayed or we removed load.

*

* Since both these conditions indicate a changed cfs_rq->avg.load we should

* call update_tg_load_avg() when this function returns true.

*/

static inline int update_cfs_rq_load_avg(

            u64 now,

            struct cfs_rq *cfs_rq)

{

    unsigned long removed_load = 0, removed_util = 0, removed_runnable = 0;

    struct sched_avg *sa = &cfs_rq->avg;

    int decayed = 0;

    //1.nr表示这个removed成员中已经累积了几个task的负载信息

    if (cfs_rq->removed.nr) {

        unsigned long r;

        u32 divider = get_pelt_divider(&cfs_rq->avg);

        //2.取出哪些已经被removed的负载信息，并清零

        raw_spin_lock(&cfs_rq->removed.lock);

        swap(cfs_rq->removed.util_avg, removed_util);

        swap(cfs_rq->removed.load_avg, removed_load);

        swap(cfs_rq->removed.runnable_avg, removed_runnable);

        cfs_rq->removed.nr = 0;

        raw_spin_unlock(&cfs_rq->removed.lock);

        //3.直接将removed累积的负载信息从cfs_rq中扣除

        // 注意下面更新*_sum负载信息的方式，

        r = removed_load;

        sub_positive(&sa->load_avg, r);

        sa->load_sum = sa->load_avg * divider;

        r = removed_util;

        sub_positive(&sa->util_avg, r);

        sa->util_sum = sa->util_avg * divider;

        r = removed_runnable;

        sub_positive(&sa->runnable_avg, r);

        sa->runnable_sum = sa->runnable_avg * divider;

        /*

         * removed_runnable is the unweighted version of removed_load so we

         * can use it to estimate removed_load_sum.

         */

        add_tg_cfs_propagate(cfs_rq,

            -(long)(removed_runnable * divider) >> SCHED_CAPACITY_SHIFT);

        decayed = 1;

    }

    //4.最主要是这里的更新cfs_rq的负载信息

    decayed |= __update_load_avg_cfs_rq(now, cfs_rq);

#ifndef CONFIG_64BIT

    smp_wmb();

    cfs_rq->load_last_update_time_copy = sa->last_update_time;

#endif

    return decayed;

}

/*

* Task first catches up with cfs_rq, and then subtract

* itself from the cfs_rq (task must be off the queue now).

*/

static void remove_entity_load_avg(struct sched_entity *se)

{

    struct cfs_rq *cfs_rq = cfs_rq_of(se);

    unsigned long flags;

    /*

     * tasks cannot exit without having gone through wake_up_new_task() ->

     * post_init_entity_util_avg() which will have added things to the

     * cfs_rq, so we can remove unconditionally.

     */

    sync_entity_load_avg(se);

    raw_spin_lock_irqsave(&cfs_rq->removed.lock, flags);

    ++cfs_rq->removed.nr;

    cfs_rq->removed.util_avg    += se->avg.util_avg;

    cfs_rq->removed.load_avg    += se->avg.load_avg;

    cfs_rq->removed.runnable_avg    += se->avg.runnable_avg;

    raw_spin_unlock_irqrestore(&cfs_rq->removed.lock, flags);

}

contrib

load_avg = --------------------------------------------- * 1

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (cfs_rq->load.weight)

contrib = decay(history_contrib) + new_contrib * cfs_rq->load.weight

else

contrib = decay(history_contrib)

contrib = decay(history_contrib) + new_contrib * cfs_rq->load.weight

<= (decay(history_contrib) + new_contrib) * cfs_rq->load.weight

contrib

load_avg = --------------------------------------------- * 1

LOAD_AVG_MAX - (1024 - sa->period_contrib)

(decay(history_contrib) + new_contrib) * cfs_rq->load.weight

<= ----------------------------------------------------------------

LOAD_AVG_MAX - (1024 - sa->period_contrib)

(decay(history_contrib) + new_contrib)

= --------------------------------------------- * cfs_rq->load.weight

LOAD_AVG_MAX - (1024 - sa->period_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (cfs_rq->h_nr_running)

contrib = decay(history_contrib) + new_contrib * cfs_rq->h_nr_running

else

contrib = decay(history_contrib)

contrib

util_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (cfs_rq->curr != NULL)

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

static inline unsigned long cfs_rq_load_avg(struct cfs_rq *cfs_rq)

{

    return cfs_rq->avg.load_avg;

}

static inline unsigned long cfs_rq_runnable_avg(struct cfs_rq *cfs_rq)

{

    return cfs_rq->avg.runnable_avg;

}

static unsigned long cpu_runnable(struct rq *rq)

{

    return cfs_rq_runnable_avg(&rq->cfs);

}

/*

* rt_rq:

*

* util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked

* util_sum = cpu_scale * load_sum

* runnable_sum = util_sum

*

* load_avg and runnable_avg are not supported and meaningless.

*

*/

int update_rt_rq_load_avg(

            u64 now,

            struct rq *rq,

            int running)            //标记当前正在运行的任务是否为rt

{

    if (___update_load_sum(now, &rq->avg_rt,

                running,

                running,

                running)) {

        ___update_load_avg(&rq->avg_rt, 1);

        trace_pelt_rt_tp(rq);

        return 1;

    }

    return 0;

}

contrib

load_avg = --------------------------------------------- * 1

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_rt(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_rt(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

util_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_rt(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

static inline void set_next_task_rt(

            struct rq *rq,

            struct task_struct *p,        //下一个要运行的rt线程

            bool first)

{

    ...

    /*

     * If prev task was rt, put_prev_task() has already updated the

     * utilization. We only care of the case where we start to schedule a

     * rt task

     */

    //1.p是下一个被pick出来即将被运行的rt线程，但是无法确定上一次运行的线程是不是rt，

    // 也就是说无法确定刚刚逝去的那段时间是不是在运行rt线程，因此要做判断

    // 满足下面条件，表示prev并不是一个rt线程，也就是说刚刚逝去的那段时间是在运行一

    // 个非rt的线程，这时候我们只需要在这里对rt_rq的原有负载信息进行衰减，不用考虑新

    // 增的负载贡献，如果当前运行的线程是rt的怎么办呢？由上面的分析可知，由rt切到rt

    // 线程，负载贡献在put_prev_task中就完成更新了，在这里不需要重复更新了

    if (rq->curr->sched_class != &rt_sched_class)

        update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 0);

    ...

}

static void put_prev_task_rt(struct rq *rq, struct task_struct *p)

{

    ...

    //1.一个rt线程运行结束后，释放cpu使用权，重新挂回对应的rt链表时，会调用这个函数

    // 因为刚刚逝去的那段时间是在运行rt线程，所以我们需要将这段逝去时间带来的负载贡献

    // 累加到rt_rq的负载信息上，所以下面参数传入1

    update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 1);

    ...

}

/*

* scheduler tick hitting a task of our scheduling class.

*

* NOTE: This function can be called remotely by the tick offload that

* goes along full dynticks. Therefore no local assumption can be made

* and everything must be accessed through the @rq and @curr passed in

* parameters.

*/

static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)

{

    ...

    //1.命中的线程正是rt，说明刚刚逝去的那段时间是在运行rt线程，

    // 此时不仅要对旧的负载贡献进行衰减，还要记录新的负载贡献

    update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 1);

    ...

}

/*

* When switching a task to RT, we may overload the runqueue

* with RT tasks. In this case we try to push them off to

* other runqueues.

*/

static void switched_to_rt(

            struct rq *rq,

            struct task_struct *p)        //即将切换到的rt线程

{

    /*

     * If we are running, update the avg_rt tracking, as the running time

     * will now on be accounted into the latter.

     */

    //1.判断rq->curr是否就是p，如果满足这个条件，则说明p刚从一个非rt

    // 属性切换到rt，也就是说刚刚逝去的那段时间实际上是在执行非rt线程，

    // 这时候需要对rt_rq的负载贡献进行衰减

    if (task_current(rq, p)) {

        update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 0);

        return;

    }

    ...

}

/*

* switched_from, switched_to and prio_changed must _NOT_ drop rq->lock,

* use the balance_callback list if you want balancing.

*

* this means any call to check_class_changed() must be followed by a call to

* balance_callback().

*/

static inline void check_class_changed (

            struct rq *rq,

            struct task_struct *p,                    //要切换调度类的线程

            const struct sched_class *prev_class,    //上一次所属的调度类

            int oldprio)

{

    //调度类发送切换就执行下面的分支，分别执行一次switched_from和switched_to

    if (prev_class != p->sched_class) {

        if (prev_class->switched_from)

            prev_class->switched_from(rq, p);

        p->sched_class->switched_to(rq, p);

    } else if (oldprio != p->prio || dl_task(p))

        p->sched_class->prio_changed(rq, p, oldprio);

}

static inline unsigned long cpu_util_rt(struct rq *rq)

{

    return READ_ONCE(rq->avg_rt.util_avg);

}

/*

* dl_rq:

*

* util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked

* util_sum = cpu_scale * load_sum

* runnable_sum = util_sum

*

* load_avg and runnable_avg are not supported and meaningless.

*

*/

int update_dl_rq_load_avg(

            u64 now,

            struct rq *rq,

            int running)                //标记当前rq上运行的线程是不是dl的

{

    if (___update_load_sum(now, &rq->avg_dl,

                running,

                running,

                running)) {

        ___update_load_avg(&rq->avg_dl, 1);

        trace_pelt_dl_tp(rq);

        return 1;

    }

    return 0;

}

contrib

load_avg = ---------------------------------------------

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_dl(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

runnable_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_dl(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

contrib

util_avg = --------------------------------------------- * 1024

LOAD_AVG_MAX - (1024 - sa->period_contrib)

if (is_dl(rq->curr))

contrib = decay(history_contrib) + new_contrib

else

contrib = decay(history_contrib)

static void set_next_task_dl(struct rq *rq, struct task_struct *p, bool first)

{

    ...

    //判断上一次运行的线程是不是dl的，如果不是dl的则需要进行衰减

    if (rq->curr->sched_class != &dl_sched_class)

        update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);

    ...

}

static void put_prev_task_dl(struct rq *rq, struct task_struct *p)

{

    ...