# 2.7.3 负载追踪 - 计算负载

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

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

![](https://640510796-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Me-3_JXLYv-4hrEXyDb%2Fuploads%2FxKmwIBnIy5YenWfd46lY%2Fpelt_cross_periods.png?alt=media\&token=b7be00f3-1cbb-4a3c-a9be-39c9eff249dd)

其中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;
}
```

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