CFS完全公平调度算法

struct sched_avg {
 /*
  * These sums represent an infinite geometric series and so are bound
  * above by 1024/(1-y).  Thus we only need a u32 to store them for all
  * choices of y < 1-2^(-32)*1024.
  */
 u32 runnable_avg_sum, runnable_avg_period;    /* 前一个：调度实体累计负载均衡值（不包括未进入运行队列期间的负载均衡值）；后一个：调度实体累计负载均衡值*/
 u64 last_runnable_update;    /* 最近一次更新负载均衡值的时间，用ns表示 */
 s64 decay_count;    /* 衰减次数 */
 unsigned long load_avg_contrib;    /* 该调度实体对它所属的CFS_RQ队列的负载均衡贡献值 */
};


调度实体的负载均衡值周期性的被更新，由__update_entity_runnable_avg（）函数实际执行该操作。struct sched_avg用于跟踪调度实体的负载变更情况。

 * 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_entity_runnable_avg(u64 now,
                            struct sched_avg *sa,
                            int runnable)
{
    u64 delta, periods;
    u32 runnable_contrib;
    int delta_w, decayed = 0;

    delta = now - sa->last_runnable_update;    /* 计算新采样周期的值 */
    /*
     * 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_runnable_update = now;
        return 0;
    }

    /*
     * Use 1024ns as the unit of measurement since it's a reasonable
     * approximation of 1us and fast to compute.
     */
    delta >>= 10;    /* 把周期值由ns转化为us */
    if (!delta)
        return 0;
    sa->last_runnable_update = now;  /* 记录负载均衡值更新的最新时间点 */

    /* delta_w is the amount already accumulated against our next period */
    delta_w = sa->runnable_avg_period % 1024;  /* 历史负载均衡值对齐到1024us的偏移量 */
    if (delta + delta_w >= 1024) {   /* 自从上一次更新负载均衡值后，已至少累计了1024us时间（上次未对齐到1024us偏移量加上本次更新周期值） */
        /* period roll-over */
        decayed = 1;  /* 返回历史负载均衡衰减状态 */

        /*
         * Now that we know we're crossing a period boundary, figure
         * out how much from delta we need to complete the current
         * period and accrue it.
         */
        delta_w = 1024 - delta_w;
        if (runnable)
            sa->runnable_avg_sum += delta_w;  /* 如果该调度实体在运行队列上，则更新runnable_avg_sum值 */
        sa->runnable_avg_period += delta_w;

        delta -= delta_w;

        /* Figure out how many additional periods this update spans */
        periods = delta / 1024;  /* 针对本次采样周期内剩余时间的负载均衡值计算，分别先算出计算周期数和1024us遗留偏移 */
        delta %= 1024;

        sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
                         periods + 1);  /* 对历史累计负载均衡值进行衰减处理，得到当前时间等效的历史累计负载均衡值 */
        sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
                         periods + 1);  /* 同上 */

        /* Efficiently calculate \sum (1..n_period) 1024*y^i */
        runnable_contrib = __compute_runnable_contrib(periods);  /* 计算本次采样周期折算计算周期数对负载均衡值的贡献值 */
        if (runnable)
            sa->runnable_avg_sum += runnable_contrib;
        sa->runnable_avg_period += runnable_contrib;  /* 累加历史负载均衡值和本次获得的负载均衡值 */
    }

    /* Remainder of delta accrued against u_0` */
    if (runnable)
        sa->runnable_avg_sum += delta;
    sa->runnable_avg_period += delta;   /* 当前总的负载均衡值还要加上未满1024us的剩余时间，这些时间不做衰减处理 */

    return decayed;
}