리눅스 CFS 스케줄러

CFS(Completely Fair Scheduler)는 리눅스의 기본 스케줄러이다. CFS라는 용어에서 알 수 있듯이 런큐에서 실행 대기 상태로 기다리는 프로세스를 공정하게 실행하도록 기회를 부여하는 스케줄러이다.

---

CFS 스케줄러를 이해하기 위해서는 다음과 같은 개념을 이해해야 한다.

- 타임 슬라이스

- 우선순위

- 가상 실행 시간(vruntime)

​

타임 슬라이스

타임 슬라이스는 스케줄러가 프로세스에게 부여한 실행 시간을 의미한다. 즉, CFS에서는 프로세스마다 실행할 수 있는 단위 시간을 부여하고 이를 타임 슬라이스라고 한다. 프로세스는 주어진 타임 슬라이스를 모두 소진하면 컨텍스트 스위칭된다. CFS 스케줄러는 타이머 인터럽트가 발생했을 때 주기적으로 프로세스가 얼마나 타임 슬라이스를 소진하고 있는지 체크한다. 만약 체크하였을 때, 프로세스가 타임 슬라이스를 모두 소진하면 스케줄러는 해당 프로세스가 선점 스케줄링이 될 대상이라고 마킹한다. 이는 해당 프로세스의 thread_info 구조체 중 flags 필드에 _TIF_NEED_RESCHED 플래그를 설정하는 행위이다.

​

우선순위

우선순위는 CFS 스케줄러가 컨텍스트 스위칭 시 다음 프로세스를 선택하는 기준 중 하나이다. CFS 스케줄러는 우선순위가 높은 프로세스를 1. 가장 먼저 CPU에서 실행시키고 2. 더 많은 타임 슬라이스를 할당한다.

리눅스는 총 140단계의 우선순위를 제공하고 다음과 같다.

​

- 0~99 : RT(실시간) 프로세스

- 100~139 : 일반 프로세스

​

가상 실행 시간

가상 실행시간(vruntime)은 커널에서 프로세스가 그동안 실행한 시간을 정규화한 시간 정보라고 할 수 있다. CFS가 프로세스를 선택할 수 있는 load weight 같은 여러 지표가 고려된 실행 시간이다. vruntime은 다음과 같은 특징을 가진다.

​

- CFS는 런큐에 실행 대기 상태에 있는 프로세스 중 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택

- 우선순위가 높은 프로세스는 우선순위가 낮은 프로세스에 비해 vruntime이 서서히 증가한다.

​

다음은 vruntime이 저장되어 있는 위치이다.

​

struct task_struct (include/linux/sched.h)

