Scheduler -15- (Load Balance-2)

 

Idle 밸런싱

현재 cpu의 런큐에서 수행시킬 태스크가 없어서 idle 상태에 진입하는데 그 전에 idle_balance()함수를 통해 다른 cpu에서 동작하는 태스크를 가져와서 동작시키게 할 수 있다.

idle_balance() 결과 값에 따라 결과 값이 양수인 경우 cfs 태스크가 있으므로 pick_next_task_fair()를 다시 시도하고 그 외의 결과 값인 경우 다음과 같다.

  • 음수인 경우RETRY_TASK를 반환하면 stop -> dl -> rt 순서로 태스크를 찾아 수행한다.
  • 0인 경우 NULL 반환하고 pick_next_task_idle()을 호출하여 idle로 진입한다.

 

idle_balance()

kernel/sched/fair.c – 1/3

/*
 * idle_balance is called by schedule() if this_cpu is about to become
 * idle. Attempts to pull tasks from other CPUs.
 */
static int idle_balance(struct rq *this_rq)
{
        unsigned long next_balance = jiffies + HZ;
        int this_cpu = this_rq->cpu;
        struct sched_domain *sd;
        int pulled_task = 0;
        u64 curr_cost = 0;

        idle_enter_fair(this_rq);

        /*
         * We must set idle_stamp _before_ calling idle_balance(), such that we
         * measure the duration of idle_balance() as idle time.
         */
        this_rq->idle_stamp = rq_clock(this_rq);

        if (this_rq->avg_idle < sysctl_sched_migration_cost ||
            !this_rq->rd->overload) {
                rcu_read_lock();
                sd = rcu_dereference_check_sched_domain(this_rq->sd);
                if (sd)
                        update_next_balance(sd, 0, &next_balance);
                rcu_read_unlock();

                goto out;
        }

idle 진입 시 idle 밸런싱을 시도한다. (결과: 0=수행할 태스크가 없다. -1=rt 또는 dl 태스크가 있다. 양수=cfs 태스크가 있다.)

  • 코드 라인 7에서 다음 밸런스 시각으로 현재 시각에서 1초를 더한다.
  • 코드 라인 13에서 idle 상태로 진입하기 전에 러너블 로드 평균을 갱신한다.
  • 코드 라인 19에서 idle 밸런싱 시각으로 현재 시각을 대입한다.
  • 코드 라인 21~30에서 평균 idle 시간이 너무 짧거나 오버로드된 상태가 아니면 out 레이블로 이동하여 idle 밸런싱을 skip 한다.  스케줄 도메인이 있는 경우 다음 밸런싱 시각을 갱신한다.
    • “/proc/sys/kernel/sched_migration_cost_ns”의 디폴트 값은 500,000 (ns)이다.

 

kernel/sched/fair.c – 2/3

.       /*
         * Drop the rq->lock, but keep IRQ/preempt disabled.
         */
        raw_spin_unlock(&this_rq->lock);

        update_blocked_averages(this_cpu);
        rcu_read_lock();
        for_each_domain(this_cpu, sd) {
                int continue_balancing = 1;
                u64 t0, domain_cost;

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

                if (this_rq->avg_idle < curr_cost + sd->max_newidle_lb_cost) {
                        update_next_balance(sd, 0, &next_balance);
                        break;
                }

                if (sd->flags & SD_BALANCE_NEWIDLE) {
                        t0 = sched_clock_cpu(this_cpu);

                        pulled_task = load_balance(this_cpu, this_rq,
                                                   sd, CPU_NEWLY_IDLE,
                                                   &continue_balancing);

                        domain_cost = sched_clock_cpu(this_cpu) - t0;
                        if (domain_cost > sd->max_newidle_lb_cost)
                                sd->max_newidle_lb_cost = domain_cost;

                        curr_cost += domain_cost;
                }

                update_next_balance(sd, 0, &next_balance);

                /*
                 * Stop searching for tasks to pull if there are
                 * now runnable tasks on this rq.
                 */
                if (pulled_task || this_rq->nr_running > 0)
                        break;
        }
        rcu_read_unlock();
  • 코드 라인 6에서 런큐에 매달린 모든 leaf cfs 런큐들에 대해 블럭드 로드 평균을 갱신하고 러너블 로드 평균에 더해 로드 평균을 갱신한다.
  • 코드 라인 8에서 요청한 cpu에 대해 최하위 스케줄 도메인부터 최상위 스케줄 도메인까지 순회한다.
  • 코드 라인 12~13에서 스케줄 도메인이 로드 밸런싱을 허용하지 않으면 skip 한다.
  • 코드 라인 15~18에서 평균 idle 시간(avg_idle)이 하위 도메인부터 누적된 밸런싱 소요 시간 + 현재 도메인에 대한 최대 밸런싱 소요 시간보다 작은 경우에는 밸런싱에 오버헤드가 발생하는 경우를 막기 위해 밸런싱을 하지 않는다. 다음 밸런싱 시각(+1초)을 갱신하고 루프를 벗어난다.
    • curr_cost
      • 하위 도메인부터 누적된 idle 밸런싱 소요 시간
    • domain_cost
      • 해당 도메인에 대한 idle 밸런싱 소요 시간
    • sd->max_newidle_lb_cost
      • 해당 도메인의 최대 idle 밸런싱 소요 시간
      • 매 스케줄 틱마다 수행되는 rebalance_domains() 함수를 통해 1초에 1%씩 줄어든다.
  • 코드 라인 20~25에서 순회 중인 스케줄 도메인이 newidle을 허용하는 경우 idle 로드밸런싱을 수행하고 마이그레이션을 한 태스크 수를 알아온다.
  • 코드 라인 27~31에서 순회 중인 도메인에서 idle 로드밸런싱에서 소요된 시간을 curr_cost에 누적시킨다. 또한 순회 중인 도메인의 idle 밸런싱 시간이 도메인의 max_newidle_lb_cost보다 큰 경우 갱신한다.
  • 코드 라인 34에서 다음 밸런싱 시각을 갱신(+1초)한다.
  • 코드 라인 40~41에서 마이그레이션한 태스크가 있거나 현재 동작 중인 엔티티가 1개 이상인 경우 루프를 벗어난다.
    • 이 cpu의 런큐에 일감(?)이 생겼으므로 idle 상태로 진입할 필요가 없어졌다.

 

kernel/sched/fair.c – 3/3

        raw_spin_lock(&this_rq->lock);

        if (curr_cost > this_rq->max_idle_balance_cost)
                this_rq->max_idle_balance_cost = curr_cost;

        /*
         * While browsing the domains, we released the rq lock, a task could
         * have been enqueued in the meantime. Since we're not going idle,
         * pretend we pulled a task.
         */
        if (this_rq->cfs.h_nr_running && !pulled_task)
                pulled_task = 1;

out:
        /* Move the next balance forward */
        if (time_after(this_rq->next_balance, next_balance))
                this_rq->next_balance = next_balance;

        /* Is there a task of a high priority class? */
        if (this_rq->nr_running != this_rq->cfs.h_nr_running)
                pulled_task = -1;

        if (pulled_task) {
                idle_exit_fair(this_rq);
                this_rq->idle_stamp = 0;
        }

        return pulled_task;
}
  • 코드 라인 3~4에서 idle 밸런싱에 사용한 시간이 현재 런큐의 max_idle_balance_cost를 초과한 경우 갱신한다.
  • 코드 라인 11~12에서 idle 밸런스를 통해 마이그레이션을 한 태스크가 없지만 그 사이에 새로운 태스크가 cfs 런큐에 엔큐된 경우 idle 상태로 진입할 필요 없으므로 pulled_task=1로 대입한다.
  • 코드 라인 16~17에서 런큐에 지정된 다음 밸런싱 시각이 이미 경과한 경우 그 시각으로 갱신한다.
  • 코드 라인 20~21에서 현재 런큐에 cfs 태스크보다 빠른 우선 순위를 가진 태스크(stop, rt, dl)가 있는 경우 pulled_task=-1을 대입하여 idle 상태로 진입할 필요를 없앤다.
  • 코드 라인 23~26에서 현재 cpu에 수행할 태스크가 있어 idle에 진입할 필요가 없는 경우이다. 러너블 로드 평균을 갱신하고 idle_stamp를 0으로 초기화한다.
  • 코드 라인 28에서 마이그레이션된 태스크 수를 반환한다. 0=수행할 태스크가 없다. -1=rt 또는 dl 태스크가 있다. 양수=cfs 태스크가 있다.

 

