Skip to main content
 首页 » 操作系统

Linux 调度器之CFS任务选核

2022年07月19日29www_RR

一、select_task_rq_fair()函数

CFS任务选核最终都是要走 select_task_rq_fair() 函数,三种CFS选核路径如下:

try_to_wake_up //core.c 
    select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags); //唤醒选核路径 
 
wake_up_new_task //core.c 
    select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0); //fork选核路径 
 
sched_exec //core.c 
    select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0); //exec选核路径

对比可以看到,只有任务唤醒选核才传了wake_flags,可能选择sync唤醒。sched_domain 的flag中是否包含 SD_BALANCE_XX 可以通过下面方法查看:

/proc/sys/kernel/sched_domain # find ./ -name flags | xargs cat 
SD_BALANCE_NEWIDLE SD_BALANCE_EXEC SD_BALANCE_FORK SD_WAKE_AFFINE SD_SHARE_PKG_RESOURCES //MC 
SD_BALANCE_NEWIDLE SD_BALANCE_EXEC SD_BALANCE_FORK SD_WAKE_AFFINE SD_ASYM_CPUCAPACITY SD_PREFER_SIBLING //DIE

可以看出对于嵌入式这种大小核的Arm64架构中,MC和DIE都没有 SD_BALANCE_WAKE 这个标志。

函数解读:

/* 
 * select_task_rq_fair: Select target runqueue for the waking task in domains 
 * that have the 'sd_flag' flag set. In practice, this is SD_BALANCE_WAKE, 
 * SD_BALANCE_FORK, or SD_BALANCE_EXEC. 
 * 
 * Balances load by selecting the idlest CPU in the idlest group, or under 
 * certain conditions an idle sibling CPU if the domain has SD_WAKE_AFFINE set. 
 * 
 * Returns the target CPU number. 
 * 
 * preempt must be disabled. 
 */ 
/* 
 * 传参: 
 * p: 待选核任务 
 * prev_cpu:任务之前运行的cpu 
 * sd_flag: 在包含此标志的sd中为任务选核,可取值 SD_BALANCE_WAKE(唤醒任务的选核)、SD_BALANCE_FORK(fork的新任务选核)、SD_BALANCE_EXEC(exec的任务选核) 
 * wake_flags: 可取值有 WF_SYNC、WF_FORK、WF_MIGRATED、WF_ON_CPU、WF_ANDROID_VENDOR,但是只对WF_SYNC进行了特殊处理,表示同步唤醒,其它标志被此函数忽略。 
 * 
 * 返回值:选出的目标cpu 
 *  
 * 执行环境:必须关抢占 
 */ 
static int select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags) 
{ 
    struct sched_domain *tmp, *sd = NULL; 
    int cpu = smp_processor_id(); 
    int new_cpu = prev_cpu; //目标cpu先默认取prev_cpu 
    int want_affine = 0; 
    int sync = (wake_flags & WF_SYNC) && !(current->flags & PF_EXITING); 
    int target_cpu = -1; 
 
    //注册了这个HOOK且不是对新fork出来的任务进行选核,就更新任务的负载 
    if (trace_android_rvh_select_task_rq_fair_enabled() && !(sd_flag & SD_BALANCE_FORK))  
        sync_entity_load_avg(&p->se); 
    //Vendor厂商可以更改选核路径,若是选到了核,就直接退出了 
    trace_android_rvh_select_task_rq_fair(p, prev_cpu, sd_flag, wake_flags, &target_cpu); probe_android_rvh_select_task_rq_fair 
    if (target_cpu >= 0) 
        return target_cpu; 
 
    //只有对唤醒任务的选核才有可能走EAS选核路径 
    if (sd_flag & SD_BALANCE_WAKE) { 
        //记录当前任何和被唤醒任务p之间是否有固定的唤醒关系 
        record_wakee(p); 
 
        //全局使能控制/proc/sys/kernel/sched_energy_aware是否开启EAS 
        if (sched_energy_enabled()) { 
            //进行EAS选核,EAS选到核了,就直接退出。里面判断了rd->overutilized,若overutilized则直接失败退出 
            new_cpu = find_energy_efficient_cpu(p, prev_cpu, sync); 
            if (new_cpu >= 0) 
                return new_cpu; 
            //若EAS没有选到核,就回退为初始状态,继续走传统路径进行选核 
            new_cpu = prev_cpu; 
        } 
 
        //若p和current之间比较有相关性且任务p允许运行在当前cpu上,就认为是want_affine 
        want_affine = !wake_wide(p) && cpumask_test_cpu(cpu, p->cpus_ptr); 
    } 
 
    rcu_read_lock(); 
    for_each_domain(cpu, tmp) { //MC-->DIE 
        /* If both 'cpu' and 'prev_cpu' are part of this domain, cpu is a valid SD_WAKE_AFFINE target.*/ 
        /* SD_WAKE_AFFINE 标志MC和DIE都定义了,恒成立, 因此可以解释为只要满足want_affine, 就肯定会进入 */ 
        if (want_affine && (tmp->flags & SD_WAKE_AFFINE) && cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) { 
            //若当前cpu就是任务p之前运行的prev_cpu, 不用调用wake_affine()选核了,若是唤醒选核直接选idle的兄弟cpu,非唤醒选核直接选prev_cpu 
            if (cpu != prev_cpu) 
                new_cpu = wake_affine(tmp, p, cpu, prev_cpu, sync); //若是既不走快速路径,又不走慢速路径,就返回它。 
 
            sd = NULL; /* Prefer wake_affine over balance flags */ 
            break; 
        } 
 
        /* 
         * 注意 tmp->flags 不会包含 SD_BALANCE_WAKE, 因为MC和DIE都没设置这个标志。只有 SD_BALANCE_FORK、SD_BALANCE_EXEC 选核才有可能赋值 
         * 对于want_affine=0的情况,这个循环退出后,sd就是当前cpu对应的DIE层级的sd. 这里的作用是找到支持sd_flag的最高层级的sd 
         */ 
        if (tmp->flags & sd_flag) 
            sd = tmp; 
        else if (!want_affine) 
            break; 
    } 
 
    if (unlikely(sd)) { //SD_BALANCE_WAKE这类休眠唤醒的任务选核不可能走慢速路径,因为sd恒为NULL 
        /* Slow path */ 
        new_cpu = find_idlest_cpu(sd, p, cpu, prev_cpu, sd_flag); 
    } else if (sd_flag & SD_BALANCE_WAKE) { //对唤醒的任务进行选核 
        /* Fast path */ 
        new_cpu = select_idle_sibling(p, prev_cpu, new_cpu); 
 
        if (want_affine) 
            current->recent_used_cpu = cpu; 
    } 
    rcu_read_unlock(); 
 
    return new_cpu; 
}

