Completely Fair Scheduler

왜 "완전히 공정한" 스케줄러인가

스케줄러의 근본적인 과제는 한정된 CPU 시간을 여러 태스크에 배분하는 것이다. 이전 세대의 리눅스 스케줄러인 O(1) 스케줄러¹는 복잡한 휴리스틱²으로 태스크의 우선순위를 동적으로 조정했지만, 그 복잡성 때문에 특정 워크로드에서 예측하기 어려운 동작을 보였고, 대화형interactive 태스크와 배치batch 태스크를 구분하는 휴리스틱이 종종 오판을 일으켰다.

CFS의 설계 철학은 단순하면서도 강력하다. 이상적인 멀티태스킹 CPU를 실제 하드웨어 위에서 모델링한다. 이상적인 CPU란, $n$개의 태스크가 실행 중이면 각 태스크가 정확히 $\frac{1}{n}$의 CPU 시간을 동시에 받는 가상의 프로세서다. 현실의 CPU는 한 번에 하나의 태스크만 실행할 수 있으므로 이 이상을 그대로 실현할 수는 없지만, CFS는 각 태스크가 이상적인 CPU에서 받았을 시간과 실제로 받은 시간의 차이를 최소화하는 방향으로 스케줄링 결정을 내린다.

이 접근법의 핵심은 공정성fairness의 정의를 수학적으로 명확히 한 것이다. 공정하다는 것은 모든 태스크가 자신의 가중치³에 비례하는 CPU 시간을 받는 것이고, CFS는 이 비례 관계에서 가장 크게 벗어난 태스크 — 즉 CPU 시간을 가장 적게 받은 태스크 — 를 다음에 실행함으로써 공정성을 유지한다.

가상 실행 시간

CFS가 공정성을 추적하는 핵심 지표가 가상 실행 시간virtual runtime, 줄여서 vruntime이다. vruntime은 태스크가 이상적인 CPU에서 소비했을 정규화된 시간을 나타내며, sched_entity 구조체의 vruntime 필드에 나노초 단위로 저장된다.

태스크가 CPU 위에서 delta_exec만큼의 물리적 시간을 실행하면, vruntime은 다음과 같이 갱신된다.

$\text{vruntime} \mathrel{+}= \text{delta\_exec} \times \frac{\text{NICE\_0\_LOAD}}{\text{weight}}$

여기서 $\text{NICE\_0\_LOAD}$는 nice 값 0에 대응하는 기준 가중치(1024)이고, $\text{weight}$는 해당 태스크의 가중치다. 이 공식의 의미를 풀어보면, 가중치가 높은 태스크(우선순위가 높은 태스크)는 같은 물리적 시간을 실행해도 vruntime이 느리게 증가하고, 가중치가 낮은 태스크는 빠르게 증가한다. CFS는 항상 vruntime이 가장 작은 태스크를 다음에 실행하므로, 결과적으로 가중치가 높은 태스크가 더 많은 CPU 시간을 받게 된다.

예를 들어 두 태스크 A와 B가 있고, A의 가중치가 B의 두 배라고 하자. 동일한 물리 시간 동안 A의 vruntime 증가량은 B의 절반이다. A의 vruntime이 느리게 증가하므로 A가 더 자주 "가장 작은 vruntime" 위치에 놓이게 되고, 결과적으로 A는 B보다 약 두 배의 CPU 시간을 할당받는다. 이것이 CFS가 가중치에 비례한 CPU 배분을 달성하는 원리다.

nice 값과 가중치

리눅스에서 태스크의 우선순위는 전통적으로 nice 값으로 표현된다. nice 값의 범위는 -20(가장 높은 우선순위)부터 +19(가장 낮은 우선순위)까지이며, 기본값은 0이다. CFS는 이 nice 값을 정수 가중치로 변환하여 vruntime 계산에 사용한다.

변환은 sched_prio_to_weight[] 룩업 테이블을 통해 이루어진다. 이 테이블은 nice 값 한 단계 차이가 약 10%의 CPU 시간 차이를 만들도록 설계되어 있다. 수학적으로는 다음과 같은 근사 관계를 따른다.

$\text{weight} \approx \frac{1024}{1.25^{\text{nice}}}$

대표적인 값들을 살펴보면 다음과 같다.

nice 0인 태스크와 nice 5인 태스크가 공존하면, nice 0 태스크는 약 3배의 CPU 시간을 받는다($1.25^5 \approx 3.05$). 이 지수적 스케일링 덕분에 nice 값의 차이가 어느 수준이든 일관된 비율 차이를 만든다.⁴

레드-블랙 트리

CFS의 런큐runqueue⁵는 레드-블랙 트리⁶로 구현된다. 모든 실행 가능한 태스크는 vruntime을 키로 하여 이 트리에 삽입되고, 트리의 왼쪽으로 갈수록 vruntime이 작은 태스크가 위치한다.

