Scheduler -5- (CFS Bandwidth)

CFS Bandwidth

태스크 그룹별로 shares 값을 설정하여 cfs 태스크의 스케줄 할당 비율을 조절할 수 있엇다. 여기서 또 다른 cfs 태스크의 스케줄 할당 비율을 조절할 수 있는 cfs bandwidth 방법을 소개한다.

 

태스크 그룹에 매 cfs_period_us 기간 마다 cfs_quota_us 기간 만큼 런타임을 할당하여 사용한다. 소진되어 런타임 잔량이 0이하가 되면 다음 period가 오기 전까지 남는 시간은 스로틀링 한다. 즉 해당 그룹을 대표하는 스케줄 엔티티가 상위 cfs 런큐로부터 dequeue되어 활동을 잠시 정지하게 된다. 이렇게 하여 다른 태스크 그룹에게 시간 할당을 양보한다.

  • cfs_period_us
    • bandwidth 기간 (us)
  • cfs_quota_us
    • bandwidth 할당 쿼터 (us)
    • 디폴트 값으로 -1(무제한)이 설정되어 있으며, 이 때에는 cfs bandwidth가 동작하지 않는다.

 

다음은 루트 태스크 그룹에 설정된 cfs_period_us와 cfs_quota_us 값을 보여준다. 디폴트로 cfs_quota_us 값이 -1이 설정되어 cfs bandwidth가 활성화되어 있지 않음을 알 수 있다.

$ cd /sys/fs/cgroup/cpu
$ ls
cgroup.clone_children  cpu.cfs_period_us  cpu.stat       cpuacct.usage_percpu  system.slice
cgroup.procs           cpu.cfs_quota_us   cpuacct.stat   notify_on_release     tasks
cgroup.sane_behavior   cpu.shares         cpuacct.usage  release_agent         user.slice
$ cat cpu.cfs_period_us 
100000
$ cat cpu.cfs_quota_us 
-1

 

다음 용어들이 빈번이 나오므로 먼저 요약한다.

  • cfs runtime
    • cfs 런큐에 태스크가 스케줄되어 동작한 시간
  • 스로틀
    • period 기간동안 quota 만큼 다 소진하면 나머지 시간을 해당 태스크 그룹에 해당하는 스케줄 엔티티를 dequeue 하여 타임할당을 받지 않는다.
    • 스로틀 후 period 시각이 되면 다시 태스크 그룹에 해당하는 스케줄 엔티티를 엔큐한다.
  • quota 정수 비율 (normalize cfs quota)
    • period 기간에 대한 quota 기간의 비율을 정수로 변환한 값이다.
    • 100%=1M(1,048,576)이다.
    • 예 1) period=10ms, quota=5ms인 경우 50%이며 이 비율을 quota 정수 비율로 표현하면 524,288이다.
    • 예 2) period=10ms, quota=20ms인 경우 200%이며 이 비율을 quota 정수 비율로 표현하면 2,097,152이다.

 

bandwidth가 적용된 사례 3개를 확인해보자.

 

사례 1) 다음 그림은 20ms 주기마다 10ms quota 만큼 cfs 스케줄되는 모습을 보여준다. 남는 시간은 스로틀링 한다.

  • 범례 설명
  • cfs running
    • 해당 태스크 그룹에 소속된 cfs 태스크들이 사용한 런타임 구간이다.
  • cfs 스로틀
    • 해당 태스크 그룹이 dequeue되고 해당 태스크 그룹 외의 다른 cfs 태스크들이 동작하는 구간이다.
    • 동작할 태스크가 하나도 없는 경우 idle 한다.
  • other 스케줄러
    • 해당 태스크 그룹의 스케줄 엔티티가 아닌 태스크들이 먼저 스케줄되어 동작하는 경우이다.
    • 물론 다른 태스크 그룹의 cfs 태스크 이외에도 dl 이나 rt 태스크는 cfs 태스크보다 우선 순위가 더 빠르기 때문에 언제든지 other 스케줄러 표시에 들어갈 수 있다.
  • 1 번째 period 구간은 해당 그룹이 먼저 동작하고 주어진 quota 만큼의 런타임을 다 소진하고 스로틀링 하여 다른 태스크들에게 스케줄링을 넘겼다.
  • 2 번째 period 구간이 되면서 다시 quota 만큼 런타임을 재충전(refill) 받아 다시 모두 사용하고 또 스로틀링하였다.
  • 3 번째 period 구간에서 other(stop, rt, dl) 스케줄러가 먼저 할당되어 동작하고 끝나면서 해당 그룹의 cfs 태스크가 수행됨을 알 수 있다.
  • 9 번째 period 구간과 같이 어쩔 수 없이 해당 태스크 그룹이 사용할 수 있는 10ms quota 만큼의 런타임을 소진하지 못하는 경우도 있음을 알 수 있다.

 

사례 2) 다음 그림은 20ms 주기마다 2개의 cpu에 총 20ms quota 만큼 cfs 스케줄한다.

  • period와 quota가 같은 경우 2개의 cpu가 주어지면 일반적으로 매 period 마다 2 개의 cpu가 번갈아 가면서 런타임이 소진된다.
  • cpu가 두 개라 period와 quota 기간이 같아도 절반의 여유가 있음을 확인할 수 있다.
  • 가능하면 스로틀링한 cpu에 런타임을 우선 할당하여 스로틀링이 교대로 됨을 알 수 있다.
  • 8 번째 period 구간의 경우 해당 태스크 그룹은 한 번도 런타임 소진을 못한 경우이다.

 

사례 3) 다음 그림은 20ms 주기마다 2개의 cpu에 총 30ms quota 만큼 cfs 스케줄한다.

  • 해당 태스크 그룹은 최대 75%의 cfs 런타임 할당을 받는 것을 확인할 수 있다.

 

다음 그림은 G1 태스크 그룹에 period, quota=25의 밴드위드를 설정하여 동작시켰을 때의 이해를 돕기 위해 더 자세히 표현하였다.

  • 다만 다음 항목들은 적용하지 않았다.
    • G1 그룹에 대한 엔티티 로드 weight 값에 tg_weight 비율을 적용하지 않고 그냥 shares를 사용하였다.
    • 태스크 6개 모두 idle 코드가 없다고 가정하였다.

 

주요 전역 변수 값

  • sysctl_sched_cfs_bandwidth_slice
    • 디폴트 값은 5000 (us) = 5 (ms)
    • “/sys/fs/kernel/sched_cfs_bandwidth_slice_us” 파일로 설정
    • 로컬 풀의 요구에 따라 글로벌 풀(tg)로부터 로컬(per cfs_rq) 풀로 런타임을 빌려와서 할당해주는 기간
  • min_cfs_rq_runtime
    • 디폴트 값은 1,000,000 (ns) = 1 (ms)
    • 로컬 풀에서 최소 할당 받을 런타임
  • min_bandwidth_expiration
    • 디폴트 값은 2,000,000 (ns) = 2 (ms)
    • 최소 남은 period 만료 시각으로 이 기간 내에서는 slack 타이머를 활성화시키지 않는다.
  • cfs_bandwidth_slack_period
    • 디폴트 값은 5,000,000 (ns) = 5 (ms)
    • slack 타이머 주기

 

CFS Runtime

그룹내에서 CFS bandwidth를 사용 시 스로틀링을 위해 남은 quota(runtime) 산출에 사용했던 CFS runtime의 구현 방법들은 다음과 같이 진화하였다.

  • 1) cfs hard limits: cfs bandwidth 적용 초기에 구현된 방법
  • 2) hybrid global pool: 현재 커널에서 구현된 방법으로 cfs bandwidth v4에서 소개되었다.

 

Hybrid global pool

global runtime으로만 구현하게 되면 cpu가 많이 있는 시스템에서 각 cpu마다 동작하는 cfs 런큐간의 lock contension에 대한 부담이 매우커지는 약점이 있다. 또한 local cpu runtime으로만 구현하더라도 cfs 런큐 간에 남은 quota들을 확인하는 복잡한 relation이 발생하므로 소규모 smp 시스템에서만 적절하다고 볼 수 있다. 따라서 성능을 위해 로컬 및 글로벌의 하이브리드 버전을 구현하여 소개되었다.

  • global runtime pool
    • 글로벌 런타임 풀은 전역 변수 하나가 아니라 태스크 그룹별로 생성된다.
    • cfs bandwidth에서 글로벌 풀로 불리우기도 하며 cfs_bandwidth 구조체에 관련 멤버들을 갖는다.
    • 추적이 발생하는 곳이며 period 타이머에 의해 매 period 마다 리필(리프레쉬)된다.
  • local cpu runtime
    • 로컬 cpu 런타임은 태스크 그룹의 각 cpu 마다 존재한다.
    • cfs bandwidth에서 로컬 풀로 불리우기도 하며 cfs_rq 구조체에 cfs bandwidth 관련 멤버들을 갖는다.
    • 로컬 런타임에서 소비가 이루어지며 각각의 local cpu에 있는 cfs 런큐에서 발생하고 성능을 위해 lock을 사용하지 않는 장점이 있다.
    • period 만료 시각에 로컬 런타임이 모두 소비된 경우 이전 period 기간에 스로틀한 로컬 풀 위주로 할당을 한다. 할당 할 수 없는 상황에서는 스로틀 한다.
    • 로컬 런타임이 모두 소비된 경우 글로벌 런타임 풀에서 적정량(slice) 만큼을 빌려올 수 있다.

 

로컬 런타임의 소모는 다음과 같은 사례에서 발생한다. 자세한 것은 각 함수들에서 알아본다.

  • Case A) period 타이머 만료 시 스로틀된 로컬들 런타임 우선 분배
    • sched_cfs_period_timer() -> distribute_cfs_runtime()
  • Case B) 매 tick 마다 빈 로컬 런타임 최소 분배
    • update_curr() -> account_cfs_rq_runtime() -> assign_cfs_rq_runtime()
  • Case C) 스케줄 엔티티 디큐 시 글로벌 런큐로 반납 후 slack 타이머 가동시켜 다른 로컬에 분배
    • dequeue_entity() -> return_cfs_rq_runtime()

 

