Scheduler -6- (CFS Scheduler)

 

CFS – Time Slice

sched_slice()

kernel/sched/fair.c

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

        for_each_sched_entity(se) {
                struct load_weight *load;
                struct load_weight lw;

                cfs_rq = cfs_rq_of(se);
                load = &cfs_rq->load;

                if (unlikely(!se->on_rq)) {
                        lw = cfs_rq->load;

                        update_load_add(&lw, se->load.weight);
                        load = &lw;
                }
                slice = __calc_delta(slice, se->load.weight, load);
        }
        return slice;
}

최상위 스케줄 엔티티의 루트까지 연결된 경우 루프를 돌며 스케줄 엔티티 cfs 런큐의 load에 스케줄 엔티티 로드를 추가한다.

  • 코드 라인 9에서 cfs 런큐에서 동작 중인 태스크들 + 1(스케줄 엔티티가 런큐에 있지 않은 경우에 한하여)의 개수로 스케줄링 latency를 구해 slice에 대입한다.
  • 코드 라인 11에서 스케줄 엔티티의 루트까지 루프를 돈다.
    • 태스크 그룹을 사용한 계층 구조인 경우 루트 태스크 그룹까지 로드를 갱신한다.
  • 코드 라인 15~16에서 요청한 스케줄 엔티티가 사용하는 cfs 런큐에서 load 값을 임시 변수 lw에 대입한다.
  • 코드 라인 18~23에서 낮은 확률로 요청한 엔티티가 아직 런큐에 없는 경우 이 스케줄링 엔티티의 load.weight 값을 임시 변수 lw를 가리키는 load에 cfs 런큐의 로드에 추가한다.
  • 코드 라인 24에서 이 엔티티에 대한 time slice를 구해온다.
  • 코드 라인 26에서 최종 slice 값을 반환한다.

 

다음 그림은 하나의 스케줄 엔티티에 대한 time slice를 산출하는 과정을 보여준다.

  • 런큐에 5개 스케줄 엔티티의 load weight가  더해있고 아직 런큐에 올라가지 않은 스케줄 엔티티를 더해서 time slice를 산출한다.

 

__sched_period()

kernel/sched/fair.c

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
        u64 period = sysctl_sched_latency;
        unsigned long nr_latency = sched_nr_latency;

        if (unlikely(nr_running > nr_latency)) {
                period = sysctl_sched_min_granularity;
                period *= nr_running;
        }

        return period;
}

태스크 스케줄에 사용할 스케줄링 latency를 산출한다.

  • sched_latency 값(rpi2 default: 18000000ns)을 반환하되 동작 중인 태스크 수 nr_running이 nr_latency(rpi2 default: 8)보다 큰 경우 sched_min_granularity(rpi2 default: 2250000ns) * nr_running 값을 반환한다.
    • = (nr_running <= sched_nr_latency(8)) ? sysctl_sched_latency : sysctl_sched_min_granularity * nr_running

 

update_load_add()

kernel/sched/fair.c

static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
        lw->weight += inc;
        lw->inv_weight = 0;
}

로드 값을 inc 만큼 추가하고 inv_weight 값은 0으로 리셋한다.

 

__calc_delta()

kernel/sched/fair.c

/*
 * delta_exec * weight / lw.weight
 *   OR
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * Either weight := NICE_0_LOAD and lw \e prio_to_wmult[], in which case
 * we're guaranteed shift stays positive because inv_weight is guaranteed to
 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
 *
 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
 * weight/lw.weight <= 1, and therefore our shift will also be positive.
 */
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
        u64 fact = scale_load_down(weight);
        int shift = WMULT_SHIFT;

        __update_inv_weight(lw);

        if (unlikely(fact >> 32)) {
                while (fact >> 32) {
                        fact >>= 1;
                        shift--;
                }
        }

        /* hint to use a 32x32->64 mul */
        fact = (u64)(u32)fact * lw->inv_weight;

        while (fact >> 32) {
                fact >>= 1;
                shift--;
        }

        return mul_u64_u32_shr(delta_exec, fact, shift);
}

스케줄링 기간을 산출하여 반환한다. (delta_exec * weight / lw.weight)

  • 코드 라인 15에서 weight 값을 scale 로드 다운하여 fact에 대입한다. 32bit 아키텍처는 scale 로드 다운하지 않는다.
    • 커널 v4.7-rc1에서 64bit 아키텍처에 대해 weight에 대한 해상도를 높여서 사용할 수 있게 변경되었다.
  • 코드 라인 18에서 0xfff_ffff / lw->weight 값을 lw->inv_weight 값으로 대입한다.
  • 코드 라인 20~25에서 작은 확률로 fact가 32bit 값 이상인 경우 상위 32bit에서 사용하는 bit 수만큼을 기존 shift(32) 값에서 빼고 그 횟수만큼 fact를 우측 시프트한다.
    • 32bit 아키텍처는 fact 값이 32bit 값을 넘어가지 않아 이 루틴은 건너뛴다.
    • 예) 0x3f_ffff_ffff -> shift=32-6=26
  • 코드 라인 28에서 나눗셈을 피하기 위해 계산된 inv_wieght 값을 fact에 곱한다.
    • delta_exec * weight / lw.weight = (delta_exec * weight * lw.inv_weight) >> 32
  • 코드 라인 30~33에서 32bit 시프트 중 남은 시프트 수를 구한다. 또한 루프 반복 횟수 만큼 fact를 시프트한다.
  • 코드 라인 35에서 (delta_exec * fact) >> shift 한 값을 반환한다.
    • 결국: (delta_exec * weight * lw.inv_weight) >> 32와 같은 결과를 반환하게 된다.

 

kernel/sched/fair.c

#define WMULT_CONST     (~0U)
#define WMULT_SHIFT     32

 

다음 그림은 5개의 태스크가 스케줄되어 산출된 각각의 time slice 값을 알아본다.

  • 녹색 박스 수식은 나눗셈을 사용한 산출 방법이다. (수학 모델)
  • 적색 박스 수식은 더 빠른 처리를 위해 나눗셈 없이 곱셈과 시프트만 사용한 방법이다. (구현 모델)

 

__update_inv_weight()

kernel/sched/fair.c

static void __update_inv_weight(struct load_weight *lw)
{
        unsigned long w;

        if (likely(lw->inv_weight))
                return;

        w = scale_load_down(lw->weight);

        if (BITS_PER_LONG > 32 && unlikely(w >= WMULT_CONST))
                lw->inv_weight = 1;
        else if (unlikely(!w))
                lw->inv_weight = WMULT_CONST;
        else
                lw->inv_weight = WMULT_CONST / w;
}

0xfff_ffff / lw->weight 값을 lw->inv_weight 값으로 대입한다.

  • 산출된 inv_weight 값은 weight 값으로 나눗셈을 하는 대신 이 값으로 곱하기 위해 반전된 weight 값을 사용한다. 그 후 32bit 우측 쉬프트를 하여 사용한다.
  • ‘delta_exec / weight =’ 과 같이 나눗셈이 필요 할 때 나눗셈 대신 ‘delta_exec * wmult >> 32를 사용하는 방법이 있다.
    • wmult 값을 만들기 위해 ‘2^32 / weight’ 값을 사용한다.

 

  • 코드 5~6에서 이미 lw->inv_weight 값이 설정된 경우 함수를 빠져나간다.
  • 코드 8에서 arm 아키텍처는 sched_load 비율을 적용하지 않으므로 그대로 lw->weight 값을 사용한다.
  • 코드 10~15에서 w 값에 따라서 lw->inv_weight 값을 다음 중 하나로 갱신한다.
    • 시스템이 64비트이고 낮은 확률로 w 값이 32bit 값을 넘어선 경우 1
    • 낮은 확률로 w 값이 0인 경우 0xffff_ffff
    • 그 외의 경우 0xffff_ffff / weight

 

mul_u64_u32_shr()

include/linux/math64.h

#if defined(CONFIG_ARCH_SUPPORTS_INT128) && defined(__SIZEOF_INT128__)
#ifndef mul_u64_u32_shr
static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
{
        return (u64)(((unsigned __int128)a * mul) >> shift);
}
#endif /* mul_u64_u32_shr */
#else   
#ifndef mul_u64_u32_shr
static inline u64 mul_u64_u32_shr(u64 a, u32 mul, unsigned int shift)
{
        u32 ah, al;
        u64 ret;

        al = a;
        ah = a >> 32;

        ret = ((u64)al * mul) >> shift;
        if (ah)
                ret += ((u64)ah * mul) << (32 - shift);

        return ret;
}
#endif /* mul_u64_u32_shr */
#endif  

a * mul >> shift 결과를 반환한다.

  • 계산의 중간에 a * mul 연산에서 128비트를 사용하는데 아키텍처가 128비트 정수 연산을 지원하는 경우와 그렇지 않은 경우에 대해 함수가 구분되어 있다.

 

스케줄링 latency 와 스케일 정책

sched_proc_update_handler()

kernel/sched/fair.c

