Scheduler -12- (Load Balance 1)

 

Load Balance

로드밸런싱에 진입하는 방법은 다음과 같이 5가지가 있다. passive 밸런싱은 태스크 상태의 변화에 따라 동작한다. periodic 밸런싱은 dynamic하게 변화하는 밸런싱 인터벌에 따라 호출되어 동작한다. Fork, Exec, Wake 밸런싱은 현재 동작시키고자하는 태스크의 대상 cpu를 결정하기 위해 idlest cpu를 찾아 동작하는 구조이다. 그리고 나머지 idle 밸런싱과 periodic 밸런싱은 busiest cpu를 찾고 그 cpu의 런큐에 위치한 태스크를 가져(pull migration)와서 동작시키는 구조이다.

  • Passive Balancing
    • Fork Balancing
      • 태스크 생성 시 태스크를 부모 태스크가 실행되던 cpu에서 수행할 지 아니면 다른 cpu로 마이그레이션할 지 결정한다.
      • 가능하면 캐시 친화력이 있는 cpu나 idle cpu를 선택하고 그렇지 않은 경우 cpu 로드가 적은 cpu의 런큐로 마이그레이션한다.
      • cpu 로드 산출 시 cpu_load[forkexec_idx] 또는 PELT의 최상위 cfs 런큐의 러너블 로드 평균 등을 이용한다.
      • wake_up_new_task() 함수에서 SD_BALANCE_FORK 플래그를 사용하여 호출한다.
    • Exec Balancing
      • 태스크 실행 시 태스크를 기존 실행되던 cpu에서 수행할 지 아니면 다른 cpu로 마이그레이션할 지 결정한다.
      • 가능하면 캐시 친화력이 있는 cpu나 idle cpu를 선택하고 그렇지 않은 경우 cpu 로드가 적은 cpu의 런큐로 마이그레이션한다.
      • cpu 로드 산출 시 cpu_load[forkexec_idx] 또는 PELT의 최상위 cfs 런큐의 러너블 로드 평균 등을 이용한다.
      • 다른 cpu로 마이그레이션 할 때 migrate 스레드를 사용한다.
      • sched_exec() 함수에서 SD_BALANCE_EXEC 플래그를 사용한다.
    • Wake Balancing
      • idle 태스크가 깨어났을 때 깨어난 cpu에서 수행할 지 아니면 다른 idle cpu로 마이그레이션할 지 결정한다.
      • cpu 로드 산출 시 cpu_load[wake_idx] 또는 PELT의 최상위 cfs 런큐의 러너블 로드 평균을 사용한다.
      • try_to_wake_up() 함수에서 SD_BALANCE_WAKE 플래그를 사용한다.
    • Idle Balancing
      • cpu가 idle 상태에 진입한 경우 가장 바쁜 스케줄 그룹의 가장 바쁜 cpu에서 태스크를 가져올지 결정한다.
      • cpu 로드 산출 시 cpu_load[newidle_idx] 또는 PELT의 최상위 cfs 런큐의 러너블 로드 평균을 사용한다.
      • idle_balance() 함수에서 SD_BALANCE_NEWIDLE 플래그를 사용한다.
  • Periodic Balancing
    • 주기적인 스케줄 틱을 통해 밸런싱 주기마다 리밸런싱 여부를 체크하여 결정한다.
      • 로드밸런스 주기는 1틱 ~ max_interval까지 동적으로 변한다.
    • SD_LOAD_BALANCE 플래그가 있는 스케줄 도메인의 스케줄 그룹에서 오버로드된 태스크를 찾아 현재 cpu로 pull 마이그레이션 하여 로드를 분산한다.
    • cpu 로드 산출 시 다음의 cpu_load[] 또는 PELT의 최상위 cfs 런큐의 러너블 로드 평균 등을 이용한다.
      • idle이 아닌 경우 cpu_load[busy_idx]
      • idle인 경우 cpu_load[idle_idx]
    • 스케줄 틱 -> raise softirq -> run_rebalance_domains() -> rebalance_domains() 호출 순서를 가진다.
    •  active 로드 밸런싱
      • 주기적인 스케줄 틱을 통해 리밸런싱 여부를 체크하여 결정하지만 특정 상황에서 몇 차례 실패하는 경우 방법으로 전환한다.
      • 특정 cpu의 워커 스레드에 의뢰하여 그 cpu 런큐에서 동작하는 curr를 제외한 하나의 태스크를 dest 런큐로 push 마이그레이션한다.

다음 그림은 CFS 로드 밸런스에 대한 주요 함수 흐름을 보여준다.

 

SCHED softirq

스케줄링 로드 밸런싱을 위한 sched softirq 호출

trigger_load_balance()

kernel/sched/fair.c”

/*
 * Trigger the SCHED_SOFTIRQ if it is time to do periodic load balancing.
 */
void trigger_load_balance(struct rq *rq)
{
        /* Don't need to rebalance while attached to NULL domain */
        if (unlikely(on_null_domain(rq)))
                return;

        if (time_after_eq(jiffies, rq->next_balance))
                raise_softirq(SCHED_SOFTIRQ);
#ifdef CONFIG_NO_HZ_COMMON
        if (nohz_kick_needed(rq))
                nohz_balancer_kick();
#endif
}

현재 시각이 밸런싱을 체크할 시각이 지났으면 sched 소프트인터럽트를 호출한다. 또한 nohz idle을 지원하는 경우 nohz kick이 필요한 경우 수행한다.

  • 코드 라인 7~8에서 스케줄링 도메인이 지정되지 않은 경우 함수를 빠져나간다.
  • 코드 라인 10~11에서 밸런싱 체크할 시각이 지난 경우 sched softirq를 호출한다.
  • 코드 라인 13~14에서 nohz kick이 필요한 경우 수행한다.

 

sched softirq 루틴

다음 그림은 스케줄 틱마다 active 로드밸런싱을 수행할 때 호출되는 함수들의 흐름을 보여준다.

 

run_rebalance_domains()

kernel/sched/fair.c

/*
 * run_rebalance_domains is triggered when needed from the scheduler tick.
 * Also triggered for nohz idle balancing (with nohz_balancing_kick set).
 */
static void run_rebalance_domains(struct softirq_action *h)
{
        struct rq *this_rq = this_rq();
        enum cpu_idle_type idle = this_rq->idle_balance ?
                                                CPU_IDLE : CPU_NOT_IDLE;

        rebalance_domains(this_rq, idle);

        /*
         * If this cpu has a pending nohz_balance_kick, then do the
         * balancing on behalf of the other idle cpus whose ticks are
         * stopped.
         */
        nohz_idle_balance(this_rq, idle);
}

CFS 로드 밸런스 softirq 루틴으로 호출될 때마다 스케줄 도메인이 로드밸런싱을 할 시간인 경우 이를 수행한다.

  • 코드 라인 8~11에서 현재 런큐의 idle_balance 값이 있는 경우 CPU_IDLE 타입(빠른 밸런싱 주기)으로 그 외에는 CPU_NOT_IDLE 타입으로 로드밸런스 루틴을 호출한다.
  • 코드 라인 18에서 nohz idle 밸런싱 루틴도 호출한다.

 

rebalance_domains()

kernel/sched/fair.c

/*
 * It checks each scheduling domain to see if it is due to be balanced,
 * and initiates a balancing operation if so.
 *
 * Balancing parameters are set up in init_sched_domains.
 */
static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
{
        int continue_balancing = 1;
        int cpu = rq->cpu;
        unsigned long interval;
        struct sched_domain *sd;
        /* Earliest time when we have to do rebalance again */
        unsigned long next_balance = jiffies + 60*HZ;
        int update_next_balance = 0;
        int need_serialize, need_decay = 0;
        u64 max_cost = 0;

        update_blocked_averages(cpu);

        rcu_read_lock();
        for_each_domain(cpu, sd) {
                /*
                 * Decay the newidle max times here because this is a regular
                 * visit to all the domains. Decay ~1% per second.
                 */
                if (time_after(jiffies, sd->next_decay_max_lb_cost)) {
                        sd->max_newidle_lb_cost =
                                (sd->max_newidle_lb_cost * 253) / 256;
                        sd->next_decay_max_lb_cost = jiffies + HZ;
                        need_decay = 1;
                }
                max_cost += sd->max_newidle_lb_cost;

                if (!(sd->flags & SD_LOAD_BALANCE))
                        continue;

                /*
                 * Stop the load balance at this level. There is another
                 * CPU in our sched group which is doing load balancing more
                 * actively.
                 */
                if (!continue_balancing) {
                        if (need_decay)
                                continue;
                        break;
                }
  • 코드 라인 14에서 밸런싱에 사용할 시각으로 최대값의 의미를 갖는 60초를 대입한다.
  • 코드 라인 19에서 블럭드 평균을 갱신한다.
  • 코드 라인 22에서 최상위 스케줄 도메인까지 순회한다.
  • 코드 라인 27~33에서 현재 시각이 만료 시각인 sd->next_decay_max_lb_cost를 지나친 경우다시 1초 후로 갱신하고, sd->max_newidle_lb_cost를 253/256 만큼 떨어뜨린다. 그런 후 이 값을 max_cost에 누적시킨다.
  • 코드 라인 35~36에서 스케줄 도메인에 SD_LOAD_BALANCE 플래그가 없는 경우 skip 한다.
  • 코드 라인 43~47에서 밸런싱에 성공하여 continue_balancing(초기값=1)이 설정되어 있지 않으면 need_decay 값에 따라 설정된 경우 skip하고 그렇지 않은 경우 루프를 벗어난다.

 

                interval = get_sd_balance_interval(sd, idle != CPU_IDLE);

                need_serialize = sd->flags & SD_SERIALIZE;
                if (need_serialize) {
                        if (!spin_trylock(&balancing))
                                goto out;
                }

                if (time_after_eq(jiffies, sd->last_balance + interval)) {
                        if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
                                /*
                                 * The LBF_DST_PINNED logic could have changed
                                 * env->dst_cpu, so we can't know our idle
                                 * state even if we migrated tasks. Update it.
                                 */
                                idle = idle_cpu(cpu) ? CPU_IDLE : CPU_NOT_IDLE;
                        }
                        sd->last_balance = jiffies;
                        interval = get_sd_balance_interval(sd, idle != CPU_IDLE);
                }
                if (need_serialize)
                        spin_unlock(&balancing);
out:
                if (time_after(next_balance, sd->last_balance + interval)) {
                        next_balance = sd->last_balance + interval;
                        update_next_balance = 1;
                }
        }
        if (need_decay) {
                /*
                 * Ensure the rq-wide value also decays but keep it at a
                 * reasonable floor to avoid funnies with rq->avg_idle.
                 */
                rq->max_idle_balance_cost =
                        max((u64)sysctl_sched_migration_cost, max_cost);
        }
        rcu_read_unlock();

        /*
         * next_balance will be updated only when there is a need.
         * When the cpu is attached to null domain for ex, it will not be
         * updated.
         */
        if (likely(update_next_balance))
                rq->next_balance = next_balance;
}
  • 코드 라인 1에서 스케줄 도메인의 밸런스 주기(jiffies)를 알아온다.
    • CPU_IDLE 상태가 아닌 CPU_NOT_IDLE, CPU_NEWLY_IDLE 상태인 경우 도메인의 밸런스 주기에 busy_factor(느린 밸런싱 주기)가 반영된다.
  • 코드 라인 3~7에서 모든 cpu에서 누마 밸런싱을 위해 요청이 온 경우 시리얼하게 처리를 하기 위해 락을 획득한다. 실패하는 경우skip 한다.
  • 코드 라인 9~20에서 현재 시각이 밸런싱 주기를 지나친 경우 로드 밸런싱을 수행한다. 그리고 밸런스 인터벌을 다시 갱신한다.
  • 코드 라인 24~27에서 next_balance은 각 도메인의 last_balance + interval 값 중 최소치를 갱신해둔다.
  • 코드 라인 29~36에서 need_decay가 설정된 경우 max_idle_balance_cost를 갱신한다.
  • 코드 라인 44~45에서 갱신해둔 최소 next_balance로 런큐의 next_balance를 설정한다.

 

get_sd_balance_interval()

kernel/sched/fair.c

static inline unsigned long
get_sd_balance_interval(struct sched_domain *sd, int cpu_busy)
{
        unsigned long interval = sd->balance_interval;

        if (cpu_busy)
                interval *= sd->busy_factor;

        /* scale ms to jiffies */
        interval = msecs_to_jiffies(interval);
        interval = clamp(interval, 1UL, max_load_balance_interval);

        return interval;
}

요청한 스케줄링 도메인의 밸런스 주기(jiffies)를 알아오는데 cpu_busy인 경우 로드밸런싱을 천천히 하도록 busy_factor를 곱하여 적용한다.

  • 코드 라인 4~7에서 스케줄 도메인의 밸런스 주기를 알아온 후 인수 cpu_busy가 설정된 경우 busy_factor(디폴트: 32)를 곱한다.
  • 코드 라인 10~13에서 ms 단위로된 밸런스 주기를 jiffies 단위로 변경하고 1 ~ max_load_balance_interval(초기값 0.1초)로 제한한 후 반환한다.

 

로드 밸런스

load_balance()

인수로 요청한 cpu가 스케줄 도메인내에서 밸런스 상태인지 체크한다. 만일 불균형을 이루면 태스크들을 이동시킨다.

kernel/sched/fair.c

/*
 * Check this_cpu to ensure it is balanced within domain. Attempt to move
 * tasks if there is an imbalance.
 */
