여래 개의 태스크들 중에서 다음번 수행시킬 태스크를 선택하여 CPU라는 자원을 할당하는 과정을 스케줄링이라고 부릅니다.
리눅스 스케줄러는 커널 2.6부터 O(1)이라는 이름의 새로운 스케줄러가 사용되고 있으며, 최근 2.6.23버전부터는 CFS
(Completely Fair Scheduler)라는 또 다른 새로운 스케줄러가 도입되었습니다.
우선 기존의 O(1) 스케줄러가 어떠한 문제점을 가지고 있는지 알아보겠습니다. 만약 시스템에 유사한 특성을 갖는 태스크가
존재한다면 CPU를 공정하게 반반씩 나누어 사용하는 것이 좋을 것입니다. 이때 사용자 태스크의 우선순위가 0(nice값이 0)
이라면 각각의 태스크는 기본적으로 100ms의 time slice를 가지게 되므로 보통 100ms마다 문맥 전환이 일어납니다. 하지만
만약 우선순위가 19(nice값이 19)인 태스크라면 각각의 태스크는 기본적으로 5ms의 time slice를 할당받기 때문에 5ms마다
문맥전환이 일어나는 비효율성이 유발됩니다. 또한 우선순위 0과 1의 사용자 태스크는 각각 100ms와 95ms의 time slice를
할당 받는 반면 우선순위 18과 19의 태스크는 각각 10ms와 5ms의 time slice를 할당 받게 되므로 한 단계의 우선순위 차이로
인해 두 배의 할당 시간 차이가 생깁니다. 또한 새로운 태스크가 계속 생기는 경우 expired 배열에 들어가있는 태스크의 평균
대기시간이 길어질 수 있는 문제점이 제기되었습니다.
따라서 리눅스 커널 2.6.23 부터는 "이상적이고, 정확한 멀티태스킹 CPU"를 목표로 하는 CFS(Completely Fair Scheduler)
라는 새로운 스케줄러가 도입되었습니다. CFS는 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 세 가지의 정책을
지원합니다. 태스크의 입장에서 본다면 이제 더 이상 SCHED_OTHER 스케줄링 정잭은 존재하지 않으며 대신 CFS 모듈이
제공하는 SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE 세 가지의 정책과, 실시간 스케줄링 모듈이 제공하는
SCHED_RR과 SCHED_FIFO 정책을 사용하는 것이 가능합니다.
CFS를 위한 런 큐를 살펴보면, struct cfs_rq라는 자료구조와 struct rt_rq라는 이름의 자료구조를 담고 있습니다.
struct_rt_rq를 보면 알 수 있듯이 실시간 스케줄링 기법은 기존과 마찬가지로 비트맵을 이용한 우선순위 기반 스케줄링을
하고 있음을 알 수 있습니다. 한편 비 실시간 태스크는 struct cfs_rq 자료구조로 관리됩니다.
struct cfs_rq 자료구조에서 태스크들은 rb_node라는 필드로 관리됩니다. 이 자료구조로부터 우리는 CFS 스케줄러가 레드-
블랙 트리(Red-Black Tree)를 이용하여 태스크를 관리하고 있음을 확인할 수 있습니다. 이 기법은 기존 O(1) 스케줄러와 달리
우선순위 배열을 유지하지 않습니다. 대신 우선순위를 고려한 가중치를 통해 태스크별로 키(key)값을 정하고, 이 키 값을
이용하여 태스크를 레드-블랙 트리로 유지합니다. 이 트리에서 가장 좌측에 존재하는 태스크가 다음번 스케줄링의 대상이
됩니다(rb_left_most 필드). 스케줄링 된 태스크는 수행 될수록 키 값이 증가되며 따라서 트리의 가장 좌측에서 점차 우측으로
이동됩니다. 반면 스케줄링 되지 않은 태스크는 대기하는 동안 점점 자신의 키 값이(상대적으로) 감소되며 따라서 점차 트리의
좌측으로 이동하게 됩니다.
