250301 CFS 태스크 선택, 제거, 삽입 (6.3.1~6.3.4)

6.3 CFS(Completely Fair Scheduling)

SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 정책을 사용하는 태스크를 처리하는 스케줄러

6.3.1 태스크를 런큐에 삽입하기

레드 블랙 트리에 enqueue

6-23 kernel/sched/fair.c enqueue_task_fair

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) { // 내 se 부터 부모 se 를 순회
        if (se->on_rq) // se 가 rq 에 들어가있는 경우 멈춤
            break;
        cfs_rq = cfs_rq_of(se);
        enqueue_entity(cfs_rq, se, flags); // 6-24

        if (cfs_rq_throttled(cfs_rq)) // 바쁜 상태면 멈춤  -->?? 그러면 못넣은 애는 언제들어가게 될까?
            break;
        cfs_rq->h_nr_running++; // h (hierarchical) 그룹 내부에 counting 까지

        flags = ENQUEUE_WAKEUP; // 가장 자식쪽에서 여길 왔다면 flag 가 ENQUEUE_WAKEUP 이 됨
    }

    // 그러면 이 se 는 없거나, rq 에 들어가서 멈췄거나, 바쁜 상태였음
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        cfs_rq->h_nr_running++; // 자식에 entity 가 추가됐더라도 h_nr_running 은 추가됨

        if (cfs_rq_throttled(cfs_rq))
            break;

        update_load_avg(se, 1); // load weight 계산, 두번째 인자는 task_group 까지 업데이트 할지. nice 로 계산 절대값
        update_cfs_shares(cfs_rq); // 비율 계산
    }

    if (!se) // 최상위까지 모두 마쳤다면 (중간에 throttle 이 걸렸다면 se 가 남아있으니)
        add_nr_running(rq, 1); // nr_running 증가

    hrtick_update(rq);
}

6-24 kernel/sched/fair.c enqueue_entity

vruntime, load weight 등 반영
이 함수는 on_rq 가 아닐때만 들어온거.

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    // re normalize 하지 않는 케이스가 있음
    // 예를들어 위 코드의, 상위 스케줄링 엔테티티를 하는 경우
    bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING);
    bool curr = cfs_rq->curr == se; // rq 의 현재 task 가 se 인지 여부

    // 현재 task 인 경우 update_curr 하기전에 미리 vruntime 을 갱신
    if (renorm && curr)
        se->vruntime += cfs_rq->min_vruntime;

    update_curr(cfs_rq);

    // 다른 task 를 넣는 경우, update_curr 을 하고 vruntime 을 갱신
    if (renorm && !curr)
        se->vruntime += cfs_rq->min_vruntime;

    enqueue_entity_load_avg(cfs_rq, se); // rq 에 load 평균을
    account_entity_enqueue(cfs_rq, se); // rq 에 se 의 weight 를 추가.
    update_cfs_shares(cfs_rq);

    if (flags & ENQUEUE_WAKEUP) { // 잠들어있던 task 의 vruntime 독점하지 않도록 조정
        place_entity(cfs_rq, se, 0);
        if (schedstat_enabled())
            enqueue_sleeper(cfs_rq, se); // stat 쪽은 통계
    }

    if (!curr)
        __enqueue_entity(cfs_rq, se); // 현재 task 가 아니었다면, 실제 런큐(rb 트리) 에 추가
    se->on_rq = 1; // 만약 현재 task 였다면 어차피 돌고있던거니까 on_rq 는 무조건 1임

    if (cfs_rq->nr_running == 1) { // rq 에 처음으로 실행이 가능해졌을때
        list_add_leaf_cfs_rq(cfs_rq); // 특정 CFS 그룹을 leaf 노드로 관리함. 
        check_enqueue_throttle(cfs_rq); // When a group wakes up we want to make sure that its quota is not already. 깨어났을때 해제
    }
}

root_cfs_rq  (on_list == 1)
 ├── cfs_rq_A (on_list == 1)  <-- 실행할 태스크가 있음
 │    ├── cfs_rq_A1 (on_list == 1)  <-- 실행할 태스크가 있음
 │    ├── cfs_rq_A2 (on_list == 0)  <-- 실행할 태스크가 없음 (or throttled)
 │
 ├── cfs_rq_B (on_list == 0)  <-- 실행할 태스크가 없음

6-25 kernel/sched/fair.c place_entity

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

    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se); // 다른 task 를 배려함

    if (!initial) { // 처음 enqueue 가 아니라면
        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 적게 뺄깨

        vruntime -= thresh; // vruntime 이 작으면 더 빨리 깨어남
    }

    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

