# 2.7.3 负载追踪 - 计算负载

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

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

![](/files/hkSmd0h46SaG0OxmAT7F)

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/load-trace/load-trace-calc.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.