다음 그림은 idle_balance()의 처리 과정을 보여준다.

 

idle_enter_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed running time before entering
 * idle. if the last scheduled task is not a CFS task, idle_enter will
 * be the only way to update the runnable statistic.
 */
void idle_enter_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 1);
}

idle 상태로 진입하기 전에 러너블 로드 평균을 갱신한다.

 

idle_exit_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed idle time before a task is
 * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
 * be the only way to update the runnable statistic.
 */
void idle_exit_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 0);
}

idle 상태를 빠져나가면서 러너블 로드 평균을 갱신한다.

 

update_rq_runnable_avg()

kernel/sched/fair.c

static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
{
        __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
        __update_tg_runnable_avg(&rq->avg, &rq->cfs);
}

런큐의 러너블 로드 평균을 갱신하고 cfs 런큐에도 적용하고 tg에 합산한다.

  • 코드 라인 3에서 런큐의 러너블 로드 평균을 갱신한다.
  • 코드 라인 4에서 런큐의 러너블 로드 평균을 최상위 cfs 런큐에 적용하고 tg에 합산한다.

 

update_blocked_averages()

kernel/sched/fair.c

static void update_blocked_averages(int cpu)
{
        struct rq *rq = cpu_rq(cpu);
        struct cfs_rq *cfs_rq;
        unsigned long flags;

        raw_spin_lock_irqsave(&rq->lock, flags);
        update_rq_clock(rq);
        /*
         * Iterates the task_group tree in a bottom up fashion, see
         * list_add_leaf_cfs_rq() for details.
         */
        for_each_leaf_cfs_rq(rq, cfs_rq) {
                /*
                 * Note: We may want to consider periodically releasing
                 * rq->lock about these updates so that creating many task
                 * groups does not result in continually extending hold time.
                 */
                __update_blocked_averages_cpu(cfs_rq->tg, rq->cpu);
        }

        raw_spin_unlock_irqrestore(&rq->lock, flags);
}

런큐에 매달린 모든 leaf cfs 런큐들에 대해 블럭드 로드 평균을 갱신하고 러너블 로드 평균에 더해 로드 평균을 갱신한다.

  • rq->leaf_cfs_rq_list에 leaf cfs 런큐들이 매달려 있다.
  • leaf cfs 런큐는 태스크가 연결된 cfs 런큐로 중복되지 않는다.

 

__update_blocked_averages_cpu()

kernel/sched/fair.c

/*
 * update tg->load_weight by folding this cpu's load_avg
 */
static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
{
        struct sched_entity *se = tg->se[cpu];
        struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];

        /* throttled entities do not contribute to load */
        if (throttled_hierarchy(cfs_rq))
                return;

        update_cfs_rq_blocked_load(cfs_rq, 1);

        if (se) {
                update_entity_load_avg(se, 1);
                /*
                 * We pivot on our runnable average having decayed to zero for
                 * list removal.  This generally implies that all our children
                 * have also been removed (modulo rounding error or bandwidth
                 * control); however, such cases are rare and we can fix these
                 * at enqueue.
                 *
                 * TODO: fix up out-of-order children on enqueue.
                 */
                if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
                        list_del_leaf_cfs_rq(cfs_rq);
        } else {
                struct rq *rq = rq_of(cfs_rq);
                update_rq_runnable_avg(rq, rq->nr_running);
        }
}

블럭드 로드 평균을 갱신하고 러너블 로드 평균과 더해 로드 평균을 갱신한다.

  • 코드 라인 10~11에서 태스크 그룹에 해당하는 cfs 런큐가 스로틀 중인 경우 그 cfs 런큐에 있는 엔티티들의 로드는 산출할 필요 없다.
  • 코드 라인 13에서 cfs 런큐의 블럭드 로드 평균을 갱신하고 러너블 로드 평균과 더해 로드 평균을 갱신한다.
  • 코드 라인 15~16에서 루트 태스크 그룹이 아닌 경우 그 그룹에 대한 스케줄 엔티티의 로드 평균을 갱신한다.
  • 코드 라인 26~27에서 러너블 평균 합이 0이면서 엔티티가 존재하지 않으면 cfs 런큐를 런큐의 leaf cfs 런큐 리스트에서 제거한다.
  • 코드 라인 28~31에서 루트 그룹인 경우 런큐의 러너블 로드 평균을 갱신한다.

 

Fork 밸런싱

wake_up_new_task()

kernel/sched/core.c

/*
 * wake_up_new_task - wake up a newly created task for the first time.
 *
 * This function will do some initial scheduler statistics housekeeping
 * that must be done for every newly created context, then puts the task
 * on the runqueue and wakes it.
 */
void wake_up_new_task(struct task_struct *p)
{
        unsigned long flags;
        struct rq *rq;
 
        raw_spin_lock_irqsave(&p->pi_lock, flags);
#ifdef CONFIG_SMP
        /*
         * Fork balancing, do it here and not earlier because:
         *  - cpus_allowed can change in the fork path
         *  - any previously selected cpu might disappear through hotplug
         */ 
        set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
#endif 

        /* Initialize new task's runnable average */
        init_task_runnable_average(p);
        rq = __task_rq_lock(p);
        activate_task(rq, p, 0);
        p->on_rq = TASK_ON_RQ_QUEUED;
        trace_sched_wakeup_new(p, true);
        check_preempt_curr(rq, p, WF_FORK);
#ifdef CONFIG_SMP
        if (p->sched_class->task_woken)
                p->sched_class->task_woken(rq, p);
#endif
        task_rq_unlock(rq, p, &flags);
}

새로운 태스크에 대해 밸런싱을 수행한다.

  • 코드 라인 20에서 fork 밸런싱을 통해 태스크가 수행될 cpu를 선택한다.
  • 코드 라인 24에서 새 태스크에 대한 러너블 로드를 초기화한다.
  • 코드 라인 25~27에서 런큐에 태스크를 엔큐한다.
  • 코드 라인 29에서 preemption 여부를 체크한다.
  • 코드 라인 31~32에서 dl 또는 rt 태스크가 러닝 중이 아니면서 곧 리스케줄도 하지 않을 것 같은 태스크에 대해 push 처리한다.

 

init_task_runnable_average()

kernel/sched/fair.c

/* Give new task start runnable values to heavy its load in infant time */
void init_task_runnable_average(struct task_struct *p)
{
        u32 slice;
        
        slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
        p->se.avg.runnable_avg_sum = slice;
        p->se.avg.runnable_avg_period = slice;
        __update_task_entity_contrib(&p->se);
}

새 태스크에 대한 러너블 로드를 초기화한다

  • 코드 라인 6~8에서 태스크에 대한 time slice를 구해 러너블 평균 합과 기간으로 초기화한다. 태스크의 초반에는 이렇게 큰 값을 준다.
  • 코드 라인 9에서 태스크의 러너블 로드 평균을 산출한다.

 

select_task_rq()

kernel/sched/core.c

/*
 * The caller (fork, wakeup) owns p->pi_lock, ->cpus_allowed is stable.
 */
static inline
int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)
{
        if (p->nr_cpus_allowed > 1)
                cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags);

        /*
         * In order not to call set_task_cpu() on a blocking task we need
         * to rely on ttwu() to place the task on a valid ->cpus_allowed
         * cpu.
         *
         * Since this is common to all placement strategies, this lives here.
         *
         * [ this allows ->select_task() to simply return task_cpu(p) and
         *   not worry about this generic constraint ]
         */
        if (unlikely(!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)) ||
                     !cpu_online(cpu)))
                cpu = select_fallback_rq(task_cpu(p), p);

        return cpu;
}

