Scheduler -7- (RT Scheduler)

 

RT 스케줄 틱

task_tick_rt()

RT 스케줄러에서 스케줄 틱마다 다음과 같은 일들을 수행한다.

  • rt 로드 평균 및 런타임을 갱신
  • 요청한 rt 태스크의 제한시간이 설정된 rt 태스크 제한시간 리미트를 초과한 경우 cpu 시간 만료 설정
  • 요청한 태스크가 라운드 로빈 정책을 사용하고 같은 우선 순위의 태스크가 복수인 경우 해당 태스크를 양보하고 라운드 로빈 처리

kernel/sched/rt.c

static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
{
        struct sched_rt_entity *rt_se = &p->rt;

        update_curr_rt(rq);

        watchdog(rq, p);

        /*
         * RR tasks need a special form of timeslice management.
         * FIFO tasks have no timeslices.
         */
        if (p->policy != SCHED_RR)
                return;

        if (--p->rt.time_slice)
                return;

        p->rt.time_slice = sched_rr_timeslice;

        /*
         * Requeue to the end of queue if we (and all of our ancestors) are not
         * the only element on the queue
         */
        for_each_sched_rt_entity(rt_se) {
                if (rt_se->run_list.prev != rt_se->run_list.next) {
                        requeue_task_rt(rq, p, 0);
                        resched_curr(rq);
                        return;
                }
        }
}
  • 코드 라인 5에서 요청한 런큐의 rt 로드 평균 및 런타임을 갱신한다.
  • 코드 라인 7에서 rt 태스크의 제한시간이 설정된 rt 태스크 제한시간 리미트를 초과한 경우 cpu 시간 만료 설정을 한다.
  • 코드 라인 13~14에서 태스크의 스케줄 정책이 라운드 로빈(SCHED_RR)이 아니면 함수를 빠져나간다.
    • rt 태스크에서 사용하는 스케줄 정책은 SCHED_RR 및 SCHED_FIFO가 있다.
  • 코드 라인 16~17에서 rt 태스크의 타임 슬라이스를 1 감소시키고 그 값이 0이 아니면 함수를 빠져나간다.
    • 라운드 로빈을 한 번 수행하면 최소한 이 시간이 지나야 다시 라운드 로빈을 할 수 있다.
  • 코드 라인 19에서 rt 태스크의 타임 슬라이스에 라운도 로빈용 타임 슬라이스(0.1초)를 대입한다.
  • 코드 라인 25~31에서 rt 태스크의 최상위 rt 스케줄 엔티티까지 순회하며 복수개의 스케줄 엔티티가 있는 경우 라운도 로빈 처리하고 리스케줄 요청 플래그를 설정한다.
    • rt 런큐 어레이 리스트 중 해당 스케줄 엔티티가 소속된 우선순위의 리스트에 복수의 rt 스케줄 엔티티가 있는 경우 해당 스케줄 엔티티의 우선순위를 양보하기 위해 해당 리스트의 뒤로 리큐하고 리스케줄 요청 플래그를 설정하는 것으로 매 스케줄 틱마다 라운드 로빈 기능을 수행한다.
    • 같은 우선 순위의 라운드 로빈 정책을 사용하는 rt 태스크는 매 스케줄 틱마다 돌아가며 수행되게 한다.

 

 

Watchdog

watchdog()

kernel/sched/rt.c

static void watchdog(struct rq *rq, struct task_struct *p)
{
        unsigned long soft, hard;

        /* max may change after cur was read, this will be fixed next tick */
        soft = task_rlimit(p, RLIMIT_RTTIME);
        hard = task_rlimit_max(p, RLIMIT_RTTIME);

        if (soft != RLIM_INFINITY) {
                unsigned long next;

                if (p->rt.watchdog_stamp != jiffies) {
                        p->rt.timeout++;
                        p->rt.watchdog_stamp = jiffies;
                }

                next = DIV_ROUND_UP(min(soft, hard), USEC_PER_SEC/HZ);
                if (p->rt.timeout > next)
                        p->cputime_expires.sched_exp = p->se.sum_exec_runtime;
        }
}

rt 태스크의 제한시간이 설정된 rt 태스크가 제한시간 리미트를 초과한 경우 cpu 시간 만료 설정을 한다.

  • 코드 라인 6~7에서 rt 태스크의 현재 제한시간(us)과 최대 제한시간(us)을 알아온다.
  • 코드 라인 9~15에서 rt 태스크의 현재 제한시간이 설정되어 있는 경우 현재 태스크의 워치독 스탬프를 갱신한다.
  • 코드 라인 17에서 rt 태스크의 현재 제한시간과 최대 제한시간 중 작은 항목을 밀리초(ms) 단위로 변환한다.
  • 코드 라인 18~19에서 rt 태스크의 타임아웃(ms)이 변환한 타임아웃(ms) 값보다 큰 경우 태스크의 cputime_expires.sched_exp에 스케줄 엔티티의 총 실행 시간 합을 대입한다.

 

라운드 로빈

requeue_task_rt()

kernel/sched/rt.c

static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
{
        struct sched_rt_entity *rt_se = &p->rt;
        struct rt_rq *rt_rq;

        for_each_sched_rt_entity(rt_se) {
                rt_rq = rt_rq_of_se(rt_se);
                requeue_rt_entity(rt_rq, rt_se, head);
        }
}

RT 태스크를 라운드 로빈 처리한다. RT 태스크를 head=1일 때 선두로, 0일 때 후미로 이동시킨다.

 

 

requeue_rt_entity()

kernel/sched/rt.c

/*
 * Put task to the head or the end of the run list without the overhead of
 * dequeue followed by enqueue.
 */
static void
requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
{
        if (on_rt_rq(rt_se)) {
                struct rt_prio_array *array = &rt_rq->active;
                struct list_head *queue = array->queue + rt_se_prio(rt_se);

                if (head)
                        list_move(&rt_se->run_list, queue);
                else
                        list_move_tail(&rt_se->run_list, queue);
        }
}

RT 스케줄 엔티티를 라운드 로빈 처리한다. 디큐 및 엔큐 처리로 인한 오버헤드를 없애기 위해 스케줄 엔티티만 이동시킨다.

  • 코드 라인 8~10에서 요청한 rt 스케줄 엔티티가 런큐에 이미 존재하는 경우 100개의 리스트 어레이 중 해당 우선 순위의 리스트를 알아온다.
  • 코드 라인 12~15에서 rt 스케줄 엔티티를 인수 head 요청에 따라 리스트의 선두 또는 후미에 추가한다.

 

 

로드 및 Runtime 갱신

update_curr_rt()

kernel/sched/rt.c

/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
static void update_curr_rt(struct rq *rq)
{
        struct task_struct *curr = rq->curr;
        struct sched_rt_entity *rt_se = &curr->rt;
        u64 delta_exec;

        if (curr->sched_class != &rt_sched_class)
                return;

        delta_exec = rq_clock_task(rq) - curr->se.exec_start;
        if (unlikely((s64)delta_exec <= 0))
                return;

        schedstat_set(curr->se.statistics.exec_max,
                      max(curr->se.statistics.exec_max, delta_exec));
        
        curr->se.sum_exec_runtime += delta_exec;
        account_group_exec_runtime(curr, delta_exec);
        
        curr->se.exec_start = rq_clock_task(rq);
        cpuacct_charge(curr, delta_exec);
        
        sched_rt_avg_update(rq, delta_exec);

        if (!rt_bandwidth_enabled())
                return;

        for_each_sched_rt_entity(rt_se) {
                struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
                
                if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
                        raw_spin_lock(&rt_rq->rt_runtime_lock);
                        rt_rq->rt_time += delta_exec;
                        if (sched_rt_runtime_exceeded(rt_rq))
                                resched_curr(rq);
                        raw_spin_unlock(&rt_rq->rt_runtime_lock);
                }
        }
}

rt 런타임 평균 및 런타임을 갱신한다.

  • 코드 라인 11~12에서 현재 동작중인 태스크가 rt 스케줄러에서 동작하지 않으면 함수를 빠져나간다.
  • 코드 라인 14~16에서 런큐의 clock_task에서 현재 태스크의 시작 실행 시각을 뺀 시간을 delta_exec에 대입한다. 만일 실행 시간이 0보다 작으면 함수를 빠져나간다.
  • 코드 라인 18~19에서 스케줄 통계를 위해 스케줄 틱 별 최대 실행 시간을 갱신한다.
  • 코드 라인 21에서 현재 태스크의 실행 시간 총합을 갱신한다.
  • 코드 라인 22에서 현재 스레드 그룹용 총 시간 관리를 위해 cpu 타이머가 동작하는 동안 총 실행 시간을 갱신한다.
    • posix timer를 통해 만료 시 시그널을 발생한다.
  • 코드 라인 24에서 현재 태스크의 시작 실행 시각을 대입한다.
  • 코드 라인 25에서 현재 태스크의 cpu accounting 그룹용 총 실행 시간을 갱신한다.
  • 코드 라인 27에서 rt 런타임 평균을 갱신한다.
  • 코드 라인 29~30에서 rt bandwidth가 설정되지 않은 경우 함수를 빠져나간다. 디폴트로 0.95초로 설정되어 있다.
    • 디폴트 값: sysctl_sched_rt_runtime(950,000 us = 0.95 s)
  • 코드 라인 32~37에서 최상위 rt 스케줄 엔티티까지 순회하며 rt 런큐의 rt_time에 실행 시각을 누적시킨다.
  • 코드 라인 38~39에서 rt 런타임이 초과된 경우 리스케줄 요청 플래그를 설정한다.

 

RT 태스크에 소모한 런타임 평균 시간 산출

sched_rt_avg_update()

kernel/sched/sched.h

#ifdef CONFIG_SMP
extern void sched_avg_update(struct rq *rq);
static inline void sched_rt_avg_update(struct rq *rq, u64 rt_delta)
{
        rq->rt_avg += rt_delta;
        sched_avg_update(rq);
}
#endif

RT 런타임 평균 값을 갱신한다.

  • 코드 라인 5에서 런큐의 rt 런타임 평균 값에 rt 실행 시간을 추가한다.
    • rq->rt_avg
      • rt 런타임 평균
  • 코드 라인 6에서 기존 갱신된 시간으로 부터 경과된 시간이 RT 태스크에 소모한 런타임 평균 시간 산출 기간보다 큰 경우 rt 런타임 평균을 절반으로 나눈다.

 

다음 그림은 sched_rt_avg_update() 함수를 통하여 RT 태스크의 런타임이 평균 로드에 반영되는 모습을 보여준다.

 

다음 그림은 RT 태스크의 런타임에 변화에 맞춰 RT 주기마다 decay되는 평균 로드의 움직임을 보여준다. (2 개의 예)

 

sched_avg_update()

kernel/sched/core.c

void sched_avg_update(struct rq *rq)
{
        s64 period = sched_avg_period();
 
        while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
                /*
                 * Inline assembly required to prevent the compiler
                 * optimising this loop into a divmod call.
                 * See __iter_div_u64_rem() for another example of this.
                 */
                asm("" : "+rm" (rq->age_stamp));
                rq->age_stamp += period;
                rq->rt_avg /= 2;
        }
}

기존 갱신된 시간으로 부터 경과된 시간이 RT 태스크에 소모한 런타임 평균 시간 산출 기간보다 큰 경우 rt 런타임 평균을 절반으로 나눈다.

  • 코드 라인 3에서 RT 태스크에 소모한 런타임 평균 시간 산출 기간을 알아와서 period에 대입한다. (500,000,000 ns)
  • 코드 라인 5에서 런큐 clock에서 age_stamp를 뺀 시간이 period보다 큰 경우에 한해 루프를 돈다.
  • 코드 라인 11~13에서 rt 런타임 평균을 절반으로 나눈다.
    • 런큐의 age_stamp에 period를 더하고 rt_avg를 절반으로 나눈다.
    • rq->age_stamp
      • cpu가 시작되어 런큐가 처음 동작할 때 시각이 담긴 이후로 rt 태스크가 실행될 때 매 스케줄 틱마다 실행 시간이 추가되어 갱신된다.

 

