Skip to main content
 首页 » 操作系统

Linux 调度器之CFS负载计算-1_PELT_不考虑CFS组调度和带宽控制

2022年07月19日25qq号

1. 负载结构描述

(1) 每个调度实体都有一个负载结构,用来跟踪调度实体对系统的负载贡献,定义如下:

struct sched_entity {  
    struct load_weight    load;   
    #ifdef CONFIG_SMP 
        struct sched_avg    avg; 
    #endif 
}; 
 
/* 
 * load_avg/util_avg 累积了一个无限几何系列(参见 kernel/sched/fair.c 中的 __update_load_avg())。 
 * 
 * load_avg 的定义:load_avg = runnable% * scale_load_down(load) 
 * 
 * 解释:runnable% 是 sched_entity 的 runnable 时间的占比。对于 cfs_rq 的,它是所有的 
 * runnable 和 blocked sched_entitiy 的 load_avg 总和。 
 * 
 * util_avg 的定义:util_avg = running% * SCHED_CAPACITY_SCALE 
 * 
 * 解释:running% 是一个 sched_entity 在 cpu 上 running 的时间占比。对于 cfs_rq 的, 
 * 它是所有的 runnable 和 blocked sched_entitiy 的 util_avg 的总和。 
 * 
 * load_avg 和 util_avg 不直接影响频率缩放和 CPU 算力缩放。 缩放是通过用于计算这些信号的 rq_clock_pelt 完成的(请参阅 update_rq_clock_pelt()) 
 * 
 * 注意,上述比率(runnable% 和 running%)本身在 [0, 1] 的范围内。 因此,为了进行定点算术,我们将它们按需要缩放到尽可能大的范围。  
 * 这由 util_avg 的 SCHED_CAPACITY_SCALE 反映。 
 * 
 * [溢出问题] 
 * 64 位 load_sum 可以有 4353082796 (=2^64/47742/88761) 个具有最高负载 (=88761) 的实体, 
 * 一直在一个 cfs_rq 上运行,并且不会溢出,因为数量已经达到 PID_MAX_LIMIT。也就是说64bit的溢出问题不用担心(88761为prio=100的cfs的weight, 
 * sched_prio_to_weight[0],47742是按PELT算法计算出的一直满跑计算出来的结果,#define LOAD_AVG_MAX 47742) 
 * 对于所有其他情况(包括 32 位内核),struct load_weight 的权重将在我们之前先溢出,因为: Max(load_avg) <= Max(load.weight) 
 * 因此考虑溢出问题是 load_weight 的责任。
* 意思是64位长度的 load_sum 值可以记录 2^64/4772/88761 个最大权重(优先级最高)且一直满跑的任务。
*/ struct sched_avg { u64 last_update_time; /* 上次负载更新时间,单位ns */ u64 load_sum; /* 负载贡献,累计runable和block衰减负载 */ u64 runnable_load_sum;/* runable状态负载贡献 */ u32 util_sum; /* running状态负载贡献,累计running衰减时间总和,是又移过10的 */ u32 period_contrib; /* 负载计算时,不足一个周期的部分 */ unsigned long load_avg; /* 平均负载,(load_sum*load->weight)/最大衰减值 */ unsigned long runnable_load_avg; /* runable 状态平均负载 */ unsigned long util_avg; /* running状态的比值,util_avg 的定义:util_avg = running% * SCHED_CAPACITY_SCALE */ struct util_est util_est; /* task唤醒的时候预估的负载 */ } /* * struct util_est - 估计 FAIR 任务的利用率(utilization) * @enqueued:task/cpu 的瞬时利用率估计 * @ewma:任务的指数加权移动平均 (EWMA) 利用率 * * 支持数据结构以跟踪 FAIR 任务利用率的指数加权移动平均值 (EWMA)。每次任务完成唤醒时,都会将新样本添加到移动平均值中。 * 选择样本的权重以使 EWMA 对任务工作负载的瞬态变化相对不敏感。 * * enqueued 属性对于 tasks 和 cpus 的含义略有不同: * - task:上次任务出队时任务的 util_avg * - cfs_rq:该 CPU 上每个 RUNNABLE 任务的 util_est.enqueued 总和。因此,任务(非cfs_rq)的 util_est.enqueued 表示该任务当前排队的 CPU 估计利用率的贡献。 * * 仅对于我们跟踪过去瞬时估计利用率的移动平均值的任务。这允许吸收其他周期性任务的利用率的零星下降。 */ struct util_est { unsigned int enqueued; unsigned int ewma; #define UTIL_EST_WEIGHT_SHIFT 2 } __attribute__((__aligned__(sizeof(u64)))); struct cfs_rq { ... /*挂入改cfs_rq的调度实体的负载权重之和*/ struct load_weight load; /*挂入改cfs_rq的调度实体的runnable weight之和*/ unsigned long runnable_weight; /* CFS load tracking PELT算法跟踪的该cfs_rq的平均负载和利用率 */ struct sched_avg avg; ... /* * 当一个任务退出或唤醒后迁移到其它cpu的时候,那么原本的cpu上的cfs_rq *上需要移除该任务带来的负载。由于持rq锁的问题,所以先把移除的负载记录 * 在这个成员中,适当的时机再更新之。 */ struct { raw_spinlock_t lock ____cacheline_aligned; /*remove_entity_load_avg中加1*/ int nr; /*remove_entity_load_avg中加上en的这个域*/ unsigned long load_avg; /*remove_entity_load_avg中加上en的这个域*/ unsigned long util_avg; /*remove_entity_load_avg中加上en的这个域*/ unsigned long runnable_sum; } removed; ... };

(2) 补充

调度实体 sched_entity 和 cfs_rq 都内嵌一个 shed_avg 结构。

最大衰减累加时间:进程在CPU上运行无限长时,根据 PELT 算法计算出的衰减值。当进程无限运行后,load_avg 总是无限接近进程权重值(load.weight)

对调度实体来说:load_sum=runnable_load_sum, load_avg=runnable_load_avg。对于CFS调度队列来说:load_sum = 整个队列负载 * 整个队列权重。

2. 负载更新函数

static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) //fair.c 
{ 
    u64 now = cfs_rq_clock_pelt(cfs_rq); 
    int decayed; //衰变的 
 
    /* 
     * Track task load average for carrying it to new CPU after migrated, and 
     * track group sched_entity load average for task_h_load calc in migration 
     */ 
    if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) { //应该是首次不进入 
        /* 更新调度实体负载 */ 
        __update_load_avg_se(now, cfs_rq, se); 
    } 
 
    /*更新CFS队列负载*/ 
    decayed  = update_cfs_rq_load_avg(now, cfs_rq); 
    decayed |= propagate_entity_load_avg(se); //若不使能CONFIG_FAIR_GROUP_SCHED函数只直接返回0 
 
    if (!se->avg.last_update_time && (flags & DO_ATTACH)) { 
        /* 
         * DO_ATTACH 表示是在 enqueue_entity() 的执行路径中。 
         * !last_update_time means 表示被迁移的 
         * 
         * 我们正在往一个新的CPU上enqueue task 
         */ 
        attach_entity_load_avg(cfs_rq, se, SCHED_CPUFREQ_MIGRATION); 
        update_tg_load_avg(cfs_rq, 0); //若不使能CONFIG_FAIR_GROUP_SCHED函数只直接返回0 
    } else if (decayed) { 
        cfs_rq_util_change(cfs_rq, 0); 
 
        if (flags & UPDATE_TG) 
            update_tg_load_avg(cfs_rq, 0); 
    } 
}