int sched_proc_update_handler(struct ctl_table *table, int write,
                void __user *buffer, size_t *lenp,
                loff_t *ppos)
{
        int ret = proc_dointvec_minmax(table, write, buffer, lenp, ppos);
        int factor = get_update_sysctl_factor();

        if (ret || !write)
                return ret;

        sched_nr_latency = DIV_ROUND_UP(sysctl_sched_latency,
                                        sysctl_sched_min_granularity);

#define WRT_SYSCTL(name) \
        (normalized_sysctl_##name = sysctl_##name / (factor))
        WRT_SYSCTL(sched_min_granularity);
        WRT_SYSCTL(sched_latency);
        WRT_SYSCTL(sched_wakeup_granularity);
#undef WRT_SYSCTL

        return 0;
}

다음 4 가지 중 하나의 스케줄링 옵션을 바꾸게될 때 호출되어 CFS 스케줄러의 스케줄링 latency 산출에 영향을 준다.

  • “/proc/sys/kernel/sched_min_granularity_ns”
    • min: 100000, max: 1000000000 (range: 100us ~ 1s)
  • “/proc/sys/kernel/sched_latency_ns”
    • min: 100000, max: 1000000000 (range: 100us ~ 1s)
  • “/proc/sys/kernel/sched_wakeup_granularity_ns”
    • min: 0, max: 1000000000 (range: 0 ~ 1s)
  • “/proc/sys/kernel/sched_tunable_scaling”
    • min:0, max: 2 (range: 0 ~ 2)

 

  • 코드 라인 5에서 kern_table[] 배열에서 해당 항목의 min/max에 적용된 범위 이내에서 관련 proc 파일 값을 읽는다.
  • 코드 라인 6~9에서 스케줄링 latency에 반영할 factor 값을 산출해온다. 만일 실패하는 경우 함수를 빠져나간다.
  • 코드 라인 11~12에서 스케줄링 latency 값을 태스크 최소 스케줄 단위로 나누면 스케쥴 latency 값으로 적용할 수 있는 최대 태스크의 수가 산출된다.
  • 코드 라인 14~15에서 WRT_SYSCTL() 매크로를 정의한다.
  • 코드 라인 16에서 normalized_sysctl_sched_min_granularity <- sysctl_sched_min_granularity / factor 값을 대입한다.
  • 코드 라인 17에서 normalized_sysctl_sched_latency <- sysctl_sched_latency / factor 값을 대입한다.
  • 코드 라인 18에서 normalized_sysctl_sched_wakeup_granularity <- sysctl_sched_wakeup_granularity / factor 값을 대입한다.

 

get_update_sysctl_factor()

kernel/sched/fair.c

/*
 * Increase the granularity value when there are more CPUs,
 * because with more CPUs the 'effective latency' as visible
 * to users decreases. But the relationship is not linear,
 * so pick a second-best guess by going with the log2 of the
 * number of CPUs.
 *
 * This idea comes from the SD scheduler of Con Kolivas:
 */
static int get_update_sysctl_factor(void)
{
        unsigned int cpus = min_t(int, num_online_cpus(), 8);
        unsigned int factor;

        switch (sysctl_sched_tunable_scaling) {
        case SCHED_TUNABLESCALING_NONE:
                factor = 1;
                break;
        case SCHED_TUNABLESCALING_LINEAR:
                factor = cpus;
                break;
        case SCHED_TUNABLESCALING_LOG:
        default:
                factor = 1 + ilog2(cpus);
                break;
        }

        return factor;
}

스케일링 정책에 따른 비율을 반환한다.  이 값은 사용하는 정책에 따라 cpu 수에 따른 스케일 latency에 변화를 주게된다.

  • “/proc/sys/kernel/sched_tunable_scaling” 을 사용하여 스케일링 정책을 바꿀 수 있다.
    • SCHED_TUNABLESCALING_NONE(0)
      • 항상 1을 사용한다.
    • SCHED_TUNABLESCALING_LOG(1)
      • 1 + ilog2(cpus)과 같이 cpu 수에 따라 변화된다.
      • rpi2: cpu=4개이고 이 옵션을 사용하므로 factor=3가 된다.
    • SCHED_TUNABLESCALING_LINEAR(2)
      • online cpu 수로 8 단위로 정렬하여 사용한다. (8, 16, 24, 32, …)

 

update_sysctl()

kernel/sched/fair.c

static void update_sysctl(void)
{
        unsigned int factor = get_update_sysctl_factor();

#define SET_SYSCTL(name) \
        (sysctl_##name = (factor) * normalized_sysctl_##name)
        SET_SYSCTL(sched_min_granularity);
        SET_SYSCTL(sched_latency);
        SET_SYSCTL(sched_wakeup_granularity);
#undef SET_SYSCTL
}

스케줄 도메인의 초기화 또는 구성이 바뀌는 경우와 cpu가 on/off 될 때에 한하여 다음 3가지의 값을 갱신한다.

  • sysctl_sched_min_granularity = factor * normalized_sysctl_sched_min_granularity
  • sysctl_sched_latency = factor * normalized_sysctl_sched_latency
  • sysctl_sched_wakeup_granularity = factor * normalized_sysctl_sched_wakeup_granularity

 

vruntime 산출

sched_vslice()

kernel/sched/fair.c

/*
 * We calculate the vruntime slice of a to-be-inserted task.
 *
 * vs = s/w
 */
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

스케줄 엔티티의 로드에 해당하는 time slice 값을 산출하고 이를 통해 vruntime 을 구한다.

  • sched_slice() 함수를 통해 스케줄 엔티티의 로드에 해당하는 기간인 time slice를 구한다.
    • 예) rpi2: 스케줄 기간 18ms에서 6개의 태스크 중 현재 태스크가 로드 weight으로 기여한 시간이 3ms라고 할 때
  • 그런 후 calc_delta_fair() 함수를 통해 스케줄 엔티티의 로드 weight과 반비례한 time slice 값을 반환한다.
    • 예) 2개의 태스크에 대해 각각 1024, 3072의 로드 weight이 주어졌을 때
      • 6ms의 스케줄 주기를 사용한 경우 각각의 로드 weight에 따라  1.5ms와 4.5ms의 time slice를 할당받는다.
      • 이 기간으로 calc_delta_fair() 함수를 통한 경우 각각 ‘1.5ms * (1024/1024)’ , ‘4.5ms * (1024/3072)=1.5ms’ 수식으로 동일하게 1.5ms의 시간이 산출된다.
      • 산출된 이 값을 기존 vruntime에 누적하여 사용한다.

 

댜음 그림은 4개의 태스크에 대해 vruntime 값이 누적되는 모습을 보여준다.

  • high-resolution timer를 사용한 HRTICK인 경우 아래 그림과 같이 태스크별 할당 시간을 다 소모한 후 preemption 한다. 그러나 hrtick을 사용하지 않는 경우 매 정규 틱마다   태스크별 할당 시간과 vruntime을 비교하여 스케줄링된다. 그러한 경우 태스크는 자신의 할당 시간을 다 소모하지 못하고 중간에 vruntime이 더 작은 대기중인 태스크에게 선점될 수 있다.
  • 아래 vruntime 값은 실제와는 다른 임의의 값으로 실전에서 아래와 같은 수치를 만들기는 어렵다.
  • RB 트리에 엔큐된 스케줄링 엔티티들은 vruntime 값이 가장 작은 RB 트리의 가장 좌측부터 vruntime 값이 가장 큰 가장 우측 스케줄 엔티티까지의 vruntime 범위가 아래와 같이 산출된 vruntime 값 범위 이내로 모여드는 특성을 가지고 있다. 아래 그림과 같이 Task A와 Task B의 경우와 같이 Task D가 한 번 수행되는 것에 반해 두 번 수행하게 되는 상황을 볼 수 있다. 이렇게 vruntime 값이 적으면 선점할 기회를 더 갖게되는데 일정 수준에 도달하면 모든 태스크가 같은 기회를 얻게된다.

 

calc_delta_fair()

kernel/sched/fair.c

/*
 * delta /= w
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
        if (unlikely(se->load.weight != NICE_0_LOAD))
                delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

        return delta;
}

time slice 값에 해당하는 vruntime 값을 산출한다.

  • vruntime = time slice * wieght-0 / weight

 

CFS 스케줄러 틱

다음 그림과 같이 고정 스케줄 틱과 high-resoultion timer를 사용한 스케줄 틱을 지원하는 경우 cfs 스케줄러의 틱을 처리하는 흐름을 보여준다.

 

task_tick_fair()

kernel/sched/fair.c

/*
 * scheduler tick hitting a task of our scheduling class:
 */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
        struct cfs_rq *cfs_rq;
        struct sched_entity *se = &curr->se;

        for_each_sched_entity(se) {
                cfs_rq = cfs_rq_of(se);
                entity_tick(cfs_rq, se, queued);
        }

        if (numabalancing_enabled)
                task_tick_numa(rq, curr);

        update_rq_runnable_avg(rq, 1);
}

CFS 스케줄러 틱 호출 시마다 수행해야 할 일을 처리한다.

  • 코드 9~12에서 요청 태스크의 스케줄링 엔티티들 각각에서 할 일을 수행한다.
    • 실행 시간 갱신. 만료 시 리스케줄 요청 처리
    • 엔티티 로드 평균 갱신
    • 블럭드 로드 갱신
    • 태스크 그룹의 shares 갱신
    • preemption 요청이 필요한 경우를 체크하여 설정
  • 코드 14~15에서 numa 밸런싱이 enable된 경우 numa 밸런싱을 수행한다.
  • 코드  17에서 런큐의 러너블 로드 평균을 갱신한다.

 