6-26 kernel/sched/fair.c __enqueue_entity

rb tree 에 insert

struct cfs_rq {
    struct rb_root tasks_timeline;
}

struct sched_entity {
    struct rb_node        run_node;
}

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
  rb_node **link = cfs->rq->task_timeline.rb_node
  entry = rb_entry(parent, struct sched_entity, run_node); 
  // rb tree insert
}

6.3.2 태스크를 런큐에서 선택하기

current task 가 timeslice 를 소진한다. (vruntime & timeslice 개념이 아직 확실치 않음)

6-27 kernel/sched/core.c pick_next_task

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    const struct sched_class *class = &fair_sched_class;
    struct task_struct *p;

    /*
     * Optimization: we know that if all tasks are in
     * the fair class we can call that function directly:
     */
    if (likely(prev->sched_class == class && // 일반적으로 fair scheduler 를 사용
           rq->nr_running == rq->cfs.h_nr_running)) { // 현재 rq 에 fair scheduling 만을 사용하는 task 가 돌고 있다면
        p = fair_sched_class.pick_next_task(rq, prev); // 6-28. 런큐에서 가져오거나 로드밸런싱을 통해 가져올 수도 있음
        if (unlikely(p == RETRY_TASK)) // normal 태스크보다 더 높은 task 를 가져왔다면
            goto again;

        /* assumes fair_sched_class->next == idle_sched_class */
        if (unlikely(!p)) // 태스크가 없다면 idle 쓰레드를 선택
            p = idle_sched_class.pick_next_task(rq, prev);

        return p;
    }

again:
    for_each_class(class) { // 우선순위가 높은 스케줄러를 차례대로 돌며 task 찾기
        p = class->pick_next_task(rq, prev);
        if (p) {
            if (unlikely(p == RETRY_TASK))
                goto again;
            return p;
        }
    }

    BUG(); /* the idle class will always have a runnable task */
}

6-28 kernel/sched/fair.c pick_next_task_fair 1

태스크를 찾는 과정

• current task 가 normal task 인 경우
• current 태스크가 normal task 가 아닌 경우 : 마무리 작업이 생략되어 단순
• CFS 런큐에 실행할 task 가 없는 경우 : 다른 cpu 의 런큐에서 마이그레이션

current_task -> enqueue 됨
next_task -> current_task 가 됨

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;
    int new_tasks;

again:
#ifdef CONFIG_FAIR_GROUP_SCHED
    if (!cfs_rq->nr_running) // run queue 에 enqueue 된 entity 가 없다면
        goto idle; // idle 로 점프하여 migration 할 수 있도록 한다

    if (prev->sched_class != &fair_sched_class) // normal task 가 아니었다면
        goto simple; // 복잡한 과정 없이 next task 만 찾는다

    /*
     * Because of the set_next_buddy() in dequeue_task_fair() it is rather
     * likely that a next task is from the same cgroup as the current.
     *
     * Therefore attempt to avoid putting and setting the entire cgroup
     * hierarchy, only change the part that actually changes.
     */

    do {
        struct sched_entity *curr = cfs_rq->curr; // 현재 돌고있던 entity

        /*
         * Since we got here without doing put_prev_entity() we also
         * have to consider cfs_rq->curr. If it is still a runnable
         * entity, update_curr() will update its vruntime, otherwise
         * forget we've ever seen it.
         */
        if (curr) {
            if (curr->on_rq) // 아직 dequeue 되지 않았다면
                update_curr(cfs_rq); // vruntime 을 갱신
            else
                curr = NULL;

            /*
             * This call to check_cfs_rq_runtime() will do the
             * throttle and dequeue its entity in the parent(s).
             * Therefore the 'simple' nr_running test will indeed
             * be correct.
             */
            if (unlikely(check_cfs_rq_runtime(cfs_rq)))
                goto simple;
        }

        se = pick_next_entity(cfs_rq, curr); // 6-30 다음 entity 찾기
        cfs_rq = group_cfs_rq(se);  // 그룹인 경우 자식을 찾아가면서 처리
    } while (cfs_rq);

    p = task_of(se); // se 를 사용하는 task

    /*
     * Since we haven't yet done put_prev_entity and if the selected task
     * is a different task than we started out with, try and touch the
     * least amount of cfs_rqs.
     */
    if (prev != p) { // 다른 task 라면
        struct sched_entity *pse = &prev->se; // p (current), se(next)

        while (!(cfs_rq = is_same_group(se, pse))) { // se, pse 의 그룹이 같아질때까지 검색 (왜냐면 더 높은 그룹이면 이미 enqueue 되어있는거니까)
            int se_depth = se->depth;
            int pse_depth = pse->depth;

            if (se_depth <= pse_depth) {
                put_prev_entity(cfs_rq_of(pse), pse);
                pse = parent_entity(pse);
            }
            if (se_depth >= pse_depth) {
                set_next_entity(cfs_rq_of(se), se);
                se = parent_entity(se);
            }
        }

        put_prev_entity(cfs_rq, pse);
        set_next_entity(cfs_rq, se);
    }

    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;