1. 主要逻辑

(1) Vendor可以注册HOOK来决定是否执行这个原生的选核流程,若注册了且选到了核,则原生选核流程不再执行。否则执行原生选核流程。

(2) 判断是否进行EAS选核,若EAS选到和核则直接退出,否则继续往下走选核流程。EAS选核的条件为:
a. 必须是唤醒场景的选核,fork和exec场景的选核都不会走EAS。
b. EAS全局控制开关/proc/sys/kernel/sched_energy_aware必须是开启的。
c. 系统没有overutilized,若是overutilized则直接退出EAS选核。

(3) 满足wake_affine选出的核会作为一个候选结果,若是唤醒场景,还有走快速路径进行选核。

(4) 慢速路径选核只有fork和exec两类选核流程会走,唤醒选核是不会走慢速路径的。且慢速路径传参sd只可能是当前cpu对应的DIE层级的sd。

(5) 快速路径选核只有唤醒选核流程会走,fork和exec两类选核流程不会走快速选核流程。虽然名字叫select_idle_sibling,但是在同cluster中选不到idle核时,还是会在所有cluster中进行选核。

二、wake affine 属性

wake affine 只支持唤醒场景的选核。主要判断当前任务与被唤醒任务之间是否有比较固定的唤醒关系,来帮助选出一个候选cpu。

1. task_struct 中有三个成员用来线程唤醒信息

struct task_struct { 
    ... 
    unsigned int        wakee_flips; //该线程唤醒不同wakee的次数,值越大说明越偏向于唤醒不同的线程且唤醒越频繁 
    unsigned long        wakee_flip_decay_ts; //记录上次wakee_flips衰减的时间点,其每秒衰减为原来的50% 
    struct task_struct    *last_wakee; //该线程上次唤醒的线程 
    ... 
}

2. record_wakee()

/* 
 * 若current对p有比较固定的唤醒关系的话,current->wakee_flips将非常的小。 
 * 若经常唤醒其它不同的线程,其值将比较大 
 */ 
static void record_wakee(struct task_struct *p) 
{ 
    /* 
     * Only decay a single time; tasks that have less then 1 wakeup per 
     * jiffy will not have built up many flips. 
     */ 
    //超过1秒衰减为原来的1/2 
    if (time_after(jiffies, current->wakee_flip_decay_ts + HZ)) { 
        current->wakee_flips >>= 1; 
        current->wakee_flip_decay_ts = jiffies; 
    } 
 
    //当前任务上下文中,若上次唤醒的不是任务p, 当前任务的wakee_flips加1 
    if (current->last_wakee != p) { 
        current->last_wakee = p; 
        current->wakee_flips++; 
    } 
}

Waker唤醒wakee的场景中,有两种选核思路:一种是聚合的思路,即让waker和wakee尽量的close,从而提高cache hit。另外一种思考是分散,即让load尽量平均分配在多个cpu上。不同的唤醒模型使用不同的放置策略,两种简单的唤醒模型:

(1) 在1:N模型中,一个server会不断的唤醒多个不同的client。
(2) 在1:1模型中,线程A和线程B不断的唤醒对方。

在1:N模型中,如果N是一个较大的数值,那么让waker和wakee尽量的close会导致负荷的极度不平均,这会waker所在的sd会承担太多的task,从而引起性能下降。
在1:1模型中,让waker和wakee尽量的close不存在这样的问题,还能提高性能。
实际的程序中,唤醒关系可能没有那么简单,一个wakee可能是另外一个关系中的waker,交互可能是M:N的形式。考虑这样一个场景:waker把wakee拉近,而wakee自身的wakee flips比较大,由于wakee也会做waker,那么更多的线程也会拉近waker所在的sd,从而进一步加剧CPU资源的竞争。因此waker和wakee的wakee flips的数值都不能太大,太大的时候应该禁止wake affine。内核中通过 wake_wide() 来判断是否使能wake affine。

3. wake_wide()

/* 
 * 通过开关频率启发式检测 M:N 唤醒者/被唤醒者关系。 
 * 许多唤醒者唤醒的是与上次不同的任务,其频率大约是唤醒某一任务的 N 倍。 
 * 为了确定我们是否应该让负载分散与合并到共享缓存,我们在一对伙伴的一个中寻找最小为 llc_size 的“翻转”频率,在另一个中寻找大于 lls_size 频率的因子。 
 * 满足这两个条件,我们可以相对确定这种关系是非一夫一妻制的,伙伴数量超过套接字大小。 
 * Waker/wakee 是client/server、worker/dispatcher、中断源或任何无关紧要的东西,传播标准是明显的合作伙伴数量超过套接字大小。 
 * 
 * 对于有比较固定唤醒关系的,返回0,否则返回1 
 */ 
