reference:
- "리눅스 커널 내부구조" / 백승재, 최종무
- "Operating Systems: Three Easy Pieces" / Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
리눅스는 일반 태스크를 위해 사용하고 있는 스케줄링 기법은 CFS(Completely Fair Schedular)이다.
완벽하게 공평한 스케줄링이란 보통 CPU 사용시간의 공평한 분배를 의미한다. 만약 A, B 두개의 태스크가 수행 중이라면, A와 B의 CPU 사용시간이 항상 1:1로 같아야 한다는 것이다.
결국 시스템에 존재하는 태스크들에게 공평한 CPU 시간을 할당하는 것을 목표로 한다. 만약 1초를 시간 단위로 한다면, 0.5초동안은 A 태스크 수행, 이 후 0.5초 동안은 B 태스크를 수행시킴으로써 1초가 지난 후 A와 B의 CPU 사용시간이 같도록 하는 것이다. 여기서 말한 시간 단위가 너무 길면 태스크의 반응성이 떨어질 것이고, 반대로 너무 짧다면 스케줄링과 문맥교환으로 인한 오버헤드가 높아질 것이므로 적절한 값을 설정하는 것이 중요하다.
런큐에 N개의 태스크가 존재한다면, 정해진 시간 단위를 N으로 나누어 N개의 태스크에게 할당해준다.
태스크의 우선순위 반영에 관해서라면 우선순위가 더 높은 태스크에게 가중치를 두어 좀 더 긴 시간 CPU를 사용할 수 있도록 해준다. 결과적으로 우선순위가 낮은 태스크보다 비교적 일찍 자신에게 주어진 일을 완료할 수 있게 만들어준다.
이를 위해 리눅스는 vruntime 개념을 도입하였다. 각 태스크는 자신만의 vruntime 값을 가지며, 이 값은 스케줄링되어 CPU를 사용하는 경우 사용시간과 우선순위를 고려하여 증가하게 된다.
일반 태스크의 우선순위는 별도의 지정(nice()같은 시스템 콜)이 없다면 부모의 우선순위와 같다.
일반 태스크는 사용자 수준에서 볼 때 -20~0~19 사이의 우선순위를 가지며, 이 값은 커널 내부적으로 priority + 120으로 변환되어 실제 우선순위는 100~139에 해당하게 되고, 항상 실시간 태스크의 우선순위보다 낮은 것이 보장된다.
아래 코드는 task_struct 구조체에 저장되는 vruntime 필드와, vruntime 갱신 시 사용되는 우선순위에 따른 가중치를 보여준다.
struct task_struct {
...
const struct sched_calss* sched_class;
struct sched_entity se;
...
};struct sched_entity {
...
struct load_weight load;
u64 vruntime;
...
};struct load_weight {
unsigned long weight;
u32 inv_weight;
};만약 사용자가 태스크에 -20의 우선순위를 부여했다면 88761의 가중치 값이, 0을 지정했다면 1024의 가중치 값이 해당 태스크의 task_struct로부터 접근가능 한 weight 필드에 저장되는 것이다. 우선순위가 더 높은 태스크에게 가중치를 더 높게 두어 좀 더 긴 시간 CPU를 사용할 수 있도록 하는 것.
리눅스는 주기적으로 발생되는 타이머 인터럽트 핸들러에서 scheduler_tick() 함수를 호출함으로써 현재 수행중인 태스크의 vruntime 값을 갱신한다. 이때 runtime 값의 증가분은 다음과 같이 계산된다.
vruntime += physicalruntime * (weight_0 / weight_curr)
weight_curr: 현재 태스크의 weight 값
weight_0: 우선 순위 0에 해당하는 weight 값
예를 들어 현재 수행중인 태스크의 우선순위가 -20이고 1초간 수행되었다면 vruntime은 약 0.0115초 증가, 우선순위가 10인 태스크가 1초간 수행되었다면 vruntime이 약 9.3091초 가량 증가된다. 결국 우선순위가 높은 태스크의 경우 종 더 긴 시간 CPU를 사용할 수 있도록 시간이 느리게 흘러가는 것처럼 관리하고, 우선순위가 낮은 태스크의경우 반대로 시간이 빠르게 흘러가는 것처럼 관리하는 것을 의미한다.
실제 스케줄링 대상이 되는 태스크를 골라낼 때 가장 작은 vruntime 값을 가지는 태스크가 가장 과거에 CPU를 사용했다고 간주하여 이러한 태스크를 다음번 스케줄링 대상으로 선정한다. 리눅스는 이러한 방식으로 공평한 스케줄링을 수행하려 노력한다.
리눅스는 가장 낮은 vruntime 값을 가지는 태스크를 빠르게 찾아내기 위해 실시간 태스크 관리와 같이 RBTree 자료구조를 사용한다. 각 태스크는 vruntime 값을 키로 하여 RBTree에 정렬되어 있으며, 이 트리에서 가장 좌측에 존재하는 태스크가 다음번 스케줄링 대상이 된다.
단, 현재 수행중인 태스크의 vruntime 값이 다른 태스크보다 커지더라도, 해당 태스크의 타임 슬라이스 혹은 스케줄링간 최소 지연 시간 내에서는 계속 수행을 보장.