CFS Bandwidth 초기화

init_cfs_bandwidth()

kernel/sched/fair.c

void init_cfs_bandwidth(struct cfs_bandwidth *cfs_b) 
{
        raw_spin_lock_init(&cfs_b->lock);
        cfs_b->runtime = 0;
        cfs_b->quota = RUNTIME_INF;
        cfs_b->period = ns_to_ktime(default_cfs_period());

        INIT_LIST_HEAD(&cfs_b->throttled_cfs_rq);
        hrtimer_init(&cfs_b->period_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
        cfs_b->period_timer.function = sched_cfs_period_timer;
        hrtimer_init(&cfs_b->slack_timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL);
        cfs_b->slack_timer.function = sched_cfs_slack_timer;
}

cfs bandwidth를 초기화한다.

  • 코드 라인 4~6에서 글로벌 runtime을 0으로, quota 값은 무한대 값인 RUNTIME_INF(0xffffffff_ffffffff = -1)로, 그리고 period 값은 디폴트 cfs period 값(100,000,000ns=0.1s)를 period에 저장한다.
  • 코드 라인 8에서 스로틀드 리스트를 초기화한다.
  • 코드 라인 9~10에서 period hrtimer를 초기화하고 만료 시 호출되는 함수를 지정한다.
  • 코드 라인 11~12에서 slack hrtimer를 초기화하고 만료 시 호출되는 함수를 지정한다.

CFS quota 설정

tg_set_cfs_quota()

kernel/sched/core.c

int tg_set_cfs_quota(struct task_group *tg, long cfs_quota_us)
{
        u64 quota, period;

        period = ktime_to_ns(tg->cfs_bandwidth.period);
        if (cfs_quota_us < 0)
                quota = RUNTIME_INF;
        else
                quota = (u64)cfs_quota_us * NSEC_PER_USEC;

        return tg_set_cfs_bandwidth(tg, period, quota);
}

요청한 태스크 그룹에 cfs quota 값(us)을 나노초로 변경하여 설정하되 가능한 범위는 1ms ~ 1s 이다.

  • 코드 라인 5에서 cfs bandwidth에 설정되어 있는 period 값을 나노초 단위로 변환해온다.
  • 코드 라인 6~9에서 인수로 받은 us 단위의 quota 값이 0보다 작은 경우 스로틀링 하지 않도록 무제한으로 설정하고, 0보다 큰 경우 quota 값을 나노초 단위로 바꾼다.
  • 코드 라인 11에서 요청한 태스크 그룹에 period(ns) 및 quota(ns) 값을 설정한다.

 

CFS period 설정

tg_get_cfs_period()

kernel/sched/core.c

int tg_set_cfs_period(struct task_group *tg, long cfs_period_us)
{
        u64 quota, period;

        period = (u64)cfs_period_us * NSEC_PER_USEC;
        quota = tg->cfs_bandwidth.quota;

        return tg_set_cfs_bandwidth(tg, period, quota);
}

요청한 태스크 그룹에 cfs period 값(us)을 나노초로 변경하여 설정하되 최소 1ms 부터 설정 가능하다.

  • 코드 라인 5에서 인수로 받은 us 단위의 period 값을 나노초 단위로 변환한다.
  • 코드 라인 6에서 cfs bandwidth에 설정되어 있는 quota(ns) 값을 알아온다.
  • 코드 라인 7에서 요청한 태스크 그룹에 period(ns) 및 quota(ns) 값을 설정한다.

 

CFS quota 및 period 공통 설정

최대 및 최소 cfs quota 제한

kernel/sched/core.c

const u64 max_cfs_quota_period = 1 * NSEC_PER_SEC; /* 1s */
const u64 min_cfs_quota_period = 1 * NSEC_PER_MSEC; /* 1ms */

cfs quota의 설정은 1ms ~ 1s 범위에서 가능하게 제한된다.

 

tg_set_cfs_bandwidth()

요청한 태스크 그룹의 bandwidth 기능 유무를 설정한다. 처리되는 항목은 다음과 같다.

  • 요청 태스크 그룹에 period(ns) 값이 1ms 이상인 경우에 한하여 설정
  • 요청 태스크 그룹에 quota(ns) 값이 1ms ~ 1s 범위내인 경우에 한하여 설정
  • 전체 태스크 그룹의 quota 정수 비율을 재설정
  • quota 설정에 따라 cfs 밴드폭 기능을 활성화, 비활성화 또는 기존 상태 유지

kernel/sched/core.c

static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
{
        int i, ret = 0, runtime_enabled, runtime_was_enabled;
        struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;

        if (tg == &root_task_group)
                return -EINVAL;

        /*
         * Ensure we have at some amount of bandwidth every period.  This is
         * to prevent reaching a state of large arrears when throttled via
         * entity_tick() resulting in prolonged exit starvation.
         */
        if (quota < min_cfs_quota_period || period < min_cfs_quota_period)
                return -EINVAL;

        /*
         * Likewise, bound things on the otherside by preventing insane quota
         * periods.  This also allows us to normalize in computing quota
         * feasibility.
         */
        if (period > max_cfs_quota_period)
                return -EINVAL;

        /*
         * Prevent race between setting of cfs_rq->runtime_enabled and
         * unthrottle_offline_cfs_rqs().
         */
        get_online_cpus();
        mutex_lock(&cfs_constraints_mutex);
        ret = __cfs_schedulable(tg, period, quota);
        if (ret)
                goto out_unlock;
  • 코드 라인 6~7에서 요청한 태스크 그룹이 루트 태스크 그룹인 경우 period 및 quota 밴드폭 설정을 할 수 없어 -EINVAL 에러를 반환한다.
  • 코드 라인 14~15에서 요청한 ns 단위의 quota 및 period 값이 최소 값(1ms) 미만인 경우 -EINVAL 에러를 반환한다.
  • 코드 라인 22~23에서요청한 ns 단위의 period 값이 최대 값(1s)을 초과하는 경우 -EINVAL 에러를 반환한다.
  • 코드 라인 31~33에서 최상위 루트 태스크부터 전체 태스크 그룹을 순회하는 동안 위에서 아래로 내려가는 순서로 각 태스크 그룹의 quota 정수 비율을 설정한다.

 

        runtime_enabled = quota != RUNTIME_INF;
        runtime_was_enabled = cfs_b->quota != RUNTIME_INF;
        /*
         * If we need to toggle cfs_bandwidth_used, off->on must occur
         * before making related changes, and on->off must occur afterwards
         */
        if (runtime_enabled && !runtime_was_enabled)
                cfs_bandwidth_usage_inc();
        raw_spin_lock_irq(&cfs_b->lock);
        cfs_b->period = ns_to_ktime(period);
        cfs_b->quota = quota;

        __refill_cfs_bandwidth_runtime(cfs_b);
        /* restart the period timer (if active) to handle new period expiry */
        if (runtime_enabled && cfs_b->timer_active) {
                /* force a reprogram */
                __start_cfs_bandwidth(cfs_b, true);
        }
        raw_spin_unlock_irq(&cfs_b->lock);

        for_each_online_cpu(i) {
                struct cfs_rq *cfs_rq = tg->cfs_rq[i];
                struct rq *rq = cfs_rq->rq;

                raw_spin_lock_irq(&rq->lock);
                cfs_rq->runtime_enabled = runtime_enabled;
                cfs_rq->runtime_remaining = 0;

                if (cfs_rq->throttled)
                        unthrottle_cfs_rq(cfs_rq);
                raw_spin_unlock_irq(&rq->lock);
        }
        if (runtime_was_enabled && !runtime_enabled)
                cfs_bandwidth_usage_dec();
out_unlock:
        mutex_unlock(&cfs_constraints_mutex);
        put_online_cpus();

        return ret;
}
  • 코드 라인 1에서 quota 값이 무제한 설정이 아니면 runtime_enable에 true가 대입된다.
  • 코드 라인 2에서 기존 quota 값이 무제한 설정이 아니면 runtime_was_enable에 true가 대입된다.
  • 코드 라인 7~8에서 quota가 무제한이었다가 설정된 경우 cfs bandwidth 기능이 동작함을 설정한다.
  • 코드 라인 10~11에서 cfs bandwidth period와 quota에 요청한 값을 저장한다. (ns 단위)
  • 코드 라인 13에서 cfs 밴드폭을 리필(리프레쉬)한다.
  • 코드 라인 15~18에서 cfs bandwidth 기능이 enable 되었고 cfs bandwidth 타이머도 enable된 경우 cfs bandwidth 기능을 시작하기 위해 cfs 밴드폭 타이머를 가동한다.
  • 코드 라인 21~32에서 cpu 수만큼 루프를 돌며 cfs 런큐에 runtime_enabled를 설정하고 runtime_remaining에 0을 대입하여 초기화한다. cfs 런큐가 이미 스로틀된 경우 언스로틀 한다.
  • 코드 라인 33~34에서 quota가 설정되었다가 무제한으로 된 경우 cfs bandwidth 기능을 disable한다.

 

__cfs_schedulable()

kernel/sched/core.c

static int __cfs_schedulable(struct task_group *tg, u64 period, u64 quota)
{               
        int ret;
        struct cfs_schedulable_data data = {
                .tg = tg,
                .period = period,
                .quota = quota,
        };
 
        if (quota != RUNTIME_INF) { 
                do_div(data.period, NSEC_PER_USEC);
                do_div(data.quota, NSEC_PER_USEC);
        }
        
        rcu_read_lock();
        ret = walk_tg_tree(tg_cfs_schedulable_down, tg_nop, &data);
        rcu_read_unlock();

        return ret;
}

최상위 루트 태스크부터 전체 태스크 그룹을 순회하는 동안 위에서 아래로 내려가는 순서로 quota 정수 비율을 설정한다. 성공하면 0을 반환한다.

  • 코드 라인 4~8에서 cfs 스케줄 데이터 구조체에 태스크 그룹과 ns 단위의 period와 quota 값을 대입한다.
  • 코드 라인 10~13에서 period와 quota 값을 us 단위로 변환한다.
  • 코드 라인 15~17에서 최상위 루트 태스크부터 전체 태스크 그룹을 순회하는 동안 위에서 아래로 내려가는 순서로 quota 정수 비율을 설정한다.

 

walk_tg_tree()

kernel/sched/sched.h

/*
 * Iterate the full tree, calling @down when first entering a node and @up when
 * leaving it for the final time.
 *      
 * Caller must hold rcu_lock or sufficient equivalent.
 */             
static inline int walk_tg_tree(tg_visitor down, tg_visitor up, void *data)
{       
        return walk_tg_tree_from(&root_task_group, down, up, data);
}

태스크 그룹 트리에서 최상위 루트 태스크부터 전체 태스크 그룹을 순회하는 동안 아래로 내려가면 down 함수를 호출하고 위로 올라가면 up 함수를 호출한다. 호출한 함수가 중간에 에러가 발생하면 그 값을 반환하고 처리를 중단한다.

 

다음 그림은 __cfs_schedulabel() 함수를 호출할 때 각 태스크 그룹을 아래로 내려갈 때마다 tg_cfs_schedulable_down()을 호출하는 모습을 보여준다.

  • 호출 순서는 번호 순이며 하향에 대한 호출 순서만 나열하면 1-D -> 2-D -> 4-D -> 5-D -> 7-D -> 10-D 순서이다.

 

tg_cfs_schedulable_down()

kernel/sched/core.c

static int tg_cfs_schedulable_down(struct task_group *tg, void *data)
{
        struct cfs_schedulable_data *d = data;
        struct cfs_bandwidth *cfs_b = &tg->cfs_bandwidth;
        s64 quota = 0, parent_quota = -1;

        if (!tg->parent) {
                quota = RUNTIME_INF;
        } else {
                struct cfs_bandwidth *parent_b = &tg->parent->cfs_bandwidth;

                quota = normalize_cfs_quota(tg, d);
                parent_quota = parent_b->hierarchical_quota;

                /*
                 * ensure max(child_quota) <= parent_quota, inherit when no
                 * limit is set
                 */
                if (quota == RUNTIME_INF)
                        quota = parent_quota;
                else if (parent_quota != RUNTIME_INF && quota > parent_quota)
                        return -EINVAL;
        }
        cfs_b->hierarchical_quota = quota;

        return 0;
}

요청한 태스크 그룹에 period에 대한 quota 정수 비율을 설정한다. 에러가 없으면 0을 반환한다.

  • 코드 라인 3에서 인수 data에서 us 단위의 period 및 quota가 담긴 구조체 포인터를 가져온다.
  • 코드 라인 7~8에서 부모가 없는 최상위 태스크 그룹인 경우 스로틀링 하지 않도록 quota에 무제한을 설정한다.
  • 코드 라인 12에서 period에 대한 quota 정수 비율을 산출한다. (예: 정수 1M=100%, 256K=25%)
  • 코드 라인 13에서 부모 quota 정수 비율을 알아온다.
  • 코드 라인 19~20에서 산출된 quota 정수 비율이 무제한인 경우 부모 quota 비율을 상속하여 사용한다.
  • 코드 라인 21~22에서 부모 quota 비율이 무제한이 아니고 산출된 quota 비율이 부모 quota 비율보다 큰 경우 -EINVAL 에러를 반환한다.
  • 코드 라인 24~26에서 요청한 태스크 그룹의 quota 비율을 설정하고 성공(0)을 반환한다.
    • 계층적으로 관리되는 태스크 그룹의 quota 정수 비율은 hierarchical_quota에 저장한다.

 

CFS quota 정수 비율 산출

normalize_cfs_quota()

kernel/sched/core.c

/*
 * normalize group quota/period to be quota/max_period
 * note: units are usecs
 */
static u64 normalize_cfs_quota(struct task_group *tg,
                               struct cfs_schedulable_data *d)
{
        u64 quota, period;

        if (tg == d->tg) {
                period = d->period;
                quota = d->quota;
        } else {
                period = tg_get_cfs_period(tg);
                quota = tg_get_cfs_quota(tg);
        }

        /* note: these should typically be equivalent */
        if (quota == RUNTIME_INF || quota == -1)
                return RUNTIME_INF;

        return to_ratio(period, quota);
}

period에 대한 quota 비율을 정수로 반환한다. (예: 정수 1M=100%, 256K=25%)

  • 코드 라인 10~12에서 요청한 태스크 그룹과 스케줄 데이터의 태스크 그룹이 동일한 경우 us 단위인 스케줄 데이터의 period와 quota 값을 사용한다.
  • 코드 라인 13~16에서 동일하지 않은 경우 태스크 그룹의 period 값과 quota 값을 us 단위로 변환하여 가져온다.
  • 코드 라인 19~20에서 quota가 무제한 설정된 경우 무제한(0xffffffff_ffffffff) 값을 반환한다.
  • 코드 라인 22에서 quota * 1M(1 << 20) / period 값을 반환한다.

 

tg_get_cfs_quota()

kernel/sched/core.c

long tg_get_cfs_quota(struct task_group *tg)
{
        u64 quota_us;

        if (tg->cfs_bandwidth.quota == RUNTIME_INF)
                return -1;

        quota_us = tg->cfs_bandwidth.quota;
        do_div(quota_us, NSEC_PER_USEC);

        return quota_us;
}

태스크 그룹의 cfs quota를 us 단위로 반환한다. 무제한 설정된 경우 -1을 반환한다.

 

tg_get_cfs_period()

kernel/sched/core.c

long tg_get_cfs_period(struct task_group *tg)
{
        u64 cfs_period_us;

        cfs_period_us = ktime_to_ns(tg->cfs_bandwidth.period);
        do_div(cfs_period_us, NSEC_PER_USEC);

        return cfs_period_us;
}

태스크 그룹의 cfs period를 us 단위로 반환한다.

 

CFS Throttling

check_enqueue_throttle()

kernel/sched/fair.c

/*
 * When a group wakes up we want to make sure that its quota is not already
 * expired/exceeded, otherwise it may be allowed to steal additional ticks of
 * runtime as update_curr() throttling can not not trigger until it's on-rq.
 */
static void check_enqueue_throttle(struct cfs_rq *cfs_rq)
{
        if (!cfs_bandwidth_used())
                return;

        /* an active group must be handled by the update_curr()->put() path */
        if (!cfs_rq->runtime_enabled || cfs_rq->curr)
                return;

        /* ensure the group is not already throttled */
        if (cfs_rq_throttled(cfs_rq))
                return;

        /* update runtime allocation */
        account_cfs_rq_runtime(cfs_rq, 0);
        if (cfs_rq->runtime_remaining <= 0)
                throttle_cfs_rq(cfs_rq);
}

현재 그룹의 cfs 런큐에서 quota 만큼의 실행이 끝나고 남은 런타임이 없으면 스로틀한다.

  • 코드 라인 8~9에서 cfs bandwidth 구성이 사용되지 않으면 함수를 빠져나간다.
  • 코드 라인 12~13에서 무제한 quota 설정이거나 cfs 런큐에서 동작 중인 태스크가 있으면 함수를 빠져나간다.
  • 코드 라인 16~17에서 cfs 런큐가 이미 스로틀된 경우 함수를 빠져나간다.
  • 코드 라인 20~22에서 cfs 런큐의 런타임을 산출하고 런타임이 남아 있지 않는 경우 스로틀한다.

 

check_enqueue_throttle() 함수에서 다음 그림의 조건들을 만족하면 cfs 런큐를 스로틀 하는 모습을 보여준다.

 

throttle_cfs_rq()

kernel/sched/fair.c

static void throttle_cfs_rq(struct cfs_rq *cfs_rq)
{
        struct rq *rq = rq_of(cfs_rq);
        struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
        struct sched_entity *se;
        long task_delta, dequeue = 1;

        se = cfs_rq->tg->se[cpu_of(rq_of(cfs_rq))];

        /* freeze hierarchy runnable averages while throttled */
        rcu_read_lock();
        walk_tg_tree_from(cfs_rq->tg, tg_throttle_down, tg_nop, (void *)rq);
        rcu_read_unlock();

        task_delta = cfs_rq->h_nr_running;
        for_each_sched_entity(se) {
                struct cfs_rq *qcfs_rq = cfs_rq_of(se);
                /* throttled entity or throttle-on-deactivate */
                if (!se->on_rq)
                        break;

                if (dequeue)
                        dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
                qcfs_rq->h_nr_running -= task_delta;

                if (qcfs_rq->load.weight)
                        dequeue = 0;
        }

        if (!se)
                sub_nr_running(rq, task_delta);

        cfs_rq->throttled = 1;
        cfs_rq->throttled_clock = rq_clock(rq);
        raw_spin_lock(&cfs_b->lock);
        /*
         * Add to the _head_ of the list, so that an already-started
         * distribute_cfs_runtime will not see us
         */
        list_add_rcu(&cfs_rq->throttled_list, &cfs_b->throttled_cfs_rq);
        if (!cfs_b->timer_active)
                __start_cfs_bandwidth(cfs_b, false);
        raw_spin_unlock(&cfs_b->lock);
}

요청한 cfs 런큐를 스로틀링한다.

  • 코드 라인 3~4에서 요청한 cfs 런큐에 해당하는 런큐와 태스크 그룹의 cfs bandwidth을알아온다.
  • 코드 라인 8에서 요청한 cfs 런큐에 해당하는 태스크 그룹용 스케줄 엔티티를 알아온다.
  • 코드 라인 11~13에서 요청한 cfs 런큐에 해당하는 태스크 그룹부터 하위의 태스크 그룹 전체를 순회하며 스로틀 되는 동안 계층적인 러너블 평균의 산출을 멈추게 한다.
    • 각 태스크 그룹의 cfs 런큐의 스로틀 카운터를 증가시키고 처음인 경우 런큐의 clock_task를 cfs 런큐의 throttled_clock_task에 대입한다.
  • 코드 라인 15에서 요청한 cfs 런큐의 동작중인 active 태스크의 수를 알아온다.
  • 코드 라인 16~20에서 요청한 cfs 런큐용 스케줄 엔티티부터 최상위 스케줄 엔티티까지 순회하며 해당 스케줄 엔티티가 런큐에 올라가 있지 않으면 순회를 멈춘다.
  • 코드 라인 22~24에서 dequeue 요청이 있을 때 현재 스케줄 엔티티를 디큐하여 sleep 하게 하고 동작 중인 태스크 수를 1 감소시킨다.
  • 코드 라인 26~27에서 현재 스케줄 엔티티를 담고 있는 cfs 런큐의 로드 weight이 0이 아니면 순회 중 다음 부모 스케줄 엔티티에 대해 dequeue를 요청하도록 dequeue에 0을 설정한다.
  • 코드 라인 30~31에서 순회가 중단된 적이 없으면 런큐의 active 태스크 수를 task_delta 만큼 감소시킨다.
    • sub_nr_running()
      • rq->nr_running -= count
  • 코드 라인 33~34에서 cfs 런큐에 스로틀되었음을 알리고 스로틀된 시각을 기록한다.
  • 코드 라인 40에서 cfs bandwidth 의 throttled_cfs_rq 리스트에 cfs 런큐의 스로틀된 cfs 런큐를 추가한다.
  • 코드 라인 41~42에서 cfs bandwidth 기능이 동작하도록 타이머를 동작시킨다.

 

다음 그림은 요청한 cfs 런큐에 대해 스로틀링을 할 때 처리되는 모습을 보여준다.

 

walk_tg_tree_from()

kernel/sched/core.c

/*
 * Iterate task_group tree rooted at *from, calling @down when first entering a
 * node and @up when leaving it for the final time.
 *
 * Caller must hold rcu_lock or sufficient equivalent.
 */
int walk_tg_tree_from(struct task_group *from,
                             tg_visitor down, tg_visitor up, void *data)
{
        struct task_group *parent, *child;
        int ret;

        parent = from;

down:
        ret = (*down)(parent, data);
        if (ret)
                goto out;
        list_for_each_entry_rcu(child, &parent->children, siblings) {
                parent = child;
                goto down;

up:
                continue;
        }
        ret = (*up)(parent, data);
        if (ret || parent == from)
                goto out;

        child = parent;
        parent = parent->parent;
        if (parent)
                goto up;
out:
        return ret;
}

태스크 그룹 트리에서 요청한 태스크 그룹 이하의 태스크 그룹을 순회하는 동안 아래로 내려가면 down 함수를 호출하고 위로 올라가면 up 함수를 호출한다. 호출한 함수가 중간에 에러가 발생하면 그 값을 반환하고 처리를 중단한다. 에러가 없으면 0을 반환한다.

  • 코드 라인 16~18에서 상위 태스크 그룹부터 인수로 받은 down() 함수를 호출한다.
    • throttle_cfs_rq() -> tg_throttle_down() 함수를 호출한다.
    • unthrottle_cfs_rq() -> tg_nop() 함수를 호출하여 아무 것도 수행하지 않는다.
  • 코드 라인 19에서 parent의 자식들에 대해 좌에서 우로 루프를 돈다. 자식이 없으면 루프를 벗어난다.
  • 코드 라인 20~21에서 선택된 자식으로 down 레이블로 이동한다.
  • 코드 라인 23~25에서 다시 자식들에 대해 계속 처리한다.
  • 코드 라인 26~28에서 하위 태스크 그룹부터 인수로 받은 up() 함수를 호출한다.
    • throttle_cfs_rq() -> tg_nop() 함수를 호출하여 아무 것도 수행하지 않는다.
    • unthrottle_cfs_rq() -> tg_unthrottle_up() 함수를 호출한다.
  • 코드 라인 30~33에서 parent의 부모를 선택하고 부모가 있으면 up 레이블로 이동한다.

 

다음 그림은 walk_tg_tree_from() 함수가 1번 down 함수 호출부터 12번 up 함수 호출하는 것 까지 트리를 순회하는 모습을 보여준다.

 

tg_throttle_down()

kernel/sched/fair.c

static int tg_throttle_down(struct task_group *tg, void *data)
{
        struct rq *rq = data;
        struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];

        /* group is entering throttled state, stop time */
        if (!cfs_rq->throttle_count)
                cfs_rq->throttled_clock_task = rq_clock_task(rq);
        cfs_rq->throttle_count++;

        return 0;
}