只要使能了 CONFIG_SMP 使用的就是这个函数,里面同时更新了调度实体和cfs_rq的负载,无论是否使用 WALT 负载跟踪算法。先从简单入,先不看 CONFIG_FAIR_GROUP_SCHED 和 CONFIG_CFS_BANDWIDTH 使能时使用的代码。

(1) update_load_avg 的主要执行过程如下:
a. 更新本层级sched entity的load avg(__update_load_avg_se)
b. 更新该se挂入的cfs rq的load avg(update_cfs_rq_load_avg)
c. 如果是group se,并且cfs--se层级结构有了调度实体的变化,那么需要处理向上传播的负载。在tick场景中,不需要这个传播过程。
d. 更新该层级task group的负载(update_tg_load_avg)。之所以计算task group的load avg,这个值后续会参与计算group se的load weight。


(2) 负载更新时机

        enqueue_entity //传参(cfs_rq, se, UPDATE_TG | DO_ATTACH) 
        dequeue_entity //传参(cfs_rq, se, UPDATE_TG) 
        set_next_entity //传参(cfs_rq, se, UPDATE_TG) 
        put_prev_entity //传参(cfs_rq, prev, 0) 
        entity_tick //传参(cfs_rq, curr, UPDATE_TG) 
        enqueue_task_fair //传参(cfs_rq, se, UPDATE_TG) 会和enqueue_entity中的更新重复吗? 
        dequeue_task_fair //传参(cfs_rq, se, UPDATE_TG) 
