Schedutil Governor (1): 언제 Frequency Transition을 하는가?

마지막으로 내가 리눅스의 CPUFreq governor를 볼 당시에는 Ondemand governor와 이의 변형인 Interactive governor가 많이 쓰이고 있었다. 그 후 Schedutil governor가 등장하여 이들을 대체하였는데, 최근에서야 관련 코드를 분석할 기회가 생겨 이 포스트에서 정리하고 넘어가려 한다.

 

Ondemand governor에 비교하여 Schedutil governor는 크게 두 가지 측면이 개선되었다.

1. 더 이상 kernel timer를 사용하여 주기적으로 frequency transition을 하지 않고, scheduler가 frequency transition 시점을 결정할 전권을 가진다.
2. Utilization이 아닌 load average 값에 기반하여 다음 frequency를 결정한다.

첫 번째 변화는 리눅스 관련 커뮤니티들에서 몇 년 전부터 주구장창 외치던 "Energy-aware Scheduling"을 위한 첫걸음으로 보인다. 2013년 CFS(Completely Fair Scheduler)의 개발자인 Ingo Molnar는 CPUFreq governor가 스케줄러와는 전혀 상관없이 kernel timer에 의해 동작하는 것에 불만을 표출한 적이 있다. 이에 따라 여러 개발자들이 스케줄러와 CPUFreq governor를 어떻게 통합할 것인지에 대해 고민을 하기 시작했다. 이번에 리눅스 커널 코드를 읽어보니 이 문제를 해결하기 위해 스케줄러가 CPUFreq governor에게 frequency transition을 요청할 수 있는 인터페이스가 추가된 것을 확인할 수 있었다.

 

Linux kernel v5.1을 기준으로 코드를 한번 살펴보자.

 

이 인터페이스의 핵심은 cpufreq_update_util() 함수이다. CPU 스케줄러는 frequency transition을 요청하고 싶을 때 이 함수를 호출한다. 그러면 CPUFreq governor가  다음 frequency를 계산하고 transition을 수행하게 된다.

 

그러면 CPU 스케줄러가 언제 cpufreq_update_util()을 호출하는지 확인해보자. 각각의 scheduling class(SCHED_NORMAL, SCHED_FIFO, SCHED_RR, SCHED_DEADLINE)마다 cpufreq_update_util() 호출 정책이 다른데, 우리는 이 중 SCHED_NORMAL, 즉 CFS의 경우만 자세히 살펴보도록 한다. CFS는 다음 두 조건 중 하나가 만족했을 때 cpufreq_update_util()을 호출한다.

1. Task가 run queue에 enqueue될 때
2. Run queue의 load average가 변할 때

/* kernel/sched/fair.c */
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    update_curr(cfs_rq);
    update_load_avg(cfs_rq, curr, UPDATE_TG);
    // ...
}

/* kernel/sched/fair.c */
static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // ...
    update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
    // ...
}

CFS는 각 run queue의 load average를 업데이트하고 필요할 경우 frequency transition을 요청하기 위해 update_load_avg() 함수를 호출한다. 이 함수를 호출하는 대표적인 두 함수는 entity_tick()과 enqueue_entity()이다. entity_tick()은 scheduler tick마다 호출되는 함수로, load average를 update하기 위해 UPDATE_TG flag를 파라미터로 가지고 update_load_avg()를 호출한다(line 6). 반면 enqueue_entity()는 task가 run queue에 enqueue될 때 호출되는 함수로, UPDATE_TG flag 뿐만이 아니라 해당 task를 run queue의 load average 계산에 사용하기 위한 DO_ATTACH flag도 같이 파라미터로 가지고 update_load_avg()를 호출하게 된다(line 15).

/* kernel/sched/fair.c */
static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // ...
    decayed  = update_cfs_rq_load_avg(now, cfs_rq);
    // ...
    if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
        attach_entity_load_avg(cfs_rq, se, SCHED_CPUFREQ_MIGRATION);
        // ...
    }
    // ...
}

/* kernel/sched/fair.c */
static inline int
update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
{
    // Update load_avg and check if it is decayed
    
    if (decayed)
        cfs_rq_util_change(cfs_rq, 0);
    
    return decayed;
}

/* kernel/sched/fair.c */
static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // ...
    cfs_rq_util_change(cfs_rq, flags);
}

/* kernel/sched/fair.c */
static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq, int flags)
{
    struct rq *rq = rq_of(cfs_rq);
    
    if (&rq->cfs == cfs_rq || (flags & SCHED_CPUFREQ_MIGRATION)) {
        cpufreq_update_util(rq, flags);
    }
}

