Scheduler -13- (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 밸런싱을 수행한다.

 

참고

답글 남기기

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