调度器21—负载均衡—框架分析
⼀、概述
1. 负载均衡模块主要分两个软件层次：核⼼负载均衡模块和 class-specific均衡模块。内核对不同的类型的任务有不同的均衡策略，普通的CFS任务和RT、Deadline任务处理⽅式是不同的。本⽂主要讲述CFS任务的均衡。
⼆、负载均衡的场景
CFS任务负载均衡主要涉及下⾯三个场景：
1. 任务放置(task placement)
当阻塞的任务被唤醒的时候，确定该任务应该放置在那个CPU上执⾏。任务放置主要发⽣在下⾯三个场景：
(1) 唤醒⼀个新fork的线程
SYSCALL_DEFINE0(fork) //fork.c
kernel_clone
wake_up_new_task //core.c
__t_task_cpu(p, lect_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0)); //为新fork的任务选核
activate_task(rq, p, ENQUEUE_NOCLOCK); //将任务queue到rq上
trace_sched_wakeup_new(p);
check_preempt_curr(rq, p, WF_FORK); //触发⼀次抢占
//其中trace打印p的信息：
RxComputationTh-9555 [001] d..2171682.441405: sched_wakeup_new: comm=RxComputationTh pid=9609 prio=120 target_cpu=002
(2) exec⼀个线程的时候
SYSCALL_DEFINE3(execve, const char __ur *, filename, const char __ur *const __ur *, argv, const char __ur *const __ur *, envp) //fs/exec.c
do_execve
do_execveat_common
bprm_execve
sched_exec //core.c
dest_cpu = current->sched_class->lect_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0) //此时是正在为正在执⾏execve系统调⽤的任务重新选核
stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg); //若是新选的核和正在运⾏的这个核不是同⼀个cpu，向任务p正在运⾏的cpu对应的stop调度类的"migration/X"线程queue⼀个work，触发主动迁移 migration_cpu_stop
__migrate_task(rq, &rf, p, arg->dest_cpu); //迁移到dst cpu上
exec_binprm
trace_sched_process_exec(current, old_pid, bprm);
当执⾏"cat trace_pipe"命令时，实际上是先fork⼀个sh的⼦任务，然后再在⼦任务中执⾏系统调⽤execve装载"/system/bin/cat"⽂件，并为正在执⾏的当前任务重新选核，然后转为执⾏cat命令的代码，也就是谁会为shell命令执⾏两次选核。
/sys/kernel/tracing # cat trace_pipe
sh-9360 [006] d..2173370.376830: sched_wakeup_new: comm=sh pid=10752 prio=120 target_cpu=001
cat-10752 [001] .... 173370.379998: sched_process_exec: filename=/system/bin/cat pid=10752 old_pid=10752//三个pid相等，同⼀个任务
(3) 唤醒⼀个阻塞的进程
在上⾯的三个场景中都会调⽤ lect_task_rq 来为task选择⼀个合适的CPU。
wake_up_process //core.c 主要⽤于各驱动中唤醒任务
wake_up_state //⽤户空间锁、signal、ptrace、swait
default_wake_function //waitqueue机制默认唤醒函数、lect机制
try_to_wake_up //core.c
trace_sched_waking(p) //此时打印的cpu还是任务上次运⾏的cpu
cpu = lect_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags)
if (task_cpu(p) != cpu) { //新选出的cpu和任务p之前运⾏的cpu不是同⼀个cpu
wake_flags |= WF_MIGRATED;
t_task_cpu(p, cpu);
就业指导课
p->sched_class->migrate_task_rq(p, new_cpu); //migrate_task_rq_fair只是主要做⼀些虚拟时间的修正操作
__t_task_cpu(p, new_cpu); //只是将p->wake_cpu = cpu; p->cpu = cpu;
}
拜佛
ttwu_queue(p, cpu, wake_flags);
ttwu_queue_wakelist(p, cpu, wake_flags) //若执⾏唤醒的cpu和⽬标cpu不在同⼀个cluster内，⾛这个分⽀
__ttwu_queue_wakelist(p, cpu, wake_flags)
p->sched_remote_wakeup = !!(wake_flags & WF_MIGRATED);
rq->ttwu_pending = 1;
__smp_call_single_queue(cpu, &p->wake_entry.llist) //将任务p挂在⽬标cpu的per-cpu的 call_single_queue 上
nd_call_function_single_ipi(cpu) //对⽬标cpu发⽣ipi中断()
arch_nd_call_function_single_ipi
smp_cross_call(cpumask_of(cpu), IPI_CALL_FUNC); //触发⽬标cpu的ipi中断
do_handle_IPI //⽬标cpu收到ipi中断
generic_smp_call_function_single_interrupt
下元节是什么节
flush_smp_call_function_queue(true)
sched_ttwu_pending //kernel/smp.c 应该会执⾏这⾥，待求证新手烤烧烤技巧
ttwu_do_activate(rq, p, p->sched_remote_wakeup ? WF_MIGRATED : 0, &rf); //sched/core.c ⽬标cpu上执⾏的
ttwu_do_activate(rq, p, wake_flags, &rf) //若执⾏唤醒的cpu和⽬标cpu在同⼀个cluster内⾛这个分⽀，传参为⽬标cpu的rq
int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;
if (wake_flags & WF_SYNC)
en_flags |= ENQUEUE_WAKEUP_SYNC;
if (wake_flags & WF_MIGRATED)
en_flags |= ENQUEUE_MIGRATED;
activate_task(rq, p, en_flags);
enqueue_task(rq, p, flags);
p->on_rq = TASK_ON_RQ_QUEUED;
ttwu_do_wakeup(rq, p, wake_flags, rf); //传参为⽬标cpu的rq
check_preempt_curr(rq, p, wake_flags);
check_preempt_wakeup //唤醒者和被唤醒者属于同⼀调度类，⾛这个分⽀，若都是CFS任务就是这个函数(只看CFS)
resched_curr(rq) //被唤醒者和curr和buddy PK 虚拟时间看是否需要抢占，需要抢占的话就调⽤这个函数
resched_curr(rq) //被唤醒者的调度类优先级⽐唤醒者⾼，⾛这个分⽀
t_tsk_need_resched(curr); //curr是⽬标cpu上的curr
t_preempt_need_resched(); //唤醒者和被唤醒者的⽬标cpu是同⼀个cpu，⾛这个分⽀，触发在下⼀个抢占点到来时重新调度
smp_nd_reschedule(cpu); //唤醒者和被唤醒者的⽬标cpu不是同⼀个cpu，⾛这个分⽀，通过IPI中断来通知⽬标cpu
smp_cross_call(cpumask_of(cpu), IPI_RESCHEDULE);
scheduler_ipi() //⽬标cpu响应函数
preempt_fold_need_resched();
t_preempt_need_resched(); //若判断需要调度，触发在下⼀个抢占点到来时重新调度，在⽬标cpu上
p->state = TASK_RUNNING;
trace_sched_wakeup(p); //trace打印的时候就已经唤醒了，此时打印出来的cpu就是⽬标cpu
//trace打印：
<...>-813 [002] d..3184883.820266: sched_waking: comm=Binder:1562_C pid=3075 prio=120 target_cpu=007//上次运⾏在cpu7
<...>-813 [002] d..4184883.820277: sched_wakeup: comm=Binder:1562_C pid=3075 prio=120 target_cpu=002//唤醒后运⾏在cpu2
总结：唤醒阻塞任务最终都会汇总到 try_to_wake_up() 中。为被唤醒任务新选出的cpu和任务p之前运⾏的cpu不是同⼀个cpu的话会置上 WF_MIGRATED 标志。若执⾏唤醒的cpu和⽬标cpu不在同⼀个cluster内，需要触发ipi IPI_CALL_FUNC 中断触发⽬标cpu执⾏ttwu_do_activate()，若是在同⼀个cluster，直接执⾏ttwu_do_activate()即可。check_preempt_curr() 中判断若被唤被醒者的调度类优先级⽐唤醒者⾼，直接触发抢占，这个是core⾥⾯做的，和具体的调度类没有关系。若被唤被醒者和唤醒者属于同⼀个调度类，则由具体调度类来决定是否触发抢占。对于CFS任务，若唤醒者和被唤醒者的⽬标cpu是同⼀个cpu，判断需要抢占的话就可以直接触发抢占，若不在同⼀个cpu，还要通过ipi中断向被唤醒者的cpu发IPI_RESCHEDULE 中断使⽬标cpu触发抢占。看来各个cpu只能触发⾃⼰的抢占，不能触发别的cpu的抢占。
2. 负载均衡(load balance)
通过迁移cpu rq上的任务，让各个CPU上的负载匹配CPU算⼒。CFS负载均衡主要有三种：
(1) periodic load balance
在tick中触发load balance，我们称之 tick load balance 或者 periodic load balance。具体的代码执⾏路径如下：
画荷花图片大全scheduler_tick //core.c 硬中断上下⽂
rq->idle_balance = idle_cpu(cpu); //表⽰当前cpu是否idle
trigger_load_balance(rq) //fair.c
if (time_after_eq(jiffies, rq->next_balance))
rai_softirq(SCHED_SOFTIRQ); //软中断响应函数后执⾏。唤醒对应的cpu的ksoftirqd/X线程来执⾏
run_rebalance_domains
enum cpu_idle_type idle = this_rq->idle_balance ? CPU_IDLE : CPU_NOT_IDLE;
nohz_idle_balance(this_rq, idle) //若 nohz_idle_balance 过了，就直接退出了，也先不看这⾥
rebalance_domains(this_rq, idle) //只有当前jieeies > sd->last_balance + interval 才执⾏
load_balance(cpu, rq, sd, idle, &continue_balancing) //执⾏负载均衡，尝试拉负载到参数cpu上
nohz_balancer_kick(rq); //这个是中断上下⽂，先执⾏，主要是触发⼀个ipi中断。只有系统中有处于nohz的idle cpu才可能起作⽤，这⾥先不看它。
(2) new idle load balance
调度器在pick next task的时候，发现当前cfs rq中没有runnable任务，只能执⾏idle线程，让CPU进⼊idle状态的时候触发的负载均衡，我们称之new idle load balance。具体的代码执⾏路径如下：
__schedule(bool preempt) //core.c
美甲店创业计划书pick_next_task(rq, prev, &rf)
pick_next_task_fair //只看CFS调度类费用英语
if (!sched_fair_runnable(rq)) //rq-&_running=0, rq上⼀个runnable的任务都没有才调⽤
new_tasks = newidle_balance(rq, rf);
if (new_tasks > 0)
goto again; //若是均衡到任务了，重新触发CFS任务选核。
return NULL; //若是没有均衡到任务，哪就选idle调度类了。
只有CFS调度类，均衡也没有均衡到cfs任务，才会执⾏idle调度类的任务。
(3) idle load banlance
当其他的cpu已经进⼊idle，但本CPU任务太重，需要通过ipi中断将其它idle的cpu唤醒来分摊负载⽽触发的负载均衡，我们称之idle load banlance。具体的代码执⾏路径如下：
scheduler_tick //core.c 硬中断上下⽂
rq->idle_balance = idle_cpu(cpu); //表⽰当前cpu是否idle
trigger_load_balance(rq) //fair.c
nohz_balancer_kick(rq); //主要看这⾥
kick_ilb(flags)
ilb_cpu = find_new_ilb(); //只找nohz idle状态中的⾸个idle cpu
smp_call_function_single_async(ilb_cpu, &cpu_rq(ilb_cpu)->nohz_csd);
generic_exec_single(cpu, csd) //参数cpu为⾸个处于no-hz idle状态的cpu
__smp_call_single_queue(cpu, &csd->llist) //将⾸个idle cpu 的 rq->nohz_csd 添加到其cpu对应的per-cpu的单链表头 call_single_queue 中
nd_call_function_single_ipi(cpu)
arch_nd_call_function_single_ipi(cpu)
smp_cross_call(cpumask_of(cpu), IPI_CALL_FUNC)
do_handle_IPI //⽬标cpu被ipi中断唤醒开始执⾏
generic_smp_call_function_interrupt肉末水蒸蛋
nohz_csd_func //就是 rq->nohz_csd.func()
rq->nohz_idle_balance = flags;
rai_softirq_irqoff(SCHED_SOFTIRQ);
//之后就是和 "periodic load balance"中的逻辑相同了。
其实 "idle load banlance" 是和 "periodic load balance" 交织在⼀起的，挡在tick中周期触发 "periodic load balance" 的时候，就会判断是有处于 no-hz idle 状态的cpus，若是有⼜需要均衡的话就使⽤ipi中断唤醒⾸个处于no-hz idle 状态的cpu，然后在它上⾯触发负载均衡，让其去拉取繁忙cpu上的负载。
注：如果没有dynamic tick特性，那么就不需要进⾏idle load balance，因为tick会唤醒处于idle的cpu，从⽽周期性tick就可以覆盖这个场景。
3. 主动均衡(active upmigration)
把当前正在运⾏的 misfit task 向上迁移到算⼒更⾼的CPU上去。当⼀个低算⼒CPU的rq中出现misfit task的时候，如果该任务持续执⾏，那么迁移runnable任务负载均衡⽆能为⼒，需要主动均衡。
主动迁移是 Load balance 的⼀种特殊场景。在负载均衡中，只要运⽤适当的同步机制（持有⼀个或者多个rq lock），runnable的任务可以在各个CPU runqueue之间移动，然⽽running的任务是例外，它不挂在CPU rq中(虽然正在running的任务的->on_rq=1，dequeue 时没有置0)，load balance⽆法覆盖。为了能够迁移running状态的任务，内核提供了active upmigration 的⽅法（利⽤stop machine调度类的 migration/X 线程，就是先抢占它，被抢占后在put_prev_entity()中将其返回rq中，然后再迁移它，见
《load_balance函数分析》）。
三、补充
1. nohz.idle_cpus_mask 的更新逻辑
scheduler_tick //core.c
trigger_load_balance //fair.c
nohz_balancer_kick(struct rq *rq) //fair.c tick中触发均衡的cpu此时是⾮idle的才调⽤
nohz_balance_enter_idle(int cpu) //fair.c cpu⾮active的才调⽤,⾮主要逻辑
sched_cpu_dying //core.c cpu hotplug 相关功能的
nohz_balance_exit_idle(struct rq *rq) //fair.c
cpumask_clear_cpu(rq->cpu, nohz.idle_cpus_mask) //fair.c
atomic_dec(&_cpus);
do_idle //idle.c
cpuidle_idle_call //idle.c
do_idle //idle.c 若cpu是offline的才执⾏
tick_nohz_idle_stop_tick //tick-sched.c
__tick_nohz_idle_stop_tick //tick-sched.c
nohz_balance_enter_idle(int cpu) //fair.c
cpumask_t_cpu(cpu, nohz.idle_cpus_mask) //fair.c
atomic_inc(&_cpus);
cpu 进⼊idle时才会设置到 nohz.idle_cpus_mask，scheduler_tick()中发现cpu不是idle的就取消设置。_cpus 表⽰ nohz.idle_cpus_mask 中idle cpu的个数。