update_nohz_stats 
_nohz_idle_balance //if (idle != CPU_NEWLY_IDLE)时调用 
newidle_balance 
run_rebalance_domains 
    update_blocked_averages 
        __update_blocked_fair //传参(cfs_rq_of(se), se, 0) 
    detach_entity_cfs_rq 
    attach_entity_cfs_rq 
        propagate_entity_cfs_rq //传参(cfs_rq, se, UPDATE_TG) 
fair_sched_class.migrate_task_rq 
    migrate_task_rq_fair //if (p->on_rq == TASK_ON_RQ_MIGRATING)成立调用 
switched_from_fair //.switched_from回调,rt_mutex_setprio/__sched_setscheduler-->check_class_changed-->switched_from 
task_move_group_fair 
    detach_task_cfs_rq 
        detach_entity_cfs_rq //传参(cfs_rq, se, 0) 
        attach_entity_cfs_rq //传参(cfs_rq, se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD) 
    proc_sched_autogroup_set_nice 
cpu_legacy_files.write_u64 //回调函数,对应cpu cgroup的"shares"文件 
    cpu_shares_write_u64 //使能CONFIG_FAIR_GROUP_SCHED才有 
cpu_files.write_u64 //回调函数,对应cpu cgroup的"weight"文件 
    cpu_weight_write_u64 
cpu_files.write_s64 //回调函数,对应cpu cgroup的"weight.nice"文件 
    cpu_weight_nice_write_s64 
        sched_group_set_shares //传参(cfs_rq_of(se), se, UPDATE_TG) 
            update_load_avg

主要是任务入队列、出队列对应的时机调用,update_curr()中并没有调用。

4. 调度实体负载更新

int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se) //pelt.c 
{ 
    /* 
     * 返回真,表示经历了一个完整周期(1024us)。从传参可以看出,对 se->sa->load_sum 和 
     * se->sa->runnable_load_sum 是否衰减更新取决于其是否在cfs_rq队列上,对 se->sa->util_sum 
     * 是否衰减更新取决于其是否为正在运行的任务。 
     */ 
    if (___update_load_sum(now, &se->avg, !!se->on_rq, !!se->on_rq, cfs_rq->curr == se)) { 
        /*传参:(&se->avg, max(2, se->load.weight>>10), max(2, se->runnable_weight>>10))*/ 
        ___update_load_avg(&se->avg, se_weight(se), se_runnable(se)); 
        /*更新se->avg.util_est.enqueued*/ 
        cfs_se_util_change(&se->avg); 
        trace_pelt_se_tp(se); 
        return 1; 
    } 
 
    return 0; 
}

(1) ___update_load_sum 函数

/* 
 * 我们可以将可运行(runnable)平均值的历史贡献表示为几何级数的系数。 为此,我们将可运行(runnable)历史细分为大约 1ms (1024us) 的段;  
 * 标记发生在 N 毫秒前的为 p_N 的段,p_0 对应于当前周期,例如 
 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ... 
 *      p0            p1            p2 
 *     (now)        (~1ms ago)    (~2ms ago) 
 * 
 * 让 u_i 表示实体可运行的 p_i 分数。 
 * 
 * 然后我们指定分数 u_i 作为我们的系数,产生以下历史负载表示: 
 *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ... 
 * 我们根据合理的调度周期选择 y,固定: 
 *   y^32 = 0.5 
 * 这意味着大约 32 毫秒前 (u_32) 的负载对负载的贡献将是当前(u_0)的负载对负载的贡献的一半。 
 * 当一个周期“滚动”并且我们有新的 u_0 时,将先前的总和再次乘以 y 就可以了: 
 *   load_avg = u_0 + y*(u_0 + u_1*y + u_2*y^2 + ... ) 
 *               = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}] 
 */ 