static int load_balance(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd, enum cpu_idle_type idle,
                        int *continue_balancing)
{
        int ld_moved, cur_ld_moved, active_balance = 0;
        struct sched_domain *sd_parent = sd->parent;
        struct sched_group *group;
        struct rq *busiest;
        unsigned long flags;
        struct cpumask *cpus = this_cpu_cpumask_var_ptr(load_balance_mask);

        struct lb_env env = {
                .sd             = sd,
                .dst_cpu        = this_cpu,
                .dst_rq         = this_rq,
                .dst_grpmask    = sched_group_cpus(sd->groups),
                .idle           = idle,
                .loop_break     = sched_nr_migrate_break,
                .cpus           = cpus,
                .fbq_type       = all,
                .tasks          = LIST_HEAD_INIT(env.tasks),
        };

        /*
         * For NEWLY_IDLE load_balancing, we don't need to consider
         * other cpus in our group
         */
        if (idle == CPU_NEWLY_IDLE)
                env.dst_grpmask = NULL;

        cpumask_copy(cpus, cpu_active_mask);

        schedstat_inc(sd, lb_count[idle]);

redo:
        if (!should_we_balance(&env)) {
                *continue_balancing = 0;
                goto out_balanced;
        }

        group = find_busiest_group(&env);
        if (!group) {
                schedstat_inc(sd, lb_nobusyg[idle]);
                goto out_balanced;
        }

        busiest = find_busiest_queue(&env, group);
        if (!busiest) {
                schedstat_inc(sd, lb_nobusyq[idle]);
                goto out_balanced;
        }

        BUG_ON(busiest == env.dst_rq);
  • 코드 라인 16~26에서 로드밸런스 환경 정보를 담고 있는 env를 준비한다.
  • 코드 라인 32~33에서 cpu가 newidle 상태로 진입한 경우(CPU_NEWLY_IDLE) dst_grpmask에 null을 대입한다.
    • CPU_NEWLY_IDLE: idle 밸런싱을 통해 진입한 경우
    • CPU_NOT_IDLE: periodic 밸런싱을 통해 idle이 아닌 cpu에서 진입한 경우
    • CPU_IDLE: periodic 밸런싱을 통해 idle cpu에서 진입한 경우
  • 코드 라인 35에서 현재 cpu의 load_balance_mask에 active cpumask를 복사한다.
  • 코드 라인 37에서 스케줄링 도메인의 lb_count[idle] 카운터를 1 증가시킨다.
  • 코드 라인 40~43에서 이미 밸런싱 상태인 경우 out_balanced 레이블로 이동하여 함수를 빠져나간다.
  • 코드 라인 45~49에서 busiest 그룹이 없는 경우 로드밸런싱을 할 필요가 없으므로 스케줄 도메인의 lb_nobusyg[idle] 카운터를 1 증가 시키고 out_balanced 레이블로 이동하여 함수를 빠져 나간다.
  • 코드 라인 51~55에서 그룹내에서 busiest 런큐가 없는 경우 역시 로드밸런싱을 할 필요가 없으므로 스케줄 도메인의 lb_nobusyq[idle] 카운터를 1 증가 시키고 out_balanced 레이블로 이동하여 함수를 빠져 나간다.

 

        schedstat_add(sd, lb_imbalance[idle], env.imbalance);

        ld_moved = 0;
        if (busiest->nr_running > 1) {
                /*
                 * Attempt to move tasks. If find_busiest_group has found
                 * an imbalance but busiest->nr_running <= 1, the group is
                 * still unbalanced. ld_moved simply stays zero, so it is
                 * correctly treated as an imbalance.
                 */
                env.flags |= LBF_ALL_PINNED;
                env.src_cpu   = busiest->cpu;
                env.src_rq    = busiest;
                env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);

more_balance:
                raw_spin_lock_irqsave(&busiest->lock, flags);

                /*
                 * cur_ld_moved - load moved in current iteration
                 * ld_moved     - cumulative load moved across iterations
                 */
                cur_ld_moved = detach_tasks(&env);

                /*
                 * We've detached some tasks from busiest_rq. Every
                 * task is masked "TASK_ON_RQ_MIGRATING", so we can safely
                 * unlock busiest->lock, and we are able to be sure
                 * that nobody can manipulate the tasks in parallel.
                 * See task_rq_lock() family for the details.
                 */

                raw_spin_unlock(&busiest->lock);

                if (cur_ld_moved) {
                        attach_tasks(&env);
                        ld_moved += cur_ld_moved;
                }

                local_irq_restore(flags);

                if (env.flags & LBF_NEED_BREAK) {
                        env.flags &= ~LBF_NEED_BREAK;
                        goto more_balance;
                }
  • 코드 라인 1에서 스케줄링 도메인의 lb_imbalance[idle] stat에 env.imbalance 값을 추가한다.
  • 코드 라인 4~14에서 busiest 런큐에 1개 이상의 러닝 태스크가 있는 경우 env의 src_cpu에 busiest cpu 및 src_rq에 busiest 런큐를 대입한다. loop_max에는 최대 루프 수로 busiest의 러닝 태스크 수를 대입하되 최대 값을 sysctl_sched_nr_migrate(디폴트 32)로 제한한다.
  • 코드 라인 23에서 마이그레이션할 태스크들을 env->src_rq에서 detach하고 그 수를 cur_ld_moved에 대입한다.
    • cur_ld_moved
      • 현재 migration을 위해 detach한 태스크 수가 대입된다.
    • ld_moved
      • migration된 태스크 수가 누적된다.
  • 코드 라인 35~38에서 detach한 태스크들을 env->dst_rq에 attach하고 ld_moved에 그 수를 더한다.
  • 코드 라인 42~45에서 LBF_NEED_BREAK 플래그가 설정된 경우 이 플래그를 제거한 후 다시 more_balance 레이블로 다시 이동하여 더 처리하도록 한다.
    • loop가 loop_max 도달 전인 경우 loop_break 횟수에 도달하는 경우 loop_break 횟수를 누적시키고 다시 시도한다.
      • loop_break
        • sched_nr_migrate_break(디폴트로 32)부터 시작하여 32개씩 증가한다.
        • 인터럽트를 너무 오랫동안 막고 migration 하는 것을 방지하기 위해 중간에 한 번씩 인터럽트를 열고 닫아줄 목적으로 사용한다.
      • loop_max
        • sysctl_sched_nr_migrate(디폴트=32) 이하의 busiest 그룹에서 동작 중인 태스크 수가 설정된다.
        • “/proc/sys/kernel/sched_latency_ns”로 한 번의 밸런싱 호출을 처리할 때 migration 태스크의 최대 수를 제한할 수 있다.

 

.               /*
                 * Revisit (affine) tasks on src_cpu that couldn't be moved to
                 * us and move them to an alternate dst_cpu in our sched_group
                 * where they can run. The upper limit on how many times we
                 * iterate on same src_cpu is dependent on number of cpus in our
                 * sched_group.
                 *
                 * This changes load balance semantics a bit on who can move
                 * load to a given_cpu. In addition to the given_cpu itself
                 * (or a ilb_cpu acting on its behalf where given_cpu is
                 * nohz-idle), we now have balance_cpu in a position to move
                 * load to given_cpu. In rare situations, this may cause
                 * conflicts (balance_cpu and given_cpu/ilb_cpu deciding
                 * _independently_ and at _same_ time to move some load to
                 * given_cpu) causing exceess load to be moved to given_cpu.
                 * This however should not happen so much in practice and
                 * moreover subsequent load balance cycles should correct the
                 * excess load moved.
                 */
                if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) {

                        /* Prevent to re-select dst_cpu via env's cpus */
                        cpumask_clear_cpu(env.dst_cpu, env.cpus);

                        env.dst_rq       = cpu_rq(env.new_dst_cpu);
                        env.dst_cpu      = env.new_dst_cpu;
                        env.flags       &= ~LBF_DST_PINNED;
                        env.loop         = 0;
                        env.loop_break   = sched_nr_migrate_break;

                        /*
                         * Go back to "more_balance" rather than "redo" since we
                         * need to continue with same src_cpu.
                         */
                        goto more_balance;
                }

                /*
                 * We failed to reach balance because of affinity.
                 */
                if (sd_parent) {
                        int *group_imbalance = &sd_parent->groups->sgc->imbalance;

                        if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0)
                                *group_imbalance = 1;
                }

                /* All tasks on this runqueue were pinned by CPU affinity */
                if (unlikely(env.flags & LBF_ALL_PINNED)) {
                        cpumask_clear_cpu(cpu_of(busiest), cpus);
                        if (!cpumask_empty(cpus)) {
                                env.loop = 0;
                                env.loop_break = sched_nr_migrate_break;
                                goto redo;
                        }
                        goto out_all_pinned;
                }
        }
  • 코드 라인 20~36에서 LBF_DST_PINNED 플래그가 설정되어 목적하는(dest) cpu로 마이그레이션을 할 수 없는 상황이다. 이 떄 로드밸런싱이 가능한 cpu들 중 dest cpu의 비트를 클리어하여 다시 dst cpu가 선택되지 않도록 막는다. 그리고 loop 카운터를 리셋한 후 다시 처음부터 시작하도록 more_balance 레이블로 이동한다.
  • 코드 라인 41~46에서 LBF_SOME_PINNED 플래그가 설정되어 현재 그룹에서 일부 태스크의 마이그레이션이 제한된 경우이다. 이 때 부모 스케줄링 도메인의 첫 스케줄 그룹의 imbalance 값을 1로 변경한다.
  • 코드 라인 49~57에서 낮은 확률로 LBF_ALL_PINNED 플래그가 설정되어 현재 런큐에 있는 모든 태스크의 마이그레이션이 불가능한 상태이다. 이러한 경우 로드밸런싱이 가능한 cpu들 중 busiest cpu의 비트를 클리어한다. 로드밸런싱이 가능한 cpu가 하나도 남지 않는 경우 out_all_pinned 레이블로 이동한하고 함수를 빠져나간다. 만일 처리할 cpu가 남아 있는 경우 loop 카운터를 리셋하고 다시 redo 레이블로 이동하여 계속 처리하게 한다.

 

.       if (!ld_moved) {
                schedstat_inc(sd, lb_failed[idle]);
                /*
                 * Increment the failure counter only on periodic balance.
                 * We do not want newidle balance, which can be very
                 * frequent, pollute the failure counter causing
                 * excessive cache_hot migrations and active balances.
                 */
                if (idle != CPU_NEWLY_IDLE)
                        sd->nr_balance_failed++;

                if (need_active_balance(&env)) {
                        raw_spin_lock_irqsave(&busiest->lock, flags);

                        /* don't kick the active_load_balance_cpu_stop,
                         * if the curr task on busiest cpu can't be
                         * moved to this_cpu
                         */
                        if (!cpumask_test_cpu(this_cpu,
                                        tsk_cpus_allowed(busiest->curr))) {
                                raw_spin_unlock_irqrestore(&busiest->lock,
                                                            flags);
                                env.flags |= LBF_ALL_PINNED;
                                goto out_one_pinned;
                        }

                        /*
                         * ->active_balance synchronizes accesses to
                         * ->active_balance_work.  Once set, it's cleared
                         * only after active load balance is finished.
                         */
                        if (!busiest->active_balance) {
                                busiest->active_balance = 1;
                                busiest->push_cpu = this_cpu;
                                active_balance = 1;
                        }
                        raw_spin_unlock_irqrestore(&busiest->lock, flags);

                        if (active_balance) {
                                stop_one_cpu_nowait(cpu_of(busiest),
                                        active_load_balance_cpu_stop, busiest,
                                        &busiest->active_balance_work);
                        }

                        /*
                         * We've kicked active balancing, reset the failure
                         * counter.
                         */
                        sd->nr_balance_failed = sd->cache_nice_tries+1;
                }
        } else
                sd->nr_balance_failed = 0;
  • 코드 라인 1~2에서 마이그레이션한 태스크가 하나도 없는 경우 스케줄링 도메인의 lb_failed[idle] 카운터를 1 증가시킨다.
  • 코드 라인 9~10에서 CPU_NEWLY_IDLE이 아닌 경우 스케줄링 도메인의 br_balance_failed 카운터를 1 증가시킨다.
  • 코드 라인 12에서 active 로드 밸런싱이 필요한 경우
    • nr_balance_failed > cache_nice_tries+2인 경우 true가 된다.
  • 코드 라인 19~25에서 현재 cpu가 busiest의 현재 태스크에 허가된 cpu가 아닌 경우 다른 태스크들도 현재 cpu에 허가되지 않았다고 간주하여 밸런싱을 하지 않는다. LBF_ALL_PINNED 플래그를 추가한 후 out_one_pinned 레이블로 이동하여 함수를 빠져나간다.
  • 코드 라인 32~36에서 busiest 런큐의 active_balance를 1로 설정하고 마이그레이션 할 cpu인 push_cpu로 push_cpu로 요청한 this_cpu(dest cpu)를 지정한다.
  • 코드 라인 39~42에서 active 밸런스를 처음 동작 시켰으면 busiest cpu가 현재 cpu인 경우에 한해 active 밸런싱을 하라고 busiest cpu에 스케줄 의뢰한다.
    • bottom-half로 동작하는 워크큐를 사용하여 active_balance_work 워크를 busiest의 cpu를 사용하는 워커스레드에 스케줄하게 한다.
    • 워커스레드는 active_load_balance_cpu_stop() 함수를 호출하는데 busiest cpu에서 동작 중인 태스크가 2개 이상일 때 현재 동작중인 태스크가 아닌 can_migrate_task() 함수가 알려주는 하나의 태스크를 선택하여 push_cpu 쪽으로 마이그레이션 한다.
  • 코드 라인 48에서 스케줄링 도메인의 nr_balance_failed에 cache_nice_tries+1 값을 대입한다.
  • 코드 라인 50~51에서 로드 밸런스로 옮겨진 태스크가 있는 경우 스케줄링 도메인의 nr_balance_failed 통계를 0으로 리셋한다.

 

        if (likely(!active_balance)) {
                /* We were unbalanced, so reset the balancing interval */
                sd->balance_interval = sd->min_interval;
        } else {
                /*
                 * If we've begun active balancing, start to back off. This
                 * case may not be covered by the all_pinned logic if there
                 * is only 1 task on the busy runqueue (because we don't call
                 * detach_tasks).
                 */
                if (sd->balance_interval < sd->max_interval)
                        sd->balance_interval *= 2;
        }

        goto out;

out_balanced:
        /*
         * We reach balance although we may have faced some affinity
         * constraints. Clear the imbalance flag if it was set.
         */
        if (sd_parent) {
                int *group_imbalance = &sd_parent->groups->sgc->imbalance;

                if (*group_imbalance)
                        *group_imbalance = 0;
        }