태스크가 동작할 적절한 cpu를 찾아 선택한다.

  • 코드 라인 7~8에서 태스크가 동작 할 수 있는 cpu가 2개 이상인 경우 밸런싱을 통해 태스크가 동작할 적절한 cpu를 찾아 선택한다.
    • dl 태스크의 경우 select_task_rq_dl() 함수를 호출하며 wake 밸런싱인 경우에만 deadline이 가장 여유 있는 cpu를 선택한다.
    • rt 태스크의 경우 select_task_rq_rt() 함수를 호출하며 wake 또는 fork 밸런싱인 경우에만 가장 낮은 우선 순위부터 요청한 태스크의 우선순위 범위 이내에서 동작할 수 있는 cpu cpu를 찾아 선택한다.
    • cfs 태스크의 경우 select_task_rq_fair() 함수를 호출하여 적절한 cpu를 선택한다.
  • 코드 라인 20~22에서 낮은 확률로 선택된 cpu가 태스크에 허용되지 않는 cpu인 경우이거나 online되지 않은 cpu인 경우 fallback cpu를 찾는다.

 

select_task_rq_fair()

kernel/sched/fair.c – 1/2

/*
 * select_task_rq_fair: Select target runqueue for the waking task in domains
 * that have the 'sd_flag' flag set. In practice, this is SD_BALANCE_WAKE,
 * SD_BALANCE_FORK, or SD_BALANCE_EXEC.
 *
 * Balances load by selecting the idlest cpu in the idlest group, or under
 * certain conditions an idle sibling cpu if the domain has SD_WAKE_AFFINE set.
 *
 * Returns the target cpu number.
 *
 * preempt must be disabled.
 */
static int
select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)
{
        struct sched_domain *tmp, *affine_sd = NULL, *sd = NULL;
        int cpu = smp_processor_id();
        int new_cpu = cpu;
        int want_affine = 0;
        int sync = wake_flags & WF_SYNC;

        if (sd_flag & SD_BALANCE_WAKE)
                want_affine = cpumask_test_cpu(cpu, tsk_cpus_allowed(p));

        rcu_read_lock();
        for_each_domain(cpu, tmp) {
                if (!(tmp->flags & SD_LOAD_BALANCE))
                        continue;

                /*
                 * If both cpu and prev_cpu are part of this domain,
                 * cpu is a valid SD_WAKE_AFFINE target.
                 */
                if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
                    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
                        affine_sd = tmp;
                        break;
                }

                if (tmp->flags & sd_flag)
                        sd = tmp;
        }

        if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
                prev_cpu = cpu;

        if (sd_flag & SD_BALANCE_WAKE) {
                new_cpu = select_idle_sibling(p, prev_cpu);
                goto unlock;
        }
  • 코드 라인 22~23에서 wake 밸런싱인 경우 현재 cpu가 태스크가 허용하는 cpu에 포함되었는지 여부를 알아와서 want_affine에 대입한다.
  • 코드 라인 26~28에서 현재 cpu의 최하위 도메인에서 최상위 도메인 까지 순회를 하며 밸런싱을 허용하지 않는 도메인에 대해서는 skip 한다.
  • 코드 라인 34~38에서 SD_WAKE_AFFINE 플래그가 있는 도메인이고 태스크도 허용하는 cpu이며 태스크가 idle 되기 전에 동작했었던 prev_cpu가 순회 중인 도메인의 cpu에 포함된 경우 affine_sd에 현재 도메인을 대입하고 루프를 빠져나온다.
    • SD_WAKE_AFFINE 플래그가 있는 도메인
      • 이 도메인은 idle 상태에서 깨어난 cpu가 도메인내의 idle sibling cpu 선택을 허용한다.
      • NUMA distance가 30이상 되는 원거리에 있는 누마 노드에 wake된 태스크가 마이그레이션하는 일 없도록 할 때 이 플래그를 사용하지 않는다.
  • 코드 라인 40~41에서 순회 중인 도메인에 sd_flag가 있는 경우 sd에 현재 순회중인 도메인을 대입한다.
  • 코드 라인 44~45에서 affine_sd가 설정되었고 현재 cpu에 태스크를 수행하는 것이 캐시(hot) 활용에 더 도움이 되는 경우 prev_cpu에 현재 cpu를 대입한다.
  • 코드 라인 47~50에서 wake 밸런싱인 경우 prev_cpu가 idle한 경우 prev_cpu를 선택하고 그렇지 않은 경우 캐시 친화력이 도메인에 속한 cpu들 및 태스크에 허용한 cpu들에 대해 적절한 idle cpu를 선택한다 unlock 레이블로 이동해서 함수를 빠져나간다.

 

kernel/sched/fair.c – 2/2

        while (sd) {
                struct sched_group *group;
                int weight;

                if (!(sd->flags & sd_flag)) {
                        sd = sd->child;
                        continue;
                }

                group = find_idlest_group(sd, p, cpu, sd_flag);
                if (!group) {
                        sd = sd->child;
                        continue;
                }

                new_cpu = find_idlest_cpu(group, p, cpu);
                if (new_cpu == -1 || new_cpu == cpu) {
                        /* Now try balancing at a lower domain level of cpu */
                        sd = sd->child;
                        continue;
                }

                /* Now try balancing at a lower domain level of new_cpu */
                cpu = new_cpu;
                weight = sd->span_weight;
                sd = NULL;
                for_each_domain(cpu, tmp) {
                        if (weight <= tmp->span_weight)
                                break;
                        if (tmp->flags & sd_flag)
                                sd = tmp;
                }
                /* while loop will break here if sd == NULL */
        }
unlock:
        rcu_read_unlock();

        return new_cpu;
}
  • 코드 라인 1~8에서 스케줄 도메인이 null이 아닌 한 루프를 수행한다.  만일 도메인에 요청한 도메인 플래그(sd_flag)가 없으면 child 도메인을 선택하고 계속한다.
  • 코드 라인 10~14에서 도메인에서 idle 상태인 스케줄링 그룹을 찾는다. 만일 찾지 못한 경우 child 도메인을 선택하고 계속한다.
  • 코드 라인 16~21에서 스케줄 그룹에서 idle 상태인 cpu를 찾는다. 만일 찾지 못한 경우 child 도메인을 선택하고 계속한다.
  • 코드 라인 24~29에서 선택한 idle cpu의 최하위 도메인부터 최상위 도메인까지 순회하며 순회 중인 도메인에 속한 cpu 수가 마지막 선택한 도메인에 속한 cpu 수 이상인 경우 루프를 벗어난다.
  • 코드 라인 30~32에서 순회 중인 도메인의 플래그에 sd_flag가 하나라도 포함된 경우 sd에 현재 순회 중인 도메인을 기억한다. sd가 null이 아닌 한 계속 루프를 돈다.

 

wake_affine()

kernel/sched/fair.c – 1/2

