CFS(Completely Fair Scheduler)는 2.6.23 커널 버전 이후 적용된 리눅스의 기본 스케줄러입니다. CFS이란 용어를 그대로 풀면 ‘완벽하게 공정한 스케줄러’라고 해석할 수 있습니다. 즉, 런큐에서 실행 대기 상태로 기다리는 프로세스를 공정하게 실행하도록 기회를 부여하는 스케줄러입니다.
이번 절에서는 CFS 알고리즘의 개념을 알아보고 코드 분석으로 세부 동작을 살펴보겠습니다.
CFS는 실행 대기 상태인 프로세스들을 우선순위에 따라 최대한 공정하게 실행하는 스케줄러입니다. CFS 세부 동작과 알고리즘을 이해하려면 다음과 같은 개념을 파악할 필요가 있습니다.
타임 슬라이스
우선순위
가상 실행 시간(vruntime)
이번 소절에는 먼저 CFS를 이루는 3가지 주요 개념을 소개합니다.
타임 슬라이스란
타임 슬라이스는 무엇을 말하는 것일까요? 먼저 용어의 뜻부터 살펴봅시다.
타임 슬라이스는 사실 운영체제에서 쓰는 용어입니다.
'스케줄러가 프로세스에게 부여한 실행 시간'
CFS는 프로세스마다 실행할 수 있는 단위 시간을 부여하는데 이를 타임 슬라이스라고 부릅니다. 프로세스는 주어진 타임 슬라이스를 다 소진하면 컨텍스트 스위칭됩니다.
타임 슬라이스로 프로세스를 관리하는 가장 큰 이유는 모든 프로세스가 최대한 CPU에서 실행할 수 있는 기회를 부여하기 위해서입니다. 만약 타임 슬라이스가 없다면 프로세스 실행 단위를 관리하기 어려울 것입니다.
스케줄러 입장에서는 타임 슬라이스는 프로세스 실행 시간을 관리하기 위한 단위라고 볼 수 있습니다. 하지만 프로세스 입장에서 타임 슬라이스는 모래시계와 같습니다. 만약 프로세스에게 부여된 타임 슬라이스가 10ms이라고 가정해봅시다. 프로세스가 5ms 시간 동안 실행했다면 실행할 수 있는 시간이 5ms 남은 것입니다. 즉 5ms 만큼 타임 슬라이스를 소진한 것입니다.
CFS 스케줄러는 타이머 인터럽트가 발생했을 때 주기적으로 프로세스가 얼마나 타임 슬라이스를 소진하고 있는지 체크합니다.
프로세스가 타임 슬라이스를 모두 소진하면 스케줄러는 어떤 동작을 할까?
스케줄러는 해당 프로세스가 선점 스케줄링 대상이라고 마킹합니다.
이 동작을 선점 스케줄링 요청을 한다라고도 부릅니다. 해당 프로세스의 struct thread_info 필드 flags에 TIF_NEED_RESCHED 플래그를 설정합니다.
선점 스케줄링 대상으로 마킹된 프로세스는 컨텍스트 스위칭됩니다.
우선순위란
우선순위는 CFS 스케줄러가 컨텍스트 스위칭 시 다음 프로세스를 선택하는 기준 중 하나입니다.
CFS 스케줄러는 우선순위가 높은 프로세스에 대해 다음과 같이 처리합니다.
가장 먼저 CPU에서 실행시킨다.
더 많은 타임 슬라이스를 할당해준다.
리눅스는 총 140단계의 우선순위 제공하며 다음과 같은 범위입니다.
0~99: RT(실시간) 프로세스
100~139: 일반 프로세스
CFS 스케줄러는 프로세스마다 설정된 우선순위를 기준으로 가상 실행 시간을 설정합니다. 이를 위해 커널이 프로세스 우선순위를 어떤 방식으로 처리하는지 파악할 필요가 있습니다.
가상 실행 시간이란
가상 실행시간(vruntime)은 가상이란 의미인 형용사인 "virtual"와 실행 시간을 뜻하는 "runtime"을 붙여 만든 용어입니다. 즉, vruntime을 가상 실행시간이라고 해석할 수 있습니다.
커널에서 vruntime는 무엇이라고 설명할 수 있을까요?
프로세스가 그 동안 실행한 시간을 정규화한 시간 정보이다.
CFS가 프로세스를 선택할 수 있는 load weight와 같은 여러 지표가 고려된 실행 시간입니다.
vruntime은 다음과 같은 특징을 지닙니다.
CFS는 런큐에 실행 대기 상태에 있는 프로세스 중 vruntime이 가장 적은 프로세스를 다음에 실행할 프로세스로 선택합니다.
우선순위가 높은 프로세스는 우선순위가 낮은 프로세스에 비해 vruntime가 더 서서히 증가합니다. 즉, 우선순위가 높은 프로세스가 낮은 프로세스에 비해 vruntime가 덜 증가한다는 것입니다.
여기서 한 가지 의문이 생깁니다.
vruntime은 어느 자료구조에서 확인할 수 있을까?
프로세스는 자신의 태스크 디스크립터 &se.vruntime 필드에 vruntime 정보를 저장합니다.
다음은 Trace32로 확인한 vruntime 정보입니다.
01 (struct task_struct *) (struct task_struct*)0xA36AF9180
...
02 (struct sched_class *) sched_class = 0xA9208BE0,
03 (struct sched_entity) se = (
04 (struct load_weight) load = ((long unsigned int) weight = 90891264,
05 (struct rb_node) run_node = ((long unsigned int) __rb_parent_color = 1,
06 (struct list_head) group_node
07 (unsigned int) on_rq = 0
08 (u64) exec_start = 13097506209
09 (u64) sum_exec_runtime = 15165884
10 (u64) vruntime = 3532405028
10 번째 줄과 같이 vruntime은 3532405028임을 알 수 있습니다.
"혹시 궁금한 점이 있으면 댓글로 질문 남겨주세요. 아는 한 성실히 답변 올려드리겠습니다!"
Thanks,
Austin Kim(austindh.kim@gmail.com)
Reference(프로세스 스케줄링)
스케줄링 소개
프로세스 상태 관리
어떤 함수가 프로세스 상태를 바꿀까?
스케줄러 클래스
런큐
CFS 스케줄러
CFS 관련 세부 함수 분석
선점 스케줄링(Preemptive Scheduling)
프로세스는 어떻게 깨울까?
스케줄링 핵심 schedule() 함수 분석
컨택스트 스위칭
스케줄링 디버깅
스케줄링 프로파일링
CPU에 부하를 주는 테스트
CPU에 부하를 주지 않는 테스트
# Reference: For more information on 'Linux Kernel';
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 1
디버깅을 통해 배우는 리눅스 커널의 구조와 원리. 2
최근 덧글