스케줄러가 다음에 실행할 태스크를 선택할 때(pick_next_entity()), 트리에서 가장 왼쪽 노드를 꺼내면 된다. CFS는 이 가장 왼쪽 노드를 cfs_rq->rb_leftmost에 캐싱해 두므로, 태스크 선택의 시간 복잡도는 $O(1)$이다. 태스크의 삽입과 삭제는 레드-블랙 트리의 특성상 $O(\log n)$에 이루어진다.

이 설계의 장점은 명확하다. $O(1)$ 스케줄러가 이름 그대로 상수 시간에 동작했지만 복잡한 배열 기반 구조와 휴리스틱이 필요했던 반면, CFS는 단순한 정렬 트리 하나로 공정성을 보장한다. 태스크 수가 수천 개에 이르더라도 $O(\log n)$의 삽입/삭제 비용은 충분히 실용적이며, 태스크 선택은 캐싱 덕분에 $O(1)$이다.

커널 자료구조

CFS의 핵심 자료구조는 struct sched_entity와 struct cfs_rq다. sched_entity는 스케줄링의 단위를 나타내며, 각 태스크의 task_struct에 se 필드로 내장되어 있다. 주요 필드를 살펴보면, vruntime은 가상 실행 시간, load.weight는 nice 값에서 변환된 가중치, run_node는 레드-블랙 트리에서의 노드 연결, sum_exec_runtime은 누적 물리 실행 시간이다.

cfs_rq는 CPU별로⁷ 하나씩 존재하는 CFS 런큐다. tasks_timeline이 레드-블랙 트리의 루트이고, rb_leftmost가 캐싱된 최소 vruntime 노드, min_vruntime이 런큐의 단조 증가 최솟값, nr_running이 실행 가능한 태스크 수를 나타낸다.

struct sched_entity {
    struct load_weight      load;           /* nice → 가중치 */
    struct rb_node          run_node;       /* RB 트리 노드 */
    u64                     vruntime;       /* 가상 실행 시간 */
    u64                     sum_exec_runtime; /* 누적 물리 실행 시간 */
    u64                     exec_start;     /* 현재 실행 시작 시각 */
    /* ... */
};

min_vruntime의 역할

cfs_rq->min_vruntime은 런큐 내 모든 태스크의 vruntime 중 최솟값을 추적하는 단조 증가monotonically increasing 변수다. 이 값은 절대로 감소하지 않으며, 런큐의 "시간 기준점" 역할을 한다.

min_vruntime이 필요한 이유는 태스크의 수면sleep과 기상wake-up에 있다. 태스크가 I/O 대기 등으로 오랫동안 수면하면 그동안 런큐의 다른 태스크들의 vruntime은 계속 증가한다. 이 태스크가 기상할 때, 수면 전의 오래된 vruntime을 그대로 사용하면 어떤 일이 벌어질까? 런큐의 다른 태스크들보다 vruntime이 월등히 작으므로, 이 태스크는 뒤처진 vruntime을 따라잡을 때까지 CPU를 독점하게 된다. 이는 다른 태스크들의 기아starvation⁸를 유발한다.

CFS는 태스크가 런큐에 진입할 때(기상 또는 fork) vruntime을 다음과 같이 보정한다.

$\text{vruntime}_{\text{new}} = \max(\text{vruntime}_{\text{old}},\ \text{min\_vruntime})$

이렇게 하면 오래 잠든 태스크도 현재 런큐의 기준점에서 출발하므로 CPU를 독점하지 않으면서도, 짧게 잠들었다 돌아온 태스크는 원래의 vruntime을 유지하여 약간의 보상을 받을 수 있다.⁹

스케줄링 주기와 타임 슬라이스

CFS는 전통적인 의미의 고정 타임 슬라이스¹⁰를 사용하지 않는다. 대신 스케줄링 주기scheduling period라는 개념을 도입한다. 스케줄링 주기는 런큐에 있는 모든 태스크가 최소 한 번씩 실행될 수 있는 시간 구간으로, sched_latency_ns 파라미터로 설정된다(기본값 약 48ms).

각 태스크가 한 스케줄링 주기 내에서 받는 CPU 시간은 가중치에 비례한다.

$\text{time\_slice}_i = \text{period} \times \frac{\text{weight}_i}{\sum_{j} \text{weight}_j}$

태스크 수가 많아져서 각 태스크의 몫이 sched_min_granularity_ns(기본값 약 4ms) 미만이 되면, 스케줄링 주기가 자동으로 늘어난다. 이는 잦은 [컨텍스트 스위치](Context Switch.md)로 인한 오버헤드를 방지하면서도 모든 태스크에 최소한의 실행 시간을 보장한다.

CFS에서 EEVDF로

CFS는 15년간 리눅스의 기본 스케줄러로 활약했지만, 근본적인 한계도 있었다. 짧은 요청을 가진 태스크(대화형 워크로드)의 꼬리 지연tail latency이 높은 부하 상황에서 급격히 증가할 수 있었고, 선점 결정이 sched_latency_ns, sched_min_granularity_ns, sched_wakeup_granularity_ns 같은 경험적 파라미터에 의존했다. 또한 태스크가 받아야 할 서비스와 실제로 받은 서비스의 차이를 형식적으로 추적하지 않아, 특정 워크로드 조합에서 미묘한 불공정이 발생할 수 있었다.