static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
{
        s64 this_load, load;
        s64 this_eff_load, prev_eff_load;
        int idx, this_cpu, prev_cpu;
        struct task_group *tg;
        unsigned long weight;
        int balanced;

        /*
         * If we wake multiple tasks be careful to not bounce
         * ourselves around too much.
         */
        if (wake_wide(p))
                return 0;

        idx       = sd->wake_idx;
        this_cpu  = smp_processor_id();
        prev_cpu  = task_cpu(p);
        load      = source_load(prev_cpu, idx);
        this_load = target_load(this_cpu, idx);

        /*
         * If sync wakeup then subtract the (maximum possible)
         * effect of the currently running task from the load
         * of the current CPU:
         */
        if (sync) {
                tg = task_group(current);
                weight = current->se.load.weight;

                this_load += effective_load(tg, this_cpu, -weight, -weight);
                load += effective_load(tg, prev_cpu, 0, -weight);
        }

        tg = task_group(p);
        weight = p->se.load.weight;

현재 cpu에서 태스크가 동작하는 것이 캐시(cache hot) 활용에 더 도움이 되는지 여부를 반환한다.

 

  • 코드 라인 14~15에서 현재 동작 중인 태스크가 요청한 태스크보다 wake 스위칭이 더 빈번한 경우 0을 반환한다.
    • hot cache 유지를 위해 빈번한 스위칭을 막는다.
  • 코드 라인 20에서 기존 태스크에서 동작한 prev_cpu의 보수적인 로드 값을 알아온다.
    • 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 작은 로드 값
  • 코드 라인 21에서 현재 cpu의 적극적인 로드 값을 알아온다.
    • 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 큰 로드 값
  • 코드 라인 28~34에서 sync(blocked) 요청인 경우 this_load 및 load에서 각각의 최대 possible 로드 값을 산출해 뺀다.
    • 태스크가 속한 태스크 그룹을 알아오고 태스크에 대한 로드 weight을 알아온다.
  • 코드 라인 36~37에서 태스크가 속한 태스크 그룹을 알아오고 태스크에 대한 로드 weight을 알아온다.

 

kernel/sched/fair.c – 2/2

        /*
         * In low-load situations, where prev_cpu is idle and this_cpu is idle
         * due to the sync cause above having dropped this_load to 0, we'll
         * always have an imbalance, but there's really nothing you can do
         * about that, so that's good too.
         *
         * Otherwise check if either cpus are near enough in load to allow this
         * task to be woken on this_cpu.
         */
        this_eff_load = 100;
        this_eff_load *= capacity_of(prev_cpu);

        prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
        prev_eff_load *= capacity_of(this_cpu);

        if (this_load > 0) {
                this_eff_load *= this_load +
                        effective_load(tg, this_cpu, weight, weight);

                prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
        }

        balanced = this_eff_load <= prev_eff_load;

        schedstat_inc(p, se.statistics.nr_wakeups_affine_attempts);

        if (!balanced)
                return 0;

        schedstat_inc(sd, ttwu_move_affine);
        schedstat_inc(p, se.statistics.nr_wakeups_affine);

        return 1;
}
  • 코드 라인 10~11에서 prev_cpu의 capacity를 100%를 곱한다.
    • 예) cortex-a7 cpu capacity가 430인 경우
      • = 430 * 100 = 43000
    • 예) cortex-a15 cpu capacity가 1535인 경우
      • = 1535 * 100 = 1535000
    • 단 시스템에서 동일한 성능의 cpu를 사용한 경우 cpu capacity는 항상 1024이다.
  • 코드 라인 13~14에서 100을 초과하는 도메인의 imbalance_pct 값의 절반을 100에 더한 후 현재 cpu의 capacity에 곱한다.
    • 예) cortex-a7 cpu capacity가 430, imbalance_pct=125인 경우
      • = 430 * 112 = 48160
    • 예) cortex-a15 cpu capacity가 1535, imbalance_pct=125인 경우
      • 1535 * 112 = 171920
  • 코드 라인 16~21에서 현재 cpu에 대한 this_load 값이 0보다 큰 경우 this_eff_load와 prev_eff_load에 각각 effective load를 산출하여 추가한다.
  • 코드 라인 23에서 현재 cpu에서 산출한 로드보다 기존 cpu의 산출한 로드값이 크거나 같은 경우 balance=1을 대입한다.
    • 1이 산출된 경우 현재 cpu에 태스크가 수행되도록한다. (wake affine하여 밸런싱 성공)
  • 코드 라인 25에서 nr_wakeups_affine_attempts 카운터를 1 증가시킨다.
  • 코드 라인 27~28에서 현재 cpu에 태스크가 동작하는 것이 더 안좋은 경우(밸런스되지 않은 경우) 0을 반환한다.
  • 코드 라인 30~33에서 ttwu_move_affine 및 nr_wakeups_affine 카운터를 각각 1씩 증가 시키고 1을 반환한다. (wake affine하여 밸런싱 성공)

 

wake_wide()

kernel/sched/fair.c

static int wake_wide(struct task_struct *p)
{
        int factor = this_cpu_read(sd_llc_size);

        /*
         * Yeah, it's the switching-frequency, could means many wakee or
         * rapidly switch, use factor here will just help to automatically
         * adjust the loose-degree, so bigger node will lead to more pull.
         */
        if (p->wakee_flips > factor) {
                /*
                 * wakee is somewhat hot, it needs certain amount of cpu
                 * resource, so if waker is far more hot, prefer to leave
                 * it alone.
                 */
                if (current->wakee_flips > (factor * p->wakee_flips))
                        return 1;
        }

        return 0;
}

현재 동작 중인 태스크가 요청한 태스크보다 wake 스위칭이 더 빈번한 경우 1을 반환한다.

  • 코드 라인 3에서 패키지 내에서 캐시를 공유하는 cpu 수를 알아와서 factor에 대입한다.
    • SD_SHARE_PKG_RESOURCES 플래그가 있는 스케줄 도메인(복수개인 경우 상위 도메인)에 소속된 cpu 수
  • 코드 라인 10에서 요청한 태스크의 wake 스위칭(wakee_flips) 횟수가 factor 값보다 큰 경우에 한해
  • 코드 라인 16~17에서 현재 태스크의 wake 스위칭(wake_flips) 횟수가 factor 배율을 적용한 현재 태스크의 wakee_flips 보다 큰 경우 1을 반환한다.
    • 예) 캐시 공유 cpu 수=4, 현재 태스크가 9번 스위칭, 밸런스 요청한 태스크가 2번인 경우
      • 9 > (4 x 2) = 1을 반환하여 더 hot한 현재 태스크가 유지되도록 1을 반환한다.

 

effective_load()

kernel/sched/fair.c – 1/2

/*
 * effective_load() calculates the load change as seen from the root_task_group
 *
 * Adding load to a group doesn't make a group heavier, but can cause movement
 * of group shares between cpus. Assuming the shares were perfectly aligned one
 * can calculate the shift in shares.
 *
 * Calculate the effective load difference if @wl is added (subtracted) to @tg
 * on this @cpu and results in a total addition (subtraction) of @wg to the
 * total group weight.
 *
 * Given a runqueue weight distribution (rw_i) we can compute a shares
 * distribution (s_i) using:
 *
 *   s_i = rw_i / \Sum rw_j                                             (1)
 *
 * Suppose we have 4 CPUs and our @tg is a direct child of the root group and
 * has 7 equal weight tasks, distributed as below (rw_i), with the resulting
 * shares distribution (s_i):
 *
 *   rw_i = {   2,   4,   1,   0 }
 *   s_i  = { 2/7, 4/7, 1/7,   0 }
 *
 * As per wake_affine() we're interested in the load of two CPUs (the CPU the
 * task used to run on and the CPU the waker is running on), we need to
 * compute the effect of waking a task on either CPU and, in case of a sync
 * wakeup, compute the effect of the current task going to sleep.
 *
 * So for a change of @wl to the local @cpu with an overall group weight change
 * of @wl we can compute the new shares distribution (s'_i) using:
 *
 *   s'_i = (rw_i + @wl) / (@wg + \Sum rw_j)                            (2)
 *
 * Suppose we're interested in CPUs 0 and 1, and want to compute the load
 * differences in waking a task to CPU 0. The additional task changes the
 * weight and shares distributions like:
 *
 *   rw'_i = {   3,   4,   1,   0 }
 *   s'_i  = { 3/8, 4/8, 1/8,   0 }
 *
 * We can then compute the difference in effective weight by using:
 *
 *   dw_i = S * (s'_i - s_i)                                            (3)
 *
 * Where 'S' is the group weight as seen by its parent.
 *
 * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7)
 * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 -
 * 4/7) times the weight of the group.
 */

