--- title: Linux CFS Scheduler 완전 정리 (Kernel 6.x 기준) date: 2026-06-29 type: note domain: kernel tags: [kernel, scheduler, cfs, eevdf] --- > 작성일: 2026-02-21 > 커널 버전: 6.17.0-14-generic (Ubuntu 24.04.4 LTS) > 목적: CFS 동작 원리, 한계, EEVDF 전환 배경까지 이해 --- ## 목차 1. [타임라인](#1-타임라인) 2. [CFS 핵심 철학](#2-cfs-핵심-철학) 3. [vruntime (Virtual Runtime)](#3-vruntime-virtual-runtime) 4. [Red-Black Tree 기반 스케줄링](#4-red-black-tree-기반-스케줄링) 5. [주요 Tunable 파라미터 (6.0~6.5)](#5-주요-tunable-파라미터-605) 6. [커널 소스 내부 구조](#6-커널-소스-내부-구조) 7. [Preemption 모델](#7-preemption-모델) 8. [CFS의 한계 1: Sleeper Fairness 문제](#8-cfs의-한계-1-sleeper-fairness-문제) 9. [CFS의 한계 2: Latency 제어 한계](#9-cfs의-한계-2-latency-제어-한계) 10. [EEVDF로의 전환](#10-eevdf로의-전환) 11. [현재 커널(6.17) 실측값](#11-현재-커널617-실측값) --- ## 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 정의 ``` ### 주요 자료구조 ```c 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`