out_all_pinned:
        /*
         * We reach balance because all tasks are pinned at this level so
         * we can't migrate them. Let the imbalance flag set so parent level
         * can try to migrate them.
         */
        schedstat_inc(sd, lb_balanced[idle]);

        sd->nr_balance_failed = 0;

out_one_pinned:
        /* tune up the balancing interval */
        if (((env.flags & LBF_ALL_PINNED) &&
                        sd->balance_interval < MAX_PINNED_INTERVAL) ||
                        (sd->balance_interval < sd->max_interval))
                sd->balance_interval *= 2;

        ld_moved = 0;
out:
        return ld_moved;
}
  • 코드 라인 1~3에서 높은 확률로 active_balance가 실행된 적이 없는 경우 스케줄링 도메인의 밸런스 주기에 최소 주기를 대입한다.
  • 코드 라인 4~13에서 그렇지 않은 경우 밸런스 주기가 최대 주기값이 아닌 경우 두 배로 높인다.
  • 코드 라인 15에서 함수를 빠져나가도록 out 레이블로 이동한다.
  • 코드 라인 22~27에서 부모 스케줄링 도메인이 있는 경우 그 스케줄링 그룹의 imbalance 값을 0으로 리셋한다.
  • 코드 라인 35에서 스케줄링 도메인의 lb_balanced[idle] 카운터를 1 증가시키고 nr_balance_failed를 0으로 리셋한다.
  • 코드 라인 39~44에서 LBF_ALL_PINNED 플래그가 설정되었고 밸런스 주기가 MAX_PINNED_INTERVAL(512) 및 max_interval 이내인 경우 밸런스 주기를 2배로 높인다.
  • 코드 라인 48에서 로드밸런싱으로 인해 마이그레이션한 태스크 수를 반환한다.

 

should_we_balance()

kernel/sched/fair.c

static int should_we_balance(struct lb_env *env)
{
        struct sched_group *sg = env->sd->groups;
        struct cpumask *sg_cpus, *sg_mask;
        int cpu, balance_cpu = -1;

        /*
         * In the newly idle case, we will allow all the cpu's
         * to do the newly idle load balance.
         */
        if (env->idle == CPU_NEWLY_IDLE)
                return 1;

        sg_cpus = sched_group_cpus(sg);
        sg_mask = sched_group_mask(sg);
        /* Try to find first idle cpu */
        for_each_cpu_and(cpu, sg_cpus, env->cpus) {
                if (!cpumask_test_cpu(cpu, sg_mask) || !idle_cpu(cpu))
                        continue;

                balance_cpu = cpu;
                break;
        }

        if (balance_cpu == -1)
                balance_cpu = group_balance_cpu(sg);

        /*
         * First idle cpu or the first cpu(busiest) in this sched group
         * is eligible for doing load balancing at this and above domains.
         */
        return balance_cpu == env->dst_cpu;
}

로드 밸런스를 하여도 되는지 여부를 반환한다.

  • 코드 라인 11~12에서 CPU_NEWLY_IDLE 상태인 경우 항상 true(1)를 반환하여 로드밸런싱을 시도하게 한다.
  • 코드 라인 14에서 스케줄 그룹에 속한 cpumask를 가져온다.
  • 코드 라인 15에서 스케줄 그룹 capacity에 기록된 cpumask를 가져온다.
  • 코드 라인 17~23에서 env에서 요청한 cpu와 스케줄링 그룹에 속한 cpu 둘 다에 속한 cpu를 순회하며 idle cpu를 찾는다.
  • 코드 라인 25~26에서 idle cpu를 찾지 못한 경우 스케줄링 그룹의 첫 번째 cpu를 balance_cpu로 대입한다.
  • 코드 라인 32에서 ilde cpu이거나 스케줄링 그룹의 첫 번째 cpu인 balance_cpu가 env의 대상 cpu인 경우에 한해 true(1)를 반환한다.

 

가장 바쁜 스케줄 그룹 찾기

find_busiest_group()

요청한 로드밸런스 환경을 사용하여 가장 바쁜 스케줄 그룹을 찾아온다.

kernel/sched/fair.c

/**
 * find_busiest_group - Returns the busiest group within the sched_domain
 * if there is an imbalance. If there isn't an imbalance, and
 * the user has opted for power-savings, it returns a group whose
 * CPUs can be put to idle by rebalancing those tasks elsewhere, if
 * such a group exists.
 *
 * Also calculates the amount of weighted load which should be moved
 * to restore balance.
 *
 * @env: The load balancing environment.
 *
 * Return:      - The busiest group if imbalance exists.
 *              - If no imbalance and user has opted for power-savings balance,
 *                 return the least loaded group whose CPUs can be
 *                 put to idle by rebalancing its tasks onto our group.
 */
static struct sched_group *find_busiest_group(struct lb_env *env)
{
        struct sg_lb_stats *local, *busiest;
        struct sd_lb_stats sds;

        init_sd_lb_stats(&sds);

        /*
         * Compute the various statistics relavent for load balancing at
         * this level.
         */
        update_sd_lb_stats(env, &sds);
        local = &sds.local_stat;
        busiest = &sds.busiest_stat;

        if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
            check_asym_packing(env, &sds))
                return sds.busiest;

        /* There is no busy sibling group to pull tasks from */
        if (!sds.busiest || busiest->sum_nr_running == 0)
                goto out_balanced;

        sds.avg_load = (SCHED_CAPACITY_SCALE * sds.total_load)
                                                / sds.total_capacity;

        /*
         * If the busiest group is imbalanced the below checks don't
         * work because they assume all things are equal, which typically
         * isn't true due to cpus_allowed constraints and the like.
         */
        if (busiest->group_type == group_imbalanced)
                goto force_balance;

        /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
        if (env->idle == CPU_NEWLY_IDLE && local->group_has_free_capacity &&
            !busiest->group_has_free_capacity)
                goto force_balance;
  • 코드 라인 23에서 로드 밸런스에 사용하는 스케줄 도메인 통계 sds를 초기화한다.
  • 코드 라인 29에서 로드 밸런스를 위해 스케줄 도메인 통계 sds를 갱신한다.
  • 코드 라인 33~35에서 cpu가 CPU_IDLE 상태로 요청하였거나 CPU_NEWLY_IDLE 상태이면서 powerpc 아키텍처에서 사용하는 asymmetric 패킹이 필요한 경우 busiest 스케줄 그룹을 반환한다.
  • 코드 라인 38~39에서 busiest 스케줄 그룹이 없거나 동작 중인 cpu가 없으면 out_balanced로 이동하여 null을 반환한다.
  • 코드 라인 41~42에서 total_load / total_capacity를 SCHED_CAPACITY_SCALE(1024) 정수 요율로 avg_load를 산출한다.

 

        /*
         * If the local group is busier than the selected busiest group
         * don't try and pull any tasks.
         */
        if (local->avg_load >= busiest->avg_load)
                goto out_balanced;

        /*
         * Don't pull any tasks if this group is already above the domain
         * average load.
         */
        if (local->avg_load >= sds.avg_load)
                goto out_balanced;

        if (env->idle == CPU_IDLE) {
                /*
                 * This cpu is idle. If the busiest group is not overloaded
                 * and there is no imbalance between this and busiest group
                 * wrt idle cpus, it is balanced. The imbalance becomes
                 * significant if the diff is greater than 1 otherwise we
                 * might end up to just move the imbalance on another group
                 */
                if ((busiest->group_type != group_overloaded) &&
                                (local->idle_cpus <= (busiest->idle_cpus + 1)))
                        goto out_balanced;
        } else {
                /*
                 * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
                 * imbalance_pct to be conservative.
                 */
                if (100 * busiest->avg_load <=
                                env->sd->imbalance_pct * local->avg_load)
                        goto out_balanced;
        }

force_balance:
        /* Looks like there is an imbalance. Compute it */
        calculate_imbalance(env, &sds);
        return sds.busiest;

out_balanced:
        env->imbalance = 0;
        return NULL;
}
  • 코드 라인 6~7에서 busiest 스케줄 그룹이 group_imbalanced 그룹 타입인 경우 곧장 force_balance 레이블로 이동하여 imbalance를 산출한다.
  • 코드 라인 13~14에서 로컬 avg_load가 sds 값 이상인 경우 out_balanced 레이블로 이동한다.
  • 코드 라인 16~26에서 CPU_IDLE 상태이고 busiest 그룹 타입이 group_overloaded가 아니면서 로컬의 idle cpu 수가 busiest 그룹의 idle cpu 수 보다 2 이상 작은 경우 이미 밸런스된 상태이므로 out_balanced 레이블로 이동한다.
  • 코드 라인 27~35에서 CPU_NEWLY_IDLE 및 CPU_NOT_IDLE 상태인 경우 평균 값 100의 비율을 적용한 busiest의 평균 로드보다 스케줄링 도메인의 imbalance_pct를 적용한 로컬의 평균 로드가 같거나 큰 경우 밸런스된 상태이므로 out_balanced 레이블로 이동한다.
  • 코드 라인 39~40에서 imbalance를 산출하고 busiest 스케줄 그룹을 반환한다.

 

update_sd_pick_busiest()

kernel/sched/fair.c

/**
 * update_sd_pick_busiest - return 1 on busiest group
 * @env: The load balancing environment.
 * @sds: sched_domain statistics
 * @sg: sched_group candidate to be checked for being the busiest
 * @sgs: sched_group statistics
 *
 * Determine if @sg is a busier group than the previously selected
 * busiest group.
 *
 * Return: %true if @sg is a busier group than the previously selected
 * busiest group. %false otherwise.
 */
static bool update_sd_pick_busiest(struct lb_env *env,
                                   struct sd_lb_stats *sds,
                                   struct sched_group *sg,
                                   struct sg_lb_stats *sgs)
{
        struct sg_lb_stats *busiest = &sds->busiest_stat;

        if (sgs->group_type > busiest->group_type)
                return true;

        if (sgs->group_type < busiest->group_type)
                return false;

        if (sgs->avg_load <= busiest->avg_load)
                return false;

        /* This is the busiest node in its class. */
        if (!(env->sd->flags & SD_ASYM_PACKING))
                return true;

        /*
         * ASYM_PACKING needs to move all the work to the lowest
         * numbered CPUs in the group, therefore mark all groups
         * higher than ourself as busy.
         */
        if (sgs->sum_nr_running && env->dst_cpu < group_first_cpu(sg)) {
                if (!sds->busiest)
                        return true;

                if (group_first_cpu(sds->busiest) > group_first_cpu(sg))
                        return true;
        }

        return false;
}

요청한 스케줄 그룹이 기존에 선택했었던 busiest 스케줄 그룹보다 더 바쁜지 여부를 반환한다. (1) 그룹 타입 비교, 2) 그룹 타입 동일 시 로드 값 비교)

  • 코드 라인 21~22에서 요청한 그룹 타입이 busiest 그룹 타입보다 큰 경우 요청한 그룹 타입이 더 바쁘다고 판단하여 true(1)를 반환한다.
    • 그룹 타입은 3 가지로 group_other(0), group_imbalanced(1) 및 group_overloaded(2)가 있다.
  • 코드 라인 24~25에서 요청한 그룹 타입이 busiest 그룹 타입보다 작은 경우 요청한 그룹 타입이 더 바쁘지 않다고 판단하여 false(0)를 반환한다.
  • 코드 라인 27~28에서 동일한 그룹 타입인 경우는 평균 로드를 비교하여 요청한 그룹이 기존 busiest 그룹보다 작거나 같으면 false(0)를 반환한다.
  • 코드 라인 31~32에서 스케줄 도메인이 SD_ASYM_PACKING(현재 powerpc 아키텍처에서만 사용) 플래그를 사용하지 않는 경우 true(1)를 반환한다.
  • 코드 라인 39에서 SD_ASYM_PACKING 플래그를 사용한 경우 powerpc의 경우 dest cpu 번호가 요청한 스케줄 그룹의 첫 번째 cpu보다 작은 경우
  • 코드 라인 40~41에서 이미 지정된 busiest 스케줄 그룹이 없는 경우에는 true(1)를 반환한다.
  • 코드 라인 43~44에서 스케줄 도메인 내에서 busiest 스케줄 그룹의 첫 번째 cpu 번호가 요청한 스케줄 그룹의 첫 cpu 번호보다 큰 경우 true(1)를 반환한다.
  • 코드 라인 46에서 그 외의 경우 요청한 스케줄 그룹의 cpu가 busiest 그룹보다 더 높은 번호에서 동작하므로 false(0)을 반환한다.

 

스케줄링 도메인 로드밸런스 통계 갱신

update_sd_lb_stats()

kernel/sched/fair.c

/**
 * update_sd_lb_stats - Update sched_domain's statistics for load balancing.
 * @env: The load balancing environment.
 * @sds: variable to hold the statistics for this sched_domain.
 */