entity_tick()

kernel/sched/fair.c

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
        /*
         * Update run-time statistics of the 'current'.
         */
        update_curr(cfs_rq);

        /*
         * Ensure that runnable average is periodically updated.
         */
        update_entity_load_avg(curr, 1);
        update_cfs_rq_blocked_load(cfs_rq, 1);
        update_cfs_shares(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK
        /*
         * queued ticks are scheduled to match the slice, so don't bother
         * validating it and just reschedule.
         */
        if (queued) {
                resched_curr(rq_of(cfs_rq));
                return;
        }
        /*
         * don't let the period tick interfere with the hrtick preemption
         */
        if (!sched_feat(DOUBLE_TICK) &&
                        hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
                return;
#endif

        if (cfs_rq->nr_running > 1)
                check_preempt_tick(cfs_rq, curr);
}

CFS 스케줄러의 스케줄 엔티티 틱 호출 시 다음과 같이 할 일을 수행한다.

  • 코드 라인 7에서 현재 스케줄 엔티티의 실행 시간에 대한 업데이트를 수행한다. 이미 실행 시간이 다 소모된 경우에는 다음 태스크를 스케줄 하도록 리스케줄 요청을 한다.
  • 코드 라인 12에서 1틱에 대한 엔티티 로드 평균을 산출하여 갱신한다.
  • 코드 라인 13에서 1틱에 대한 런큐 블럭드 로드를 산출하여 갱신한다.
  • 코드 라인 14에서 태스크 그룹별 shares 값을 갱신한다.
  • 코드 라인 16~24에서 스케줄러용 hrtick을 지원하고 인수로 queue 요청이 있으면 리스케줄 요청 플래그를 설정하고 함수를 빠져나간다.
  • 코드 라인 28~30에서 더블 틱 기능을 사용하지 않고 스케줄러용 hrtick을 지원하면 높은 우선 순위의 태스크가 preemption 요청 시마다 곧바로 리스케줄한다. 따라서 고정 tick 마다 호출되는 이루틴에서 preemption 상황이 필요한지에 대한 체크를 수행할 필요가 없어 함수를 빠져나간다.
    • High-res 타이머를 사용하는 경우 런큐가 사용하는 hrtimer가 동작중인 경우 즉, 아직 태스크에 배정된 런타임이 있음을 의미한다.
  • 코드 라인 33~34에서 cfs 런큐에 2 개 이상의 태스크가 동작하는 경우 preemption이 필요한지를 체크한다. 필요시 리스케줄 요청 플래그가 설정된다.
    • 현재 태스크의 vruntime과 다음 cfs 런큐에서 대기중인 첫 태스크의 vruntime과 비교하여 첫 태스크의  vruntime이 더 적어진 경우 리스케줄 요청 플래그를 설정한다.

 

현재 태스크의 런타임 통계들 갱신(만료 시간 포함)

update_curr()

kernel/sched/fair.c

/*
 * Update the current task's runtime statistics.
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
        struct sched_entity *curr = cfs_rq->curr;
        u64 now = rq_clock_task(rq_of(cfs_rq));
        u64 delta_exec;

        if (unlikely(!curr))
                return;

        delta_exec = now - curr->exec_start;
        if (unlikely((s64)delta_exec <= 0))
                return;

        curr->exec_start = now;

        schedstat_set(curr->statistics.exec_max,
                      max(delta_exec, curr->statistics.exec_max));

        curr->sum_exec_runtime += delta_exec;
        schedstat_add(cfs_rq, exec_clock, delta_exec);

        curr->vruntime += calc_delta_fair(delta_exec, curr);
        update_min_vruntime(cfs_rq);

        if (entity_is_task(curr)) {
                struct task_struct *curtask = task_of(curr);

                trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
                cpuacct_charge(curtask, delta_exec);
                account_group_exec_runtime(curtask, delta_exec);
        }

        account_cfs_rq_runtime(cfs_rq, delta_exec);
}

현재 태스크의 런타임 통계들을 갱신한다. 현재 태스크의 실행 시간을 다 소모하였으면 리스케줄 요청한다.

  • 코드 라인 6~11에서 cfs 런큐에 현재 돌고 있던 태스크가 없었으면 지나간 태스크의 스케줄링 엔티티에 대해 시간을 갱신할 필요가 없으므로 함수를 빠져나간다.
  • 코드 라인 13~15에서 기존 시작  실행 시각에서 현재 시각을 뺀 시간을 delta_exec에 대입하고 혹시 0 이하인 경우 함수를 빠져나간다.
  • 코드 라인 17에서 cfs 런큐의 현재 스케줄 엔티티의 시작 실행 시작을 현재 시각으로 갱신한다.
  • 코드 라인 22에서 실행된 런타임 시간 합을 갱신한다.
  • 코드 라인 25에서 실행된 delta 기간에서 현재 스케줄링 엔티티의 로드 비율 만큼의 vruntime 값을 구해 현재 스케줄링 엔티티의 vruntime 값에 추가한다.
    • curr->vruntime += delta_exec * wieght-0 / curr->load.weight
  • 코드 라인 26에서 cfs 런큐의 min_vruntime 값을 갱신한다. 현재 태스크와 첫 번째 대기 중인 태스크 둘 중 작은 vruntime 값을 cfs 런큐의 min_vruntime 값보다 큰 경우에만 갱신한다.
  • 코드 라인 28~34에서 현재 스케줄링 엔티티가 태스크인 경우 실행된 delta 시간을 cpuusage와 cputimer 통계에 추가하여 갱신하게 한다.
  • 코드 라인 36에서 cfs 런큐의 runtime_remaining에 실행된 delta 기간을 뺀 값을 갱신하고 이 값이 0 이하이면 현재 태스크의 실행 시간을 다 소모하였으므로 다음 태스크로 리스케줄 요청 플래그를 설정한다.

 

 

update_min_vruntime()

kernel/sched/fair.c

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
        u64 vruntime = cfs_rq->min_vruntime;

        if (cfs_rq->curr)
                vruntime = cfs_rq->curr->vruntime;

        if (cfs_rq->rb_leftmost) {
                struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
                                                   struct sched_entity,
                                                   run_node);

                if (!cfs_rq->curr)
                        vruntime = se->vruntime;
                else
                        vruntime = min_vruntime(vruntime, se->vruntime);
        }

        /* ensure we never gain time by being placed backwards. */
        cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
        smp_wmb();
        cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

cfs 런큐의 min_vruntime 값을 갱신한다. 현재 태스크와 첫 번째 대기 중인 태스크 둘 중 작은 vruntime 값을 cfs 런큐의 min_vruntime 값보다 큰 경우에만 갱신한다.

  • 코드 라인 3~6에서 cfs 런큐의 min_vruntime 값을 가져오되 cfs 런큐에 스케줄링 엔티티가 있으면 그 스케줄링 엔티티의 vruntime 값을 사용한다.
  • 코드 라인 8~17에서 cfs 런큐에서 대기중인 스케줄링 엔티티가 있는 경우 가장 먼저 실행될 스케줄링 엔티티의 vruntime과 비교하여 가장 작은 것을 산출한다.
  • 코드 라인 20에서 위에서 산출된 가장 작은 vruntime 값이 cfs 런큐의 min_vruntime 값보다 큰 경우에만 갱신한다.
    • cfs 런큐의 min_vruntime을 새로운 min_vruntime으로 갱신하는데 새로 갱신하는 값은 기존 보다 더 큰 값이 된다.
  • 코드 라인 21~24에서 32bit 시스템인 경우에만 min_vruntime을 min_vruntime_copy에도 복사한다.

 

다음 그림은 update_min_vruntime()에 대한 동작을 보여준다.

 

주기적 태스크 preemption 체크

check_preempt_tick()

kernel/sched/fair.c

/*
 * Preempt the current task with a newly woken task if needed:
 */
static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
        unsigned long ideal_runtime, delta_exec;
        struct sched_entity *se;
        s64 delta;

        ideal_runtime = sched_slice(cfs_rq, curr);
        delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
        if (delta_exec > ideal_runtime) {
                resched_curr(rq_of(cfs_rq));
                /*
                 * The current task ran long enough, ensure it doesn't get
                 * re-elected due to buddy favours.
                 */
                clear_buddies(cfs_rq, curr);
                return;
        }

        /*
         * Ensure that a task that missed wakeup preemption by a
         * narrow margin doesn't have to wait for a full slice.
         * This also mitigates buddy induced latencies under load.
         */
        if (delta_exec < sysctl_sched_min_granularity)
                return;

        se = __pick_first_entity(cfs_rq);
        delta = curr->vruntime - se->vruntime;

        if (delta < 0)
                return;

        if (delta > ideal_runtime)
                resched_curr(rq_of(cfs_rq));
}