sched_avg_period()

kernel/sched/sched.h

static inline u64 sched_avg_period(void)
{
        return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
}

RT 태스크에 소모한 런타임 평균 시간 산출 기간을 나노초 단위로 반환한다.

  • sysctl_sched_time_avg의 디폴트 값은 1,000 ms(1초)이므로 반환되는 값은 500,000,000 ns (0.5s)이다.

 

kernel/sched/core.c

/*
 * period over which we average the RT time consumption, measured
 * in ms.
 *
 * default: 1s
 */
const_debug unsigned int sysctl_sched_time_avg = MSEC_PER_SEC;

RT 런타임 계산에 사용하는 평균 기간으로 디폴트 값은 1,000 ms(1초)이다.

 

 

RT Bandwidth

RT bandwidth 기능은 CFS 스케줄러와 달리 RT 그룹 스케줄링을 사용하지 않아도 항상 기본 동작하도록 설정되어 있다. 디폴트 값으로 다음과 같은 설정이 되어 있다.

  • sysctl_sched_rt_runtime
    • 디폴트 값: 950,000 us (0.95 초)
  • sysctl_sched_rt_period
    • 디폴트 값: 1,000,000 us (1초)

 

커널이 cgroup을 사용하면서 CONFIG_RT_GROUP_SCHED 커널 옵션을 사용하여 RT 그룹 스케줄링을 동작시키는 경우 루트 태스크 그룹을 제외한 태스크 그룹마다 bandwidth 기능을 설정하여 사용할 수 있게 된다.

  • rt_runtime_us
    • “/sys/fs/cgroup/cpu/rt_runtime_us” 파일에 설정
    • 디폴트 값: 950,000 us (0.95초)
  • rt_period_us
    • “/sys/fs/cgroup/cpu/rt_period_us” 파일에 설정
    • 디폴트 값: 1,000,000 us (1초)

 

디폴트 설정을 그대로 사용하는 경우 rt 태스크는 1초 기간 내에 0.95초 만큼 런타임을 사용할 수 있다. 이는 1개의 cpu를 사용하는 시스템을 가정할 때 최대 95%의 cpu를 rt 스케줄러가 점유할 수 있도록 한다.

  • 일반적으로 RT 태스크들은 매우 짧은 시간만 스케줄링되어 동작하므로 1초 주기동안 RT 태스크의 런타임이 95%를 초과하여 스로틀링하는 경우는 매우 드물다고 할 수 있다.

 

RT Bandwidth 초기화

init_rt_bandwidth()

kernel/sched/rt.c

void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
{
        rt_b->rt_period = ns_to_ktime(period);
        rt_b->rt_runtime = runtime;
        
        raw_spin_lock_init(&rt_b->rt_runtime_lock);

        hrtimer_init(&rt_b->rt_period_timer,
                        CLOCK_MONOTONIC, HRTIMER_MODE_REL);
        rt_b->rt_period_timer.function = sched_rt_period_timer;
}

rt period와 runtime 값을 사용하여 초기화한다.

  • 코드 라인 3에서 인수로 전달받은 us 단위의 period 값을 나노초 단위로 바꾸어 rt_period에 저장한다.
  • 코드 라인 4에서 인수로 전달받은 us 단위의 runtime 값을 나노초 단위로 바꾸어 rt_runtime에 저장한다.
  • 코드 라인 8~10에서 hrtimer를 초기화하고 만료 시 호출 함수를 지정한다.

 

RT runtime 설정

sched_group_set_rt_runtime()

kernel/sched/core.c

static int sched_group_set_rt_runtime(struct task_group *tg, long rt_runtime_us)
{
        u64 rt_runtime, rt_period;

        rt_period = ktime_to_ns(tg->rt_bandwidth.rt_period);
        rt_runtime = (u64)rt_runtime_us * NSEC_PER_USEC;
        if (rt_runtime_us < 0)
                rt_runtime = RUNTIME_INF;

        return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
}

요청한 태스크 그룹에 rt 런타임(us)을 나노초로 변경하여 설정한다.

  • 코드 라인 5에서 rt bandwidth에 설정되어 있는 period 값을 나노초 단위로 변환해온다.
  • 코드 라인 6에서 rt bandwidth에 설정되어 있는 런타임 값을 나노초 단위로 변환해온다.
  • 코드 라인 7~8에서 rt 런타임 값이 0보다 작으면 무제한(-1)으로 설정하여 rt bandwidth가 동작하지 않게한다.
  • 코드 라인 10에서 요청한 태스크 그룹에 rt bandwidth의 period(ns) 및 runtime(ns) 값을 설정한다.

 

RT period 설정

sched_group_set_rt_period()

kernel/sched/core.c

static int sched_group_set_rt_period(struct task_group *tg, long rt_period_us)
{
        u64 rt_runtime, rt_period;

        rt_period = (u64)rt_period_us * NSEC_PER_USEC;
        rt_runtime = tg->rt_bandwidth.rt_runtime;

        return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
}

요청한 태스크 그룹에 rt period(us) 값을 나노초로 변경하여 설정한다.

  • 코드 라인 5에서 인수로 받은 rt_period_us 값을 나노초 단위로 변환한다.
  • 코드 라인 6에서 rt bandwidth에 설정되어 있는 런타임(ns) 값을 가져온다.
  • 코드 라인 8에서 요청한 태스크 그룹에 rt bandwidth의 period(ns) 및 runtime(ns) 값을 설정한다.

 

RT runtime & period 공통 설정

tg_set_rt_bandwidth()

kernel/sched/core.c

static int tg_set_rt_bandwidth(struct task_group *tg,
                u64 rt_period, u64 rt_runtime)
{
        int i, err = 0;

        /*
         * Disallowing the root group RT runtime is BAD, it would disallow the
         * kernel creating (and or operating) RT threads.
         */
        if (tg == &root_task_group && rt_runtime == 0)
                return -EINVAL;

        /* No period doesn't make any sense. */
        if (rt_period == 0)
                return -EINVAL;

        mutex_lock(&rt_constraints_mutex);
        read_lock(&tasklist_lock);
        err = __rt_schedulable(tg, rt_period, rt_runtime);
        if (err)
                goto unlock;

        raw_spin_lock_irq(&tg->rt_bandwidth.rt_runtime_lock);
        tg->rt_bandwidth.rt_period = ns_to_ktime(rt_period);
        tg->rt_bandwidth.rt_runtime = rt_runtime;

        for_each_possible_cpu(i) {
                struct rt_rq *rt_rq = tg->rt_rq[i];

                raw_spin_lock(&rt_rq->rt_runtime_lock);
                rt_rq->rt_runtime = rt_runtime;
                raw_spin_unlock(&rt_rq->rt_runtime_lock);
        }
        raw_spin_unlock_irq(&tg->rt_bandwidth.rt_runtime_lock);
unlock:
        read_unlock(&tasklist_lock);
        mutex_unlock(&rt_constraints_mutex);

        return err;
}

 

RT 런타임 초과 여부

sched_rt_runtime_exceeded()

kernel/sched/rt.c

static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
{
        u64 runtime = sched_rt_runtime(rt_rq);

        if (rt_rq->rt_throttled)
                return rt_rq_throttled(rt_rq);

        if (runtime >= sched_rt_period(rt_rq))
                return 0;

        balance_runtime(rt_rq);
        runtime = sched_rt_runtime(rt_rq);
        if (runtime == RUNTIME_INF)
                return 0;

        if (rt_rq->rt_time > runtime) {
                struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

                /*
                 * Don't actually throttle groups that have no runtime assigned
                 * but accrue some time due to boosting.
                 */
                if (likely(rt_b->rt_runtime)) {
                        rt_rq->rt_throttled = 1;
                        printk_deferred_once("sched: RT throttling activated\n");
                } else {
                        /*
                         * In case we did anyway, make it go away,
                         * replenishment is a joke, since it will replenish us
                         * with exactly 0 ns.
                         */
                        rt_rq->rt_time = 0;
                }

                if (rt_rq_throttled(rt_rq)) {
                        sched_rt_rq_dequeue(rt_rq);
                        return 1;
                }
        }

        return 0;
}

RT 로컬에서 소모한 런타임이 할당된 런타임을 초과한 경우 밸런싱 작업을 수행한다. 스로틀이 필요한 경우 1을 반환한다.

  • 코드 라인 5~6에서 rt 런큐에 throttled가 설정되었으면 스로틀 여부를 반환한다.
  • 코드 라인 8~9에서 rt bandwidth를 위해 알아온 runtime >= rt period 설정보다 같거나 크면 함수를 처리하지 않고 0을 반환한다.
  • 코드 라인 11에서 rt 로컬 런큐의 할당된 런타임을 모두 소모한 경우 런타임 밸런싱을 수행한다.
  • 코드 라인 12~14에서 rt 로컬 런큐에 할당된 런타임을 알아온다. 만일 무한대의 런타임이 할당된 경우 스로틀하지 않도록 0을 반환한다.
    • 디폴트 값: sysctl_sched_rt_runtime(950,000 us = 0.95 s)
  • 코드 라인 16~33에서 밸런싱 작업을 하고 이 루틴에 들어왔다. 그런데도 rt 로컬의 할당된 런타임이 부족한 경우 높은 확률로 rt 글로벌 풀의 런타임이 남아 있는 경우 rt 런큐에 스로틀됨을 알리기 위해 1을 설정한다. 그렇지 않은 경우 rt 로컬 런타임 소모량을 0으로 리셋한다.
  • 코드 라인 35~38에서 rt 로컬이 이미 스로틀된 경우 런큐에서 rt 런큐를 디큐하여 rt 런큐에서 동작중인 스케줄 엔티티 수만큼 감소시킨다. 그런 후 스로틀링 하도록 1을 반환한다.

 

다음 그림과 같이 소모한 런타임이 초과된 경우 UP 시스템에서 처리되는 모습을 보여준다.

 

다음 그림과 같이 소모한 런타임이 초과된 경우 SMP 시스템에서는 다른 cpu로 부터 런타임을 빌려온다. 더 이상 빌려올 곳이 없으면 스로틀을 계획한다.

  • rt 런큐가 스로틀링을 하는 경우 cfs 런큐에 등록된 엔티티들을 동작시킬 수있다.

 

최상위 RT 런큐의 디큐 및 엔큐 상태 변경

dequeue_top_rt_rq()

kernel/sched/rt.c

static void 
dequeue_top_rt_rq(struct rt_rq *rt_rq)
{
        struct rq *rq = rq_of_rt_rq(rt_rq);

        BUG_ON(&rq->rt != rt_rq);

        if (!rt_rq->rt_queued)
                return;

        BUG_ON(!rq->nr_running);

        sub_nr_running(rq, rt_rq->rt_nr_running);
        rt_rq->rt_queued = 0;
}

최상위 rt 런큐를 디큐 상태로 바꾸고 동작했던 태스크 수만큼 런큐에서 감소시킨다. (rq->nr_running 갱신)

  • 코드 라인 8~9에서 rt 로컬 런큐가 이미 디큐 상태이면 함수를 빠져나온다.
    • rq->rt_queued
      • 런큐에서 rt 런큐의 가동 상태를 나타낸다. (1=엔큐, 0=디큐)
  • 코드 라인 13에서 현재 rt 런큐에서 동작중인 rt 태스크의 수를 런큐에서 동작중인 태스크 수에서 뺀다.
    • rq->nr_running -= rt_rq->rt_nr_running
  • 코드 라인 14에서 최상위 rt 런큐를 디큐된 상태로 설정한다.

 

다음 그림은 rt 런큐의 디큐와 엔큐 처리 과정을 보여준다.

 

enqueue_top_rt_rq()