static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sds)
{
        struct sched_domain *child = env->sd->child;
        struct sched_group *sg = env->sd->groups;
        struct sg_lb_stats tmp_sgs;
        int load_idx, prefer_sibling = 0;
        bool overload = false;

        if (child && child->flags & SD_PREFER_SIBLING)
                prefer_sibling = 1;

        load_idx = get_sd_load_idx(env->sd, env->idle);

        do {
                struct sg_lb_stats *sgs = &tmp_sgs;
                int local_group;

                local_group = cpumask_test_cpu(env->dst_cpu, sched_group_cpus(sg));
                if (local_group) {
                        sds->local = sg;
                        sgs = &sds->local_stat;

                        if (env->idle != CPU_NEWLY_IDLE ||
                            time_after_eq(jiffies, sg->sgc->next_update))
                                update_group_capacity(env->sd, env->dst_cpu);
                }

                update_sg_lb_stats(env, sg, load_idx, local_group, sgs,
                                                &overload);

                if (local_group)
                        goto next_group;
  • 코드 라인 14~15에서 child 스케줄링 도메인에 SD_PREFER_SIBLING 플래그(DIE 토플로지에서 사용)가 설정된 경우 prefer_sibling=1로 설정한다.
  • 코드 라인 17에서 요청한 cpu idle 타입에 따른 스케줄 도메인에 지정된 cpu 로드 인덱스 값을 알아온다.
  • 코드 라인 19~26에서 스케줄 그룹에 dst_cpu가 포함되어 있는 경우 로컬 stat을 선택한다.
  • 코드 라인 28~30에서 cpu idle 타입이 CPU_IDLE 또는 CPU_NOT_IDLE 타입이거나 현재 시각이 next_update를 이미 지난 경우 그룹 capacity를 갱신한다.
  • 코드 라인 33~34에서 스케줄 그룹의 로드밸런스 stat을 갱신한다.

 

                /*
                 * In case the child domain prefers tasks go to siblings
                 * first, lower the sg capacity factor to one so that we'll try
                 * and move all the excess tasks away. We lower the capacity
                 * of a group only if the local group has the capacity to fit
                 * these excess tasks, i.e. nr_running < group_capacity_factor. The
                 * extra check prevents the case where you always pull from the
                 * heaviest group when it is already under-utilized (possible
                 * with a large weight task outweighs the tasks on the system).
                 */
                if (prefer_sibling && sds->local &&
                    sds->local_stat.group_has_free_capacity) {
                        sgs->group_capacity_factor = min(sgs->group_capacity_factor, 1U);
                        sgs->group_type = group_classify(sg, sgs);
                }

                if (update_sd_pick_busiest(env, sds, sg, sgs)) {
                        sds->busiest = sg;
                        sds->busiest_stat = *sgs;
                }

next_group:
                /* Now, start updating sd_lb_stats */
                sds->total_load += sgs->group_load;
                sds->total_capacity += sgs->group_capacity;

                sg = sg->next;
        } while (sg != env->sd->groups);

        if (env->sd->flags & SD_NUMA)
                env->fbq_type = fbq_classify_group(&sds->busiest_stat);

        if (!env->sd->parent) {
                /* update overload indicator if we are at root domain */
                if (env->dst_rq->rd->overload != overload)
                        env->dst_rq->rd->overload = overload;
        }

}
  • 코드 라인 11~15에서 prefer_sibling=1이 설정되었고 sds의 로컬 stat의 group_has_free_capacity도 설정된 경우 스케줄 그룹 stat의 group_capacity_factor를 갱신하되 1을 초과하지 않도록 제한한다.
  • 코드 라인 17~20에서 스케줄 도메인내에서 가장 바쁜 스케줄 그룹의 stat을 갱신한다.
  • 코드 라인 24~25에서 도메인의 total_load 및 total_capacity에 그룹의 group_load 및 group_capacity를 추가한다.
  • 코드 라인 27~28에서 다음 스케줄 그룹을 순회한다. (한 바퀴 돌면 빠져나간다)
  • 코드 라인 30~31에서 누마 스케줄 도메인인 경우 fbq  타입을 알아온다.
  • 코드 라인 33~37에서 부모 도메인이 없는 최상위 도메인이고 dst 런큐의 루트도메인에 overload를 갱신한다.

 

get_sd_load_idx()

kernel/sched/fair.c

/**
 * get_sd_load_idx - Obtain the load index for a given sched domain.
 * @sd: The sched_domain whose load_idx is to be obtained.
 * @idle: The idle status of the CPU for whose sd load_idx is obtained.
 *
 * Return: The load index.
 */
static inline int get_sd_load_idx(struct sched_domain *sd,
                                        enum cpu_idle_type idle)
{
        int load_idx;

        switch (idle) {
        case CPU_NOT_IDLE:
                load_idx = sd->busy_idx;
                break;

        case CPU_NEWLY_IDLE:
                load_idx = sd->newidle_idx;
                break;
        default:
                load_idx = sd->idle_idx;
                break;
        }

        return load_idx;
}

cpu idle 타입에 따른 cpu 로드 인덱스 값을 반환한다. 이 인덱스로 cpu_load[] 값을 읽어올 때 사용한다.

  • 코드 라인 13~16에서 CPU_NOT_IDLE 타입인 경우 sd->busy_idx 값을 반환한다.
  • 코드 라인 18~20에서 CPU_NEWLY_IDLE 타입인 경우 sd->newidle_idx 값을 반환한다.
  • 코드 라인 21~23에서 그 외(CPU_IDLE) 타입인 경우 sd->idle_idx 값을 반환한다.

 

fbq_classify_group()

kernel/sched/fair.c

#ifdef CONFIG_NUMA_BALANCING
static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
{
        if (sgs->sum_nr_running > sgs->nr_numa_running)
                return regular;
        if (sgs->sum_nr_running > sgs->nr_preferred_running)
                return remote;
        return all;
}
#else
static inline enum fbq_type fbq_classify_group(struct sg_lb_stats *sgs)
{
        return all;
}
#endif

NUMA 시스템에서는 regular(0), remote(1), all(2) 타입을 구분하여 반환한다. 단 UMA 시스템에서는 all(2) 만을 반환한다.

 

fbq_classify_rq()

kernel/sched/fair.c

#ifdef CONFIG_NUMA_BALANCING
static inline enum fbq_type fbq_classify_rq(struct rq *rq)
{
        if (rq->nr_running > rq->nr_numa_running)
                return regular;
        if (rq->nr_running > rq->nr_preferred_running)
                return remote;
        return all;
}
#else
static inline enum fbq_type fbq_classify_rq(struct rq *rq)
{
        return regular;
}
#endif

NUMA 시스템에서는 regular(0), remote(1), all(2) 타입을 구분하여 반환한다. 단 UMA 시스템에서는 regular(0) 만을 반환한다.

 

스케줄링 그룹 로드밸런스 통계 갱신

update_sg_lb_stats()

kernel/sched/fair.c -1/2-

/**
 * update_sg_lb_stats - Update sched_group's statistics for load balancing.
 * @env: The load balancing environment.
 * @group: sched_group whose statistics are to be updated.
 * @load_idx: Load index of sched_domain of this_cpu for load calc.
 * @local_group: Does group contain this_cpu.
 * @sgs: variable to hold the statistics for this group.
 * @overload: Indicate more than one runnable task for any CPU.
 */
static inline void update_sg_lb_stats(struct lb_env *env,
                        struct sched_group *group, int load_idx,
                        int local_group, struct sg_lb_stats *sgs,
                        bool *overload)
{
        unsigned long load;
        int i;

        memset(sgs, 0, sizeof(*sgs));

        for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
                struct rq *rq = cpu_rq(i);

                /* Bias balancing toward cpus of our domain */
                if (local_group)
                        load = target_load(i, load_idx);
                else
                        load = source_load(i, load_idx);

                sgs->group_load += load;
                sgs->sum_nr_running += rq->cfs.h_nr_running;

                if (rq->nr_running > 1)
                        *overload = true;

#ifdef CONFIG_NUMA_BALANCING
                sgs->nr_numa_running += rq->nr_numa_running;
                sgs->nr_preferred_running += rq->nr_preferred_running;
#endif
                sgs->sum_weighted_load += weighted_cpuload(i);
                if (idle_cpu(i))
                        sgs->idle_cpus++;
        }
  • 코드 라인 18에서 출력 인수로 지정된 sgs를 0으로 초기화한다.
  • 코드 라인 20에서 스케줄 그룹에 속한 cpu에 한해 요청한 cpu들을 순회한다.
  • 코드 라인 24~27에서 인수로 주어진 load_idx를 사용하여 로드 값을 알아온다. 인수 local_group이 선택된 경우 타겟에는 진보적인 로드 값을 알아오고 그렇지 않은 경우 소스에는 보수적인 로드 값을 알아온다.
  • 코드 라인 29~30에서 sgs->group_load에 로드 값을 더한다. sgs->sum_nr_running에는 엔티티들의 수를 모두 더한다.
  • 코드 라인 32~33에서 런큐에서 동작 중인 태스크가 1개 이상인 경우 출력 인수 overload에는 true(1)를 대입한다.
  • 코드 라인 35~38에서 누마 관련한 stat들도 갱신한다.
  • 코드 라인 39에서 sgs->sum_weighted_load에 순회중인 cpu의 최상위 cfs 런큐의 러너블 로드 평균을 추가한다.

 

kernel/sched/fair.c – 2/2

        /* Adjust by relative CPU capacity of the group */
        sgs->group_capacity = group->sgc->capacity;
        sgs->avg_load = (sgs->group_load*SCHED_CAPACITY_SCALE) / sgs->group_capacity;

        if (sgs->sum_nr_running)
                sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;

        sgs->group_weight = group->group_weight;
        sgs->group_capacity_factor = sg_capacity_factor(env, group);
        sgs->group_type = group_classify(group, sgs);

        if (sgs->group_capacity_factor > sgs->sum_nr_running)
                sgs->group_has_free_capacity = 1;
}
  • 코드 라인 2에서 sgs->group_capacity에 스케줄 그룹의 capacity 값을 대입한다.
  • 코드 라인 3에서 sgs->avg_load에는 sgs에 모은 그룹 로드에 scale이 적용하고 capacity로 나눈다.
  • 코드 라인 5~6에서 모두 합한 스케줄 엔티티 수가 1개 이상인 경우 sgs->load_per_task에 태스크별 로드를 산출한다.
  • 코드 라인 8에서 sgs->group_weight에 스케줄 그룹의 weight를 대입한다.
  • 코드 라인 9에서 sgs->group_capacity_factor에 스케줄 그룹의 capacity 요율을 산출한다.
    • cortex-a7과 cortex-a15 두 종류가 동시에 사용될 때 각 capacity 요율은 다음과 같다.
      • 430 (0.41) -> cortex-a7
      • 1535 (1.49) -> cortex-a15
  • 코드 라인 10에서 sgs->group_type에 스케줄 그룹의 그룹 타입을 산출한다.
  • 코드 라인 12~13에서 그룹 capacity 요율이 수행 중인 엔티티 합보다 큰 경우 sgs->group_has_free_capacity를 1로 설정한다.

 

source_load()

kernel/sched/fair.c

/*
 * Return a low guess at the load of a migration-source cpu weighted
 * according to the scheduling class and "nice" value.
 *
 * We want to under-estimate the load of migration sources, to
 * balance conservatively.
 */
static unsigned long source_load(int cpu, int type)
{
        struct rq *rq = cpu_rq(cpu);
        unsigned long total = weighted_cpuload(cpu);

        if (type == 0 || !sched_feat(LB_BIAS))
                return total;

        return min(rq->cpu_load[type-1], total);
}

요청한 cpu의 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 작은 로드 값을 반환한다. 보수적으로 로드 값을 평가한다.

  • LB_BIAS feature는 디폴트로 true이다.

 

target_load()

kernel/sched/fair.c

/*
 * Return a high guess at the load of a migration-target cpu weighted
 * according to the scheduling class and "nice" value.
 */
static unsigned long target_load(int cpu, int type)
{
        struct rq *rq = cpu_rq(cpu);
        unsigned long total = weighted_cpuload(cpu);

        if (type == 0 || !sched_feat(LB_BIAS))
                return total;

        return max(rq->cpu_load[type-1], total);
}

요청한 cpu의 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 큰 로드 값을 반환한다. 적극적인 로드 값을 평가한다.

 

weighted_cpuload()

kernel/sched/fair.c

/* Used instead of source_load when we know the type == 0 */
static unsigned long weighted_cpuload(const int cpu)
{
        return cpu_rq(cpu)->cfs.runnable_load_avg;
}

요청한 cpu의 최상위 cfs 런큐의 러너블 로드 평균을 반환한다.

 

불균형 산출

calculate_imbalance()

kernel/sched/fair.c

/**
 * calculate_imbalance - Calculate the amount of imbalance present within the
 *                       groups of a given sched_domain during load balance.
 * @env: load balance environment
 * @sds: statistics of the sched_domain whose imbalance is to be calculated.
 */
static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
{
        unsigned long max_pull, load_above_capacity = ~0UL;
        struct sg_lb_stats *local, *busiest;

        local = &sds->local_stat;
        busiest = &sds->busiest_stat;

        if (busiest->group_type == group_imbalanced) {
                /*
                 * In the group_imb case we cannot rely on group-wide averages
                 * to ensure cpu-load equilibrium, look at wider averages. XXX
                 */
                busiest->load_per_task =
                        min(busiest->load_per_task, sds->avg_load);
        }

        /*
         * In the presence of smp nice balancing, certain scenarios can have
         * max load less than avg load(as we skip the groups at or below
         * its cpu_capacity, while calculating max_load..)
         */
        if (busiest->avg_load <= sds->avg_load ||
            local->avg_load >= sds->avg_load) {
                env->imbalance = 0;
                return fix_small_imbalance(env, sds);
        }

        /*
         * If there aren't any idle cpus, avoid creating some.
         */
        if (busiest->group_type == group_overloaded &&
            local->group_type   == group_overloaded) {
                load_above_capacity =
                        (busiest->sum_nr_running - busiest->group_capacity_factor);

                load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
                load_above_capacity /= busiest->group_capacity;
        }
  • 코드 라인 15~22에서 busiest 그룹이 group_imbalanced(1) 타입인 경우 태스크 당 로드 값인 load_per_task가 sds->avg_load보다 작으면 갱신한다.
  • 코드 라인 29~33에서 busiest 그룹의 평균 로드가 도메인의 평균 로드 이하 또는 local 그룹의 평균 로드가 도메인의 평균 로드 이상인 경우
  • 코드 라인 38~45에서 busiest 및 local 그룹 모두 group_overloaded(2) 타입인 경우 즉, idle cpu들이 없는 경우

 

        /*
         * We're trying to get all the cpus to the average_load, so we don't
         * want to push ourselves above the average load, nor do we wish to
         * reduce the max loaded cpu below the average load. At the same time,
         * we also don't want to reduce the group load below the group capacity
         * (so that we can implement power-savings policies etc). Thus we look
         * for the minimum possible imbalance.
         */
        max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity);

        /* How much load to actually move to equalise the imbalance */
        env->imbalance = min(
                max_pull * busiest->group_capacity, 
                (sds->avg_load - local->avg_load) * local->group_capacity
        ) / SCHED_CAPACITY_SCALE;

        /*
         * if *imbalance is less than the average load per runnable task
         * there is no guarantee that any tasks will be moved so we'll have
         * a think about bumping its value to force at least one task to be
         * moved
         */
        if (env->imbalance < busiest->load_per_task)
                return fix_small_imbalance(env, sds);
}
  • 코드 라인 9에서 busiest 그룹의 평균 로드가 도메인의 평균 로드를 초과한 차이와 load_above_capacity 값 중 작은 값을 max_pull에 대입한다.
  • 코드 라인 12~15에서 max_pull 값을 busiest 그룹의 capacity 값과 곱한 값과 도메인의 평균 로드에서 local 그룹의 평균 로드를 뺀 값을 local 그룹의 capacity 값 중 작은 값을 / SCHED_CAPACITY_SCALE(1024)로 나누어 env->imbalance를 산출한다.
  • 코드 라인 23~24에서 산출된 imbalance가 busiest 그룹의 태스크 당 로드 값보다 작은 경우 fix small imabalance 값을 반환한다.

 

