调度器12—PELT算法中的预估利用率 util_est

基于MTK Linux-4.14

一、PELT 中预估利用率简介

由于在 PELT 算法下任务的 util 增加减少的都比较慢，对于长时间休眠后的重负载任务，其 util 增加的比较慢，导致不能及时触发提频和迁核。为了补救 PELT 的这一缺陷，引入了预估负载。在任务(休眠)出队列时更新任务的预估负载，当任务入队列时将出队列时的负载加到cfs_rq的预估负载上。

二、PELT 中预估利用率的赋值和使用

1. 赋值

(1) 调度实体 dequeue 时

static void util_est_dequeue(struct cfs_rq *cfs_rq, struct task_struct *p, bool task_sleep) //fair.c
{
    if (!sched_feat(UTIL_EST))
        return;

    ue.enqueued = 0; //若是没有任务，默认就是0了
    if (cfs_rq->nr_running) {
        ue.enqueued  = cfs_rq->avg.util_est.enqueued;
        //保证不要被减成负数了，enqueue任务是或上，然后cfs_se_util_change/util_est_dequeue中去除
        ue.enqueued -= min_t(unsigned int, ue.enqueued, (_task_util_est(p) | UTIL_AVG_UNCHANGED));
    }
    WRITE_ONCE(cfs_rq->avg.util_est.enqueued, ue.enqueued); //dequeue时将任务的util_est从rq的util_est中移除
    trace_sched_util_est_cpu(cpu_of(rq_of(cfs_rq)), cfs_rq);

　　if (!task_sleep) //只有因为睡眠而触发的任务切换，task_sleep判断才是真。也就是说只有是任务睡眠才更新，被强占不更新。
　　　　return;

    ...
    /* 如果 PELT 值自入队时间以来未更改，请跳过 util_est 更新 */
    ue = p->se.avg.util_est; //对ue做了赋值更改，此时是任务的了。
    if (ue.enqueued & UTIL_AVG_UNCHANGED) //enqueue任务是或上，然后cfs_se_util_change/util_est_dequeue中去除
        return;

    /*当任务的 EWMA 已经接近其上次激活值约 1% 时，跳过更新任务的估计利用率 */
    ue.enqueued = (task_util(p) | UTIL_AVG_UNCHANGED); //p->se.avg.util_avg，enqueued 成员赋值的是此次睡眠时任务的实际 util
    last_ewma_diff = ue.enqueued - ue.ewma;
    if (within_margin(last_ewma_diff, (SCHED_CAPACITY_SCALE / 100)))
        return;

    /* ue.ewma的计算公式：ewma(t) = w * task_util(p) + (1-w) * ewma(t-1) ==> 整理后：w * (last_ewma_diff + ewma(t-1) / w),w 取1/4 */
    ue.ewma <<= UTIL_EST_WEIGHT_SHIFT;
    ue.ewma  += last_ewma_diff;
    ue.ewma >>= UTIL_EST_WEIGHT_SHIFT;
    WRITE_ONCE(p->se.avg.util_est, ue); //写回给任务，也就是说任务在出队列时更新其 p->se.avg.util_est.enqueued 和 ewma

    trace_sched_util_est_task(p, &p->se.avg);
}

先将此任务的 util_est 从 cfs_rq 的 util_est 删除，然后再更新任务的 util_est。

调用路径：

dequeue_task_fair //fair.c，dequeue的是task不是entity，最后调用
    util_est_dequeue

当任务 dequeue 时，先将其 ue.enqueued 从 cfs_rq->avg.util_est.enqueued 中移除，然后再更新任务的 util_est。

(2) 调度实体 enqueue 时

static inline void util_est_enqueue(struct cfs_rq *cfs_rq, struct task_struct *p) //fair.c
{
    if (!sched_feat(UTIL_EST))
        return;

    /* Update root cfs_rq's estimated utilization */
    enqueued  = cfs_rq->avg.util_est.enqueued;
    enqueued += (_task_util_est(p) | UTIL_AVG_UNCHANGED); //enqueue任务是或上，然后cfs_se_util_change中去除
    WRITE_ONCE(cfs_rq->avg.util_est.enqueued, enqueued);

    trace_sched_util_est_task(p, &p->se.avg);
    trace_sched_util_est_cpu(cpu_of(rq_of(cfs_rq)), cfs_rq);
}

调用路径：

enqueue_task_fair //fair.c 最先调用的
    util_est_enqueue

当调度实体 enqueue 时，直接将其 util_est 加到 cfs_rq 的 util_est 中。

(3) util_change 中清除标志位

static inline void cfs_se_util_change(struct sched_avg *avg)
{
    if (!sched_feat(UTIL_EST))
        return;

    /* Avoid store if the flag has been already set */
    enqueued = avg->util_est.enqueued;
    if (!(enqueued & UTIL_AVG_UNCHANGED)) //没有这个标志位直接退出
        return;

    /* Reset flag to report util_avg has been updated */
    enqueued &= ~UTIL_AVG_UNCHANGED; //从数值中清除这个标志位
    WRITE_ONCE(avg->util_est.enqueued, enqueued);
}

调用路径：

enqueue_task_fair
unthrottle_cfs_rq
    enqueue_entity //fair.c 无条件条调用