루트 태스크 그룹에서 본 effective 로드 값을 산출한다.

  • weight 변화분(wl)을 요청한 cpu의 그룹(tg)에 가감할 때의 유효 로드 변경분을 산출한다.
  • 주어진 런큐 weight(rw_i)을 전체 런큐 weight으로 나누어 공유 배분(s_i)을 산출한다.
    • (1) s_i = rw_i / \Sum rw_j
      • 공유 배분(s_i) = 요청 런큐 weight(rw_i) / 전체 런큐 weight(\Sum rw_j)
  • 4개의 cpu와 최상위  루트 그룹의 자식 태스크 그룹(tg)에 7개의 동일한 weight을 가진 태스크들이 있다고 가정한다. 이 때 각 cpu의 런큐 weight 배분(rw_i)과 공유 배분(s_i)은 다음과 같다.
    • rw_i = { 2, 4, 1, 0 }
      • cpu별 런큐 weight(rw_i)
    • s_i = { 2/7, 4/7, 1/7, 0 }
      • cpu별 공유 배분(s_i)
  • wake_affine() 함수에 따라 두 개의 cpu 로드에 관심이 있다. 태스크가 수행되던 기존 cpu와 깨어나서 동작할 cpu 둘 중, 어느 cpu에서 태스크가 깨어나야 더 효과적인지 계산해야 한다. 그리고 sync wakeup인 경우 현재 태스크가 sleep할 때의 효과도 산출해야 한다.
  • 로컬 cpu의 런큐 weight(rw_i)에 weight(wl) 변화분을 적용한 값을 전체 cpu의 런큐 weight(\Sum rw_j)에 그룹 weight 변화분(wg)을 적용한 값으로 나누면 새 공유 배분(s’_i)을 계산할 수 있다.
    • (2) s’_i = (rw_i + @wl) / (@wg + \Sum rw_j)
      • 새 공유 배분(s’_i) = (로컬 cpu 런큐 weight(rw_i) + weight 변화분(wl)) / (그룹 weight 변화분(wg) + 전체 cpu 런큐 weight(\Sum rw_j))
  • cpu 0번과 1번에 관심이 있다고 가정하고 cpu 0번에서 태스크가 깨어날 때의 로드 변화분을 산출해본다. 추가 태스크의 변화에 따른 런큐 weight과 공유 배분은 다음과 같다.
    • rw’_i = { 3, 4, 1, 0 }
      • weight 변화분(wl)이 추가된 cpu별 런큐 weight(rw_i)
    • s’_i = { 3/8, 4/8, 1/8, 0 }
      • 그룹 weight 변화분(wg)이 추가된 cpu별 공유 배분 weight(s’_i)
  • 다음과 같이 유효 로드 변경분을 산출할 수 있다.
    • (3) dw_i = S * (s’_i – s_i)
      • 런큐 weight 변경분(dw_i) = 부모 그룹 weight(S) * (새 공유 배분(s’_i) – 공유 배분(s_i))
  • 결국 cpu 0에서 그룹 weight * 5/56 (=3/8 – 2/7)의 effective 로드값을 얻고, cpu 1은 그룹 weight * -4/56 (= 4/8 – 4/7)의 effective 로드값을 얻는다.

 

kernel/sched/fair.c – 2/2

static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
{
        struct sched_entity *se = tg->se[cpu];

        if (!tg->parent)        /* the trivial, non-cgroup case */
                return wl;

        for_each_sched_entity(se) {
                long w, W;

                tg = se->my_q->tg;

                /*
                 * W = @wg + \Sum rw_j
                 */
                W = wg + calc_tg_weight(tg, se->my_q);

                /*
                 * w = rw_i + @wl
                 */
                w = se->my_q->load.weight + wl;

                /*
                 * wl = S * s'_i; see (2)
                 */
                if (W > 0 && w < W)
                        wl = (w * (long)tg->shares) / W;
                else
                        wl = tg->shares;

                /*
                 * Per the above, wl is the new se->load.weight value; since
                 * those are clipped to [MIN_SHARES, ...) do so now. See
                 * calc_cfs_shares().
                 */
                if (wl < MIN_SHARES)
                        wl = MIN_SHARES;

                /*
                 * wl = dw_i = S * (s'_i - s_i); see (3)
                 */
                wl -= se->load.weight;

                /*
                 * Recursively apply this logic to all parent groups to compute
                 * the final effective load change on the root group. Since
                 * only the @tg group gets extra weight, all parent groups can
                 * only redistribute existing shares. @wl is the shift in shares
                 * resulting from this level per the above.
                 */
                wg = 0;
        }

        return wl;
}

이 함수는 그룹 스케줄링을 사용하는 NUMA 밸런싱을 위해 사용되었는데 최근 커널 v4.13-rc1에서 numa_wake_affine() 함수에 구현을 바꾸었으므로 이 함수가 필요 없어져서 제거하였다.

 

  • 코드 라인 5~6에서 그룹 스케줄링을 사용하지 않는 경우 wl을 그대로 반환한다.
  • 코드 라인 8~11에서 태스크가 위치한 태스크 그룹을 대표하는 스케줄 엔티티부터 최상위 엔티티까지 순회하며 대응하는 태스크 그룹 tg를 알아온다.
    • 결국 요청한 태스크 그룹부터 루트 그룹의 직전 child 그룹까지 순회한다.
  • 코드 라인 16에서 전체 런큐 weight인 tg weight에 그룹 weight 변화분(wg)을 더해 분모쪽 W를 산출한다.
  • 코드 라인 21에서 요청한 cpu의 런큐 weight에 로컬 weight 변화분(wl)을 더해 분자쪽 w를 산출한다.
  • 코드 라인 26~29에서 w/W가 적용된 공유 배분을 구한다.
    • (2) tg->shares * w / W
    • w/W가 1을 초과하면 비율을 사용하지 않고 그냥 tg->shares를 사용한다.
  • 코드 라인 36~37에서 공유 배분이 최소 값(2) 미만으로 내려가지 않게 제한한다.
  • 코드 라인 42에서 산출한 wl에서 요청한 cpu의 그룹 weight을 빼는 것으로 상위 그룹에 대한 effective 로드 변경값을 구한다.
  • 코드 라인 51~54에서 마지막까지 루프를 반복하면 루트 그룹에 대한 effective 로드 값을 구할 수 있게 된다.

 

다음 그림은 wakeup할 태스크가 기존 cpu와 현재 cpu 둘 중 어느쪽에서 동작하는 것이 효과적인지 산출해내는 모습을 보여준다.

 

select_idle_sibling()

kernel/sched/fair.c

/*
 * Try and locate an idle CPU in the sched_domain.
 */
static int select_idle_sibling(struct task_struct *p, int target)
{
        struct sched_domain *sd;
        struct sched_group *sg;
        int i = task_cpu(p);

        if (idle_cpu(target))
                return target;

        /*
         * If the prevous cpu is cache affine and idle, don't be stupid.
         */
        if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
                return i;

        /*
         * Otherwise, iterate the domains and find an elegible idle cpu.
         */
        sd = rcu_dereference(per_cpu(sd_llc, target));
        for_each_lower_domain(sd) {
                sg = sd->groups;
                do {
                        if (!cpumask_intersects(sched_group_cpus(sg),
                                                tsk_cpus_allowed(p)))
                                goto next;

                        for_each_cpu(i, sched_group_cpus(sg)) {
                                if (i == target || !idle_cpu(i))
                                        goto next;
                        }

                        target = cpumask_first_and(sched_group_cpus(sg),
                                        tsk_cpus_allowed(p));
                        goto done;
next:
                        sg = sg->next;
                } while (sg != sd->groups);
        }
done:
        return target;
}

요청한 target cpu가 idle한 경우 target cpu를 선택하고 그렇지 않은 경우 캐시 친화력이 도메인에 속한 cpu들 및 태스크에 허용한 cpu들에 대해 적절한 idle cpu를 선택한다.

  • 코드 라인 8에서 태스크가 동작했었던 cpu를 알아온다.
  • 코드 라인 10~11에서 인수 target cpu가 idle 상태인 경우 target cpu를 반환한다.
  • 코드 라인 16~17에서 target cpu와 태스크가 동작했었던 cpu가 다르지만 두 cpu끼리 캐시 친화력이 높고 기존 태스크 cpu가 idle cpu인 경우 기존 태스크 cpu를 반환한다. (바보같이 마이그레이션을 할 필요가 없다.)
    • arm의 경우 MC 도메인 토플로지 레벨에만 SD_SHARE_PKG_RESOURCE 플래그가 설정되어 있고, 이 도메인의 cpu들은 서로 캐시를 공유하여 캐시 친화력이 높은 도메인이다. (L2 캐시 등)
  • 코드 라인 22에서 target cpu에 대해 캐시 친화력이 있는 만큼의 상위 도메인을 선택한다.
  • 코드 라인 23에서 최하위 도메인까지 순회한다.
  • 코드 라인 24~28에서 두 번째 루프로 스케줄링 그룹을 순회하고 태스크가 허용하는 cpu가 없는 스케줄 그룹인 경우 next 레이블로 이동하여 그룹을 skip 한다.
  • 코드 라인 30~33에서 스케줄 그룹에 포함된 cpu에서 기존 태스크 cpu 이거나 idle 하지 않는 cpu의 경우 next 레이블로 이동하여 그룹을 skip 한다.
  • 코드 라인 35~37에서 스케줄 그룹의 cpu들 중 태스크가 허용하는 cpu에 대해 가장 처음 cpu를 target으로 반환한다.

 