kernel/sched/rt.c

static void
enqueue_top_rt_rq(struct rt_rq *rt_rq)
{
        struct rq *rq = rq_of_rt_rq(rt_rq);

        BUG_ON(&rq->rt != rt_rq);

        if (rt_rq->rt_queued)
                return;
        if (rt_rq_throttled(rt_rq) || !rt_rq->rt_nr_running)
                return;

        add_nr_running(rq, rt_rq->rt_nr_running);
        rt_rq->rt_queued = 1;
}

최상위 rt 런큐를 엔큐 상태로 바꾸고 최상위 rt 런큐에있는 태스크 수만큼 증가시킨다. (rq->nr_running 갱신)

  • 코드 라인 8~9에서 최상위 rt 로컬 런큐가 이미 엔큐된 상태이면 함수를 빠져나온다.
  • 코드 라인 10~11에서 최상위 rt 로컬 런큐가 이미 스로틀상태이거나 동작 중인 rt 태스크가 없는 경우 함수를 빠져나간다.
  • 코드 라인 13에서 현재 최상위 rt 런큐에 있는 rt 태스크 수를 런큐에서 동작중인 태스크 수에 더한다.
    • rq->nr_running += rt_rq->rt_nr_running
  • 코드 라인 14에서 최상위 rt 런큐를 엔큐된 상태로 설정한다.

 

RT 런타임 밸런싱

balance_runtime()

kernel/sched/rt.c

static int balance_runtime(struct rt_rq *rt_rq)
{
        int more = 0;

        if (!sched_feat(RT_RUNTIME_SHARE))
                return more;

        if (rt_rq->rt_time > rt_rq->rt_runtime) {
                raw_spin_unlock(&rt_rq->rt_runtime_lock);
                more = do_balance_runtime(rt_rq);
                raw_spin_lock(&rt_rq->rt_runtime_lock);
        }

        return more;
}

요청한 rt 런큐의 할당된 런타임을 모두 소모한 경우 다른 rt 로컬 풀로부터 빌려와서 최대한 rt_period 만큼 더 할당하여 늘리도록 밸런싱을 수행한다.

  • 코드 라인 5~6에서 RT_RUNTIME_SHARE 기능이 없는 경우 0을 반환한다.
  • 코드 라인 8~12에서 요청한 rt 런큐의 할당된 런타임을 모두 소모한 경우 다른 rt 로컬 풀로부터 빌려와서 최대한 rt_period 만큼 더 할당하여 늘리도록 밸런싱을 수행한다.

 

do_balance_runtime()

kernel/sched/rt.c

static int do_balance_runtime(struct rt_rq *rt_rq)
{
        struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);
        struct root_domain *rd = rq_of_rt_rq(rt_rq)->rd;
        int i, weight, more = 0;
        u64 rt_period;

        weight = cpumask_weight(rd->span);

        raw_spin_lock(&rt_b->rt_runtime_lock);
        rt_period = ktime_to_ns(rt_b->rt_period);
        for_each_cpu(i, rd->span) {
                struct rt_rq *iter = sched_rt_period_rt_rq(rt_b, i);
                s64 diff;

                if (iter == rt_rq)
                        continue;

                raw_spin_lock(&iter->rt_runtime_lock);
                /*
                 * Either all rqs have inf runtime and there's nothing to steal
                 * or __disable_runtime() below sets a specific rq to inf to
                 * indicate its been disabled and disalow stealing.
                 */
                if (iter->rt_runtime == RUNTIME_INF)
                        goto next;

                /*
                 * From runqueues with spare time, take 1/n part of their
                 * spare time, but no more than our period.
                 */
                diff = iter->rt_runtime - iter->rt_time;
                if (diff > 0) {
                        diff = div_u64((u64)diff, weight);
                        if (rt_rq->rt_runtime + diff > rt_period)
                                diff = rt_period - rt_rq->rt_runtime;
                        iter->rt_runtime -= diff;
                        rt_rq->rt_runtime += diff;
                        more = 1;
                        if (rt_rq->rt_runtime == rt_period) {
                                raw_spin_unlock(&iter->rt_runtime_lock);
                                break;
                        }
                }
next:
                raw_spin_unlock(&iter->rt_runtime_lock);
        }
        raw_spin_unlock(&rt_b->rt_runtime_lock);

        return more;
}

요청한 rt 로컬 런큐에 런타임 할당량을 루트 도메인의 다른 rt 로컬 런큐에서 사용하고 남은 만큼 빌려 할당한다.

  • 코드 라인 3~4에서 rt 로컬 런큐에 해당하는 rt 글로벌 풀과 루트 도메인을 알아온다.
  • 코드 라인 8에서 루트 도메인에 사용할 수 있는 cpu 수를 알아온다.
  • 코드 라인 11에서 글로벌 풀의 rt period 값을 나노초 단위로 변환하여 알아온다.
  • 코드 라인 12~13에서 루트 도메인에 사용할 수 있는 cpu를 순회하며 글로벌 풀의 태스크 그룹에 연결된 rt  로컬 런큐를 iter에 대입한다.
  • 코드 라인 16~17에서 순회하는 rt 로컬 런큐가 인수로 요청한 rt 로컬 런큐와 같은 경우 skip 한다.
    • 요청한 rt 로컬 런큐가 다른 rt 로컬 런큐로부터 런타임을 얻어와야하기 때문에 자신은 skip 한다.
  • 코드 라인 25~26에서 순회하는 rt 로컬 런큐에 런타임 할당이 안된 경우 rt bandwidth가 설정되지 않은 경우이므로 next로 이동하고 skip 한다.
  • 코드 라인 32에서 순회하는 rt 로컬 런큐의 할당된 런타임에서 소모한 rt 런타임의 차를 diff에 대입하여 아직 사용하지 않은 기간을 알아온다.
  • 코드 라인 33~34에서 순회하는 rt 로컬 런큐의 사용하지 않은 런타임이 있는 경우 그 값을 루트 도메인의 cpu 수만큼 나눈다.
  • 코드 라인 35~36에서 순회하는 rt 로컬 런큐의 할당된 런타임과 빌려올 diff 값을 더한 값이 rt_period 기간을 초과하지 않도록 빌려올 값 diff를 조절한다.
  • 코드 라인 37~39에서 순회하는 rt 로컬 런큐의 런타임 할당 값에서 diff를 빌려오고 인수로 요청한 rt 로컬 런큐의 런타임 할당 값에 추가한다. more=1을 하여 빌려온 런타임이 있음을 나타낸다.
  • 코드 라인 40~43에서 빌려와서 채운 런타임 할당이 rt_period와 같은 경우 더 이상 빌려올 필요가 없으므로 루프를 탈출한다.
  • 코드 라인 50에서 런타임을 빌려와서 설정했는지 여부를 반환한다.

 

Enqueue & Dequeue RT 엔티티

 

다음 그림은 enqueue_rt_entity()와 dequeue_rt_entity() 함수의 함수간 처리 흐름도이다.

 

enqueue_rt_entity()

kernel/sched/rt.c

static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
        struct rq *rq = rq_of_rt_se(rt_se);

        dequeue_rt_stack(rt_se);
        for_each_sched_rt_entity(rt_se)
                __enqueue_rt_entity(rt_se, head);
        enqueue_top_rt_rq(&rq->rt);
}

rt 엔티티를 엔큐한다.

  • 코드 라인 5에서 최상위 rt 엔티티부터 요청한 rt 엔티티까지 top-down 방향으로 rt 엔티티를 디큐한다.
    • 기존에 엔큐되어 있었으면 먼저 디큐한다.
  • 코드 라인 6~7에서 요청한 rt 엔티티부터 최상위 rt 엔티티까지 다시 엔큐한다.
  • 코드 라인 8에서 최상위 rt 런큐를 엔큐 상태로 바꾸고 최상위 rt 런큐에있는 태스크 수만큼 증가시킨다. (rq->nr_running 갱신)

 

dequeue_rt_entity()

kernel/sched/rt.c

static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
        struct rq *rq = rq_of_rt_se(rt_se);

        dequeue_rt_stack(rt_se); 

        for_each_sched_rt_entity(rt_se) {
                struct rt_rq *rt_rq = group_rt_rq(rt_se);

                if (rt_rq && rt_rq->rt_nr_running)
                        __enqueue_rt_entity(rt_se, false);
        }
        enqueue_top_rt_rq(&rq->rt);
}

rt 엔티티를 디큐한다.

  • 코드 라인 5에서 최상위 rt 엔티티부터 요청한 rt 엔티티까지 top-down 방향으로 rt 엔티티를 디큐한다.
  • 코드 라인 7~12에서 순회 중인 rt 엔티티가 그룹을 대표하고 그 그룹에서 여전히 또 다른 태스크가 동작중인 경우 순회 중인 rt 엔티티를 엔큐한다.
  • 코드 라인 13에서 최상위 rt 런큐를 엔큐 상태로 바꾸고 최상위 rt 런큐에있는 태스크 수만큼 증가시킨다. (rq->nr_running 갱신)

 

dequeue_rt_stack()

kernel/sched/rt.c

/*
 * Because the prio of an upper entry depends on the lower
 * entries, we must remove entries top - down.
 */
static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
{
        struct sched_rt_entity *back = NULL;

        for_each_sched_rt_entity(rt_se) {
                rt_se->back = back;
                back = rt_se;
        }

        dequeue_top_rt_rq(rt_rq_of_se(back));

        for (rt_se = back; rt_se; rt_se = rt_se->back) {
                if (on_rt_rq(rt_se))
                        __dequeue_rt_entity(rt_se);
        }
}

최상위 rt 엔티티부터 요청한 rt 엔티티까지 top-down 방향으로 rt 엔티티들을 디큐한다.

  • 코드 라인 9~12에서 루트 방향의 계층적 rt 엔티티를 반대로 구성한다.
  • 코드 라인 14에서 최상위 rt 런큐를 디큐 상태로 바꾸고 최상위 rt 런큐에있는 태스크 수만큼 감소시킨다. (rq->nr_running 갱신)
  • 코드 라인 16~19에서 최상위 엔티티부터 요청한 rt 엔티티까지 순회하며 순회 중인 rt 엔티티가 해당 rt 런큐에서 동작하는 경우 그 rt 엔티티를 디큐한다.

 

__enqueue_rt_entity()

kernel/sched/rt.c

static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
        struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
        struct rt_prio_array *array = &rt_rq->active;
        struct rt_rq *group_rq = group_rt_rq(rt_se);
        struct list_head *queue = array->queue + rt_se_prio(rt_se);

        /*
         * Don't enqueue the group if its throttled, or when empty.
         * The latter is a consequence of the former when a child group
         * get throttled and the current group doesn't have any other
         * active members.
         */
        if (group_rq && (rt_rq_throttled(group_rq) || !group_rq->rt_nr_running))
                return;

        if (head)
                list_add(&rt_se->run_list, queue);
        else
                list_add_tail(&rt_se->run_list, queue);
        __set_bit(rt_se_prio(rt_se), array->bitmap);

        inc_rt_tasks(rt_se, rt_rq);
}

엔큐된 rt 엔티티에 대한 처리를 수행한다.

  • 코드 라인 3에서 rt 엔티티의 스케줄을 담당하는 rt 런큐를 얻어온다.
  • 코드 라인 5에서 rt 엔티티의 그룹 rt 런큐를 얻어온다.
  • 코드 라인 6에서 rt 엔티티의 우선순위에 해당하는 큐리스트를 알아온다.
  • 코드 라인 14~15에서 태스크 그룹용 rt 엔티티이면서 이 그룹이 스로틀되었거나 엔큐된 rt 태스크가 없으면 함수를 빠져나간다.
    • 태스크 그룹을 엔큐하였지만 그 그룹에 엔큐된 rt 태스크가 하나도 없는 경우이다.
  • 코드 라인 17~20에서 인수 head 요청에 따라 rt 엔티티를 큐리스트의 선두 또는 후미에 추가한다.
  • 코드 라인 21에서 해당 우선 순위별 리스트큐에 대한 비트를 설정한다.
  • 코드 라인 23에서 엔큐된 rt 태스크에 대한 후속 작업을 진행한다.

 