2023년, Peter Zijlstra는 CFS의 핵심 알고리즘을 Earliest Eligible Virtual Deadline First(Earliest Eligible Virtual Deadline First)로 교체했다. EEVDF는 1995년 Ion Stoica와 Hussein Abdel-Wahab이 제안한 비례 공유 스케줄링 알고리즘으로, Linux v6.6에서 기본 스케줄러로 채택되었다. EEVDF는 적격성eligibility과 가상 데드라인virtual deadline이라는 두 가지 개념을 도입하여, CFS의 vruntime 기반 선택을 데드라인 기반 선택으로 대체한다. 자세한 내용은 Earliest Eligible Virtual Deadline First 포스트에서 다룬다.

---

출처

• Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) Operating System Concepts. 10th ed. Hoboken, NJ: Wiley.
• Arpaci-Dusseau, R. H. and Arpaci-Dusseau, A. C. (2023) Operating Systems: Three Easy Pieces. 1.10 ed. Arpaci-Dusseau Books.
• Bovet, D. P. and Cesati, M. (2008) Understanding the Linux Kernel. 3rd ed. Sebastopol, CA: O'Reilly.
• Love, R. (2010) Linux Kernel Development. 3rd ed. Upper Saddle River, NJ: Addison-Wesley.
• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th ed. Cambridge, MA: MIT Press.
• Stoica, I. and Abdel-Wahab, H. (1995) 'Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation', Technical Report TR-95-22, Old Dominion University.
• Molnár, I. (2007) '[PATCH] Modular Scheduler Core and Completely Fair Scheduler [CFS]', Linux Kernel Mailing List.
• Linux kernel source v6.19 — kernel/sched/fair.c, kernel/sched/sched.h.
• Linux kernel documentation — Documentation/scheduler/sched-design-CFS.rst, Documentation/scheduler/sched-eevdf.rst.

Footnotes

1. O(1) 스케줄러는 Linux 2.6.0부터 2.6.22까지 사용된 스케줄러로, 태스크 수에 관계없이 상수 시간에 스케줄링 결정을 내린다. 활성active 배열과 만료expired 배열 두 개를 사용하여 우선순위별로 태스크를 관리했다. — Love, R. (2010) Linux Kernel Development, 3rd ed., Chapter 4. ↩

2. 휴리스틱heuristic은 최적해를 보장하지는 않지만 실용적으로 충분히 좋은 결과를 빠르게 얻기 위한 경험적 규칙이다. O(1) 스케줄러는 태스크의 수면 시간 비율 등을 기반으로 대화형 여부를 판단하는 휴리스틱을 사용했다. ↩

3. 가중치는 태스크의 상대적 CPU 점유 비율을 결정하는 정수 값으로, nice 값에서 변환된다. 자세한 내용은 "nice 값과 가중치" 절에서 다룬다. ↩

4. 이 설계는 Con Kolivas의 관찰에서 비롯되었다. nice 값의 절대 위치가 아니라 상대 차이가 일정한 CPU 비율 차이를 만들어야 직관적이다. nice 0과 1의 차이가 nice 18과 19의 차이와 동일한 ~10%의 CPU 비율 변화를 가져온다. — Molnár, I. (2007) '[PATCH] Modular Scheduler Core and Completely Fair Scheduler', LKML. ↩

5. 런큐runqueue는 특정 CPU에서 실행 대기 중인 태스크들을 관리하는 per-CPU 자료구조다. 리눅스에서는 struct rq로 구현되며, 스케줄링 클래스별 서브큐(cfs_rq, rt_rq 등)를 포함한다. — kernel/sched/sched.h. ↩

6. 레드-블랙 트리는 자가 균형 이진 탐색 트리의 일종으로, 삽입·삭제·탐색 모두 $O(\log n)$을 보장한다. 각 노드가 빨간색 또는 검은색으로 칠해지며, 루트에서 리프까지의 검은 노드 수가 모든 경로에서 동일하다는 성질로 균형을 유지한다. — Cormen, T. H. et al. (2022) Introduction to Algorithms, 4th ed., Chapter 13. ↩

7. per-CPU 자료구조는 각 CPU 코어마다 독립된 복사본을 두는 데이터로, 잠금 없이 접근할 수 있어 성능이 좋다. — include/linux/percpu.h. ↩

8. 기아starvation란 특정 태스크가 자원(여기서는 CPU 시간)을 무기한으로 받지 못하는 상태를 말한다. — Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) Operating System Concepts, 10th ed., §7.1. ↩

9. 실제 구현에서는 기상 시 vruntime에서 약간의 보정을 빼주어(sched_latency_ns의 절반 정도), 짧게 수면한 대화형 태스크가 기상 직후 빠르게 스케줄링될 수 있도록 한다. — kernel/sched/fair.c, place_entity(). ↩

10. 타임 슬라이스time slice(또는 타임 퀀텀)은 스케줄러가 하나의 태스크에 연속으로 허용하는 최대 CPU 사용 시간이다. — Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) Operating System Concepts, 10th ed., §5.3.4. ↩