fix_small_imbalance()

local 그룹과 busiest 그룹의 상대 로드 값을 비교하여 busiest 그룹의 태스크들을 마이그레이션 하는 것이 유리하면 busiest 그룹의 태스크당 로드 값을 imbalance에 산출해온다.

kernel/sched/fair.c

/**
 * fix_small_imbalance - Calculate the minor imbalance that exists
 *                      amongst the groups of a sched_domain, during
 *                      load balancing.
 * @env: The load balancing environment.
 * @sds: Statistics of the sched_domain whose imbalance is to be calculated.
 */
static inline
void fix_small_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
{
        unsigned long tmp, capa_now = 0, capa_move = 0;
        unsigned int imbn = 2;
        unsigned long scaled_busy_load_per_task;
        struct sg_lb_stats *local, *busiest;

        local = &sds->local_stat;
        busiest = &sds->busiest_stat;

        if (!local->sum_nr_running)
                local->load_per_task = cpu_avg_load_per_task(env->dst_cpu);
        else if (busiest->load_per_task > local->load_per_task)
                imbn = 1;

        scaled_busy_load_per_task =
                (busiest->load_per_task * SCHED_CAPACITY_SCALE) /
                busiest->group_capacity;

        if (busiest->avg_load + scaled_busy_load_per_task >=
            local->avg_load + (scaled_busy_load_per_task * imbn)) {
                env->imbalance = busiest->load_per_task;
                return;
        }
  • 코드 라인 19~20에서 local 그룹의 엔티티 수가 하나도 없는 경우 local 그룹의 태스크당 로드 값인 load_per_task에 dst_cpu의 태스크 당 로드 평균 값을 산출한다.
  • 코드 라인 21~22에서 busiest 그룹의 태스크 당 로드 값이 local 그룹의 태스크 당 로드 값보다 큰 경우 imbn값을 2에서 1로 떨어뜨린다.
  • 코드 라인 24~26에서 busiest 그룹의 태스크 당 로드 값에 capacity scale(1024)를 적용한 후 busiest 그룹의 capacity로 나눈 값을 산출한다.
  • 코드 라인 28~32에서 busiest 그룹의 평균 로드 + scale 적용된 busiest 그룹의 태스크당 로드 값이 local 그룹의 평균 로드 + busiest 그룹의 태스크당 로드 값 이상인 경우 env->imbalance에 busiest 그룹의 태스크당 로드 평균을 대입하고 함수를 빠져나간다. 만일 imbn이 2인 경우 busiest 그룹의 평균 로드가 더 커야 이 조건을 만족시킨다.

 

        /*
         * OK, we don't have enough imbalance to justify moving tasks,
         * however we may be able to increase total CPU capacity used by
         * moving them.
         */

        capa_now += busiest->group_capacity *
                        min(busiest->load_per_task, busiest->avg_load);
        capa_now += local->group_capacity *
                        min(local->load_per_task, local->avg_load);
        capa_now /= SCHED_CAPACITY_SCALE;

        /* Amount of load we'd subtract */
        if (busiest->avg_load > scaled_busy_load_per_task) {
                capa_move += busiest->group_capacity *
                            min(busiest->load_per_task,
                                busiest->avg_load - scaled_busy_load_per_task);
        }

        /* Amount of load we'd add */
        if (busiest->avg_load * busiest->group_capacity <
            busiest->load_per_task * SCHED_CAPACITY_SCALE) {
                tmp = (busiest->avg_load * busiest->group_capacity) /
                      local->group_capacity;
        } else {
                tmp = (busiest->load_per_task * SCHED_CAPACITY_SCALE) /
                      local->group_capacity;
        }
        capa_move += local->group_capacity *
                    min(local->load_per_task, local->avg_load + tmp);
        capa_move /= SCHED_CAPACITY_SCALE;

        /* Move if we gain throughput */
        if (capa_move > capa_now)
                env->imbalance = busiest->load_per_task;
}
  • 코드 라인 7~11에서 capa_now에는 busiest 그룹 및 로컬 그룹의 로드 평균을 더한다.
  • 코드 라인 14~18에서 busiest 그룹의 평균 로드가 scale 적용된 busiest 그룹의 태스크당 로드보다 큰 경우 capa_move에 capacity 적용된 일정량의 로드를 더한다.
  • 코드 라인 21~28에서 local 그룹 대비 busiest 그룹의 상대 평균 로드 값(평균 로드와 태스크당 로드 둘 중 작은 값으로)을 tmp에 대입한다.
    • 예) local(group_capacity=860, load_avg=100, load_per_task=50),   busiest(roup_capacity=3070, avg_load=300, load_per_task=150)
      • tmp = 150 * 1024 / 860 = 178
  • 코드 라인 29~31에서 capa_move를 산출한다.
    • capa_move = 860 * 50 / 1024 = 41
  • 코드 라인 34~35에서 local 그룹보다 busiest 그룹의 상대 로드가 더 큰 경우 마이그레이션을 하는 것이 유리하다. 이 때 imbalance에 busiest으 태스크당 로드 값을 대입한다.

 

check_asym_packing()

kernel/sched/fair.c

/**
 * check_asym_packing - Check to see if the group is packed into the
 *                      sched doman.
 *
 * This is primarily intended to used at the sibling level.  Some
 * cores like POWER7 prefer to use lower numbered SMT threads.  In the
 * case of POWER7, it can move to lower SMT modes only when higher
 * threads are idle.  When in lower SMT modes, the threads will
 * perform better since they share less core resources.  Hence when we
 * have idle threads, we want them to be the higher ones.
 *
 * This packing function is run on idle threads.  It checks to see if
 * the busiest CPU in this domain (core in the P7 case) has a higher
 * CPU number than the packing function is being run on.  Here we are
 * assuming lower CPU number will be equivalent to lower a SMT thread
 * number.
 *
 * Return: 1 when packing is required and a task should be moved to
 * this CPU.  The amount of the imbalance is returned in *imbalance.
 *
 * @env: The load balancing environment.
 * @sds: Statistics of the sched_domain which is to be packed
 */
static int check_asym_packing(struct lb_env *env, struct sd_lb_stats *sds)
{
        int busiest_cpu;

        if (!(env->sd->flags & SD_ASYM_PACKING))
                return 0;

        if (!sds->busiest)
                return 0;

        busiest_cpu = group_first_cpu(sds->busiest);
        if (env->dst_cpu > busiest_cpu)
                return 0;

        env->imbalance = DIV_ROUND_CLOSEST(
                sds->busiest_stat.avg_load * sds->busiest_stat.group_capacity,
                SCHED_CAPACITY_SCALE);

        return 1;
}

asymetric(뷸균형) 패킹이 필요한 상태인지 여부를 반환한다.  POWER7 아키텍처가 아닌 경우 항상 0을 반환한다.

  • 코드 라인 28~29에서 SD_ASYM_PACKING 플래그를 사용하지 않는 스케줄링 도메인은 0을 반환한다.
    • SD_ASYM_PACKING 플래그는 POWER7(powerpc) 아키텍처에서만 사용한다.
    • POWER7 아키텍처의 경우 SMT 스레드들 중 작은 번호의 스레드를 사용하는 것을 권장한다.
    • 작은 번호의 스레드를 사용하여야 코어 리소스를 덜 공유하여 더 높은 성능을 낸다.
  • 코드 라인 31~32에서 busiest 스케줄 그룹이 없는 경우 0을 반환한다.
  • 코드 라인 34~36에서 busiest 스케줄 그룹에서 가장 처음 cpu를 busiest_cpu로 구하되 env->dst_cpu보다 낮은 경우 0을 반환한다.
  • 코드 라인 38~40에서 busiest_stat의 avg_load * group_capacity를 SCHED_CAPACITY_SHIFT(1024)로 나누어 반올림한 값을 env->imbalance에 대입한다.
  • 코드 라인 42에서 하위 스레드에서 놀고 있는 cpu가 있으므로 패킹을 위해 1을 반환한다.

 

find_busiest_queue()

스케줄 그룹내에서 가장 busy한 워크 로드(cpu capacity * 러너블 로드 평균)를 가진 cpu 런큐를 반환한다.

kernel/sched/fair.c

/*
 * find_busiest_queue - find the busiest runqueue among the cpus in group.
 */
static struct rq *find_busiest_queue(struct lb_env *env,
                                     struct sched_group *group)
{
        struct rq *busiest = NULL, *rq; 
        unsigned long busiest_load = 0, busiest_capacity = 1;
        int i;

        for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
                unsigned long capacity, capacity_factor, wl;
                enum fbq_type rt;

                rq = cpu_rq(i);
                rt = fbq_classify_rq(rq);

                /*
                 * We classify groups/runqueues into three groups:
                 *  - regular: there are !numa tasks
                 *  - remote:  there are numa tasks that run on the 'wrong' node
                 *  - all:     there is no distinction
                 *
                 * In order to avoid migrating ideally placed numa tasks,
                 * ignore those when there's better options.
                 *
                 * If we ignore the actual busiest queue to migrate another
                 * task, the next balance pass can still reduce the busiest
                 * queue by moving tasks around inside the node.
                 *
                 * If we cannot move enough load due to this classification
                 * the next pass will adjust the group classification and
                 * allow migration of more tasks.
                 *
                 * Both cases only affect the total convergence complexity.
                 */
                if (rt > env->fbq_type)
                        continue;

                capacity = capacity_of(i);
                capacity_factor = DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE);
                if (!capacity_factor)
                        capacity_factor = fix_small_capacity(env->sd, group);
  • 코드 라인 11에서 스케줄 그룹 cpu들에 포함된 env->cpus 들을 순회한다.
  • 코드 라인 37~38에서 NUMA 밸런싱을 사용하는 시스템의 경우 런큐의 fbq 타입이 env->fbq_type 보다 큰 경우 busy하지 않은 cpu로 skip 한다.
    • NUMA 밸런싱을 사용하지 않는 경우 런큐의 fbq 타입은 항상 regular(0)이므로 skip 하지 않는다.
  • 코드 라인 40~41에서 cpu capacity 값을 알아와서 1024 단위로 나눌 때 반올림 처리한 값을 capacity_factor에 대입한다. (예: 1200 -> 1, 1800 -> 2)
  • 코드 라인 42~43에서 capacity_factor 값이 0인 경우 fix small capacity를 산출한다.
    • arm, arm64의 경우 항상 0을 반환한다.

 

                wl = weighted_cpuload(i);

                /*
                 * When comparing with imbalance, use weighted_cpuload()
                 * which is not scaled with the cpu capacity.
                 */
                if (capacity_factor && rq->nr_running == 1 && wl > env->imbalance)
                        continue;

                /*
                 * For the load comparisons with the other cpu's, consider
                 * the weighted_cpuload() scaled with the cpu capacity, so
                 * that the load can be moved away from the cpu that is
                 * potentially running at a lower capacity.
                 *
                 * Thus we're looking for max(wl_i / capacity_i), crosswise
                 * multiplication to rid ourselves of the division works out
                 * to: wl_i * capacity_j > wl_j * capacity_i;  where j is
                 * our previous maximum.
                 */
                if (wl * busiest_capacity > busiest_load * capacity) {
                        busiest_load = wl; 
                        busiest_capacity = capacity;
                        busiest = rq;
                }
        }

        return busiest;
}
  • 코드 라인 1에서 최상위 cfs 런큐의 러너블 로드 평균을 알아와서 wl에 대입한다.
  • 코드 라인 7~8에서 런큐에서 동작하는 태스크가 1개이고 capacity_factor가 1 이상이고 wl이 env->imbalance 값을 초과하는 경우 무조건 busy 하지 않다고 판단하여 skip 한다.
  • 코드 라인 21~25에서 각 cpu의 cpu capacity 비율을 반영한 워크로드 중 가장 busy한 cpu를 갱신한다.
    • 처음 루프에서는 무조건 갱신한다.
    • 예) 두 개의 cpu capacity가 A=1535, B=430과 같이 다른 경우 각각 A=700, B=197의 워크로드를 가지는 경우 누가 busy cpu일까?
      • 45.6%(A: 700/1535)  <  45.8%(B: 430/197)

 

fix_small_capacity()

kernel/sched/fair.c

/*
 * Try and fix up capacity for tiny siblings, this is needed when
 * things like SD_ASYM_PACKING need f_b_g to select another sibling
 * which on its own isn't powerful enough.
 *
 * See update_sd_pick_busiest() and check_asym_packing().
 */
static inline int
fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
{
        /*
         * Only siblings can have significantly less than SCHED_CAPACITY_SCALE
         */
        if (!(sd->flags & SD_SHARE_CPUCAPACITY))
                return 0;

        /*
         * If ~90% of the cpu_capacity is still there, we're good.
         */
        if (group->sgc->capacity * 32 > group->sgc->capacity_orig * 29)
                return 1;

        return 0;
}

