Scheduler -9- (RT Scheduler)

<kernel v5.4>

RT 스케줄러

RT 스케줄러의 우선 순위

rt 태스크들은 cfs 태스크들보다 항상 우선순위가 높아 먼저 실행될 권리를 갖는다. 다만 cpu를 offline 시킬 때 사용하는 stop 스케줄러에서 사용되는 stop 태스크와 deadline 스케줄러에서 사용하는 deadline 태스크들 보다는 우선 순위가 낮다. 스케줄러들 끼리의 우선 순위를 보면 다음과 같다.

 

RT 태스크의 우선 순위

rt 태스크들 끼리 경쟁할 때 스케줄링 순서를 알아본다. rt 태스크의 우선 순위는 0(highest priority) ~ 99(lowest priority)로 나뉜다. 이를 RT0 ~ RT99라고 표현하기도 한다. 동시에 RT50 태스크와 RT60 태스크가 경쟁하는 경우 RT50이 우선 순위가 더 높아 먼저 실행된다.

 

RT 런큐

rt 런큐는 cpu 수 만큼 생성된다. 물론 그룹 스케줄링을 사용하는 경우(cgroup의 cpu subsystem) 서브 그룹이 만들어질 때마다 cpu 수 만큼 추가로 만들어지는데 이는 잠시 후에 언급한다. rt 태스크들이 rt 스케줄러에 큐잉되면 rt 런큐에 존재하는 active라는 이름의 큐에 들어가는데 100개의 리스트로 이루어진 array[]에서 관리한다.  rt 스케줄러는 2 개 이상의 rt 태스크가 큐에서 관리될 때 우선 순위가 가장 높은 rt 태스크부터 실행시킨다.

 

아래 그림은 cpu#0의 rt 런큐에 4개의 rt 태스크들이 큐잉되어 동작하는 모습을 보여준다. 동작하는 순서는 A 태스크부터 D 태스크까지 각 rt 태스크들이 디큐될 때마다 다음 우선 순위의 태스크가 실행된다.

 

RT 태스크 실행 시간

RT 태스크는 한 번 실행되면 다음 조건으로만 멈추거나 다른 태스크로 변경될 수 있다.

• rt 스케줄러 보다 더 높은 우선 순위를 가진 스케줄러의 동작
  • stop 또는 deadline 태스크의 실행
• rt 태스크 스스로 슬립
  • schedule(), yield() 및 msleep() 등
• preemtible 커널에서 더 높은 우선 순위를 가진 rt 태스크의 실행
• RR(Round Robin) policy를 사용하고 동등한 우선 순위를 사용하는 태스크들 사이에서 실행 태스크 변경
• rt 밴드위드로 인해 스로틀
• rt 태스크 종료

 

RT 태스크용 스케줄링 정책(policy)

RT 태스크의 우선 순위가 같을 때 처리 순서가 바뀌는 다음 2 가지의 RT 스케줄링 정책을 지원한다.

• SCHED_FIFO
  • 먼저 실행된 태스크가 끝날 때 까지 계속 수행한다.
• SCHED_RR
  • 같은 우선 순위의 태스크는 커널에서 설정된 기간(디폴트 100ms) 단위로 실행 순서를 바꾼다.

 

RT 태스크 preemption

현재 처리하는 RT 태스크의 우선 순위보다 더 높은 우선 순위의 RT 태스크가 RT 런큐에 엔큐되면 당연히 우선 순위가 더 높은 RT 태스크를 실행한다. 하지만 기존 태스크가 커널에서 만들어진 커널용 태스크인 경우에는 커널의 preemption  옵션에 따라 우선 순위가 바뀌지 않을 수도 있고, 약간 지연 또는 즉각 반영되어 바뀔 수도 있다.

• 참고: Scheduler -3- (Preemption & Context Switch) | 문c

 

RT 그룹 스케줄링

그룹 스케줄링을 사용하는 경우 아래 그림과 같이 관리된다. 우선 순위만 보면 RT 그룹 스케줄링을 사용하는 것과 사용하지 않는 것은 스케줄링에 대해 다른 점을 구별할 수 없다. RT 그룹 스케줄링을 사용할 때에는 RT 밴드위드에서 쓰임새가 달라진다. RT 밴드위드의 동작은 CFS 밴드위드의 동작과 거의 유사하게 동작한다. 그룹에 주기(period)와 런타임(runtime)이 주어지고 주기마다 런타임이 소진되면 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,
        .set_next_task          = set_next_task_rt,

#ifdef CONFIG_SMP
        .balance                = balance_rt,
        .select_task_rq         = select_task_rq_rt,
        .set_cpus_allowed       = set_cpus_allowed_common,
        .rq_online              = rq_online_rt,
        .rq_offline             = rq_offline_rt,
        .task_woken             = task_woken_rt,
        .switched_from          = switched_from_rt,
#endif

        .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,

#ifdef CONFIG_UCLAMP_TASK
        .uclamp_enabled         = 1,
#endif
};

 

---

RT 스케줄 틱

task_tick_rt()

kernel/sched/rt.c

/*
 * scheduler tick hitting a task of our scheduling class.
 *
 * NOTE: This function can be called remotely by the tick offload that
 * goes along full dynticks. Therefore no local assumption can be made
 * and everything must be accessed through the @rq and @curr passed in
 * parameters.
 */

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);
        update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 1);

        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;
                }
        }
}

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

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

 

• 코드 라인 5에서 현재 실행 중인 rt 태스크에 대한 런타임 등을 갱신한다.
• 코드 라인 6에서 rt 런큐의 로드 평균 등을 갱신한다.
• 코드 라인 8에서 유저용 rt 태스크에 제한시간(RLIMIT_RTTIME)이 설정된 경우 태스크의 cpu 시간 만료를 체크한다.
• 코드 라인 14~15에서 태스크의 스케줄 정책이 라운드 로빈(SCHED_RR)이 아니면 함수를 빠져나간다.
  • rt 태스크에서 사용하는 스케줄 정책은 SCHED_RR 및 SCHED_FIFO가 있다.
• 코드 라인 17~18에서 라운드 로빈 policy를 가진 경우이다. 아직 라운드 로빈할 시각이 안된 경우 함수를 빠져나간다.
  • sched_rr_timeslice
    • 디폴트 100 ms에 해당하는 RR 틱 카운터
• 코드 라인 20에서 rt 태스크의 타임 슬라이스에 라운도 로빈용 타임 슬라이스(디폴트 100 ms)를 대입한다.
• 코드 라인 26~32에서 rt 태스크의 최상위 rt 스케줄 엔티티까지 순회하며 복수개의 스케줄 엔티티가 있는 경우 라운도 로빈 처리하고 리스케줄 요청 플래그를 설정한다.
  • rt 런큐 어레이 리스트 중 해당 스케줄 엔티티가 소속된 우선순위의 리스트에 복수의 rt 스케줄 엔티티가 있는 경우 해당 스케줄 엔티티의 우선순위를 양보하기 위해 해당 리스트의 뒤로 리큐하고 리스케줄 요청 플래그를 설정하는 것으로 매 스케줄 틱마다 라운드 로빈 기능을 수행한다.
  • 같은 우선 순위의 라운드 로빈 정책을 사용하는 rt 태스크는 매 스케줄 틱마다 돌아가며 수행되게 한다.

 

다음 그림은 task_tick_rt() 함수 이후의 호출 관계를 보여준다.

 

라운드 로빈

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 태스크를 라운드 로빈 처리한다. @head=1일 때 리스트의 선두로, 0일 때 후미로 이동시킨다.

 

다음 그림은 같은 우선 순위를 가진 RT 태스크(R1, A1, A2)들이 라운드 로빈을 하는 모습을 보여준다.

• A1 -> R1 -> A2 -> R1 사이클을 반복한다.

 

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 스케줄 엔티티를 라운드 로빈 처리한다. 디큐 및 엔큐 처리로 인한 오버헤드를 없애기 위해 스케줄 엔티티만 이동시킨다.

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

 

다음 그림은 요청한 rt 엔티티를 라운드 로빈하는 것을 보여준다.

 

---

