pick next task

현재 실행중인 태스크는 언젠가는 CPU를 양보해야 한다. 새로운 태스크가 CPU를 선점하게 된다. 이런 일의 시작은 __schedule()에서 발생한다.

static void __sched notrace __schedule(bool preempt)
{
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
        prev = rq->curr;
        ...
        next = pick_next_task(rq, prev);
        ...
}

pick_next_task()는 @rq에 enqueue되어 있는 task를 pick하게 된다. 모든 스케쥴링 클래스별 pick_next_task()를 호출해서 각 타입별 태스크를 pick한다. 우선순위가 높은 스케쥴링 클래스순으로 pick을 시도한다.

범위를 cfs 스케쥴링클래스로 제한하고 알아보자. pick_next_task_fair()가 호출되고 current cpu의 cfs_rq에 enqueue된 first entity를 얻어온다. first entity는 rb tree의 leftmost node에 enqueue된 entity를 의미한다.

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
        struct rb_node *left = cfs_rq->rb_leftmost;

        if (!left)
                return NULL;

        return rb_entry(left, struct sched_entity, run_node);
}

얻어온 스케쥴링엔티티가 자신만의 cfs_rq를 가지고 있을 수가 있다. 스케쥴링엔티티가 태스크그룹일 경우이다. 이 경우엔 그룹내에서 다시 태스크를 선택하는 과정을 반복한다. 이 과정은 태스크의 스케쥴링엔티티(자신만의 cfs_rq를 가지고 있지 않은 스케쥴링엔티티)가 얻어질때까지 반복된다.

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev)
{  
        ...
        do {
                struct sched_entity *curr = cfs_rq->curr;
                ...
                se = pick_next_entity(cfs_rq, curr);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);
        ...
}

그림. 몇단계의 cfs_rq를 거쳐서 최하위 태스크의 스케쥴링엔티티가 선택되는 과정..

pick_next_task(rq, prev)
-> pick_next_task_fair(rq, prev)
->-> pick_next_entity(cfs_rq, curr)
->->-> __pick_first_entity(cfs_rq)