cpus_share_cache()

kernel/sched/core.c

bool cpus_share_cache(int this_cpu, int that_cpu)
{       
        return per_cpu(sd_llc_id, this_cpu) == per_cpu(sd_llc_id, that_cpu);
}

요청한 두 cpu가 같은 캐시 친화력을 공유하는지 여부를 반환한다.

 

find_idlest_group()

kernel/sched/fair.c

/*
 * find_idlest_group finds and returns the least busy CPU group within the
 * domain.
 */
static struct sched_group *
find_idlest_group(struct sched_domain *sd, struct task_struct *p,
                  int this_cpu, int sd_flag)
{
        struct sched_group *idlest = NULL, *group = sd->groups;
        unsigned long min_load = ULONG_MAX, this_load = 0;
        int load_idx = sd->forkexec_idx;
        int imbalance = 100 + (sd->imbalance_pct-100)/2;

        if (sd_flag & SD_BALANCE_WAKE)
                load_idx = sd->wake_idx;

        do {
                unsigned long load, avg_load;
                int local_group;
                int i;

                /* Skip over this group if it has no CPUs allowed */
                if (!cpumask_intersects(sched_group_cpus(group),
                                        tsk_cpus_allowed(p)))
                        continue;

                local_group = cpumask_test_cpu(this_cpu,
                                               sched_group_cpus(group));

                /* Tally up the load of all CPUs in the group */
                avg_load = 0;

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

                        avg_load += load;
                }

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

                if (local_group) {
                        this_load = avg_load;
                } else if (avg_load < min_load) {
                        min_load = avg_load;
                        idlest = group;
                }
        } while (group = group->next, group != sd->groups);

        if (!idlest || 100*this_load < imbalance*min_load)
                return NULL;
        return idlest;
}

스케줄링 도메인내에서 cpu 로드가 가장 낮은 idlest 스케줄 그룹을 찾아 반환한다.  idlest 스케줄 그룹의 cpu 로드에 100%를 초과하는 imbalance_pct의 절반을 추가 적용하여 로컬 그룹의 cpu 로드보다 오히려 커지는 경우 null을 반환한다.

  • 코드 라인 11에서 로드 인덱스로 forkexec_idx를 사용하게 지정한다.
  • 코드 라인 12에서 요청한 도메인의 imbalance_pct에서 100 이하의 값은 절반만 적용한 값을 imbalance로 사용한다.
    • 예) imbalance_pct=117인 경우 imbalance=108
  • 코드 라인 14~15에서 wake 밸런싱을 요청한 경우 로드 인덱스는 wake_idx를 사용한다.
  • 코드 라인 17~25에서 스케줄링 그룹에 소속된 cpu들이 태스크에서 허용하는 cpu에 하나도 없는 경우 다음 그룹으로 skip 한다.
  • 코드 라인 27~28에서 스케줄 그룹에 소속된 cpu에 this_cpu의 포함 여부를 local_group에 대입한다. (1=로컬 그룹)
  • 코드 라인 33~41에서 스케줄 그룹에 소속된 cpu들을 순회하면서 cpu 로드 값을 읽어 avg_load에 합산한다. cpu 로드 값을 읽어올 때 로컬 그룹인 경우 보수 적인 로드 값을 알아오고, 그렇지 않고 리모트 그룹인 경우 적극적인 로드 값을 알아와서 avg_load에 더한다.
    • source_load()
      • 요청한 cpu의 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 작은 로드 값을 반환한다.
      • 로컬 그룹에서의 로드 산출은 보수적으로 로드 값을 평가한다.
    • target_load()
      • 요청한 cpu의 최상위 cfs 런큐의 러너블 로드 평균과 cpu_load[type-1] 중 큰 로드 값을 반환한다.
      • 리모트 그룹에서의 로드 산출은 적극적으로 로드 값을 평가한다.
  • 코드 라인 44에서 산출한 평균 로드를 그대로 비교하지 않고 순회 중인 스케줄 그룹의 capacity 비율을 적용한다.
    • 예) 첫 번째 그룹에 2개의 cortex-a15 cpu의 각각 1535 capacity를 가지고 있고 이를 합친 group->sgc->capacity=3070이며 두 cpu에 대한 avg_load가 512일 때
      • capacity 반영된 평균 로드(avg_load) = 512 * 1024 / 3070 = 170으로 평가된다.
    • 예) 두 번째 그룹에 2개의 cortex-a7 cpu의 각각 430 capacity를 가지고 있고 이를 합친 group->sgc->capacity=860이며 두 cpu에 대한 avg_load가 300일 때
      • capacity 반영된 평균 로드(avg_load) = 300 * 1024 / 860 = 357로 평가된다.
  • 코드 라인 46~47에서 로컬 그룹인 경우 this_load에 avg_load를 반영한다.
  • 코드 라인 48~51에서 리모트 그룹인 경우 그 그룹의 cpu 로드가 최소 로드 값인 경우 갱신한다. 그리고 그 그룹을 idlest 그룹으로 갱신한다.
    • min_load
      • 도메인 내의 스케줄 그룹들 중 가장 적은 로드 값이 담긴다.
    • idlest
      • min_load가 산출된 스케줄 그룹
  • 코드 라인 54~55에서 결정된 idlest 그룹이 없거나 결정된 idlest 그룹이 있어도 로컬 그룹의  평균 로드보다 imbalance 비율을 적용한 idlest 그룹의 평균 로드가 더 큰 경우 null을 반환한다.
  • 코드 라인 56에서 결정된 idlest 그룹을 반환한다.

 

다음 그림은 요청 도메인내에서 cpu capacity 요율을 적용한 cpu 로드가 가장 낮은 스케줄 그룹을 찾는 모습을 보여준다.

 

다음 그림 역시 위의 그림과 같이 idlest 스케줄 그룹을 찾는다. 하지만 이 idlest 그룹의 cpu 로드에 100%를 초과하는 imbalance_pct의 절반을 더 적용한 경우 로컬 그룹의 cpu 로드보다 오히려 커지면 idlest 그룹을 반환하지 않고 null을 반환하는 모습을 보여준다.

 

find_idlest_cpu()

kernel/sched/fair.c

/*
 * find_idlest_cpu - find the idlest cpu among the cpus in group.
 */
static int
find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
{
        unsigned long load, min_load = ULONG_MAX;
        unsigned int min_exit_latency = UINT_MAX;
        u64 latest_idle_timestamp = 0;
        int least_loaded_cpu = this_cpu;
        int shallowest_idle_cpu = -1;
        int i;

        /* Traverse only the allowed CPUs */
        for_each_cpu_and(i, sched_group_cpus(group), tsk_cpus_allowed(p)) {
                if (idle_cpu(i)) {
                        struct rq *rq = cpu_rq(i);
                        struct cpuidle_state *idle = idle_get_state(rq);
                        if (idle && idle->exit_latency < min_exit_latency) {
                                /*
                                 * We give priority to a CPU whose idle state
                                 * has the smallest exit latency irrespective
                                 * of any idle timestamp.
                                 */
                                min_exit_latency = idle->exit_latency;
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
                        } else if ((!idle || idle->exit_latency == min_exit_latency) &&
                                   rq->idle_stamp > latest_idle_timestamp) {
                                /*
                                 * If equal or no active idle state, then
                                 * the most recently idled CPU might have
                                 * a warmer cache.
                                 */
                                latest_idle_timestamp = rq->idle_stamp;
                                shallowest_idle_cpu = i;
                        }
                } else if (shallowest_idle_cpu == -1) {
                        load = weighted_cpuload(i);
                        if (load < min_load || (load == min_load && i == this_cpu)) {
                                min_load = load;
                                least_loaded_cpu = i;
                        }
                }
        }

        return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
}