요청 태스크 그룹에 대해 스로틀 되는 동안 러너블 평균의 산출을 멈추게 한다.

  • 요청 태스크 그룹의 cfs 런큐의 스로틀 카운터를 증가시키고 처음인 경우 런큐의 clock_task를 cfs 런큐의 throttled_clock_task에 대입한다.
  • 코드 라인 3~4에서 두 번째 인수로 받은 런큐의 cpu 번호를 알아와서 요청 태스크 그룹의 cfs 런큐를 알아온다.
  • 코드 라인 7~8에서 처음 스로틀링에 들어가는 경우 런큐의 clock_task를 cfs 런큐의 throttled_clock_task에 대입한다.
  • 코드 라인 9에서 cfs 런큐의 스로틀 카운터를 1 증가시킨다.

 

tg_unthrottle_up()

kernel/sched/fair.c

/* updated child weight may affect parent so we have to do this bottom up */
static int tg_unthrottle_up(struct task_group *tg, void *data)
{
        struct rq *rq = data; 
        struct cfs_rq *cfs_rq = tg->cfs_rq[cpu_of(rq)];

        cfs_rq->throttle_count--;
#ifdef CONFIG_SMP
        if (!cfs_rq->throttle_count) {
                /* adjust cfs_rq_clock_task() */
                cfs_rq->throttled_clock_task_time += rq_clock_task(rq) -
                                             cfs_rq->throttled_clock_task;
        }
#endif

        return 0;
}