로드 및 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;
        u64 now;

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

        now = rq_clock_task(rq);
        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 = now;
        cpuacct_charge(curr, 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 태스크의 런타임을 갱신한다. 그리고  라운드 로빈할 태스크가 있는 경우 리스케줄 요청한다.

• 코드 라인 8~9에서 현재 동작중인 태스크가 rt 태스크가 아닌 경우 함수를 빠져나간다.
• 코드 라인 11~14에서 현재 시각에서 지난 갱신 때의 시각을 뺀 delta 실행 시간을 구한다. 만일 실행 시간이 0보다 작으면 함수를 빠져나간다.
• 코드 라인 16~17에서 스케줄 통계를 위해 태스크의 최대 delta 실행 시각을 갱신한다.
• 코드 라인 19에서 현재 태스크의 실행 시간 총합을 갱신한다.
• 코드 라인 20에서 현재 스레드 그룹용 총 시간 관리를 위해 cpu 타이머가 동작하는 동안 총 실행 시간을 갱신한다.
  • posix timer를 통해 만료 시 시그널을 발생한다.
• 코드 라인 22에서 다음 갱신시 delta 실행 시각을 구하기 위해 현재 시각을 기록한다.
• 코드 라인 23에서 태스크의 cputime과 cpu cgroup용 cputime을 갱신한다.
  • cputime: 커널 소모 시간과 유저 소모 시간 누적
• 코드 라인 25~26에서글로벌 rt bandwidth가 설정되지 않은 경우 함수를 빠져나간다.
  • 디폴트로 0.95초로 설정되어 있다.
    • sysctl_sched_rt_runtime(950,000 us = 0.95 s)
    • “/proc/sys/kernel/sched_rt_runtime_us“
• 코드 라인 32~37에서 최상위 rt 엔티티까지 순회하며 rt 런큐의 rt_time에 실행 시각을 누적시킨다.
• 코드 라인 38~39에서 rt 런타임이 초과된 경우 rt 스로틀 시킨 후 리스케줄 요청 플래그를 설정한다.

 

다음 예와 같이 태스크 그룹에 대해 커널이 사용한 시간과 유저가 사용한 시간을 틱 수로 보여준다.

$ cat /sys/fs/cgroup/cpu/A/cpuacct.stat
user 47289
system 5

 

---

RT Watchdog

유저용 RT 태스크가 슬립 없이 일정 기간(rlimit) 이상 가동되는 경우 이 RT 태스크에 시그널을 전달한다. 별도의 시그널 처리기가 없으면 태스크가 종료된다.

• RLIMIT_RTTIME 파라미터로 rlimit min/max를 설정한다. (us)
• min 타임이 초과하는 경우 SIGXCPU 시그널을 전달한다.
• max 타임이 초과하는 경우 SIGKILL 시그널을 전달한다.

 

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)
                        posix_cputimers_rt_watchdog(&p->posix_cputimers,
                                                    p->se.sum_exec_runtime);
        }
}

유저용 rt 태스크에 제한시간(RLIMIT_RTTIME)이 설정된 경우 태스크의 cpu 시간 만료를 체크한다.

• 코드 라인 6~7에서 rt 태스크의 현재 제한시간(us)과 최대 제한시간(us)을 알아온다.
• 코드 라인 9~15에서 rt 태스크에 RLIMIT_RTTIME이 설정되어 있는 경우 현재 rt 태스크의 실행 시간(틱 카운터로 p->rt.timeout 사용)을 증가시키고, 워치독 스탬프에 현재 시각(jiffies)을 갱신한다.
• 코드 라인 17~20에서 틱 단위로 증가시킨 rt 태스크 실행 시간이 us 단위의 soft 또는 hard rlimit 값을 틱 단위로 바꾼 시각을 초과한 경우 POSIX cpu 타이머에 수행 시간 총합을 기록하여 posix cpu 타이머 처리 루틴에서 관련 시그널을 선택하여 보낼 수 있게 한다.
  • 참고로 rt 태스크가 슬립했다 깨어나는 경우 timeout은 0으로 다시 초기화된다.

 

RT 태스크 실행 시간 제약 샘플

test.c

#include <sys/resource.h>

void main()
{
        long long n = 0;
        struct rlimit rlim;

        rlim.rlim_cur = 2000000; /* us */
        rlim.rlim_max = 3000000; /* us */
        if (setrlimit(RLIMIT_RTTIME, &rlim) == -1)
                return;

        while (1)
                n++;
}

 

run.sh

gcc test.c -o test
date +"%Y-%m-%d %H:%M:%S.%N"
chrt -f 50 ./test
date +"%Y-%m-%d %H:%M:%S.%N"

 

슬립없이 유저용 rt 태스크를 계속 돌리면 SIGXCPU 시그널이 발생된 후 다음과 같이 메시지를 출력하고 태스크를 종료시킨다.

$ ./run.sh
2020-10-21 20:36:48.014463532
./run.sh: line 3:  8697 CPU time limit exceeded chrt -f 50 ./test
2020-10-21 20:36:50.025738816

 

---

RT Bandwidth

글로벌 RT Bandwidth

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

• sysctl_sched_rt_runtime
  • 디폴트 값: 950,000 us (0.95 초)
  • “/proc/sys/kernel/sched_rt_runtime_us“
• sysctl_sched_rt_period
  • 디폴트 값: 1,000,000 us (1초)
  • “/proc/sys/kernel/sched_rt_period_us“

 

그룹 RT Bandwidth

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

• rt_runtime_us
  • 하위 태스크 그룹의 디폴트 값: 0 us (disable)
  • 루트 태스크 그룹의 디폴트 값: 950,000 us (0.95초)
  • “/sys/fs/cgroup/cpu/<태스크 그룹>/rt_runtime_us“
• rt_period_us
  • 디폴트 값: 1,000,000 us (1초)
  • “/sys/fs/cgroup/cpu/<태스크 그룹>/rt_period_us“

 

디폴트 설정을 그대로 사용하는 경우 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;
        else if ((u64)rt_runtime_us > U64_MAX / NSEC_PER_USEC)
                return -EINVAL;

        return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);
}

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

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

        if (tg->rt_bandwidth.rt_runtime == RUNTIME_INF)
                return -1;

        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~6에서 rt 런타임이 설정되지 않은 경우 period 설정을 포기한다.
• 코드 라인 8에서 인수로 받은 rt_period_us 값을 나노초 단위로 변환한다.
• 코드 라인 9에서 rt bandwidth에 설정되어 있는 런타임(ns) 값을 가져온다.
• 코드 라인 11에서 요청한 태스크 그룹에 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을 반환한다.

• 코드 라인 3에서 로컬 rt 런타임을 알아온다.
• 코드 라인 5~6에서 rt 런큐가 이미 스로틀 중인 경우 rt_rq_throttled() 결과를 반환한다.
  • 부스트된 경우에 빠르게 처리하기 위해 스로틀 여부와 상관 없이 0을 반환하여 리스케줄링 하지 않게 한다.
• 코드 라인 8~9에서 태스크 그룹의 rt bandwidth 런타임 설정이 기간 설정보다 큰 경우 스로틀할 필요가 없으므로 0을 반환한다.
• 코드 라인 11에서 RT_RUNTIME_SHARE feature(default=false)를 사용하면서 로컬 rt 런큐의 실행 시간이 글로벌 런타임을 초과한 경우 런타임 밸런싱을 수행한다.
  • 런타임밸런싱은 모자라는 런타임을 다른 cpu에서 빌려오는 일을 수행한다.
  • UP 시스템은 cpu가 1개 이므로 다른 cpu에서 남은 런타임을 빌릴 수 없어서 밸런싱 작업에 아무런 일도 하지 않는다.