__dequeue_rt_entity()

kernel/sched/rt.c

static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
        struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
        struct rt_prio_array *array = &rt_rq->active;

        list_del_init(&rt_se->run_list);
        if (list_empty(array->queue + rt_se_prio(rt_se)))
                __clear_bit(rt_se_prio(rt_se), array->bitmap);

        dec_rt_tasks(rt_se, rt_rq);
}

디큐된 rt 엔티티에 대한 처리를 수행한다.

  • 코드 라인 3에서 rt 엔티티의 스케줄을 담당하는 rt 런큐를 얻어온다.
  • 코드 라인 6에서 rt 엔티티를 리스트에서 제거한다.
  • 코드 라인 7~8에서 rt 엔티티가 제거된 리스트가 비게된 경우 해당 우선 순위별 리스트큐에 대한 비트를 클리어한다
  • 코드 라인 10에서 디큐된 rt 태스크에 대한 후속 작업을 진행한다.

 

inc_rt_tasks()

kernel/sched/rt.c

static inline
void inc_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        int prio = rt_se_prio(rt_se);

        WARN_ON(!rt_prio(prio));
        rt_rq->rt_nr_running += rt_se_nr_running(rt_se);

        inc_rt_prio(rt_rq, prio);
        inc_rt_migration(rt_se, rt_rq);
        inc_rt_group(rt_se, rt_rq);
}

추가된 rt 태스크에 대한 후속 작업을 진행한다.

  • 코드 라인 4에서 rt 엔티티의 우선순위를 알아온다.
  • 코드 라인 7에서 rt 런큐이하에서 동작 중인 rt 태스크 수를 갱신한다.
    • rt 엔티티가 태스크인 경우 1을 증가시키고 그룹인 경우 그룹이하에서 동작하는 rt 태스크의 수를 증가시킨다.
  • 코드 라인 9에서 엔큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.
  • 코드 라인 10에서 추가된 rt 엔티티가 태스크인 경우 런큐의 overload 카운터를 증가시키고 런큐에 오버로드 여부를 갱신한다.
    • rt_nr_total++
    • 태스크에 2 개 이상 cpu가 할당된 경우 rt_nr_migratory++
    • 태스크에 2개 이상 cpu가 할당되고 2개 이상 rt 태스크가 동작하는 경우 현재 런큐에 overload 설정
  • 코드 라인 11에서 추가된 rt 그룹에 대한 작업을 수행한다.

 

dec_rt_tasks()

kernel/sched/rt.c

static inline
void dec_rt_tasks(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        WARN_ON(!rt_prio(rt_se_prio(rt_se)));
        WARN_ON(!rt_rq->rt_nr_running);
        rt_rq->rt_nr_running -= rt_se_nr_running(rt_se);

        dec_rt_prio(rt_rq, rt_se_prio(rt_se));
        dec_rt_migration(rt_se, rt_rq);
        dec_rt_group(rt_se, rt_rq);
}

제거된 rt 태스크에 대한 후속 작업을 진행한다.

  • 코드 라인 6에서 rt 런큐 이하에서 동작 중인 rt 태스크 수를 갱신한다.
    • rt 엔티티가 태스크인 경우 1을 감소시키고 그룹인 경우 그룹이하에서 동작하는 rt 태스크의 수를 감소시킨다.
  • 코드 라인 8에서 디큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.
  • 코드 라인 9에서 추가된 rt 엔티티가 태스크인 경우 런큐의 overload 카운터를 감소시키고 런큐에 오버로드 여부를 갱신한다.
    • rt_nr_total–
    • 태스크에 2 개 이상 cpu가 할당된 경우 rt_nr_migratory–
    • 태스크에 cpu가 1개만 설정되거나 rt 태스크가 1개 이하이면 오버로드할 수 없으므로 클리어
  • 코드 라인 10에서 추가된 rt 그룹에 대한 작업을 수행한다.

 

rt_se_nr_running()

kernel/sched/rt.c

static inline
unsigned int rt_se_nr_running(struct sched_rt_entity *rt_se)
{
        struct rt_rq *group_rq = group_rt_rq(rt_se);

        if (group_rq)
                return group_rq->rt_nr_running;
        else
                return 1;
}

rt 엔티티에 동작하는 태스크 수를 반환한다. rt 엔티티가 태스크이면 1을 반환하고, 태스크 그룹용이면 태스크 그룹을 포함한 그 이하 child 태스크의 수를 반환한다.

 

Highest RT Priority 갱신

inc_rt_prio()

kernel/sched/rt.c

#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
static void
inc_rt_prio(struct rt_rq *rt_rq, int prio)
{
        int prev_prio = rt_rq->highest_prio.curr;

        if (prio < prev_prio)
                rt_rq->highest_prio.curr = prio;

        inc_rt_prio_smp(rt_rq, prio, prev_prio);
}

엔큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.

  • 코드 라인 5~8에서 rt 런큐내에서 요청한 우선 순위가 가장 높은(낮은 prio 숫자값이 가장 높은 우선순위이다.)인 경우 이를 갱신한다.
  • 코드 라인 10에서 요청한 rt 런큐의 cpu와 우선 순위에 대해 cpupri에 증가 반영한다.

 

dec_rt_prio()

kernel/sched/rt.c

static void
dec_rt_prio(struct rt_rq *rt_rq, int prio)
{
        int prev_prio = rt_rq->highest_prio.curr;

        if (rt_rq->rt_nr_running) {

                WARN_ON(prio < prev_prio);

                /*
                 * This may have been our highest task, and therefore
                 * we may have some recomputation to do
                 */
                if (prio == prev_prio) {
                        struct rt_prio_array *array = &rt_rq->active;

                        rt_rq->highest_prio.curr =
                                sched_find_first_bit(array->bitmap);
                }

        } else
                rt_rq->highest_prio.curr = MAX_RT_PRIO;

        dec_rt_prio_smp(rt_rq, prio, prev_prio);
}

디큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.

  • 코드 라인 6~19에서 rt 런큐내에서 동작중인 rt 태스크가 있고 요청한 우선 순위가 가장 높은 우선 순위인 경우 다음 우선 순위를 가장 높은 우선 순위로 갱신한다.
  • 코드 라인 21~22에서 rt 런큐내에서 동작중인 rt 태스크가 없으면 rt 런큐내에서 가장 높은 우선 순위를 초기화한다. (100으로 설정)
  • 코드 라인 24에서 요청한 rt 런큐의 cpu와 우선 순위에 대해 cpupri에 감소 반영한다.

 

inc_rt_prio_smp()

kernel/sched/rt.c

static void
inc_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
{
        struct rq *rq = rq_of_rt_rq(rt_rq);

#ifdef CONFIG_RT_GROUP_SCHED
        /*
         * Change rq's cpupri only if rt_rq is the top queue.
         */
        if (&rq->rt != rt_rq)
                return;
#endif
        if (rq->online && prio < prev_prio)
                cpupri_set(&rq->rd->cpupri, rq->cpu, prio);
}

요청한 rt 런큐에서 가장 높은 우선 순위인 경우 cpu와 우선 순위를 cpupri에 설정한다.

  • 코드 라인 6~12에서 그룹 스케줄링을 사용하는 경우 최상위 rt 런큐가 아닌 경우 함수를 빠져나간다.
  • 코드 라인 13~14에서 최고 우선 순위가 갱신된 경우 런큐의 cpu와 요청 우선 순위에 대해 cpupri에 설정한다.

 

dec_rt_prio_smp()

kernel/sched/rt.c

static void
dec_rt_prio_smp(struct rt_rq *rt_rq, int prio, int prev_prio)
{
        struct rq *rq = rq_of_rt_rq(rt_rq);

#ifdef CONFIG_RT_GROUP_SCHED
        /*
         * Change rq's cpupri only if rt_rq is the top queue.
         */
        if (&rq->rt != rt_rq)
                return;
#endif
        if (rq->online && rt_rq->highest_prio.curr != prev_prio)
                cpupri_set(&rq->rd->cpupri, rq->cpu, rt_rq->highest_prio.curr);
}

요청한 rt 런큐에서 요청한 우선 순위가 가장 높은 우선 순위인 경우 cpu와 차순위로 갱신된 최고 우선 순위를 cpupri에 설정한다.

  • 코드 라인 10~11에서 rt 그룹 스케줄링이 지원되는 커널인 경우 최상위 rt 런큐가 아니면 함수를 빠져나간다.
  • 코드 라인 13~14에서 online 상태의 런큐이면서 최고 우선 순위의 rt 엔티티가 디큐된 cpu와 차순위로 갱신된 최고 우선 순위를 cpupri에  설정한다.

 

CPU Priority Management with highest priority

cpupri_set()

요청한 cpu와 현재 동작 중인 스케줄러내에서의 최고 우선 순위를 cpupri에 설정한다.

kernel/sched/cpupri.c – 1/2

/**
 * cpupri_set - update the cpu priority setting
 * @cp: The cpupri context
 * @cpu: The target cpu
 * @newpri: The priority (INVALID-RT99) to assign to this CPU
 *
 * Note: Assumes cpu_rq(cpu)->lock is locked
 *
 * Returns: (void)
 */
void cpupri_set(struct cpupri *cp, int cpu, int newpri)
{
        int *currpri = &cp->cpu_to_pri[cpu];
        int oldpri = *currpri;
        int do_mb = 0;

        newpri = convert_prio(newpri);

        BUG_ON(newpri >= CPUPRI_NR_PRIORITIES);

        if (newpri == oldpri)
                return;

        /*
         * If the cpu was currently mapped to a different value, we
         * need to map it to the new value then remove the old value.
         * Note, we must add the new value first, otherwise we risk the
         * cpu being missed by the priority loop in cpupri_find.
         */
        if (likely(newpri != CPUPRI_INVALID)) {
                struct cpupri_vec *vec = &cp->pri_to_cpu[newpri];

                cpumask_set_cpu(cpu, vec->mask);
                /*
                 * When adding a new vector, we update the mask first,
                 * do a write memory barrier, and then update the count, to
                 * make sure the vector is visible when count is set.
                 */
                smp_mb__before_atomic();
                atomic_inc(&(vec)->count);
                do_mb = 1;
        }
  • 코드 라인 17에서 인수로 받은 우선순위를 사용하여 cpupri로 변환한다.
  • 코드 라인 21~22에서 현재 cpu가 이미 같은 우선 순위를 사용하고 있었으면 함수를 빠져나간다.
  • 코드 라인 30~33에서 새 우선 순위에 해당하는 벡터의 cpumask에 요청한 cpu 비트를 설정한다.
  • 코드 라인 39~41에서 새 우선 순위에서 동작하는 벡터의 cpu 카운터를 증가시킨다. 다음 카운터를 감소시키는 동작이 나올 예정인데 그 때 메모리 배리어 동작이 필요하므로 1을 대입한다.

 

kernel/sched/cpupri.c – 2/2

        if (likely(oldpri != CPUPRI_INVALID)) {
                struct cpupri_vec *vec  = &cp->pri_to_cpu[oldpri];

                /*
                 * Because the order of modification of the vec->count
                 * is important, we must make sure that the update
                 * of the new prio is seen before we decrement the
                 * old prio. This makes sure that the loop sees
                 * one or the other when we raise the priority of
                 * the run queue. We don't care about when we lower the
                 * priority, as that will trigger an rt pull anyway.
                 *
                 * We only need to do a memory barrier if we updated
                 * the new priority vec.
                 */
                if (do_mb)
                        smp_mb__after_atomic();

                /*
                 * When removing from the vector, we decrement the counter first
                 * do a memory barrier and then clear the mask.
                 */
                atomic_dec(&(vec)->count);
                smp_mb__after_atomic();
                cpumask_clear_cpu(cpu, vec->mask);
        }

        *currpri = newpri;
}
  • 코드 라인 1에서 기존 cpupri가 설정되지 않은 경우
  • 코드 라인 16~17에서 메모리 배리어 동작이 필요한 경우 수행한다.
    • arm은 컴파일러 배리어인 barrier()를 동작시킨다.
  • 코드 라인 23에서 기존 우선 순위에서 동작하는 벡터의 cpu 카운터를 감소시킨다.
  • 코드 라인 25에서 기존 우선 순위에 해당하는 벡터의 cpumask에 요청한 cpu 비트를 클리어한다.

 