update_load_avg() 함수는 (1) 현재 run queue에 들어 있는 task들로부터 load average 값을 계산하기 위해 update_cfs_rq_load_avg() 함수를 호출하고(line 5), (2) run queue에 task가 enqueue되는 경우(DO_ATTACH), 이 task로 인한 load average의 변화를 계산하기 위해 attach_entity_load_avg() 함수를 추가로 호출한다(line 8). update_cfs_rq_load_avg()는 만약 run queue의 load average가 decay되었다면 cfs_rq_util_change() 함수를 호출한다(line 21). 반면 attach_entity_load_avg() 함수의 경우 무조건 cfs_rq_util_change() 함수를 호출한다(line 30). 그리고 cfs_rq_util_change() 함수는 아까 언급했던 frequency transition을 수행하는 cpufreq_update_util() 함수를 호출한다(line 39).

 

지금까지의 코드 분석을 정리하면 다음과 같다.

• CFS는 scheduler tick과 run queue에 task가 삽입되는 시점에 load average를 갱신한다.
• Load average 갱신을 했을 때 그 값이 decay되었으면 frequency transition을 위해 cpufreq_update_util()을 호출한다.
• 만약 run queue에 task가 삽입되어 load average를 갱신하는 상황이면 무조건 frequency transition을 위해 cpufreq_update_util()을 호출한다.

 

다시 cpufreq_update_util() 함수로 돌아가서, 이 함수의 내부가 어떻게 구성되었는지 확인하고 이번 글을 마무리하겠다.

/* kernel/sched/sched.h */
static inline void cpufreq_update_util(struct rq *rq, unsigned int flags)
{
    struct update_util_data *data;

    data = rcu_dereference_sched(*per_cpu_ptr(&cpufreq_update_util_data,
                          cpu_of(rq)));
    if (data)
        data->func(data, rq_clock(rq), flags);
}

cpufreq_update_util()은 (1) 다음 frequency를 계산하고, (2) 해당 frequency로의 transition을 CPUFreq driver에게 요청한다. 이를 실질적으로 수행하는 함수는 update_util_data 구조체에 저장된 func라는 function pointer가 가리키는 함수이다(line 9). Schedutil의 경우 이 함수는 sugov_update_shared()나 sugov_update_single()을 가리키고 있다.

/* kernel/sched/cpufreq_schedutil.c */
static int sugov_start(struct cpufreq_policy *policy)
{
    // ...
    cpufreq_add_update_util_hook(cpu, &sg_cpu->update_util,
                         policy_is_shared(policy) ?
                            sugov_update_shared :
                            sugov_update_single);
    // ...
}

/* kernel/sched/cpufreq.c */
void cpufreq_add_update_util_hook(int cpu, struct update_util_data *data,
            void (*func)(struct update_util_data *data, u64 time,
                     unsigned int flags))
{
    // ...
    data->func = func;
    // ...
}

위의 코드는 Schedutil이 처음 초기화 될 때 sugov_update_shared()나 sugov_update_single()을 등록하는 과정을 보여준다. CPUFreq governor가 초기화 될 때는 항상 cpufreq_start_governor() 함수가 호출되고, Schedutil governor의 경우 이에 따라 line 1의 sugov_start() 함수가 호출된다. 이 함수의 주요 동작 중 하나는 update_util_data 구조체의 func() 함수를 등록하는 것이다(line 18). CPU 코어들이 정책을 공유하면 sugov_update_shared() 함수를 등록하고(line 7), 아닐 경우 sugov_update_single() 함수를 등록한다(line 8).

/* kernel/sched/cpufreq_schedutil.c */
static void
sugov_update_single(struct update_util_data *hook, u64 time, unsigned int flags)
{
    // ...
    next_f = get_next_freq(sg_policy, util, max);
    // ...
    if (sg_policy->policy->fast_switch_enabled) {
        sugov_fast_switch(sg_policy, time, next_f);
    } else {
        raw_spin_lock(&sg_policy->update_lock);
        sugov_deferred_update(sg_policy, time, next_f);
        raw_spin_unlock(&sg_policy->update_lock);
    }
}

sugov_update_shared()와 sugov_update_single()의 동작은 유사하기 때문에 sugov_update_single()만 조금 더 뜯어보자. 이 함수 내부에서는 다음 frequency를 계산하는 get_next_freq() 함수가 호출되고, 그 결과를 next_f에 저장한다(line 6). 그 이후 next_f로의 frequency transition이 일어난다(line 8-14). Frequency transition의 방법에는 (1) interrupt context에서 일어나는 fast switch 방식(line 9)과 (2) kernel thread 상에서 일어나는 deferred update 방식(line 12)이 있는데, 자세한 내용은 추후 다른 글에서 다루도록 하겠다.

 

이번 글에서는 Schedutil governor에서 frequency transition 시점에 어떻게 결정되는지에 대해 알아보았다. 다음 글에서는 load average가 무엇이고, Schedutil governor는 이 값을 어떻게 이용해서 frequency를 결정하는지를 소개하도록 하겠다.