Skip to main content
 首页 » 操作系统

Linux 调度器之PELT算法中的预估利用率 util_est

2022年07月19日24kerrycode

基于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。也就是说 cfs_rq->avg.util_est.enqueued 只是enqueue到rq上的任务的util_est之和(runnable+runing).

(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)

触发调频使用的是 boosted_cpu_util() 获取的cpu util,任务迁移和均衡使用的是 cpu_overutilized() 进行判断的。


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