다음 그림은 루트 도메인의 cpupri 내부에 있는 102개의 cpupri 벡터와  cpu_to_pri를 갱신하는 모습을 보여준다.

  • 4개의 cpu를 번호 순서대로 RT0, NORMAL, IDLE, RT99와 같은 우선 순위가 동작하는 상황에서 마지막 cpu에 디폴트 nice 0 우선순위인 prio=120 우선순위로 설정한다.

 

convert_prio()

kernel/sched/cpupri.c

/* Convert between a 140 based task->prio, and our 102 based cpupri */
static int convert_prio(int prio)
{
        int cpupri;

        if (prio == CPUPRI_INVALID)
                cpupri = CPUPRI_INVALID;
        else if (prio == MAX_PRIO)
                cpupri = CPUPRI_IDLE;
        else if (prio >= MAX_RT_PRIO)
                cpupri = CPUPRI_NORMAL;
        else
                cpupri = MAX_RT_PRIO - prio + 1;

        return cpupri;
}

태스크 기반의 140단계 우선 순위를 102단계의 cpupri로 변환하여 반환한다.

  • 코드 라인 6~7에서 prio=CPUPRI_INVALID(-1)인 경우 그 값을 그대로 반환한다.
  • 코드 라인 8~9에서 prio=140인 idle task의 우선순위인 경우 CPUPRI_IDLE(0) 값을 반환한다.
  • 코드 라인 10~11에서 prio>=100인 notmal(cfs) task 우선 순위인 경우 CPUPRI_NORMAL(1) 값을 반환한다.
  • 코드 라인 12~13에서 prio<100인 rt task 우선 순위인 경우 RT0 ~ RT99 -> 101 ~ 2로 뒤집어서 값을 반환한다.

 

다음 그림은 태스크 기반의 140단계 우선 순위를 102단계의 cpupri로 변경하는 모습을 보여준다.

 

cpupri_find()

102 단계의 가장 낮은 우선 순위부터 요청한 태스크의 우선순위 범위 이내에서 동작할 수 있는 cpu가 있는지 여부를 찾아 반환한다. cpu를 찾은 경우 1을 반환한다. 또한 출력 인수 lowest_mask에 찾은 best(lowest) 우선순위에서 동작할 수 있는 cpumask를 반환한다.

kernel/sched/cpupri.c – 1/2

/**
 * cpupri_find - find the best (lowest-pri) CPU in the system
 * @cp: The cpupri context
 * @p: The task
 * @lowest_mask: A mask to fill in with selected CPUs (or NULL)
 *
 * Note: This function returns the recommended CPUs as calculated during the
 * current invocation.  By the time the call returns, the CPUs may have in
 * fact changed priorities any number of times.  While not ideal, it is not
 * an issue of correctness since the normal rebalancer logic will correct
 * any discrepancies created by racing against the uncertainty of the current
 * priority configuration.
 *
 * Return: (int)bool - CPUs were found
 */
int cpupri_find(struct cpupri *cp, struct task_struct *p,
                struct cpumask *lowest_mask)
{
        int idx = 0; 
        int task_pri = convert_prio(p->prio);

        BUG_ON(task_pri >= CPUPRI_NR_PRIORITIES);

        for (idx = 0; idx < task_pri; idx++) {
                struct cpupri_vec *vec  = &cp->pri_to_cpu[idx];
                int skip = 0;

                if (!atomic_read(&(vec)->count))
                        skip = 1;
  • 코드 라인 20에서 태스크에 설정된 140 단계의 우선 순위로 102 단계의 cpupri 우선 순위로 변환하여 task_pri에 대입한다.
  • 코드 라인 24~25에서 인덱스를 0부터 태스크의 cpupri 번호까지 순회하며 해당하는 인덱스의 cpupri 벡터를 알아온다.
  • 코드 라인 28~29에서 인덱스 번호의 cpupri를 사용하는 cpu가 없는 경우 skip=1을 설정한다.

 

kernel/sched/cpupri.c – 2/2

                /*
                 * When looking at the vector, we need to read the counter,
                 * do a memory barrier, then read the mask.
                 *
                 * Note: This is still all racey, but we can deal with it.
                 *  Ideally, we only want to look at masks that are set.
                 *
                 *  If a mask is not set, then the only thing wrong is that we
                 *  did a little more work than necessary.
                 *
                 *  If we read a zero count but the mask is set, because of the
                 *  memory barriers, that can only happen when the highest prio
                 *  task for a run queue has left the run queue, in which case,
                 *  it will be followed by a pull. If the task we are processing
                 *  fails to find a proper place to go, that pull request will
                 *  pull this task if the run queue is running at a lower
                 *  priority.
                 */
                smp_rmb();

                /* Need to do the rmb for every iteration */
                if (skip)
                        continue;

                if (cpumask_any_and(&p->cpus_allowed, vec->mask) >= nr_cpu_ids)
                        continue;

                if (lowest_mask) {
                        cpumask_and(lowest_mask, &p->cpus_allowed, vec->mask);

                        /*
                         * We have to ensure that we have at least one bit
                         * still set in the array, since the map could have
                         * been concurrently emptied between the first and
                         * second reads of vec->mask.  If we hit this
                         * condition, simply act as though we never hit this
                         * priority level and continue on.
                         */
                        if (cpumask_any(lowest_mask) >= nr_cpu_ids)
                                continue;
                }

                return 1;
        }

        return 0;
}
  • 코드 라인 19~23에서 메모리 배리어를 수행한 후 skip 설정이 있으면 다음 인덱스 번호로 skip 한다.
  • 코드 라인 25~26에서 순회하는 cpupri 벡터에서 사용하는 cpu와 태스크에 허용된 cpu들이 중복된 cpu들 중 하나의 랜덤 cpu 번호가 최대 cpu 수 이상이면 처리할 수 없어 skip 한다.
    • cpus_allowed는 cgroup의 cpuset 서브시스템을 컨트롤하여 특정 태스크에 허용하는 cpu들을 지정한다.
  • 코드 라인 28~29에서 출력 인수 lowest_mask가 지정된 경우 순회하는 cpupri 벡터에서 사용하는 cpu와 태스크에 허용된 cpu들이 중복된 cpu들을 알아와서 출력 인수 lowest_mask에 대입한다.
  • 코드 라인 39~40에서 출력 인수 lowest_mask에서 랜덤으로 가져온 cpu 번호가 최대 cpu 수 이상이면 처리할 수 없어 skip 한다.
  • 코드 라인 43~46에서 정상적으로 찾았으므로 1을 반환하고 루프를 다 돌도록 찾지 못한 경우 0을 반환한다.

 

다음 그림은 102단계의 cpupri 벡터들에서 가장 낮은 우선 순위 0부터 요청한 태스크의 우선순위까지 검색하여 best (lowest) 우선 순위의 cpu들을 찾는 모습을 보여준다.

  • 태스크는 cpu#0과 cpu#1로 제한된 상태이다. (cgroup -> cpuset 사용)
  • cpupri 벡터에서 0번 idle에는 cpu#2번만 사용되고 있어 skip
  • cpupri 벡터에서 1번 normal에는 cpu#1과 cpu#3이 사용되고 있어 cpu#1만 cpumask로 출력인수에 반환한다.

 

RT Migration

최상위 rt 런큐에 rt 태스크가 엔큐될 때마다 그 태스크가 2 개 이상이면서 2 개 이상의 cpu로 할당된 경우 오버로드될 수 있다고 판단한다.

inc_rt_migration()

kernel/sched/rt.c

static void inc_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        struct task_struct *p;

        if (!rt_entity_is_task(rt_se))
                return;

        p = rt_task_of(rt_se);
        rt_rq = &rq_of_rt_rq(rt_rq)->rt;

        rt_rq->rt_nr_total++;
        if (p->nr_cpus_allowed > 1)
                rt_rq->rt_nr_migratory++;

        update_rt_migration(rt_rq);
}

rt 태스크의 수를 증가시킨다. 또한 rt 태스크가 이주 가능한 경우 이주가능한 rt 태스크의 수를 증가시킨다.

  • 코드 라인 5~6에서 엔티티가 태스크가 아니면 함수를 빠져나간다.
  • 코드 라인 8~9에서 태스크와 최상위 루트 rt 런큐를 알아온다.
  • 코드 라인 11에서 최상위 루트 rt 런큐에서 rt 태스크의 수를 증가시킨다.
  • 코드 라인 12~13에서 만일 태스크에 배정된 cpu 수가 2개 이상인 경우 최상위 루트 rt 런큐의 이주 가능한 태스크의 수를 증가시킨다.
  • 코드 라인 15에서 최상위 루트 RT 런큐의 이주와 관련된 상태를 갱신한다.

 

dec_rt_migration()

kernel/sched/rt.c

static void dec_rt_migration(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        struct task_struct *p;

        if (!rt_entity_is_task(rt_se))
                return;

        p = rt_task_of(rt_se);
        rt_rq = &rq_of_rt_rq(rt_rq)->rt;

        rt_rq->rt_nr_total--;
        if (p->nr_cpus_allowed > 1)
                rt_rq->rt_nr_migratory--;

        update_rt_migration(rt_rq);
}

rt 태스크의 수를 감소시킨다. 또한 rt 태스크가 이주 가능한 경우 이주가능한 rt 태스크의 수를 감소시킨다.

  • 코드 라인 5~6에서 엔티티가 태스크가 아니면 함수를 빠져나간다.
  • 코드 라인 8~9에서 태스크와 최상위 루트 rt 런큐를 알아온다.
  • 코드 라인 11에서 최상위 루트 rt 런큐에서 rt 태스크의 수를 감소시킨다.
  • 코드 라인 12~13에서 만일 태스크에 배정된 cpu 수가 2개 이상인 경우 최상위 루트 rt 런큐의 이주 가능한 태스크의 수를 감소시킨다.
  • 코드 라인 15에서 최상위 루트 RT 런큐의 이주와 관련된 상태를 갱신한다

 

이주와 관련된 멤버들

  • 최상위 root rt_rq->rt_nr_total
    • rt 태스크의 수
  • 최상위 root rt_rq->rt_nr_migratory
    • 이주 가능한 rt 태스크의 수

 

update_rt_migration()

kernel/sched/rt.c

static void update_rt_migration(struct rt_rq *rt_rq)
{
        if (rt_rq->rt_nr_migratory && rt_rq->rt_nr_total > 1) {
                if (!rt_rq->overloaded) {
                        rt_set_overload(rq_of_rt_rq(rt_rq));
                        rt_rq->overloaded = 1;
                }
        } else if (rt_rq->overloaded) {
                rt_clear_overload(rq_of_rt_rq(rt_rq));
                rt_rq->overloaded = 0;
        }
}

요청한 RT 런큐의 이주와 관련된 상태를 갱신한다. RT 런큐에 2 개 이상의 태스크가 있는 경우 오버로드 상태로 설정한다. 이미 오버로드된 상태라면 클리어한다.

  • 코드 라인 3에서 RT 런큐에서 migration된 횟수가 0보다 크고 2개 이상의 rt 태스크가 엔큐된 경우에 한해
  • 코드 라인 4~7에서 런큐를 오버로드로 설정한다.
  • 코드 라인 8~11에서 RT 런큐가 오버로드된 상태인 경우 클리어한다.

 

 