요청한 스케줄 그룹 및 태스크에 허용된 cpu들 중 idlest cpu를 찾아 반환한다.

  • case A) idle cpu가 1개 이상인 경우 깨어나는데 소요되는 시간이 가장 적은 cpu를 선택한다.
    • 동일한 exit_latency를 가진 경우 최근에 idle 진입한 cpu를 선택한다.
  • case B) idle cpu가 없는 경우 가장 낮은 cpu 로드를 가진 cpu를 선택한다.
    • 낮은 cpu로드 중 this_cpu가 포함된 경우 this_cpu를 선택한다. (밸런싱 불필요)

 

  • 코드 라인 15에서 스케줄 그룹에 소속된  cpu들 중 태스크에 허가된 cpu들에 대해 순회한다.
  • 코드 라인 16~18에서 순회 중인 cpu가 idle 중이면 런큐에 연결된 cpuidle_state를 알아온다.
    • cpuidle_state
      • cpu idle 상태를 관리하고 cpu idle PM을 위한 generic 프레임워크와 연결된다. 여기서 cpu idle 드라이버와 연결하여 사용한다.
  • 코드 라인 19~27에서 런큐에 지정된 cpu idle PM이 있고 idle 상태에서 깨어나는데 걸리는 시간(exit_latency)이 가장 작은 cpu를 찾아 shallowest_idle_cpu에 대입하고 cpu idle PM에서 지정해둔 exit_latency 시간을 min_exit_latency에  대입한다. latest_idle_timestamp에 idle 진입 시각을 대입한다.
    • idle->exit_latency (us 단위)
      • arm에서 사용하는 대부분의 idle 드라이버는 cpu idle과 클러스터 idle의 2단계의 상태 정도로 나누어 관리한다. 그 중 클러스터 idle의 경우 idle로 진입한 후 다시 wake될 때까지 사이클에 소요되는 시간이 크므로 이를 exit_latency에 대입하여 관리한다.
      • 이 값은 초기 커널에서는 하드 코딩하여 각 시스템에 지정하였는데 최근에는 디바이스 트리에서 지정한 값으로도 관리된다. 보통 수 us 부터 수십 ms까지 전원 관리를 얼마나 깊게 하는가에 따라 다르다.
      • idle cpu가 wake하기 위해 걸리는 시간이 작은 cpu를 선택하여 더욱 성능 효율을 낼 수 있다.
      • exit_latency가 서로 동일한 경우 idle 진입한 시각이 얼마되지 않은 cpu를 선택한다.
        • 최근에 idle 상태에 진입한 cpu를 선택하는 것으로 L2 이상의 share 캐시에 데이터가 남아있을 가능성이 크다. (더 높은 성능을 위해)
  • 코드 라인 28~37에서 런큐에 지정된 cpu idle PM이 없거나 latency 값이 최소 값과 서로 동일한 경우에는 가장 최근에 idle에 진입한 cpu를 선택하여 최대한 캐시에 남아 있는 데이터를 활용할 수 있게 한다.
  • 코드 라인 38~44에서 cpu가 busy 상태이면 가장 낮은 cpu 로드를 가진 cpo를 선택하여 shallowest_idle_cpu에 대입한다. 최소 로드 값은 min_load에 대입한다.
    • 로드 값: 최상위 cfs 런큐의 러너블 로드 평균
  • 코드 라인 47에서 shallowest_idle_cpu를 반환한다. 만일 idle cpu가 없으면 가장 낮은 cpu 로드를 가진 least_loaded_cpu를 반환한다.

 

다음 4 개의 그림은 스케줄 그룹내에서 태스크가 허용하면서 가장 idlest한 cpu를 찾는 과정을 보여준다.

 

select_fallback_rq()

요청한 cpu와 태스크를 사용하여 fallback cpu를 찾아 반환한다. 다음 순서대로 찾는다.

  1. 요청한 cpu가 소속된 노드와 태스크가 허용하는 online cpu를 찾아 반환한다.
  2. 노드와 상관없이 태스크가 허용하는 online cpu를 찾아 반환한다.
  3. cpuset에 설정된 effective_cpus를 태스크에 설정하고 그 중 online cpu를 찾아 반환한다.
  4. possible cpu를 태스크에 설정하고 그 중 online cpu를 찾아 반환한다.

 

kernel/sched/core.c – 1/2

/*
 * ->cpus_allowed is protected by both rq->lock and p->pi_lock
 */