struct task_struct { .. struct sched_entity se; } struct sched_entity { struct load_weight load; unsigned long runnable_weight; struct rb_node run_node; struct list_head group_node; unsigned int on_rq; u64 exec_start; u64 sum_exec_runtime; u64 vruntime;

task_struct 구조체의 sched_entity 필드인 se에 vruntime이 저장되어 있는것을 확인할 수 있다.

---

CFS 스케줄러의 알고리즘에 대해서 분석한다. CFS 스케줄러는 용어 그대로 프로세스를 공정하게 실행하도록 구현된 스케줄러이다. CFS의 목표는 런큐에 있는 실행 대기 상태의 프로세스에게 CPU 시간을 우선순위에 따라 공정하게 할당하는 것이다. 이를 위해서 CFS 에서는 우선순위의 비율로 CPU 시간을 분배한다.

즉, 정수형 우선순위는 우선순위 비율이 되는 것이고, 이것이 load_weight이다. 프로세스가 더 큰 load weight을 가지고 있으면 CFS는 더 자주 실행할 수 있는 기회를 부여한다. 다음은 프로세스가 갖고 있는 우선순위를 load weight로 변환하는 역할을 수행하는 set_load_weight()이다.

​

set_load_weight() (kernel/sched/core.c)

static void set_load_weight(struct task_struct *p, bool update_load) { int prio = p->static_prio - MAX_RT_PRIO; struct load_weight *load = &p->se.load; .. if (update_load && p->sched_class == &fair_sched_class) { reweight_task(p, prio); } else { load->weight = scale_load(sched_prio_to_weight[prio]); load->inv_weight = sched_prio_to_wmult[prio]; } }

3번째 줄 : 태스크 디스크립터에 저장된 static_prio 우선순위를 변환해 prio 변수에 저장한다. 여기서 MAX_RT_PRIO는 100이다. static_prio의 범위는 100~139이니 prio 변수의 범위는 0~39이다.

10번째 줄 : sched_prio_to_weight 배열을 인자로 scale_load()를 호출한다. 이 함수는 전달받은 인자값을 왼쪽으로 10비트만큼 시프트하는 동작을 수행한다. 이는 64비트 아키텍처 기반의 커널에서만 작동하고, 32비트 기반 ARMv7 아키텍처인 라즈비안은 작동하지 않는다. 즉, sched_prio_to_weight[prio]의 값이 load->weight에 저장된다.

​

다음은 sched_prio_to_weight 배열이다.

​

sched_prio_to_weight (kernel/sched/core.c)

const int sched_prio_to_weight[40] = { /* -20 */ 88761, 71755, 56483, 46273, 36291, /* -15 */ 29154, 23254, 18705, 14949, 11916, /* -10 */ 9548, 7620, 6100, 4904, 3906, /* -5 */ 3121, 2501, 1991, 1586, 1277, /* 0 */ 1024, 820, 655, 526, 423, /* 5 */ 335, 272, 215, 172, 137, /* 10 */ 110, 87, 70, 56, 45, /* 15 */ 36, 29, 23, 18, 15, };

이 배열은 우선순위별로 가중치를 적용한 테이블이다. 가장 큰 load weight은 88761인 것을 확인할 수 있다. 해당 load->weight은 프로세스 태스크 디스크립터의 다음 필드에 저장된다.

​

task_struct (include/linux/sched.h)

struct task_struct { struct sched_entity se; struct sched_entity { struct load_weight load; struct load_weight { unsigned long weight; u32 inv_weight;

​

정리하자면 set_load_weight()는 프로세스의 태스크 디스크립터의 se.load.weight에 우선순위별로 가중치가 적용된 load weight을 저장한다.

​

또한 런큐 구조체의 cfs 필드에는 런큐에 등록한 프로세스들의 load weight을 합한 값을 load.weight에 저장한다.

​

(kernel/sched/sched.h)

struct rq { struct cfs_rq cfs; struct cfs_rq { struct load_weight load;

---

이어서 CFS 스케줄러에서 타임 슬라이스를 계산하는 방법을 살펴본다.

​

출처 : http://rousalome.egloos.com/10002542

​

각 프로세스의 타임 슬라이스는 위 공식으로 계산된다. 스케줄링 레이턴시란 CFS 런큐에서 실행 대기 상태로 기다리는 프로세스들의 타임 슬라이스를 합한 값이다. 위 식에 의해서 각 프로세스는 load weight 비율만큼의 타임 슬라이스를 얻게 된다.

---

vruntime은 프로세스가 그동안 실행한 시간을 정규화한 시간 정보다. CFS 스케줄러가 프로세스를 선택할 수 있는 load weight와 같은 지표가 고려된 실행 시간이다. CFS 스케줄러는 런큐에 등록된 프로세스중 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택하기 때문에 vruntime은 중요하다. vruntime은 프로세스가 실행되는 동안 update_curr()에서 지속적으로 업데이트 된다.

​

update_curr() (kernel/sched/fair.c)

static void update_curr(struct cfs_rq *cfs_rq) { .. u64 delta_exec; .. delta_exec = now - curr->exec_start; .. curr->vruntime += calc_delta_fair(delta_exec, curr); update_min_vruntime(cfs_rq); 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; }

6번째 줄 : delta_exec는 코드에서 볼 수 있듯이 프로세스가 실행된 시간이다.

8번째 줄 : calc_delta_fair()를 호출하여 얻은 vruntime 증가분을 curr->vruntime 필드에 저장한다.

​

위 소스코드에서 본 변수이름을 살려서 vruntime 계산 공식을 쓰면 다음과 같다. (NICE_O_LOAD는 1024로 고정되어 있다)

​

출처 : http://rousalome.egloos.com/10002542

​

즉, load weight이 분모이니 우선순위가 높은 프로세스는 vruntime이 서서히 증가한다. vruntime은 다음과 같은 특징을 가지게 된다.

- CFS는 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택한다

- vruntime은 프로세스가 실행을 하면 할수록 계속 증가한다

- vruntime이 천천히 커질수록 스케줄러에 의해 선택될 확률이 높다. 이 말은 우선순위가 높은 중요한 프로세스는 load weight이 크고 이는 분모로 들어가기 때문에 vruntime이 서서히 증가하고 따라서 스케줄러에 선택될 확률이 높아진다.

- 프로세스가 잠든 상태이면 vruntime은 업데이트 되지 않는다.

- 새로운 프로세스는 0으로 vruntime이 초기화 되어 있다,

---

CFS 관련 세부 함수에 관해 분석한다.

​

프로세스는 자신에게 주어진 타임 슬라이스를 모두 소진하면 선점된다. 즉, CPU에서 실행을 멈추고 CPU를 비우게 되는 것이다. 이를 커널에서 관리하는 방법을 소스코드를 통해 분석한다.

CFS 관련 세부 함수의 흐름도

scheduler_tick() (kernel/sched/core.c)

void scheduler_tick(void) { int cpu = smp_processor_id(); struct rq *rq = cpu_rq(cpu); struct task_struct *curr = rq->curr; struct rq_flags rf; sched_clock_tick(); rq_lock(rq, &rf); update_rq_clock(rq); curr->sched_class->task_tick(rq, curr, 0);

5번째 줄 : rq->curr필드에 접근하여 현재 실행중인 프로세스의 태스크 디스크립터 주소를 가져온다

8번째 줄 : sched_clock_tick()을 호출하여 스케줄링 클록의 틱 정보를 업데이트 한다.

13번째 줄 : 프로세스 태스크 디스크립터의 sched_class 필드 중 task_tick에 저장된 함수를 호출한다. 일반 프로세스는 CFS 스케줄러 클래스를 사용하므로 task_tick 필드에 등록된 함수는 task_tick_fair()이다.

​

task_tick_fair() (kernel/sched/fair.c)

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); }

8번째 줄에서 entity_tick()를 호출한다.

​

entity_tick() (kernel/sched/fair.c)

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued) { update_curr(cfs_rq); update_load_avg(cfs_rq, curr, UPDATE_TG); update_cfs_group(curr); .. if (cfs_rq->nr_running > 1) check_preempt_tick(cfs_rq, curr); }

11~12번째 줄 : 현재 런큐에서 삽입된 프로세스의 개수가 1보다 많으면 check_preempt_tick()를 호출한다.

​

check_preempt_tick() (kernel/sched/fair.c)

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)); .. return ; } 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)); }