/* 
 * update_load_avg调用传参:(now, &se->avg, !!se->on_rq, !!se->on_rq, cfs_rq->curr == se) 
 * 根据运行时间 delta 值,调用 accumulate_sum() 先将原负载进行衰减,然后计算出新负载,然后 
 * 再累加到衰减后的负载上。delta是经历了一个完整周期(就是加上上一次计算剩余的不足一个周期的 
 * sa->period_contrib部分后大于1024us)就返回1,否则返回0. 
 */ 
static __always_inline int ___update_load_sum(u64 now, struct sched_avg *sa, unsigned long load, unsigned long runnable, int running) //pelt.c 
{ 
    u64 delta; 
 
    delta = now - sa->last_update_time; 
    /*这只有时间反向增长的时候才可能发生,在翻滚后sched clock init时会不幸的发生*/ 
    if ((s64)delta < 0) { 
        sa->last_update_time = now; 
        return 0; 
    } 
 
    /*为了快速计数,以us为单位进行对比,这里大约地将1024ns转换为1us,小于1us直接退出 */ 
    delta >>= 10; 
    if (!delta) 
        return 0; 
 
    sa->last_update_time += delta << 10; //更新last_update_time,没有更新回delta 
 
    /* 
     * running 是 runnable (weight) 的一个子集,因此如果 runnable 被清理了,则无法设置 running。  
     * 但是在某些极端情况下,当前 se 已经 dequeue 了,但 cfs_rq->curr 仍然指向它。 这意味着权重 
     * 将为 0,但不会让此 sched_entity 运行,如果 cfs_rq 空闲,也会不为 cfs_rq 运行。 例如,这 
     * 发生在调用 update_blocked_averages() 的 idle_balance() 期间。 
     */ 
    if (!load) 
        runnable = running = 0; //若第一个参数传0,第二第三个参数也赋值为0 
 
    /* 
     * 现在我们知道我们通过了测量单位边界的判断。 *_avg 分两步累积: 
     * 第 1 步:自 last_update_time 累积 *_sum。 如果我们还没有跨越时期界限,那就结束吧。 
     */ 
    if (!accumulate_sum(delta, sa, load, runnable, running)) 
        return 0; 
 
    return 1; 
} 
 
 
/* 
 * 累加三个独立部分的总和; d1 上一个(不完整)周期的剩余时间,d2 整个周期的跨度,d3 是(不完整)当前周期的剩余部分。 
 * 
 *           d1          d2           d3 
 *           ^           ^            ^ 
 *           |           |            | 
 *         |<->|<----------------->|<--->| 
 * ... |---x---|------| ... |------|-----x (now) 
 * 
 *                           p-1 
 * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0 
 *                           n=1 
 * 
 *    = u y^p +                    (Step 1) 
 * 
 *                     p-1 
 *      d1 y^p + 1024 \Sum y^n + d3 y^0        (Step 2) 
 *                     n=1 
 */ 
/*此函数作用:先将原负载进行衰减,然后计算出新负载,然后再累加到衰减后的负载上*/ 
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,此时delta应该对应上面的d1+d2+d3的和,此时的delta的单位是us,在传入之前时间做差后右移10了 */ 
    u64 periods; 
 
    /* 这里加的是d1前面不足1个周期的部分(看来负载是按整周期计算的,不足一个周期的部分放在这里) */ 
    delta += sa->period_contrib; 
    periods = delta / 1024; /* A period is 1024us (~1ms) 除以1024将us转化为ms */ 
 
    /* 第 1 步:如果我们跨越了周期边界,则衰减旧的 *_sum。*/ 
    if (periods) { 
        /*这里只是将原来的负载衰减periods个周期*/ 
        sa->load_sum = decay_load(sa->load_sum, periods); //执行 sa->load_sum * y^periods 也就是对原负载进行衰减 
        sa->runnable_load_sum = decay_load(sa->runnable_load_sum, periods); //执行 sa->runnable_load_sum * y^periods 
        sa->util_sum = decay_load((u64)(sa->util_sum), periods); //执行 sa->util_sum * y^periods 
 
        /* Step 2 */ 
        /* 不足一个周期(1024us)的部分,就是d3,上面dalta加上了sa->period_contrib后使d1部分也凑足一个周期了, 
         * 所以delta %= 1024后是d3。1024 - sa->period_contrib 就是d1。  
         * __accumulate_pelt_segments的形参:(u64 periods, u32 d1, u32 d3) 
         */ 
        delta %= 1024; 
        contrib = __accumulate_pelt_segments(periods, 1024 - sa->period_contrib, delta); 
    } 
    /* 将本次运行的不足一个周期的部分赋值给sa->period_contrib,其单位是us */ 
    sa->period_contrib = delta; 
 
    /* __update_load_avg_se()传参传下来的手势bool值,!!se->on_rq。这里可以看出这三者的计算区别 */ 
    if (load) 
        sa->load_sum += load * contrib; 
    if (runnable) 
        sa->runnable_load_sum += runnable * contrib; 
    if (running) 
        sa->util_sum += contrib << SCHED_CAPACITY_SHIFT; //这里应该不应理解为将us又转换为ns,这些*_sum使用的contribute都是us为单位的,这里应该理解为scale_up好一点。 
 
    return periods; 
} 
 