static int select_fallback_rq(int cpu, struct task_struct *p)
{
        int nid = cpu_to_node(cpu);
        const struct cpumask *nodemask = NULL;
        enum { cpuset, possible, fail } state = cpuset;
        int dest_cpu;

        /*
         * If the node that the cpu is on has been offlined, cpu_to_node()
         * will return -1. There is no cpu on the node, and we should
         * select the cpu on the other node.
         */
        if (nid != -1) { 
                nodemask = cpumask_of_node(nid);

                /* Look for allowed, online CPU in same node. */
                for_each_cpu(dest_cpu, nodemask) {
                        if (!cpu_online(dest_cpu))
                                continue;
                        if (!cpu_active(dest_cpu))
                                continue;
                        if (cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
                                return dest_cpu;
                }
        }
  • 코드 라인 16~28 에서 cpu에 해당하는 메모리 노드에 속한 cpu들을 순회하며 순회 중인 cpu가 offline 또는 deactivate된 경우 skip한다. 만일 태스크에 허용된 cpu인 경우 해당 cpu를 반환한다.

 

kernel/sched/core.c – 2/2

        for (;;) {
                /* Any allowed, online CPU? */
                for_each_cpu(dest_cpu, tsk_cpus_allowed(p)) {
                        if (!cpu_online(dest_cpu))
                                continue;
                        if (!cpu_active(dest_cpu))
                                continue;
                        goto out;
                }

                switch (state) {
                case cpuset:
                        /* No more Mr. Nice Guy. */
                        cpuset_cpus_allowed_fallback(p);
                        state = possible;
                        break;

                case possible:
                        do_set_cpus_allowed(p, cpu_possible_mask);
                        state = fail;
                        break;

                case fail:
                        BUG();
                        break;
                }
        }

out:
        if (state != cpuset) {
                /*
                 * Don't tell them about moving exiting tasks or
                 * kernel threads (both mm NULL), since they never
                 * leave kernel.
                 */
                if (p->mm && printk_ratelimit()) {
                        printk_deferred("process %d (%s) no longer affine to cpu%d\n",
                                        task_pid_nr(p), p->comm, cpu);
                }
        }

        return dest_cpu;
}
  • 코드 라인 1~9에서 태스크에 허용된 cpu들을 순회하며 순회 중인 cpu가 offline 또는 deactivate된 경우 skip한다. out 레이블로 이동하여 해당 cpu를 반환한다.
  • 코드 라인 11~16에서 task가 소속된 cpuset 그룹의 effective_cpus를 태스크의 cpus_allowed에 설정하여 태스크의 허용 cpu들을 바꾼다.  그런 후 다시 루프를 순회한다.
    • “sys/fs/cgroup/cpuset/<group…>/cpuset.effective_cpus”
  • 코드 라인 18~21에서 태스크의 cpus_allowed에 possible cpu를 대입한 후 다시 루프를 순회한다.
  • 코드 라인 23~26에서 모든 시도가 실패한 경우 BUG() 함수를 호출한다
  • 코드 라인 30~40에서 possible cpu를 적용하여 cpu를 선택한 경우 경고 메시지를 출력한다.
  • 코드 라인 42에서 최종 선택한 cpu를 반환한다.

 

Exec 밸런싱

sched_exec()

kernel/sched/core.c

/*
 * sched_exec - execve() is a valuable balancing opportunity, because at
 * this point the task has the smallest effective memory and cache footprint.
 */
void sched_exec(void)
{
        struct task_struct *p = current;
        unsigned long flags;
        int dest_cpu;

        raw_spin_lock_irqsave(&p->pi_lock, flags);
        dest_cpu = p->sched_class->select_task_rq(p, task_cpu(p), SD_BALANCE_EXEC, 0);
        if (dest_cpu == smp_processor_id())
                goto unlock;

        if (likely(cpu_active(dest_cpu))) {
                struct migration_arg arg = { p, dest_cpu };

                raw_spin_unlock_irqrestore(&p->pi_lock, flags);
                stop_one_cpu(task_cpu(p), migration_cpu_stop, &arg);
                return;
        }
unlock:
        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
}

실행될 태스크에 대해 밸런싱을 수행한다.

  • 코드 라인 12~14에서 exec 밸런싱을 통해 태스크가 수행될 cpu를 선택한다. 선택한 cpu가 현재 cpu인 경우 마이그레이션 없이 함수를 빠져나간다.
  • 코드 라인 16~22에서 현재 태스크를 수행될 cpu로 마이그레이션 하도록 워크큐를 사용하여 워커스레드에 요청한다.

 

migration_cpu_stop()

kernel/sched/core.c

/*
 * migration_cpu_stop - this will be executed by a highprio stopper thread
 * and performs thread migration by bumping thread off CPU then
 * 'pushing' onto another runqueue.
 */
static int migration_cpu_stop(void *data)
{
        struct migration_arg *arg = data;

        /*
         * The original target cpu might have gone down and we might
         * be on another cpu but it doesn't matter.
         */
        local_irq_disable();
        /*
         * We need to explicitly wake pending tasks before running
         * __migrate_task() such that we will not miss enforcing cpus_allowed
         * during wakeups, see set_cpus_allowed_ptr()'s TASK_WAKING test.
         */
        sched_ttwu_pending();
        __migrate_task(arg->task, raw_smp_processor_id(), arg->dest_cpu);
        local_irq_enable();
        return 0;
}

런큐에서 wake up 시도 중인 태스크들을 모두 activate 시킨 후 요청한 태스크를 dest cpu의 런큐에 마이그레이션한다.

 

__migrate_task()

kernel/sched/core.c

/*
 * Move (not current) task off this cpu, onto dest cpu. We're doing
 * this because either it can't run here any more (set_cpus_allowed()
 * away from this CPU, or CPU going down), or because we're
 * attempting to rebalance this task on exec (sched_exec).
 *
 * So we race with normal scheduler movements, but that's OK, as long
 * as the task is no longer on this CPU.
 *
 * Returns non-zero if task was successfully migrated.
 */
static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
{
        struct rq *rq;
        int ret = 0;

        if (unlikely(!cpu_active(dest_cpu)))
                return ret;

        rq = cpu_rq(src_cpu);

        raw_spin_lock(&p->pi_lock);
        raw_spin_lock(&rq->lock);
        /* Already moved. */
        if (task_cpu(p) != src_cpu)
                goto done;

        /* Affinity changed (again). */
        if (!cpumask_test_cpu(dest_cpu, tsk_cpus_allowed(p)))
                goto fail;

        /*
         * If we're not on a rq, the next wake-up will ensure we're
         * placed properly.
         */
        if (task_on_rq_queued(p))
                rq = move_queued_task(p, dest_cpu);
done:
        ret = 1;
fail:
        raw_spin_unlock(&rq->lock);
        raw_spin_unlock(&p->pi_lock);
        return ret;
}

요청한 태스크를 dest cpu의 런큐에 마이그레이션한다. 실패한 경우 0을 반환한다.

  • 코드 라인 17~18에서 낮은 확률로 dest cpu가 active 상태가 아닌 경우 마이그레이션 없이 결과 값 0으로 함수를 빠져나간다.
  • 코드 라인 25~26에서 이미 마이그레이션된 경우 결과 값 1로 함수를 빠져나간다.
  • 코드 라인 29~30에서 dest cpu가 태스크에 허용된 cpu가 아닌 경우 결과 값 0으로 함수를 빠져나간다.
    • cpu affinity가 갑자기 변경된 경우를 대응하기 위한 예외 처리이다.
  • 코드 라인 36~37에서 태스크가 온전히 기존 cpu의 런큐에 있는 경우 dest cpu로 마이그레이션한다.

 

move_queued_task()

kernel/sched/core.c

/*
 * move_queued_task - move a queued task to new rq.
 *
 * Returns (locked) new rq. Old rq's lock is released.
 */
static struct rq *move_queued_task(struct task_struct *p, int new_cpu)
{
        struct rq *rq = task_rq(p);

        lockdep_assert_held(&rq->lock);

        dequeue_task(rq, p, 0);
        p->on_rq = TASK_ON_RQ_MIGRATING;
        set_task_cpu(p, new_cpu);
        raw_spin_unlock(&rq->lock);

        rq = cpu_rq(new_cpu);

        raw_spin_lock(&rq->lock);
        BUG_ON(task_cpu(p) != new_cpu);
        p->on_rq = TASK_ON_RQ_QUEUED;
        enqueue_task(rq, p, 0);
        check_preempt_curr(rq, p, 0);

        return rq;
}

요청한 태스크를 new cpu로 마이그레이션한다.

  • 코드 라인 12~13에서 런큐에서 디큐하고 태스크의 on_rq에 마이그레이션 중이라고 상태를 바꾼다.
  • 코드 라인 14에서 태스크에 새 cpu 번호를 대입한다.
  • 코드 라인 21~22에서 태스크의 on_rq에 런큐에 엔큐된 상태로 바꾸고 태스크를 new cpu의 런큐에 엔큐한다.
  • 코드 라인 23에서 태스크를 마이그레이션한 후 preemption 필요한 경우 리스케줄 요청을 설정하도록 체크한다.

 

Wake 밸런싱

try_to_wake_up() 함수 내부에서 select_task_rq()를 호출할 떄 SD_BALANCE_WAKE 플래그를 사용하여 wake 밸런싱을 수행한다.

 

참고

 

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

load_balance() 함수는 현재 cpu 로드와 스케줄링 도메인내의 가장 바쁜 cpu 로드와 비교하여 불균형 상태이면 밸런스 조절을 위해 가장 바쁜 cpu의 태스크를 마이그레이션해온다.

load_balance() 함수에 진입 시 사용되는 cpu_idle_type은 다음과 같이 3가지가 있다.

  • CPU_IDLE
    • 스케줄틱에 의해 주기적 로드밸런스 조건에서 진입 시, 현재 cpu의 런큐가 idle 중이다.
  • CPU_NOT_IDLE
    • 스케줄틱에 의해 주기적 로드밸런스 조건에서 진입 시, 현재 cpu의 런큐에서 어떤 태스크가 동작 중이다.
  • CPU_NEWLY_IDLE
    • 패시브 로드밸런스 조건으로, 런큐에서 마지막 동작하던 어떤 태스크가 dequeue되어 idle 진입 직전에 이 함수에 진입하였다.

 

즉, 위와 같은 조건일 때에 인자로 요청한 스케줄 도메인에 포함된 cpu들과 현재 cpu 간에 뷸균형 로드가 발견되면 가장 바쁜 cpu의 태스크를 현재 cpu로 가져오는 것으로 로드밸런싱을 수행한다.

 

도메인내에서 가장 바쁜 cpu를 찾는 알고리즘은 다음과 같다.

  • 첫 번째, find_busiest_group() 함수를 통해 도메인에서 가장 바쁜(busiest) 그룹을 찾는다.
    • cpu 그룹의 로드 값에 그룹 평균 cpu capacity를 나누어 비교한다.
    • 예) 다음 두 그룹의 로드는 고성능 및 저성능 그룹 각각 동일하다.
      • 그룹A) 그룹로드=1035, 그룹 capacity =2070
      • 그룹B) 그룹로드=430, 그룹 capacity =860
  • 두 번째, find_busiest_queue() 함수를 통해 가장 바쁜(busiest) 그룹에서 가장 바쁜 cpu를 찾는다.
    • cpu의 로드 값에 cpu capacity를 나누어 비교한다.
    • 예) 다음 두 cpu의 로드는 고성능 및 저성능 cpu 각각 동일하다.
      • cpu A) cpu 로드=1535, 그룹 capacity =1535
      • cpu B) cpu 로드=430, 그룹 capacity =430

 

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에는 cfs 태스크들의 수를 모두 더한다.
  • 코드 라인 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
    • 로드밸런싱할 태스크 리스트

 

참고