다음 상황이 포함된 경우 리스케줄 요청 플래그를 설정한다.

  • 실행 시간이 다 소모된 경우
  • 더 실행해야 할 시간은 남아 있지만 더 빠르게 동작시켜야 할 cfs 런큐에 엔큐된 태스크가 있는 경우
    • 현재 태스크의 vruntime이 다음 수행할 태스크의 vruntime보다 크고 현재 태스크의 time slice 값을 초과하는 경우이다.

 

  • 코드 라인 11에서 현재 태스크가 동작해야 할 time slice 값을 구해 ideal_runtime에 대입한다.
  • 코드 라인 12에서 총 실행 시간에서 기존 실행 시간을 빼면 delta 실행 시간이 산출된다.
  • 코드 라인 13~21에서 delta 실행 시간이 ideal_runtime을 초과한 경우 태스크에 주어진 시간을 다 소모한 것이다. 이러한 경우 리스케줄 요청 플래그를 설정하고 버디들을 클리어하고 함수를 빠져나간다.
  • 코드 라인 28~29에서 delta 실행 시간이 최소 preemption에 필요한 시간(0.75ms) 값보다 작은 경우 현재 태스크가 계속 실행될 수 있도록 함수를 빠져나간다.
  • 코드 라인 31~32에서 cfs 런큐에서 다음 실행할 첫 엔티티를 가져와서 현재 스케줄링 엔티티의 vruntime에서 다음 스케줄링 엔티티의 vruntime을 뺀 delta 시간을 구한다.
  • 코드 라인 34~35에서 delta 시간이 0보다 작은 경우 즉, 다음 스케줄링 엔티티의 vruntime이 현재 스케줄링 엔티티보다 더 큰 일반적인 경우 함수를 빠져나간다.
  • 코드 라인 37에서 delta 시간이 ideal_runtime보다 큰 경우 리스케줄 요청 플래그를 설정한다.

 

resched_curr()

kernel/sched/fair.c

/*
 * resched_curr - mark rq's current task 'to be rescheduled now'.
 *
 * On UP this means the setting of the need_resched flag, on SMP it
 * might also involve a cross-CPU call to trigger the scheduler on
 * the target CPU.
 */
void resched_curr(struct rq *rq)
{
        struct task_struct *curr = rq->curr;
        int cpu;

        lockdep_assert_held(&rq->lock);

        if (test_tsk_need_resched(curr))
                return;

        cpu = cpu_of(rq);

        if (cpu == smp_processor_id()) {
                set_tsk_need_resched(curr);
                set_preempt_need_resched();
                return;
        }

        if (set_nr_and_not_polling(curr))
                smp_send_reschedule(cpu);
        else
                trace_sched_wake_idle_without_ipi(cpu);
}

현재 태스크에 리스케줄 요청 플래그를 설정한다. 만일 런큐의 cpu가 현재 cpu가 아닌 경우 리스케줄 요청 IPI call을 수행한다.

  • 코드 라인 런큐에서 동작중인 현재 태스크에 이미 리스케줄 요청 플래그가 설정된 경우 함수를 빠져나간다.
  • 코드 라인 18~24에서 런큐의 cpu가 현재 cpu와 동일한 경우 태스크에 리스케줄 요청 플래그를 설정하고 함수를 빠져나간다.
    • arm 커널에서 set_preempt_need_resched() 함수는 아무런 동작도 하지 않는다.
  • 코드 라인 26~27에서 리스케줄 요청할 태스크가 현재 런큐의 cpu가 아닌 경우이다. 만일 TIF_POLLING_NRFLAG가 설정되지 않은 경우 리스케줄 요청 플래그를 설정하고 리스케줄 요청 IPI 호출을 수행한다.

 

test_tsk_need_resched()

include/linux/sched.h

static inline int test_tsk_need_resched(struct task_struct *tsk)
{
        return unlikely(test_tsk_thread_flag(tsk,TIF_NEED_RESCHED));
}

현재 태스크에 리스케줄 요청 플래그가 설정되었는지 여부를 반환한다. 낮은 확률로 설정된 경우 true를 반환한다.

 

set_tsk_need_resched()

include/linux/sched.h

static inline void set_tsk_need_resched(struct task_struct *tsk)
{
        set_tsk_thread_flag(tsk,TIF_NEED_RESCHED);
}

현재 태스크에 리스케줄 요청 플래그를 설정한다.

 

set_nr_and_not_polling()

kernel/sched/core.c

#if defined(CONFIG_SMP) && defined(TIF_POLLING_NRFLAG)
/*
 * Atomically set TIF_NEED_RESCHED and test for TIF_POLLING_NRFLAG,
 * this avoids any races wrt polling state changes and thereby avoids
 * spurious IPIs.
 */
static bool set_nr_and_not_polling(struct task_struct *p)
{
        struct thread_info *ti = task_thread_info(p);
        return !(fetch_or(&ti->flags, _TIF_NEED_RESCHED) & _TIF_POLLING_NRFLAG);
}
#else
static bool set_nr_and_not_polling(struct task_struct *p)
{       
        set_tsk_need_resched(p);
        return true;
}

smp 시스템이면서 TIF_POLLING_NRFLAG가 지원되는 커널 여부에 따라 IPI 호출 여부를 판단하기 위해 다음과 같은 동작을 수행한다.

  • 지원되는 경우 현재 태스크가 가리키는 스레드의 플래그에 리스케줄 요청 플래그를 설정한다. 그리고 그 플래그에 _TIF_POLLING_NRFLAG가 설정된 경우 write 폴링 상태 변화 시에 무분별한 IPI 호출이 발생하지 않도록 false를 반환한다.
  • 지원되지 않는 경우 태스크에 리스케줄 요청 플래그를 설정하고 true를 반환한다.

 

smp_send_reschedule()

kernel/smp.c

void smp_send_reschedule(int cpu)
{
        smp_cross_call(cpumask_of(cpu), IPI_RESCHEDULE);
}

지정 cpu로 리스케줄 요청 IPI 호출을 수행한다.

 

태스크가 리스케줄되지 않도록 정리

clear_buddies()

kernel/sched/fair.c

static void clear_buddies(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        if (cfs_rq->last == se)
                __clear_buddies_last(se);

        if (cfs_rq->next == se)
                __clear_buddies_next(se);

        if (cfs_rq->skip == se)
                __clear_buddies_skip(se);
}

다음에 이 스케줄링 엔티티가 재선택되지 않도록 계층적 정리한다.

  • 코드 라인 3~4에서 cfs 런큐의 last가 요청한 스케줄링 엔티티와 동일한 경우 last에 대한 계층적 정리를 수행한다.
  • 코드 라인 5~6에서 cfs 런큐의 next가 요청한 스케줄링 엔티티와 동일한 경우 next에 대한 계층적 정리를 수행한다.
  • 코드 라인 3~4에서 cfs 런큐의 skip이 요청한 스케줄링 엔티티와 동일한 경우 skip에 대한 계층적 정리를 수행한다.

 

__clear_buddies_last()

kernel/sched/fair.c

static void __clear_buddies_last(struct sched_entity *se)
{
        for_each_sched_entity(se) {
                struct cfs_rq *cfs_rq = cfs_rq_of(se);
                if (cfs_rq->last != se)
                        break;

                cfs_rq->last = NULL;
        }
}

최상위 태스크 그룹까지 루프를 돌며 cfs 런큐의 last가 요청한 스케줄링 엔티티인 경우 null을 대입하여 클리어한다.

 

__clear_buddies_next()

kernel/sched/fair.c

static void __clear_buddies_next(struct sched_entity *se)
{
        for_each_sched_entity(se) {
                struct cfs_rq *cfs_rq = cfs_rq_of(se);
                if (cfs_rq->next != se)
                        break;

                cfs_rq->next = NULL;
        }
}

최상위 태스크 그룹까지 루프를 돌며 cfs 런큐의 next가 요청한 스케줄링 엔티티인 경우 null을 대입하여 클리어한다.

 

__clear_buddies_skip()

kernel/sched/fair.c

static void __clear_buddies_skip(struct sched_entity *se)
{
        for_each_sched_entity(se) {
                struct cfs_rq *cfs_rq = cfs_rq_of(se);
                if (cfs_rq->skip != se)
                        break;

                cfs_rq->skip = NULL;
        }
}

최상위 태스크 그룹까지 루프를 돌며 cfs 런큐의 skip이 요청한 스케줄링 엔티티인 경우 null을 대입하여 클리어한다.

 

태스크 Fork

task_fork_fair()

sched/fair.c

/*
 * called on fork with the child task as argument from the parent's context
 *  - child not yet on the tasklist
 *  - preemption disabled
 */
static void task_fork_fair(struct task_struct *p)
{
        struct cfs_rq *cfs_rq;
        struct sched_entity *se = &p->se, *curr;
        int this_cpu = smp_processor_id();
        struct rq *rq = this_rq();
        unsigned long flags;

        raw_spin_lock_irqsave(&rq->lock, flags);

        update_rq_clock(rq);

        cfs_rq = task_cfs_rq(current);
        curr = cfs_rq->curr;

        /*
         * Not only the cpu but also the task_group of the parent might have
         * been changed after parent->se.parent,cfs_rq were copied to
         * child->se.parent,cfs_rq. So call __set_task_cpu() to make those
         * of child point to valid ones.
         */
        rcu_read_lock();
        __set_task_cpu(p, this_cpu);
        rcu_read_unlock();

        update_curr(cfs_rq);

        if (curr)
                se->vruntime = curr->vruntime;
        place_entity(cfs_rq, se, 1);

        if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
                /*
                 * Upon rescheduling, sched_class::put_prev_task() will place
                 * 'current' within the tree based on its new key value.
                 */
                swap(curr->vruntime, se->vruntime);
                resched_curr(rq);
        }

        se->vruntime -= cfs_rq->min_vruntime;

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