RT Overload

RT 런큐에 2 개 이상의 태스크가 엔큐된 경우 이를 오버로드라 부르고 트래킹하기 위해 사용한다.

  • rq->rd->rto_count
    • 도메인내에서의 rt 오버로드된 횟수
  • rq->rd->rdo_mask
    • 도메인내에서의 rt 오버로드된 cpu
  • rt_rq->overloaded
    • rt 런큐의 오버로드 여부

참고: sched: add rt-overload tracking

 

rt_set_overload()

kernel/sched/rt.c

static inline void rt_set_overload(struct rq *rq)
{
        if (!rq->online)
                return;

        cpumask_set_cpu(rq->cpu, rq->rd->rto_mask);
        /*
         * Make sure the mask is visible before we set
         * the overload count. That is checked to determine
         * if we should look at the mask. It would be a shame
         * if we looked at the mask, but the mask was not
         * updated yet.
         *
         * Matched by the barrier in pull_rt_task().
         */
        smp_wmb();
        atomic_inc(&rq->rd->rto_count);
}

rt 오버로드 카운터를 증가시키고 rt 오버로드 마스크 중 해당 cpu의 비트를 설정한다.

 

rt_clear_overload()

kernel/sched/rt.c

static inline void rt_clear_overload(struct rq *rq)
{
        if (!rq->online)
                return;

        /* the order here really doesn't matter */
        atomic_dec(&rq->rd->rto_count);
        cpumask_clear_cpu(rq->cpu, rq->rd->rto_mask);
}

rt 오버로드 카운터를 감소시키고 rt 오버로드 마스크 중 해당 cpu의 비트를 클리어한다.

 

RT Group 및 타이머 가동

inc_rt_group()

kernel/sched/rt.c

static void
inc_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        if (rt_se_boosted(rt_se))
                rt_rq->rt_nr_boosted++;

        if (rt_rq->tg)
                start_rt_bandwidth(&rt_rq->tg->rt_bandwidth);
}

요청한 rt 런큐의 boosted 카운터를 증가시키고 rt period 타이머를 가동시킨다.

 

dec_rt_group()

kernel/sched/rt.c

static void
dec_rt_group(struct sched_rt_entity *rt_se, struct rt_rq *rt_rq)
{
        if (rt_se_boosted(rt_se))
                rt_rq->rt_nr_boosted--;

        WARN_ON(!rt_rq->rt_nr_running && rt_rq->rt_nr_boosted);
}

요청한 rt 런큐의 boosted 카운터를 감소시킨다.

 

 

RT Period 타이머

 

다음 그림은 rt period 타이머에 대한 가동과 호출 함수에 대한 함수간 처리 흐름을 보여준다.

 

RT period 타이머 가동

start_rt_bandwidth()

kernel/sched/rt.c

static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
{
        if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
                return;

        if (hrtimer_active(&rt_b->rt_period_timer))
                return;

        raw_spin_lock(&rt_b->rt_runtime_lock);
        start_bandwidth_timer(&rt_b->rt_period_timer, rt_b->rt_period);
        raw_spin_unlock(&rt_b->rt_runtime_lock);
}
  • 코드 라인 3~4에서 전역 sysctl_sched_rt_runtime rt period 가 음수 이거나 글로벌 rt 런타임이 -1인 경우 함수를 빠져나간다.
    • 전역 런타임과 tg 별 글로벌 런타임이 음수인 경우 rt bandwidth가 동작하지 않는 상태이다.
  • 코드 라인 6~7에서 이미 글로벌의 rt_period_timer가 active인 경우 함수를 빠져나간다.
  • 코드 라인 10에서 글로벌의 rt_period_timer를 가동시킨다.

 

RT period 타이머 만료 시

sched_rt_period_timer()

kernel/sched/rt.c

static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
{
        struct rt_bandwidth *rt_b =
                container_of(timer, struct rt_bandwidth, rt_period_timer);
        ktime_t now;
        int overrun;
        int idle = 0;

        for (;;) {
                now = hrtimer_cb_get_time(timer);
                overrun = hrtimer_forward(timer, now, rt_b->rt_period);

                if (!overrun)
                        break;

                idle = do_sched_rt_period_timer(rt_b, overrun);
        }

        return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
}

 

  • 코드 라인 3~4에서 rt period timerr가 소속된 글로벌 rt bandwidth를 알아온다.
  • 코드 라인 9~11에서 타이머가 현재 시각을 지나간 경우 최근 만료 시각 기준으로 rt_period 간격으로 현재 시각 이후의 만료시각을 재설정한다.
  • 코드 라인 13~14에서 overrun이 0인 경우 만료된 적이 없으므로 함수를 빠져나간다.
  • 코드 라인 16에서 rt period 만료 시 해야 할 일을 수행한다. 인수로 overrun 값을 가지고 간다.
  • 코드 라인 19에서 idle 결과 값에 따라 idle인 경우 hrtimer가 재설정되지 않게 HRTIMER_NORESTART를 반환한다. idle이 아닌 경우 hrtimer가 재설정되도록 HRTIMER_RESTART를 반환한다.

 

do_sched_rt_period_timer()

rt period 만료 시 해야 할 일을 수행한다

  • rt 엔티티가 엔큐되고 rt period 타이머가 동작된 후 다른 cpu로부터 할당 런타임을 빌려와서 설정하고 잔량이 남는 경우 스로틀하지 않게되는데 이 때 rt 런큐가 스로틀 되었었던 경우 런큐에 엔큐한다.

 

kernel/sched/rt.c – 1/2

static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
{
        int i, idle = 1, throttled = 0;
        const struct cpumask *span;

        span = sched_rt_period_mask();
#ifdef CONFIG_RT_GROUP_SCHED
        /*
         * FIXME: isolated CPUs should really leave the root task group,
         * whether they are isolcpus or were isolated via cpusets, lest
         * the timer run on a CPU which does not service all runqueues,
         * potentially leaving other CPUs indefinitely throttled.  If
         * isolation is really required, the user will turn the throttle
         * off to kill the perturbations it causes anyway.  Meanwhile,
         * this maintains functionality for boot and/or troubleshooting.
         */
        if (rt_b == &root_task_group.rt_bandwidth)
                span = cpu_online_mask;
#endif
  • 코드 라인 6에서 현재 cpu 런큐의 루트 도메인에 허가된 cpu 비트마스크를 알아온다.
  • 코드 라인 7~19에서 rt 그룹 스케줄링을 사용하는 경우 타이머가 소속된 그룹이 루트 태스크 그룹인 경우 online된 cpu 전체를 사용한다.

 

kernel/sched/rt.c – 2/2

        for_each_cpu(i, span) {
                int enqueue = 0;
                struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
                struct rq *rq = rq_of_rt_rq(rt_rq);

                raw_spin_lock(&rq->lock);
                if (rt_rq->rt_time) {
                        u64 runtime;
                        
                        raw_spin_lock(&rt_rq->rt_runtime_lock);
                        if (rt_rq->rt_throttled)
                                balance_runtime(rt_rq);
                        runtime = rt_rq->rt_runtime;
                        rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);
                        if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
                                rt_rq->rt_throttled = 0;
                                enqueue = 1;

                                /*
                                 * When we're idle and a woken (rt) task is
                                 * throttled check_preempt_curr() will set
                                 * skip_update and the time between the wakeup
                                 * and this unthrottle will get accounted as
                                 * 'runtime'.
                                 */
                                if (rt_rq->rt_nr_running && rq->curr == rq->idle)
                                        rq_clock_skip_update(rq, false);
                        }
                        if (rt_rq->rt_time || rt_rq->rt_nr_running)
                                idle = 0;
                        raw_spin_unlock(&rt_rq->rt_runtime_lock);
                } else if (rt_rq->rt_nr_running) {
                        idle = 0;
                        if (!rt_rq_throttled(rt_rq))
                                enqueue = 1;
                }
                if (rt_rq->rt_throttled)
                        throttled = 1;

                if (enqueue)
                        sched_rt_rq_enqueue(rt_rq);
                raw_spin_unlock(&rq->lock);
        }

        if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
                return 1;

        return idle;
}
  • 코드 라인 1~4에서 글로벌에 허용된 cpu 수만큼 순회하며 rt 런큐와 런큐를 알아온다.
  • 코드 라인 7~에서 글로벌의 소모된 런타임이 0보다 큰 경우
  • 코드 라인 11~12에서 글로벌에서 스로틀된 적이 있는 경우 다른 rt 로컬 풀로부터 런타임을 빌려와서 최대한 rt_period 만큼 더 할당하여 늘리도록 밸런싱을 수행한다.
  • 코드 라인 13~14에서 글로벌에 재 할당된 런타임량만큼 글로벌의 소모 런타임을 줄인다. 단 0 미만이 되지 않도록 조절한다.
  • 코드 라인 15~17에서 글로벌에서 스로틀된 적이 있으면서 할당량보다 소모 런타임이 적은 경우 스로틀되지 않은 것으로 바꾼다. 다시 엔큐될 수 있도록 enqueue=1을 대입한다.
  • 코드 라인 26~27에서 글로벌에 엔큐된 rt 태스크가 있으면서 런큐에서 현재 동작중인 태스크가 idle인 경우 런큐의 clock_skip_update에서 RQCF_REQ_SKIP 플래그를 삭제한다.
  • 코드 라인 29~30에서 글로벌에 소모 런타임이 있거나 동작 중인 엔티티가 있는 경우 idle에 0을 대입한다.
  • 코드 라인 32~36에서 글로벌에 소모 런타임이 없지만 엔큐된 rt 태스크가 있는 경우에도 idle에 0을 대입하고 스로틀된적이 없는 경우 enqueue=1을 대입한다.
  • 코드 라인 37~38에서 글로벌에 스로틀된적이 있으면 throttled에 1을 대입한다.
  • 코드 라인 40~41에서 enqueue 요청이 잇는 경우
  • 코드 라인 45~48에서 스로틀되지 않고 rt bandwidth도 동작하지 않은 경우 1을 반환하고 그렇지 않은 경우 idle 상태를 반환한다.

 

sched_rt_rq_enqueue()

kernel/sched/rt.c

static inline void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
{
        struct rq *rq = rq_of_rt_rq(rt_rq);

        if (!rt_rq->rt_nr_running)
                return;

        enqueue_top_rt_rq(rt_rq);
        resched_curr(rq);
}

rt 런큐를 런큐에 엔큐한다.

  • 코드 라인 5~6에서 요청한 rt 런큐에 엔큐된 rt 태스크가 없는 경우 함수를 빠져나간다.
  • 코드 라인 8에서 최상위 rt 런큐를 엔큐하여 rt 런큐의 엔큐된 rt 태스크 수를 갱신한다. (rq->nr_running에 추가된다)
  • 코드 라인 9에서 리스케줄 요청 플래그를 설정한다.

 

Check Preempt

check_preempt_curr_rt()

kernel/sched/rt.c

/*
 * Preempt the current task with a newly woken task if needed:
 */
static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
{
        if (p->prio < rq->curr->prio) {
                resched_curr(rq);
                return;
        }

#ifdef CONFIG_SMP
        /*
         * If:
         *
         * - the newly woken task is of equal priority to the current task
         * - the newly woken task is non-migratable while current is migratable
         * - current will be preempted on the next reschedule
         *
         * we should check to see if current can readily move to a different
         * cpu.  If so, we will reschedule to allow the push logic to try
         * to move current somewhere else, making room for our non-migratable
         * task.
         */
        if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
                check_preempt_equal_prio(rq, p);
#endif
}