• 코드 라인 12~14에서 런타임 밸런싱 작업을 하고 이 루틴에 들어왔다. 다시 한 번 보충되었을 수도 있는 로컬 rt 런타임 값을 알아온다. 단 로컬 런타임이 disable 상태라면 스로틀하지 않도록 0을 반환한다.
• 코드 라인 16~33에서 런타임 밸런싱 이후에도 로컬 rt 런큐의 실행 시간이 남은 로컬 rt 런타임을 초과한 경우이다. 만일 높은 확률로 rt 런타임이 설정되어 있는 경우 스로틀됨을 알리기 위해 1을 설정한다. 그렇지 않은 경우 rt 로컬 런타임 소모량을 0으로 리셋한다.
• 코드 라인 35~38에서 rt 로컬이 이미 스로틀되었고 pi 부스팅하지 않은 경우 rt 런큐에서 동작중인 엔티티 수만큼 감소시킨다. 그런 후 스로틀링 하도록 1을 반환한다. (그룹 엔티티의 디큐가 아님에 주의한다.)
  • 참고: sched/rt: Do not throttle when PI boosting (2012, v3.4-rc1)
• 코드 라인 41에서 스로틀 하지 않도록 0을 반환한다.

 

RT_RUNTIME_SHARE feature

• default 설정은 false이다.
• 이 feture를 켜서 사용하는 경우 어느 한 cpu에서 초과시킨 runtime을 다른 cpu의 runtime을 share하여 가져와서 사용하게 하여 사용자가 설정한 runtime을 전체 cpu를 대상으로 제어를 하게된다.
  • 예) runtime=18ms 설정하였고, 4 cpu system에서 cpu#0이 정해진 runtime을 초과하여 20ms를 실행한 경우 나머지 다른cpu에서 런타임을 1ms씩 각출하여 빌려온다.
    • cpu#0: runtime=20ms, cpu#1: runtime=19ms, cpu#2: runtime=19ms, cpu#3: runtime=19ms
• 이 feture를 사용하지 않으면 어느 한 cpu에서 초과시킨 runtime이 있어도, 다른 cpu들은 이를 무시하고 원래 정해진 runtime 만큼만 사용하게 한다.
  • 예) runtime=18ms 설정하였고, 4 cpu system에서 cpu#0이 정해진 runtime을 초과하여 20ms를 실행한 경우 나머지 다른cpu들에게서 runtime을 빌려오지 않고 각자 따라 동작한다.
    • cpu#0: runtime=20ms, cpu#1: runtime=20ms, cpu#2: runtime=20ms, cpu#3: runtime=20ms

 

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

 

---

RT 런큐의 디큐 및 엔큐

sched_rt_rq_dequeue()

kernel/sched/rt.c

static void sched_rt_rq_dequeue(struct rt_rq *rt_rq)
{
        struct sched_rt_entity *rt_se;
        int cpu = cpu_of(rq_of_rt_rq(rt_rq));

        rt_se = rt_rq->tg->rt_se[cpu];

        if (!rt_se) {
                dequeue_top_rt_rq(rt_rq);
                /* Kick cpufreq (see the comment in kernel/sched/sched.h). */
                cpufreq_update_util(rq_of_rt_rq(rt_rq), 0);
        }
        else if (on_rt_rq(rt_se))
                dequeue_rt_entity(rt_se, 0);
}

rt 런큐를 디큐한다.

• 코드 라인 6에서 rt 런큐에 해당하는 그룹 엔티티를 알아온다.
• 코드 라인 8~12에서 최상위 root 인경우 rt 그룹 엔티티가 없다. 이 때엔 최상위 rt 런큐를 디큐 표시하고, util을 갱신한다.
• 코드 라인 13~14에서 rt 그룹 엔티티를 디큐한다.

 

sched_rt_rq_enqueue()

kernel/sched/rt.c

static void sched_rt_rq_enqueue(struct rt_rq *rt_rq)
{
        struct task_struct *curr = rq_of_rt_rq(rt_rq)->curr;
        struct rq *rq = rq_of_rt_rq(rt_rq);
        struct sched_rt_entity *rt_se;

        int cpu = cpu_of(rq);

        rt_se = rt_rq->tg->rt_se[cpu];

        if (rt_rq->rt_nr_running) {
                if (!rt_se)
                        enqueue_top_rt_rq(rt_rq);
                else if (!on_rt_rq(rt_se))
                        enqueue_rt_entity(rt_se, 0);

                if (rt_rq->highest_prio.curr < curr->prio)
                        resched_curr(rq);
        }
}

rt 런큐를 엔큐한다.

• 코드 라인 9에서 rt 런큐에 해당하는 그룹 엔티티를 알아온다.
• 코드 라인 11에서 rt 런큐에 동작 중인 엔티티가 있는 경우에만 엔큐를 할 수 있다.
• 코드 라인 12~13에서 최상위 root 인경우 rt 그룹 엔티티가 없다. 이 때엔 최상위 rt 런큐를 엔큐 표시한다.
• 코드 라인 14~15에서 rt 그룹 엔티티를 엔큐한다.
• 코드 라인 17~18에서 우선 순위의 변경이 필요한 경우 리스케줄 요청한다.

 

최상위 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 런큐에서 동작중인 엔티티 수를 감산하여 갱신한다.
  • rq->nr_running -= rt_rq->rt_nr_running
• 코드 라인 14에서 rt 런큐를 디큐된 상태로 설정한다.

 

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

• rt 태스크의 수가 18개 씩이나 동시에 동작하는 상황은 보통 실제 상황에는 거의 없고, 이해를 돕기 위한 숫자일 뿐이다.

 

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))
                return;

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

        /* Kick cpufreq (see the comment in kernel/sched/sched.h). */
        cpufreq_update_util(rq, 0);
}

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

• 코드 라인 8~9에서 최상위 rt 로컬 런큐가 이미 엔큐된 상태이면 함수를 빠져나온다.
• 코드 라인 11~12에서 최상위 rt 로컬 런큐가 이미 스로틀 상태이면서  pi 부스트하지 않는 경우 함수를 빠져나간다.
• 코드 라인 14~17에서 rt 런큐에 동작 가능한 엔티티가 있는 경우 rt 런큐를 엔큐 상태로 변경한다. 그리고 동작중인 태스크 수를 추가하여 갱신한다.
  • rq->nr_running += rt_rq->rt_nr_running
• 코드 라인 20에서 런큐 util을 갱신한다.

 

---

RT 런타임 밸런싱

balance_runtime()

kernel/sched/rt.c

static void balance_runtime(struct rt_rq *rt_rq)
{
        if (!sched_feat(RT_RUNTIME_SHARE))
                return;

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

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

• 코드 라인 3~4에서 RT_RUNTIME_SHARE 기능을 사용하지 않는 경우 함수를 빠져나간다.
  • 빌려오는 런타임때문에 cfs 태스크의 기아(starving) 현상이 발생할 수 있어 커널 v5.10-rc1에서 디폴트 값을 disable 하였다.
    • 참고: sched/rt: Disable RT_RUNTIME_SHARE by default (2020)
• 코드 라인 6~10에서 요청한 rt 런큐의 할당된 런타임을 모두 소모한 경우 다른 rt 로컬 풀로부터 빌려와서 최대한 rt_period 만큼 더 할당하여 늘리도록 밸런싱을 수행한다.

 

다음 그림은 RT_RUNTIME_SHARE 기능을 사용하지 않을 때 특정 태스크 그룹의 rt 밴드위드의 동작을 보여준다.

 

다음 그림은 RT_RUNTIME_SHARE 기능을 사용할 때 특정 태스크 그룹의 rt 밴드위드의 동작을 보여준다.

• 로컬 런타임이 부족한 경우 SMP 시스템에서는 다른 cpu로 부터 런타임을 빌려오는 런타임 밸런싱 작업을 수행한다.

 

do_balance_runtime()

kernel/sched/rt.c

/*
 * We ran out of runtime, see if we can borrow some from our neighbours.
 */

static void 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;
        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;
                        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);
}

요청한 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~38에서 순회하는 rt 로컬 런큐의 런타임 할당 값에서 diff를 빌려오고 인수로 요청한 rt 로컬 런큐의 런타임 할당 값에 추가한다.
• 코드 라인 39~42에서 빌려와서 채운 런타임 할당이 rt_period와 같은 경우 더 이상 빌려올 필요가 없으므로 루프를 탈출한다.

 

---

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 엔티티들을 디큐한다.