부모 context로 부터 fork된 새 child 태스크의 vruntime을 결정한다. (cfs 런큐의 RB 트리의 위치를 결정한다)

  • 코드 라인 16에서 런큐 클럭을 갱신한다.
  • 코드 라인 18에서 현재 처리중인 cfs 태스크의 cfs 런큐를 알아온다.
  • 코드 라인 19에서 cfs 런큐에서 현재 동작중인 스케줄링 엔티티를 알아와서 curr에 대입한다.
  • 코드 라인 28에서 새 태스크의  cpu에 해당하는 각 런큐(cfs 런큐, rt 런큐) 및 엔티티(cfs 스케줄링 엔티티, rt 스케줄링 엔티티)를 설정하고 태스크에 cpu를 지정한다.
  • 코드 라인 31에서 cfs 런큐에서 현재 동작중인 태스크의 런타임 통계들을 갱신한다. 태스크의 실행 시간을 다 소모하였으면 리스케줄 요청한다.
  • 코드 라인 33~34에서 cfs 런큐에서 동작중인 태스크가 있으면 새 스케줄링 엔티티에 현재 동작중인 태스크의 vruntime을 대입한다.
  • 코드 라인 35에서 새 스케줄링 엔티티의 vruntime을 지정한다. (cfs 런큐의 RB 트리에 넣을 위치가 결정된다)
  • 코드 라인 37~44에서 새 child가 먼저 동작하라는 sysctl_sched_child_runs_first가 true이고 현재 동작중인 스케줄링 엔티티가 새 스케줄링 엔티티의 vruntime보다 더 우선인 경우 vruntime 값을 서로 교환하여 자리를 바꾼다. 그런 후 리스케줄 요청한다.
    • “/proc/sys/kernel/sched_child_runs_first”의 default 값은 0으로 1로 설정되는 경우 새 child가 가장 먼저 동작하도록 한다.
  • 코드 라인 46에서 스케줄링 엔티티에서 cfs 런큐의 min_vruntime을 감소시킨다.
    • cfs 런큐에 엔큐된 상태가 아니므로 이 때에는  min_vruntime이 적용되면 안되므로 그 만큼 빼준다.

 

RB 트리에서의 스케줄 엔티티의 위치 설정(vruntime)

place_entity()

kernel/sched/fair.c

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
        u64 vruntime = cfs_rq->min_vruntime;

        /*
         * The 'current' period is already promised to the current tasks,
         * however the extra weight of the new task will slow them down a
         * little, place the new task so that it fits in the slot that
         * stays open at the end.
         */
        if (initial && sched_feat(START_DEBIT))
                vruntime += sched_vslice(cfs_rq, se);

        /* sleeps up to a single latency don't count. */
        if (!initial) {
                unsigned long thresh = sysctl_sched_latency;

                /*
                 * Halve their sleep time's effect, to allow
                 * for a gentler effect of sleepers:
                 */
                if (sched_feat(GENTLE_FAIR_SLEEPERS))
                        thresh >>= 1;

                vruntime -= thresh;
        }

        /* ensure we never gain time by being placed backwards. */
        se->vruntime = max_vruntime(se->vruntime, vruntime);
}

스케줄 엔티티의 vruntime 값을 갱신한다. (vruntime 값이 RB 트리내에서 앞으로 전진하지는 못하고 뒤로 후진만 가능하다)

  • 코드 라인 4에서 cfs 런큐의 min_vruntime 값을 알아온다.
    • 태스크가 cfs 런큐되는 상황이 다음과 같이 있다.
      • 처음 fork 된 태스크
      • 다른 태스크 그룹에서 넘어온 태스크
      • sleep 되었다가 다시 깨어난 태스크
      • 다른 클래스에 있다가 넘어온 태스크
    • place_entity() 함수가 호출되는 case
      • 처음 fork 된 태스크 -> task_fork_fair() -> place_entity(initial=1)
      • 스로틀되었다가 다시 깨어난 태스크 -> unthrottle_cfs_rq(ENQUEUE_WAKEUP) -> enqueue_entity() -> place_entity(initial=0)
      • 다른 클래스로 넘어가려는 태스크 -> switched_from_fair() -> detach_task_cfs_rq() -> place_entity(initial=0)
      • 다른 태스크 그룹에서 넘어온 태스크 -> task_move_group_fair() -> detach_task_cfs_rq() -> place_entity(initial=0)
    • 태스크가 다시 cfs 런큐에 들어올 때 min_vruntime을 가지고 시작한다.
    • cfs 런큐는 글로벌 런큐에도 위치하고 태스크 그룹이 설정된 경우 각각의 태스크 그룹에도 설정되어 사용된다.
  • 코드 라인 12~13에서 태스크에 대한 초기 태스크인 경우이고 START_DEBIT 기능을 사용하는 경우 스케줄 엔티티에 대한 vrumtime을 더 추가하여 조금 더 늦게 실행되도록 유도한다.
    •  initial
      • 초기 태스크가 스케줄링될 때 이 값이 1로 요청된다.
      • 경로: copy_process() -> sched_fork() —p->sched_class->task_fork(p)–> task_fork_fair() -> place_entity()
    • START_DEBIT 기능이 보통 true로 설정되어 있고 cfs 런큐에 진입한 태스크에 대해 이렇게 한 타임(vruntime) 만큼 뒤로 위치시켜 동작시킨다.
      • “/proc/sys/kernel/sched_child_runs_first” 기능을 사용하는 경우 이 함수를 빠져나간 후에 현재 실행 중인 태스크보다 fork된 자식 태스크를 먼저 실행 시키기 위해 현재 태스크의 vruntime과 swap 시킨다.
  • 코드 라인 16~27에서 초기 태스크 생성시 호출된 경우가 아니면 스케줄 latency 만큼 vruntime을 줄인다. 단 GENTLE_FAIR_SLEEPERS 기능을 사용하는 경우 절반만 줄인다.
  • 코드 라인 30에서 산출된 vruntime 값이 스케줄 엔티티의 vruntime 값보다 큰 경우 갱신한다.
    • cfs_rq->min_vruntime <= se->vruntime

 

sched_feat() 매크로

kernel/sched/sched.h

#define SCHED_FEAT(name, enabled)       \
        __SCHED_FEAT_##name ,

enum {
#include "features.h"
        __SCHED_FEAT_NR,
};

#define sched_feat(x) (sysctl_sched_features & (1UL << __SCHED_FEAT_##x))

 

kernel/sched/features.h

SCHED_FEAT(GENTLE_FAIR_SLEEPERS, true)
SCHED_FEAT(START_DEBIT, true)
SCHED_FEAT(NEXT_BUDDY, false)
SCHED_FEAT(LAST_BUDDY, true)
SCHED_FEAT(CACHE_HOT_BUDDY, true)
SCHED_FEAT(WAKEUP_PREEMPTION, true)
SCHED_FEAT(ARCH_CAPACITY, true)
SCHED_FEAT(HRTICK, false)
SCHED_FEAT(DOUBLE_TICK, false)
SCHED_FEAT(LB_BIAS, true)
SCHED_FEAT(NONTASK_CAPACITY, true)
SCHED_FEAT(TTWU_QUEUE, true)
SCHED_FEAT(FORCE_SD_OVERLAP, false)
SCHED_FEAT(RT_RUNTIME_SHARE, true)
SCHED_FEAT(LB_MIN, false)
SCHED_FEAT(NUMA,        false)
SCHED_FEAT(NUMA_FAVOUR_HIGHER, true)
SCHED_FEAT(NUMA_RESIST_LOWER, false)

 

sysctl_sched_features 초기값

kernel/sched/core.c

/*
 * Debugging: various feature bits
 */

#define SCHED_FEAT(name, enabled)       \
        (1UL << __SCHED_FEAT_##name) * enabled |

const_debug unsigned int sysctl_sched_features =
#include "features.h"
        0;

 

Enque & Dequeue

enqueue_task_fair()

kernel/sched/fair.c

/*
 * The enqueue_task method is called before nr_running is
 * increased. Here we update the fair scheduling stats and
 * then put the task into the rbtree:
 */
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
        struct cfs_rq *cfs_rq;
        struct sched_entity *se = &p->se;

        for_each_sched_entity(se) {
                if (se->on_rq)
                        break;
                cfs_rq = cfs_rq_of(se);
                enqueue_entity(cfs_rq, se, flags);

                /*
                 * end evaluation on encountering a throttled cfs_rq
                 *
                 * note: in the case of encountering a throttled cfs_rq we will
                 * post the final h_nr_running increment below.
                */
                if (cfs_rq_throttled(cfs_rq))
                        break;
                cfs_rq->h_nr_running++;

                flags = ENQUEUE_WAKEUP;
        }

        for_each_sched_entity(se) {
                cfs_rq = cfs_rq_of(se);
                cfs_rq->h_nr_running++;

                if (cfs_rq_throttled(cfs_rq))
                        break;

                update_cfs_shares(cfs_rq);
                update_entity_load_avg(se, 1);
        }

        if (!se) {
                update_rq_runnable_avg(rq, rq->nr_running);
                add_nr_running(rq, 1);
        }
        hrtick_update(rq);
}