현재 태스크보다 더 높은 우선 순위 또는 동등한 우선 순위의 태스크에 리스케줄해야 하는 경우를 체크하여 필요 시 리스케줄 요청 플래그를 설정한다.

  • 코드 라인 6~9에서 요청한 태스크의 우선 순위가 현재 런큐에서 동작하는 태스크의 우선 순위보다 높은 경우 리스케줄 요청 플래그를 설정한다.
  • 코드 라인 24~25에서 smp 시스템의 경우 요청한 태스크의 우선 순위와 현재 런큐에서 동작 중인 우선 순위가 동일하면서 현재 동작중인 태스크에 리스케줄 요청이 없으면 조건에 따라 요청한 태스크를 라운드 로빈하고 리스케줄 요청 플래그를 설정해야 하는지 체크한다.

 

kernel/sched/rt.c

static void check_preempt_equal_prio(struct rq *rq, struct task_struct *p)
{
        /*
         * Current can't be migrated, useless to reschedule,
         * let's hope p can move out.
         */
        if (rq->curr->nr_cpus_allowed == 1 ||
            !cpupri_find(&rq->rd->cpupri, rq->curr, NULL))
                return;

        /*
         * p is migratable, so let's not schedule it and
         * see if it is pushed or pulled somewhere else.
         */
        if (p->nr_cpus_allowed != 1
            && cpupri_find(&rq->rd->cpupri, p, NULL))
                return;

        /*
         * There appears to be other cpus that can accept
         * current and none to run 'p', so lets reschedule
         * to try and push current away:
         */
        requeue_task_rt(rq, p, 1);
        resched_curr(rq);
}

조건에 따라 요청한 태스크를 라운드 로빈하고 리스케줄 요청 플래그를 설정해야 하는지 체크한다.

  • 코드 라인 7~9에서 현재 태스크에서 사용할 수 있는  cpu가 1개 밖에 없는 경우 이거나 런큐의 루트도메인에서 102 단계의 가장 낮은 우선 순위부터 현재 런큐에서 동작중인 태스크의 우선순위 범위 이내에서 동작할 수 있는 cpu가 있으면 함수를 빠져나간다.
  • 코드 라인 15~17에서 현재 태스크에서 사용할 수 있는  cpu가 2개 이상인 경우이고 런큐의 루트도메인에서 102 단계의 가장 낮은 우선 순위부터 요청한 태스크의 우선순위 범위 이내에서 동작할 수 있는 cpu가 있으면 함수를 빠져나간다.
  • 코드 라인 24~25에서 현재 태스크를 리큐하여 라운드 로빈할 수 있게한 후 리스케줄 요청 플래그를 설정한다.

 

다음 태스크 픽업

pick_next_task_rt()

kernel/sched/rt.c

static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev)
{
        struct task_struct *p;
        struct rt_rq *rt_rq = &rq->rt;

        if (need_pull_rt_task(rq, prev)) {
                pull_rt_task(rq);
                /*
                 * pull_rt_task() can drop (and re-acquire) rq->lock; this
                 * means a dl or stop task can slip in, in which case we need
                 * to re-start task selection.
                 */
                if (unlikely((rq->stop && task_on_rq_queued(rq->stop)) ||
                             rq->dl.dl_nr_running))
                        return RETRY_TASK;
        }

        /*
         * We may dequeue prev's rt_rq in put_prev_task().
         * So, we update time before rt_nr_running check.
         */
        if (prev->sched_class == &rt_sched_class)
                update_curr_rt(rq);

        if (!rt_rq->rt_queued)
                return NULL;

        put_prev_task(rq, prev);

        p = _pick_next_task_rt(rq);

        /* The running task is never eligible for pushing */
        dequeue_pushable_task(rq, p);

        set_post_schedule(rq);

        return p;
}

다음에 스케줄할 가장 높은 우선 순위의 rt 태스크를 알아온다.

  • 코드 라인 7에서 요청한 태스크의 우선 순위가 최상위 rt 런큐에서 가장 높은 우선 순위보다 높거나 같은 경우
  • 코드 라인 8에서 오버로드된 런큐들에 대해 현재 런큐에서 진행하려고 하는 우선 순위 태스크보다 더 높은 우선 순위 태스크가 있으면 끌어온다.
  • 코드 라인 14~16에서 낮은 확률로 런큐에서 stop 태스크가 동작 중인 경우 retry를 반환한다.
  • 코드 라인 23~24에서 기존 틱에서도 rt 스케줄러가 동작한 경우 다음과 같은 일들을 수행한다.
    • rt 로드 평균 및 런타임을 갱신
    • 요청한 rt 태스크의 제한시간이 설정된 rt 태스크 제한시간 리미트를 초과한 경우 cpu 시간 만료 설정
    • 요청한 태스크가 라운드 로빈 정책을 사용하고 같은 우선 순위의 태스크가 복수인 경우 해당 태스크를 양보하고 라운드 로빈 처리
  • 코드 라인 26~27에서 rt 스케줄러에 엔큐된 태스크가 없는 경우 null을 반환하여 다음 스케줄러를 선택하게 한다.
  • 코드 라인 29~31에서 기존 틱에서 동작했던 태스크를 다시 밀어넣고 다음 태스크를 알아온다.
  • 코드 라인 34에서 스케줄할 태스크를 pushable task 리스트에서 제거한다
  • 코드 라인 36에서 런큐의 post_schedule 멤버에 pushable task의 존재 여부를 대입한다.

 

need_pull_rt_task()

kernel/sched/rt.c

static inline bool need_pull_rt_task(struct rq *rq, struct task_struct *prev)
{
        /* Try to pull RT tasks here if we lower this rq's prio */
        return rq->rt.highest_prio.curr > prev->prio;
}

요청한 태스크의 우선 순위가 최상위 rt 런큐에서 가장 높은 우선 순위보다 높거나 같은 경우 true를 반환한다.

 

pull_rt_task()

오버로드된 런큐들에 대해 현재 런큐에서 진행하려고 하는 우선 순위 태스크보다 더 높은 우선 순위 태스크가 있으면 끌어온다.

kernel/sched/rt.c

static int pull_rt_task(struct rq *this_rq)
{
        int this_cpu = this_rq->cpu, ret = 0, cpu;
        struct task_struct *p;
        struct rq *src_rq;

        if (likely(!rt_overloaded(this_rq)))
                return 0;

        /*
         * Match the barrier from rt_set_overloaded; this guarantees that if we
         * see overloaded we must also see the rto_mask bit.
         */
        smp_rmb();

        for_each_cpu(cpu, this_rq->rd->rto_mask) {
                if (this_cpu == cpu)
                        continue;

                src_rq = cpu_rq(cpu);

                /*
                 * Don't bother taking the src_rq->lock if the next highest
                 * task is known to be lower-priority than our current task.
                 * This may look racy, but if this value is about to go
                 * logically higher, the src_rq will push this task away.
                 * And if its going logically lower, we do not care
                 */
                if (src_rq->rt.highest_prio.next >=
                    this_rq->rt.highest_prio.curr)
                        continue;

                /* 
                 * We can potentially drop this_rq's lock in
                 * double_lock_balance, and another CPU could
                 * alter this_rq
                 */
                double_lock_balance(this_rq, src_rq);
  • 코드 라인 7~8에서 요청한 런큐의 도메인내에서 오버로드가 없는 경우 0을 반환한다.
  • 코드 라인 16~18에서 오버로드된 cpu를 순회하며 요청한 cpu인 경우 skip 한다.
  • 코드 라인 20에서 순회하는 cpu에 해당하는 런큐를 알아온다.
  • 코드 라인 29~31에서 순회중인 cpu에 대한 최상위 rt 런큐의 차순위보다 요청한 런큐의 최우선순위가 높거나 같은 경우 skip 한다.
  • 코드 라인 38에서 두 개의 런큐에 대해 안전하게 double 락을 건다.

 

                /*
                 * We can pull only a task, which is pushable
                 * on its rq, and no others.
                 */
                p = pick_highest_pushable_task(src_rq, this_cpu);

                /*
                 * Do we have an RT task that preempts
                 * the to-be-scheduled task?
                 */
                if (p && (p->prio < this_rq->rt.highest_prio.curr)) {
                        WARN_ON(p == src_rq->curr);
                        WARN_ON(!task_on_rq_queued(p));

                        /*
                         * There's a chance that p is higher in priority
                         * than what's currently running on its cpu.
                         * This is just that p is wakeing up and hasn't
                         * had a chance to schedule. We only pull
                         * p if it is lower in priority than the
                         * current task on the run queue
                         */
                        if (p->prio < src_rq->curr->prio)
                                goto skip;

                        ret = 1;

                        deactivate_task(src_rq, p, 0);
                        set_task_cpu(p, this_cpu);
                        activate_task(this_rq, p, 0);
                        /*
                         * We continue with the search, just in
                         * case there's an even higher prio task
                         * in another runqueue. (low likelihood
                         * but possible)
                         */
                }
skip:
                double_unlock_balance(this_rq, src_rq);
        }

        return ret;
}
  • 코드 라인 5에서 pushable tasks 리스트에 연결된 태스크를 순회하며 active 되지 않은 첫 태스크를 알아온다. (높은 우선 순위 -> 낮은 우선 순위로 순회)
  • 코드 라인 11~24에서 얻어온 태스크의 우선 순위가 순회중인 cpu의 최상위 rt 런큐에서 현재 동작 중인 우선 순위보다 높은 경우 skip 한다.
    • 해당 런큐에서 곧 동작할 예정이므로 pull 하지 않는다.
  • 코드 라인 26~30에서 순회 중인 cpu의 최상위 rt 런큐에서 얻어온 태스크를 비활성화한 후 현재 cpu로 다시 설정하고 요청한 런큐에 다시 태스크를 활성화시킨다. ret에 1을 대입하여 다른 cpu로 부터 높은 우선 순위의 rt 태스크를 가져왔음을 알린다.
  • 코드 라인 39에서 두 개의 런큐에 대해 double 락을 해제한다.

 

다음 그림은 오버로드된 다른 cpu의 런큐에서 현재 런큐에서 수행하려고 하는 태스크의 우선 순위보다 더 높은 우선 순위를 가진 태스크를 끌어오는 과정을 보여준다.

 

_pick_next_task_rt()

kernel/sched/rt.c

static struct task_struct *_pick_next_task_rt(struct rq *rq)
{
        struct sched_rt_entity *rt_se;
        struct task_struct *p;
        struct rt_rq *rt_rq  = &rq->rt;

        do {
                rt_se = pick_next_rt_entity(rq, rt_rq);
                BUG_ON(!rt_se);
                rt_rq = group_rt_rq(rt_se);
        } while (rt_rq);

        p = rt_task_of(rt_se);
        p->se.exec_start = rq_clock_task(rq);
        
        return p;
}

rt 런큐의 rt 어레이 리스트에서 가장 높은 우선 순위의 rt 태스크를 찾아 반환한다. 반환 할 때 시작 실행 시각을 현재 시각으로 설정한다.

  • 코드 라인 8에서 rt 런큐의 rt 어레이 리스트에서 가장 높은 우선 순위의 rt 엔티티를 찾아 반환한다.
  • 코드 라인 10~11에서 rt 엔티티가 그룹인 경우 다음 하위 그룹으로 이동하며 최종적으로 task인 rt 엔티티를 알아온다.
  • 코드 라인 13~16에서 rt 태스크의 시작 실행 시각을 현재 시각(런큐의 클럭 태스크)으로 설정하고 태스크를 반환한다.

 

다음 그림은 런큐에서 가장 높은 우선 순위의 rt 태스크를 찾아오는 모습을 보여준다.

 

pick_next_rt_entity()

kernel/sched/rt.c

static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
                                                   struct rt_rq *rt_rq)
{
        struct rt_prio_array *array = &rt_rq->active;
        struct sched_rt_entity *next = NULL;
        struct list_head *queue;
        int idx;

        idx = sched_find_first_bit(array->bitmap);
        BUG_ON(idx >= MAX_RT_PRIO);

        queue = array->queue + idx;
        next = list_entry(queue->next, struct sched_rt_entity, run_list);