요청 태스크 그룹에 대해 스로틀이 완료되었으므로 러너블 평균의 산출을 재개한다. 로드 weight들은 부모 태스크 그룹에게 영향을 끼치므로 아래에서 위 순서로 적용해야 한다.

  • 요청 태스크 그룹의 cfs 런큐의 스로틀 카운터를 감소시키고 처음인 경우 런큐의 clock_task를 cfs 런큐의 throttled_clock_task에 대입한다.
  • 코드 라인 4~5에서 두 번째 인수로 받은 런큐의 cpu 번호를 알아와서 요청 태스크 그룹의 cfs 런큐를 알아온다.
  • 코드 라인 7에서 cfs 런큐의 스로틀 카운터를 1 감소시킨다.
  • 코드 라인 8~14에서 smp 시스템에서 스로틀 카운터가 0인 경우 런큐의 clock_task에서 cfs 런큐의 throttled_clock_task를 뺀 시간을 cfs 런큐의 throttled_clock_task_time에 추가한다.

 

unthrottle_cfs_rq()

kernel/sched/fair.c

void unthrottle_cfs_rq(struct cfs_rq *cfs_rq)
{
        struct rq *rq = rq_of(cfs_rq);
        struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
        struct sched_entity *se;
        int enqueue = 1;
        long task_delta;

        se = cfs_rq->tg->se[cpu_of(rq)];

        cfs_rq->throttled = 0;

        update_rq_clock(rq);

        raw_spin_lock(&cfs_b->lock);
        cfs_b->throttled_time += rq_clock(rq) - cfs_rq->throttled_clock;
        list_del_rcu(&cfs_rq->throttled_list);
        raw_spin_unlock(&cfs_b->lock);

        /* update hierarchical throttle state */
        walk_tg_tree_from(cfs_rq->tg, tg_nop, tg_unthrottle_up, (void *)rq);

        if (!cfs_rq->load.weight)
                return;

        task_delta = cfs_rq->h_nr_running;
        for_each_sched_entity(se) {
                if (se->on_rq)
                        enqueue = 0;

                cfs_rq = cfs_rq_of(se);
                if (enqueue)
                        enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP);
                cfs_rq->h_nr_running += task_delta;

                if (cfs_rq_throttled(cfs_rq))
                        break;
        }

        if (!se)
                add_nr_running(rq, task_delta);

        /* determine whether we need to wake up potentially idle cpu */
        if (rq->curr == rq->idle && rq->cfs.nr_running)
                resched_curr(rq);
}

요청한 cfs 런큐를 언스로틀링한다.

  • 코드 라인 9에서 요청한 cfs 런큐에 해당하는 런큐와 태스크 그룹의 cfs bandwidth을알아온다.
  • 코드 라인 11에서 cfs 런큐의 throttled를 0으로 하여 스로틀링을 해제한 것으로 설정한다.
  • 코드 라인 16에서 글로벌 풀에 스로틀된 시간을 기록한다.
  • 코드 라인 17에서 로컬 풀을 스로틀 리스트에서 제거한다.
  • 코드 라인 21에서 각 태스크 그룹의 하위 그룹들에 대해 bottom-up 방향으로 각 로컬 풀을 언스로틀하도록 요청한다.
  • 코드 라인 23~24에서 현재 로컬 풀의 로드 weight이 0이면 부모에 영향을 끼치지 않으므로 더이상 처리하지 않고 함수를 빠져나간다.
  • 코드 라인 26에서 task_delta에 요청한 cfs 런큐에서 동작중인 active 태스크 수를 알아온다.
  • 코드 라인 27~29에서 요청한 cfs 런큐용 스케줄 엔티티부터 최상위 스케줄 엔티티까지 순회하며 해당 스케줄 엔티티가 런큐에 올라가 있는 상태이면 enqueue에 0을 대입하여 엔큐를 못하게 설정한다.
  • 코드 라인 31~33에서 enqueue를 못하게 하지 않은 경우 스케줄 엔티티의 wakeup 플래그로 엔티티를 엔큐한다.
  • 코드 라인 34에서 순회중인 스케줄 엔티티의 cfs 런큐 이하의 active 태스크 수에 읽어온 task_delta를 추가한다.
  • 코드 라인 36~37에서 cfs 런큐가 스로틀된 적 있으면 루프를 빠져나간다.
  • 코드 라인 40~41에서 최상위 스케줄 엔티티(루트 태스크 그룹에 연결된)까지 루프를 다 돌은 경우 런큐에 task_delta를 추가한다.
  • 코드 라인 44~45에서 현재 태스크가 idle 중이면서 최상위 cfs 런큐에서 동작중인 스케줄 엔티티가 있으면 리스케줄 요청 플래그를 설정한다.

 