태스크를 런큐에 추가하고 로드 weight 및 runtime 통계들을 갱신한다. cgroup을 사용하여 태스크(스케줄링) 그룹이 구성되어 운영되는 경우 각 태스크 그룹의 cfs 런큐에 각각의 스케줄 엔티티를 큐잉하고 역시 로드 weight 및 runtime 통계들을 갱신한다.

  • 코드 라인 12~14에서 요청 태스크의 스케줄링 엔티티들에 대해 루프를 돌며 현재의 스케줄링 엔티티가 런큐에 이미 존재하면 루프를 탈출한다.
  • 코드 라인 15~16에서 현재의 스케줄링 엔티티의 cfs 런큐에서 스케줄링 엔티티를 큐에 넣는다.
  • 코드 라인 24~29에서 cfs 런큐가 스로틀된 경우 루프를 탈출하고 그렇지 않은 경우 루프를 계속 진행한다.
  • 코드 라인 31~36에서 스케줄링 엔티티가 중간에서 멈춘 경우 그 중간 부터 계속 하여 루프를 돌며 cfs 런큐가 스로틀된 경우 루프를 벗어난다.
  • 코드 라인 38~40에서 cfs 공유를 갱신하고 엔티티 로드 평균을 갱신한다.
  • 코드 라인 42~45에서 위 두 번째 스케줄링 엔티티 루프에서도 스로틀되어 탈출했었던 경우 런큐 러너블 평균을 갱신하고 런큐의 nr_running을 1 증가시킨다.
  • 코드 라인 46에서 hrtick을 갱신한다.

 

다음 그림은 enqueue_task_fair() 함수에서 태스크를 추가할 때 각 태스크 그룹의 cfs 런큐에 큐잉되는 모습을 보여준다.

 

for_each_sched_entity() 매크로

“kernel/sched/fair.c

/* Walk up scheduling entities hierarchy */
#define for_each_sched_entity(se) \
                for (; se; se = se->parent)

스케줄 엔티티의 최상위 부모까지 루프를 돈다.

  • cgroup을 사용하여 태스크(스케줄링) 그룹을 계층적으로 만들어서 운영하는 경우 스케줄 엔티티는 태스크가 있는 하위 스케줄 엔티티부터 루트 태스크 그룹까지 부모로 연결된다.
  • 그러나 태스크(스케줄링) 그룹을 운영하지 않는 경우 태스크는 태스크 구조체 내부에 임베드된 스케줄 엔티티 하나만을 갖게되어 루프를 돌지 않는다.

 

 

enqueue_entity()

kernel/sched/fair.c

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
        /*
         * Update the normalized vruntime before updating min_vruntime
         * through calling update_curr().
         */
        if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
                se->vruntime += cfs_rq->min_vruntime;

        /*
         * Update run-time statistics of the 'current'.
         */
        update_curr(cfs_rq);
        enqueue_entity_load_avg(cfs_rq, se, flags & ENQUEUE_WAKEUP);
        account_entity_enqueue(cfs_rq, se);
        update_cfs_shares(cfs_rq);

        if (flags & ENQUEUE_WAKEUP) {
                place_entity(cfs_rq, se, 0);
                enqueue_sleeper(cfs_rq, se);
        }

        update_stats_enqueue(cfs_rq, se);
        check_spread(cfs_rq, se);
        if (se != cfs_rq->curr)
                __enqueue_entity(cfs_rq, se);
        se->on_rq = 1;

        if (cfs_rq->nr_running == 1) {
                list_add_leaf_cfs_rq(cfs_rq);
                check_enqueue_throttle(cfs_rq);
        }
}

스케줄 엔티티를 RB 트리에 큐잉하고 런타임 통계를 갱신한다.

  • 코드 라인 7~8에서 wakeup 또는 waking 플래그가 지정되지 않은 경우 vruntime에 min_vruntime을 추가한다.
  • 코드 라인 14에서 현재 태스크의 런타임 통계들을 갱신한다. 또한 현재 태스크의 실행 시간을 다 소모하였으면 리스케줄 요청한다.
  • 코드 라인 15에서 엔티티 로드 평균을 추가한다.
  • 코드 라인 16에서 cfs 런큐에 스케줄 엔티티의 로드를 추가한다. 부모 스케줄 엔티티가 없으면 cfs 런큐가 속한 런큐의 로드에도 추가한다.
  • 코드 라인 17에서 cfs 스케줄러을 위해 태스크 그룹별 shares 값을 갱신한다.
  • 코드 라인 19~22에서 ENQUEUE_WAKEUP 플래그가 요청된 경우스케줄 엔티티의 vruntime 값을 갱신하고 스케줄 슬립 통계  항목들을 업데이트한다.
  • 코드 라인 24에서 enque된 스케줄 엔티티가 cfs 런큐에서 현재 돌고 있지 않은 경우 wait_start를 현재 런큐 시각으로 설정한다.
  • 코드 라인 25에서 디버깅을 위해 nr_spread_over를 갱신한다.
  • 코드 라인 26~27에서 스케줄 엔티티가 cfs 런큐에서 현재 러닝중이지 않으면 엔큐한다.
  • 코드 라인 28에서 on_rq에 1을 대입하여 현재 스케줄 엔티티가 런큐에서 동작함을 알린다.
  • 코드 라인 30~33에서 cfs 런큐에서 동작 중인 active 태스크가 1개 뿐인 경우 런큐의 cfs 리스트에 cfs 런큐를 추가하고 필요한 경우 스로틀 한다.

 

__enqueue_entity()

kernel/sched/fair.c

/*
 * Enqueue an entity into the rb-tree:
 */
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
        struct rb_node *parent = NULL;
        struct sched_entity *entry;
        int leftmost = 1;

        /*
         * Find the right place in the rbtree:
         */
        while (*link) {
                parent = *link;
                entry = rb_entry(parent, struct sched_entity, run_node);
                /*
                 * We dont care about collisions. Nodes with
                 * the same key stay together.
                 */
                if (entity_before(se, entry)) {
                        link = &parent->rb_left;
                } else {
                        link = &parent->rb_right;
                        leftmost = 0;
                }
        }

        /*
         * Maintain a cache of leftmost tree entries (it is frequently
         * used):
         */
        if (leftmost)
                cfs_rq->rb_leftmost = &se->run_node;

        rb_link_node(&se->run_node, parent, link);
        rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

스케줄 엔티티를 RB 트리에 추가한다.

  • 코드 라인 6에서 처음 비교할 노드로 RB 트리 루트 노드를 선택한다.
  • 코드 라인 14에서 루프를 돌며 노드가 있는 동안 루프를 돈다. (null이되면 끝)
  • 코드 라인 15~16에서 parent에 현재 비교할 노드를 보관하고 이 노드에 담긴 스케줄 엔티티를 entry에 대입한다.
  • 코드 라인 21~26에서 스케줄 엔티티의 vruntime이 비교 entry의 vruntime보다 작은 경우 좌측 노드 방향을 선택하고 그렇지 않은 경우 우측 노드 방향을 선택한다.
  • 코드 라인 33~34에서 요청한 스케줄 엔티티의 vruntime 값이 RB 트리에서 가장 작은 수인 경우 루프 안에서 한 번도 우측 방향을 선택하지 않았던 경우 이다. 이러한 경우 cfs 런큐의 rb_leftmost는 이 스케줄 엔티티를 가리키게 한다. cfs 런큐에서 다음에 스케줄 엔티티를 pickup할 경우 가장 먼저 선택된다.
  • 코드 라인 36~37에서 RB 트리에 추가하고 color를 갱신한다.

 

다음 그림은 스케줄 엔티티를 cfs 런큐에 큐잉하는 모습을 보여준다.

 

list_add_leaf_cfs_rq()

kernel/sched/fair.c

static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
{
        if (!cfs_rq->on_list) {
                /*
                 * Ensure we either appear before our parent (if already
                 * enqueued) or force our parent to appear after us when it is
                 * enqueued.  The fact that we always enqueue bottom-up
                 * reduces this to two cases.
                 */
                if (cfs_rq->tg->parent &&
                    cfs_rq->tg->parent->cfs_rq[cpu_of(rq_of(cfs_rq))]->on_list) {
                        list_add_rcu(&cfs_rq->leaf_cfs_rq_list,
                                &rq_of(cfs_rq)->leaf_cfs_rq_list);
                } else {
                        list_add_tail_rcu(&cfs_rq->leaf_cfs_rq_list,
                                &rq_of(cfs_rq)->leaf_cfs_rq_list);
                }

                cfs_rq->on_list = 1;
                /* We should have no load, but we need to update last_decay. */
                update_cfs_rq_blocked_load(cfs_rq, 0);
        }
}

요청한 cfs 런큐를 leaf 리스트에 추가한다. (leaf 리스트 선두는 항상 태스크를 소유한 스케줄 엔티티의 가장 아래 cfs 런큐가 있어야 한다.)

  • 코드 라인 3에서 요청한 cfs 런큐가 leaf 리스트에 없는 경우
    • on_list
      • cfs 런큐가 leaf_cfs_rq_list에 추가 되어 있는 경우 true가 된다.
  • 코드 라인 10~17에서 부모 cfs 런큐가 leaf 리스트에 이미 올라가 있는 경우 요청한 leaf cfs 런큐를 런큐의 leaf 리스트의 선두에 추가하고 그렇지 않은 경우 후미에 추가한다.
  • 코드 라인 19~21에서 요청한 cfs 런큐가 leaf 리스트에 올라갔음을 표시하고, 런큐 블럭드 로드 평균을 갱신한다.

 

