완전 공정 스케줄러 (CFS, Completely Fair Scheduler)

핵심 인사이트 (3줄 요약)

본질: 리눅스의 CFS(Completely Fair Scheduler)는 전통적인 우선순위 큐와 타임 슬라이스(Time Quantum) 개념을 폐기하고, 오직 '가상 실행 시간(vruntime, Virtual Runtime)'이라는 단일 지표를 레드-블랙 트리(Red-Black Tree)에 정렬하여 가장 적게 실행된 프로세스에게 무조건 CPU를 내어주는 혁명적인 스케줄러다.

가치: 스케줄러가 "이 놈이 대화형(I/O)인가?"를 추측하는 더러운 휴리스틱(Heuristics) 코드를 전부 삭제하고, 적게 일하고 대기한 프로세스는 자연스럽게 vruntime이 낮아져 즉각적인 응답성(Response Time)을 획득하는 **'수학적으로 완벽한 공정성(Fairness)'**을 증명해 냈다.

융합: 보장 스케줄링(Guaranteed)의 철학과 다중 큐(MQA), 컨테이너 자원 격리(cgroups)를 O(log N)의 가벼운 트리 탐색 구조 위에서 하나로 융합해 낸, 2007년 이후 현재까지 전 세계 클라우드와 안드로이드를 지배하고 있는 현대 운영체제의 마스터피스다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: 잉고 몰나르(Ingo Molnar)가 리눅스 2.6.23 버전에 도입한 디폴트 스케줄러다. 완벽한 다중 처리기(Ideal Multi-tasking CPU)를 모델링하여, $N$개의 프로세스가 동시에 실행된다면 각 프로세스가 정확히 $\frac{1}{N}$의 속도로 CPU를 나눠 쓰고 있다는 환상을 심어주는 알고리즘이다.
필요성: 이전의 O(1) 스케줄러는 속도는 빨랐지만, 프로세스가 착한지 나쁜지(I/O 바운드인지 CPU 바운드인지) 찍어 맞추는 경험적 편법(Heuristics)에 찌들어 동영상 재생이나 3D 게임 환경에서 끔찍한 렉(Jitter)을 뿜어냈다. 인간의 얄팍한 추측을 버리고, 누가 얼마나 굶었는지 **과거의 팩트(실제 사용 시간)**만을 절대 기준으로 삼는 투명하고 우아한 시스템이 절실했다.
💡 비유: 복잡한 우선순위나 VIP 회원 등급을 다 없애버리고, 오직 **'태어나서 지금까지 식당에서 밥 먹은 누적 시간(vruntime)'**이 가장 적은 불쌍한 사람을 무조건 줄 맨 앞으로 세워 밥을 먹여주는 **'완벽한 평등주의 복지 식당'**과 같다.
등장 배경: 콘 콜리바스(Con Kolivas)가 만든 데스크톱 환경의 부드러움을 극대화한 RSDL 스케줄러에서 영감을 받아, 리눅스 핵심 해커들이 "서버의 처리량과 데스크톱의 응답성을 복잡한 코드 없이 하나의 수학적 철학으로 통합하자"고 결의하여 탄생했다.

  [기존 타임 슬라이스(O(1)) vs CFS의 가상 시간(vruntime) 철학 비교]

  [ 기존 스케줄러 (고정 배급제) ]
  스케줄러: "너는 우선순위가 높으니까 100ms 덩어리로 줄게, 너는 낮으니까 10ms 줄게. 다 쓰면 맨 뒤로 가!"
  ▶ 단점: 배급받은 덩어리를 들고 튀거나 꼼수 부리는 놈들 통제 불가.
  
  [ CFS 스케줄러 (누적 계좌제) ]
  스케줄러: "시간 덩어리 같은 건 안 준다. 대신 네가 CPU에 붙어서 연산한 시간을 
            나노초(ns) 단위로 계좌(vruntime)에 칼같이 빚으로 달아둘 거다."
  ▶ P1의 계좌(vruntime): 15ms
  ▶ P2의 계좌(vruntime): 3ms  (🚨 P2가 너무 못 먹었네! 당장 P2부터 실행시켜!)

[다이어그램 해설] CFS는 스케줄링의 패러다임을 '배분(Allocation)'에서 '추적(Tracking)'으로 바꿨다. 미래에 얼마를 줄지 짱구를 굴리지 않는다. 과거에 얼마나 먹었는지 가계부(vruntime)만 철저히 쓰고, 그 가계부 잔고가 가장 적은 사람을 기계적으로 부른다. I/O 대기하느라 화면 뒤에서 1시간 동안 잠들어있던 프로세스가 깨어나면? 이놈의 가계부 점수는 바닥(0)이므로, 깨어나는 찰나의 순간에 모든 무거운 프로세스의 목을 날려버리고(선점) 즉각적으로 마우스/키보드 응답을 뱉어내는 기적을 보여준다.