static int wake_wide(struct task_struct *p) 
{ 
    unsigned int master = current->wakee_flips; 
    unsigned int slave = p->wakee_flips; 
    int factor = __this_cpu_read(sd_llc_size); //表示此cpu所在cluster中cpu的个数 
 
    if (master < slave) 
        swap(master, slave); 
    //这里是用的是或 
    if (slave < factor || master < slave * factor) 
        return 0; 
    return 1; 
}

这个函数返回0,并且当前cpu在任务p的亲和性里面,就判断为want_affine。这里的or逻辑是存疑的,因为master和slave其一的wakee_flips比较小就满足wake affine,这会使得任务太容易在LLC domain堆积了。在1:N模型中(例如手机转屏的时候,一个线程会唤醒非常非常多的线程来处理configChange消息),master的wakee_flips巨大无比,slave的wakee_flips非常小,如果仍然wake affine是不合理的。

4. wake_affine()

/* 
 * select_task_rq_fair传参:sd为当前cpu对应的MC或DIE层级的sd; p为待选核任务; this_cpu为当前正在执行的cpu;  
 * prev_cpu为任务之前运行的cpu; sync表示选核时是否指定了同步WF_SYNC标志 
 */ 
static int wake_affine(struct sched_domain *sd, struct task_struct *p, int this_cpu, int prev_cpu, int sync) 
{ 
    int target = nr_cpumask_bits; 
 
    if (sched_feat(WA_IDLE)) 
        target = wake_affine_idle(this_cpu, prev_cpu, sync); 
 
    if (sched_feat(WA_WEIGHT) && target == nr_cpumask_bits) //若上面没有选到cpu 
        target = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync); 
 
    schedstat_inc(p->se.statistics.nr_wakeups_affine_attempts); //增加统计计数 
    if (target == nr_cpumask_bits) 
        return prev_cpu; //若是还是没选到核,就返回prev_cpu,否则返回选到的cpu 
 
    schedstat_inc(sd->ttwu_move_affine); 
    schedstat_inc(p->se.statistics.nr_wakeups_affine); 
    return target; 
} 
 
 
/* 
 * The purpose of wake_affine() is to quickly determine on which CPU we can run 
 * soonest. For the purpose of speed we only consider the waking and previous CPU. 
 * 
 * wake_affine_idle() - only considers 'now', it check if the waking CPU is 
 *            cache-affine and is (or    will be) idle. 
 * 
 * wake_affine_weight() - considers the weight to reflect the average 
 *              scheduling latency of the CPUs. This seems to work 
 *              for the overloaded case. 
 * 
 * wake_affine传参:this_cpu是当前正在执行的cpu; prev_cpu是任务上次运行的cpu; sync是是 
 * 否指定了AF_SYNC同步唤醒标志 
 */ 
static int wake_affine_idle(int this_cpu, int prev_cpu, int sync) 
{ 
    /* 
     * If this_cpu is idle, it implies the wakeup is from interrupt 
     * context. Only allow the move if cache is shared. Otherwise an 
     * interrupt intensive(密集型) workload could force all tasks onto one 
     * node depending on the IO topology or IRQ affinity settings. 
     * 
     * If the prev_cpu is idle and cache affine then avoid a migration. 
     * There is no guarantee that the cache hot data from an interrupt 
     * is more important than cache hot data on the prev_cpu and from 
     * a cpufreq perspective, it's better to have higher utilisation 
     * on one CPU. 
     */ 
    //若正在执行的cpu是idle的(中断唤醒),且当前cpu和任务上次运行的cpu属于同一个cluster 
    if (available_idle_cpu(this_cpu) && cpus_share_cache(this_cpu, prev_cpu)) 
        //若prev_cpu也idle就返回prev_cpu,否则返回当前正在运行的idle cpu 
        return available_idle_cpu(prev_cpu) ? prev_cpu : this_cpu; 
 
    /* 
     * 若同步唤醒且当前cpu上只有一个任务(也就是waker)在运行,就返回当前cpu,因为sync唤醒, 
     * 当前waker马上就要睡眠了。 
     */ 
    if (sync && cpu_rq(this_cpu)->nr_running == 1) 
        return this_cpu; 
 
    return nr_cpumask_bits; //没选到cpu返回它 
} 
 
 
/* 
 * wake_affine传参:sd是当前正在运行的cpu对应的MC或DIE层级的sd; p是待选核的任务; this_cpu是当前正在执行的cpu; prev_cpu是任务上次运行的cpu;  
 * sync是是否指定了AF_SYNC同步唤醒标志。 
 */ 