        return next;
}

rt 런큐의 rt 어레이 리스트에서 가장 높은 우선 순위의 rt 엔티티를 찾아 반환한다.

  • 코드 라인 9에서 rt 우선순위별 리스트 어레이에서 엔티티가 존재하는 가장 우선 순위가 높은 리스트의 인덱스를 알아온다.
    • bit(0) = 0번 우선 순위로 가장 높은 우선순위
  • 코드 라인 12~13에서 리스트에 있는 가장 처음 rt 엔티티를 반환한다.

 

 

Pushable Task

enqueue_pushable_task()

kernel/sched/rt.c

static void enqueue_pushable_task(struct rq *rq, struct task_struct *p)
{
        plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);
        plist_node_init(&p->pushable_tasks, p->prio);
        plist_add(&p->pushable_tasks, &rq->rt.pushable_tasks);

        /* Update the highest prio pushable task */
        if (p->prio < rq->rt.highest_prio.next)
                rq->rt.highest_prio.next = p->prio;
}

요청한 태스크를 최상위 런큐의 pushable_tasks 리스트에 추가하고 최상위 rt 런큐의 차순위를 갱신한다.

  • 코드 라인 3에서 현재 태스크를 최상위 rt 런큐의 pushable_tasks 리스트에서 제거한다.
  • 코드 라인 4~5에서 현재 태스크의 우선 순위를 pushable_tasks 노드에 설정하고 최상위 rt 런큐의 pushable_tasks 리스트에 다시 추가한다.
    • 가장 우선 순위가 높은(숫자가 낮은) 노드가 pushable_tasks 리스트에서 가장 앞에 정렬된다.
  • 코드 라인 8~9에서 요청 태스크의 우선 순위가 런큐의 차순위 우선 순위보다 더 높은 경우 갱신한다.

 

다음 그림은 태스크를 pushable task 리스트에 추가할 때 차순위(highest_prio.next)를 갱신하는 모습을 보여준다.

 

dequeue_pushable_task()

kernel/sched/rt.c

static void dequeue_pushable_task(struct rq *rq, struct task_struct *p)
{
        plist_del(&p->pushable_tasks, &rq->rt.pushable_tasks);

        /* Update the new highest prio pushable task */
        if (has_pushable_tasks(rq)) {
                p = plist_first_entry(&rq->rt.pushable_tasks,
                                      struct task_struct, pushable_tasks);
                rq->rt.highest_prio.next = p->prio;
        } else
                rq->rt.highest_prio.next = MAX_RT_PRIO;
}

요청한 태스크를 최상위 런큐의 pushable_tasks 리스트에서 제거하고 최상위 rt 런큐의 차순위를 갱신한다.

  • 코드 라인 3에서 현재 태스크를 최상위 rt 런큐의 pushable_tasks 리스트에서 제거한다.
  • 코드 라인 6~11에서 런큐에 pushable task가 있으면 그 중 가장 높은 우선 순위를 런큐의 차순위 우선순위로 설정한다. 만일 pushable task가 없으면 런큐의 차순위를 비워둔다.

 

다음 그림은 태스크를 pushable task 리스트에서 삭제할 때 차순위(highest_prio.next)를 갱신하는 모습을 보여준다.

 

pick_highest_pushable_task()

kernel/sched/rt.c

/*
 * Return the highest pushable rq's task, which is suitable to be executed
 * on the cpu, NULL otherwise
 */
static struct task_struct *pick_highest_pushable_task(struct rq *rq, int cpu)
{
        struct plist_head *head = &rq->rt.pushable_tasks;
        struct task_struct *p;

        if (!has_pushable_tasks(rq))
                return NULL;

        plist_for_each_entry(p, head, pushable_tasks) {
                if (pick_rt_task(rq, p, cpu))
                        return p;
        }

        return NULL;
}

pushable tasks 리스트에 연결된 태스크를 순회하며 active 되지 않은 첫 태스크를 알아온다. (높은 우선 순위 -> 낮은 우선 순위로 순회)

  • 코드 라인 10~11에서 요청한 런큐의 pushable task 리스트가 비어 있으면 null을 반환한다.
  • 코드 라인 13~16에서 pushable tasks 리스트에 연결된 태스크를 순회하며 active 되지 않은 첫 태스크를 알아온다.

 

pick_rt_task()

kernel/sched/rt.c

static int pick_rt_task(struct rq *rq, struct task_struct *p, int cpu)
{
        if (!task_running(rq, p) &&
            cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
                return 1;
        return 0;
}

요청한 cpu에서 동작 가능하고 active 되지 않은 태스크인지 여부를 반환한다.

 

plist (Descending-priority-sorted double-linked list)

다음 그림은 plist의 각 노드가 연결되어 있는 모습을 보여준다.

 

 

기존 태스크 수행 완료 처리

put_prev_task()

kernel/sched/sched.h

static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
{
        prev->sched_class->put_prev_task(rq, prev);
}

 

put_prev_task_rt()

kernel/sched/rt.c

static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
{
        update_curr_rt(rq);

        /*
         * The previous task needs to be made eligible for pushing
         * if it is still active
         */
        if (on_rt_rq(&p->rt) && p->nr_cpus_allowed > 1)
                enqueue_pushable_task(rq, p);
}

태스크가 rt 런큐에 있고 태스크에 할당된 cpu 수가 2개 이상인 경우 요청한 태스크를 최상위 런큐의 pushable_tasks 리스트에 추가하고 최상위 rt 런큐의 차순위를 갱신한다.

 

RT 스케줄러 ops

kernel/sched/rt.c

const struct sched_class rt_sched_class = {
        .next                   = &fair_sched_class,
        .enqueue_task           = enqueue_task_rt,
        .dequeue_task           = dequeue_task_rt,
        .yield_task             = yield_task_rt,

        .check_preempt_curr     = check_preempt_curr_rt,

        .pick_next_task         = pick_next_task_rt,
        .put_prev_task          = put_prev_task_rt,

#ifdef CONFIG_SMP
        .select_task_rq         = select_task_rq_rt,

        .set_cpus_allowed       = set_cpus_allowed_rt,
        .rq_online              = rq_online_rt,
        .rq_offline             = rq_offline_rt,
        .post_schedule          = post_schedule_rt,
        .task_woken             = task_woken_rt,
        .switched_from          = switched_from_rt,
#endif

        .set_curr_task          = set_curr_task_rt,
        .task_tick              = task_tick_rt,

        .get_rr_interval        = get_rr_interval_rt,

        .prio_changed           = prio_changed_rt,
        .switched_to            = switched_to_rt,

        .update_curr            = update_curr_rt,
};

 

 

구조체

sched_rt_entity 구조체

kernel/sched/sched.h

struct sched_rt_entity {
        struct list_head run_list;
        unsigned long timeout;
        unsigned long watchdog_stamp;
        unsigned int time_slice;

        struct sched_rt_entity *back;
#ifdef CONFIG_RT_GROUP_SCHED
        struct sched_rt_entity  *parent;
        /* rq on which this entity is (to be) queued: */
        struct rt_rq            *rt_rq;
        /* rq "owned" by this entity/group: */
        struct rt_rq            *my_q;
#endif
};
  • run_list
    • 100개의 큐리스트 중 하나에 엔큐될 때 사용
  • timeout
    • 태스크에 설정된 실행 제한시간
  • watchdog_stamp
    • 마지막에 체크한 watchdog 시각
  • time_slice
    • 라운드 로빈용 rt 타임 슬라이스로 100ms에 해당하는 tick 수
    • 1개의 우선 순위 리스트큐 내의 rt 태스크들이 라운드로빈 처리 시 이 기간 이내에 라운드로빈 하지 않도록 제한한다.
    • 라운드 로빈 한 번 할 때마다 리필된다.
  • *back
    • rt 엔티티를 top-down으로 연결하고자 할 때 임시적으로 사용
  • *parent
    • 부모 rt 엔티티를 가리킨다.
    • RT 그룹 스케줄링을 사용하지 않는 경우 null
  • *rt_rq
    • rt 엔티티가 스케줄되어 소속될 rt 런큐를 가리킨다.
  • *my_q
    • rt 엔티티가 그룹을 대표하는 경우 그 대표하는 rt 런큐를 가리킨다.

 

rt_bandwidth 구조체

kernel/sched/sched.h

struct rt_bandwidth {
        /* nests inside the rq lock: */
        raw_spinlock_t          rt_runtime_lock;
        ktime_t                 rt_period;
        u64                     rt_runtime;
        struct hrtimer          rt_period_timer;
};
  • rt_period
    • rt 글로벌 풀의 period (ns)
    • 디폴트 값은 1초
  • rt_runtime
    • rt 글로벌 풀의 런타임 (ns)
    • 디폴트 값은 0.95초
  • rt_period_timer
    • rt period 타이머

 

rt_rq 구조체의 런타임 관련

kernel/sched/sched.h

/* Real-Time classes' related field in a runqueue: */
struct rt_rq { 
        struct rt_prio_array active;
        unsigned int rt_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
        struct {
                int curr; /* highest queued rt task prio */
#ifdef CONFIG_SMP
                int next; /* next highest */
#endif
        } highest_prio;
#endif
#ifdef CONFIG_SMP
        unsigned long rt_nr_migratory;
        unsigned long rt_nr_total;
        int overloaded;
        struct plist_head pushable_tasks;
#endif
        int rt_queued;

        int rt_throttled;
        u64 rt_time;
        u64 rt_runtime;
        /* Nests inside the rq lock: */
        raw_spinlock_t rt_runtime_lock;

#ifdef CONFIG_RT_GROUP_SCHED
        unsigned long rt_nr_boosted;

        struct rq *rq;
        struct task_group *tg;
#endif
};
  • active
    • rt_prio_array 구조체로 내부에 100개의 큐리스트가 어레이로 구성되어 있다.
  • rt_nr_running
    • rt 런큐 이하 계층 구조의 child 그룹들 모두에서 동작중인 rt 태스크의 수
  • highest_prio.curr
    • 현재 동작중인 최고 우선 순위
  • highest_prio.next
    • 차 우선 순위
  • rt_nr_migratory
    • migration 가능한 rt 태스크의 수로 엔큐/디큐될 때 태스크가 1개의 cpu로 고정된 경우가 아니면 증가/감소한다.
    • 다른 cpu로 push 가능한 태스크의 수
    • 참고: sched: add RT-balance cpu-weight
  • rt_nr_total
    • 최상위 rt 런큐만 갱신되는 rt 태스크의 수로 overload 체크를 위해 태스크가 엔큐/디큐될 때 증가/감소한다.
    • 이 값이 2 이상이고 rt_nr_migratory가 1 이상일 때 overload가 설정된다.
    • sched_rt: Fix overload bug on rt group scheduling
  • overloaded
    • 2 개 이상이 런큐에서 동작하려 할 때 1
    • 오버로드된 경우 가능하면 다른 cpu에서 끌어갈 수 있도록 한다. (for push operation)
  • pushable_tasks
  • rt_queued
    • rt 런큐가 이미 런큐에 엔큐된 경우 1
  •  rt_throttled
  • rt_time
    • RT 태스크가 사용한 런타임이 누적된다.
    • 아래 로컬 풀(rt_runtime)에 할당된 런타임을 초과하는 경우 스로틀한다.
  • rt_runtime
    • rt 로컬 풀에 할당된 런타임
    • UP 시스템인 경우 항상 글로벌의 런타임 값을 사용한다.
    • SMP 시스템인 경우 스로틀되는 cpu에 대해 밸런싱이 enable 된 경우 더 많은 런타임이 가도록 밸런싱을 할 수 있다.
    • sched: rt-group: smp balancing
  • rt_nr_boosted
  • *rq
    • 런큐를 가리킨다.
  • *tg
    • cgroup에서 그룹 스케줄링을 사용하는 경우 태스크 그룹을 가리킨다.

 

참고

 

 

답글 남기기

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