다음 그림은 list_add_leaf_cfs_rq() 함수가 패치되기 전/후의 동작을 보여준다.

 

add_nr_running()

kernel/sched/sched.h

static inline void add_nr_running(struct rq *rq, unsigned count)
{
        unsigned prev_nr = rq->nr_running;

        rq->nr_running = prev_nr + count;

        if (prev_nr < 2 && rq->nr_running >= 2) {
#ifdef CONFIG_SMP
                if (!rq->rd->overload)
                        rq->rd->overload = true;
#endif

#ifdef CONFIG_NO_HZ_FULL
                if (tick_nohz_full_cpu(rq->cpu)) {
                        /*
                         * Tick is needed if more than one task runs on a CPU.
                         * Send the target an IPI to kick it out of nohz mode.
                         *
                         * We assume that IPI implies full memory barrier and the
                         * new value of rq->nr_running is visible on reception
                         * from the target.
                         */
                        tick_nohz_full_kick_cpu(rq->cpu);
                }
#endif
        }
}

런큐에서 돌고있는 active 태스크의 수를 count 만큼 추가한다.

  • 코드 라인 3~5에서 런큐에서 돌고있는 active 태스크의 수를 count 만큼 추가한다.
  • 코드 라인 7~11에서 기존 active 태스크 수가 2개 미만이었지만 추가한 태스크를 포함하여 active 태스크가 2개 이상이 된 경우 smp 시스템이면 런큐의 루트 도메인에 있는 overload를 true로 변경한다.
  • 코드 라인 13~25에서 nohz full을 지원하는 커널인 경우 현재 런큐가 nohz full을 지원하는 상태이면 nohz full 상태에서 빠져나와 tick을 발생하게 한다.

 

hrtimer를 사용한 hrtick

hrtick 갱신

hrtick_update()

kernel/sched/fair.c

/*
 * called from enqueue/dequeue and updates the hrtick when the
 * current task is from our class and nr_running is low enough
 * to matter.
 */
static void hrtick_update(struct rq *rq)
{
        struct task_struct *curr = rq->curr;

        if (!hrtick_enabled(rq) || curr->sched_class != &fair_sched_class)
                return;

        if (cfs_rq_of(&curr->se)->nr_running < sched_nr_latency)
                hrtick_start_fair(rq, curr);
}

다음 hrtick 만료 시각을 갱신한다. 이 함수는 스케줄 엔티티가 엔큐/디큐될 때마다 호출된다.

  • 코드 라인 10~11에서 high-resolution 모드의 hitimer를 사용하는 hrtick이 사용되지 않거나 현재 태스크가 cfs 스케줄러를 사용하지 않으면 함수를 빠져나간다.
  • 코드 라인 13~14에서 현재 태스크의 스케줄 엔티티의 cfs 런큐에서 동작하는 active 태스크가 sched_nr_latency(디폴트 8) 미만인 경우 다음 hrtick 만료 시각을 설정한다.

 

/*
 * Use hrtick when:
 *  - enabled by features
 *  - hrtimer is actually high res 
 */
static inline int hrtick_enabled(struct rq *rq)
{
        if (!sched_feat(HRTICK))
                return 0;
        if (!cpu_active(cpu_of(rq)))
                return 0;
        return hrtimer_is_hres_active(&rq->hrtick_timer);
}

high-resolution 모드의 hitimer를 사용하는 hrtick 동작 여부를 반환한다.

  •  hrtimer_is_hres_active()
    • return timer->base->cpu_base->hres_active

 

static void hrtick_start_fair(struct rq *rq, struct task_struct *p)
{
        struct sched_entity *se = &p->se;
        struct cfs_rq *cfs_rq = cfs_rq_of(se);

        WARN_ON(task_rq(p) != rq);

        if (cfs_rq->nr_running > 1) {
                u64 slice = sched_slice(cfs_rq, se);
                u64 ran = se->sum_exec_runtime - se->prev_sum_exec_runtime;
                s64 delta = slice - ran;

                if (delta < 0) {
                        if (rq->curr == p)
                                resched_curr(rq);
                        return;
                }
                hrtick_start(rq, delta);
        }
}

다음 hrtick 만료 시각을 설정한다.

  • 코드 라인 8에서 요청한 태스크의 스케줄 엔티티의 cfs 런큐에서 동작 중인 active 태스크 수가 1개를 초과하는 경우
  • 코드 라인 9~11에서 현재 스케줄 엔티티의 에 대한 time slice – (총 실행 시간에서 기존 실행 시간)을 delta에 대입한다.
  • 코드 라인 13~17에서 delta 시간이 0보다 작은 경우 함수를 빠져나간다. 만일 현재 런큐에서 요청 태스크가 동작중인 경우 현재 태스크에 리스케줄 요청 플래그를 설정한다.
  • 코드 라인 11에서 delta 만료 시간으로 런큐의 hrtick 타이머를 가동시킨다.

 

다음 그림은 hrtick 만료 시각을 설정하는 모습을 보여준다.

 

hrtick 만료 시각 설정

hrtick_start()

kernel/sched/core.c

/*
 * Called to set the hrtick timer state.
 *              
 * called with rq->lock held and irqs disabled
 */
void hrtick_start(struct rq *rq, u64 delay)
{
        struct hrtimer *timer = &rq->hrtick_timer;
        ktime_t time;
        s64 delta;

        /*
         * Don't schedule slices shorter than 10000ns, that just
         * doesn't make sense and can cause timer DoS.
         */
        delta = max_t(s64, delay, 10000LL);
        time = ktime_add_ns(timer->base->get_time(), delta);

        hrtimer_set_expires(timer, time);

        if (rq == this_rq()) {
                __hrtick_restart(rq);
        } else if (!rq->hrtick_csd_pending) {
                smp_call_function_single_async(cpu_of(rq), &rq->hrtick_csd);
                rq->hrtick_csd_pending = 1;
        }
}

delta 만료 시간으로 런큐의 hrtick 타이머를 가동시킨다. 런큐가 현재 cpu인 경우 hrtimer를 곧바로 설정하고 그렇지 않은 경우 IPI call을 통해 hrtick에 대한 hrtimer를 설정한다.

  • 코드 라인 16~17에서 요청한 delta 값이 10000ns(10us) 보다 작지 않도록 교정하고 현재 시각에 더해 만료 시각 time을 산출한다.
  • 코드 라인 19에서 hrtimer에 만료 시각 time을 설정한다.
  • 코드 라인 21~22에서 요청 런큐가 현재 cpu에서 동작중인 경우 곧바로 hrtick에 대한 hrtimer를 가동시킨다.
    • 만료 시간이 되면 init_rq_hrtick()에서 초기화 설정해둔 hrtick() 함수가 호출된다.
  • 코드 라인 23~26에서 런큐에서 hrtick_csd_pending 상태가 아니면 hrtick에 대한 IPI 호출을 수행하고 런큐의 hrtick_csd_pending을 1로 설정한다.
    • init_rq_hrtick()에서 초기화 설정해둔 __hrtick_start() 함수가 IPI 호출 시 동작된다.

 

hrtick IPI 호출

__hrtick_start()

kernel/sched/core.c

/*
 * called from hardirq (IPI) context
 */
static void __hrtick_start(void *arg)
{
        struct rq *rq = arg;

        raw_spin_lock(&rq->lock);
        __hrtick_restart(rq);
        rq->hrtick_csd_pending = 0;
        raw_spin_unlock(&rq->lock);
}

다른 cpu로부터 IPI 호출을 받아 동작되는 이 함수에서는 런큐의 hrtick을 리프로그램한다.

  • 코드 라인 9에서 런큐의 hrtick을 리프로그램한다.
  • 코드 라인 10에서 런큐의 hrtick_csd_pending에 0을 대입하여 hrtick에 대한 call single data IPI 가 처리되었음을 알린다.

 

hrtick 만료시 호출

hrtick()

kernel/sched/core.c

/*
 * High-resolution timer tick.
 * Runs from hardirq context with interrupts disabled.
 */
static enum hrtimer_restart hrtick(struct hrtimer *timer)
{
        struct rq *rq = container_of(timer, struct rq, hrtick_timer);

        WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());

        raw_spin_lock(&rq->lock);
        update_rq_clock(rq);
        rq->curr->sched_class->task_tick(rq, rq->curr, 1);
        raw_spin_unlock(&rq->lock);

        return HRTIMER_NORESTART;
}

런큐 클럭을 갱신하고 현재 태스크의 스케줄러의 후크 함수(*task_tick)에 등록된 함수를 호출한다

  • 각각의 스케줄러에서 사용되는 함수는 다음과 같다.
    • task_tick_rt()
    • task_tick_dl()
    • task_tick_fair()
    • task_tick_idle()
    • task_tick_stop()

 

 

구조체

load_weight 구조체

include/linux/sched.h