이 함수는 1. 현재 CPU에서 실행 중인 프로세스가 소진한 타임 슬라이스 정보를 읽고 2. 프로세스가 타임슬라이스를 모두 소진했으면 resched_curr()를 호출하여 선점 요청을 한다. 즉, 현재 실행 중인 프로세스의 thread_info 구조체의 flags 필드에 _TIF_NEED_RESCHED를 설정한다.

​

8번째 줄 : sched_slice()를 호출하여 프로세스의 타임 슬라이스를 읽는다.

9번째 줄 : 프로세스가 소진한 타임 슬라이스의 시각을 계산해 delta_exec 지역변수에 저장한다.

10번째 줄 : 타임 슬라이스를 소진했다면 (delta_exec>ideal_runtime) resched_curr()를 호출하여 해당 프로세스에 대해 선점 요청을 한다. 그리고 함수를 종료한다.

16번째 줄 : 만약 프로세스가 부여받은 최소 실행 시각보다 타임 슬라이스가 작은 경우 바로 함수를 종료한다.

19번째 줄 : 현재 프로세스가 레드 블랙 트리에서 가장 왼쪽 노드에 있는지 체크한다. 이 경우 22번째 줄에 가서 함수를 종료한다. (그런데 가장 왼쪽에 있으면 delta는 0인것 같은데 이해가 안된다)