static int wake_affine_weight(struct sched_domain *sd, struct task_struct *p, int this_cpu, int prev_cpu, int sync) 
{ 
    s64 this_eff_load, prev_eff_load; 
    unsigned long task_load; 
 
    //当前正在运行cpu上的CFS任务的负载 
    this_eff_load = cpu_load(cpu_rq(this_cpu)); //return cfs_rq->avg.load_avg; 
 
    if (sync) { 
        unsigned long current_load = task_h_load(current); //约为 current->se.avg.load_avg; 
        //当前任务的负载比当前cpu上cfs任务的负载之和还大?应该是安全的容错处理 
        if (current_load > this_eff_load) 
            return this_cpu; 
 
        this_eff_load -= current_load; 
    } 
 
    task_load = task_h_load(p); //约为 p->se.avg.load_avg; 
 
    this_eff_load += task_load; //计算若p把current从当前cpu上挤下去后,cpu上CFS任务的总负载 
    if (sched_feat(WA_BIAS)) 
        this_eff_load *= 100; //乘以100 
     
    this_eff_load *= capacity_of(prev_cpu); //再乘以cpu算力中可用于cfs任务的算力(出去温限/irq/rt/dl占用后的算力),乘以的竟然是prev_cpu的! 
 
    prev_eff_load = cpu_load(cpu_rq(prev_cpu)); //prev_cpu::rq.cfs_rq->avg.load_avg 
    prev_eff_load -= task_load; //这里为什么要减去? 
    if (sched_feat(WA_BIAS)) 
        prev_eff_load *= 100 + (sd->imbalance_pct - 100) / 2; //MC和DIE都是乘以 100+(117-100)/2 
    prev_eff_load *= capacity_of(this_cpu); //乘以的竟然是this_cpu可用于cfs任务的算力! 
 
    /* 
     * If sync, adjust the weight of prev_eff_load such that if 
     * prev_eff == this_eff that select_idle_sibling() will consider 
     * stacking the wakee on top of the waker if no other CPU is 
     * idle. 
     * 如果同步唤醒,则调整 prev_eff_load 的权重,以便如果 prev_eff == this_eff 则 select_idle_sibling() 将考虑在没有其它空闲CPU的情况下将 
     * 被唤醒的任务放在唤醒它的CPU上。 
     */ 
    if (sync) 
        prev_eff_load += 1; //前面乘以100又乘以CPU可用于CFS任务的算力了,这里加1有啥用? 
 
    /*公式整理一下为:this_cpu_load/this_cpu_cap < 108.5% * prev_cpu_load/prev_cpu_cap 成立就返回this_cpu*/ 
    return this_eff_load < prev_eff_load ? this_cpu : nr_cpumask_bits; 
}

三、慢速路径

只有fork和exec类型的选核才会走慢速路径,慢速路径选核函数为 find_idlest_cpu(),走慢速路径选核时传参sd只可能是DIE层级的。

/* 
 * 只有fork或exec的选核才可能走这个函数。 
 * 
 * 传参:sd当前cpu对应的DIE层级的sd(只可能是DIE层级); p是待选核任务; cpu为当前cpu; prev_cpu为任务p之前运行的cpu; sd_flag表示哪种选核类型。 
 * 
 * 作用:在最idle的sg中找出最idle的cpu, 若是没找到就返回当前cpu. 
 */ 
static inline int find_idlest_cpu(struct sched_domain *sd, struct task_struct *p, int cpu, int prev_cpu, int sd_flag) 
{ 
    int new_cpu = cpu; 
 
    //这个sd中的所有cpu都不在任务p的cpu亲和性里面 
    if (!cpumask_intersects(sched_domain_span(sd), p->cpus_ptr)) 
        return prev_cpu; 
 
    /* 
     * We need task's util for cpu_util_without, sync it up to prev_cpu's last_update_time. 
     */ 
    //仅对于exec类型的选核更新任务的负载 
    if (!(sd_flag & SD_BALANCE_FORK)) 
        sync_entity_load_avg(&p->se); 
 
    while (sd) { 
        struct sched_group *group; 
        struct sched_domain *tmp; 
        int weight; 
 
        if (!(sd->flags & sd_flag)) { //恒不成立,因为fork或exec类型的选核MC/DIE都支持 
            sd = sd->child; 
            continue; 
        } 
 
        //若是返回NULL,直接选的是当前cpu 
        group = find_idlest_group(sd, p, cpu); 
        if (!group) { 
            sd = sd->child; 
            continue; 
        } 
 
        //若是在d中找到了最忙的sg,就在其中选退出延迟最小且最后进idle的cpu,若是没有idle的cpu就选load最小的cpu 
        new_cpu = find_idlest_group_cpu(group, p, cpu); 
        if (new_cpu == cpu) { 
            /* Now try balancing at a lower domain level of 'cpu': */ 
            sd = sd->child; 
            continue; 
        } 
 
        /* Now try balancing at a lower domain level of 'new_cpu': */ 
        cpu = new_cpu; 
        weight = sd->span_weight; 
        sd = NULL; 
        for_each_domain(cpu, tmp) { 
            if (weight <= tmp->span_weight) //一进来就退出了,相当于没有执行 
                break; 
            if (tmp->flags & sd_flag) 
                sd = tmp; 
        } 
    } 
 
    return new_cpu; 
}

1. find_idlest_group()

在当前cpu对应的sd中找出最空闲的sg

/* 
 * find_idlest_group() finds and returns the least busy CPU group within the domain. 
 * 
 * Assumes p is allowed on at least one CPU in sd. 
 * 
 * find_idlest_cpu传参:sd为当前cpu DIE层级对应的sd; p为待选核任务; cpu为当前cpu; 
 */ 
static struct sched_group *find_idlest_group(struct sched_domain *sd, struct task_struct *p, int this_cpu) 
{ 
    struct sched_group *idlest = NULL, *local = NULL, *group = sd->groups; 
    struct sg_lb_stats local_sgs, tmp_sgs; 
    struct sg_lb_stats *sgs; 
    unsigned long imbalance; 
    struct sg_lb_stats idlest_sgs = { 
            .avg_load = UINT_MAX, 
            .group_type = group_overloaded, //初始化为最大的不均衡 
    }; 
 
    //1024 * (sd->imbalance_pct-100) / 100 
    imbalance = scale_load_down(NICE_0_LOAD) * (sd->imbalance_pct-100) / 100; 
 
