> [!abstract] Introduction > 여러 태스크가 하나의 CPU를 공유해야 할 때, "공정하다"는 것은 무엇을 의미할까요? CFS(Completely Fair Scheduler)는 이 질문에 대한 리눅스 커널의 대답입니다. 이상적인 멀티태스킹 CPU를 수학적으로 모델링하고, 가상 실행 시간*virtual runtime*이라는 개념으로 각 태스크의 CPU 점유율을 추적하며, 레드-블랙 트리로 다음에 실행할 태스크를 효율적으로 선택합니다. 이 글에서는 CFS의 설계 철학과 핵심 메커니즘을 살펴보고, Linux v6.6에서 CFS를 대체한 EEVDF 알고리즘까지 다룹니다. ## 왜 "완전히 공정한" 스케줄러인가 [스케줄러](Scheduler.md)의 근본적인 과제는 한정된 CPU 시간을 여러 태스크에 배분하는 것이다. 이전 세대의 리눅스 스케줄러인 O(1) 스케줄러[^o1]는 복잡한 휴리스틱[^heuristic]으로 태스크의 우선순위를 동적으로 조정했지만, 그 복잡성 때문에 특정 워크로드에서 예측하기 어려운 동작을 보였고, 대화형*interactive* 태스크와 배치*batch* 태스크를 구분하는 휴리스틱이 종종 오판을 일으켰다. 2007년, Ingo Molnár는 이 복잡한 휴리스틱을 모두 걷어내고 근본적으로 다른 접근법을 제안했다. CFS의 설계 철학은 단순하면서도 강력하다 — **이상적인 멀티태스킹 CPU를 실제 하드웨어 위에서 모델링한다.** 이상적인 CPU란, $n$개의 태스크가 실행 중이면 각 태스크가 정확히 $\frac{1}{n}$의 CPU 시간을 동시에 받는 가상의 프로세서다. 현실의 CPU는 한 번에 하나의 태스크만 실행할 수 있으므로 이 이상을 그대로 실현할 수는 없지만, CFS는 각 태스크가 이상적인 CPU에서 받았을 시간과 실제로 받은 시간의 차이를 최소화하는 방향으로 스케줄링 결정을 내린다. 이 접근법의 핵심은 공정성*fairness*의 정의를 수학적으로 명확히 한 것이다. 공정하다는 것은 모든 태스크가 자신의 가중치[^weight-intro]에 비례하는 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` | 가중치 | CPU 비율 (상대적) | |--------|--------|------------------| | -20 | 88761 | ~86.7× | | -10 | 9548 | ~9.3× | | 0 | 1024 | 1× (기준) | | 10 | 110 | ~0.11× | | 19 | 15 | ~0.015× | `nice` 0인 태스크와 `nice` 5인 태스크가 공존하면, `nice` 0 태스크는 약 3배의 CPU 시간을 받는다($1.25^5 \approx 3.05$). 이 지수적 스케일링 덕분에 `nice` 값의 차이가 어느 수준이든 일관된 비율 차이를 만든다.[^nice-ratio] ## 레드-블랙 트리 CFS의 런큐*runqueue*[^runqueue]는 레드-블랙 트리[^rbtree]로 구현된다. 모든 실행 가능한 태스크는 `vruntime`을 키로 하여 이 트리에 삽입되고, 트리의 왼쪽으로 갈수록 `vruntime`이 작은 태스크가 위치한다. ![[cfsRbTree.svg]] [스케줄러](Scheduler.md)가 다음에 실행할 태스크를 선택할 때(`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별로[^per-cpu] 하나씩 존재하는 CFS 런큐다. `tasks_timeline`이 레드-블랙 트리의 루트이고, `rb_leftmost`가 캐싱된 최소 `vruntime` 노드, `min_vruntime`이 런큐의 단조 증가 최솟값, `nr_running`이 실행 가능한 태스크 수를 나타낸다. ```c 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*[^starvation]를 유발한다. CFS는 태스크가 런큐에 진입할 때(기상 또는 `fork`) `vruntime`을 다음과 같이 보정한다. $\text{vruntime}_{\text{new}} = \max(\text{vruntime}_{\text{old}},\ \text{min\_vruntime})$ 이렇게 하면 오래 잠든 태스크도 현재 런큐의 기준점에서 출발하므로 CPU를 독점하지 않으면서도, 짧게 잠들었다 돌아온 태스크는 원래의 `vruntime`을 유지하여 약간의 보상을 받을 수 있다.[^sleep-bonus] ## 스케줄링 주기와 타임 슬라이스 CFS는 전통적인 의미의 고정 타임 슬라이스[^timeslice]를 사용하지 않는다. 대신 **스케줄링 주기*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)로 인한 오버헤드를 방지하면서도 모든 태스크에 최소한의 실행 시간을 보장한다. ![[cfsVruntimeFlow.svg]] ## 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%20Eligible%20Virtual%20Deadline%20First.md)(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](Earliest%20Eligible%20Virtual%20Deadline%20First.md) 포스트에서 다룬다. --- [^o1]: O(1) 스케줄러는 Linux 2.6.0부터 2.6.22까지 사용된 스케줄러로, 태스크 수에 관계없이 상수 시간에 스케줄링 결정을 내린다. 활성*active* 배열과 만료*expired* 배열 두 개를 사용하여 우선순위별로 태스크를 관리했다. — Love, R. (2010) *Linux Kernel Development*, 3rd ed., Chapter 4. [^heuristic]: 휴리스틱*heuristic*은 최적해를 보장하지는 않지만 실용적으로 충분히 좋은 결과를 빠르게 얻기 위한 경험적 규칙이다. O(1) 스케줄러는 태스크의 수면 시간 비율 등을 기반으로 대화형 여부를 판단하는 휴리스틱을 사용했다. [^weight-intro]: 가중치는 태스크의 상대적 CPU 점유 비율을 결정하는 정수 값으로, `nice` 값에서 변환된다. 자세한 내용은 "nice 값과 가중치" 절에서 다룬다. [^nice-ratio]: 이 설계는 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. [^runqueue]: 런큐*runqueue*는 특정 CPU에서 실행 대기 중인 태스크들을 관리하는 per-CPU 자료구조다. 리눅스에서는 `struct rq`로 구현되며, 스케줄링 클래스별 서브큐(`cfs_rq`, `rt_rq` 등)를 포함한다. — `kernel/sched/sched.h`. [^rbtree]: 레드-블랙 트리는 자가 균형 이진 탐색 [트리](Tree.md)의 일종으로, 삽입·삭제·탐색 모두 $O(\log n)$을 보장한다. 각 노드가 빨간색 또는 검은색으로 칠해지며, 루트에서 리프까지의 검은 노드 수가 모든 경로에서 동일하다는 성질로 균형을 유지한다. — Cormen, T. H. et al. (2022) *Introduction to Algorithms*, 4th ed., Chapter 13. [^per-cpu]: per-CPU 자료구조는 각 CPU 코어마다 독립된 복사본을 두는 데이터로, 잠금 없이 접근할 수 있어 성능이 좋다. — `include/linux/percpu.h`. [^starvation]: 기아*starvation*란 특정 태스크가 자원(여기서는 CPU 시간)을 무기한으로 받지 못하는 상태를 말한다. — Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) *Operating System Concepts*, 10th ed., §7.1. [^sleep-bonus]: 실제 구현에서는 기상 시 `vruntime`에서 약간의 보정을 빼주어(`sched_latency_ns`의 절반 정도), 짧게 수면한 대화형 태스크가 기상 직후 빠르게 스케줄링될 수 있도록 한다. — `kernel/sched/fair.c`, `place_entity()`. [^timeslice]: 타임 슬라이스*time slice*(또는 타임 퀀텀)은 [스케줄러](Scheduler.md)가 하나의 태스크에 연속으로 허용하는 최대 CPU 사용 시간이다. — Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) *Operating System Concepts*, 10th ed., §5.3.4. ## 출처 - 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`.