dequeue_task_fair
throttle_cfs_rq
    dequeue_entity //fair.c 无条件条调用
    set_next_entity //fair.c 只有se->on_rq才调用，选一个cfs任务去运行
    put_prev_entity //fair.c 只有se->on_rq才调用，取消一个在运行的cfs任务
    entity_tick //fair.c 在scheduler_tick()中对正在运行的任务以Hz为频度更新负载
    enqueue_task_fair //fair.c 无条件调用
    dequeue_task_fair //fair.c 无条件调用
    update_blocked_averages //fair.c 负载均衡路径
    propagate_entity_cfs_rq //fair.c fair group sched里面的
    detach_entity_cfs_rq //fair.c 无条件条调用
    attach_entity_cfs_rq //fair.c 无条件条调用
    sched_group_set_shares //fair.c fair group sched cgroup分组
        update_load_avg //fair.c
            __update_load_avg_se //fair.c
                cfs_se_util_change(&se->avg) //传参是se的sched_avg

这个函数只是将 UTIL_AVG_UNCHANGED 标志位清除掉，这个标志位是 enqueue_entity 时或上的，在 dequeue_task_fair 和 cfs_se_util_change 中清除。在 util_est_enqueue 中已经将任务的预估负载加到 cfs_rq 上了，在这之后的任何时刻应该都可以清除标志位。

2. 使用

(1) 任务的预估负载的获取

static inline unsigned long _task_util_est(struct task_struct *p)
{
    struct util_est ue = READ_ONCE(p->se.avg.util_est);
    return max(ue.ewma, ue.enqueued); //兼顾实时性和休眠的历史负载，取二者之间的较大值，rwma记录了历史衰减。
}

unsigned long task_util_est(struct task_struct *p)
{
    return max(task_util(p), _task_util_est(p));
}

调用路径：

update_sg_util //eas_plus.c
find_energy_efficient_cpu_enhanced //eas_plus.c
schedtune_task_margin //fair.c
boosted_task_util //fair.c
find_best_target  //fair.c
get_eenv //fair.c
find_energy_efficient_cpu //fair.c
wake_energy
select_task_rq_fair //fair.c 这里对util_est进行trace
load_balance //fair.c
calc_cpu_util //sched_ctl.c
    task_util_est

这些路径下都是直接获取带有预估的util数据。

(2) CPU的预估负载的获取

static inline unsigned long cpu_util(int cpu)
{
    struct cfs_rq *cfs_rq;
    unsigned int util;

    /* WLAT算法下CPU的util */
#ifdef CONFIG_SCHED_WALT
    if (likely(!walt_disabled && sysctl_sched_use_walt_cpu_util)) {
        u64 walt_cpu_util = cpu_rq(cpu)->cumulative_runnable_avg; //walt算法下返回的是这个，是不使用预估负载的

        walt_cpu_util <<= SCHED_CAPACITY_SHIFT;
        do_div(walt_cpu_util, walt_ravg_window);

        return min_t(unsigned long, walt_cpu_util, capacity_orig_of(cpu));
    }
#endif

    /* PELT算法下CPU的util */
    cfs_rq = &cpu_rq(cpu)->cfs;
    util = READ_ONCE(cfs_rq->avg.util_avg);

    if (sched_feat(UTIL_EST))
        util = max(util, READ_ONCE(cfs_rq->avg.util_est.enqueued)); //取cfs_rq的util和预估util的较大值, 此处获取cpu的util直接使用的是enqueued成员，更具有实时性。

    return min_t(unsigned long, util, capacity_orig_of(cpu));
}

调用路径：

    show_eas_info_attr //eas_plus.c 接口/sys/devices/system/cpu/eas/info 打印的util= 241(on)，on表示此cpu是否onlline
        show_cpu_capacity //eas_plus.c
            get_cpu_util //fair.c
    sugov_update_single/sugov_update_shared //cpufreq_schedutil.c 调频接口函数
        sugov_get_util //cpufreq_schedutil.c 获取的是这个util触发调频的
            boosted_cpu_util //fair.c stune还可以对一个cpu进行boost, TODO：看
                cpu_util_freq //fair.c
                cpu_util_without //fair.c 不包括任务p的cpu的util，通常是在任务迁移、唤醒选核时使用
find_energy_efficient_cpu //fair.c 选择能效最高的cpu    
    select_energy_cpu_idx //fair.c
        compute_energy //fair.c
            calc_sg_energy //fair.c
                group_idle_state //fair.c 计算此sched_group中所有cpu的cpu_util只和
        enqueue_task_fair
        task_tick_fair
            update_overutilized_status //fair.c
    find_busiest_group //fair.c 负载均衡时查找最繁忙的组
        update_sd_lb_stats //fair.c
            update_sg_lb_stats //fair.c
        load_balance //fair.c
            need_active_balance //fair.c
        SELECT_TASK_RQ_FAIR //fair.c
            nohz_kick_needed //fair.c no_hz相关
            trigger_load_balance //fair.c
                cpu_overutilized //fair.c 主要是负载均衡和迁核功能中调用
                update_sg_lb_stats //fair.c 对一个组内的sg_lb_stats.group_util进行累加赋值
                    cpu_util(cpu)