Skip to main content
 首页 » 操作系统

Linux 调度器之负载均衡—框架分析

2022年07月19日29yxwkf

一、概述

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 
            __set_task_cpu(p, select_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..2 171682.441405: sched_wakeup_new: comm=RxComputationTh pid=9609 prio=120 target_cpu=002

(2) exec一个线程的时候

SYSCALL_DEFINE3(execve, const char __user *, filename, const char __user *const __user *, argv, const char __user *const __user *, envp) //fs/exec.c 
    do_execve 
        do_execveat_common 
            bprm_execve 
                sched_exec //core.c 
                    dest_cpu = current->sched_class->select_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..2 173370.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) 唤醒一个阻塞的进程

在上面的三个场景中都会调用 select_task_rq 来为task选择一个合适的CPU。

wake_up_process //core.c 主要用于各驱动中唤醒任务 
wake_up_state //用户空间锁、signal、ptrace、swait 
default_wake_function //waitqueue机制默认唤醒函数、select机制 
    try_to_wake_up //core.c 
        trace_sched_waking(p) //此时打印的cpu还是任务上次运行的cpu 
        cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags) 
        if (task_cpu(p) != cpu) { //新选出的cpu和任务p之前运行的cpu不是同一个cpu 
            wake_flags |= WF_MIGRATED; 
            set_task_cpu(p, cpu); 
            p->sched_class->migrate_task_rq(p, new_cpu); //migrate_task_rq_fair只是主要做一些虚拟时间的修正操作 
            __set_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 上 
                        send_call_function_single_ipi(cpu) //对目标cpu发生ipi中断() 
                            arch_send_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) //被唤醒者的调度类优先级比唤醒者高,走这个分支 
                            set_tsk_need_resched(curr); //curr是目标cpu上的curr 
                            set_preempt_need_resched(); //唤醒者和被唤醒者的目标cpu是同一个cpu,走这个分支,触发在下一个抢占点到来时重新调度 
                            smp_send_reschedule(cpu); //唤醒者和被唤醒者的目标cpu不是同一个cpu,走这个分支,通过IPI中断来通知目标cpu 
                                smp_cross_call(cpumask_of(cpu), IPI_RESCHEDULE); 
                                    scheduler_ipi() //目标cpu响应函数 
                                        preempt_fold_need_resched(); 
                                            set_preempt_need_resched(); //若判断需要调度,触发在下一个抢占点到来时重新调度,在目标cpu上 
                    p->state = TASK_RUNNING; 
                    trace_sched_wakeup(p); //trace打印的时候就已经唤醒了,此时打印出来的cpu就是目标cpu 
                     
 
//trace打印: 
<...>-813     [002] d..3 184883.820266: sched_waking: comm=Binder:1562_C pid=3075 prio=120 target_cpu=007 //上次运行在cpu7 
<...>-813     [002] d..4 184883.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)) 
            raise_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->cfs.nr_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 中 
                            send_call_function_single_ipi(cpu) 
                                arch_send_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; 
                                                    raise_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的任务的se->on_rq=1,dequeue se时没有置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(&nohz.nr_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_set_cpu(cpu, nohz.idle_cpus_mask) //fair.c 
                    atomic_inc(&nohz.nr_cpus);

cpu 进入idle时才会设置到 nohz.idle_cpus_mask,scheduler_tick()中发现cpu不是idle的就取消设置。nohz.nr_cpus 表示 nohz.idle_cpus_mask 中idle cpu的个数。


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