다음 그림은 여러 가지 clock에 대해 동작되는 모습을 보여준다.

  • 스로틀링 시간 역시 rq->clock에 동기되는 time 누적과 rq->clock_task를 사용한 task_time 누적으로 나뉘어 관리된다.
  • rq->clock에서 irq 처리 부분만 제외시킨 부분이 rq->clock_task 이다.
  • 그러나 CONFIG_IRQ_TIME_ACCOUNTING 커널 옵션을 사용하지 않으면 irq 소요시간을 측정하지 않으므로 이러한 경우에는 rq->clock과 rq->clock_task가 동일하게 된다.

 

 

CFS Runtime 최소 slice 할당

account_cfs_rq_runtime()

kernel/sched/fair.c

static __always_inline
void account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
{
        if (!cfs_bandwidth_used() || !cfs_rq->runtime_enabled)
                return;

        __account_cfs_rq_runtime(cfs_rq, delta_exec);
}

글로벌 런타임에서 최소 slice 만큼을 차용하여 로컬 런타임을 할당한다. 만일 글로벌 런타임이 모두 소비된 경우 더 이상 로컬 런타임에 할당하지 않고 곧바로 리스케줄 요청 플래그를 설정한다..

참고: sched: Accumulate per-cfs_rq cpu usage and charge against bandwidth

 

__account_cfs_rq_runtime()

kernel/sched/fair.c

static void __account_cfs_rq_runtime(struct cfs_rq *cfs_rq, u64 delta_exec)
{
        /* dock delta_exec before expiring quota (as it could span periods) */
        cfs_rq->runtime_remaining -= delta_exec;
        expire_cfs_rq_runtime(cfs_rq);

        if (likely(cfs_rq->runtime_remaining > 0))
                return;

        /*
         * if we're unable to extend our runtime we resched so that the active
         * hierarchy can be throttled
         */
        if (!assign_cfs_rq_runtime(cfs_rq) && likely(cfs_rq->curr))
                resched_curr(rq_of(cfs_rq));
}

로컬 런타임이 모두 소비된 경우 글로벌 런타임에서 최소 slice 만큼을 차용하여 로컬 런타임을 할당한다. 만일 글로벌 런타임이 모두 소비된 경우 더 이상 로컬 런타임에 할당하지 않고 곧바로 리스케줄 요청 플래그를 설정한다.

  • 코드 라인 4에서 로컬 런타임 잔량에 요청한 delta 실행시간을 뺀다.
    • 매 스케줄 틱마다 update_curr() 함수를 통해 이 루틴이 불리는데 실행되었던 시간 만큼을 로컬 런타임에서 소모시킨다.
  • 코드 라인 5에서 부적절한 로컬 런타임 만료 시각이 발생하면 만료된 것으로 처리한다.
  • 코드 라인 7~8에서 로컬 runtime_remaining이 아직 남아 있으면 함수를 빠져나간다.
  • 코드 라인 14~15에서 로컬 런타임의 할당이 실패하고 높은 확률로 cfs 런큐에서 태스크가 동작 중인 경우 리스케줄 요청 플래그를 설정한다.

 

expire_cfs_rq_runtime()

kernel/sched/fair.c

/*
 * Note: This depends on the synchronization provided by sched_clock and the
 * fact that rq->clock snapshots this value.
 */
static void expire_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
        struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);

        /* if the deadline is ahead of our clock, nothing to do */
        if (likely((s64)(rq_clock(rq_of(cfs_rq)) - cfs_rq->runtime_expires) < 0))
                return;

        if (cfs_rq->runtime_remaining < 0)
                return;

        /*
         * If the local deadline has passed we have to consider the
         * possibility that our sched_clock is 'fast' and the global deadline
         * has not truly expired.
         *
         * Fortunately we can check determine whether this the case by checking
         * whether the global deadline has advanced. It is valid to compare
         * cfs_b->runtime_expires without any locks since we only care about
         * exact equality, so a partial write will still work.
         */

        if (cfs_rq->runtime_expires != cfs_b->runtime_expires) {
                /* extend local deadline, drift is bounded above by 2 ticks */
                cfs_rq->runtime_expires += TICK_NSEC;
        } else {
                /* global deadline is ahead, expiration has passed */
                cfs_rq->runtime_remaining = 0;
        }
}

부적절한 로컬 런타임 만료 시각이 발생하면 만료된 것으로 처리한다.

  • 코드 라인 7에서 요청한 cfs 런큐의 태스크 그룹에 있는 글로벌 bandwidth을 알아온다.
  • 코드 라인 10~11에서 현재 시각이 아직 로컬 런타임 만료 시각에 도래하지 않은 경우 함수를 빠져나간다.
  • 코드 라인 13~14에서 로컬 런타임 잔량이 0 미만인 경우 함수를 빠져나간다.
  • 코드 라인 27~33에서 로컬 런타임 만료시각이 글로벌 런타임 만료시각과 다른 경우 로컬 런타임 만료 시각을 1 tick 만큼 연장한다. 그렇지 않은 경우 로컬 런타임 잔량을 0으로 만든다.
    • lock 사용을 회피하기 위해 로컬 만료 시각을 사용하는데 혹시라도 글로벌 만료 시각보다 로컬 만료 시각이 먼저 도래하는 경우 로컬 만료 시각을 1 tick씩 연장한다.

 

assign_cfs_rq_runtime()

kernel/sched/fair.c

/* returns 0 on failure to allocate runtime */
static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
        struct task_group *tg = cfs_rq->tg;
        struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(tg);
        u64 amount = 0, min_amount, expires;

        /* note: this is a positive sum as runtime_remaining <= 0 */
        min_amount = sched_cfs_bandwidth_slice() - cfs_rq->runtime_remaining;

        raw_spin_lock(&cfs_b->lock);
        if (cfs_b->quota == RUNTIME_INF)
                amount = min_amount;
        else {
                /*
                 * If the bandwidth pool has become inactive, then at least one
                 * period must have elapsed since the last consumption.
                 * Refresh the global state and ensure bandwidth timer becomes
                 * active.
                 */
                if (!cfs_b->timer_active) {
                        __refill_cfs_bandwidth_runtime(cfs_b);
                        __start_cfs_bandwidth(cfs_b, false);
                }

                if (cfs_b->runtime > 0) {
                        amount = min(cfs_b->runtime, min_amount);
                        cfs_b->runtime -= amount;
                        cfs_b->idle = 0;
                }
        }
        expires = cfs_b->runtime_expires;
        raw_spin_unlock(&cfs_b->lock);

        cfs_rq->runtime_remaining += amount;
        /*
         * we may have advanced our local expiration to account for allowed
         * spread between our sched_clock and the one on which runtime was
         * issued.
         */
        if ((s64)(expires - cfs_rq->runtime_expires) > 0)
                cfs_rq->runtime_expires = expires;

        return cfs_rq->runtime_remaining > 0;
}

글로벌 런타임에서 최소 slice 만큼을 차용하여 로컬 런타임을 할당한다. 로컬 런타임 할당이 실패한 경우 0을 반환한다.

  • 코드 라인 9에서 로컬 런타임이 다 소진된 상태에서 글로벌 런타임 풀에서 빌릴 시간을 결정한다. 글로벌 slice – 로컬 잔여 런타임을 min_amount에 대입한다.
    • 로컬 잔여 런타임이 다 소진되어 0이거나 음수인 경우에만 이 함수에 진입되었다.
    • 로컬 잔여 런타임이 다 소모되어 0인 경우 글로벌 slice(디폴트 5ms)를 빌려올 값으로 사용한다.
    • 로컬 잔여 런타임이 오버 소모되어 음수인 경우 오버 소모된 양은 뺀 글로벌 slice(디폴트 5ms)를 빌려올 값으로 사용한다.
  • 코드 라인 12~13에서 quota 설정이 무한대인 경우 빌려올 양은 항상 글로벌 slice 기간으로 고정된다.
  • 코드 라인 14~24에서 quota 설정이 있는 경우 cfs 밴드폭 타이머가 active 되지 않으면 cfs 밴드폭 런타임을 리필하고 타이머를 가동시킨다.
  • 코드 라인 26~30에서 글로벌 런타임에서 빌려올 기간을 뺀다. 만일 글로벌 런타임이 0보다 작아지면 0으로 제한한다.
    • 예) cfs_b->runtime=3ms이고 빌릴 값=5ms인 경우 cfs_b->runtime=0이되고 빌릴양은 3ms이다.
    • 예) cfs_b->runtime=10ms이고 빌릴 값=5ms인 경우 cfs_b->runtime=5가되고 빌릴양은 5ms이다.
  • 코드 라인 35에서 로컬 런타임 소비 잔량에 글로벌 런타임에서 빌려온 량을 추가한다.
  • 코드 라인 41~42에서 글로벌 런타임 만료 시각이 로컬 런타임 만료 시각보다 나중인 경우  로컬 런타임 만료 시각을 글로벌 런타임 만료 시각과 동일하게 설정한다.
  • 코드 라인 44에서 로컬 풀의 잔여 런타임이 있는지 여부를 반환한다.

 