• 코드 라인 5~8에서 루트 방향의 계층적 rt 엔티티를 반대로 구성한다.
• 코드 라인 10에서 최상위 rt 런큐를 디큐 상태로 바꾸고 최상위 rt 런큐에있는 태스크 수만큼 감소시킨다. (rq->nr_running 갱신)
• 코드 라인 12~15에서 최상위 엔티티부터 요청한 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 엔티티를 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;

        if (move_entity(flags)) {
                WARN_ON_ONCE(!rt_se->on_list);
                __delist_rt_entity(rt_se, array);
        }
        rt_se->on_rq = 0;
        dec_rt_tasks(rt_se, rt_rq);
}

rt 엔티티를 rt 런큐에서 디큐한다.

• 코드 라인 6~9에서 rt 엔티티를 리스트에서 제거한다. 이 때 비트맵도 같이 갱신한다.
• 코드 라인 10에서 rt 엔티티에 디큐된 상태를 표시한다.
• 코드 라인 11에서 디큐된 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);
        rt_rq->rr_nr_running += rt_se_rr_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 엔티티에 대한 후속 작업을 수행한다.

• 코드 라인 7에서 rt 런큐 이하에서 동작 중인 rt 태스크 수를 갱신한다.
  • rt 엔티티가 태스크인 경우 1을 증가시키고 그룹인 경우 그룹이하에서 동작하는 rt 태스크의 수를 증가시킨다.
• 코드 라인 8에서 rt 런큐 이하에서 동작 중인  round robin policy를 가진 rt 태스크 수를 증가시킨다.
• 코드 라인 10에서 엔큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.
• 코드 라인 11에서 추가된 rt 엔티티가 태스크인 경우 런큐의 overload 카운터를 증가시키고 런큐에 오버로드 여부를 갱신한다.
  • rt_nr_total++
  • 태스크에 2 개 이상 cpu가 할당된 경우 rt_nr_migratory++
  • 태스크에 2개 이상 cpu가 할당되고 2개 이상 rt 태스크가 동작하는 경우 현재 런큐에 overload 설정
• 코드 라인 12에서 추가된 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);
        rt_rq->rr_nr_running -= rt_se_rr_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 태스크의 수를 감소시킨다.
• 코드 라인 7에서 rt 런큐 이하에서 동작 중인  round robin policy를 가진 rt 태스크 수를 감소시킨다.
• 코드 라인 9에서 디큐된 rt 엔티티로 인해 최고 우선 순위가 변경된 경우 이를 갱신하고 cpupri 설정도 수행한다.
• 코드 라인 10에서 추가된 rt 엔티티가 태스크인 경우 런큐의 overload 카운터를 감소시키고 런큐에 오버로드 여부를 갱신한다.
  • rt_nr_total–
  • 태스크에 2 개 이상 cpu가 할당된 경우 rt_nr_migratory–
  • 태스크에 cpu가 1개만 설정되거나 rt 태스크가 1개 이하이면 오버로드할 수 없으므로 클리어
• 코드 라인 11에서 추가된 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 태스크의 수를 반환한다.

 

rt_se_rr_nr_running()

kernel/sched/rt.c

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

        if (group_rq)
                return group_rq->rr_nr_running;

        tsk = rt_task_of(rt_se);

        return (tsk->policy == SCHED_RR) ? 1 : 0;
}

round robin policy를 가진 rt 엔티티와 관련된 태스크 수를 반환한다. rt 엔티티가 rr 태스크이면 1을 반환하고, 태스크 그룹용이면 태스크 그룹을 포함한 그 이하 child rr 태스크의 수를 반환한다.

 

---

CPU Priority Management with highest priority

다음과 같이 총 102개의 우선 순위를 관리한다.

• 100개의 RT 우선 순위
• idle
• cfs normal

 

위의 102 단계의 우선 순위를 다음과 같이 즉각 변환하도록 관리한다.

• cpu -> 우선 순위
• 우선 수위 -> cpu

 

다음 그림은 cpu와 priority와의 컨버전에 사용되는 배열을 보여준다.

 

inc_rt_prio()

kernel/sched/rt.c

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 설정도 수행한다.

• 코드 라인 4~7에서 rt 런큐내에서 요청한 우선 순위가 가장 높은(낮은 prio 숫자값이 가장 높은 우선순위이다.)인 경우 이를 갱신한다.
• 코드 라인 9에서 요청한 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 태스크가 없으면 비어 있는 상태로 초기화한다. (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에  설정한다.

 

Highest RT 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;
        }

• 코드 라인 7에서 인수로 받은 우선순위를 사용하여 cpupri로 변환한다.
• 코드 라인 11~13에서 현재 cpu가 이미 같은 우선 순위를 사용하고 있었으면 함수를 빠져나간다.
• 코드 라인 20~23에서 새 우선 순위에 해당하는 벡터의 cpumask에 요청한 cpu 비트를 설정한다.
• 코드 라인 29~31에서 새 우선 순위에서 동작하는 벡터의 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 비트를 클리어한다.
• 코드 라인 28에서 현재 cpu 위치에 newpri 값을 기록한다.

 

다음 그림은 루트 도메인의 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()

kernel/sched/cpupri.c

/**
 * 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;
                /*
                 * 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;
}

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

• 코드 라인 5에서 태스크에 설정된 140 단계의 우선 순위로 102 단계의 cpupri 우선 순위로 변환하여 task_pri에 대입한다.
• 코드 라인 9~10에서 인덱스를 0부터 태스크의 cpupri 번호까지 순회하며 해당하는 인덱스의 cpupri 벡터를 알아온다.
• 코드 라인 13~14에서 인덱스 번호의 cpupri를 사용하는 cpu가 없는 경우 skip=1을 설정한다.
• 코드 라인 36~37에서 메모리 배리어를 수행한 후 skip 설정이 있으면 다음 인덱스 번호로 skip 한다.
• 코드 라인 39~40에서 순회하는 cpupri 벡터에서 사용하는 cpu와 태스크에 허용된 cpu들이 중복된 cpu들 중 하나의 랜덤 cpu 번호가 최대 cpu 수 이상이면 처리할 수 없어 skip 한다.
  • cpus_allowed는 cgroup의 cpuset 서브시스템을 컨트롤하여 특정 태스크에 허용하는 cpu들을 지정한다.
• 코드 라인 42~43에서 출력 인수 lowest_mask가 지정된 경우 순회하는 cpupri 벡터에서 사용하는 cpu와 태스크에 허용된 cpu들이 중복된 cpu들을 알아와서 출력 인수 lowest_mask에 대입한다.
• 코드 라인 53~54에서 출력 인수 lowest_mask에서 랜덤으로 가져온 cpu 번호가 최대 cpu 수 이상이면 처리할 수 없어 skip 한다.
• 코드 라인 57~60에서 정상적으로 찾았으므로 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;

        raw_spin_lock(&rt_b->rt_runtime_lock);
        if (!rt_b->rt_period_active) {
                rt_b->rt_period_active = 1;
                /*
                 * SCHED_DEADLINE updates the bandwidth, as a run away
                 * RT task with a DL task could hog a CPU. But DL does
                 * not reset the period. If a deadline task was running
                 * without an RT task running, it can cause RT tasks to
                 * throttle when they start up. Kick the timer right away
                 * to update the period.
                 */
                hrtimer_forward_now(&rt_b->rt_period_timer, ns_to_ktime(0));
                hrtimer_start_expires(&rt_b->rt_period_timer,
                                      HRTIMER_MODE_ABS_PINNED_HARD);
        }
        raw_spin_unlock(&rt_b->rt_runtime_lock);
}

rt bandwidth용 period 타이머를 동작시킨다.

• 코드 라인 3~4에서 글로벌 밴드위드가 설정되지 않았거나, 그룹에 rt 런타임 설정이 없는 경우 함수를 빠져나간다.
• 코드 라인 6~21에서 rt_period_timer가 않는 경우에 한해 타이머를 가동시킨다.
  • rt period 타이머는 hardirq에서 동작하도록 설정된다.

 

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);
        int idle = 0;
        int overrun;

        raw_spin_lock(&rt_b->rt_runtime_lock);
        for (;;) {
                overrun = hrtimer_forward_now(timer, rt_b->rt_period);
                if (!overrun)
                        break;

                raw_spin_unlock(&rt_b->rt_runtime_lock);
                idle = do_sched_rt_period_timer(rt_b, overrun);
                raw_spin_lock(&rt_b->rt_runtime_lock);
        }
        if (idle)
                rt_b->rt_period_active = 0;
        raw_spin_unlock(&rt_b->rt_runtime_lock);

        return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
}