SD_SHARE_CPUCAPACITY 플래그를 사용하는 SMT(Simultaneous Multi Thread) 도메인인 경우 이 스레드가 cfs 태스크 시간(irq time + rt task time + dl task time을 제외한) 비율이 약 90%(90.625) 이상인 경우 1을 반환한다.

  • arm 및 arm64의 경우 현재까지도 하드웨어 스레드를 지원하는 아키텍처가 출시되지 않아 아직 SMT를 사용하지 않는다. 따라서 항상 0을 반환한다.
  • factor * 32 = 100 * 29일 때 factor = 90.625

 

디태치 태스크들

detach_tasks()

kernel/sched/fair.c

/*
 * detach_tasks() -- tries to detach up to imbalance weighted load from
 * busiest_rq, as part of a balancing operation within domain "sd".
 *
 * Returns number of detached tasks if successful and 0 otherwise.
 */
static int detach_tasks(struct lb_env *env)
{
        struct list_head *tasks = &env->src_rq->cfs_tasks;
        struct task_struct *p;
        unsigned long load;
        int detached = 0;

        lockdep_assert_held(&env->src_rq->lock);

        if (env->imbalance <= 0)
                return 0;

        while (!list_empty(tasks)) {
                p = list_first_entry(tasks, struct task_struct, se.group_node);

                env->loop++;
                /* We've more or less seen every task there is, call it quits */
                if (env->loop > env->loop_max)
                        break;

                /* take a breather every nr_migrate tasks */
                if (env->loop > env->loop_break) {
                        env->loop_break += sched_nr_migrate_break;
                        env->flags |= LBF_NEED_BREAK;
                        break;
                }

                if (!can_migrate_task(p, env))
                        goto next;

                load = task_h_load(p);

                if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
                        goto next;

                if ((load / 2) > env->imbalance)
                        goto next;

                detach_task(p, env);
                list_add(&p->se.group_node, &env->tasks);

                detached++;
                env->imbalance -= load;

소스 런큐의 cfs_tasks 리스트에 있는 태스크들을 디태치하여 env->tasks 리스트에 넣어온다. 반환되는 값으로 디태치한 태스크 수를 알아온다.

  • 코드 라인 16~17에서 env->imbalance가 0 이하이면 밸런싱할 필요가 없으므로 0을 반환한다.
  • 코드 라인 19~20에서 src 런큐의 cfs_tasks 리스트에 처리할 태스크가 없을 때까지 루프를 돌며 앞에서 부터 태스크를 하나씩 가져온다.
  • 코드 라인 22~25에서 루프 카운터를 증가시키고 loop_max를 초과하면 루프를 벗어난다.
  • 코드 라인 28~32에서 루프 카운터가 loop_break를 초과하는 경우에는 LBF_NEED_BREAK 플래그를 설정한채 루프를 벗어난다.
    • 이 경우 이 함수를 호출한 load_balance() 함수로 돌아간 후 unlock 후 다시 처음부터 lock을 다시 잡고 시도하게된다. loop_max가 매우 클 경우 lock을 잡고 한번에 처리하는 개수가 크면 시간이 너무 많이 소요되므로 이를 loop_break 단위로 나누어 처리하도록 한다.
  • 코드 라인 34~35에서 태스크를 마이그레이션 할 수 없으면 next 레이블로 이동하여 리스트의 뒤로 옮긴다음 계속 루프를 돈다.
  • 코드 라인 37에서 태스크의 로드 평균 기여값을 알아온다.
  • 코드 라인 39~40에서 LB_MIN feature를 사용하고 로드가 16보다 작고 도메인에 밸런싱이 실패한 적이 없으면 next 레이블로 이동하여 리스트의 뒤로 옮긴다음 계속 루프를 돈다.
    • 디폴트로 LB_MIN feature를 사용하지 않는다.
  • 코드 라인 42~43에서 로드 값의 절반이 imbalance보다 큰 경우 next 레이블로 이동하여 리스트의 뒤로 옮긴다음 계속 루프를 돈다.
  • 코드 라인 45~49에서 태스크를 detach하고 env->tasks 리스트에 추가한다. env->imbalance에 로드 값을 감소시킨다.

 

#ifdef CONFIG_PREEMPT
                /*
                 * NEWIDLE balancing is a source of latency, so preemptible
                 * kernels will stop after the first task is detached to minimize
                 * the critical section.
                 */
                if (env->idle == CPU_NEWLY_IDLE)
                        break;
#endif

                /*
                 * We only want to steal up to the prescribed amount of
                 * weighted load.
                 */
                if (env->imbalance <= 0)
                        break;

                continue;
next:
                list_move_tail(&p->se.group_node, tasks);
        }

        /*
         * Right now, this is one of only two places we collect this stat
         * so we can safely collect detach_one_task() stats here rather
         * than inside detach_one_task().
         */
        schedstat_add(env->sd, lb_gained[env->idle], detached);

        return detached;
}
  • 코드 라인 1~9에서 preempt 커널 옵션을 사용하고 NEWIDLE 밸런싱이 수행중인 경우 하나만 처리하고 루프를 벗어난다.
  • 코드 라인 15~16에서 imbalance가 0 이하인 경우 루프를 벗어난다. 즉 로드를 더 뺄 imbalance 값이 없는 경우 그만 처리한다.
  • 코드 라인 18에서 계속 순회한다.
  • 코드 라인 19~21에서 next 레이블에 도착하면 태스크를 소스 런큐의 cfs_tasks 리스트의 후미로 옮긴다.
  • 코드 라인 28~30에서 lb_gained[] 통계를 갱신하고 detached된 수를 반환한다.

 

task_h_load()

kernel/sched/fair.c

#ifdef CONFIG_FAIR_GROUP_SCHED
static unsigned long task_h_load(struct task_struct *p)
{
        struct cfs_rq *cfs_rq = task_cfs_rq(p);

        update_cfs_rq_h_load(cfs_rq);
        return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load,
                        cfs_rq->runnable_load_avg + 1);
}
#else
static unsigned long task_h_load(struct task_struct *p)
{
        return p->se.avg.load_avg_contrib;
}
#endif

태스크의 로드 평균 기여값을 반환한다. 만일 그룹 스케줄링을 사용하는 경우 태스크의 로드 평균 기여에 cfs 런큐의 h_load 비율을 곱하고 러너블 로드 평균으로 나누어 반환한다.

  • 코드 라인 4~6에서 요청한 태스크의 cfs 런큐부터 최상위 cfs 런큐까지 h_load를 갱신한다.
  • 코드 라인 7~8에서 태스크의 로드 평균 기여에 cfs 런큐의 h_load 비율을 곱하고 러너블 로드 평균으로 나누어 반환한다.

 

다음 그림은 요청한 태스크의 로드 평균 기여를 산출하는 모습을 보여준다.

 

update_cfs_rq_h_load()

kernel/sched/fair.c

/*
 * Compute the hierarchical load factor for cfs_rq and all its ascendants.
 * This needs to be done in a top-down fashion because the load of a child
 * group is a fraction of its parents load.
 */
static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
{
        struct rq *rq = rq_of(cfs_rq);
        struct sched_entity *se = cfs_rq->tg->se[cpu_of(rq)];
        unsigned long now = jiffies;
        unsigned long load;

        if (cfs_rq->last_h_load_update == now)
                return;

        cfs_rq->h_load_next = NULL;
        for_each_sched_entity(se) {
                cfs_rq = cfs_rq_of(se);
                cfs_rq->h_load_next = se;
                if (cfs_rq->last_h_load_update == now)
                        break;
        }

        if (!se) {
                cfs_rq->h_load = cfs_rq->runnable_load_avg;
                cfs_rq->last_h_load_update = now;
        }

        while ((se = cfs_rq->h_load_next) != NULL) {
                load = cfs_rq->h_load;
                load = div64_ul(load * se->avg.load_avg_contrib,
                                cfs_rq->runnable_load_avg + 1);
                cfs_rq = group_cfs_rq(se);
                cfs_rq->h_load = load;
                cfs_rq->last_h_load_update = now;
        }
}

요청한 cfs 런큐부터 최상위 까지의 h_load를 갱신한다.

  • 코드 라인 13~14에서 이미 마지막 h_load가 갱신된 시각(jiffies)이면 함수를 빠져나간다.
  • 코드 라인 16에서 요청한 cfs 런큐를 대표하는 엔티티의 cfs 런큐 h_load_next에 null을 대입한다. h_load_next는 스케줄 엔티티를 top down으로 연결시키기 위해 잠시 사용되는 변수이다.
  • 코드 라인 16~22에서 요청한 cfs 런큐를 대표하는 엔티티부터 최상위 엔티티까지 순회하며 순회중인 스케줄 엔티티의 cfs 런큐 h_load_next 에 스케줄 엔티티를 대입한다. 만일 순회 중 h_load가 갱신되어 있으면 순회를 중단한다.
  • 코드 라인 24~27에서 순회가 중단되지 않고 끝까지 수행되었거나 최상위 cfs 런큐로 요청된 경우 cfs 런큐의 h_load에 러너블 로드 평균을 대입하고 h_load 갱신이 완료된 현재 시각을 대입한다.
  • 코드 라인 29~에서 엔티티를 top down으로 순회를 한다. h_load 값에 로드 평균 기여를 곱한 후 러너블 로드로 나누어 h_load를 갱신한다. 그 후 갱신된 시각에 현재 시각을 대입한다.

 

다음 그림은 h_load 값이 산출되는 모습을 보여준다.

 

어태치 태스크들

attach_tasks()

kernel/sched/fair.c

/*
 * attach_tasks() -- attaches all tasks detached by detach_tasks() to their
 * new rq.
 */
static void attach_tasks(struct lb_env *env)
{
        struct list_head *tasks = &env->tasks;
        struct task_struct *p;

        raw_spin_lock(&env->dst_rq->lock);

        while (!list_empty(tasks)) {
                p = list_first_entry(tasks, struct task_struct, se.group_node);
                list_del_init(&p->se.group_node);

                attach_task(env->dst_rq, p);
        }

        raw_spin_unlock(&env->dst_rq->lock);
}

디태치한 태스크들을 모두 dst 런큐에 어태치한다.

 

attach_task()

kernel/sched/fair.c

/*
 * attach_task() -- attach the task detached by detach_task() to its new rq.
 */
static void attach_task(struct rq *rq, struct task_struct *p)
{
        lockdep_assert_held(&rq->lock);

        BUG_ON(task_rq(p) != rq);
        p->on_rq = TASK_ON_RQ_QUEUED;
        activate_task(rq, p, 0);
        check_preempt_curr(rq, p, 0);
}

태스크를 요청한 런큐에 어태치한다.  그런 후 preemption 조건을 만족하면 요청 플래그를 설정한다.

 

activate_task()

kernel/sched/core.c

void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible--;

        enqueue_task(rq, p, flags);
}

태스크를 런큐에 엔큐한다.

  • 코드 라인 3~4에서 태스크가 로드에 기여하는 경우 nr_uninterruptible stat을 감소시킨다.
  • 코드 라인 6에서 런큐에 태스크를 엔큐한다.

 

task_contributes_to_load()

include/linux/sched.h

#define task_contributes_to_load(task)  \
                                ((task->state & TASK_UNINTERRUPTIBLE) != 0 && \
                                 (task->flags & PF_FROZEN) == 0)

태스크가 로드에 기여하는지 여부를 반환한다.

  • TASK_UNINTERRUPTIBLE 상태가 아니면서 suspend에 의해 frozen된 태스크도 아니면 1을 반환한다.

 

Active 밸런스

need_active_balance()

kernel/sched/fair.c

static int need_active_balance(struct lb_env *env)
{
        struct sched_domain *sd = env->sd;

        if (env->idle == CPU_NEWLY_IDLE) {

                /*
                 * ASYM_PACKING needs to force migrate tasks from busy but
                 * higher numbered CPUs in order to pack all tasks in the
                 * lowest numbered CPUs.
                 */
                if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
                        return 1;
        }

        return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
}

active 로드 밸런싱이 필요한지 여부를 반환한다. (nr_balance_failed > cache_nice_tries+2인 경우 1)

  • 코드 라인 5~14에서 CPU_NEWLY_IDLE 상황이고 스케줄링 도메인에 SD_AYSM_PACKING 플래그가 있고 src_cpu보다 dst_cpu가 큰 경우 true(1)를 반환한다.
    • powerpc에서 사용하는 플래그이다.
  • 코드 라인 16에서 낮은 확률로 로드밸런스 실패 횟수가 cache_nice_tries+2 보다 큰 경우 true를 반환한다.

 

stop_one_cpu_nowait()

include/linux/stop_machine.h

static inline void stop_one_cpu_nowait(unsigned int cpu,
                                       cpu_stop_fn_t fn, void *arg,
                                       struct cpu_stop_work *work_buf)
{
        if (cpu == smp_processor_id()) {
                INIT_WORK(&work_buf->work, stop_one_cpu_nowait_workfn);
                work_buf->fn = fn;
                work_buf->arg = arg;
                schedule_work(&work_buf->work);
        }
}

요청한 cpu가 현재 cpu인 경우 인수로 받은 함수를 워크큐에 담은 후 워커 스레드에서 동작하도록 스케줄한다.

  • 현재 커널 소스에서 인수로 사용되는 함수는 active_load_balance_cpu_stop() 함수가 유일하다.
  • 이 함수를 통해 busiest cpu의 태스크를 push_cpu로 옮기게 한다.

 

active_load_balance_cpu_stop()

kernel/sched/fair.c

/*
 * active_load_balance_cpu_stop is run by cpu stopper. It pushes
 * running tasks off the busiest CPU onto idle CPUs. It requires at
 * least 1 task to be running on each physical CPU where possible, and
 * avoids physical / logical imbalances.
 */