다음 그림은 스케줄 tick이 발생하여 delta 실행 시간을 로컬 런타임 풀에서 소모시키고 소모 시킬 로컬 런타임이 없으면 slice 만큼의 런타임을 글로벌 런타임에서 빌려오는 것을 보여준다.

 

sched_cfs_bandwidth_slice()

kernel/sched/fair.c

static inline u64 sched_cfs_bandwidth_slice(void)
{
        return (u64)sysctl_sched_cfs_bandwidth_slice * NSEC_PER_USEC;
}

cfs bandwidth slice 값을 나노초 단위로 반환한다.

 

/*
 * Amount of runtime to allocate from global (tg) to local (per-cfs_rq) pool
 * each time a cfs_rq requests quota.
 *
 * Note: in the case that the slice exceeds the runtime remaining (either due
 * to consumption or the quota being specified to be smaller than the slice)
 * we will always only issue the remaining available time.
 *
 * default: 5 msec, units: microseconds
  */
unsigned int sysctl_sched_cfs_bandwidth_slice = 5000UL;
  • 매번 cfs 런큐가 요청하는 quota 마다 태스크 그룹의 글로벌에서 로컬 cfs 런큐 풀로 할당해줄 수 있는 runtime
  • “/proc/sys/kernel/sched_cfs_bandwidth_slice_us” -> 디폴트 값은 5000 (us)

 

__refill_cfs_bandwidth_runtime()

이 함수는 다음 그림과 같이 두 가지의 함수에서 호출되어 사용되는 것을 보여준다.

  • 매 period 타이머 만료 시에 sched_cfs_period_timer() 함수를 통해 호출된다.
  • assign_cfs_rq_runtime() 함수를 통해 호출된다.

 

kernel/sched/fair.c

/*
 * Replenish runtime according to assigned quota and update expiration time.
 * We use sched_clock_cpu directly instead of rq->clock to avoid adding
 * additional synchronization around rq->lock.
 *
 * requires cfs_b->lock
 */
void __refill_cfs_bandwidth_runtime(struct cfs_bandwidth *cfs_b)
{
        u64 now;

        if (cfs_b->quota == RUNTIME_INF)
                return;

        now = sched_clock_cpu(smp_processor_id());
        cfs_b->runtime = cfs_b->quota;
        cfs_b->runtime_expires = now + ktime_to_ns(cfs_b->period);
}

글로벌 풀의 런타임을 quota 만큼으로 설정하고 런타임 만료 시각도 재설정한다.

  • 코드 라인 12~13에서 quota가 무제한으로 설정된 경우 runtime 계산이 필요 없으므로 함수를 빠져나간다.
  • 코드 라인 16에서 cfs bandwidth runtime을 quota 값으로 리필한다.
  • 코드 라인 17에서 runtime 만료 시각을 현재  스케줄 클럭으로 부터 period 나노초 후로 설정한다.

 

글로벌 런타임 풀로 반납 후 처리

return_cfs_rq_runtime()

kernel/sched/fair.c

static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
        if (!cfs_bandwidth_used())
                return;

        if (!cfs_rq->runtime_enabled || cfs_rq->nr_running)
                return;

        __return_cfs_rq_runtime(cfs_rq);
}

cfs 스케줄러에서 스케줄 엔티티가 디큐될 때 이 함수가 호출되면 남은 로컬 런타임을 회수하여 글로벌 풀로 반납한다. 그런 후에 5ms 주기의 slack 타이머를 가동시켜서 스로틀된 다른 태스크에게 런타임을 할당해준다.

 

__return_cfs_rq_runtime()

kernel/sched/fair.c

/* we know any runtime found here is valid as update_curr() precedes return */
static void __return_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
        struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
        s64 slack_runtime = cfs_rq->runtime_remaining - min_cfs_rq_runtime;

        if (slack_runtime <= 0)
                return;

        raw_spin_lock(&cfs_b->lock);
        if (cfs_b->quota != RUNTIME_INF &&
            cfs_rq->runtime_expires == cfs_b->runtime_expires) {
                cfs_b->runtime += slack_runtime;

                /* we are under rq->lock, defer unthrottling using a timer */
                if (cfs_b->runtime > sched_cfs_bandwidth_slice() &&
                    !list_empty(&cfs_b->throttled_cfs_rq))
                        start_cfs_slack_bandwidth(cfs_b);
        }
        raw_spin_unlock(&cfs_b->lock);

        /* even if it's not valid for return we don't want to try again */
        cfs_rq->runtime_remaining -= slack_runtime;
}
  • 코드 라인 5~8에서 로컬 런타임으로부터 글로벌 풀로 반납할 잔량을 구한다. 반납할 량이 0보다 적으면 함수를 빠져나간다.
    • 로컬 런타임의 잔량 – 최소 런타임(1ms)
  • 코드 라인 11~13에서 quota가 설정되었고 로컬 런타임 만료 시각과 글로벌 런타임 만료 시각이 동일한 경우 글로벌 풀에 반납한다.
  • 코드 라인 16~18에서 글로벌 풀의 런타임이 slice 보다 크고 스로틀되어 있는 로컬 풀이 있으면 slack 타이머를 가동한다.
  • 코드 라인 23에서 로컬 런타임 잔량을 반납한 양 만큼 빼서 갱신한다.

 

 

CFS Bandwidth 타이머

 

다음 그림은 cfs bandwidth에 대한 두 개의 타이머에 대한 함수 호출 관계를 보여준다.

  • period 타이머 주요 기능
    • period 주기마다 만료되어 호출된다.
    • 글로벌 런타임을 재충전(refill) 한다.
    • 스로틀 cfs 런큐에 우선 분배한다.
  • slack 타이머 주요 기능
    • 태스크 dequeue 시 5ms 후에 만료되어 호출된다.
    • 남은 로컬 잔량을 글로벌 런타임에 반납하여 다른 로컬에서 사용하게 한다.

 

 

CFS Period Timer – (1) 활성화

__start_cfs_bandwidth()

kernel/sched/fair.c

/* requires cfs_b->lock, may release to reprogram timer */
void __start_cfs_bandwidth(struct cfs_bandwidth *cfs_b, bool force)
{
        /*
         * The timer may be active because we're trying to set a new bandwidth
         * period or because we're racing with the tear-down path
         * (timer_active==0 becomes visible before the hrtimer call-back
         * terminates).  In either case we ensure that it's re-programmed
         */
        while (unlikely(hrtimer_active(&cfs_b->period_timer)) &&
               hrtimer_try_to_cancel(&cfs_b->period_timer) < 0) {
                /* bounce the lock to allow do_sched_cfs_period_timer to run */
                raw_spin_unlock(&cfs_b->lock);
                cpu_relax();
                raw_spin_lock(&cfs_b->lock);
                /* if someone else restarted the timer then we're done */
                if (!force && cfs_b->timer_active)
                        return;
        }

        cfs_b->timer_active = 1;
        start_bandwidth_timer(&cfs_b->period_timer, cfs_b->period);
}

글로벌 풀의 period 타이머를 가동시킨다.

  • 코드 라인 10~16에서 낮은 확률로 period 타이머가 콜백 함수를 현재 실행하고 있어서 동작을 cancel하지 못하는 동안 루프를 돌며 글로벌 풀의 락을 풀었다 다시 건다.
  • 코드 라인 17~18에서 여전히 타이머가 활성화 설정중이면서 인수 force가 0인 즉, 끝까지 완료 하지 않아도 되는 상태인 경우 함수를 빠져나간다.
  • 코드 라인 21~22에서 타아머가 활성화되었다는 표시를 하고 period 타이머를 가동시킨다.

 

start_bandwidth_timer()

kernel/sched/core.c

void start_bandwidth_timer(struct hrtimer *period_timer, ktime_t period)
{
        unsigned long delta;
        ktime_t soft, hard, now;

        for (;;) {
                if (hrtimer_active(period_timer))
                        break;

                now = hrtimer_cb_get_time(period_timer);
                hrtimer_forward(period_timer, now, period);

                soft = hrtimer_get_softexpires(period_timer);
                hard = hrtimer_get_expires(period_timer);
                delta = ktime_to_ns(ktime_sub(hard, soft));
                __hrtimer_start_range_ns(period_timer, soft, delta,
                                         HRTIMER_MODE_ABS_PINNED, 0);
        }
}

요청한 타이머를 가동시킨다. (글로벌 풀의 period 및 slack 타이머에서 사용한다)

  • 코드 라인 6~8에서 요청한 hrtimer가 활성화될 때까지 루프를 돈다.
  • 코드 라인 10~11에서 요청한 타이머에 설정된 클럭에서 현재 시각을 읽어오고 hrtimer가 현재 시각 이전인 경우 현재 시각 이후의 period 인터벌 단위 시간만큼 뒤에 만료가 되도록 설정한다.
    • 설정되는 만료 시각은 now + period가 아니고 항상 period 단위로 만료 시각이 설정되도록 계산된다.
    • hrtimer_forward()  함수의 동작은 조금 복잡하므로 다음 장을 참고로 한다.
  • 코드 라인 13~15에서 요청한 타이머에 설정된 slack이 적용된 hard 시각에서 slack이 적용되지 않은 원래 soft 시각을 뺀 delta 기간을 구한다.
  • 코드 라인 16~17에서 soft 시각에서 delta 기간 후에 요청한  타이머가 만료되도록 hrtimer를 가동한다.

 

CFS Period Timer – (2) 만료 시 호출

sched_cfs_period_timer()

kernel/sched/fair.c

static enum hrtimer_restart sched_cfs_period_timer(struct hrtimer *timer)
{
        struct cfs_bandwidth *cfs_b =
                container_of(timer, struct cfs_bandwidth, period_timer);
        ktime_t now;
        int overrun;
        int idle = 0;

        raw_spin_lock(&cfs_b->lock);
        for (;;) {
                now = hrtimer_cb_get_time(timer);
                overrun = hrtimer_forward(timer, now, cfs_b->period);

                if (!overrun)
                        break;

                idle = do_sched_cfs_period_timer(cfs_b, overrun);
        }
        raw_spin_unlock(&cfs_b->lock);

