이번 소절에서는 vruntime 핵심 동작과 관련된 커널 소스 코드를 분석합니다.
프로세스를 vruntime 기준으로 CFS 런큐 레드 블랙 트리에 등록
CFS가 다음 프로세스를 레드 블랙 트리에서 선택(pick)하는 과정
프로세스를 vruntime 기준으로 CFS 런큐 레드 블랙 트리에 등록
프로세스는 실행 요청을 할 때 자신을 런큐에 등록합니다. 이 과정에서 다음 동작을 처리합니다.
CFS는 실행 요청을 한 프로세스의 vruntime과 이미 런큐에 등록된 프로세스들의
vruntime을 비교한 후, 레드 블랙 트리에 등록을 한다.
세부 동작은 enqueue_entity() 함수에서 확인할 수 있습니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
1 static void
2 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
3 {
4 bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
5 bool curr = cfs_rq->curr == se;
...
6 update_curr(cfs_rq);
...
7 account_entity_enqueue(cfs_rq, se);
...
8 if (!curr)
9 __enqueue_entity(cfs_rq, se);
10 se->on_rq = 1;
...
11 }
6 번째 줄 코드에서 update_curr() 함수를 호출해서 스케줄러 세부 엔티티 정보를 업데이트합니다.
6 update_curr(cfs_rq);
다음 7 번째 줄 코드를 보겠습니다.
7 account_entity_enqueue(cfs_rq, se);
account_entity_enqueue() 함수를 호출해서 다음과 같은 동작을 수행합니다.
update_load_add()함수 호출로 런큐에 Enqueue하는 프로세스의 load weight를 CFS 런큐 load wieght에 더함
nr_running 필드를 +1만큼 증감시킴
다음 9 번째 줄 코드를 보겠습니다.
8 if (!curr)
9 __enqueue_entity(cfs_rq, se);
__enqueue_entity() 함수를 호출합니다.
__enqueue_entity()
이어서 __enqueue_entity() 함수 코드를 분석하겠습니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
1 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
2 {
3 struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
4 struct rb_node *parent = NULL;
5 struct sched_entity *entry;
6 bool leftmost = true;
7
8
9 while (*link) {
10 parent = *link;
11 entry = rb_entry(parent, struct sched_entity, run_node);
12
13 if (entity_before(se, entry)) {
14 link = &parent->rb_left;
15 } else {
16 link = &parent->rb_right;
17 leftmost = false;
18 }
19 }
20
21 rb_link_node(&se->run_node, parent, link);
22 rb_insert_color_cached(&se->run_node,
23 &cfs_rq->tasks_timeline, leftmost);
24 }
9~19 번째 줄 코드 블락은 while 루프입니다. 레드 블랙 트리에 추가할 위치를 찾기 위해 탐색하는 루틴입니다.
먼저 13~18 번째 줄 코드를 보겠습니다.
13 if (entity_before(se, entry)) {
14 link = &parent->rb_left;
15 } else {
16 link = &parent->rb_right;
17 leftmost = false;
18 }
13~14 번째 줄 코드를 실행하면 다음과 같은 일을 합니다.
레드 블랙 트리에서 탐색한 노드보다 등록한 프로세스의 vruntime이 작으면 노드의
왼쪽 자식 노드를 선택한다.
else문인 16~17 번째 줄 코드는 다음과 같이 동작합니다.
탐색한 노드보다 vruntime이 클 경우 오른쪽 자식 노드를 선택한다.
만약 런큐에 enqueue하는 프로세스의 vruntime이 가장 적은 경우 이를 어떻게 처리할까요?
해당 프로세스의 노드를 &cfs_rq->tasks_timeline에 저장한다.
&cfs_rq->tasks_timeline 는 vruntime 캐시라고 부르며 스케줄러가 다음 프로세스를 선택할 때 사용합니다.
다음 22 번째 줄입니다.
22 rb_insert_color_cached(&se->run_node,
23 &cfs_rq->tasks_timeline, leftmost);
프로세스의 &se->run_node를 레드 블랙 트리에 연결합니다.
여기까지 프로세스가 런큐에 Enqueue할 때 vruntime을 레드 블랙 트리에 등록하는 코드 흐름을 살펴봤습니다. 스케줄러는 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택하는데 이 정보는 &cfs_rq->tasks_timeline 자료구조에 저장돼 있습니다.
&cfs_rq->tasks_timeline를 vruntime 캐시라고 합니다.
CFS가 다음 프로세스를 레드 블랙 트리에서 선택(pick)하는 과정
스케줄러는 __schedule() 함수에서 pick_next_task() 함수를 호출해서 다음에 실행할 프로세스를 선택합니다. 다음 함수 흐름으로 __pick_first_entity() 함수를 호출해서 레드 블랙 트리 가장 왼쪽에 위치한 노드의 프로세스를 선택합니다.
[그림 10.31] 프로세스가 레드 블랙 트리에서 다음에 실행할 프로세스를 선택
pick_next_entity()
pick_next_entity() 함수를 먼저 보겠습니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
1 static struct sched_entity *
2 pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
3 {
4 struct sched_entity *left = __pick_first_entity(cfs_rq);
5 struct sched_entity *se;
4 번째 줄 코드와 같이 __pick_first_entity() 함수를 호출해서 레드 블랙 트리 가장 왼쪽에 있는 노드에 있는 스케줄링 엔티티를 읽습니다.
__pick_first_entity()
이번엔 __pick_first_entity() 함수를 분석하겠습니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
1 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
2 {
3 struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
4
5 if (!left)
6 return NULL;
7
8 return rb_entry(left, struct sched_entity, run_node);
9 }
레브 블랙 트리인 tasks_timeline으로 가장 왼쪽 노드를 읽습니다.
3 struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
8 return rb_entry(left, struct sched_entity, run_node);
CFS는 다음에 실행할 프로세스를 선택할 때 레드 블랙 트리 가장 왼쪽에 있는 노드에 있는 프로세스를 선택합니다.
"혹시 궁금한 점이 있으면 댓글로 질문 남겨주세요. 아는 한 성실히 답변 올려드리겠습니다!"
Thanks,
Austin Kim(austindh.kim@gmail.com)
Reference(프로세스 스케줄링)
스케줄링 소개
프로세스 상태 관리
어떤 함수가 프로세스 상태를 바꿀까?
스케줄러 클래스
런큐
CFS 스케줄러
CFS 관련 세부 함수 분석
선점 스케줄링(Preemptive Scheduling)
프로세스는 어떻게 깨울까?
스케줄링 핵심 schedule() 함수 분석
컨택스트 스위칭
스케줄링 디버깅
스케줄링 프로파일링
CPU에 부하를 주는 테스트
CPU에 부하를 주지 않는 테스트
# Reference: For more information on 'Linux Kernel';
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 1
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 2
최근 덧글