static int active_load_balance_cpu_stop(void *data)
{
        struct rq *busiest_rq = data;
        int busiest_cpu = cpu_of(busiest_rq);
        int target_cpu = busiest_rq->push_cpu;
        struct rq *target_rq = cpu_rq(target_cpu);
        struct sched_domain *sd;
        struct task_struct *p = NULL;
        
        raw_spin_lock_irq(&busiest_rq->lock);
        
        /* make sure the requested cpu hasn't gone down in the meantime */
        if (unlikely(busiest_cpu != smp_processor_id() ||
                     !busiest_rq->active_balance))
                goto out_unlock;

        /* Is there any task to move? */
        if (busiest_rq->nr_running <= 1)
                goto out_unlock;

        /*
         * This condition is "impossible", if it occurs
         * we need to fix it. Originally reported by
         * Bjorn Helgaas on a 128-cpu setup.
         */
        BUG_ON(busiest_rq == target_rq);

busiest cpu의 태스크 하나를 idle cpu로 옮긴다.

  • 코드 라인 19~21에서 낮은 확률로 busiest cpu가 현재 cpu가 아니거나 busiest 런큐의 active_balance가 해제된 경우 out_unlock 레이블로 이동하여 마이그레이션을 포기한다.
  • 코드 라인 24~25에서 busiest 런큐에서 동작 중인 태스크가 한 개 이하인 경우 out_unlock 레이블로 이동하여 마이그레이션을 포기한다.

 

        /* Search for an sd spanning us and the target CPU. */
        rcu_read_lock();
        for_each_domain(target_cpu, sd) {
                if ((sd->flags & SD_LOAD_BALANCE) &&
                    cpumask_test_cpu(busiest_cpu, sched_domain_span(sd)))
                                break;
        }

        if (likely(sd)) {
                struct lb_env env = {
                        .sd             = sd,
                        .dst_cpu        = target_cpu,
                        .dst_rq         = target_rq,
                        .src_cpu        = busiest_rq->cpu,
                        .src_rq         = busiest_rq,
                        .idle           = CPU_IDLE,
                };

                schedstat_inc(sd, alb_count);

                p = detach_one_task(&env);
                if (p)
                        schedstat_inc(sd, alb_pushed);
                else
                        schedstat_inc(sd, alb_failed);
        }
        rcu_read_unlock();
out_unlock:
        busiest_rq->active_balance = 0;
        raw_spin_unlock(&busiest_rq->lock);

        if (p)
                attach_one_task(target_rq, p);

        local_irq_enable();

        return 0;
}
  • 코드 라인 3~7에서 target cpu의 하위 도메인에서 최상위 도메인까지 순회하며 busiest cpu가 밸런싱 가능한 경우 루프를 빠져나온다.
  • 코드 라인 9~26에서 높은 확률로 밸런싱 가능한 도메인인 경우 alb_count 카운터를 증가시키고 busiest cpu 에서 태스크를 디태치해온다. 디태치한 경우 alb_pushed 카운터를 증가시키고 그렇지 못한 경우 alb_failed 카운터를 증가시킨다.
  • 코드 라인 28~37에서 busiest 런큐의 avtive_balance에 0을 대입하고 target cpu에 디태치 했었던 태스크를 어태치하고 함수를 빠져나간다.

 

detach_one_task()

kernel/sched/fair.c

/*
 * detach_one_task() -- tries to dequeue exactly one task from env->src_rq, as
 * part of active balancing operations within "domain".
 *
 * Returns a task if successful and NULL otherwise.
 */
static struct task_struct *detach_one_task(struct lb_env *env)
{
        struct task_struct *p, *n;

        lockdep_assert_held(&env->src_rq->lock);

        list_for_each_entry_safe(p, n, &env->src_rq->cfs_tasks, se.group_node) {
                if (!can_migrate_task(p, env))
                        continue;

                detach_task(p, env);

                /*
                 * Right now, this is only the second place where
                 * lb_gained[env->idle] is updated (other is detach_tasks)
                 * so we can safely collect stats here rather than
                 * inside detach_tasks().
                 */
                schedstat_inc(env->sd, lb_gained[env->idle]);
                return p;
        }
        return NULL;
}

src 런큐에서 동작하는 태스크들 중 마이그레이션 가능한 태스크 하나를 디태치하고 반환한다.

  • 코드 라인 13~15에서 src 런큐에서 동작하는 태스크들을 순회하며 마이그레이션 할 수 없는 태스크는 skip 한다.
  • 코드 라인 17~27에서 태스크를 디태치하고 lb_gained[]의 stat 카운터를 증가시키고 태스크를 반환한다.
  • 코드  라인 28에서 디태치를 못한 경우 null을 반환한다.

 

attach_one_task()

kernel/sched/fair.c

/*
 * attach_one_task() -- attaches the task returned from detach_one_task() to
 * its new rq.
 */
static void attach_one_task(struct rq *rq, struct task_struct *p)
{
        raw_spin_lock(&rq->lock);
        attach_task(rq, p);
        raw_spin_unlock(&rq->lock);
}

요청한 태스크를 어태치한다. (런큐에 엔큐)

 

마이그레이션 가능 여부 체크

can_migrate_task()

kernel/sched/fair.c

/*
 * can_migrate_task - may task p from runqueue rq be migrated to this_cpu?
 */
static
int can_migrate_task(struct task_struct *p, struct lb_env *env)
{
        int tsk_cache_hot = 0;

        lockdep_assert_held(&env->src_rq->lock);

        /*
         * We do not migrate tasks that are:
         * 1) throttled_lb_pair, or
         * 2) cannot be migrated to this CPU due to cpus_allowed, or
         * 3) running (obviously), or
         * 4) are cache-hot on their current CPU.
         */
        if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
                return 0;

        if (!cpumask_test_cpu(env->dst_cpu, tsk_cpus_allowed(p))) {
                int cpu;

                schedstat_inc(p, se.statistics.nr_failed_migrations_affine);

                env->flags |= LBF_SOME_PINNED;

                /*
                 * Remember if this task can be migrated to any other cpu in
                 * our sched_group. We may want to revisit it if we couldn't
                 * meet load balance goals by pulling other tasks on src_cpu.
                 *
                 * Also avoid computing new_dst_cpu if we have already computed
                 * one in current iteration.
                 */
                if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED))
                        return 0;

                /* Prevent to re-select dst_cpu via env's cpus */
                for_each_cpu_and(cpu, env->dst_grpmask, env->cpus) {
                        if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p))) {
                                env->flags |= LBF_DST_PINNED;
                                env->new_dst_cpu = cpu;
                                break;
                        }
                }

                return 0;
        }

 

태스크를 마이그레이션해도 되는지 여부를 반환한다.

  • 코드 라인 18~19에서 태스크가 스케줄된 그룹의 src 또는 dest cpu의 cfs 런큐가 스로틀된 경우 0을 반환한다.
  • 코드 라인 21~46에서 dst cpu들 중 태스크에 허락된 cpu가 없는 경우 nr_failed_migrations_affine stat을 증가시키고 LBF_SOME_PINNED 플래그를 설정하고 0을 반환한다. 만일 dst_grpmask가 비어있지 않으면서 LBF_DST_PINNED 플래그가도 설정되지 않은 경우 env->cpus를 순회하며 태스크가 허용하는 cpu에 한하여 LBF_DST_PINNED 플래그를 설정하고 new_dst_cpu에 cpu를 대입하고 0을 반환한다.

 

        /* Record that we found atleast one task that could run on dst_cpu */
        env->flags &= ~LBF_ALL_PINNED;

        if (task_running(env->src_rq, p)) {
                schedstat_inc(p, se.statistics.nr_failed_migrations_running);
                return 0;
        }

        /*
         * Aggressive migration if:
         * 1) destination numa is preferred
         * 2) task is cache cold, or
         * 3) too many balance attempts have failed.
         */
        tsk_cache_hot = task_hot(p, env);
        if (!tsk_cache_hot)
                tsk_cache_hot = migrate_degrades_locality(p, env);

        if (migrate_improves_locality(p, env) || !tsk_cache_hot ||
            env->sd->nr_balance_failed > env->sd->cache_nice_tries) {
                if (tsk_cache_hot) {
                        schedstat_inc(env->sd, lb_hot_gained[env->idle]);
                        schedstat_inc(p, se.statistics.nr_forced_migrations);
                }
                return 1;
        }

        schedstat_inc(p, se.statistics.nr_failed_migrations_hot);
        return 0;
}
  • 코드 라인 2에서 LBF_ALL_PINNED 플래그를 제거한다.
  • 코드 라인 4~7에서 src 런큐에서 태스크가 러닝 중이면 nr_failed_migrations_running stat을 증가시키고 0을 반환한다.
  • 코드 라인 15~17에서 태스크가 cache hot 상태이거나 numa 밸런싱을 하는 경우 locality가 저하되는지 여부를 확인한다.
    • cache-hot을 유지하는 경우 마이그레이션을 하지 않는다.
    • numa 밸런싱을 사용하지 않는 경우 migrate_degrades_locality() 함수의 결과는 항상 false(0)이다.
  • 코드 라인 19~26에서 numa 밸런싱을 하는 경우 locality가 상승하거나 태스크가 cache hot 상태가 아니거나 밸런싱 실패가 cache_nice_tries 보다 많은 경우 마이그레이션을 할 수 있다고 1을 반환한다. 만일 태스크가 캐시 hot 상태인 경우 lb_hot_gained[] 및 nr_forced_migrations stat 을 증가시킨다.
    • numa 밸런싱을 사용하지 않는 경우 migrate_improves_locality() 함수의 결과는 항상 false(0)이다.
  • 코드 라인 28~29에서 nr_failed_migrations_hot stat을 증가시키고 0을 반환한다.

 

/*
 * Ensure that neither of the group entities corresponding to src_cpu or
 * dest_cpu are members of a throttled hierarchy when performing group
 * load-balance operations.
 */
static inline int throttled_lb_pair(struct task_group *tg,
                                    int src_cpu, int dest_cpu)
{
        struct cfs_rq *src_cfs_rq, *dest_cfs_rq;

        src_cfs_rq = tg->cfs_rq[src_cpu];
        dest_cfs_rq = tg->cfs_rq[dest_cpu];

        return throttled_hierarchy(src_cfs_rq) ||
               throttled_hierarchy(dest_cfs_rq);
}

태스크 그룹에 대한 src 또는 dest cpu의 cfs 런큐가 스로틀되었는지 여부를 반환한다.

 

throttled_hierarchy()

kernel/sched/fair.c

/* check whether cfs_rq, or any parent, is throttled */
static inline int throttled_hierarchy(struct cfs_rq *cfs_rq)
{
        return cfs_bandwidth_used() && cfs_rq->throttle_count;
}

요청한 cfs 런큐가 스로틀되었는지 여부를 반환한다.

 

task_hot()

kernel/sched/fair.c

/*
 * Is this task likely cache-hot:
 */
static int task_hot(struct task_struct *p, struct lb_env *env)
{
        s64 delta;

        lockdep_assert_held(&env->src_rq->lock);

        if (p->sched_class != &fair_sched_class)
                return 0;

        if (unlikely(p->policy == SCHED_IDLE))
                return 0;

        /*
         * Buddy candidates are cache hot:
         */
        if (sched_feat(CACHE_HOT_BUDDY) && env->dst_rq->nr_running &&
                        (&p->se == cfs_rq_of(&p->se)->next ||
                         &p->se == cfs_rq_of(&p->se)->last))
                return 1;

        if (sysctl_sched_migration_cost == -1)
                return 1;
        if (sysctl_sched_migration_cost == 0)
                return 0;

        delta = rq_clock_task(env->src_rq) - p->se.exec_start;

        return delta < (s64)sysctl_sched_migration_cost;
}

태스크가 cache-hot 상태인지 여부를 반환한다. (cache가 hot hot 상태인 경우 가능하면 마이그레이션 하지 않고 이 상태를 유지하게 한다)

  • 코드 라인 10~11에서 cfs 태스크가 아닌 경우 0을 반환한다.
  • 코드 라인 13~14에서 태스크가 SCHED_IDLE policy를 사용하는 경우 0을 반환한다.
  • 코드 라인 18~22에서 CACHE_HOT_BUDDY feature를 사용하면서 dst 런큐에서 동작 중인 태스크가 있고 이 태스크가 next 및 last 버디에 모두 지정된 경우 1을 반환한다.
    • CACHE_HOT_BUDDY feature는 디폴트로 true이다.
    • 혼자 열심히 잘 돌고 있으므로 방해하면 안된다. 마이그레이션하면 캐시만 낭비된다.
  • 코드 라인 24~25에서 sysctl_sched_migration_cost가 -1로 설정된 경우 항상 마이그레이션을 하도록 1을 반환한다.
    • “/proc/sys/kernel/sched_migration_cost_ns”의 디폴트 값은 500,000(ns)이다.
  • 코드 라인 26~27에서 sysctl_sched_migration_cost가 0으로 설정된 경우 항상 마이그레이션을 하지 못하게 0을 반환한다.
  • 코드 라인 29~31에서 실행 시간이 sysctl_sched_migration_cost보다 작은지 여부를 반환한다.
    • 실행 시간이 극히 적은데도 마이그레이션하면 캐시만 낭비하므로 마이그레이션을 하지 못하도록 1을 반환한다.

 

migrate_degrades_locality()

kernel/sched/fair.c

static bool migrate_degrades_locality(struct task_struct *p, struct lb_env *env)
{
        struct numa_group *numa_group = rcu_dereference(p->numa_group);
        int src_nid, dst_nid;

        if (!sched_feat(NUMA) || !sched_feat(NUMA_RESIST_LOWER))
                return false;

        if (!p->numa_faults || !(env->sd->flags & SD_NUMA))
                return false;

        src_nid = cpu_to_node(env->src_cpu);
        dst_nid = cpu_to_node(env->dst_cpu);

        if (src_nid == dst_nid)
                return false;

        if (numa_group) {
                /* Task is moving within/into the group's interleave set. */
                if (node_isset(dst_nid, numa_group->active_nodes))
                        return false;

                /* Task is moving out of the group's interleave set. */
                if (node_isset(src_nid, numa_group->active_nodes))
                        return true;

                return group_faults(p, dst_nid) < group_faults(p, src_nid);
        }

        /* Migrating away from the preferred node is always bad. */
        if (src_nid == p->numa_preferred_nid)
                return true;

        return task_faults(p, dst_nid) < task_faults(p, src_nid);
}