📢 섹션 요약 비유: 은행에서 번호표를 뽑을 때 1번, 2번(우선순위)이 없습니다. 오직 "태어나서 은행 창구 직원과 대화한 시간이 가장 적은 사람"이 문 열고 들어오자마자 무조건 프리패스로 상담을 받는 극단적인 약자 구제(공정성) 시스템입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

1. 가상 실행 시간 (vruntime)의 수학적 계산

CFS의 모든 결정은 오직 이 vruntime 변수 하나로 이루어진다.

vruntime = 실제 쓴 CPU 시간 (actual runtime) × (NICE_0_LOAD / 프로세스의 가중치 Weight)

공평함의 마법: 우선순위가 높은(NICE 값이 낮은, 가중치가 큰) VIP 프로세스는 CPU를 10ms 실제 썼더라도, 분모(가중치)가 커서 장부(vruntime)에는 2ms 쓴 걸로 깎아서 기록해 준다.
결과: 장부 점수가 낮으므로 스케줄러가 "아이고 우리 VIP님 아직도 배가 고프시구나" 하고 계속 CPU를 던져준다. 즉, CFS 환경에서 우선순위란 "시간이 얼마나 천천히 흐르는가(시간의 무게)"를 의미한다.

2. 레드-블랙 트리 (Red-Black Tree)를 통한 O(log N) 정렬

CFS는 140개의 복잡한 큐(Array)를 다 버리고, 오직 레드-블랙 트리(이진 탐색 트리) 딱 1개만 쓴다.

트리의 노드는 각 프로세스를 의미하며, 노드를 정렬하는 기준값(Key)은 오직 vruntime이다.
가장 덜 먹은 놈(가장 vruntime이 작은 놈)은 **무조건 트리의 가장 왼쪽 아래 끝(Leftmost Node)**에 위치한다.

  ┌────────────────────────────────────────────────────────────────────────┐
  │         CFS의 레드-블랙 트리(RB-Tree) 탐색 및 스케줄링 구조            │
  ├────────────────────────────────────────────────────────────────────────┤
  │                                                                        │
  │                  [ P_Root (vruntime: 50) ]                             │
  │                 /                         \                            │
  │               /                             \                          │
  │      [ P_A (vruntime: 30) ]        [ P_B (vruntime: 80) ]              │
  │       /                 \                   /                          │
  │     /                     \               /                            │
  │ [ P_C (vruntime: 10) ]   [ P_D (40) ] [ P_E (70) ]                     │
  │    ⭐ Leftmost Node                                                    │
  │                                                                        │
  │  [스케줄러의 동작]                                                     │
  │  1. "누구 vruntime이 제일 작지?" ─▶ 트리 맨 왼쪽 P_C(10) 획득!         │
  │  2. P_C를 실행시킴. (10ms 씀)                                          │
  │  3. P_C의 vruntime이 10 + 10 = 20 으로 갱신됨.                         │
  │  4. P_C를 트리에 다시 꽂음. 여전히 P_A(30)보다 작으니 계속 왼쪽 끝!    │
  │  5. 또 P_C 실행. 이번엔 20 + 15 = 35 로 갱신됨!                        │
  │  6. 🚨 P_C를 트리에 꽂으니, 이번엔 P_A(30)보다 커져서 우측으로 밀려남. │
  │  7. 새로운 Leftmost Node가 된 P_A(30)가 영광의 CPU를 쟁취함!           │
  └────────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 스케줄러가 하는 일은 너무나 단순하다. 타이머 인터럽트가 뜰 때마다 1. 트리 맨 왼쪽 놈을 꺼내서 일 시키고, 2. 일한 만큼 장부(vruntime) 점수 올린 다음, 3. 다시 트리에 던져 넣는 것뿐이다. 트리 정렬 비용은 $O(\log N)$이므로 10만 개의 프로세스가 떠 있어도 고작 17번의 탐색만으로 완벽히 공정한 타깃을 찾아낸다.

📢 섹션 요약 비유: 운동장 한가운데에 몸무게(vruntime) 순서대로 아이들을 트리 모양으로 세워둡니다. 가장 가벼운 아이(맨 왼쪽)부터 불러내어 밥을 먹이면 몸무게가 찝니다. 밥 먹은 아이를 다시 트리에 밀어 넣으면 살찐 만큼 자연스럽게 오른쪽으로 밀려나고, 그사이에 뒤에 있던 두 번째로 가벼웠던 아이가 맨 왼쪽으로 나와 밥을 먹게 되는 환상적인 자가 조절(Self-regulating) 시스템입니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

고전적 타임 슬라이스 방식 (O(1)) vs 대상 지연 시간 방식 (CFS)