---

이번에는 프로세스를 vruntime 키 값으로 CFS 런큐의 레드 블랙 트리에 등록하고 CFS가 다음 프로세스를 레드 블랙 트리에서 선택하는 과정을 살펴본다.

​

프로세스는 실행 요청을 할 때 자신을 런큐에 등록한다. 이 과정에서 CFS는 실행 요청을 한 프로세스의 vruntime을 기준으로 레드 블랙 트리에 등록한다. 세부 동작은 enqueue_entity()에서 확인한다.

​

enqueue_entity() (kernel/sched/fair.c)

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) { bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED); bool curr = cfs_rq->curr == se; .. update_curr(cfs_rq); .. account_entity_enqueue(cfs_rq, se); .. if (!curr) __enqueue_entity(cfs_rq, se); se->on_rq = 1;

7번째 줄 : update_curr를 호출하여 스케줄러의 세부 엔티티 정보를 업데이트 한다.

9번째 줄 : account_entity_enqueue()를 호출하여 다음과 같은 동작을 수행한다.

- update_load_add()를 호출하여 런큐에 삽입하는 프로세스의 load weight를 CFS 런큐의 load.weight필드에 더한다

- nr_running 필드를 1만큼 증가시킨다

11번째 줄 : __enqueue_entity()를 호출한다.

​

__enqueue_entity() (kernel/sched/fair.c)

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node; struct rb_node *parent = NULL; struct sched_entity *entry; bool leftmost = true; while (*link) { parent = *link; entry = rb_entry(parent, struct sched_entity, run_node); if (entity_before(se, entry)) { link = &parent->rb_left; } else { link = &parent->rb_right; leftmost = false; } } rb_link_node(&se->run_node, parent, link); rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost); }

9~19번째 줄 : while 루프로 레드 블랙 트리에 추가할 위치를 찾기 위해 vruntime을 key 값으로 노드를 탐색하는 루틴이다. 이 때 만약 런큐에 삽입하는 프로세스의 vruntime이 가장 작다면 해당 프로세스의 노드를 &cfs_rq->tasks_timeline에 저장한다. &cfs_rq->tasks_timeline은 vruntime 캐시라고 부르며 스케줄러가 다음 프로세스를 선택할 때 사용한다.

21~23번째 줄 : 찾은 위치로 &se->run_node를 레드 블랙 트리에 연결한다.

---

스케줄러는 __schedule()에서 pick_next_task()를 호출하여 다음에 실행할 프로세스를 선택한다. 다음과 같은 함수 흐름으로 __pick_first_entry()를 호출하여 레드 블랙 트리의 맨 왼쪽에 위치한 노드의 프로세스를 선택한다.

pick_next_entity() (kernel/sched/fair.c)

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); struct sched_entity *se;

4번째 줄 : __pick_first_entity()를 호출하여 레드 블랙 트리의 맨 왼쪽에 있는 노드에 있는 스케줄링 엔티티를 읽는다.

​

__pick_first_entity() (kernel/sched/fair.c)

struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) { struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline); if (!left) return NULL; return rb_entry(left, struct sched_entity, run_node); }

3번째 줄 : tasks_timeline으로 맨 왼쪽 노드를 읽는다.

​

CFS에서는 다음에 실행할 프로세스를 선택할 때 레드 블랙 트리의 맨 왼쪽에 있는 노드의 프로세스를 선택한다는 것을 알 수 있었다.

 

[출처] CFS 스케줄러|작성자 pwr2011