NUMA 밸런싱을 사용하는 경우 태스크의 마이그레이션이 locality를 저하시키는지 여부를 반환한다.  true인 경우 locality가 저하되므로 마이그레이션 권장하지 않는다. (NUMA 밸런싱을 사용하지 않는 경우 항상 false)

  • 코드 라인 6~7에서 NUMA 또는 NUMA_RESIST_LOWER feature를 사용하지 않는 경우 false를 반환한다.
  • 코드 라인 9~10에서 태스크의 누마 폴트가 없거나 NUMA 도메인이 아닌 경우 false를 반환한다.
  • 코드 라인 12~16에서 src 노드와 dst 노드가 같은 경우 false를 반환한다.
  • 코드 라인 18~21에서 태스크의 누마 그룹이 설정되어 있는 경우 dst 노드가 누마 그룹의 active_nodes에 포함된 경우 false를 반환한다.
  • 코드 라인 24~25에서 src 노드가 누마 그룹의 active_nodes에 포함된 경우 true를 반환한다. (locality 저하)
  • 코드 라인 27에서 태스크가 가리키는 누마 그룹에서 dst 노드의 폴트 수가 src 노드의 폴트 수보다 작은 경우 true를 반환한다. (locality 저하)
  • 코드 라인 31~32에서 src 노드가 태스크가 권장하는 노드인 경우 true를 반환한다. (마이그레이션 하지 않게 유도한다)
  • 코드 라인 34에서 태스크에서 dst 노드의 메모리 폴트 수가 src 노드의 메모리 폴트 수보다 작은 경우 true를 반환한다. (locality 저하)

 

group_faults()

kernel/sched/fair.c

static inline unsigned long group_faults(struct task_struct *p, int nid)
{
        if (!p->numa_group)
                return 0;

        return p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 0)] +
                p->numa_group->faults[task_faults_idx(NUMA_MEM, nid, 1)];
}

태스크가 가리키는 누마 그룹에서 요청한 누마 id의 메모리 폴트 값을 알아온다.

  • 코드 라인 3~4에서 누마 그룹이 설정되지 않은 경우 0을 반환한다.
  • 코드 라인 6~7에서 누마 그룹의 NUMA_MEM의 해당 노드의 두 개 faults[] stat을 더해서 반환한다.

 

task_faults()

kernel/sched/fair.c

static inline unsigned long task_faults(struct task_struct *p, int nid)
{
        if (!p->numa_faults)
                return 0;

        return p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)] +
                p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];
}

태스크에서 요청한 누마 id의 메모리 폴트 수를 알아온다.

  • faults[] 배열은 4개의 타입 x 노드 수 x 2개로 구성되어 있다.
    • faults[4][nid][2]
    • 4개의 타입은 다음과 같다.
      • NUMA_MEM(0), NUMA_CPU(1), NUMA_MEMBUF(2), NUMA_CPUBUF(3)
  • faults[] 값들은 시간에 따라 exponential decay 된다.

 

task_faults_idx()

kernel/sched/fair.c

/*
 * The averaged statistics, shared & private, memory & cpu,
 * occupy the first half of the array. The second half of the
 * array is for current counters, which are averaged into the
 * first set by task_numa_placement.
 */
static inline int task_faults_idx(enum numa_faults_stats s, int nid, int priv)
{
        return NR_NUMA_HINT_FAULT_TYPES * (s * nr_node_ids + nid) + priv;
}

태스크에서 요청한 누마 id의 요청한 타입의 폴트 수를 알아온다.  priv가 0인 경우 shared stat, 1인 경우 private 카운터 값을 반환한다.

  • 예) 4개의 노드, NUMA_CPU stat, nid=2, priv=0
    • 인덱스 = 2 * (1 * 4 + 2) + 0 = 12
  • 예) 4개의 노드, NUMA_CPU stat, nid=3, priv=0
    • 인덱스 = 2 * (1 * 4 + 3) + 0 = 14

 

migrate_improves_locality()

kernel/sched/fair.c

/* Returns true if the destination node has incurred more faults */
static bool migrate_improves_locality(struct task_struct *p, struct lb_env *env)
{
        struct numa_group *numa_group = rcu_dereference(p->numa_group);
        int src_nid, dst_nid;

        if (!sched_feat(NUMA_FAVOUR_HIGHER) || !p->numa_faults ||
            !(env->sd->flags & SD_NUMA)) {
                return false;
        }

        src_nid = cpu_to_node(env->src_cpu);
        dst_nid = cpu_to_node(env->dst_cpu);

        if (src_nid == dst_nid)
                return false;

        if (numa_group) {
                /* Task is already in the group's interleave set. */
                if (node_isset(src_nid, numa_group->active_nodes))
                        return false;

                /* Task is moving into the group's interleave set. */
                if (node_isset(dst_nid, numa_group->active_nodes))
                        return true;

                return group_faults(p, dst_nid) > group_faults(p, src_nid);
        }

        /* Encourage migration to the preferred node. */
        if (dst_nid == p->numa_preferred_nid)
                return true;

        return task_faults(p, dst_nid) > task_faults(p, src_nid);
}

NUMA 밸런싱을 사용하는 경우 태스크의 마이그레이션이 locality를 상승시키는지 여부를 반환한다.  true인 경우 locality가 상승하므로 마이그레이션을 권장한다. (NUMA 밸런싱을 사용하지 않는 경우 항상 false)

  • 코드 라인 7~10에서 NUMA 또는 NUMA_FLAVOUR_HIGHER feature를 사용하지 않거나 태스크의 누마 폴트가 없으면 false를 반환한다.
  • 코드 라인 12~16에서 src 노드와 dst 노드가 같은 경우 false를 반환한다.
  • 코드 라인 18~21에서 태스크의 누마 그룹이 설정되어 있는 경우 src 노드가 누마 그룹의 active_nodes에 포함된 경우 false를 반환한다.
  • 코드 라인 24~25에서 dst 노드가 누마 그룹의 active_nodes에 포함된 경우 true를 반환한다. (locality 상승)
  • 코드 라인 27에서 태스크가 가리키는 누마 그룹에서 dst 노드의 폴트 수가 src 노드의 폴트 수보다 큰 경우 true를 반환한다. (locality 상승)
  • 코드 라인 31~32에서 dst 노드가 태스크가 권장하는 노드인 경우 true를 반환한다. (마이그레이션 하도록 한다.)
  • 코드 라인 34에서 태스크에서 dst 노드의 메모리 폴트 수가 src 노드의 메모리 폴트 수보다 큰 경우 true를 반환한다. (locality 상승)

 

nohz idle 밸런스

nohz_idle_balance()

/*
 * In CONFIG_NO_HZ_COMMON case, the idle balance kickee will do the
 * rebalancing for all the cpus for whom scheduler ticks are stopped.
 */
static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) 
{
        int this_cpu = this_rq->cpu;
        struct rq *rq;
        int balance_cpu;

        if (idle != CPU_IDLE ||
            !test_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu)))
                goto end;

        for_each_cpu(balance_cpu, nohz.idle_cpus_mask) {
                if (balance_cpu == this_cpu || !idle_cpu(balance_cpu))
                        continue;

                /*
                 * If this cpu gets work to do, stop the load balancing
                 * work being done for other cpus. Next load
                 * balancing owner will pick it up.
                 */
                if (need_resched())
                        break;

                rq = cpu_rq(balance_cpu);

                /*
                 * If time for next balance is due,
                 * do the balance.
                 */
                if (time_after_eq(jiffies, rq->next_balance)) {
                        raw_spin_lock_irq(&rq->lock);
                        update_rq_clock(rq);
                        update_idle_cpu_load(rq);
                        raw_spin_unlock_irq(&rq->lock);
                        rebalance_domains(rq, CPU_IDLE);
                }

                if (time_after(this_rq->next_balance, rq->next_balance))
                        this_rq->next_balance = rq->next_balance;
        }
        nohz.next_balance = this_rq->next_balance;
end:
        clear_bit(NOHZ_BALANCE_KICK, nohz_flags(this_cpu));
}

현재 cpu의 nohz 플래그 중 NOHZ_BALANCE_KICK 플래그가 설정된 cpu에 대해 로드 밸런싱을 시도한다.

  • 코드 라인 11~13에서 CPU_IDLE이 아니거나 NOHZ_BALANCE_KICK 플래그가 없는 경우 end 레이블로 이동하여 함수를 빠져나간다.
  • 코드 라인 15~17에서 nohz idle 중인 cpu를 순회한다. 현재 cpu인 경우 즉 이미 깨어났거나 또는 idle 중이 아니면 skip 한다.
  • 코드 라인 24~25에서 리스케줄 요청이 있는 경우 루프를 벗어난다.
  • 코드 라인 33~39에서 다음 밸런싱 시각을 넘어선 경우 순회 중인 cpu의 idle로 인한 cpu 로드를 갱신하고 CPU_IDLE로 밸런싱을 시도한다.
  • 코드 라인 41~42에서 요청한 런큐의 다음 밸런싱 시각을 순회 중인 다음 밸런싱 시각 중 가장 마지막에 위치한 시각으로 갱신하게 한다.
  • 코드 라인 44에서 nohz 다음 밸런싱 시각을 갱신한다.
  • 코드 라인 현재 cpu의 nohz 플래그에서 NOHZ_BALANCE_KICK 플래그를 제거한다.

 

update_idle_cpu_load()

kernel/sched/proc.c

/*
 * There is no sane way to deal with nohz on smp when using jiffies because the
 * cpu doing the jiffies update might drift wrt the cpu doing the jiffy reading
 * causing off-by-one errors in observed deltas; {0,2} instead of {1,1}.
 *
 * Therefore we cannot use the delta approach from the regular tick since that
 * would seriously skew the load calculation. However we'll make do for those
 * updates happening while idle (nohz_idle_balance) or coming out of idle
 * (tick_nohz_idle_exit).
 *
 * This means we might still be one tick off for nohz periods.
 */

/*
 * Called from nohz_idle_balance() to update the load ratings before doing the
 * idle balance.
 */
void update_idle_cpu_load(struct rq *this_rq)
{
        unsigned long curr_jiffies = ACCESS_ONCE(jiffies);
        unsigned long load = get_rq_runnable_load(this_rq);
        unsigned long pending_updates;

        /*
         * bail if there's load or we're actually up-to-date.
         */
        if (load || curr_jiffies == this_rq->last_load_update_tick)
                return; 

        pending_updates = curr_jiffies - this_rq->last_load_update_tick;
        this_rq->last_load_update_tick = curr_jiffies;

        __update_cpu_load(this_rq, load, pending_updates);
}

nohz idle 기간에 대한 cpu 로드를 갱신한다.

  • 코드 라인 21에서 요청한 런큐의 로드 값을 알아온다.
    • SMP의 경우 최상위 cfs 런큐의 러너블 로드 평균 값
    • UP의 경우 런큐의 로드 weight
  • 코드 라인 27~28에서 로드 값이 존재하거나 이미 갱신된 경우 함수를 빠져나간다.
  • 코드 라인 30~31에서 현재 시각에서 최종 갱신 시각을 뺀 시간(jiffies 수)을 산출하고 현재 시각으로 갱신한다.
  • 코드 라인 33에서 런큐의 cpu 로드를 갱신한다.

 

Schedule Features

# cat /sys/kernel/debug/sched_features 
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION ARCH_CAPACITY NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN
  •  feature를 설정하는 방법
    • echo HRTICK > sched_features
  • feature를 클리어하는 방법
    • echo NO_HRTICK > sched_features

 

구조체

lb_env 구조체

kernel/sched/fair.c

struct lb_env {
        struct sched_domain     *sd;

        struct rq               *src_rq;
        int                     src_cpu;

        int                     dst_cpu;
        struct rq               *dst_rq;

        struct cpumask          *dst_grpmask;
        int                     new_dst_cpu;
        enum cpu_idle_type      idle;
        long                    imbalance;
        /* The set of CPUs under consideration for load-balancing */
        struct cpumask          *cpus;

        unsigned int            flags;

        unsigned int            loop;
        unsigned int            loop_break;
        unsigned int            loop_max;

        enum fbq_type           fbq_type;
        struct list_head        tasks;
};
  • *sd
    • 로드밸런싱을 수행할 스케줄링 도메인
  • *src_rq
    • source 런큐
  • src_cpu
    • source cpu
  • dst_cpu
    • dest cpu
  • *dst_rq
    • dest 런큐
  • *dst_grpmask
    • dest 그룹의 cpu 마스크
  • new_dst_cpu
    • 새 dst cpu
  • idle
    • idle 타입
      • CPU_IDLE
        • 정규 틱에서 cpu가 idle 상태일 때 밸런싱 시도한 경우
      • CPU_NOT_IDLE
        • 정규 틱에서 cpu가 idle 상태가 아닐 때 밸런싱 시도한 경우
      • CPU_NEWLY_IDLE
        • 새롭게 cpu가 idle 상태가 되었을 때 밸런싱 시도한 경우
  • imbalance
    • 로드밸런싱이 필요한 강도만큼 수치가 설정된다.
    • 이 값이 클 수록 불균형 상태이므로 로드밸런싱 확률이 높아진다.
  • *cpus
    • 로드 밸런싱에 고려되는 cpu들에 대한 cpu mask
  • flags
    • LBF_ALL_PINNED(0x01)
      • 모든 태스크들을 마이그레이션 하지 못하는 상황이다.
    • LBF_NEED_BREAK(0x02)
      • loop_break 단위로 나누기 위해 마이그레이션 루프에서 잠시 빠져나온 후 다시 시도한다.
    • LBF_DST_PINNED(0x04)
      • 목적 cpu로 마이그레이션을 할 수 없는 상황이다.
    • LBF_SOME_PINNED(0x08)
      • 일부 태스크가 마이그레이션을 할 수 없는 상황이다.
  • loop
    • migration 진행 중인 내부 카운터
  • loop_break
    • loop가 이 값에 도달하면 루프를 멈추었다가 다시 시도한다.
  • loop_max
    • loop가 최대 수
  • fbq_type
    • regular(0)
    • remote(1)
    • all(2)
  • tasks
    • 로드밸런싱할 태스크 리스트

 

참고

답글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다.