static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3) //pelt.c 
{ 
    u32 c1, c2, c3 = d3; /* y^0 == 1 */ 
 
    /* 
     * c1 = d1 y^p 
     */ 
    /* 执行d1*y^periods, 这里是对d1多衰减一个周期的,看上图可知,d1应该衰减periods-1个周期。*/ 
    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 
     * 
     * 1024 表示满窗(1024us),c2是近似值,n越大结果就越小了,可以忽略不计了。 
     */ 
    c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024; 
 
    return c1 + c2 + c3; 
}

__update_load_avg_se 函数只在 update_load_avg 中调用。

(2) ___update_load_avg 函数

/*传参:(&se->avg, max(2, se->load.weight>>10), max(2, se->runnable_weight>>10))*/ 
static __always_inline void ___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable) //pelt.c 
{ 
    /*当前窗口负载(sa->period_contrib) + 所有历史负载(LOAD_AVG_MAX - 1024)最大值,可理解为此任务一会满跑的情况下PELT计算出来的时间衰减累积值*/ 
    u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib; 
 
    /* Step 2: update *_avg. *_avg = *_sum / divider */ 
    sa->load_avg = div_u64(load * sa->load_sum, divider); 
    sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider); 
    WRITE_ONCE(sa->util_avg, sa->util_sum / divider); //在sa->util_sum的计算时已经体现乘以1024了,因此除以的结果是 running% * 1024 
}

由上面函数可以看出,*_avg = 优先级对应的权重值  x  *_sum / divider。解释起来就是,权重*历史负载/历史负载最大值,也就是说一个任务若是一直运行(running + runnable),其load_avg就接近其权重值。这里说的这个权重值是优先级对应的sched_prio_to_weight[] 的值,而不是 se->load.weight,因为这个成员保存的是 scale_up(就是乘以1024) 后的权重值,需要除以1024才是。

(3) cfs_se_util_change 函数

/* 
 * 当任务出队时,如果其 util_avg 没有至少更新一次,则不应更新其估计利用率。 
 * 此标志用于将 util_avg 更新与 util_est 更新同步。 
 * 我们将此信息映射到出队时保存的利用率的 LSB 位(即 util_est.dequeued)。 
 */ 
#define UTIL_AVG_UNCHANGED 0x1 
 
static inline void cfs_se_util_change(struct sched_avg *avg) 
{ 
    unsigned int enqueued; 
 
    if (!sched_feat(UTIL_EST)) //默认为true 
        return; 
 
    /* Avoid store if the flag has been already set */ 
    enqueued = avg->util_est.enqueued; 
    if (!(enqueued & UTIL_AVG_UNCHANGED)) //使用最后一bit来保持同步 
        return; 
 
    /* Reset flag to report util_avg has been updated */ 
    enqueued &= ~UTIL_AVG_UNCHANGED; 
    WRITE_ONCE(avg->util_est.enqueued, enqueued); 
}

更新 avg->util_est.enqueued,其最后一bit用来做同步。

5. cfs_rq 负载更新