    //遍历MC层级先的每个cpu 
    do { 
        int local_group; 
 
        /* Skip over this group if it has no CPUs allowed */ 
        //跳过任务p亲和性不允许的cpu 
        if (!cpumask_intersects(sched_group_span(group), p->cpus_ptr)) 
            continue; 
 
        //当前正在运行的cpu是否在这个group中 
        local_group = cpumask_test_cpu(this_cpu, sched_group_span(group)); 
        if (local_group) { 
            sgs = &local_sgs; 
            local = group; 
        } else { 
            sgs = &tmp_sgs; 
        } 
 
        update_sg_wakeup_stats(sd, group, sgs, p); 
 
        //group和idlest比较,看group是否比idlest更闲 
        if (!local_group && update_pick_idlest(idlest, &idlest_sgs, group, sgs)) { 
            idlest = group; 
            idlest_sgs = *sgs; 
        } 
 
    } while (group = group->next, group != sd->groups); 
 
 
    /* There is no idlest group to push tasks to */ 
    //若没找到idlest sg,选当前cpu 
    if (!idlest) 
        return NULL; 
 
    /* The local group has been skipped because of CPU affinity */ 
    //此sd中若没有local group就直接返回idlest,否则还要和local group再PK一下,此例中,local group恒存在的 
    if (!local) 
        return idlest; 
 
    /* 
     * If the local group is idler than the selected idlest group 
     * don't try and push the task. 
     */ 
    //若local sg更闲,选当前cpu 
    if (local_sgs.group_type < idlest_sgs.group_type) 
        return NULL; 
 
    /* 
     * If the local group is busier than the selected idlest group 
     * try and push the task. 
     */ 
    if (local_sgs.group_type > idlest_sgs.group_type) 
        return idlest; 
 
    //local group和idlest group一样闲的情况了: 
    switch (local_sgs.group_type) { 
    case group_overloaded: 
    case group_fully_busy: 
        /* 
         * When comparing groups across NUMA domains, it's possible for 
         * the local domain to be very lightly loaded relative to the 
         * remote domains but "imbalance" skews the comparison making 
         * remote CPUs look much more favourable. When considering 
         * cross-domain, add imbalance to the load on the remote node 
         * and consider staying local. 
         */ 
        //大小核架构没有SD_NUMA标志,恒不执行 
        if ((sd->flags & SD_NUMA) && ((idlest_sgs.avg_load + imbalance) >= local_sgs.avg_load)) 
            return NULL; 
 
        /* 
         * If the local group is less loaded than the selected 
         * idlest group don't try and push any tasks. 
         */ 
        //最闲的sg和local sg差值大于阈值17*1024,选当前cpu 
        if (idlest_sgs.avg_load >= (local_sgs.avg_load + imbalance)) 
            return NULL; 
 
        //local_avg_load/idlest_avg_load <= sd->imbalance_pct%,选当前cpu 
        if (100 * local_sgs.avg_load <= sd->imbalance_pct * idlest_sgs.avg_load) 
            return NULL; 
        break; 
 
    case group_imbalanced: 
    case group_asym_packing: 
        /* Those type are not used in the slow wakeup path */ 
        return NULL; //选当前cpu 
 
    case group_misfit_task: 
        /* Select group with the highest max capacity */ 
        if (local->sgc->max_capacity >= idlest->sgc->max_capacity) 
            return NULL; //选当前cpu 
        break; 
 
    case group_has_spare: 
        if (sd->flags & SD_NUMA) { 
#ifdef CONFIG_NUMA_BALANCING //没使能,不执行 
            int idlest_cpu; 
            /* 
             * If there is spare capacity at NUMA, try to select 
             * the preferred node 
             */ 
            if (cpu_to_node(this_cpu) == p->numa_preferred_nid) 
                return NULL; 
 
            idlest_cpu = cpumask_first(sched_group_span(idlest)); 
            if (cpu_to_node(idlest_cpu) == p->numa_preferred_nid) 
                return idlest; 
#endif 
            /* 
             * Otherwise, keep the task on this node to stay close 
             * its wakeup source and improve locality. If there is 
             * a real need of migration, periodic load balance will 
             * take care of it. 
             */ 
            if (local_sgs.idle_cpus) 
                return NULL;  //若local sg有idle cpu存在,选当前cpu 
        } 
 
        /* 
         * Select group with highest number of idle CPUs. We could also 
         * compare the utilization which is more stable but it can end 
         * up that the group has less spare capacity but finally more 
         * idle CPUs which means more opportunity to run task. 
         */ 
        //若local sg的idle cpu个数比idlest sg更多,选当前cpu 
        if (local_sgs.idle_cpus >= idlest_sgs.idle_cpus) 
            return NULL; 
        break; 
    } 
 
    return idlest; 
}

update_sg_wakeup_stats 更新 sgs:

/* 
 * update_sg_wakeup_stats - Update sched_group's statistics for wakeup. 
 * @sd: The sched_domain level to look for idlest group. 
 * @group: sched_group whose statistics are to be updated. 
 * @sgs: variable to hold the statistics for this group. 
 * @p: The task for which we look for the idlest group/CPU. 
 * 
 * find_idlest_group传参:sd为当前cpu对应的MC层级的sd; group为MC层级的一个sg; sgs为未初始化的参数; p为待选核任务 
 * 作用:更新 sgs  
 */ 
static inline void update_sg_wakeup_stats(struct sched_domain *sd, 
                      struct sched_group *group, struct sg_lb_stats *sgs, struct task_struct *p) 
{ 
    int i, nr_running; 
 
    memset(sgs, 0, sizeof(*sgs)); 
 
