CFS는 용어 그대로 프로세스를 공정하게 실행하도록 구현된 스케줄러입니다.
CFS의 목표는 런큐에 있는 실행 대기 상태 프로세스에게 CPU 시간을 우선순위에 따라 공정하게 할당하는 것입니다. 우선순위가 높은 프로세스는 CPU 시간을 더 부여하고 우선순위가 낮은 프로세스는 CPU 시간을 적게 할당합니다.
load weight 소개
CFS 적용 전 프로세스에게 우선순위의 절대값을 기준으로 타임 슬라이스를 할당 했었습니다. 하지만 프로세스에게 공정한 CPU 시간을 할당 할 수 없었습니다. 그래서 CFS에서는 프로세스에게 공정한 CPU 시간 할당을 위해 우선순위의 비율로 CPU 시간을 분배하게 됐습니다.
정수형 우선순위를 절대값이 아니라 우선순위 비율로 정한 것이다.
이것이 load weight입니다. 프로세스가 더 큰 load weight 를 갖고 있으면 CFS는 더 자주 실행합니다.
이해를 돕기 위해 관련 소스 코드를 볼까요?
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/core.c]
01 static void set_load_weight(struct task_struct *p)
02 {
03 int prio = p->static_prio - MAX_RT_PRIO;
04 struct load_weight *load = &p->se.load;
...
05 if (update_load && p->sched_class == &fair_sched_class) {
06 reweight_task(p, prio);
07 } else {
08 load->weight = scale_load(sched_prio_to_weight[prio]);
09 load->inv_weight = sched_prio_to_wmult[prio];
10 }
set_load_weight() 함수는 프로세스가 갖고 있는 우선순위를 load weight로 변환하는 역할을 수행합니다.
3 번째 줄 코드를 보면 프로세스 태스크 디스크립터에 저장된 static_prio 우선순위를 변환해 prio 변수에 저장합니다.
3 int prio = p->static_prio - MAX_RT_PRIO;
여기서 MAX_RT_PRIO는 100입니다. 프로세스의 static_prio 범위는 100~139이니 prio 변수의 범위는 0~39입니다.
08번재 줄 코드를 보겠습니다.
08 load->weight = scale_load(sched_prio_to_weight[prio]);
sched_prio_to_weight[] 이란 배열에 prio 변수로 접근해 load->weight 에 저장합니다.
sched_prio_to_weight[] 배열 선언부를 보겠습니다.
1 const int sched_prio_to_weight[40] = {
2 /* -20 */ 88761, 71755, 56483, 46273, 36291,
3 /* -15 */ 29154, 23254, 18705, 14949, 11916,
4 /* -10 */ 9548, 7620, 6100, 4904, 3906,
5 /* -5 */ 3121, 2501, 1991, 1586, 1277,
6 /* 0 */ 1024, 820, 655, 526, 423,
7 /* 5 */ 335, 272, 215, 172, 137,
8 /* 10 */ 110, 87, 70, 56, 45,
9 /* 15 */ 36, 29, 23, 18, 15,
10 };
sched_prio_to_weight 배열은 우선순위 별로 가중치를 적용한 테이블입니다.
2 번째 줄과 같이 가장 우선순위가 큰 load weight는 88761임을 알 수 있습니다.
load weigth는 프로세스 태스크 디스크립터 다음 필드에 저장합니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/include/linux/sched.h]
01 struct task_struct {
...
02 const struct sched_class *sched_class;
03 struct sched_entity se;
04
05 struct sched_entity {
06 struct load_weight load;
07
08 struct load_weight {
09 unsigned long weight;
10 u32 inv_weight;
11 };
위 선언부 코드를 종합하면 다음 필드에 load weigth를 저장한다는 사실을 알 수 있습니다.
current->se.load.weight
여기서 current 매크로의 구조체는 struct task_struct입니다.
또한 런큐 구조체 cfs 필드에는 런큐에 등록한 프로세스들의 load weight를 합한 load weight를 저장합니다.
1 (struct rq *)0xBCF15A00
2 (raw_spinlock_t) lock = ((arch_spinlock_t) raw_lock
3 (unsigned int) nr_running = 2
...
4 (u64) nr_switches = 7403
5 (struct cfs_rq) cfs = (
6 (struct load_weight) load = (
7 (long unsigned int) weight = 2097152
8 (u32) inv_weight = 0
위 정보는 Trace32에서 확인한 런큐의 필드 정보입니다. 런큐 cfs 필드는 CFS 런큐 구조체인데 load 필드 내에 weight 정보를 확인할 수 있습니다.
CFS 런큐 load weight는 7번째 줄과 같이 2097152 입니다.
이렇게 런큐의 load weight는 런큐에 실행을 기다리는 전체 프로세스들의 load weight를 더한 결과 입니다. 런큐의 load wieght와 프로세스 개수 비율을 고려해서 프로세스에게 타임 슬라이스를 부여합니다.
이어서 스케줄러에서 타임 슬라이스를 어떻게 계산하는지 살펴보겠습니다.
타임 슬라이스 알아보기
CFS에서 프로세스 타임 슬라이스는 다음 공식으로 계산할 수 있습니다.
[그림 10.26] 타임 슬라이스 계산식
여기서 스케줄링 레이턴시란 CFS 런큐에서 실행 대기 상태로 기다리는 프로세스들의 타임 슬라이스를 합한 값입니다.
이번에는 2가지 조건에서 각각 프로세스에 타임 슬라이스를 어떻게 할당하는지 알아봅시다.
만약 CPU1 런큐에 2개 프로세스가 있고 각각 static_prio가 120이라고 가정하겠습니다.
먼저 A 프로세스의 load weight는 계산해 보겠습니다.
sched_prio_to_weight 인덱스 = static_prio - 100
20 = 120 - 100
이는 sched_prio_to_weight[] 배열 인덱스입니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/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,
sched_prio_to_weight[20] = 1024가 됩니다.
A와 B 프로세스의 load weight는 각각 1024입니다. A와 B 프로세스의 load weight가 1024이니 CFS 런큐 load weight는 2048가 됩니다.
2048 = 1024 + 1024
다음 계산으로 A와 B프로세스에겐 9ms초 만큼 타임 슬라이스를 할당할 수 있습니다.
분자인 1024는 A와 B 프로세스의 load weight이고 분모인 2048은 CFS load weight입니다.
이렇게 계산한 타임 슬라이스는 다음 그림과 같이 확인할 수 있습니다.
[그림 10.27] A와 B 프로세스에 할당된 타임 슬라이스
A와 B 프로세스에게 9000000ns(9밀리초) 만큼 타임 슬라이스를 부여한 것입니다. 두 프로세스의 우선순위가 같으니 타임 슬라이스도 같습니다.
이번에는 A 프로세스의 static_prio가 119이고 B와 C 프로세스 static_prio가 120인 경우를 살펴봅시다.
먼저 A 프로세스의 load weight를 계산해봅시다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/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,
sched_prio_to_weight[19] = 1277가 됩니다.
1277을 왼쪽으로 10만큼 비트 시프트를 하면 1307648이 됩니다.
1277 << 10
1277 * 1024 = 1307648
B와 C 프로세스의 load weight는 1048576(0x100000)이 됩니다.
1048576 = 1024 << 10
위 정보를 참고로 CFS 런큐 load weight를 계산하면 다음과 같습니다.
3404800 = 1307648 + 1048576 + 1048576
CFS 런큐 load weight는 런큐에 등록된 모든 프로세스의 load weight를 더한 값입니다.
A 프로세스의 타임 슬라이스는 다음 계산식으로 얻을 수 있습니다.
B와 C프로세스의 타임 스라이스 계산 과정은 다음과 같습니다.
A, B와 C 프로세스에게 할당된 타임 슬라이스를 모아 다음 그림으로 표현할 수 있습니다.
[그림 10.28] A, B와 C 프로세스에게 할당된 타임 슬라이스
이렇게 타임 슬라이스는 런큐에 등록된 프로세스 개수와 우선순위 비율 따라 결정됩니다.
vruntime 알아보기
커널에서 vruntime은 프로세스가 그 동안 실행한 시간을 정규화한 시간 정보입니다. CFS 스케줄러가 프로세스를 선택할 수 있는 load weight와 같은 지표가 고려된 실행 시간입니다.
vruntime이 CFS 스케줄러에서 중요한 이유는 무엇일까요? 그것은 다음과 같은 이유 때문입니다.
CFS 스케줄러는 런큐에 등록된 프로세스 중 vruntime 이 가장 적은 프로세스를 다음에
실행할 프로세스로 선택한다.
vruntime는 프로세스가 실행하는 동안 update_curr() 함수에서 지속적으로 업데이트됩니다.
vruntime을 계산하는 공식을 알기 위해선 update_curr() 함수를 분석할 필요가 있습니다.
update_curr() 함수는 정기적 스케줄러를 포함한 다음과 같은 다양한 스케줄링 공통 함수에서 호출됩니다.
enqueue_entity()
dequeue_entity()
put_prev_entity()
check_preempt_wakeup()
yield_task_fair()
task_fork_fair()
참고로 프로세스가 타임 슬라이스를 모두 소진하면 다음 과정으로 선점 스케줄링됩니다.
프로세스 struct thread_info 구조체 flags를 TIF_NEED_RESCHED 플래그로 지정
선점 스케줄링됨(인터럽트 핸들링 후, 시스템 콜 핸들링 후)
update_curr() 함수에서 vruntime 업데이트 과정 확인하기
다음 코드는 update_curr() 함수와 calc_delta_fair() 함수에서 vruntime을 계산하는 부분입니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
01 static void update_curr(struct cfs_rq *cfs_rq)
02 {
...
03 u64 delta_exec;
...
04 delta_exec = now - curr->exec_start;
...
05 curr->vruntime += calc_delta_fair(delta_exec, curr);
06
07 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
08 {
09 if (unlikely(se->load.weight != NICE_0_LOAD))
10 delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
11 return delta;
12}
delta_exec는 다음 코드와 같이 프로세스가 실행한 시각입니다.
4 delta_exec = now - curr->exec_start;
vrumtime 은 다음 5 번째 줄 코드에서 바뀝니다.
5 curr->vruntime += calc_delta_fair(delta_exec, curr);
calc_delta_fair() 함수를 호출해서 얻은 vruntime 증감분을 curr->vruntime 필드에 저장합니다.
위 소스 코드에서 본 변수 이름을 그대로 살리면 vrumtime 계산 공식은 다음과 같습니다.
[그림 10.29] 소스 코드 변수 이름 기준 vruntime 계산 공식
NICE_0_LOAD는 1024이고 &se->load.weight는 프로세스 load weight 정보입니다. 위 공식을 쉽게 풀어 쓰면 다음과 같습니다.
[그림 10.30] vruntime 계산 공식
분모가 load weight 이니 우선순위가 높은 프로세스는 vruntime이 더 천천히 증가합니다.
vruntime 특징 알아보기
vruntime은 다음과 같은 특징을 지닙니다.
1. CFS는 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택합니다.
2. vruntime은 프로세스 실행 시각을 계속 더합니다. 따라서 계속 vruntime은 커지게 됩니다.
3. vruntime이 천천히 커질수록 스케줄러에 의해 선택될 확률이 높습니다. 달리 보면 우선순위가 높은 중요한 프로세스는 vruntime이 서서히 증가합니다. 그 이유는 vruntime 계산식에서 분모가 load weight이기 때문입니다. load weight 값이 클수록 프로세스 우선순위가 높습니다.
4. 프로세스가 잠든 상태(휴면)이면 vruntime은 업데이트되지 않습니다.
일반적인 상황에서 vruntime은 계속 증가합니다. 그런데 새로 생성된 프로세스는 다음 코드와 같이 vruntime 타임을 0으로 초기화합니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/core.c]
1 static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
2 {
3 p->on_rq = 0;
...
4 p->se.vruntime = 0;
새롭게 생성된 프로세스의 vruntime은 0인데 다른 프로세스들은 훨씬 큰 vruntime을 갖고 있을 것입니다. 새롭게 생성된 프로세스는 가장 작은 vruntime을 갖고 있으니 스케줄러가 가장 먼저 실행할 것입니다.
또한 새롭게 생성된 프로세스는 vruntime 값이 0이니 다른 프로세스의 vruntime 만큼 커질 때까지 충분히 많은 시간을 동안 CPU를 점유할 것입니다.
최소 vruntime이란
이런 문제를 해결하기 위해 스케줄러는 최소 vruntime을 주기적으로 계산합니다. 이 값을 새롭게 생성된 프로세스에게 갱신합니다.
최소 vruntime은 update_min_vruntime() 함수에서 갱신됩니다.
[https://github.com/raspberrypi/linux/blob/rpi-4.19.y/kernel/sched/fair.c]
1 static void update_min_vruntime(struct cfs_rq *cfs_rq)
2 {
3 struct sched_entity *curr = cfs_rq->curr;
4 struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);
5
6 u64 vruntime = cfs_rq->min_vruntime;
...
7 /* ensure we never gain time by being placed backwards. */
8 cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
8 번째 줄 코드와 같이 최소 vruntime을 계산해서 CFS 런큐 min_vruntime 필드에 갱신합니다.
세부 코드 분석은 책의 범위를 벗어나는 것 같으니 주기적으로 min_vruntime 즉 최소 vruntime을 계산해 새롭게 생성된 프로세스 vruntime에 갱신하다는 정도로 기억해둡시다.
"혹시 궁금한 점이 있으면 댓글로 질문 남겨주세요. 아는 한 성실히 답변 올려드리겠습니다!"
Thanks,
Austin Kim(austindh.kim@gmail.com)
Reference(프로세스 스케줄링)
스케줄링 소개
프로세스 상태 관리
어떤 함수가 프로세스 상태를 바꿀까?
스케줄러 클래스
런큐
CFS 스케줄러
CFS 관련 세부 함수 분석
선점 스케줄링(Preemptive Scheduling)
프로세스는 어떻게 깨울까?
스케줄링 핵심 schedule() 함수 분석
컨택스트 스위칭
스케줄링 디버깅
스케줄링 프로파일링
CPU에 부하를 주는 테스트
CPU에 부하를 주지 않는 테스트
# Reference: For more information on 'Linux Kernel';
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 1
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 2
최근 덧글