/** 
 * update_cfs_rq_load_avg - 更新 cfs_rq 的负载(load)/利用率(util)平均值 
 * @now:当前时间,根据 cfs_rq_clock_pelt() 
 * @cfs_rq: 要更新的 cfs_rq  
 * 
 * cfs_rq avg 是其所有实体(blocked 和 runnable)avg 的直接总和。直接的 
 * 推论是必须附加所有(公平的)任务,请参阅 post_init_entity_util_avg()。 
 * 例如,cfs_rq->avg 用于 task_h_load() 和 update_cfs_share()。 
 * 如果负载衰减或我们移除了负载,则返回 true。 
 * 由于这两个条件都表明 cfs_rq->avg.load 发生了变化,我们应该在此函数返回 true 时调用 update_tg_load_avg()。 
 */ 
static inline int update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq) //fair.c 
{ 
    unsigned long removed_load = 0, removed_util = 0, removed_runnable_sum = 0; 
    struct sched_avg *sa = &cfs_rq->avg; 
    int decayed = 0; 
 
    if (cfs_rq->removed.nr) { 
        unsigned long r; 
        u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib; //divider恒这个计算公式 
 
        raw_spin_lock(&cfs_rq->removed.lock); 
        swap(cfs_rq->removed.util_avg, removed_util); //数值交换,为啥是交换而不是直接赋值? 
        swap(cfs_rq->removed.load_avg, removed_load); 
        swap(cfs_rq->removed.runnable_sum, removed_runnable_sum); 
        cfs_rq->removed.nr = 0; 
        raw_spin_unlock(&cfs_rq->removed.lock); 
 
        r = removed_load; 
        sub_positive(&sa->load_avg, r); //if(arg1-arg2 > arg1) arg1=0; 说明arg2是个负数(溢出) 
        sub_positive(&sa->load_sum, r * divider); 
 
        r = removed_util; 
        sub_positive(&sa->util_avg, r); 
        sub_positive(&sa->util_sum, r * divider); 
 
        add_tg_cfs_propagate(cfs_rq, -(long)removed_runnable_sum); //不使能CONFIG_FAIR_GROUP_SCHED就是空函数 
 
        decayed = 1; 
    } 
 
    decayed |= __update_load_avg_cfs_rq(now, cfs_rq); 
 
#ifndef CONFIG_64BIT 
    smp_wmb(); 
    cfs_rq->load_last_update_time_copy = sa->last_update_time; 
#endif 
 
    /*delta满足一个周期或cfs_rq->removed.nr不为0就返回1*/ 
    return decayed; 
} 
 
int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq) 
{ 
    /*传参:(now, &cfs_rq->avg, max(2, cfs_rq->load.weight>>10), max(2, cfs_rq->runnable_weight>>10), cfs_rq->curr != NULL)*/ 
    if (___update_load_sum(now, &cfs_rq->avg, scale_load_down(cfs_rq->load.weight), scale_load_down(cfs_rq->runnable_weight), cfs_rq->curr != NULL)) { 
        /*由 *_sum 计算 *_avg 取公式:*_avg  = *_sum / divider*/ 
        ___update_load_avg(&cfs_rq->avg, 1, 1); 
        trace_pelt_cfs_tp(cfs_rq); 
        return 1; 
    } 
 
    return 0; 
}

cfs_rq 的负载更新函数和 se 的调用的是同一个,只不过传参不同,se 的传参为 bool 值。cfs_rq 传的是数值,最终在计算负载的时候是累加此值乘以这段时间的负载贡献的。不太明白 #####

(1) update_cfs_rq_load_avg 的调用路径

//调用路径上面梳理了 
update_load_avg 
    update_cfs_rq_load_avg 
 
    find_busiest_group 
        update_sd_lb_stats 
            update_sg_lb_stats 
init_sched_fair_class //open_softirq(SCHED_SOFTIRQ, run_rebalance_domains); 在软中断上下文执行 
    run_rebalance_domains 
        nohz_idle_balance 
balance_fair 
pick_next_task_fair //cfs_rq上没有任务可供pick的时候 
    newidle_balance 
        nohz_newidle_balance 
            _nohz_idle_balance 
                update_nohz_stats 
                _nohz_idle_balance //if (idle != CPU_NEWLY_IDLE)才调用 
                newidle_balance 
                run_rebalance_domains 
                    update_blocked_averages 
                        __update_blocked_fair //CPU进入idle状态,那么意味着该CPU上的 load avg的负载都是blocked load,需要不间断进行衰减。 
                            update_cfs_rq_load_avg

