Linux CFS Scheduler 완전 정리 (Kernel 6.x 기준)
작성일: 2026-02-21 커널 버전: 6.17.0-14-generic (Ubuntu 24.04.4 LTS) 목적: CFS 동작 원리, 한계, EEVDF 전환 배경까지 이해
목차
- 타임라인
- CFS 핵심 철학
- vruntime (Virtual Runtime)
- Red-Black Tree 기반 스케줄링
- 주요 Tunable 파라미터 (6.0~6.5)
- 커널 소스 내부 구조
- Preemption 모델
- CFS의 한계 1: Sleeper Fairness 문제
- CFS의 한계 2: Latency 제어 한계
- EEVDF로의 전환
- 현재 커널(6.17) 실측값
1. 타임라인
Kernel 2.6.23 (2007) ─── CFS 도입 (Con Kolivas의 아이디어 → Ingo Molnár 구현)
│
Kernel 2.6 ~ 5.x ─── CFS가 기본 스케줄러로 약 16년간 사용
│
Kernel 6.6 (2023.10) ─── EEVDF로 교체, CFS tunable 제거
│
Kernel 6.17 (현재) ─── 현재 커널, EEVDF 기반
2. CFS 핵심 철학
“이상적인 멀티태스킹 CPU"를 소프트웨어로 근사
이상적인 CPU가 있다면 N개 태스크에 각각 1/N의 CPU 시간을 동시에 줄 수 있다.
현실에서는 불가능하므로, CFS는 누가 가장 적게 실행됐는지 추적해서 그 태스크를 다음에 실행한다.
3. vruntime (Virtual Runtime)
계산 공식
vruntime += delta_exec × (NICE_0_WEIGHT / task_weight)
| 요소 | 의미 |
|---|---|
delta_exec |
실제로 CPU를 사용한 물리적 시간 (ns) |
NICE_0_WEIGHT |
nice 0의 가중치 = 1024 |
task_weight |
해당 태스크의 nice에 따른 가중치 |
동작 원리
- nice가 낮을수록(우선순위 높음) → weight 큼 → vruntime이 느리게 증가 → 더 오래 실행됨
- nice가 높을수록(우선순위 낮음) → weight 작음 → vruntime이 빠르게 증가 → 빨리 양보
계산 예시
Task A (nice 0, weight 1024): 1ms 실행 → vruntime += 1ms
Task B (nice 5, weight 335): 1ms 실행 → vruntime += 3.05ms
Task C (nice -5, weight 3121): 1ms 실행 → vruntime += 0.33ms
→ Task C는 같은 시간을 써도 vruntime이 천천히 오르므로 CPU를 더 많이 받음
4. Red-Black Tree 기반 스케줄링
[vruntime 기준 정렬된 RB-Tree]
(50ms)
/ \
(30ms) (80ms)
/ \ \
(10ms) (40ms) (100ms)
↑
leftmost
= 다음 실행 대상
- 모든 runnable 태스크를 vruntime 오름차순으로 RB-Tree에 삽입
- 스케줄러는 항상 leftmost 노드(가장 작은 vruntime)를
O(1)로 pick - 삽입/삭제는
O(log N)
5. 주요 Tunable 파라미터 (6.0~6.5)
주의: 커널 6.6 이후(EEVDF)에서는 이 파라미터들이 제거되었다.
/proc/sys/kernel/sched_latency_ns = 6000000 (6ms)
/proc/sys/kernel/sched_min_granularity_ns = 750000 (0.75ms)
/proc/sys/kernel/sched_wakeup_granularity_ns = 1000000 (1ms)
/proc/sys/kernel/sched_nr_migrate = 32
| 파라미터 | 의미 |
|---|---|
sched_latency_ns |
스케줄링 주기. 이 시간 안에 모든 runnable 태스크가 최소 1번 실행됨 |
sched_min_granularity_ns |
태스크당 최소 실행 시간. 이보다 짧게 preempt하지 않음 |
sched_wakeup_granularity_ns |
wakeup preemption 임계값. 깨어난 태스크의 vruntime이 현재 태스크보다 이만큼 작아야 preempt |
sched_nr_migrate |
로드 밸런싱 시 한 번에 옮기는 최대 태스크 수 |
타임슬라이스 계산
태스크 수가 적을 때 (N ≤ sched_latency / sched_min_granularity = 8):
timeslice = sched_latency × (task_weight / total_weight)
태스크 수가 많을 때 (N > 8):
timeslice = sched_min_granularity × (task_weight / total_weight)
(실제 주기 = sched_min_granularity × N 으로 확장)
예: nice 0인 태스크 4개, sched_latency = 6ms
각 태스크 timeslice = 6ms × (1024/4096) = 1.5ms
→ 6ms 주기 안에 4개가 1.5ms씩 실행
예: nice 0인 태스크 12개 (> 8)
각 태스크 timeslice = 0.75ms (min_granularity)
→ 실제 주기 = 0.75ms × 12 = 9ms로 확장
6. 커널 소스 내부 구조
핵심 파일
kernel/sched/fair.c ← CFS 메인 로직
kernel/sched/core.c ← 스케줄러 코어
include/linux/sched.h ← task_struct 정의
주요 자료구조
struct sched_entity {
struct rb_node run_node; // RB-Tree 노드
u64 vruntime; // 가상 런타임
u64 sum_exec_runtime; // 누적 실행 시간
struct load_weight load; // nice 기반 가중치
...
};
struct cfs_rq {
struct rb_root_cached tasks_timeline; // RB-Tree (cached = leftmost 포인터)
u64 min_vruntime; // 현재 큐의 최소 vruntime
struct sched_entity *curr; // 현재 실행 중인 엔티티
unsigned int nr_running; // runnable 태스크 수
...
};
핵심 함수 흐름
schedule()
→ __schedule()
→ pick_next_task_fair() // CFS에서 다음 태스크 선택
→ pick_next_entity()
→ __pick_first_entity() // RB-Tree leftmost 반환
→ context_switch() // 실제 컨텍스트 스위칭
7. Preemption 모델
CONFIG_PREEMPT_NONE → 서버용, 커널 내부에서 preempt 안 함
CONFIG_PREEMPT_VOLUNTARY → 데스크탑 기본, 명시적 preemption point에서만
CONFIG_PREEMPT → 저지연, 거의 모든 커널 코드에서 preempt 가능
CONFIG_PREEMPT_RT → 실시간, 스핀락도 preemptible
CFS 자체는 유저스페이스 스케줄링 정책이고, preemption 모델은 커널 코드 내부에서 얼마나 자주 스케줄러에게 제어권을 넘기느냐를 결정한다.
8. CFS의 한계 1: Sleeper Fairness 문제
문제 정의
태스크가 sleep(I/O 대기, timer 등)하면 RB-Tree에서 빠진다. 깨어났을 때 vruntime을 어떻게 설정하느냐가 sleeper fairness 문제의 핵심이다.
vruntime 보정 메커니즘
깨어난 태스크의 vruntime 보정:
vruntime = max(자기 vruntime, cfs_rq->min_vruntime - sched_latency_ns)
이 보정의 의도는 “오래 잠든 태스크가 깨어났을 때 지나치게 낮은 vruntime을 갖지 않도록” 하는 것이다. 하지만 이 보정이 여러 문제를 만든다.
시나리오 1: 짧은 sleep을 반복하는 태스크의 CPU 독점
[Timeline]
Task A: ████ sleep ████ sleep ████ sleep ████ (1ms 실행, 1ms sleep 반복)
Task B: ████████████████████████████████████ (CPU-bound, 쉬지 않고 실행)
Task A의 vruntime: sleep할 때마다 "정지" → 깨어나면 항상 상대적으로 낮음
Task B의 vruntime: 계속 증가
결과:
Task A가 깨어날 때마다 vruntime이 Task B보다 낮으므로 즉시 preempt
→ Task A가 실제로는 50% 시간만 쓰면서 "공정한 50%보다 더 빠른 응답"을 받음
→ Task B는 공정 몫보다 적은 CPU를 받게 됨
시나리오 2: 의도적 sleep 악용 (Gaming)
악의적 태스크 전략:
1. 아주 짧은 시간(수 μs)만 sleep
2. 깨어나면 vruntime이 낮으므로 즉시 스케줄됨
3. 반복 → 사실상 CPU-bound이면서도 vruntime 이득을 계속 챙김
결과: nice 값을 조작하지 않고도 불공정한 CPU 점유 가능
시나리오 3: 많은 I/O 태스크가 동시에 깨어날 때 (Thundering Herd)
100개 태스크가 동시에 I/O 완료로 깨어남
→ 전부 min_vruntime 근처의 낮은 vruntime을 가짐
→ 현재 실행 중인 CPU-bound 태스크를 계속 preempt
→ 대량의 불필요한 context switch 발생
→ 전체 throughput 저하
근본 원인
CFS의 vruntime은 CPU를 얼마나 받았느냐만 추적한다.
“얼마나 오래 기다렸느냐"는 vruntime 보정으로 간접적/경험적으로만 반영할 수 있고,
이 보정의 정도(sched_latency_ns 기반)가 모든 워크로드에 적절할 수 없다.
9. CFS의 한계 2: Latency 제어 한계
문제 정의
CFS에서 nice 값은 **CPU 비율(bandwidth)**만 조절한다. **응답 지연시간(latency)**을 독립적으로 제어할 방법이 없다.
nice 값이 제어하는 것과 제어하지 못하는 것
nice 값이 제어하는 것:
- CPU 시간 비율 (weight 기반)
- 예: nice -10 → 전체 CPU의 더 큰 비율
nice 값이 제어하지 못하는 것:
- 깨어난 후 실제로 CPU를 받기까지의 지연시간
- 스케줄링 주기 내에서 얼마나 빨리 첫 실행을 받는지
현실 문제: 같은 nice에서 다른 latency 요구사항
시나리오: 서버에서 두 종류의 태스크가 돌고 있다
Task A: 오디오 재생 데몬
- CPU 사용량: 매우 적음 (1~2%)
- latency 요구: 매우 엄격 (10ms 이내에 반드시 스케줄)
- nice: 0
Task B: 로그 집계 배치
- CPU 사용량: 많음 (80%)
- latency 요구: 느슨 (수백 ms 지연 OK)
- nice: 0
CFS에서는 둘 다 nice 0이므로:
- 같은 weight, 같은 vruntime 증가 속도
- Task A가 sleep에서 깨어났을 때 Task B보다 먼저 실행될 보장 없음
- sched_wakeup_granularity_ns 조건을 만족해야만 preempt 가능
nice를 조절하면 되지 않나?
Task A를 nice -10으로 설정하면?
→ latency는 개선됨 (vruntime이 느리게 증가하므로)
→ 하지만 CPU 비율도 같이 올라감 (1~2%만 필요한데 큰 비율을 배정받음)
→ 다른 중요한 태스크의 CPU를 불필요하게 뺏음
핵심 문제: nice는 "CPU 비율"과 "응답 지연"을 하나의 축으로 묶어버림
→ 둘을 독립적으로 조절할 수 없음
구체적 지연 발생 구조
sched_latency_ns = 6ms, 태스크 8개 (전부 nice 0)
각 태스크 timeslice = 6ms / 8 = 0.75ms
최악의 경우 대기 시간:
태스크가 깨어났을 때 → 다른 7개가 각 0.75ms씩 실행 → 최대 5.25ms 대기
태스크가 20개로 늘어나면:
실제 주기 = 0.75ms × 20 = 15ms
최악 대기 = 14.25ms
→ 태스크 수에 비례해 지연이 선형 증가
→ 특정 태스크만 "낮은 지연"을 보장할 방법 없음
CFS에서 시도했던 우회 방법들
| 방법 | 효과 | 한계 |
|---|---|---|
sched_wakeup_granularity_ns 축소 |
wakeup 시 preempt 확률 증가 | 모든 태스크에 적용됨, 불필요한 context switch 증가 |
sched_latency_ns 축소 |
스케줄링 주기 단축 | 모든 태스크의 timeslice 축소, throughput 저하 |
| nice 값 조정 | CPU 비율+지연 동시 변경 | 비율과 지연 분리 불가 |
| SCHED_FIFO/RR 사용 | 지연 보장 가능 | RT 클래스로 완전히 빠지므로 CFS 공정성 포기, priority inversion 위험 |
latency_nice: 해결을 위한 제안
기존:
nice: -20 ────────── 0 ────────── +19
CPU 비율 높음 CPU 비율 낮음
(지연도 낮음) (지연도 높음) ← 분리 불가
EEVDF + latency_nice 제안:
nice: CPU 비율만 제어
latency_nice: 응답 지연만 제어 (-20 ~ +19)
예: { nice: 10, latency_nice: -10 }
→ CPU 비율은 적게, 하지만 깨어나면 빠르게 응답
→ 오디오 데몬 같은 워크로드에 이상적
이 latency_nice 개념은 CFS 구조에서는 구현이 어려웠으나,
EEVDF의 virtual deadline 메커니즘으로 자연스럽게 구현 가능해졌다.
10. EEVDF로의 전환
CFS → EEVDF 전환 요약
| CFS의 문제점 | EEVDF의 해결 |
|---|---|
| Sleeper fairness 문제 | Deadline 기반으로 엄밀한 fairness 보장 |
| Latency-nice 미지원 | latency_nice 힌트로 지연시간 우선순위 분리 가능 |
| Tunable 난잡 | Tunable 대부분 제거, 알고리즘 자체가 공정성 보장 |
| Heuristic 의존 | Eligible time + virtual deadline으로 수학적 판단 |
EEVDF 핵심 개념
CFS: "vruntime이 가장 작은 놈을 실행"
EEVDF: "eligible한 놈 중에서 virtual deadline이 가장 빠른 놈을 실행"
EEVDF 핵심 두 값:
eligible time = 이 태스크가 실행 자격을 얻는 시점
virtual deadline = eligible time + (request_length / weight)
→ 자격이 있으면서(eligible) 마감이 가장 급한(earliest deadline) 태스크를 선택
→ sleep에서 깨어난 태스크도 동일한 수학적 기준으로 판단
→ vruntime 보정 같은 heuristic 불필요
Sleeper Fairness가 EEVDF에서 해결되는 이유
CFS:
sleep 복귀 → vruntime 보정 (heuristic) → 보정 정도에 따라 공정/불공정
EEVDF:
sleep 복귀 → eligible time 재계산 → virtual deadline 부여
→ "자격이 되는 시점"과 "마감"이 수학적으로 결정됨
→ sleep 시간과 무관하게, 공정한 몫만큼의 deadline을 받음
→ gaming 불가: 짧은 sleep을 반복해도 deadline은 공정하게 계산됨
Latency 제어가 EEVDF에서 해결되는 이유
EEVDF에서 latency_nice는 request_length(timeslice 크기)에 영향:
latency_nice 낮음 → 짧은 timeslice 요청 → 짧은 deadline → 빨리 스케줄됨
latency_nice 높음 → 긴 timeslice 요청 → 긴 deadline → 나중에 스케줄됨
핵심: timeslice가 짧으면 자주 스케줄되지만 매번 적게 실행
→ CPU 비율(nice)과 응답 지연(latency_nice)이 독립적으로 제어 가능
11. 현재 커널(6.17) 실측값
존재하지 않는 파라미터 (CFS 전용, 제거됨)
sched_latency_ns ← 없음
sched_min_granularity_ns ← 없음
sched_wakeup_granularity_ns ← 없음
실제 존재하는 스케줄러 파라미터
/proc/sys/kernel/sched_cfs_bandwidth_slice_us = 5000 (5ms, cgroup bandwidth 용)
/proc/sys/kernel/sched_rr_timeslice_ms = 100 (100ms, SCHED_RR 전용)
/proc/sys/kernel/sched_rt_period_us (RT 스케줄러 주기)
/proc/sys/kernel/sched_rt_runtime_us (RT 스케줄러 런타임)
/proc/sys/kernel/sched_autogroup_enabled (autogroup on/off)
/proc/sys/kernel/sched_schedstats (스케줄러 통계 on/off)
커널 빌드 설정
CONFIG_HZ=1000 (1ms tick, 기존 예상 250이 아님)
CONFIG_SCHED_CLASS_EXT=y (sched_ext 지원 — BPF 기반 커스텀 스케줄러)
CONFIG_CFS_BANDWIDTH=y (cgroup CPU bandwidth 제한 기능)
참고
- CFS 원작자: Ingo Molnár (2007, kernel 2.6.23)
- EEVDF 논문: Stoica & Abdel-Wahab, 1995
- EEVDF 커널 통합: Peter Zijlstra (2023, kernel 6.6)
- 커널 소스:
kernel/sched/fair.c,kernel/sched/core.c