2.7.3 负载追踪 - 计算负载

虽然负载的计算公式是一个无穷级数之和，但由于我们对历史负载并不感兴趣，因此计算起来还是很方便的，假设系统每个周期都会计算一次负载，那么当前负载的计算方式为 L = L0 + L1*y, 其中L1是上一个周期的负载，这样从第一个周期开始，每个周期在计算负载时都已经完成了对前面所有周期的负载累计。

然而问题是计算负载的时间点并没有这么精确，两次的时间差可能跨越了多个周期，如下图所示：

其中t1是上次系统计算负载的时间点，假设当时的负载为u, now是当前时间，每个周期为1024us, 那么根据Linux负载的计算公式，当前系统的负载为： u' = u*y^p + d1*y^p + 1024 * (y^(p-1) + y^(p-2) + ... + y) + d3, 我们将该公式分为两部分来分析：

1. L2 = u*y^p ，其中 u+d1 为一常数，系统需要找到高效的方式计算 y^p. 为了避免浮点数运算，系统将该指数运算等价于 y^p=y^p *2^32 >> 32, 即先乘以一个 232, 再将结果右移32位。为了提升效率，系统将 y^p*2^32 的值提前计算好了存放在数组 runnable_avg_yN_inv 中，其内容如下：

   /* file: kernel/sched/sched-pelt.h */
   static const u32 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,
   };

   该数组只有32个元素，因为 y^32=0.5, 所以当 p>32 时，我们可以将 y^p*2^32 转换为 0.5*y^(p-32)*2^32 进行计算。

   系统实现该部分计算的函数是 decay_load:

   /* file: kernel/sched/pelt.c */
   /* 计算 val*y^n, 即val衰减n个周期后的值 */
   static u64 decay_load(u64 val, u64 n)
   {
       unsigned int local_n;
   
       /* 规定经过32*63个周期后衰减为0 */
       if (unlikely(n > LOAD_AVG_PERIOD * 63))
           return 0;
   
       /* after bounds checking we can collapse to 32-bit */
       local_n = n;
   
       /* LOAD_AVG_PERIOD=32, 这里将结果val右移 n=local_n/32 位，就是乘以n个0.5, 也就是乘以n个y^32 */
       if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
           val >>= local_n / LOAD_AVG_PERIOD;
           local_n %= LOAD_AVG_PERIOD;
       }
   
       /* 借助数组 runnable_avg_yN_inv 计算出最后的值 */
       val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
       return val;
   }

2. L1 = d1*y^p + 1024 * (y^(p-1) + y^(p-2) + ... + y) + d3 这里我们详细讨论 1024 * (y^(p-1) + y^(p-2) + ... + y) 这部分数列的计算方式，该部分的推导如下图所示：

   等比数列的求和公式为： S = a(1-q^n)/(1-y), 因此级数 yp 的和式为：(1-yn)/(1-y), 当n趋近于无穷时，结果为 1/(1-y), 我们知道 y32 = 0.5, 因此系统可以提前将 1024/(1-y) 的值计算出来，该值保存在宏 LOAD_AVG_MAX 中：

   /* file: kernel/sched/sched-pelt.h */
   #define LOAD_AVG_MAX 47742

   另外 y^p * 1024/(1-y) 就是将 LOAD_AVG_MAX 衰减p次，可以调用前文介绍过的函数 decay_load 来完成计算。因此整个数列的和为： LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024.

   整个L1 的计算函数是 __accumulate_pelt_segments:

   /* file: kernel/sched/pelt.c */
   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
        *
        *                        inf
        * LOAD_AVG_MAX = 1024 * \Sum y^n, 即等比数列求和，n趋近于无穷时的情况
        *                        n=0
        *
        * LOAD_AVG_MAX 通过文件 ~Documentation/scheduler/sched-pelt.c
        中的代码在编译时生成
       */
       c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;
   
       return c1 + c2 + c3;
   }

   其中c1 = d1*yp, c3 = d3, 而参数 periods 就是上图中的 p=delta/1024.

理解了上面的逻辑之后，我们再来看累计负载的函数 accumulate_sum:

/* file: kernel/sched/pelt.c */
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;

    /* 为什么需要加上sa->period_contrib?
     * 因为在计算delta时，使用的是now - sa->last_update_time,
     *
     而sa->last_update_time记录的是上次更新负载的时间点。sa->period_contrib表示上次更新负载时，当前period中的那部分时间，即这次更新时，该时间会是上图中的d3.因此这里将其加到delta上去，以方便后续计算periods与当前的d3
     * */
    delta += sa->period_contrib;
    periods = delta / 1024; /* A period is 1024us (~1ms) */

    /*
     * Step 1: decay old *_sum if we crossed period boundaries.
     */
    if (periods) {
        /* 根据 periods
           对之前累计的负载进行衰减，之前累计的负载既上一次更新负载的那个时间点记录下来的负载，距当前可能已经过了很多个周期了
           * 一个周期就是 1ms, 这里将其换算成1024us, 以方便运算 */
        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此时为当前周期的时间量，即注释中标注的d3由于前面已经把前一次更新负载时当时的d3加到了delta中，因此这里计算本次的d3就很简单了
        */
        delta %= 1024;
        if (load) {
            contrib =
                __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta);
        }
    }
    /* 此时的delta就是上图中的d3 */
    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;
}

该函数就是前面所讨论过的整个负载算法的实现。