• 코드 라인 3~4에서 그룹에 설정된 rt bandwidth 값을 알아온다.
• 코드 라인 9~17에서 타이머를 forward 시키고, overrun이 없는 경우 더 이상 처리할 일이 없으므로 루프를 빠져나가고, overrun이 발생한 경우 period 타이머 만료에 대한 처리를 수행한다.
• 코드 라인 18~19에서 idle 결과인 경우 period 타이머가 동작하지 않음을 알리도록 rt_period_active를 0으로 설정한다.
• 코드 라인 22에서 idle 결과 값에 따라 idle인 경우 hrtimer가 재설정되지 않게 HRTIMER_NORESTART를 반환한다. idle이 아닌 경우 hrtimer가 재설정되도록 HRTIMER_RESTART를 반환한다.

 

do_sched_rt_period_timer()

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
        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);
                int skip;

                /*
                 * When span == cpu_online_mask, taking each rq->lock
                 * can be time-consuming. Try to avoid it when possible.
                 */
                raw_spin_lock(&rt_rq->rt_runtime_lock);
                if (!sched_feat(RT_RUNTIME_SHARE) && rt_rq->rt_runtime != RUNTIME_INF)
                        rt_rq->rt_runtime = rt_b->rt_runtime;
                skip = !rt_rq->rt_time && !rt_rq->rt_nr_running;
                raw_spin_unlock(&rt_rq->rt_runtime_lock);
                if (skip)
                        continue;

                raw_spin_lock(&rq->lock);
                update_rq_clock(rq);

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

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

 

• 코드 라인 3에서 idle 변수는 period 타이머를 stop 시킬지 여부를 반환하기 위한 값이다. (1=stop, 0=continue)
• 코드 라인 6에서 현재 cpu 런큐의 루트 도메인에 허가된 cpu 비트마스크를 알아온다.
• 코드 라인 17~18에서 루트 태스크 그룹의 경우 online된 cpu 전체를 사용한다.
• 코드 라인 20~22에서 rt 런큐에 소속된 cpu들을 순회한다.
• 코드 라인 31~32에서 RT_RUNTIME_SHARE 기능이 없고 그룹에 rt 런타임이 설정된 경우 그 설정 값을 로컬 런타임이 매 period 마다 사용하게 한다.
• 코드 라인 33~36에서 rt 수행시간이 없고, 수행할 rt 태스크도 없는 경우 skip 한다.
• 코드 라인 39에서 런큐 클럭을 갱신한다.

 

kernel/sched/rt.c -2/2-

                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_cancel_skipupdate(rq);
                        }
                        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에서 rt 런큐에서 rt 태스크가 수행한 시간이 0보다 큰 경우이다.
• 코드 라인 5~7에서 로컬 rt 런큐가 스로틀된 적이 있는 경우 다른 rt 로컬 풀로부터 런타임을 빌려오는 balance_runtime()을 수행한다. 그런 후 다시 로컬 런타임을 알아온다.
• 코드 라인 8에서 rt 런큐의 rt 수행시간에 overrun * rt 런타임 시간만큼 감소시칸다. 단 rt_time이 0 미만으로 내려가지 않게 제한한다.
• 코드 라인 9~24에서 스로틀을 해제할 수 있는 상황인경우 rt런큐를 엔큐한다.
  • rt 런큐가 스로틀 중이고, 런타임에 여유가 생겼으면 스로틀을 해제하기 위해 rt_throttled에 0을 대입한다.
  • idle 상태에서 rt 태스크가 깨어난 상황인 경우 클럭의 skip 요청을 취소한다.
• 코드 라인 26~35에서 rt_time이 0인 경우 idle=0, 그리고 스로틀을 풀러야 하는 상황이라면 엔큐를 한다.
• 코드 라인 39~40에서 rt 밴드위드를 동작시키지 않아도 될 때에는 1을 반환한다.
  • 스로틀되지 않고 rt bandwidth 설정도 없어야 한다.
• 코드 라인 42에서 period 타이머의 stop 여부를 결정하는 idle 상태를 반환한다. (1=stop, 0=continue)

 

---

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 시스템의 경우 요청한 태스크의 우선 순위와 현재 런큐에서 동작 중인 우선 순위가 동일하면서 현재 동작중인 태스크에 리스케줄 요청이 없으면 조건에 따라 요청한 태스크를 라운드 로빈하고 리스케줄 요청 플래그를 설정해야 하는지 체크한다.

 

check_preempt_equal_prio()

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에서 현재 태스크를 리큐하여 라운드 로빈할 수 있게한 후 리스케줄 요청 플래그를 설정한다.

 

---

Enqueue & Dequeue RT 태스크

enqueue_task_rt()

kernel/sched/rt.c

/*
 * Adding/removing a task to/from a priority array:
 */

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

        if (flags & ENQUEUE_WAKEUP)
                rt_se->timeout = 0;

        enqueue_rt_entity(rt_se, flags);

        if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
                enqueue_pushable_task(rq, p);
}

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

• 코드 라인 6~7에서 rt 태스크가 막 깨어나서 다시 런큐에 등록될 때엔 rt 워치독을 위한 timeout 설정을 클리어한다.
• 코드 라인 9에서 rt 엔티티를 rt 런큐에 엔큐한다.
• 코드 라인 11~12에서 rt 태스크가 rt 런큐에서 대기해야 하는 상황이고 현재 cpu로 제한하지 않은 상태인 경우 다른 cpu로 migration할 수 있도록 pushable 태스크 리스트에 추가한다.

 

dequeue_task_rt()

kernel/sched/rt.c

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

        update_curr_rt(rq);
        dequeue_rt_entity(rt_se, flags);

        dequeue_pushable_task(rq, p);
}

rt 태스크를 런큐에서 디큐한다.

• 코드 라인 5에서 현재 동작 중인 rt 태스크의 실행 시간등을 갱신한다.
• 코드 라인 6에서 rt 엔티티를 rt 런큐에서 디큐한다.
• 코드 라인 8에서 pushable 태스크 리스트에서 현재 rt 태스크를 디큐한다.

 

pushable 태스크 리스트에 추가 및 삭제

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 되지 않은 첫 태스크를 알아온다.

 

has_pushable_tasks()

kernel/sched/rt.c

static inline int has_pushable_tasks(struct rq *rq)
{
        return !plist_head_empty(&rq->rt.pushable_tasks);
}

pushable 태스크 리스트에 태스크가 존재하는지 여부를 반환한다.

 

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 되지 않은 태스크인지 여부를 반환한다.

 

pick_next_pushable_task()

kernel/sched/rt.c

static struct task_struct *pick_next_pushable_task(struct rq *rq)
{
        struct task_struct *p;

        if (!has_pushable_tasks(rq))
                return NULL;

        p = plist_first_entry(&rq->rt.pushable_tasks,
                              struct task_struct, pushable_tasks);

        BUG_ON(rq->cpu != task_cpu(p));
        BUG_ON(task_current(rq, p));
        BUG_ON(p->nr_cpus_allowed <= 1);

        BUG_ON(!task_on_rq_queued(p));
        BUG_ON(!rt_task(p));

        return p;
}

요청한 런큐의 pushable tasks 리스트에서 대기 중인 첫 번째 rt 태스크를 반환한다.

 

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

우선 순위 기반으로 소팅된 이중 리스트이다. 키에 사용될 우선 순위가 0~99까지 100개로 제한되어 있어서 RB 트리를 사용하는 것보다 더 효율적이다. 따라서 RT 스케줄러에서 이 자료 구조는 overload된 태스크들을 pushable_tasks plist에 추가할 때 소팅에 최적화된 모습을 보여준다.

• pushable_tasks에서 가장 높은 우선 순위의 태스크를 검색하는 경우: 가장 head에 있는 태스크를 사용한다.
• pushable_tasks에 태스크를 추가하는 경우: 2  개의 이중 리스트 중 prio_list를 사용하면 중복되는 우선 순위를 건너 띄며 검색하므로 더 빠른 검색이 가능하다. (물론 최악의 경우 99번이 필요하다.)

 

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

 