        return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;
}

period 타이머 만료 시에  호출되며 타이머에 연동된 태스크 그룹의 quota를 글로벌 런타임에 리필하고 추가적으로 필요한 작업들을 수행한다.

  • 코드 라인 3~4에서 타이머에 연동된 태스크 그룹의 cfs bandwidth를 알아온다.
  • 코드 라인 10~15에서 period 타이머가 만료된 경우에 한해 만료 시각으로 부터 period 간격으로 now를 지난 시각을 만료 시각으로 설정한다. (주의: now + interval이 아님)  그리고 만료 시각을 변경하지 않은 경우 루프를 탈출한다.
    • overrun: 기존 만료 시각으로 부터 새 만료 시각 사이의 인터벌 수
    • 참고: Timer -2- (HRTimer) | 문c
  • 코드 라인 17에서 태스크 그룹의 quota를 글로벌 런타임에 리필하고 추가적으로 필요한 작업들을 수행하고 idle 여부를 알아온다.
  • 코드 라인 21에서 타이머의 재스타트 여부를 반환한다.
    • HRTIMER_RESTART=1
    • HRTIMER_NORESTART=0

 

do_sched_cfs_period_timer()

태스크 그룹의 quota를 글로벌 런타임에 리필하고 이전 period에서 언스로틀된 cfs 런큐들에 대해 글로벌 런타임을 먼저 배포하고 언스로틀한다.

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

/*
 * Responsible for refilling a task_group's bandwidth and unthrottling its
 * cfs_rqs as appropriate. If there has been no activity within the last
 * period the timer is deactivated until scheduling resumes; cfs_b->idle is
 * used to track this state.
 */
static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b, int overrun)
{
        u64 runtime, runtime_expires;
        int throttled;

        /* no need to continue the timer with no bandwidth constraint */
        if (cfs_b->quota == RUNTIME_INF)
                goto out_deactivate;

        throttled = !list_empty(&cfs_b->throttled_cfs_rq);
        cfs_b->nr_periods += overrun;

        /*
         * idle depends on !throttled (for the case of a large deficit), and if
         * we're going inactive then everything else can be deferred
         */
        if (cfs_b->idle && !throttled)
                goto out_deactivate;

        /*
         * if we have relooped after returning idle once, we need to update our
         * status as actually running, so that other cpus doing
         * __start_cfs_bandwidth will stop trying to cancel us.
         */
        cfs_b->timer_active = 1;

        __refill_cfs_bandwidth_runtime(cfs_b);

        if (!throttled) {
                /* mark as potentially idle for the upcoming period */
                cfs_b->idle = 1;
                return 0;
        }
  • 코드 라인 13~14에서 태스크 그룹에 cfs quota 설정을 안한 경우 cfs bandwidth 설정이 안된 것이므로 period 타이머를 비활성화 시키고 1을 반환한다.
  • 코드 라인 16에서 태스크 그룹에 스로틀된 cfs 런큐가 있는지 여부를 throttled에 대입한다.
  • 코드 라인 17에서 period 간격이 진행된 횟수인 nr_periods를 overrun 횟수만큼 증가시킨다.
  • 코드 라인 23~24에서 스로틀 그룹이 idle 상태이면서 스로틀된 적이 없으면 period 타이머를 비활성화 시키고 1을 반환한다.
  • 코드 라인 31에서 period 타이머가 활성화되었음을 표시하기 위해 timer_active에 1을 대입한다.
  • 코드 라인 33에서 cfs bandwith를 리필한다. (런타임을 quota 만큼 리필)
  • 코드 라인 35~39에서 스로틀된 cfs 런큐가 없는 경우 태스크 그룹에 idle=1로 설정하고 0을 반환한다.

 

kernel/sched/fair.c -2/2-

        /* account preceding periods in which throttling occurred */
        cfs_b->nr_throttled += overrun;

        runtime_expires = cfs_b->runtime_expires;

        /*
         * This check is repeated as we are holding onto the new bandwidth while
         * we unthrottle. This can potentially race with an unthrottled group
         * trying to acquire new bandwidth from the global pool. This can result
         * in us over-using our runtime if it is all used during this loop, but
         * only by limited amounts in that extreme case.
         */
        while (throttled && cfs_b->runtime > 0) {
                runtime = cfs_b->runtime;
                raw_spin_unlock(&cfs_b->lock);
                /* we can't nest cfs_b->lock while distributing bandwidth */
                runtime = distribute_cfs_runtime(cfs_b, runtime,
                                                 runtime_expires);
                raw_spin_lock(&cfs_b->lock);

                throttled = !list_empty(&cfs_b->throttled_cfs_rq);

                cfs_b->runtime -= min(runtime, cfs_b->runtime);
        }

        /*
         * While we are ensured activity in the period following an
         * unthrottle, this also covers the case in which the new bandwidth is
         * insufficient to cover the existing bandwidth deficit.  (Forcing the
         * timer to remain active while there are any throttled entities.)
         */
        cfs_b->idle = 0;

        return 0;

out_deactivate:
        cfs_b->timer_active = 0;
        return 1;
}
  • 코드 라인 2에서 스로틀된 횟수를 overrun 만큼 증가시킨다.
  • 코드 라인 13~18에서 스로틀된 cfs 런큐가 있고 글로벌 런타임이 0보다 큰 경우 스로틀된 cfs 런큐들을 순서대로 글로벌 잔량이 남아있는 한 오버런한 런타임을 우선 배분하고 언스로틀한다.
  • 코드 라인 21에서 여전히 태스크 그룹에 스로틀된 cfs 런큐가 남아있는지 여부를 알아온다.
  • 코드 라인 23에서 글로벌 런타임 값이 0보다 작아지지 않는 범위에서 cfs 런큐에 할당해준 만큼 글로벌 런타임을 감소시킨다.
  • 코드 라인 32~34에서 글로벌 풀의 idle에 0을 대입하고 성공(0)을 반환한다.

 

 

distribute_cfs_runtime()

kernel/sched/fair.c

static u64 distribute_cfs_runtime(struct cfs_bandwidth *cfs_b,
                u64 remaining, u64 expires)
{
        struct cfs_rq *cfs_rq;
        u64 runtime;
        u64 starting_runtime = remaining;

        rcu_read_lock();
        list_for_each_entry_rcu(cfs_rq, &cfs_b->throttled_cfs_rq,
                                throttled_list) {
                struct rq *rq = rq_of(cfs_rq);

                raw_spin_lock(&rq->lock);
                if (!cfs_rq_throttled(cfs_rq))
                        goto next;

                runtime = -cfs_rq->runtime_remaining + 1;
                if (runtime > remaining)
                        runtime = remaining;
                remaining -= runtime;

                cfs_rq->runtime_remaining += runtime;
                cfs_rq->runtime_expires = expires;

                /* we check whether we're throttled above */
                if (cfs_rq->runtime_remaining > 0)
                        unthrottle_cfs_rq(cfs_rq);

next:
                raw_spin_unlock(&rq->lock);

                if (!remaining)
                        break;
        }
        rcu_read_unlock();

        return starting_runtime - remaining;
}

스로틀된 cfs 런큐들을 순서대로 글로벌 잔량이 남아있는 한 오버런한 런타임을 우선 배분하고 언스로틀한다.

  • 코드 라인 9~15에서 태스크 그룹의 스로틀된 cfs 런큐 리스트를 순회하며 cfs 런큐가 스로틀되지 않은 경우 cfs 런큐가 발견되면 skip 처리하기 위해 next 레이블로 이동한다.
  • 코드 라인 17~20에서 글로벌 런타임에서 cfs 런큐의 초과 수행한 런타임을 제외한 런타임을 을 받은 인수 remaining으로 받은  런타임에 잔여 런타임을 음수로 만든 후 1을 더한 값을 뺀다. 만일 런타임이 remaining 보다 큰 경우 런타임을 remaing 만큼 줄인다.
    • cfs 런큐가 스로틀되었다는 의미는 cfs 런큐의 잔여 런타임은 0이 되었거나 초과 수행되어 음수 값인 상태이다.
  • 코드 라인 22~23에서 잔여 런타임에 런타임을 추가하고 runtime_expires에 인수 expires를 대입한다.
  • 코드 라인 26~27에서 cfs 런큐의 잔여 런타임이 0보다 큰 경우 언스로틀한다.
  • 코드 라인 32~33에서 remaing 값이 0인 경우 루프를 벗어난다.
  • 코드 라인 37에서 인수로 받은 최초 remaing 값에서 변경된 remaing 값을 뺀 차이를 반환한다.

 

다음 그림은 distribute_cfs_runtime() 함수의 동작 시 글로벌 런타임을 기존 스로틀된 cfs 런큐의 오버런한 런타임에 우선 배포하고 언스로틀하는 과정을 보여준다.

 

 

CFS Slack Timer – (1) 활성화

start_cfs_slack_bandwidth()

kernel/sched/fair.c

static void start_cfs_slack_bandwidth(struct cfs_bandwidth *cfs_b)
{
        u64 min_left = cfs_bandwidth_slack_period + min_bandwidth_expiration;

        /* if there's a quota refresh soon don't bother with slack */
        if (runtime_refresh_within(cfs_b, min_left))
                return;

        start_bandwidth_timer(&cfs_b->slack_timer,
                                ns_to_ktime(cfs_bandwidth_slack_period));
}

 

slack 타이머를 slack 주기(디폴트 5ms)로 가동시킨다. 단 period 타이머의 만료 시각이 slack 불필요 범위(디폴트 7ms) 이내인 경우에는 가동시키지 않는다.

  • 코드 라인 3에서 최소 만료 시간과 slack 주기를 더해 min_left(디폴트=2+5=7ms)에 담는다.
  • 코드 라인 6~7에서 런타임 리필(리프레쉬) 주기가 다가온 경우 slack 타이머를 활성화할 필요 없으므로 함수를 빠져나간다.
  • 코드 라인 9~10에서 slack 타이머를 cfs_bandwidth_slack_period(디폴트 5ms) 주기로 활성화한다.

 

