• linux PELT算法中的load计算

    滑窗平均的累加计算

    权重y按滑窗距离衰减，y^32 = 0.5，也就是经历32个周期将衰减一半的权重，假设本周期值是Ｖ，本周期的加权累加值为Ｖx，则：

    一个完整周期是T，给一个基础值1024

    T = 1024 \\ V_x =T*V×\left \{\frac{(p_1-p_0)}{T}y^{p_3-p_1}+1\sum_{n=1}^{\frac{T}{p_2-p_1}} y^n + (\frac{p_3-p_2}{T})y^{p_1-p_1}\right \} \\ V_{sum}=V_0+V_x \\ V_{avg} = \frac{V_{sum}}{T\times[\sum_{n=0}^{\infty}y^n + ({p3-p2})]}

    其中

    \sum_{0}^{\infty }y^n = \frac{1-y^{\infty}}{1-y}= \frac{1}{1-0.5^\frac{1}{32} } =46 \\ \sum_{1}^{p2-p1} y^n= \sum_{0}^{\infty}y^n-\sum_{p2-p1}^{\infty}y^n-y^0

    Group entity share 的计算

    一个entity 的share值指它在计算runqueue上的load时（load_avg）赋予的权重，这个权重用它所在的group的对应cpu上分得的share值来表示（group 在每个cpu上都有一个runqueue，cpu上分得的share用runqueue的share来表示）

    runqueue 的 load weight计算，用avg更合适，因为它比实时的weight更稳定，但由于avg的启动比较慢，在极端的场景要保证与用weight来表示的权重一致。例如组内cpu全idle突然启动一个task的场景，这相当于一个只有一个cpu的场景，需要让avg得到的值和单cpu时的值一致，即：

    \frac{Share*W_{avg(rq)}}{\sum W_{avg(rq)}} \rightarrow \frac{Share*W_{rq}}{\sum W_{rq}}

    于是用一个近似的形式来拟合：

     \frac{Share*W_{rq}}{\sum W_{avg(rq)}-W_{avg(rq)}+W_{rq}}

    考虑到Wrq=0时可能有除0问题，分母变为

    \sum W_{avg(rq)}-W_{avg(rq)}+max(W_{avg(rq)},W_{rq})

    Entity 与 runqueue 在 load 计算上的区别

    block 的 entity 虽然不在 cpu 的 runqueue 上了，但依然在 cfs runqueue 上，只是 load 会以 0 的值对窗口加权。sleep 时间久了，entity 对应的 load avg 会越来越小。

    entity 有两种：task，group

    task

    load sum： 是 runnable 的时间加权和

    load avg： 是 load sum × 瞬时权值/ 所有时间窗口加权值

    所有时间窗口加权值即前面提过的：

    {\sum_{n=0}^{\infty}y^n + (p3-p2)}

    task blocking 时，瞬时值是 0, running 时瞬时值由 nice 值决定，瞬时值与 nice 值关系如下：

    1. const int sched_prio_to_weight[40] = {
    2.  /* -20 */     88761,     71755,     56483,     46273,     36291,
    3.  /* -15 */     29154,     23254,     18705,     14949,     11916,
    4.  /* -10 */      9548,      7620,      6100,      4904,      3906,
    5.  /*  -5 */      3121,      2501,      1991,      1586,      1277,
    6.  /*   0 */      1024,       820,       655,       526,       423,
    7.  /*   5 */       335,       272,       215,       172,       137,
    8.  /*  10 */       110,        87,        70,        56,        45,
    9.  /*  15 */        36,        29,        23,        18,        15,
    10. };

    group entity

    一个 group entity 对应一个　group 中某个 cpu 上的 run queue

    load sum ： 有一个任务在 running 状态的时间加权和

    load avg ： entity对应cfs runqueue分到的share值 * load_sum / 所有时间窗口加权值

    cfs runqueue分到的share值是上面提到的：

    \frac{Share*W_{rq}}{\sum_{rq.in.group} W_{avg(rq)}-W_{avg(rq)}+max(W_{avg(rq)},W_{rq})}

    runqueue

    load sum：runqueue 中每个 entity 的 load sum * entity 的权重的和

    load avg：runqueue 中每个 entity 的 load avg 的和（load avg 已经被加权过了，不用再重新加权）

    指标的更新

    主要分析下update_curr、update_load_avg、update_cfs_group三个函数

    update_curr 主要更新当前任务绑定的cpu的时长，包括：

    １、task本身的物理时长（sum_exec_runtime）和虚拟时长（vruntime）

    ２、每层cpu的物理时长（每层task->cgroups->subsys(cpuacct_cgrp_id)->css）

    ３、上层group的cpu时长（task->cgroups->dfl_cgrp->self.parent->rstat_cpu->bstat.cputime.sum_exec_runtime）

    ４、task作在runqueue的最小时间（min_vruntime）和剩余时长（runtime_remaining）

    update_load_avg　主要更新load相关的load, runnable, util 指标，并连带修改其所在的group

    有三种情况：添加entity，移除entity，更新group

    １、首先更新该entity 与操作runqueue的指标，如果entity是group，它的load_avg需要包含从下层递归累积上来的runtime（update_tg_load_avg）

    ２、这之后就可以根据相应的情况来算entity对它所在的runqueue的影响了，有两方面：一方面为runqueue加或减其贡献的指标，另一方面，它所在的runqueue的tg_load_avg_contrib变了，会影响到它所在的runqueue在整个group中的权重）

    update_cfs_group

    对于group entity，它绑定的runqueue的load变了，需要根据该group各cpu的runqueue的贡献值重新计算这个group entity 的权值

  • 相关阅读:
    5分钟生成10条短视频,AI重构电商营销
    浅谈“天线和通信历史“
    数据标准化算法介绍—数据建模工具
    Resin反序列化链分析
    java 特点了解及 JDK 初谈（程序员必看！）
    项目：TCP在线云词典
    服务器租用多少钱一年？
    第十四届蓝桥杯第二期模拟赛题解
    【webrtc】IsNewerTimestamp 时间戳新旧比较及使用
    什么是架构基本概念和架构本质
  • 原文地址：https://blog.csdn.net/qq_37517281/article/details/134039766