---

다음 태스크 픽업

pick_next_task_rt()

kernel/sched/rt.c

static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        struct task_struct *p;

        WARN_ON_ONCE(prev || rf);

        if (!sched_rt_runnable(rq))
                return NULL;

        p = _pick_next_task_rt(rq);
        set_next_task_rt(rq, p);
        return p;
}

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

• 코드 라인 8~9에서 런큐에 동작하는 rt 태스크가 없으면 null을 반환한다.
• 코드 라인 11에서 런큐에서 실행시킬 rt 태스크를 알아온다.
• 코드 라인 12~13에서 실행 시킬 rt 태스크를 next 태스크로 지정하고 반환한다.

 

_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 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);

        return rt_task_of(rt_se);
}

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

• 코드 라인 7에서 rt 런큐의 rt 어레이 리스트에서 가장 높은 우선 순위의 rt 엔티티를 찾아온다.
• 코드 라인 9~10에서 rt 엔티티가 그룹인 경우 다음 하위 그룹으로 이동하며 최종적으로 task인 rt 엔티티를 알아온다.
• 코드 라인 12에서 찾은 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 엔티티를 반환한다.

 

---

실행할 rt 태스크 지정

set_next_task_rt()

kernel/sched/rt.c

static inline void set_next_task_rt(struct rq *rq, struct task_struct *p)
{
        p->se.exec_start = rq_clock_task(rq);

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

        /*
         * If prev task was rt, put_prev_task() has already updated the
         * utilization. We only care of the case where we start to schedule a
         * rt task
         */
        if (rq->curr->sched_class != &rt_sched_class)
                update_rt_rq_load_avg(rq_clock_pelt(rq), rq, 0);

        rt_queue_push_tasks(rq);
}

요청한 태스크를 rt 런큐에서 지금 실행할 태스크로 지정한다.

• 코드 라인 3에서 rt 태스크에 시작 시각을 기록한다.
• 코드 라인 6에서 현재 cpu에서 동작시킬 것이므로 migration되지 않도록 pushable tasks 리스트에서 제거한다.
• 코드 라인 13~14에서 현재 실행 중인 태스크가 rt 태스크가 아닌 경우 rt 로드 평균 등을 갱신한다.
• 코드 라인 16에서 현재 런큐를 push 태스크 리스트에 등록한다.

 

---

기존 태스크 수행 완료 처리

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 런큐내에서 기존 rt 태스크의 수행 완료 처리를 한다.

• 코드 라인 3에서 rt 런큐의 현재 태스크에 대해 런타임 등을 갱신한다.
• 코드 라인 9~10에서 필요태스크가 rt 런큐에 있고 태스크에 할당된 cpu 수가 2개 이상인 경우 요청한 태스크를 최상위 런큐의 pushable_tasks 리스트에 추가한다.

 

---

밸런스

두  개 이상의 rt 태스크가 하나의 cpu에서 동작을 해야 하는 경우 하나의 rt 태스크를 제외한 나머지를 migration 시킬 수 있도록 다음과 같은 관리를 수행한다.

• pushable 태스크 리스트
  • migration이 필요한 rt 태스크를 해당 cpu 런큐의 pushable 리스트에 추가한다.
    • rq->pushable_lists
• overload 마스크
  • migration이 필요한 cpu에 대해 overload 마스크 설정을 한다.
    • rto_count++, rto_mask 설정

 

rt 태스크가 다른 cpu로 migration될 때 다음 함수 호출을 통해서 수행한다. 또한 migration할 cpu를 찾기 위해 cpu별로 102개의 priority를 갱신하여 이를 통해 우선 순위가 가장 낮은 cpu들을 가려낸다.

• balance_rt() – (*balance)
  • pull_rt_task() 함수 호출
  • RT_PUSH_IPI feature 사용 여부에 따라 IPI를 사용한 push 마이그레이션 또는 직접 pull 마이그레이션 해온다.
    • RT_PUSH_IPI feature 사용 시 overload된 cpu로 IPI 호출한다. 그 후 IPI 호출된 cpu는 가장 높은 우선 순위의 pushable 태스크부터 하나씩 낮은 우선 순위를 가진 cpu를 찾아 push 마이그레이션 한다.
    • RT_PUSH_IPI feature 미 사용 시 현재 cpu가 직접 overload된 cpu들의 런큐에서 현재 cpu의 우선 순위보다 높은 pushable 태스크들을 pull 마이그레이션해온다.
• task_woken_rt() – (*task_woken)
  • push_rt_tasks() 함수 호출
  • rt 런큐에 이미 동작 중인 태스크가 있고, 이 rt 태스크가 현재 cpu로 고정되었거나 깨어날 rt 태스크보다 우선 순위가 더 높은 경우 깨어날 rt 태스크를 migration하기 위해 해당 cpu가 직접 push 마이그레이션 한다.
• balance_callback() – (*balance_callback)
  • __schedule() 함수의 가장 마지막에서 post 처리를 위해 현재 cpu가 직접 push 마이그레이션 및 pull 마이그레이션을 수행하는 다음 함수 중 하나를 호출한다.
    • push_rt_tasks()
    • pull_rt_task()

 

balance_rt()

kernel/sched/rt.c

static int balance_rt(struct rq *rq, struct task_struct *p, struct rq_flags *rf)
{
        if (!on_rt_rq(&p->rt) && need_pull_rt_task(rq, p)) {
                /*
                 * This is OK, because current is on_cpu, which avoids it being
                 * picked for load-balance and preemption/IRQs are still
                 * disabled avoiding further scheduler activity on it and we've
                 * not yet started the picking loop.
                 */
                rq_unpin_lock(rq, rf);
                pull_rt_task(rq);
                rq_repin_lock(rq, rf);
        }

        return sched_stop_runnable(rq) || sched_dl_runnable(rq) || sched_rt_runnable(rq);
}

rt 태스크의 로드밸런스가 필요한지 여부를 확인하고 수행한다.

• 코드 라인 3에서 요청한 rt 태스크가 런큐에 없고, 현재 동작 중인 rt 태스크보다 우선 순위가 더 높은 경우이다.
• 코드 라인 11에서 rt 태스크를 마이그레이션 한다.
• 코드 라인 5에서 stop, dl 및 rt 태스크가 존재하는 경우 1을 반환한다.

 

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를 반환한다.

 

Push 태스크

rt_queue_push_tasks()

kernel/sched/rt.c

static inline void rt_queue_push_tasks(struct rq *rq)
{
        if (!has_pushable_tasks(rq))
                return;

        queue_balance_callback(rq, &per_cpu(rt_push_head, rq->cpu), push_rt_tasks);
}

런큐에 pushable 태스크가 있는 경우 콜백함수로 push_rt_tasks() 함수를 지정한다.

• __schedule() 함수에서 스케줄 처리를 완료한 후 마지막에 post 처리를 위해 이 콜백 함수가 호출된다.

 

queue_balance_callback()

kernel/sched/rt.c

static inline void
queue_balance_callback(struct rq *rq,
                       struct callback_head *head,
                       void (*func)(struct rq *rq))
{
        lockdep_assert_held(&rq->lock);

        if (unlikely(head->next))
                return;

        head->func = (void (*)(struct callback_head *))func;
        head->next = rq->balance_callback;
        rq->balance_callback = head;
}

런큐의 balance_callback 리스트에 밸런스를 위한 콜백 함수를 추가한다.

 

push_rt_tasks()

kernel/sched/rt.c

tatic void push_rt_tasks(struct rq *rq)
{
        /* push_rt_task will return true if it moved an RT */
        while (push_rt_task(rq))
                ;
}

런큐에서 overload된 태스크들을 모두 다른 cpu로 마이그레이션한다.

 

push_rt_task()

kernel/sched/rt.c

/*
 * If the current CPU has more than one RT task, see if the non
 * running task can migrate over to a CPU that is running a task
 * of lesser priority.
 */