runtime_refresh_within()

kernel/sched/fair.c

/*
 * Are we near the end of the current quota period?
 *
 * Requires cfs_b->lock for hrtimer_expires_remaining to be safe against the
 * hrtimer base being cleared by __hrtimer_start_range_ns. In the case of
 * migrate_hrtimers, base is never cleared, so we are fine.
 */
static int runtime_refresh_within(struct cfs_bandwidth *cfs_b, u64 min_expire)
{
        struct hrtimer *refresh_timer = &cfs_b->period_timer;
        u64 remaining;

        /* if the call-back is running a quota refresh is already occurring */
        if (hrtimer_callback_running(refresh_timer))
                return 1;

        /* is a quota refresh about to occur? */
        remaining = ktime_to_ns(hrtimer_expires_remaining(refresh_timer));
        if (remaining < min_expire)
                return 1;

        return 0;
}

런타임 리프레쉬 주기가 다가오는지 여부를 확인한다.

  • 코드 라인 10~15에서 hrtimer가 만료되어 콜백이 진행중이면 1을 반환한다. 현재 리프레시 진행 중이므로 굳이 slack 타이머를 가동시킬 필요 없다.
  • 코드 라인 18~22에서 만료될 시간이 인수로 받은 min_expire 기준 시간 보다 작은 경우 곧 리프레쉬 주기가 다가오므로 1을 반환하고 그 외의 경우 slack 타이머가 동작하도록0을 반환한다.

 

CFS Slack Timer – (2) 만료 시 호출

sched_cfs_slack_timer()

kernel/sched/fair.c

static enum hrtimer_restart sched_cfs_slack_timer(struct hrtimer *timer)
{
        struct cfs_bandwidth *cfs_b =
                container_of(timer, struct cfs_bandwidth, slack_timer);
        do_sched_cfs_slack_timer(cfs_b);

        return HRTIMER_NORESTART;
}

slack 타이머 만료 시 글로벌 풀로부터 스로틀된 로컬의 런타임들에 분배한다. (디폴트로 slack 타이머는 5ms이다)

  • 디큐된 태스크의 남은 런타임 잔량을 글로벌에 반납하면서 slack 타이머를 통해  할당을 못받고 스로틀되고 있는 로컬 풀에 런타임 할당 기회를 준다.

 

do_sched_cfs_slack_timer()

kernel/sched/fair.c

/*
 * This is done with a timer (instead of inline with bandwidth return) since
 * it's necessary to juggle rq->locks to unthrottle their respective cfs_rqs.
 */
static void do_sched_cfs_slack_timer(struct cfs_bandwidth *cfs_b)
{
        u64 runtime = 0, slice = sched_cfs_bandwidth_slice();
        u64 expires;

        /* confirm we're still not at a refresh boundary */
        raw_spin_lock(&cfs_b->lock);
        if (runtime_refresh_within(cfs_b, min_bandwidth_expiration)) {
                raw_spin_unlock(&cfs_b->lock);
                return;
        }

        if (cfs_b->quota != RUNTIME_INF && cfs_b->runtime > slice)
                runtime = cfs_b->runtime;

        expires = cfs_b->runtime_expires;
        raw_spin_unlock(&cfs_b->lock);

        if (!runtime)
                return;

        runtime = distribute_cfs_runtime(cfs_b, runtime, expires);

        raw_spin_lock(&cfs_b->lock);
        if (expires == cfs_b->runtime_expires)
                cfs_b->runtime -= min(runtime, cfs_b->runtime);
        raw_spin_unlock(&cfs_b->lock);
}

 

slack 타이머 만료 시 글로벌 풀로부터 스로틀된 로컬의 런타임들에 분배한다. (디폴트로 slack 타이머는 5ms이다)

  • 코드 라인 7에서 cfs bandwidth의 slice를 구해온다.
    • slice: 글로벌 풀에서 로컬로 빌려올 수 있는 런타임 시간
  • 코드 라인 12~15에서 period 타이머의 만료 시각이 최소 만료 시각(디폴트 2ms)이내로 곧 다가오는 경우 처리하지 않고 함수를 빠져나간다.
  • 코드 라인 17~18에서 quota 설정이 되었으면서 글로벌 풀의 런타임이 slice 보다 큰 경우 분배할 런타임으로 글로벌 런타임을 사용한다.
  • 코드 라인 20에서 설정할 만료 시각으로 글로벌 풀의 만료 시각을 사용한다.
  • 코드 라인 23~24에서 분배할 런타임이 준비되지 않은 경우 함수를 빠져나간다.
  • 코드 라인 26에서 스로틀된 cfs 런큐들을 순서대로 글로벌 잔량이 남이있는 한 오버런한 런타임을 우선 배분하고 언스로틀한다.
  • 코드 라인 29~30에서 글로벌 풀의 런타임에서 분배에 소진한 런타임을 뺀다. 글로벌 런타임이 0 미만이 되지 않도록 0으로 제한한다.

 

 

DL Bandwidth

init_dl_bandwidth()

kernel/sched/deadline.c

void init_dl_bandwidth(struct dl_bandwidth *dl_b, u64 period, u64 runtime)
{
        raw_spin_lock_init(&dl_b->dl_runtime_lock);
        dl_b->dl_period = period;
        dl_b->dl_runtime = runtime;
}

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

  • 코드 라인 4에서 인수로 전달받은 us 단위의 period 값을 나노초 단위로 바꾸어 dl_period에 저장한다.
  • 코드 라인 5에서 인수로 전달받은 us 단위의 runtime 값을 나노초 단위로 바꾸어 dl_runtime에 저장한다.

 

구조체

cfs_bandwidth 구조체

kernel/sched/sched.h

struct cfs_bandwidth {
#ifdef CONFIG_CFS_BANDWIDTH
        raw_spinlock_t lock;
        ktime_t period;
        u64 quota, runtime;
        s64 hierarchical_quota;
        u64 runtime_expires;

        int idle, timer_active;
        struct hrtimer period_timer, slack_timer;
        struct list_head throttled_cfs_rq;

        /* statistics */
        int nr_periods, nr_throttled;
        u64 throttled_time;
#endif
};
  • lock
    • spin 락
  • period
    • 태스크 그룹의 cpu 사용량을 제어하기 위한 주기로 ns 단위로 저장된다.
    • 1ms ~ 1s까지 설정가능하며 디폴트 값=100ms
    • “/sys/fs/cgroup/cpu/cpu.cfs_period_us”에서 설정하고 ns 단위로 변환하여 저장된다.
  • quota
    • 태스크 그룹이 period 동안 수행 할 쿼터로  ns 단위로 저장된다.
    • 1ms~ 부터 설정 가능
    • 0xffffffff_ffffffff 또는 -1인 경우 무제한(bandwidth 설정 없음)
    • “/sys/fs/cgroup/cpu/cpu.cfs_quota_us”에서 설정하고 ns 단위로 변환하여 저장된다.
  • runtime
    • 글로벌 런타임(ns)
    • period 타이머 주기마다 quota 시간으로 refill(refresh) 된다.
    • slack 타이머 주기마다 스로틀된 로컬에 런타임을 빌려주면서 점점 줄어든다.
  • hierarchical_quota
    • 계층적으로 관리되는 태스크 그룹의 period에 대한 quota 정수 비율이다.
    • 정수 값은 1M(1 << 20)가 100%이고 512K는 50%에 해당한다.
  • runtime_expires
    • period 내에서 quota 만큼의 런타임이 수행된 후 만료될 시각(ns)
  • idle
    • idle(1) 상태인 경우 로컬에 런타임 할당이 필요 없는 상태로 만들고 다음 주기에 스로틀되도록 하려는 목적이다.
    • 로컬에 런타임 할당을 하거나 스로틀링을 한 경우는 idle 상태에서 해제(0)된다.
  • timer_active
    • period 타이머의 가동 여부
  • period_timer
    • period 주기마다 동작하는 타이머
    • 이 때 마다 글로벌 런타임 소비 잔량(runtime_remaining)을 quota 값으로 refill(refresh) 한다.
  • slack_timer
    • 슬랙 타이머 (디폴트 5ms)
    • 태스크가 dequeue되어 남는 로컬 런타임 잔량을 글로벌 풀로 반납한다.
  • throttled_cfs_rq
  • nr_periods
    • 주기가 반복 진행된 횟수
  • nr_throttled
    • 스로틀링된 횟수
  • throttled_time
    • 스로틀링된 시간 합

“/sys/fs/cgroup/cpu/cpu.stat” 파일을 통해 nr_periods, nr_throttled, throttled_time 값을 볼 수 있다.

cfs_rq 구조체 (bandwidth 멤버만)

kernel/sched/sched.

struct cfs_rq {

        (...생략...)

#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 */
};
  • runtime_enabled
    • period 타이머 활성화 여부
  • runtime_expires
    • period 타이머 만료 시각
  • runtime_remaining
    • 잔여 런타임
    • 글로벌 풀로부터 필요한 만큼 분배 받아서 설정된다.
  • throttled_clock
    • 스로틀된 시각으로 irq 처리 타임을 포함한 rq->clock으로 산출된다.
  • throttled_clock_task
    • 스로틀된 시각으로 irq 처리 타임을 뺸 태스크 실행시간만으로 rq->clock_task를 사용하여 산출된다.
  • throttled_clock_task_time
    • 스로틀된 시간 총합(irq 처리 타임을 뺀 태스크 스로틀링된 시간만 누적)
  • throttled
    • 스로틀된 적이 있었는지 여부(1=스로틀된 적이 있는 경우)
  • throttle_count
    • 스로틀 횟수
  • throttled_list
    • 태스크 그룹에 있는 cfs_bandwidth의 throttled_cfs_rq 리스트에 추가할 때 사용하는 링크 노드

 

참고

2 thoughts to “Scheduler -5- (CFS Bandwidth)”

답글 남기기

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