    //MC层级一个sg中只有一个cpu 
    for_each_cpu(i, sched_group_span(group)) { 
        struct rq *rq = cpu_rq(i); 
        unsigned int local; 
 
        sgs->group_load += cpu_load_without(rq, p); 
        sgs->group_util += cpu_util_without(i, p); 
        sgs->group_runnable += cpu_runnable_without(rq, p); 
        local = task_running_on_cpu(i, p); //判断p是否queue在这个cpu的rq上,此case下应该return 0 
        sgs->sum_h_nr_running += rq->cfs.h_nr_running - local; 
 
        nr_running = rq->nr_running - local; 
        sgs->sum_nr_running += nr_running; 
 
        /* 
         * No need to call idle_cpu_without() if nr_running is not 0 
         */ 
        if (!nr_running && idle_cpu_without(i, p)) 
            sgs->idle_cpus++; 
 
    } 
 
    /* Check if task fits in the group */ 
    //只有DIE层级有这个标志,恒不成立 
    if (sd->flags & SD_ASYM_CPUCAPACITY && !task_fits_capacity(p, group->sgc->max_capacity)) { 
        sgs->group_misfit_task_load = 1; 
    } 
 
    sgs->group_capacity = group->sgc->capacity; 
    sgs->group_weight = group->group_weight; 
    sgs->group_type = group_classify(sd->imbalance_pct, group, sgs); 
 
    /* 
     * Computing avg_load makes sense only when group is fully busy or overloaded 
     */ 
    if (sgs->group_type == group_fully_busy || sgs->group_type == group_overloaded) 
        sgs->avg_load = (sgs->group_load * SCHED_CAPACITY_SCALE) / sgs->group_capacity; 
} 
 
 
//根据imbalance_pct和sgs来确认group_type 
static inline enum group_type group_classify(unsigned int imbalance_pct, struct sched_group *group, struct sg_lb_stats *sgs) 
{ 
    /* 
     * sgs->sum_nr_running <= sgs->group_weight 返回fase, 只要cpu个数大于任务个数,就不认为group_overloaded 
     * group_util/group_capacity > imbalance_pct/100=117% 或 group_runnable/group_capacity > imbalance_pct/100=117% 返回true 
     */ 
    if (group_is_overloaded(imbalance_pct, sgs)) 
        return group_overloaded; 
 
    if (sg_imbalanced(group)) //return group->sgc->imbalance; 
        return group_imbalanced; 
 
    if (sgs->group_asym_packing) 
        return group_asym_packing; 
 
    if (sgs->group_misfit_task_load) 
        return group_misfit_task; 
 
    if (!group_has_capacity(imbalance_pct, sgs)) 
        return group_fully_busy; 
 
    return group_has_spare; 
}

后续判断的group和idlest比较,看group是否比idlest更闲:

static bool update_pick_idlest(struct sched_group *idlest, struct sg_lb_stats *idlest_sgs, 
                   struct sched_group *group, struct sg_lb_stats *sgs) 
{ 
    if (sgs->group_type < idlest_sgs->group_type) 
        return true; 
 
    if (sgs->group_type > idlest_sgs->group_type) 
        return false; 
 
    /* 
     * The candidate and the current idlest group are the same type of 
     * group. Let check which one is the idlest according to the type. 
     */ 
    //group_type相等的情况下比较谁更闲 
    switch (sgs->group_type) { 
    case group_overloaded: 
    case group_fully_busy: //哪个sg的avg_load,哪个sg更闲 
        /* Select the group with lowest avg_load. */ 
        if (idlest_sgs->avg_load <= sgs->avg_load) 
            return false; 
        break; 
 
    case group_imbalanced: 
    case group_asym_packing: 
        /* Those types are not used in the slow wakeup path */ 
        return false; 
 
    case group_misfit_task: //哪个sg的最大算力大,哪个sg更闲 
        /* Select group with the highest max capacity */ 
        if (idlest->sgc->max_capacity >= group->sgc->max_capacity) 
            return false; 
        break; 
 
    case group_has_spare: //哪个sg的idle cpu个数多,哪个sg更闲 
        /* Select group with most idle CPUs */ 
        if (idlest_sgs->idle_cpus > sgs->idle_cpus) 
            return false; 
 
        /* Select group with lowest group_util */ 
        //若idle cpu个数相等,哪个group_util小哪个更闲 
        if (idlest_sgs->idle_cpus == sgs->idle_cpus && idlest_sgs->group_util <= sgs->group_util) 
            return false; 
 
        break; 
    } 
 
    return true; 
}

2. find_idlest_group_cpu()

/* 
 * find_idlest_group_cpu - find the idlest CPU among the CPUs in the group. 
 * 
 * find_idlest_cpu传参:group为在当前cpu对应的MC层级sd中找出的最闲的sg; p为待选核任务; this_cpu为当前正在执行的cpu 
 */ 