static int push_rt_task(struct rq *rq)
{
        struct task_struct *next_task;
        struct rq *lowest_rq;
        int ret = 0;

        if (!rq->rt.overloaded)
                return 0;

        next_task = pick_next_pushable_task(rq);
        if (!next_task)
                return 0;

retry:
        if (WARN_ON(next_task == rq->curr))
                return 0;

        /*
         * It's possible that the next_task slipped in of
         * higher priority than current. If that's the case
         * just reschedule current.
         */
        if (unlikely(next_task->prio < rq->curr->prio)) {
                resched_curr(rq);
                return 0;
        }

        /* We might release rq lock */
        get_task_struct(next_task);

        /* find_lock_lowest_rq locks the rq if found */
        lowest_rq = find_lock_lowest_rq(next_task, rq);

        if (!lowest_rq) {
                struct task_struct *task;
                /*
                 * find_lock_lowest_rq releases rq->lock
                 * so it is possible that next_task has migrated.
                 *
                 * We need to make sure that the task is still on the same
                 * run-queue and is also still the next task eligible for
                 * pushing.
                 */
                task = pick_next_pushable_task(rq);
                if (task == next_task) {
                        /*
                         * The task hasn't migrated, and is still the next
                         * eligible task, but we failed to find a run-queue
                         * to push it to.  Do not retry in this case, since
                         * other CPUs will pull from us when ready.
                         */
                        goto out;
                }

                if (!task)
                        /* No more tasks, just exit */
                        goto out;

                /*
                 * Something has shifted, try again.
                 */
                put_task_struct(next_task);
                next_task = task;
                goto retry;
        }

        deactivate_task(rq, next_task, 0);
        set_task_cpu(next_task, lowest_rq->cpu);
        activate_task(lowest_rq, next_task, 0);
        ret = 1;

        resched_curr(lowest_rq);

        double_unlock_balance(rq, lowest_rq);

out:
        put_task_struct(next_task);

        return ret;
}

런큐에서 overload된 태스크 하나를 다른 cpu로 마이그레이션한다.

• 코드 라인 7~8에서 런큐가 오버 로드된 적이 없으면 함수를 빠져나간다.
• 코드 라인 10~12에서 pushable 태스크 리스트에서 가장 우선 순위가 높은 태스크를 알아온다.
• 코드 라인 14~16에서 retry: 레이블이다. 선택된 next 태스크가 런큐에서 이미 실행 중인 경우 함수를 빠져나간다.
• 코드 라인 23~26에서 선택된 next 태스크가 현재 런큐에서 동작 중인 태스크보다 더 높은 우선 순위를 가진 경우 리스케줄 요청하고 함수를 빠져나간다.
• 코드 라인 32에서 가장 낮은 우선 순위를 가진 cpu의 런큐를 선택한다. 이 때 런큐와 찾은 cpu의 런큐 둘 다 락을 건 상태로 온다.
• 코드 라인 34~65에서 적절한 cpu를 찾지 못한 경우 다시 한 번 시도하기 위해 retry 레이블로 이동한다.
• 코드 라인 67~69에서 마이그레이션을 하기 위해 next_task를 현재 런큐에서 꺼낸 후 찾은 cpu의 런큐에 집어 넣는다. 이 때 태스크에는 이동되는 cpu 번호를 기록한다.
• 코드 라인 70에서 리턴 값으로 1을 지정하여 추가 마이그레이션을 하도록 한다.
• 코드 라인 72에서 찾은 cpu의 런큐에 리스케줄 요청을 한다.
• 코드 라인 74에서 두 개의 런큐 락을 해제한다.

 

find_lock_lowest_rq()

kernel/sched/rt.c

/* Will lock the rq it finds */
static struct rq *find_lock_lowest_rq(struct task_struct *task, struct rq *rq)
{
        struct rq *lowest_rq = NULL;
        int tries;
        int cpu;

        for (tries = 0; tries < RT_MAX_TRIES; tries++) {
                cpu = find_lowest_rq(task);

                if ((cpu == -1) || (cpu == rq->cpu))
                        break;

                lowest_rq = cpu_rq(cpu);

                if (lowest_rq->rt.highest_prio.curr <= task->prio) {
                        /*
                         * Target rq has tasks of equal or higher priority,
                         * retrying does not release any lock and is unlikely
                         * to yield a different result.
                         */
                        lowest_rq = NULL;
                        break;
                }

                /* if the prio of this runqueue changed, try again */
                if (double_lock_balance(rq, lowest_rq)) {
                        /*
                         * We had to unlock the run queue. In
                         * the mean time, task could have
                         * migrated already or had its affinity changed.
                         * Also make sure that it wasn't scheduled on its rq.
                         */
                        if (unlikely(task_rq(task) != rq ||
                                     !cpumask_test_cpu(lowest_rq->cpu, task->cpus_ptr) ||
                                     task_running(rq, task) ||
                                     !rt_task(task) ||
                                     !task_on_rq_queued(task))) {

                                double_unlock_balance(rq, lowest_rq);
                                lowest_rq = NULL;
                                break;
                        }
                }

                /* If this rq is still suitable use it. */
                if (lowest_rq->rt.highest_prio.curr > task->prio)
                        break;

                /* try again */
                double_unlock_balance(rq, lowest_rq);
                lowest_rq = NULL;
        }

        return lowest_rq;
}

가장 낮은 우선 순위를 가진 cpu의 런큐를 선택한다. 성공 시 요청한 런큐와 찾은 cpu의 런큐 둘 다 락을 건 상태로 리턴한다.

• 코드 라인 8~9에서 최대 3번 동안 순회하며 cpu들 중 가장 우선 순위가 낮은 태스크들이 수행되는 cpu의 lowest 런큐를 찾는다.
• 코드 라인 11~12에서 찾은 cpu가 현재 cpu인 경우 루프를 멈춘다.
• 코드 라인 14~24에서 찾은 lowest 런큐에서 동작 중인 태스크의 우선 순위가 요청한 태스크(현재 cpu에서 동작 중)의 우선 순위보다 더 높은 경우 찾은 lowest 런큐를 포기하고 null을 반환한다.
• 코드 라인 27~44에서 두 개의 런큐 락을 획득한다.
• 코드 라인 34~43에서 다음의 경우들은 lowest 런큐를 포기하고 null을 반환한다.
  • 요청한 태스크가 현재 런큐에 없거나 만일 실패하는 경우
  • 태스크에 지정된 cpu 범위를 벗어난 경우
    • 예: taskset -c 0-3 -> 0~3번 cpu만 사용
  • 태스크가 이미 러닝 중인 경우
  • 태스크가 rt 태스크가 아닌 경우
  • 태스크가 rt 런큐에서 디큐된 경우
• 코드 라인 47~48에서 최종 선택한 lowest 런큐에서 수행 중인 태스크 보다 요청한 태스크의 우선 순위가 더 높은 경우 찾은 lowest 런큐를 반환한다.
• 코드 라인 51~52에서 최대 3회를 다시 시도한다.
• 코드 라인 55에서 찾은 lowest 런큐를 반환한다.

 

Pull 태스크

rt_queue_pull_task()

kernel/sched/rt.c

static inline void rt_queue_pull_task(struct rq *rq)
{
        queue_balance_callback(rq, &per_cpu(rt_pull_head, rq->cpu), pull_rt_task);
}

런큐에 pushable 태스크가 있는 경우 콜백함수로 pull_rt_task() 함수를 지정한다.

• __schedule() 함수에서 스케줄 처리를 완료한 후 마지막에 post 처리를 위해 이 콜백 함수가 호출된다.

 

pull_rt_task()

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