struct load_weight {
        unsigned long weight;
        u32 inv_weight;
};
  • weight
    • CFS 스케줄러에서 사용하는 유저 태스크에 주어진 우선순위 nice에 대한 태스크 로드 값
    • default nice 값 0인 경우 weight=1024
  • inv_weight
    • prio_to_wmult[] 배열에 이미 만들어진 nice값에 해당하는 2^32/weight 값

 

sched_entity 구조체

include/linux/sched.h

struct sched_entity {
        struct load_weight      load;           /* for load-balancing */
        struct rb_node          run_node;
        struct list_head        group_node;
        unsigned int            on_rq;

        u64                     exec_start;
        u64                     sum_exec_runtime;
        u64                     vruntime;
        u64                     prev_sum_exec_runtime;

        u64                     nr_migrations;

#ifdef CONFIG_SCHEDSTATS
        struct sched_statistics statistics;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
        int                     depth;
        struct sched_entity     *parent;
        /* rq on which this entity is (to be) queued: */
        struct cfs_rq           *cfs_rq;
        /* rq "owned" by this entity/group: */
        struct cfs_rq           *my_q;
#endif

#ifdef CONFIG_SMP
        /* Per-entity load-tracking */
        struct sched_avg        avg;
#endif
};
  • load
    • 스케줄 엔티티의 load weight 값
  • run_node
    • cfs 런큐의 RB 트리에 연결될 때 사용되는 노드
  • group_node
    • cfs 런큐의 cfs_tasks 리스트에 연결될 떄 사용되는 노드
  • on_rq
    • cfs 런큐에 엔큐 여부
  • exec_start
    • 현재 스케줄 엔티티의 실행 시각(ns)
  • sum_exec_runtime
    • 현재 스케줄 엔티티가 실행한 총 시간(ns)
  • vruntime
    • 가상 런타임 값으로 이 시간을 기준으로 cfs 런큐의 RB 트리에 엔큐된다.
  • prev_sum_exec_runtime
    • 이전 스케줄 엔티티가 실행한 총 시간(ns)
  • nr_migrations
    • 로드 밸런스 횟수
  • statistics
    • 스케줄 통계
  • depth
    • 태스크 그룹의 단계별 depth로 루트 그룹이 0이다.
  • *parent
    • 부모 스케줄 엔티티
    • 태스크 그룹이 구성되면 스케줄 엔티티가 계층 구조로 구성된다.
  • *cfs_rq
    • 연결된 cfs 런큐
  • *my_q
    • 런큐의 cfs 런큐
  • avg
    • 스케줄 엔티티의 로드 평균(PELT)

 

cfs_rq 구조체

kernel/sched/sched.h

/* CFS-related fields in a runqueue */
struct cfs_rq {
        struct load_weight load;
        unsigned int nr_running, h_nr_running;

        u64 exec_clock;
        u64 min_vruntime;
#ifndef CONFIG_64BIT
        u64 min_vruntime_copy;
#endif

        struct rb_root tasks_timeline;
        struct rb_node *rb_leftmost;

        /*
         * 'curr' points to currently running entity on this cfs_rq.
         * It is set to NULL otherwise (i.e when none are currently running).
         */
        struct sched_entity *curr, *next, *last, *skip;

#ifdef  CONFIG_SCHED_DEBUG
        unsigned int nr_spread_over;
#endif

#ifdef CONFIG_SMP
        /*
         * CFS Load tracking
         * Under CFS, load is tracked on a per-entity basis and aggregated up.
         * This allows for the description of both thread and group usage (in
         * the FAIR_GROUP_SCHED case).
         */
        unsigned long runnable_load_avg, blocked_load_avg;
        atomic64_t decay_counter;
        u64 last_decay;
        atomic_long_t removed_load;

#ifdef CONFIG_FAIR_GROUP_SCHED
        /* Required to track per-cpu representation of a task_group */
        u32 tg_runnable_contrib;
        unsigned long tg_load_contrib;

        /*
         *   h_load = weight * f(tg)
         *
         * Where f(tg) is the recursive weight fraction assigned to
         * this group.
         */
        unsigned long h_load;
        u64 last_h_load_update;
        struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */

#ifdef CONFIG_FAIR_GROUP_SCHED
        struct rq *rq;  /* cpu runqueue to which this cfs_rq is attached */

        /*
         * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
         * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
         * (like users, containers etc.)
         *
         * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
         * list is used during load balance.
         */
        int on_list;
        struct list_head leaf_cfs_rq_list;
        struct task_group *tg;  /* group that "owns" this runqueue */

#ifdef CONFIG_CFS_BANDWIDTH
        int runtime_enabled;
        u64 runtime_expires;
        s64 runtime_remaining;

        u64 throttled_clock, throttled_clock_task;
        u64 throttled_clock_task_time;
        int throttled, throttle_count;
        struct list_head throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};
  • load
    • cfs 런큐의 load weight 값
  • nr_running
    • cfs 런큐의 cpu 파워를 분할하여 사용하는 스케줄 엔티티 수
  • h_nr_running
    • cfs 런큐에서 동작중인 active 태스크 수
  • exec_clock
    • 실행 시각
  • vruntime
    • cfs 런큐의 RB 트리에 등록될 때 이 값으로 정렬한다.
    • 이 값이 가장 작은 수가 cfs 런큐에서 다음 우선적으로 선택될 태스크이다.
  • min_vruntime
    • 최소 가상 런타임
    • RB 트리에서 엔큐된 스케줄 엔티티의 vruntime에서 이 값을 빼서 사용한다.
  • min_vruntime_copy
    • 32비트 시스템에서 사용
  • tasks_timeline
    • cfs 런큐의 RB 트리
  • *rb_leftmost
    • cfs 런큐의 RB 트리에 있는 가장 좌측의 노드를 가리킨다.
    • 가장 작은 vruntime 값을 가지는 스케줄 엔티티 노드
  • *curr
    • cfs 런큐에서 동작 중인 현재 스케줄 엔티티
  • *next
    • cfs 런큐에서 다음에 동작할 스케줄 엔티티
  • *last
    • cfs 런큐에서 마지막 위치한 스케줄 엔티티
  • *skip
    • cfs 런큐에서 skip할 스케줄 엔티티
  • nr_spread_over
  • runnable_load_avg
    • PELT 기반 러너블 로드 평균
  • blocked_load_avg
    • PELT 기반 블럭드 로드 평균
  • decay_counter
    • decay된 횟수
  • last_decay
    • 마지막 decay된 시각
  • removed_load
  • tg_runnable_contrib
    • 태스크 그룹의 러너블 기여
  • tg_load_contrib
    • 태스크 그룹의 로드 기여
  • h_load
  • last_h_load_update
  • *h_load_next
  • *rq
    • cfs 런큐가 속한 런큐를 가리킨다.
  • on_list
    • leaf cfs 런큐 리스트에 포함 여부
  • leaf_cfs_rq_list
    • cfs_rq가 추가되며 child cfs 런큐가 리스트의 앞으로 추가된다.
  • *tg
    • cfs 런큐가 속한 태스크 그룹
  • runtime_enabled
    • cfs 런큐에서 cfs 밴드폭 구성 사용
    • quota가 설정된 경우 사용
  • runtime_expires
    • 런타임 만료
  • runtime_remaing
    • 남은 런타임
  • throttled_clock
    • 스로틀 시작 시각
  • throttled_clock_task
    • 스로틀 시작 시각(irq 처리 시간을 제외한 태스크 시간)
    • throttled_clock은 rq->clock을 사용하였고 throttled_clock_task는 rq->clock_task를 사용하였다. 둘의 차이는 cfs bandwidth를 참고한다.
  • throttled_clock_task_time
    • 스로틀된 시간 총합(irq 처리 시간을 제외하고 스로틀된 태스크 시간)
  • throttled
    • cfs 런큐가 스로틀된 경우 true
  • throttle_count
    • cfs 런큐가 스로틀된 횟수로 계층 구조의 스케줄 엔티티에 대해 child 부터 시작하여 스로된 cfs 런큐가 있는 경우 카운터가 증가되다.
  • throttled_list
    • cfs_bandwidth의 throttled_cfs_rq 리스트에 추가할 때 사용하는 cfs 런큐의 스로틀 리스트

 

 

CFS 스케줄러 ops

kernel/sched/fair.c

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class = {
        .next                   = &idle_sched_class,
        .enqueue_task           = enqueue_task_fair,
        .dequeue_task           = dequeue_task_fair,
        .yield_task             = yield_task_fair,
        .yield_to_task          = yield_to_task_fair,

        .check_preempt_curr     = check_preempt_wakeup,

        .pick_next_task         = pick_next_task_fair,
        .put_prev_task          = put_prev_task_fair,

#ifdef CONFIG_SMP
        .select_task_rq         = select_task_rq_fair,
        .migrate_task_rq        = migrate_task_rq_fair,

        .rq_online              = rq_online_fair,
        .rq_offline             = rq_offline_fair,

        .task_waking            = task_waking_fair,
#endif

        .set_curr_task          = set_curr_task_fair,
        .task_tick              = task_tick_fair,
        .task_fork              = task_fork_fair,

        .prio_changed           = prio_changed_fair,
        .switched_from          = switched_from_fair,
        .switched_to            = switched_to_fair,

        .get_rr_interval        = get_rr_interval_fair,

        .update_curr            = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
        .task_move_group        = task_move_group_fair,
#endif
};

 

참고

 

 

답글 남기기

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