CFS는 "고정된 타임 퀀텀(예: 무조건 10ms)"이라는 개념을 아예 파괴해 버렸다.

비교	기존 O(1) 스케줄러	현대 CFS 스케줄러
할당 방식	절대량 배급 ("너 10ms 써", "너 100ms 써")	비율 지분제 (목표 지연시간을 프로세스 수 N으로 나눔)
타임 퀀텀	고정되어 있음	동적(Dynamic). 큐에 프로세스가 많아지면 슬라이스가 잘게 쪼개짐
I/O 대화형 판별	휴리스틱 코드로 추측해서 보너스 부여	추측 안 함. I/O 대기하느라 vruntime이 멈춰있었으므로 깨어나면 무조건 1등 먹음
오버헤드	$O(1)$ 로 극강의 속도	$O(\log N)$ 트리를 타야 하므로 살짝 무겁지만 완벽한 방어 가능

목표 지연 시간 (Target Latency)의 도입

CFS는 파이(Pie)의 크기를 먼저 정한다. 만약 커널 목표 지연 시간이 20ms라고 치자.

프로세스가 2개면: 20ms / 2 = 각자 10ms씩 타임 퀀텀을 부여받는다.
프로세스가 4개면: 20ms / 4 = 각자 5ms씩 부여받는다.
프로세스가 100개면: 20ms / 100 = 0.2ms... 인데, 너무 작으면 스래싱(문맥교환 폭주)이 터지므로 최소 보장 퀀텀(Minimum Granularity, 예: 1ms) 이하로는 쪼개지지 않도록 방어막을 쳐둔다.
📢 섹션 요약 비유: 피자를 나눌 때 예전에는 무조건 "1인당 손바닥만 한 조각!"이라고 정해놔서 사람이 늘어나면 피자가 모자랐습니다. CFS는 "일단 1판(Target Latency) 안에서 온 사람이 다 나눠 먹어라!" 하고 사람 수대로 칼집을 미세하게 내어주는 완벽한 비율 분배 경제입니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

서버 응답성 vs 처리량(Throughput) 커널 파라미터 튜닝: 리눅스 커널 관리자는 sysctl을 통해 CFS의 성격을 마법처럼 바꿀 수 있다.
- sched_latency_ns (목표 지연 시간): 이 값을 짧게 주면(예: 10ms) 화면 반응이 즉각적으로 변하는 데스크톱 환경이 된다. 길게 주면(예: 100ms) 프로세스 교체가 안 일어나 캐시 히트율이 극강이 되는 배치/DB 서버 환경이 된다.
- sched_min_granularity_ns (최소 조각 단위): 1만 개의 스레드가 떴을 때 컨텍스트 스위치 지옥을 막기 위해 최소 3ms 이하로는 쪼개지 말라고 방어벽을 세우는 필수 튜닝이다.
신규 프로세스(Fork)의 무한 증식 꼼수 방어: 해커가 fork()를 미친 듯이 호출해 자식 프로세스를 10만 개 띄웠다. 이 자식들이 vruntime 0으로 태어나면 세상의 모든 CPU를 다 선점해 버린다(호위 효과).
- CFS의 실무 조치: 자식이 태어날 때 부모의 무거운 vruntime 값을 고스란히 상속(Inherit)받거나, 현재 큐의 min_vruntime보다 크게 설정하여 태어나게 만듦으로써 꼼수로 CPU를 탈취하려는 시도를 수학적으로 완벽히 격리(Penalty)시킨다.

  ┌────────────────────────────────────────────────────────────────────┐
  │     K8s/Docker 환경에서 CFS Cgroups 자원 격리(Throttling) 구조     │
  ├────────────────────────────────────────────────────────────────────┤
  │                                                                    │
  │   [ 물리 CPU 코어 0번 ]                                            │
  │   └── CFS Runqueue (Red-Black Tree)                                │
  │        │                                                           │
  │        ├─▶ [ 그룹 A (Redis Pod) ] (Limit: 50%)                     │
  │        │    └─ 내부 vruntime 경쟁: T1, T2                          │
  │        │                                                           │
  │        └─▶ [ 그룹 B (Web Pod) ] (Limit: 20%)                       │
  │             └─ 내부 vruntime 경쟁: T3, T4                          │
  │                                                                    │
  │   🚨 CFS 대역폭 제어 (Bandwidth Control):                          │
  │   그룹 A의 T1, T2가 50%의 시간을 소진하는 순간, CFS는 즉시         │
  │   그룹 A의 트리 노드 전체를 트리에서 뽑아버리고(Throttle) 100ms    │
  │   뒤에 재충전될 때까지 유배(Sleep) 보내어 완벽한 SLA를 보장한다.   │
  └────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 단순히 스레드 1개만 트리에 넣는 것이 아니다. 그룹(Cgroups) 자체를 거대한 하나의 노드로 만들어 트리에 넣는 **'계층적 스케줄링(Hierarchical Scheduling)'**이 CFS의 진정한 실무적 가치다. Docker 컨테이너에 CPU Limit을 0.5로 걸었을 때 정확히 50%에서 모가지가 잘리는 이유가 바로 CFS 대역폭 제어(CFS Bandwidth Control) 매커니즘이 작동하기 때문이다.