static int find_idlest_group_cpu(struct sched_group *group, struct task_struct *p, int this_cpu) 
{ 
    unsigned long load, min_load = ULONG_MAX; 
    unsigned int min_exit_latency = UINT_MAX; 
    u64 latest_idle_timestamp = 0; 
    int least_loaded_cpu = this_cpu; 
    int shallowest_idle_cpu = -1; 
    int i; 
 
    /* Check if we have any choice: */ 
    //对于MC层级的sg这里就直接就返回了,因为sg中只有一个cpu,DIE层级继续往下走。 
    if (group->group_weight == 1) 
        return cpumask_first(sched_group_span(group)); 
 
    /* Traverse only the allowed CPUs */ 
    //DIE层级的sg,遍历这个cluster中任务p亲和性允许的cpu 
    for_each_cpu_and(i, sched_group_span(group), p->cpus_ptr) { 
        if (sched_idle_cpu(i)) //若此cpu rq中只有SCHED_IDLE类型的任务,就选此cpu 
            return i; 
 
        //判断此cpu是否是idle cpu: rq->curr==rq->idle && rq->nr_running==0 && rq->ttwu_pending==0 
        if (available_idle_cpu(i)) { 
            struct rq *rq = cpu_rq(i); 
            struct cpuidle_state *idle = idle_get_state(rq); //return rq->idle_state; 
            if (idle && idle->exit_latency < min_exit_latency) { 
                /* 
                 * We give priority to a CPU whose idle state has the smallest exit latency irrespective 
                 * of any idle timestamp. 
                 */ 
                min_exit_latency = idle->exit_latency; //记录最小退出延迟 
                latest_idle_timestamp = rq->idle_stamp; 
                shallowest_idle_cpu = i; //记录最小的退出延迟的cpu 
            } else if ((!idle || idle->exit_latency == min_exit_latency) && rq->idle_stamp > latest_idle_timestamp) { //idle退出延迟相等,且进入idle的时间更晚 
                /* 
                 * If equal or no active idle state, then the most recently idled CPU might have 
                 * a warmer cache. 
                 */ 
                latest_idle_timestamp = rq->idle_stamp; 
                shallowest_idle_cpu = i; 
            } 
        } else if (shallowest_idle_cpu == -1) {//对于非idle类型的cpu,并且之前也没有遍历到idle cpu 
            load = cpu_load(cpu_rq(i)); 
            if (load < min_load) { 
                min_load = load; //记录load最小的cpu 
                least_loaded_cpu = i; 
            } 
        } 
    } 
 
    //若是有idle cpu就选idle cpu,若是没有idle cpu就选load最小的cpu 
    return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu; 
}

同 load_balance()寻找最忙的cpu类似。这里的慢速路径,选择最空闲的cpu,先在sd中找最空闲的sg,然后再sg中找最空闲的cpu。这里最空闲指的是当前cpu所在cluster内,有idle的cpu就算idle的cpu,若是没有idle的cpu就选负载最小的cpu。

四、快速路径

快速选核路径只有唤醒选核流程才会走。虽然函数名中是选兄弟cpu,但是在选不到idle cpu的时候,也会在其它Cluster进行选核

/* 
 * Try and locate an idle core/thread in the LLC cache domain. 
 * 
 * select_task_rq_fair传参:p为待选核任务; prev是任务上次运行的cpu; target是备选目标cpu,可能是prev_cpu也可能是wake_affine选出的cpu 
 */ 
static int select_idle_sibling(struct task_struct *p, int prev, int target) 
{ 
    struct sched_domain *sd; 
    unsigned long task_util; 
    int i, recent_used_cpu; 
 
    /* 
     * On asymmetric system, update task utilization because we will check 
     * that the task fits with cpu's capacity. 
     */ 
    if (static_branch_unlikely(&sched_asym_cpucapacity)) { 
        sync_entity_load_avg(&p->se); 
        task_util = uclamp_task_util(p); //将util_est clamp 在MIN和MAX之间 
    } 
 
    /* 
     * 传入的target是一个idle cpu且可以容纳的了uclamp后的任务的util,就直接选之前选的cpu。 
     * Wake affine的场景下,target cpu是通过wake_affine函数寻找的target cpu,其他场景下, 
     * target CPU其实等于prev CPU。 
     */ 
    if ((available_idle_cpu(target) || sched_idle_cpu(target)) && asym_fits_capacity(task_util, target)) 
        return target; 
 
    /* 
     * If the previous CPU is cache affine and idle, don't be stupid: 
     * 
     * 若传入的参数是由wake_affine选出的cpu,且和prev_cpu属于同一个cluster(共享L2-Cache), 且prev_cpu是idle的, 且prev_cpu能容纳的下uclamp后的任务p的util 
     */ 
    if (prev != target && cpus_share_cache(prev, target) && (available_idle_cpu(prev) || sched_idle_cpu(prev)) && asym_fits_capacity(task_util, prev)) 
        return prev; 
 
    /* 
     * Allow a per-cpu kthread to stack with the wakee if the kworker thread and the tasks previous CPUs are the same. 
     * The assumption is that the wakee queued work for the per-cpu kthread that is now complete and the wakeup is 
     * essentially a sync wakeup. An obvious example of this pattern is IO completions. 
     * 翻译: 
     * 如果 kworker 线程和任务prev_cpu是同一个,则允许 per-cpu kthread 与被唤醒线程堆叠。假设是被唤醒任务往per-cpu的kthread 
     * 上queue work, 唤醒本质上是同步唤醒。这种模式的一个明显例子是 IO 完成。 
     * 
     * 当前任务是一个per-cpu的内核线程,且任务的prev_cpu就是当前cpu,且当前cpu上最多只有一个任务在运行,就选prev_cpu. 
     */ 
    if (is_per_cpu_kthread(current) &&  prev == smp_processor_id() && this_rq()->nr_running <= 1) { 
        return prev; 
    } 
 
    /* Check a recently used CPU as a potential idle candidate: */ 
    /* 
     * recent_used_cpu的更新位置: 
     * select_task_rq_fair: 更新 current->recent_used_cpu 为当前正在运行的cpu 
     * select_idle_sibling: 将待选核任务 p->recent_used_cpu 设置为 prev_cpu 
     * 
     * 若 p->recent_used_cpu 既不是prev_cpu也不是target_cpu, 但是是和target_cpu共cluster的,且是idle的, 且任务的亲和性允许, 
     * 且算力能够容纳任务,那么就选 p->recent_used_cpu。 
     */ 
    recent_used_cpu = p->recent_used_cpu; 
    if (recent_used_cpu != prev && recent_used_cpu != target && cpus_share_cache(recent_used_cpu, target) && 
        (available_idle_cpu(recent_used_cpu) || sched_idle_cpu(recent_used_cpu)) && cpumask_test_cpu(p->recent_used_cpu, p->cpus_ptr) && 
        asym_fits_capacity(task_util, recent_used_cpu)) { 
        /* 
         * Replace recent_used_cpu with prev as it is a potential candidate for the next wake: 
         */ 
        p->recent_used_cpu = prev; 
        return recent_used_cpu; //还将p放在它最近使用过的cpu上 
    } 
 
    /* 
     * For asymmetric CPU capacity systems, our domain of interest is sd_asym_cpucapacity rather than sd_llc. 
     */ 
    if (static_branch_unlikely(&sched_asym_cpucapacity)) { 
        sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, target)); //target_cpu对应的DIE层级的sd 
        /* 
         * On an asymmetric CPU capacity system where an exclusive cpuset defines a symmetric island (i.e. one unique 
         * capacity_orig value through the cpuset), the key will be set but the CPUs within that cpuset will not have 
         * a domain with SD_ASYM_CPUCAPACITY. These should follow the usual symmetric capacity path. 
         */ 
        if (sd) { 
            //这个函数还可能返回-1,但是并没有兼容这个错误的结果!后续的使用也没有做判断,是个BUG!! 
            i = select_idle_capacity(p, sd, target); 
            return ((unsigned)i < nr_cpumask_bits) ? i : target; //这里会返回,下面的部分不会被执行到 
        } 
    } 
 
    /* 下面就是非大小核架构会执行的路径了 */ 
 
    sd = rcu_dereference(per_cpu(sd_llc, target)); //target_cpu对应的MC层级的sd 
    if (!sd) 
        return target; 
 
    i = select_idle_core(p, sd, target); //CONFIG_SCHED_SMT没定义为空函数 
    if ((unsigned)i < nr_cpumask_bits) 
        return i; 
 
    i = select_idle_cpu(p, sd, target); //CONFIG_SCHED_SMT没定义为空函数 
    if ((unsigned)i < nr_cpumask_bits) 
        return i; 
 
    i = select_idle_smt(p, sd, target); //CONFIG_SCHED_SMT没定义为空函数 
    if ((unsigned)i < nr_cpumask_bits) 
        return i; 
 
    return target; 
} 
 
 
/* 
 * select_idle_sibling传参:p为待选核任务; sd为参数target_cpu对应的DIE层级的sd; target为候选的target_cpu 
 * 
 * 作用:从target_cpu开始遍历,找一个能容纳下任务p的idle cpu, 若所有idle cpu都不能容纳下任务,就返回算力最大的idle cpu, 
 * 否则返回-1; 
 */ 
