上一篇文章中介绍了 accumulate_sum 函数，此函数实现了load_sum/runnable_sum/util_sum的计算，而实际上的计算方式是 decay_load，本文介绍decay_load函数

另一方面accumulate_sum也使用了__accumulate_pelt_segments函数来计算新值贡献，本文一并介绍清楚

__accumulate_pelt_segments

此函数的实现如下


static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
{
        u32 c1, c2, c3 = d3; /* y^0 == 1 */

        /*
         * c1 = 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
         */
        c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;

        return c1 + c2 + c3;
}

此函数比较清晰，首先使用了 decay_load 计算d1*y^p周期的衰减，然后使用LOAD_AVG_MAX这个速算值，如下


1024 × Σ(y^n, n=1 到 p-1)

最终就是上文提到的


d1 × y^p + 1024 × Σ(y^n, n=1 到 p-1) + d3 × y^0

在此函数中我们记作


c1 + c2 + c3

所以此函数我们的重点是解析c2


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

首先我们看看我们计算的目标


c2 = 1024 × (y¹ + y² + y³ + ... + y^{p-1})

我们先以始为终的方式认为


LOAD_AVG_MAX = 1024 * Σ(y^n, n=0 到 n)

那么 decay_load(LOAD_AVG_MAX, periods) 就是


1024 * Σ(y^n, n=p)

那么两值相减就是


1024 * Σ(y^n, n=0 到 p) = 1024 * Σ(y^n, n=0 到 n) - 1024 * Σ(y^n, n=p)

我们要求的c2是


Σ(y^n, n=1 到 p-1) = 1024 * Σ(y^n, n=0 到 p) - 1024 * y^0

那就就得到了


c2 = 1024 * ((y0 + y² + y³ + ... + y^{n}) - (y0 + y² + y³ + ... + y^{p}) - (y0))

进入代码转换就是


c2 = 1024 * (LOAD_AVG_MAX / 1024 - decay_load(LOAD_AVG_MAX, periods) / 1024 - 1);

LOAD_AVG_MAX

好了，那么我们继续关注 LOAD_AVG_MAX 这个宏，为什么它假设成立，我们看假设


LOAD_AVG_MAX = 1024 * Σ(y^n, n=0 到 n)
或
LOAD_AVG_MAX = 1024 * (y0 + y² + y³ + ... + y^{n})

我们看代码的定义


#define LOAD_AVG_MAX pelt_load_avg_max
int pelt_load_avg_max = PELT32_LOAD_AVG_MAX;
#define PELT32_LOAD_AVG_MAX 47742

所以我们看 47742 这个值怎么预先计算的我们先看y这个常量


y^32 = 0.5
y = 0.9786

按照我们之前分析的，LOAD_AVG_MAX等效于


LOAD_AVG_MAX / 1024 = (y0 + y² + y³ + ... + y^{n})

因为y = 0.9786，所以此公式是收敛的，我们一定可以获取一个收敛值。下面开始计算，假设S = LOAD_AVG_MAX / 1024


S = 1 + y + y² + y³ + ... + y^{n}
S * y = y + y2 + y3 + ... + y^{n+1}
S - S * y = (1 + y + y² + y³ + ... + y^{n}) - (y + y2 + y3 + ... + y^{n+1})

我们假设取n为无限值先，那么n=n+1，可以得到近似如下


S * (1 - y) = 1
S = 1 / (1 - y)

我们要计算的是LOAD_AVG_MAX，这里把1024代入


LOAD_AVG_MAX = 1024 / (1 - y)

然后我们把y代入


y = 2^(-1/32)
LOAD_AVG_MAX = 1024 / (1 - 2^(-1/32)) = 47742

所以内核直接预先计算了 LOAD_AVG_MAX 为 47742。

到这里，我们就完全明白了__accumulate_pelt_segments的计算过程，下面看decay_load

decay_load

首先看函数原型


/*
 * Approximate:
 *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
 */
static u64 decay_load(u64 val, u64 n)
{
        unsigned int local_n;

        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.
         */
        if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
                val >>= local_n / LOAD_AVG_PERIOD;
                local_n %= LOAD_AVG_PERIOD;
        }

        val = mul_u64_u32_shr(val, pelt_runnable_avg_yN_inv[local_n], 32);
        return val;
}

我们知道 decay_load 用来计算就旧值衰减 u y^p，所以输入参数是val, n，下面看LOAD_AVG_PERIOD的定义


#define LOAD_AVG_PERIOD pelt_load_avg_period
int pelt_load_avg_period = PELT32_LOAD_AVG_PERIOD;
#define PELT32_LOAD_AVG_PERIOD 32

如果local_n大于等于32，那么将local_n除以32后，这样可以速算y^32的部分，因为其值是0.5。解释如下


y^n = y^(32*n/32) * y^(n%32)

这种展开就是为了让 y^32 = 0.5 能够速算为如下


y^n = 0.5^(n/32) * y^(n%32)

pelt_runnable_avg_yN_inv

上面通过代码分析描述了decay_load的目的，其计算就是简单将y^n拆解成0.5^(n/32) * y^(n%32)，而实际计算的时候，还依赖另一个速算表pelt_runnable_avg_yN_inv，我们先看其定义


pelt_runnable_avg_yN_inv = pelt32_runnable_avg_yN_inv;
static const u32 pelt32_runnable_avg_yN_inv[] __maybe_unused = {
        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,
};

这个是y^(-n)的速算值，n的取值范围是0-31。为什么要这样速算呢，如下

首先我们知道y^32=0.5，我的目的是计算val * y^n，那么可以拆解如下


val * y^n = val / y^(32-n) * y^32 ~= val * y^(-n) / 2^32

所以 pelt32_runnable_avg_yN_inv 就是 y^(-n), 这样只需要统计获取n从0-31的所有值进行计算进行代入，也就是如下


val * y^n = val * pelt32_runnable_avg_yN_inv / 2^32

总结

本文介绍了CFS中计算累加和以及旧值衰减的计算公式和速查表解释。可以看到，cfs中通过内置预先计算好的表来屏蔽复杂运算的耗时，而计算的过程中，通过一定的数据近似尽可能的获得了累加和和旧值衰减的较准确值。

我们在开发调度的时候，这些东西不需要取修改，因为是社区经过统计得出来得有效经验值，但是为了更清晰得了解调度，这个详细得计算细节还是要扣清楚的。

目录

__accumulate_pelt_segments

LOAD_AVG_MAX

decay_load

pelt_runnable_avg_yN_inv

总结