update_cfs_rq_load_avg 除了在 update_load_avg 函数中调用外,主要是在负载均衡路径中直接调用这个函数。

6. sched_pelt 中成员的计算

sched_pelt.h 中的内容来自 Documentation/scheduler/sched-pelt.c 计算得到的

kernel/msm-5.4/Documentation/scheduler$ gcc sched-pelt.c -o pp -lm  
kernel/msm-5.4/Documentation/scheduler$ ./pp 
/* Generated by Documentation/scheduler/sched-pelt; do not modify. */ 
 
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,  
}; 
 
#define LOAD_AVG_PERIOD 32 
#define LOAD_AVG_MAX 47742

(1) runnable_avg_yN_inv 数组

runnable_avg_yN_inv[i] 的值为( (1UL<<32)-1) * y^i,其中 y = pow(0.5, 1/(double)LOAD_AVG_PERIOD),就是0.5开32次方就是y,y的32次方等于0.5,对应负载经历32个周期后(一个周期1024us~=1ms) 负载衰减到原来的1/2。runnable_avg_yN_inv[] 中一共有 LOAD_AVG_PERIOD 个元素。

(2) LOAD_AVG_PERIOD

y 的 LOAD_AVG_PERIOD 次方等于1/2,1/2 开 LOAD_AVG_PERIOD 次方等于y。

(3) LOAD_AVG_MAX

按照 PELT 负载计算算法能得出的最大负载的最大值,也就是当一个任务一直无限运行,所有周期全满窗,其负载可以无限接近 LOAD_AVG_PERIOD 值,其对于的计算公式为:

/* 
 *                            inf 
 *    LOAD_AVG_MAX  = 1024 * \Sum y^n 
 *                            n=0  
 */

这个宏的值是 Documentation/scheduler/sched-pelt.c中 calc_converged_max() 计算得出的,其只计算了320个窗口(inf取320为47741.4),若inf取10000000(约单次满窗运行10000秒),得出的就是 47788

注:只要满足上面规律,LOAD_AVG_PERIOD 是可以该小的,比如 WALT 负载更新算法中就将其改小为8了。

7. 可以 cat /proc/<pid>/sched 看各个成员的状态,可以设置优先级和绑核,在系统idle状态下进行观察。

8. RT 任务的负载统计与权重无关,所以RT任务封装的负载统计 ___update_load_avg() 函数中权重和runnable的权重传的都是1,对于cfs的group se传的也是1,对于普通cfs任务的传的是其优先级对应的权重值。

9. MTK平台下做个实验

(1) 运行三个死循环 
# while true; do let i=i+1; done & 
[1] 25805# while true; do let i=i+1; done & 
[2] 25806# while true; do let i=i+1; done & 
[3] 25807 
 
(2) 将三个死循环绑定在CPU6上 
taskset -p 40 25805 
taskset -p 40 25806 
taskset -p 40 25807 
 
(3) 优先级分别设置为 100,120,139 
renice -n -20 -p 25805 
renice -n 19 -p 25807 
 
(4) 运行一段时间后cat 
# cat /proc/25805/sched 
se.load.weight                               :             90891264 //90891264 = 88761 * 1024,88761就是100优先级对应的权重值,也就是 sched_prio_to_weight[0] 的值,对权重还进行了scale_up() 
se.avg.load_sum                              :           3335661917 //PELT算法下,这个为 Sum(权重 * 运行时间),由于在不断对历史的load_sum做衰减,100优先级的任务一直满跑,其最终会趋于一个定值,88761 * 47742 = 4237627662 
se.avg.util_sum                              :             34445249 //PELT算法下,为scale_up后的运行时间的衰减累加值,与优先级无关,只与delta时间有关,其最终会趋向一个定值:1024 * 47742 = 48887808,说明见"注1" 
se.avg.load_avg                              :                71239 //一直跑,就会接近其优先级对应的权重值,优先级和权重的对应关系见 sched_prio_to_weight[] 
se.avg.util_avg                              :                  735 //是一个scale_up(就是<<10)后的运行时间的比值,定义为 running% * 1024,最大值为1024,此时其负载为 735/1024 = 71.8%。WALT算法中只要满跑,此域瞬间就达到1024 
se.avg.last_update_time                      :       23338900368384 
se.avg.util_est.ewma                         :                  320 
se.avg.util_est.enqueued                     :                  732 
policy                                       :                    0 
prio                                         :                  100