static int select_idle_capacity(struct task_struct *p, struct sched_domain *sd, int target) 
{ 
    unsigned long task_util, best_cap = 0; 
    int cpu, best_cpu = -1; 
    struct cpumask *cpus; 
 
    cpus = this_cpu_cpumask_var_ptr(select_idle_mask); 
    //先赋值后使用 
    cpumask_and(cpus, sched_domain_span(sd), p->cpus_ptr); 
 
    task_util = uclamp_task_util(p); 
 
    //这里从target_cpu开始遍历,利用了之前判断的结果target_cpu的算力是能容纳任务p的 
    for_each_cpu_wrap(cpu, cpus, target) { 
        unsigned long cpu_cap = capacity_of(cpu); 
 
        if (!available_idle_cpu(cpu) && !sched_idle_cpu(cpu)) //若此cpu非idle则跳过这个cpu 
            continue; 
        if (fits_capacity(task_util, cpu_cap)) //返回一个能容纳任务的idle cpu 
            return cpu; 
 
        if (cpu_cap > best_cap) { //若是没有能容纳的,则返回一个算力最大的 
            best_cap = cpu_cap; 
            best_cpu = cpu; 
        } 
    } 
 
    return best_cpu; 
}

1. 此函数中要使用到p的util, 所以需要先更新其负载。

2. 快速路径选核依次判断:
(1) 传入的target是一个idle cpu, 且可以容纳的了uclamp后的任务的util,就直接选之前选的这个 target_cpu
(2) 若传入的参数target是由wake_affine选出的cpu,且和prev_cpu属于同一个cluster(共享L2-Cache), 且prev_cpu是idle的, 且prev_cpu能容纳的下uclamp后的任务p的util, 那么选择 prev_cpu。
(3) 当前任务是一个per-cpu的内核线程,且任务的prev_cpu就是当前cpu,且当前cpu上最多只有一个任务在运行,就选 prev_cpu。一个典型的例子是IO操作场景。
(4) 若 p->recent_used_cpu 既不是prev_cpu也不是target_cpu, 但是是和target_cpu共cluster的,且是idle的, 且任务的亲和性允许,且算力能够容纳任务,那么就选 p->recent_used_cpu。
(5) 从target_cpu开始遍历,找一个能容纳下任务p的idle cpu, 若所有idle cpu都不能容纳下任务,就返回算力最大的idle cpu, 否则返回-1;

3. 注意有个BUG: select_idle_capacity()返回-1的话没有做容错处理。

五、总结

1. 有三种任务选核路径,sd_flag分别对应为 SD_BALANCE_WAKE(唤醒场景)、SD_BALANCE_FORK(fork新任务场景)、SD_BALANCE_EXEC(exec场景)。其中EAS选核和wake-affine选核只适用于唤醒场景,EAS选到核后直接退出,wake-affine选到核后还需要走快速路径继续选核,希望在当前cpu的同cluster中选一个空闲cpu或prev_cpu,若选不到,最终也会尝试在所有cluster中选核。fork新任务场景和exec场景走慢速选核路径,找出系统中最闲的cpu作为目标cpu。

参考:https://blog.csdn.net/feelabclihu/article/details/122007603?spm=1001.2014.3001.5501


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