📢 섹션 요약 비유: CFS 트리는 마트료시카(인형 속에 인형) 같습니다. 구글 클라우드라는 큰 트리 안에 넷플릭스라는 노드가 있고, 그 넷플릭스 노드 안을 열어보면 또 트리가 있어서 각 스레드들이 자기들끼리 싸웁니다. 넷플릭스가 돈 낸 만큼(50%)만 정확히 놀 수 있게 큰 트리가 숨통을 조였다 풀었다(Throttling) 합니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

휴리스틱 코드(땜질 처방)의 삭제로 커널이 가벼워지고 버그가 근절되었으며, O(log N)의 안정적인 탐색 속도와 완벽한 기아(Starvation) 방어 메커니즘을 통해 슈퍼컴퓨터의 배치 연산부터 스마트폰의 부드러운 터치 스크롤링까지 단 하나의 스케줄러로 전부 포괄하는 '통일장 이론'을 완성했다.

결론 및 미래 전망

리눅스의 CFS(Completely Fair Scheduler)는 스케줄링 이론이 도달한 하나의 정점이자 21세기 IT 인프라의 심장이다. 세상 모든 웹 서버, 안드로이드 폰, 쿠버네티스 노드가 지금 이 순간에도 vruntime 트리를 갱신하고 있다. 미래에는 여기서 한 발 더 나아가, ARM big.LITTLE 코어 구조처럼 전력 효율이 다른 코어들에 프로세스를 던질 때, 전력 소모량(W)을 vruntime 계산에 융합하는 EAS (Energy Aware Scheduling) 기술과, 커널을 수정하지 않고 개발자가 eBPF를 통해 vruntime 트리의 가중치를 런타임에 마음대로 조작하는 **Bpf-based Custom Scheduler (sched_ext)**의 시대로 거대한 패러다임 쉬프트가 일어나고 있다.

📢 섹션 요약 비유: 복잡한 편법과 오지랖(O(1) 시절)을 다 버리고, "공정한 장부(vruntime) 하나만 남기자"는 단순함의 미학이 결국 세상을 지배했습니다. CFS는 컴퓨터 과학 역사상 가장 위대한 "뺄셈의 철학(더러운 코드 삭제)"이 만들어낸 마스터피스입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
가상 실행 시간 (vruntime)	CFS의 영혼. 프로세스가 CPU를 쓴 물리적 시간에 우선순위 가중치를 곱해 "시간의 상대적 흐름"을 구현한 천재적 장부다.
레드-블랙 트리 (Red-Black Tree)	vruntime을 O(log N)의 준수한 속도로 삽입/삭제/정렬해 내며 O(1) 스케줄러를 대체한 CFS의 물리적 자료구조다.
Cgroups (Control Groups)	CFS의 계층적 트리에 올라타 컨테이너 단위의 완벽한 자원 쿼터(Quota) 격리를 실현한 클라우드 시대의 핵심 기술이다.
리눅스 O(1) 스케줄러	속도는 O(1)로 최고였으나, 대화형/연산형을 찍어 맞추려는 더러운 휴리스틱 코드 때문에 무너져 CFS에게 자리를 물려준 선배다.
보장 스케줄링 (Guaranteed)	$\frac{1}{N}$ 비율로 자원을 공평하게 나누어 주자는 학술적 철학으로, 이 철학이 현실의 C 코드로 육화(Incarnation)된 것이 바로 CFS다.

👶 어린이를 위한 3줄 비유 설명

게임방에서 "착한 애는 많이 주고 나쁜 애는 쫓아내자"라고 사람이 마음대로 정하면 억울한 일(렉 발생)이 생겨요.
리눅스 CFS는 마음대로 정하는 걸 다 없애고, 오직 "태어나서 지금까지 게임기(CPU)를 제일 적게 만진 불쌍한 사람(가장 낮은 vruntime)부터 무조건 1등으로 시켜주자!"라는 완벽하게 공평한 장부를 만들었어요.
잠만 자느라 게임을 한 번도 못 한 친구가 깨어나면 장부 점수가 바닥이니까, 눈을 뜨자마자 다른 애들을 다 밀어내고 즉시 게임을 할 수 있게 되어 화면이 하나도 안 끊기고 부드럽게 돌아간답니다!