# cat /proc/25806/sched se.load.weight : 1048576 //1048576 = 1024 * 1024,1024为120优先级对应的weight, se.avg.load_sum : 38715383 se.avg.util_sum : 2760254 se.avg.load_avg : 822 se.avg.util_avg : 58 se.avg.last_update_time : 23343228391424 se.avg.util_est.ewma : 0 se.avg.util_est.enqueued : 0 policy : 0 prio : 120

# cat /proc/25807/sched se.load.weight : 15360 //15360 = 15 * 1024,15为139优先级对应的weight, se.avg.load_sum : 573337 se.avg.util_sum : 2810605 se.avg.load_avg : 12 se.avg.util_avg : 58 se.avg.last_update_time : 23326280420352 se.avg.util_est.ewma : 0 se.avg.util_est.enqueued : 0 policy : 0 prio : 139

注1:根据util_avg 的定义:util_avg = running% * SCHED_CAPACITY_SCALE,和 ___update_load_avg() 中 WRITE_ONCE(sa->util_avg, sa->util_sum / divider); 其中 divider 取最大值为 47742,util_avg 取最大值为 1024,因此 util_sum 的最大值只能是 1024 * 47742 = 48887808,这个是scale_up的,也就是乘以1024后的值。

注2:若任务一直跑,其se.avg.load_avg就会接近其优先级对应的权重值,但是反过来并不成立,比如任务先一直运行一段时间,然后sleeping或被冻结住,此时其load_avg还没来得及更新,还是会一直保持接近其权重值,可以通过cat /proc/<PID>/status 看线程的状态来确定。

10. 总结

1. se.avg.load_sum:PELT算法下,这个为 Sum(权重 * 运行时间),由于在不断对历史的 load_sum 做衰减,100优先级的任务一直满跑,其最终会趋于一个定值,sched_prio_to_weight[0] * LOAD_AVG_MAX,若是取 q = 0.5^(1/32), 最大值也就是 88761 * 47742 = 4237627662

2. load_avg 的定义:load_avg = runnable% * scale_load_down(load),更新见 ___update_load_avg(),计算公式简化为:runnable time / LOAD_AVG_MAX * sched_prio_to_weight[nice]。se.load.weight 是 sched_prio_to_weight[nice] 的值 scale_up 后的,也就是乘以1024后的。一般 scale_load_down(load) 传的load是scale_up后的,scale_down后就是sched_prio_to_weight[nice] 的值。若一个任务无限运行,其 load_avg 就等于其权重值,也就是 sched_prio_to_weight[nice] 的值。

3. util_avg 的定义:util_avg = running% * SCHED_CAPACITY_SCALE,更新见 ___update_load_avg(),计算公式简化为:running time / LOAD_AVG_MAX * SCHED_CAPACITY_SCALE。

补充

(1) RT 任务的负载统计与权重无关,所以RT任务封装的负载统计 ___update_load_avg() 函数中权重和runnable的权重传的都是1,对于cfs的group se传的也是1,对于普通cfs任务的传的是其优先级对应的权重值。

(2) MTK平台测试,一个优先级为100的cfs进程,死循环,跑在大核上其 PELT算法下 se.avg.util_avg 为788,跑在小核上为 220。正常应该为1024的,和 CPU 算力cpu_capacity文件数值也不匹配。原因是受到CPU算力影响,而且会随着CPU频点进行scale。

(3) load_sum 考虑了 running 和 runnable 时间,而 util_sum 只考虑了 running 时间。

(4) 5.10 GKI后的内核支持半衰期窗口个数配置为8还是32,通过如下方式配置

/* 
chosen: chosen { 
    bootargs = "pelt=8 ..."; 
}; 
*/ 
early_param("pelt", set_pelt); //pelt.c

本文参考链接:https://www.cnblogs.com/hellokitty2/p/15335189.html