target group 의 cfs_rq 는 cpu 개수만큼 존재

struct cfs_rq *cfs_rq = tg->cfs_rq[i];

6-28 kernel/sched/fair.c pick_next_task_fair 2

simple:
    cfs_rq = &rq->cfs;
#endif

    if (!cfs_rq->nr_running) // entity 가 없다면 migration 시도
        goto idle;

    put_prev_task(rq, prev); // 부모방향으로 가며 curr 을 null 로 초기화. rq 에 enqueue

    do {
        se = pick_next_entity(cfs_rq, NULL); // 다음에 실행할 태스크를 top-down 으로 검색 6-30
        set_next_entity(cfs_rq, se); // current entity 로 설정
        cfs_rq = group_cfs_rq(se); // ..? 여기두
    } while (cfs_rq);

    p = task_of(se);

    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;

idle:
    /*
     * This is OK, because current is on_cpu, which avoids it being picked
     * for load-balance and preemption/IRQs are still disabled avoiding
     * further scheduler activity on it and we're being very careful to
     * re-start the picking loop.
     */
    lockdep_unpin_lock(&rq->lock);
    new_tasks = idle_balance(rq); // 다른 cpu 에서 task 가져오기
    lockdep_pin_lock(&rq->lock);
    /*
     * Because idle_balance() releases (and re-acquires) rq->lock, it is
     * possible for any higher priority task to appear. In that case we
     * must re-start the pick_next_entity() loop.
     */
    if (new_tasks < 0)
        return RETRY_TASK; // 더 높은 우선순위

    if (new_tasks > 0)
        goto again;

    return NULL; // 태스크가 없음
}

6-30 kernel/sched/fair.c pick_next_entity

vruntime 이 작거나 buddy 로 설정된 sched_entity 가져오기

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq); // get leftmost

    if (!left || (curr && entity_before(curr, left))) left = curr; // left 가 없거나 curr vruntime 이 더 작음

    se = left; /* ideally we run the leftmost entity */

    /*
     * Avoid running the skip buddy, if running something else can
     * be done without getting too unfair.
     */
    if (cfs_rq->skip == se) { // yield_task_fair 등에서 skip 을 설정함
        struct sched_entity *second;

        if (se == curr) { // curr 이었던 경우는 어차피 rb 에 없었음
            second = __pick_first_entity(cfs_rq);
        } else {
            second = __pick_next_entity(se); // left 다음 노드
            if (!second || (curr && entity_before(curr, second)))
                second = curr;
        }

        if (second && wakeup_preempt_entity(second, left) < 1) // second 가 더 많이 돌았지만, 차이가 많이 안나는 경우
            se = second;
    }

    /*
     * Prefer last buddy, try to return the CPU to a preempted task.
     */
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last; // 최근에 돌았던 se 를 우선 선택

    /*
     * Someone really wants this to run. If it's not unfair, run it.
     */
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next; // buddy 로 설정된것

    clear_buddies(cfs_rq, se); // 선택된 last, next, skip 을 제거

    return se;
}

6-31 kernel/sched/fair.c put_prev_entity

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    if (prev->on_rq) // 넣기전에 돌고있었다면 업데이트
        update_curr(cfs_rq);

    /* throttle cfs_rqs exceeding runtime */
    check_cfs_rq_runtime(cfs_rq); // 너무 많이 돌았다면 throttle 걸기

    if (schedstat_enabled()) {
        check_spread(cfs_rq, prev);
        if (prev->on_rq)
            update_stats_wait_start(cfs_rq, prev);
    }

    if (prev->on_rq) {
        /* Put 'current' back into the tree. */
        __enqueue_entity(cfs_rq, prev); // rb 트리에 넣기
        /* in !on_rq case, update occurred at dequeue */
        update_load_avg(prev, 0 /*update_tg*/);
    }
    cfs_rq->curr = NULL; // 돌고있는 entity 를 null 로 설정
}

