CFS 스케줄러

CFS 스케줄러란?

스케줄러는 CPU 자원을 프로세스들에게 분배하는 OS의 중요한 일부분이다.
2007년 발표 된 리눅스 커널의 스케줄러인 CFS(Completely Fiar Scheduler)는
RSDL(Rotating Staircase Deadline) 스케줄러를 기초로 한 RB-트리(Red-Black Tree) 데이터 구조를 사용하는 O(logN) 성능을 가지는 스케줄러이다.
CFS는 시간단위로 나노초를 사용한다.

만약 A, B 두 개의 태스크가 진행되고 있다면 A와 B의 CPU 사용시간은 항상 1:1로 같아야한다.
그러나 두 태스크가 번갈아 가며 수행되므로 임의의 시점에 두 태스크의 CPU 사용 시간이 항상 1:1로 같을 수 없다.
따라서 CFS는 정해진 ‘시간 단위’로 봤을때 시스템에 존재하는 태스크들에게 공평한 CPU 시간을 할당하는 것을 목표로 한다.
만약 1초를 ‘시간 단위’로 한다면 0.5초 동안 A 태스크를 수행시키고, 그런 뒤 0.5초간 B 태스크를 수행시킴으로써 1초가 지난 이후 A와 B의 CPU 사용시간이 1:1이 되도록 하는 것이다.
CFS의 기본 개념은 작업에 프로세서 시간을 제공할 때 밸런스(공평성)를 유지하는 것이다.
즉 프로세스에 공평한 양의 프로세서(=CPU)가 제공되어야 한다.
작업 시간의 밸런스가 무너진 경우에는(다른 작업에 비해 하나 이상의 작업에 공평한 양의 시간이 주어지지 않은 경우) 작업 시간이 적게 지정된 작업에 실행 시간이 주어져야 한다.

또한 CFS에는 대기자 공평성이라는 개념도 포함되어 있다.
이 개념은 현재 실행할 수 없는 작업(예를 들어, I/O를 대기 중인 작업)이 나중에 프로세서가 필요할 때 대기했던 시간에 상응하는 프로세서 시간을 받을 수 있도록 보장한다.

하지만 CFS는 이전 Linux 스케줄러와는 달리 실행 큐에서 작업을 관리하지 않고 시간순으로 정렬된 RB-트리를 유지한다.
Red-Black 트리에는 흥미롭고 유용한 두 가지 특성이 있다.
첫 번째는 스스로 밸런스를 조절한다는 것이다.
즉, 이 트리의 모든 경로는 다른 경로보다 두 배 이상 길어지지 않는다.
두 번째는 트리에 대한 작업이 O(log n) 시간(여기서 n는 트리의 노드 수임) 내에 발생한다는 것이다.
따라서 작업을 빠르고 효율적으로 삽입하거나 삭제할 수 있다.