static void pull_rt_task(struct rq *this_rq)
{
        int this_cpu = this_rq->cpu, cpu;
        bool resched = false;
        struct task_struct *p;
        struct rq *src_rq;
        int rt_overload_count = rt_overloaded(this_rq);

        if (likely(!rt_overload_count))
                return;

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

        /* If we are the only overloaded CPU do nothing */
        if (rt_overload_count == 1 &&
            cpumask_test_cpu(this_rq->cpu, this_rq->rd->rto_mask))
                return;

#ifdef HAVE_RT_PUSH_IPI
        if (sched_feat(RT_PUSH_IPI)) {
                tell_cpu_to_push(this_rq);
                return;
        }
#endif

        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;

오버로드된 런큐들에 대해 현재 런큐에서 진행하려고 하는 우선 순위 태스크보다 더 높은 우선 순위 태스크가 있으면 끌어온다. 단 RT_PUSH_IPI feature(디폴트 enable)를 사용 중인 경우 오버로드된 런큐의 cpu로 IPI 호출하여 직접 push 하도록 한다.

• 코드 라인 7~10에서 요청한 런큐의 도메인내에서 오버로드가 없는 경우 함수를 빠져나간다.
• 코드 라인 19~21에서 오버로드돤 태스크가 1개 이고 현재 cpu인 경우 pull할 필요 없으므로 함수를 빠져나간다.
• 코드 라인 23~28에서 RT_PUSH_IPI feature를 사용하는 경우 오버로드된 런큐의 cpu로 IPI 호출하여 해당 cpu 스스로 직접  push 하도록 한다.
• 코드 라인 30~32에서 오버로드된 cpu를 순회하며 현재 (요청한 cpu)인 경우 skip 한다.
• 코드 라인 34에서 순회하는 cpu에 해당하는 런큐를 알아온다.
• 코드 라인 43~45에서 순회중인 cpu에 대한 최상위 rt 런큐의 차순위보다 요청한 런큐의 우선순위가 더 높거나 같은 경우 skip 한다.
  • 참고: sched: use highest_prio.next to optimize pull operations

 

kernel/sched/rt.c -2/2-

                /*
                 * 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);

                /*
                 * 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;

                        resched = true;

                        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);
        }

        if (resched)
                resched_curr(this_rq);
}

• 코드 라인 6에서 두 개의 런큐에 대해 안전하게 double 락을 건다.
• 코드 라인 12에서 pushable tasks 리스트에 연결된 태스크를 순회하며 active 되지 않은 첫 태스크를 알아온다. (높은 우선 순위 -> 낮은 우선 순위로 순회)
• 코드 라인 18~30에서 얻어온 태스크의 우선 순위가 순회중인 cpu의 최상위 rt 런큐에서 현재 동작 중인 우선 순위보다 높은 경우 skip 한다.
  • 해당 런큐에서 곧 동작할 예정이므로 pull 하지 않는다.
• 코드 라인 32~36에서 순회 중인 cpu의 최상위 rt 런큐에서 얻어온 태스크를 비활성화한 후 현재 cpu로 다시 설정하고 요청한 런큐에 다시 태스크를 활성화시킨다. 함수를 빠져나갈때엔 리스케줄 요청을 위해 resched 플래그를 설정한다.
• 코드 라인 45~46에서 skip: 레이블이다. 두 개의 런큐에 대해 double 락을 해제한다.
• 코드 라인 49~50에서 resched 플래그가 설정된 경우 리스케줄 요청을 수행한다.

 

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

 

---

구조체

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;
        unsigned short                  on_rq;
        unsigned short                  on_list;

        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
} __randomize_layout;

• run_list
  • 100개의 큐리스트 중 하나에 엔큐될 때 사용하는 엔트리 노드이다.
• timeout
  • 태스크에 설정된 실행 제한시간
• watchdog_stamp
  • 마지막에 갱신한 watchdog 시각
• time_slice
  • 라운드 로빈용 rt 타임 슬라이스로 100ms에 해당하는 tick 수
  • 1개의 우선 순위 리스트큐 내의 rt 태스크들이 라운드로빈 처리 시 이 기간 이내에 라운드로빈 하지 않도록 제한한다.
  • 라운드 로빈 한 번 할 때마다 리필된다.
• on_rq
  • rt 엔티티가 런큐에 엔큐된 상태를 나타낸다. (1=엔큐된 상태)
• on_list
  • rt 엔티티가 rt 런큐 리스트 자료 구조에 연결된 상태를 나타낸다. (1=리스트에 등록된 상태)
•  *back
  • rt 엔티티를 rt 런큐에 엔큐 및 디큐할 떄 bottom-up으로 올라간 경로대로 다시 내려갈 때 사용할 목적으로 잠시 사용한다.
• *parent
  • 그룹 스케줄링을 사용하지 않는 경우 null
  • 그룹 스케줄링을 사용할 때 부모 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_runtime_lock
  • 스핀락
•  rt_period
  • rt period (ns)
  • 글로벌 rt period 및 태스크 그룹의 rt period에서 디폴트 값은 1초이다.
• rt_runtime
  • rt 런타임 (ns)
  • 글로벌 rt 런타임 및 루트 태스크 그룹의 디폴트 값은 0.95초, 하위 태스크 그룹의 경우 디폴트 값은 0이다.
• 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;
        unsigned int            rr_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 /* CONFIG_SMP */
        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 태스크의 수
• rr_nr_running
  • rt 런큐 이하 계층 구조의 child 그룹들 모두에서 동작중인 round robin policy를 사용하는 rt 태스크의 수
• highest_prio.curr
  • 현재 동작중인 RT 태스크의 최고 우선 순위
• highest_prio.next
  • 다음에 동작할 RT 태스크의 우선 순위
  • 2 개의 태스크가 둘 다 최고 우선 순위를 가지는 경우 curr와 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
  • 오버로드된 태스크들를 push 하기 위해 리스트에 높은 우선 순위부터 정렬된다. (for push operation)
  • SMP 시스템에서 우선 순위가 낮은 cpu에서 이 리스트에 접근하여 끌어갈 수 있다. (for pull operation)
  • sched: create “pushable_tasks” list to limit pushing to one attempt
• rt_queued
  • rt 런큐가 이미 런큐에 엔큐된 경우 1
•  rt_throttled
  • 스로틀된 경우 1
  • sched: rt time limit
• rt_time
  • RT 태스크가 사용한 런타임이 누적된다.
  • 아래 로컬 풀(rt_runtime)에 할당된 런타임을 초과하는 경우 스로틀한다.
• rt_runtime
  • rt 로컬 풀에 할당된 런타임
    • RT_RUNTIME_SHARE 기능을 사용 유무에 따라
      • 사용하지 않을 때에는 매 period마다 태스크 그룹에 설정된 rt 런타임이 사용된다.
      • 사용할 경우에는 각 cpu들은 처음 태스크 그룹에 설정된 rt 런타임을 사용하고, 다른 cpu의 rt 런타임을 빌려 주고 받는다. 즉 런타임이 더 필요한 곳으로 다른 cpu들의 런타임을 몰아줄 수도 있다.
•  rt_nr_boosted
  • Priority Inversion 문제를 해결하기 위해 사용한다.
    • 참고: sched: rt-group: deal with PI
• *rq
  • 런큐를 가리킨다.
• *tg
  • cgroup에서 그룹 스케줄링을 사용하는 경우 태스크 그룹을 가리킨다.

 

참고

• Scheduler -1- (Basic) | 문c
• Scheduler -2- (Global Cpu Load) | 문c
• Scheduler -3- (PELT) | 문c
• Scheduler -4- (Group Scheduling) | 문c
• Scheduler -5- (Scheduler Core) | 문c
• Scheduler -6- (CFS Scheduler) | 문c
• Scheduler -7- (Preemption & Context Switch) | 문c
• Scheduler -8- (CFS Bandwidth) | 문c
• Scheduler -9- (RT Scheduler) | 문c – 현재 글
• Scheduler -10- (Deadline Scheduler) | 문c
• Scheduler -11- (Stop Scheduler) | 문c
• Scheduler -12- (Idle Scheduler) | 문c
• Scheduler -13- (Scheduling Domain 1) | 문c
• Scheduler -14- (Scheduling Domain 2) | 문c
• Scheduler -15- (Load Balance 1) | 문c
• Scheduler -16- (Load Balance 2) | 문c
• Scheduler -17- (Load Balance 3 NUMA) | 문c
• Scheduler -18- (Load Balance 4 EAS) | 문c
• Scheduler -19- (초기화) | 문c
• PID 관리 | 문c
• do_fork() | 문c
• cpu_startup_entry() | 문c
• 런큐 로드 평균(cpu_load[]) – v4.0 | 문c
• PELT(Per-Entity Load Tracking) – v4.0 | 문c

 

•  Real-Time group scheduling | kernel.org