on_rq : 태스크가 CFS 런큐에 있는지 여부, 즉 실행 대기 상태인지를 나타냅니다. (rq 에 있거나 rb 트리에 enqueue)

6-32 kernel/sched/fair.c set_next_entity

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /* 'current' is not kept within the tree. */
    if (se->on_rq) {
        /*
         * Any task has to be enqueued before it get to execute on
         * a CPU. So account for the time it spent waiting on the
         * runqueue.
         */
        if (schedstat_enabled())
            update_stats_wait_end(cfs_rq, se);
        __dequeue_entity(cfs_rq, se); // 트리에서 dequeue
        update_load_avg(se, 1);
    }

    update_stats_curr_start(cfs_rq, se);
    cfs_rq->curr = se; // 현재 task 를 설정
    se->prev_sum_exec_runtime = se->sum_exec_runtime; // 백업

6.3.3 태스크를 런큐에서 제거하기

더이상 CPU 를 사용하지 않을때

6-33 kernel/sched/fair.c dequeue_task_fair

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;
    int task_sleep = flags & DEQUEUE_SLEEP; // TASK_RUNNING 이 아닌상태로 스위칭 되거나, throttling 이 걸린 경우

    for_each_sched_entity(se) { // bottom-up
        cfs_rq = cfs_rq_of(se);
        dequeue_entity(cfs_rq, se, flags); // rb 트리에서 제거 & on_rq = 0

        if (cfs_rq_throttled(cfs_rq))
            break;
        cfs_rq->h_nr_running--;

        /* Don't dequeue parent if it has other entities besides us */
        if (cfs_rq->load.weight) { // 그룹에 weight 가 남아있는 경우, 순회를 멈춘다
            if (task_sleep && parent_entity(se)) // sleep 요청이 오면서 root group 이 아닌경우
                set_next_buddy(parent_entity(se)); // 같은 그룹이 먼저 실행 될 수 있도록 buddy 등록

            /* avoid re-evaluating load for this entity */
            se = parent_entity(se);
            break;
        }
        flags |= DEQUEUE_SLEEP;
    }

    for_each_sched_entity(se) { // load 정보 갱신
        cfs_rq = cfs_rq_of(se);
        cfs_rq->h_nr_running--;

        if (cfs_rq_throttled(cfs_rq))
            break;

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

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

    hrtick_update(rq);
}

6-34 kernel/sched/fair.c dequeue_entity

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    update_curr(cfs_rq);
    dequeue_entity_load_avg(cfs_rq, se);

    if (schedstat_enabled())
        update_stats_dequeue(cfs_rq, se, flags);

    clear_buddies(cfs_rq, se);

    if (se != cfs_rq->curr) // curr 인 경우 설정되는 과정에서 이미 dequeue 됨
        __dequeue_entity(cfs_rq, se);
    se->on_rq = 0;
    account_entity_dequeue(cfs_rq, se);

    /*
     * Normalize the entity after updating the min_vruntime because the
     * update can refer to the ->curr item and we need to reflect this
     * movement in our normalized position.
     */
    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= cfs_rq->min_vruntime;

    /* return excess runtime on last dequeue */
    return_cfs_rq_runtime(cfs_rq);

    update_min_vruntime(cfs_rq); // min_vruntime 을 갱신
    update_cfs_shares(cfs_rq);
}

se->on_rq / task->on_rq  다른듯

6.3.4 주기적으로 발생하는 틱 처리하기

6-35 kernel/sched/fair.c task_tick_fair

void scheduler_tick(void) // 타이머 인터럽트(틱) 에서 호출
{
  curr->sched_class->task_tick(rq, curr, 0);
}

6-36 kernel/sched/fair.c entity_tick

스케줄링 정보 갱신 & currenty 엔티티가 충분히 돌았다면 선점 요청

6-37 kernel/sched/fair.c check_preempt_tick

틱마다 호출되어 current entity 를 선점 가능한지 확인

• current 가 타임 슬라이스 이상으로 실행한 경우
• current 가 최소 보장 시간보다 더 실행됐고, leftmost 와 차이가 타임 슬라이스 이상인 경우

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    ideal_runtime = sched_slice(cfs_rq, curr); // 이상적 실행시간
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    if (delta_exec > ideal_runtime) {...}
}