Chaos and Order

💡 왼쪽 원문을 읽으면서 오른쪽에 따라 써보세요. Tab 키로 힌트를 받을 수 있습니다.

들어가며 — 스케줄러는 OS의 심장이다

스케줄러는 한 마디로 "어떤 태스크가 CPU를 가질지 결정하는 모듈"이다. 이 결정이 잘못되면 게임은 끊기고, 데이터베이스는 느려지고, 인터랙티브 셸은 멈춰 보인다. 반대로 잘 동작하면 사용자는 수만 개의 태스크가 동시에 돌고 있다는 사실조차 모른다.

Linux 스케줄러는 지난 30년 동안 여러 번 다시 쓰였다. 단순한 라운드로빈 → O(N) 스케줄러 → Ingo Molnar의 O(1) → Con Kolivas의 도전 → 2007년 CFS(Completely Fair Scheduler) 도입 → 그리고 2023년 10월 Linux 6.6에서 **EEVDF(Earliest Eligible Virtual Deadline First)**로의 전환. 각 단계는 그 시점에 풀어야 할 새로운 문제에 대한 답이었다.

이 글은 Linux 스케줄러의 역사와 현재를 모두 다룬다. CFS의 vruntime이 무엇인지, 왜 레드블랙 트리를 쓰는지, EEVDF가 CFS와 무엇이 다른지, 그리고 컨테이너와 PREEMPT_RT, sched_ext 같은 모든 모던 토픽을 한 글에서 정리한다.

이 글은 "Linux 내부 구조 시리즈"의 세 번째 글이다. 이전 글:

Linux 부팅 과정 딥다이브 — 부팅 경로
io_uring 완벽 가이드 — I/O 경로

세 글을 모두 읽으면 "내 프로세스가 시작되어 CPU를 받고 I/O를 하기까지 커널이 무엇을 해주는가"라는 풍경 전체를 볼 수 있다.

1. 스케줄러의 기본 — 왜 어려운가

1.1 무엇을 결정해야 하나

스케줄러는 두 개의 질문에 답한다:

누가 다음에 CPU를 받을 것인가 — 큐에 있는 여러 태스크 중 하나를 골라야 한다.
얼마나 오래 줄 것인가 — 너무 짧으면 컨텍스트 스위치 비용이, 너무 길면 응답성이 나빠진다.

이 두 결정은 매번 인터럽트가 들어올 때마다, 매번 태스크가 sleep할 때마다, 매번 새 태스크가 깨어날 때마다 다시 내려야 한다. 1초에 수십만 번씩 일어나는 결정이다.

1.2 좋은 스케줄러의 조건

이상적인 스케줄러는 다음을 모두 만족해야 한다:

공정성(Fairness) — 같은 우선순위의 태스크는 비슷한 양의 CPU를 받아야 한다.
응답성(Responsiveness) — 인터랙티브 태스크 (셸, GUI)는 빨리 깨어나야 한다.
처리량(Throughput) — 배치 태스크 (컴파일, 인코딩)는 효율적으로 돌아야 한다.
공평한 우선순위(Priority) — nice 값으로 누군가 양보를 표현했다면 존중해야 한다.
확장성(Scalability) — 수만 개의 태스크와 수백 개의 코어에서도 결정 시간이 일정해야 한다.
실시간 보장(Real-time) — 데드라인이 있는 태스크는 그 시간 안에 실행을 보장.

이 모든 것을 동시에 만족하는 것은 불가능에 가깝다. 어느 것을 우선할지가 스케줄러 설계의 핵심 트레이드오프이다.

★ Insight ─────────────────────────────────────

공정성과 응답성은 종종 충돌한다: 100% 공정하려면 모든 태스크에 정확히 같은 시간을 줘야 하지만, 인터랙티브 태스크는 그 사이에 끼어들어 빨리 처리되어야 한다. 이 긴장이 모든 스케줄러 설계의 핵심 갈등이다.
CFS가 풀지 못한 핵심 문제: 공정성은 아주 잘 풀었지만, 인터랙티브 태스크에 "지연 보장"을 주는 것은 휴리스틱(예: 깨어나는 태스크에 가산점)에 의존했다. EEVDF는 이를 정식 모델로 끌어올렸다.
NUMA가 더한다: 멀티 소켓 시스템에서는 같은 코어를 주는 것보다 같은 소켓을 주는 것이 캐시 히트와 메모리 대역폭 측면에서 훨씬 중요하다. 이는 단일 큐 모델로는 표현할 수 없다. ─────────────────────────────────────────────────

2. 역사적 배경 — Linux 스케줄러의 진화

2.1 Linux 1.x — 진짜 단순한 라운드로빈

Linux 0.01~1.x 시절 스케줄러는 매우 단순했다. 모든 프로세스를 리스트로 관리하고, 각자에게 카운터(counter)를 주었다. 매 틱마다 카운터를 줄이고, 0이 되면 다른 태스크에 양보. 모든 카운터가 0이 되면 한꺼번에 리셋했다.

// Linux 1.0 sched.c (개념 코드)
while (1) {
    struct task_struct *p, *next = idle_task;
    int max_counter = 0;

    for_each_task(p) {
        if (p->state == TASK_RUNNING && p->counter > max_counter) {
            max_counter = p->counter;
            next = p;
        }
    }

    if (max_counter == 0) {
        // 모든 카운터가 0 — 리셋
        for_each_task(p) {
            p->counter = (p->counter >> 1) + p->priority;
        }
    }

    switch_to(next);
}

문제: 매 결정마다 모든 태스크를 순회. O(N) 복잡도. 태스크 수가 늘면 결정 시간도 늘어난다. 1990년대 워크스테이션에서는 견딜 만했지만 서버에서는 한계.

2.2 Linux 2.4 — 여전히 O(N), 더 정교해짐

Linux 2.4의 스케줄러는 1.x의 모델을 정교화했다. goodness() 함수가 각 태스크의 점수를 계산하고, 가장 높은 태스크를 골랐다. SMP를 위해 CPU별 큐가 도입되었지만, 본질적으로는 여전히 O(N)이었다.

2.3 Linux 2.6.0 — Ingo Molnar의 O(1) 스케줄러

2003년 Linux 2.6.0에서 Ingo Molnar가 O(1) 스케줄러를 도입했다. 핵심 아이디어:

140개의 우선순위 큐 — 0-139번. 각 큐는 같은 우선순위의 태스크 리스트.
활성/만료 큐 두 개 — 한 번 실행한 태스크는 만료 큐로 옮긴다. 활성 큐가 비면 두 큐를 swap.
비트맵으로 다음 큐 찾기 — 140비트 비트맵의 첫 1을 찾으면 가장 높은 우선순위 큐.

// 핵심 구조 (개념 코드)
struct prio_array {
    int nr_active;
    unsigned long bitmap[BITMAP_SIZE];
    struct list_head queue[MAX_PRIO];  // 140
};

struct runqueue {
    spinlock_t lock;
    int nr_running;
    struct prio_array *active, *expired;
    struct prio_array arrays[2];
};

pick_next_task는 비트맵에서 첫 비트를 찾고 (find_first_bit, bsf 명령어 한 번), 해당 큐의 첫 태스크를 골랐다. 모든 동작이 O(1).

문제는 다른 데서 왔다. 인터랙티브성 휴리스틱이 너무 복잡했다. 태스크가 인터랙티브한지 배치인지를 sleep 시간으로 추정하고, 우선순위를 보너스로 +/- 5까지 조정하는 로직이 수백 줄에 달했다. 이 휴리스틱은 자주 틀렸고, 사용자들은 "오디오가 끊긴다", "마우스가 끊긴다"는 버그 리포트를 계속 올렸다.

2.4 Con Kolivas의 RSDL/SD — 외부의 도전

2006년 Con Kolivas라는 호주의 마취과 의사이자 커널 해커가 RSDL(Rotating Staircase Deadline)이라는 새 스케줄러를 발표했다. 이후 SD(Staircase Deadline)로 이름을 바꿨다. 핵심 철학:

휴리스틱 없음 — 인터랙티브성을 추정하지 않는다.
정확한 공정성 — 각 태스크는 자신의 우선순위에 비례하는 양의 CPU를 받는다.

Con Kolivas는 "데스크탑 사용자의 경험"에 집중했다. 그의 스케줄러는 데스크탑에서 O(1)보다 명백히 좋은 응답성을 보였지만, 메인라인에는 머지되지 못했다. 정치적 갈등도 있었다 (Linus와 Ingo 진영 vs Con).

2.5 2007 — CFS의 등장

Con의 도전에 자극을 받은 Ingo Molnar는 2007년 CFS(Completely Fair Scheduler)를 발표했다. RSDL의 "공정성 우선" 철학을 받아들이되, 더 우아한 알고리즘을 사용했다:

vruntime(virtual runtime) — 각 태스크가 "실행한 시간"을 가상화한 값. 우선순위가 낮을수록 vruntime이 빨리 늘어난다.
레드블랙 트리 — 모든 실행 가능한 태스크를 vruntime 순으로 정렬.
항상 leftmost를 선택 — 가장 vruntime이 작은 태스크가 다음에 실행.

Linux 2.6.23(2007년 10월)부터 메인 스케줄러가 되었다.

2.6 2023 — EEVDF로 교체

CFS는 16년간 군림했지만, 응답성 문제는 여전했다. Peter Zijlstra(현재 Linux 스케줄러 메인테이너)는 1995년 Stoica, Abdel-Wahab, Plaxton의 28년 전 논문 "Earliest Eligible Virtual Deadline First"를 다시 발견했다. 이 알고리즘은 공정성과 지연 보장을 동시에 제공한다.

2023년 10월 Linux 6.6에서 CFS는 공식적으로 EEVDF로 교체되었다. 코드는 여전히 kernel/sched/fair.c에 있고 함수 이름도 그대로지만, 알고리즘은 다르다.

이 글의 나머지 절은 CFS와 EEVDF를 함께 다룬다. 둘은 같은 가족이고, EEVDF를 이해하려면 CFS를 이해해야 한다.

3. CFS의 핵심 개념

3.1 "완전히 공정한"의 의미

CFS의 이상적인 모델은 이렇다: N개의 태스크가 있다면, 각자에게 1/N의 CPU를 동시에 준다. 즉, 100% 공정하게 시간을 나눈다.

물론 실제 CPU는 한 번에 하나의 태스크만 실행할 수 있다. 그래서 시간 슬라이싱으로 흉내낸다 — 매우 짧은 시간 동안 한 태스크에 100%를 주고, 다음 태스크로 넘어간다.

이상적인 비례 공정성에서 각 태스크가 받았어야 할 CPU 시간을 이상적인 실행 시간이라고 하면, 실제 실행 시간은 이상적인 시간을 따라잡으려고 노력한다. CFS는 매번 "지금 가장 뒤처진 태스크"를 골라서 실행한다.

3.2 vruntime — 정규화된 실행 시간

vruntime은 각 태스크가 실행한 시간을 우선순위로 정규화한 값이다. 공식:

delta_vruntime = delta_real_time * (NICE_0_LOAD / task_weight)

delta_real_time: 실제 실행한 시간 (나노초)
NICE_0_LOAD: nice=0일 때의 가중치 (1024)
task_weight: 해당 태스크의 가중치

nice=0 태스크는 vruntime이 실제 시간과 같은 속도로 증가한다. nice=-5 태스크는 가중치가 약 4배이므로 vruntime이 1/4 속도로 증가 (즉, 더 자주 실행됨). nice=+5 태스크는 반대로 4배 빠르게 증가.

vruntime의 정의가 자동으로 우선순위를 표현한다. 스케줄러는 단지 "vruntime이 가장 작은 태스크"를 선택할 뿐이고, 그 결과로 nice 값에 비례하는 CPU 분배가 자연스럽게 일어난다.

3.3 nice → weight 변환 표

Linux는 nice 값과 가중치를 미리 계산된 표로 매핑한다:

const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

각 단계마다 약 1.25배 차이가 난다. nice 값이 1 차이 나면 CPU 비율이 약 10% 차이 난다고 알려져 있다. nice -20과 +19의 비율은 약 5,900배.

3.4 sched_entity와 task_group

CFS는 단순한 태스크뿐 아니라 태스크 그룹도 스케줄링한다. cgroups의 CPU controller가 이를 활용한다. 핵심 추상화:

struct sched_entity {
    struct load_weight load;        /* 가중치 */
    struct rb_node     run_node;     /* 레드블랙 트리 노드 */
    unsigned int       on_rq;
    u64                exec_start;
    u64                sum_exec_runtime;
    u64                vruntime;
    u64                slice;        /* EEVDF의 슬라이스 */
    s64                lag;          /* EEVDF의 lag */
    u64                deadline;     /* EEVDF의 가상 데드라인 */
    /* ... */
    struct cfs_rq      *cfs_rq;       /* 소속 큐 */
    struct cfs_rq      *my_q;          /* 그룹일 경우 자식 큐 */
};

sched_entity는 태스크일 수도 있고 그룹일 수도 있다. 그룹이면 my_q가 자식들의 cfs_rq를 가리킨다. 이 재귀 구조 덕분에 그룹 안의 그룹이 가능하다 (예: 컨테이너 안의 컨테이너).

3.5 cfs_rq — CPU별 실행 큐

각 CPU마다 하나의 cfs_rq가 있다. 같은 cgroup 안에서도 CPU마다 별도의 큐가 있다 (락 경쟁 회피).

struct cfs_rq {
    struct load_weight       load;
    unsigned int             nr_running;
    u64                      min_vruntime;     /* 트리 안에서 가장 작은 vruntime */
    struct rb_root_cached    tasks_timeline;   /* 레드블랙 트리 */
    struct sched_entity      *curr;             /* 현재 실행 중인 entity */
    struct sched_entity      *next;             /* 다음 후보 */
    /* ... */
};

min_vruntime은 매우 중요하다. 새로 깨어나는 태스크의 vruntime을 어떻게 초기화할지 결정하는 기준이다. 너무 작게 두면 sleep만 하던 태스크가 깨어나서 영원히 CPU를 독차지한다.

4. CFS 알고리즘 — pick_next_task와 task_tick

4.1 다음 태스크 고르기

CFS의 pick_next_task 핵심 로직:

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left) return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

레드블랙 트리의 leftmost 노드. 정렬 키는 vruntime이므로, leftmost가 항상 vruntime이 최소인 entity이다. rb_first_cached는 leftmost를 캐싱하므로 O(1)이다.

4.2 매 틱마다 일어나는 일

scheduler_tick은 매 틱(보통 4ms)마다 호출된다. CFS의 처리:

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued) {
    struct sched_entity *se = &curr->se;
    struct cfs_rq *cfs_rq = cfs_rq_of(se);

    update_curr(cfs_rq);   // vruntime 갱신
    update_load_avg(cfs_rq, se, UPDATE_TG);

    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

update_curr은 현재 entity가 마지막 호출 이후로 얼마나 실행했는지 측정해 vruntime에 반영한다.

check_preempt_tick은 "지금 다른 태스크가 실행되어야 하지 않을까?"를 검사한다. 두 가지 조건:

현재 태스크의 슬라이스 (sched_slice(...))를 다 썼는가?
다른 태스크와의 vruntime 차이가 임계값을 넘었는가?

조건이 맞으면 resched_curr(rq)로 리스케줄 플래그를 켠다. 다음 안전한 시점에 컨텍스트 스위치가 일어난다.

4.3 sched_period와 sched_min_granularity

CFS는 두 개의 핵심 튜닝 파라미터를 가진다:

sched_latency_ns (= sched_period) — 모든 태스크를 한 번씩 돌리는 데 걸리는 목표 시간. 기본 6ms.
sched_min_granularity_ns — 한 태스크가 받는 최소 슬라이스. 기본 0.75ms.

태스크가 N개라면 각자의 슬라이스는 sched_latency / N. 단, 이 값이 min_granularity보다 작아지면 min_granularity로 클램핑된다. 즉, N이 너무 크면 sched_latency가 늘어난다 (sched_latency = N * sched_min_granularity).

// 6.1 이전 (CFS) sched_slice 의사 코드
unsigned long sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    unsigned int nr_running = cfs_rq->nr_running;
    u64 slice = sched_latency;
    if (nr_running > sched_nr_latency)
        slice = nr_running * sched_min_granularity;

    // 가중치 비율로 분배
    slice = slice * se->load.weight / cfs_rq->load.weight;
    return slice;
}

이 모델은 "공정"하지만 응답성은 약하다. 특히 인터랙티브 태스크가 막 깨어났을 때 자기 슬라이스가 끝날 때까지 기다려야 할 수 있다.

4.4 깨어난 태스크의 vruntime — place_entity

새 태스크나 sleep에서 깨어난 태스크는 vruntime을 어떻게 초기화할까? 너무 작으면 영원히 CPU를 독차지하고, 너무 크면 깨어난 응답성이 나빠진다.

CFS는 place_entity에서 min_vruntime을 기준으로 약간의 패널티를 준다:

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                         int initial) {
    u64 vruntime = cfs_rq->min_vruntime;

    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);  // 새 태스크는 디빗

    if (!initial) {
        unsigned long thresh = sysctl_sched_latency / 2;
        vruntime -= thresh;  // 깨어난 태스크는 보너스
    }

    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

thresh만큼의 보너스가 인터랙티브 응답성의 휴리스틱이다. 이 값이 너무 크면 sleep만 하는 태스크가 너무 우대받고, 너무 작으면 응답성이 나빠진다.

5. CFS의 한계 — 왜 EEVDF로 옮겼나

CFS는 매우 우아하지만 몇 가지 약점이 있었다:

5.1 지연 보장 부족

CFS는 "공정성"은 잘 풀었지만, "이 태스크는 100us 안에 깨어나서 처리되어야 한다"는 보장을 줄 방법이 없었다. 우선순위는 비율을 표현하지 (nice -5는 nice 0보다 약 4배의 CPU), 절대 지연을 표현하지 못한다.

5.2 인터랙티브 휴리스틱

place_entity에서 thresh만큼의 보너스를 주는 것은 휴리스틱이다. 이 값은 워크로드에 따라 너무 크거나 너무 작다. 게이밍/오디오/실시간 워크로드에서는 항상 부족했다.

5.3 latency-nice 패치의 시도

2018-2022년 사이에 Vincent Guittot이 latency-nice라는 개념을 제안했다. nice가 "CPU 비율"을 표현한다면, latency-nice는 "응답 지연 우선순위"를 표현한다. 이 패치는 여러 번 리뷰되었지만 메인라인에 머지되지 못했다 — 너무 복잡하고 기존 CFS와 잘 어우러지지 않았다.

5.4 EEVDF 논문의 재발견

이 시점에 Peter Zijlstra가 1995년 Stoica, Abdel-Wahab, Plaxton의 논문을 다시 들여다보았다. 이 논문은 "공정성과 지연 보장을 동시에 제공하는" 알고리즘을 제시했다. 개념이 미세하게 우아했고, 무엇보다 latency-nice를 자연스럽게 통합할 수 있었다.

2023년 7월부터 패치 시리즈가 나왔고, 10월 6.6에서 메인라인에 머지되었다.

6. EEVDF — Earliest Eligible Virtual Deadline First

6.1 핵심 아이디어 셋

EEVDF는 세 가지 개념 위에서 동작한다:

Lag — 태스크가 받았어야 할 양 vs 실제로 받은 양의 차이.
Eligible time — 그 태스크가 "현재 받을 자격이 있는" 가상 시간.
Virtual deadline — 그 태스크의 슬라이스가 끝나야 하는 가상 시간.

스케줄러는 매번 "현재 eligible한 태스크 중에서 가장 가까운 deadline을 가진 것"을 선택한다.

6.2 Lag — 빚과 저축

각 태스크는 "이상적으로 받았어야 할 vruntime"이 있다. 실제 vruntime이 그보다 크면 — 즉 너무 많이 받았으면 — 음의 lag (빚이 있음). 작으면 양의 lag (저축이 있음).

lag = ideal_vruntime - actual_vruntime

새 태스크는 lag = 0으로 시작. sleep에서 깨어나면 lag을 그대로 유지하고 (이게 핵심), 그 만큼만 우선순위를 받는다.

6.3 Eligible Time

태스크가 "지금 받을 자격이 있는가"를 결정한다. 공식 (단순화):

eligible(task) = (lag(task) >= 0)

저축이 있는 태스크는 eligible. 빚이 있는 태스크는 일단 대기. 단, 모든 태스크가 빚이 있다면? 그러면 lag이 가장 큰 태스크가 우선 (가장 덜 빚진 태스크).

6.4 Virtual Deadline

각 eligible 태스크에 데드라인을 부여:

deadline = eligible_time + (slice / weight_normalized)

작은 슬라이스를 가진 태스크 (즉, 응답성을 원하는 태스크)는 더 가까운 데드라인을 가진다. 큰 슬라이스를 가진 태스크 (배치 워크로드)는 더 먼 데드라인.

6.5 EEVDF의 선택 함수

매 결정마다:

eligible한 태스크 집합을 구한다.
그 중에서 데드라인이 가장 빠른 태스크를 고른다.

레드블랙 트리는 vruntime이 아닌 deadline 기준으로 정렬되도록 변경되었다. eligible 검사는 트리 순회 중에 한다.

// 6.6+ pick_eevdf 의사 코드
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) {
    struct sched_entity *se = NULL;
    struct rb_node *node;

    for (node = rb_first_cached(&cfs_rq->tasks_timeline);
         node; node = rb_next(node)) {
        struct sched_entity *e = rb_entry(node, struct sched_entity, run_node);
        if (!entity_eligible(cfs_rq, e))
            continue;
        if (!se || deadline_lt(e->deadline, se->deadline))
            se = e;
        // Optimization: 부분 트리 스킵
    }
    return se;
}

실제 구현은 트리 안에 "이 서브트리에서 가장 빠른 데드라인" 같은 보조 정보를 두고 부분 트리를 스킵한다. 평균 O(log N)을 유지한다.

6.6 슬라이스가 응답성을 표현한다

EEVDF에서 응답성을 원하는 태스크는 슬라이스를 짧게 설정하면 된다. 그러면 데드라인이 가까워져 자주 선택된다. 이는 sched_setattr로 latency-nice (또는 slice 직접 지정)를 통해 노출된다.

// 사용자 공간 예제
struct sched_attr attr = {
    .size = sizeof(attr),
    .sched_policy = SCHED_NORMAL,
    .sched_runtime = 1 * 1000 * 1000,  // 1ms 슬라이스 (응답성 우선)
    .sched_period = 0,
    .sched_deadline = 0,
};
sched_setattr(0, &attr, 0);

오디오 처리, 게이밍 같은 응답성 critical 태스크는 슬라이스를 1-2ms로 설정. 배치 워크로드는 기본 (보통 6ms 정도) 사용.

★ Insight ─────────────────────────────────────

EEVDF의 미세한 우아함: CFS는 "공정성을 풀고 응답성은 휴리스틱으로"였다. EEVDF는 "공정성과 응답성을 같은 모델로 한꺼번에 푼다." Lag이 공정성을 보장하고, deadline이 응답성을 보장한다. 두 개념이 직교한다.
이상한 부분: EEVDF 코드에서도 vruntime이라는 이름이 살아남았다. 의미는 약간 달라졌지만 (lag 계산의 기준점), 호환성을 위해 이름을 유지한다. "CFS 코드가 그대로 EEVDF 코드"라는 말은 절반은 사실이다.
lag을 sleep을 가로지르며 유지: 깨어난 태스크가 자기 lag을 그대로 가져온다. 이 한 가지 변화로 인터랙티브성이 자연스럽게 풀린다 — 오랫동안 sleep한 태스크는 자연스럽게 큰 lag을 가지므로 깨어났을 때 우선권을 받는다. ─────────────────────────────────────────────────

7. 멀티코어 — sched domain과 로드 밸런싱

지금까지의 모든 이야기는 단일 CPU에서의 스케줄링이었다. 하지만 모던 시스템은 수십~수백 개의 코어를 가진다. 코어 간 태스크 분배가 새로운 문제이다.

7.1 CPU별 큐

Linux는 CPU마다 별도의 runqueue를 가진다. 락 경쟁이 줄어들고 캐시 친화적이지만, 큐 사이의 균형을 맞추는 비용이 새로 생긴다.

7.2 sched_domain 계층 구조

CPU들은 계층적인 도메인으로 묶여 있다. 예를 들어 두 소켓, 각 소켓에 8 코어, 각 코어에 2 SMT(하이퍼스레딩):

[NUMA 도메인]
   ├── [소켓 0 도메인]
   │      ├── [코어 0 도메인 (SMT 0, SMT 1)]
   │      ├── [코어 1 도메인 (SMT 2, SMT 3)]
   │      └── ...
   └── [소켓 1 도메인]
          ├── [코어 8 도메인 (SMT 16, SMT 17)]
          └── ...

도메인마다 로드 밸런싱 정책이 다르다. 가까운 도메인 (SMT 형제) 간에는 자주, 자주, 적은 비용으로. 먼 도메인 (NUMA) 간에는 드물게, 큰 비용으로 옮겨야 한다.

7.3 Periodic Load Balancing

매 틱마다 (정확히는 nohz_idle_balancer가 결정한 시점에) 각 CPU는 자기 도메인의 로드 균형을 검사한다:

static void run_rebalance_domains(struct softirq_action *h) {
    struct rq *this_rq = this_rq();
    enum cpu_idle_type idle = this_rq->idle_balance ? CPU_IDLE : CPU_NOT_IDLE;
    rebalance_domains(this_rq, idle);
}

load_balance 함수는 sched_domain을 순회하며:

가장 바쁜 그룹을 찾는다 (find_busiest_group).
그 그룹의 가장 바쁜 CPU를 찾는다 (find_busiest_queue).
그 CPU에서 일부 태스크를 가져온다 (move_tasks).

이 작업은 비싸다. 특히 NUMA 경계를 넘으면 캐시 미스와 메모리 트래픽이 발생한다.

7.4 Newly Idle Balancing

CPU가 막 idle이 되면 (즉, 자기 큐가 비면), 즉시 다른 CPU에서 일을 가져오려고 시도한다. 이는 응답성을 위해 매우 중요하다 — idle CPU가 있는데 다른 CPU에 일이 쌓여 있으면 안 된다.

7.5 NUMA Balancing — AutoNUMA

NUMA 시스템에서는 태스크의 메모리가 어느 노드에 있는지가 매우 중요하다. 태스크와 메모리가 다른 노드에 있으면 매번 인터커넥트를 거쳐야 해서 느리다.

Linux는 AutoNUMA라는 기능으로 이를 자동 조정한다:

주기적으로 페이지 폴트를 일으켜서 (prot=NONE 트릭) 어떤 페이지가 자주 접근되는지 추적.
자주 접근되는 페이지가 다른 노드에 있으면 마이그레이션.
또는 태스크를 메모리가 있는 노드로 옮김.

/proc/sys/kernel/numa_balancing으로 켜고 끌 수 있다.

7.6 CPU Capacity와 Big.LITTLE

ARM big.LITTLE 같은 비대칭 시스템에서는 코어마다 처리 능력이 다르다. Linux는 각 CPU의 cpu_capacity 값을 가지고 (보통 1024가 최대), 이를 로드 밸런싱에 반영한다.

이를 정교하게 다루는 것이 EAS(Energy Aware Scheduling). 모바일/임베디드에서 큰 코어와 작은 코어 사이에 태스크를 분배해 전력을 절약한다. Android의 메인 스케줄링 정책이다.

8. 다른 스케줄링 클래스 — Linux는 단일 스케줄러가 아니다

CFS/EEVDF는 SCHED_NORMAL (또는 SCHED_OTHER) 정책 아래의 태스크를 처리한다. 그러나 Linux는 다른 정책도 지원한다.

8.1 SCHED_FIFO와 SCHED_RR (Real-Time)

POSIX에서 정의한 실시간 스케줄링 정책. 우선순위 1-99를 가진다. CFS 태스크보다 항상 먼저 실행된다.

SCHED_FIFO: 자발적으로 양보(sched_yield)하거나 더 높은 우선순위 태스크가 깨어나기 전까지는 실행을 계속한다.
SCHED_RR: FIFO와 같지만, 같은 우선순위의 태스크끼리는 라운드로빈으로 시간을 나눈다.

struct sched_param param = { .sched_priority = 50 };
sched_setscheduler(0, SCHED_FIFO, &param);

위험한 정책이다. SCHED_FIFO로 무한 루프를 돌리면 시스템이 응답하지 않는다. RLIMIT_RTTIME과 /proc/sys/kernel/sched_rt_runtime_us 같은 제한이 있다 (기본 95% — 나머지 5%는 일반 태스크 보호용).

8.2 SCHED_DEADLINE (CBS)

Linux 3.14에서 도입된 EDF 기반 스케줄링 정책. 각 태스크는 세 개의 파라미터를 선언한다:

runtime: 한 주기에 보장받을 CPU 시간
deadline: 그 안에 runtime을 받을 시간 한도
period: 다음 주기까지의 시간

struct sched_attr attr = {
    .size = sizeof(attr),
    .sched_policy = SCHED_DEADLINE,
    .sched_runtime  = 10 * 1000 * 1000,  // 10 ms
    .sched_deadline = 30 * 1000 * 1000,  // 30 ms
    .sched_period   = 30 * 1000 * 1000,  // 30 ms
};
sched_setattr(0, &attr, 0);

이 태스크는 매 30ms마다 적어도 10ms의 CPU 시간을 받는다. 그렇지 않으면 커널은 어드미션 컨트롤을 통해 태스크 생성을 거부한다 (시스템이 그만한 약속을 지킬 수 없는 경우).

내부적으로 CBS(Constant Bandwidth Server)라는 알고리즘을 사용하여, 한 태스크가 약속을 어기면 다른 태스크에 영향을 주지 않는다.

8.3 SCHED_IDLE과 SCHED_BATCH

SCHED_IDLE: nice +19보다 더 낮은 우선순위. 진짜 한가할 때만 실행.
SCHED_BATCH: 인터랙티브 보너스를 받지 않는 일반 태스크. 컴파일/인코딩 같은 배치 워크로드용.

chrt 명령어로 외부에서 설정 가능:

chrt -i 0 ./background-task   # SCHED_IDLE
chrt -b 0 ./compile-job        # SCHED_BATCH

8.4 우선순위 매트릭스

정책	우선순위 범위	설명
SCHED_DEADLINE	(별도)	EDF 기반, 어드미션 제어
SCHED_FIFO	1-99	실시간, 양보 안 함
SCHED_RR	1-99	실시간, 라운드로빈
SCHED_NORMAL	nice -20..+19	CFS/EEVDF
SCHED_BATCH	nice -20..+19	인터랙티브 보너스 없음
SCHED_IDLE	(최저)	한가할 때만

스케줄러는 이 순서대로 클래스를 검사한다. 높은 클래스에 실행 가능한 태스크가 있으면 낮은 클래스는 무시된다.

9. PREEMPT_RT — 진짜 실시간 Linux

기본 Linux 커널은 일부 코드 영역이 선점 불가능하다 (preempt_disable, spin_lock, 인터럽트 핸들러 등). 이 영역에서 머무르는 시간이 100us를 넘기도 한다. 진짜 실시간(예: 산업용 제어, 음악 처리)에는 부족하다.

PREEMPT_RT는 Ingo Molnar가 2004년부터 시작한 패치 셋으로, 거의 모든 커널 코드를 선점 가능하게 만든다:

스핀락 → rt_mutex (잠 들 수 있는 락)
인터럽트 핸들러 → 커널 스레드로 변환
ksoftirqd가 모든 softirq를 처리

20년 가까이 외부 패치였다가, 2024년 9월 Linux 6.12에서 메인라인에 부분 머지되었다 (PREEMPT_RT 옵션).

★ Insight ─────────────────────────────────────

메인라인 머지의 의미: PREEMPT_RT는 단순한 옵션이 아니다. 거의 모든 동기화 프리미티브의 의미를 바꾼다. 메인라인 머지는 20년에 걸친 Linux 동기화 코드의 점진적 재작성의 결과다.
누가 쓰나: Bosch, Siemens 같은 산업 자동화 회사들. Tesla의 차량 OS도 PREEMPT_RT 기반이라고 알려져 있다. 음악 워크스테이션의 ALSA 백엔드도 PREEMPT_RT를 권장한다.
트레이드오프: 진짜 실시간을 얻는 대신 일반 처리량은 약간 떨어진다 (5-15%). 데스크탑이나 서버에는 보통 권장되지 않는다. ─────────────────────────────────────────────────

10. cgroups CPU controller — 컨테이너의 스케줄링

컨테이너의 CPU 제한은 CFS의 그룹 스케줄링과 cgroups CPU controller로 구현된다.

10.1 cpu.weight (cgroup v2)

각 cgroup은 가중치를 가진다. 형제 cgroup 사이에서 가중치 비율로 CPU가 분배된다.

# cgroup v2
echo 100 > /sys/fs/cgroup/my-container/cpu.weight   # 기본 100
echo 200 > /sys/fs/cgroup/my-container/cpu.weight   # 2배

내부적으로 sched_entity의 load.weight로 변환된다. CFS/EEVDF가 알아서 비례 분배를 한다.

10.2 cpu.max — 하드 캡

# "한 주기 동안 최대 50% CPU"
echo "50000 100000" > /sys/fs/cgroup/my-container/cpu.max
# format: <quota> <period>, 단위 us

이는 CFS bandwidth control(CFS BWC)으로 구현된다. 태스크가 quota를 다 쓰면 다음 주기까지 sleep된다.

10.3 throttling의 부작용

CFS BWC는 "throttle" 시 큰 지연을 유발할 수 있다. 멀티스레드 태스크의 경우, 일부 스레드가 quota를 다 쓰면 모두가 throttle된다. 이는 Java, Go 같은 멀티스레드 런타임에서 특히 문제가 된다.

해결책:

quota를 충분히 크게 설정 (단순)
멀티스레드 친화적 quota 분배 (커널 패치, 일부 제공)
코어 핀(cpuset)을 함께 사용 (런타임 라이브러리가 핀을 인식해야 함)

10.4 cpuset — CPU 핀

특정 CPU에만 태스크를 핀시킨다:

echo "0-3" > /sys/fs/cgroup/my-container/cpuset.cpus
echo "0" > /sys/fs/cgroup/my-container/cpuset.mems

NUMA 인지 핀이 가능하다. 데이터베이스 워크로드는 NUMA 노드 단위 핀이 표준이다.

11. 관찰성 — 무엇을 어떻게 보나

11.1 schedstats

/proc/sched_debug는 매 cfs_rq의 상태, 트리 통계, vruntime 등을 보여준다. 디버깅의 출발점.

$ cat /proc/sched_debug
...
cpu#0
  .nr_running                    : 4
  .load                          : 4096
  .nr_switches                   : 12345678
  .nr_load_updates               : 234567
  .min_vruntime                  : 12345678901234.000000
  ...
cfs_rq[0]:/
  .exec_clock                    : 9876543.210
  .min_vruntime                  : 12345678901234.000000
  .nr_running                    : 4
  ...

11.2 perf sched

perf sched record sleep 5
perf sched latency

perf sched는 스케줄러 이벤트를 기록하고 태스크별 평균/최대 지연, wakeup 지연 등을 보여준다. 스케줄러 디버깅의 표준 도구.

11.3 ftrace의 sched 이벤트

echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe

매 컨텍스트 스위치, 매 태스크 wakeup, 매 fork/exit가 기록된다. 매우 자세하고 무거우니 짧게 켰다 끈다.

11.4 bpftrace

# 컨텍스트 스위치 빈도
bpftrace -e 'tracepoint:sched:sched_switch { @[comm] = count(); }'

# wakeup 지연 분포
bpftrace -e '
tracepoint:sched:sched_wakeup { @start[args->pid] = nsecs; }
tracepoint:sched:sched_switch /args->next_pid != 0/ {
    if (@start[args->next_pid]) {
        @lat = hist((nsecs - @start[args->next_pid]) / 1000);
        delete(@start[args->next_pid]);
    }
}'

bpftrace 한 줄로 wakeup 지연 분포를 마이크로초 단위로 볼 수 있다.

12. 실전 튜닝 — 어떤 노브가 있나

12.1 sysctl 노브

/proc/sys/kernel/에서 만질 수 있는 것들:

sched_latency_ns: 기본 6ms, 늘리면 처리량 우선, 줄이면 응답성 우선
sched_min_granularity_ns: 기본 0.75ms, 컨텍스트 스위치 빈도와 직접 연관
sched_wakeup_granularity_ns: 깨어난 태스크가 즉시 선점할지 결정
sched_migration_cost_ns: 태스크 마이그레이션 비용 추정 (캐시 친화성에 영향)
sched_tunable_scaling: 0=고정, 1=로그 스케일, 2=선형 스케일
sched_rt_runtime_us: 실시간 태스크가 한 주기에 받을 수 있는 최대 시간
sched_rt_period_us: 위 값의 주기

EEVDF 도입 후 일부 노브의 의미가 달라졌다. 예를 들어 sched_latency_ns는 이제 "기본 슬라이스의 기준값" 정도이다.

12.2 CPU isolation (`isolcpus`)

부팅 파라미터로 특정 CPU를 일반 스케줄러에서 제외할 수 있다:

isolcpus=4-7 nohz_full=4-7 rcu_nocbs=4-7

isolcpus: 해당 CPU에 일반 태스크를 보내지 않음
nohz_full: 해당 CPU의 타이머 틱을 끔 (HPC, DPDK 워크로드용)
rcu_nocbs: RCU 콜백을 다른 CPU로 떠넘김

이렇게 격리된 CPU에 사용자 공간 코드가 핀하면 거의 모든 커널 잡음에서 벗어날 수 있다. DPDK, HFT(고빈도 거래), 게임 엔진 같은 워크로드의 표준 패턴이다.

12.3 uclamp — 동적 주파수 힌트

SCHED_FLAG_UTIL_CLAMP_MIN/MAX 플래그로 태스크의 utilization 클램프 값을 설정할 수 있다. 이는 CPU 주파수 조절기(cpufreq governor)에 힌트를 준다.

struct sched_attr attr = {
    .sched_flags = SCHED_FLAG_UTIL_CLAMP_MIN,
    .sched_util_min = 512,  // 최소 50% 주파수
};

게임이나 인터랙티브 앱이 "내가 깨어났을 때는 CPU를 풀 스피드로 돌려달라"고 표현하는 방법.

13. sched_ext — BPF로 스케줄러 작성

2024년 Linux 6.12에서 메인라인에 머지된 sched_ext는 사용자 공간이 BPF 프로그램으로 스케줄링 정책을 작성할 수 있게 한다. 게임에서 영감을 받은 기능이다.

13.1 동기

게임용 PC에서는 응답성이 절대적이다. Valve(Steam Deck 제조사)는 자신의 게임 워크로드에 맞춰진 스케줄러가 필요했다. 메인라인 변경은 너무 느리고, 모든 워크로드에 맞아야 했다. BPF로 자기 정책을 끼워 넣는 방법이 자연스러웠다.

13.2 작동 방식

// 사용자 공간 BPF 코드 (개념)
SEC("struct_ops/select_cpu")
s32 BPF_STRUCT_OPS(my_select_cpu, struct task_struct *p, s32 prev_cpu, u64 wake_flags) {
    // 게임 스레드는 큰 코어로
    if (p->tgid == game_tgid) return BIG_CORE;
    // 나머지는 작은 코어로
    return prev_cpu;
}

SEC("struct_ops/enqueue")
void BPF_STRUCT_OPS(my_enqueue, struct task_struct *p, u64 enq_flags) {
    scx_bpf_dispatch(p, SCX_DSQ_GLOBAL, 0, enq_flags);
}

이 BPF 프로그램을 로드하면 커널의 일반 스케줄러 자리에 끼어든다. 잘못 동작하면 안전 모드로 떨어져서 CFS/EEVDF로 폴백한다.

13.3 활용 사례

scx_lavd: 게임 워크로드 우선 스케줄러 (Valve 후원)
scx_rusty: Rust로 작성된 균형형 스케줄러
scx_layered: 워크로드 클래스를 레이어로 나눠 처리

미래에는 데이터베이스나 머신러닝 워크로드용 전용 스케줄러가 BPF로 배포될 수도 있다.

14. ARM big.LITTLE과 EAS

ARM 모바일 SoC는 보통 큰 코어 4개 + 작은 코어 4개 같은 비대칭 구성을 가진다. 큰 코어는 빠르지만 전력을 많이 쓰고, 작은 코어는 느리지만 전력 효율이 좋다.

EAS(Energy Aware Scheduling)는 태스크의 utilization과 코어의 에너지 모델을 보고, "어디서 실행하는 게 가장 적은 에너지를 쓸까"를 계산한다.

// 개념 의사 코드
unsigned long compute_energy(struct task_struct *p, int cpu) {
    unsigned long capacity = arch_scale_cpu_capacity(cpu);
    unsigned long util = task_util_est(p);
    return em_pd_energy(perf_domain_of(cpu), capacity, util);
}

매 wakeup마다 후보 CPU들의 에너지 비용을 계산하고 가장 작은 것을 선택한다. 이 모델은 안드로이드 폰의 배터리 수명에 직접적인 영향을 준다.

15. 데드라인 워크로드 — 산업 자동화 사례

Bosch, Siemens 같은 산업 자동화 업체들은 PLC를 Linux + PREEMPT_RT + SCHED_DEADLINE으로 대체하고 있다. 시나리오:

1ms 주기의 모터 제어 루프
100us 안에 깨어나서 처리해야 함
미스 한 번이면 부품이 부서질 수 있음

이런 경우 SCHED_DEADLINE으로:

runtime: 0.5ms
deadline: 0.8ms
period: 1ms

어드미션 컨트롤이 시스템 전체의 실시간 약속을 검증한다. 보장 못 할 시스템에는 태스크를 만들 수 없다.

이는 Linux가 이제 "실시간 운영체제(RTOS) 시장"에서도 진지한 선택지라는 의미이다. VxWorks, QNX 같은 전통 RTOS의 점유율을 잠식하고 있다.

16. 안티패턴과 흔한 함정

16.1 SCHED_FIFO + sleep 없는 루프 = 시스템 행

SCHED_FIFO 태스크가 무한 루프를 돌면 같은 CPU의 모든 일반 태스크가 굶주린다. RLIMIT_RTTIME이 보호하지만, 그 전까지는 시스템이 응답하지 않는다.

대안: 항상 nanosleep으로 양보하거나, SCHED_DEADLINE 사용.

16.2 멀티스레드 컨테이너 + cpu.max = throttling 폭탄

위에서 본 CFS BWC throttling. 4코어 전체를 다 쓸 수 있는 quota라도, 짧은 burst가 quota를 넘기면 throttle. JVM/Go의 GC pause 폭증의 흔한 원인이다.

대안:

quota를 풍부히
bandwidth control 끄기 (echo max > cpu.max)
cpuset으로 명시적 핀

16.3 너무 작은 sched_min_granularity

이 값을 0.1ms로 만들면 컨텍스트 스위치 비용이 폭발한다. 캐시 미스로 처리량이 절반이 될 수 있다.

16.4 isolcpus와 nohz_full을 잘못 조합

nohz_full이 효과를 보려면 isolcpus와 rcu_nocbs도 같이 설정해야 한다. 셋 중 하나만 빠지면 이상한 잡음이 들어온다.

16.5 nice 값에 너무 의존

nice는 비율적 배분이지 절대 보장이 아니다. nice -20 태스크라도 시스템이 100% 바쁘면 굶주릴 수 있다. 진짜 보장이 필요하면 SCHED_FIFO나 SCHED_DEADLINE.

17. 비교 — 다른 OS와의 차이

17.1 Windows 스케줄러

Windows는 32단계의 우선순위 + Quantum 기반 라운드로빈. 인터랙티브성을 위해 GUI 포커스 윈도우의 스레드에 부스트를 준다. 진짜 실시간은 별도의 driver level에서 처리.

차이점: 비례 공정성(CFS/EEVDF) 모델이 아니다. 절대 우선순위 모델. 우선순위 인버전 회피 메커니즘은 비슷하다.

17.2 macOS XNU

XNU는 4개의 우선순위 밴드 + 각각의 라운드로빈. QoS(Quality of Service) 클래스로 태스크가 자기를 분류 (UserInteractive, UserInitiated, Default, Utility, Background). GCD가 이 위에 얹혀 있다.

특이점: 인터랙티브성을 운영체제가 추정하지 않고, 사용자 공간이 명시적으로 선언한다. iOS의 미친 응답성의 일부가 여기에서 나온다.

17.3 BSD 스케줄러

FreeBSD는 ULE라는 스케줄러를 쓴다. CFS와 비슷하게 비례 공정성 + 인터랙티브성 휴리스틱. SMP 친화적. NetBSD/OpenBSD는 더 단순한 모델.

17.4 어떻게 다른가

기준	Linux CFS/EEVDF	Windows	macOS XNU	FreeBSD ULE
모델	비례 공정성 + 데드라인 (EEVDF)	절대 우선순위 + 부스트	QoS 밴드	비례 공정성
인터랙티브성	모델 (EEVDF) / 휴리스틱 (CFS)	부스트	명시적 선언	휴리스틱
실시간	SCHED_FIFO/RR/DEADLINE + PREEMPT_RT	기본은 약함	별도 카테고리	SCHED_FIFO
BPF 확장	sched_ext (6.12+)	없음	없음	없음
그룹 (cgroups)	CFS BWC	작업 객체	App Sandbox	RCTL

18. 결론 — 스케줄러는 끝나지 않는다

Linux 스케줄러는 30년 동안 여러 번 다시 쓰였고, 앞으로도 계속 다시 쓰일 것이다. 워크로드는 계속 변하고, 하드웨어도 계속 변한다. 어제의 정답이 오늘의 오답이 된다.

EEVDF는 현재의 답이지만 영원하지 않을 것이다. ARM big.LITTLE 같은 비대칭 시스템, NUMA가 더 깊어지는 멀티 소켓 시스템, AI 워크로드의 GPU/NPU 통합, 메모리 계층의 지속적 변화 — 이 모든 것이 다음 세대 스케줄러의 문제 영역이다.

sched_ext가 "정답을 정해두지 말고, 사용자가 자기 워크로드에 맞게 만들어라"는 답이라면, EEVDF는 "기본은 이걸로 하되 슬라이스로 응답성을 표현하라"는 답이다. 두 접근이 공존하면서 Linux 스케줄러의 미래를 만들어 갈 것이다.

이 글을 다 읽었다면, 적어도 이런 질문에 답할 수 있을 것이다:

vruntime이 무엇이고 왜 그렇게 정의되었나?
CFS는 어떻게 공정성을 푸는가?
EEVDF는 CFS와 무엇이 다른가?
nice 값과 latency-nice의 차이는?
cgroups CPU controller가 어떻게 동작하나?
SCHED_DEADLINE은 언제 쓰는가?
PREEMPT_RT의 의미는?
sched_ext가 왜 도입되었는가?

다음 글에서는 Linux 메모리 관리 또는 Linux Block Layer를 다룰 예정이다. 부팅 → 스케줄러 → I/O → 메모리 → 블록 — 이렇게 다섯 글이 모이면 Linux 커널의 "프로세스 생애주기 관점"이 거의 완성된다.

부록 A — 참고 자료

Linux Kernel Documentation: Scheduler — 공식 커널 문서.
Stoica, Abdel-Wahab, Plaxton (1995): "Earliest Eligible Virtual Deadline First" — EEVDF 원논문.
LWN: An EEVDF CPU scheduler for Linux (Jonathan Corbet, 2023) — EEVDF 도입 분석.
LWN: A new approach to deadline scheduling (Jake Edge) — SCHED_DEADLINE 도입 글.
Ingo Molnar의 CFS 발표 (2007) — CFS 첫 발표.
Ulrich Drepper, "What Every Programmer Should Know About Memory" (2007) — 캐시와 NUMA 이해.
Frank Mayer 외, "Selinux by Example" — 권한과 스케줄링 상호작용.
sched_ext 공식 GitHub — BPF 스케줄러 예제 모음.

부록 B — 자주 묻는 질문

Q: nice 값은 어디까지 효과가 있나? A: 다른 동시 태스크와 비교해서만 의미가 있다. 시스템에 혼자 돌고 있으면 nice는 무의미하다.

Q: CFS와 EEVDF, 어떤 코드를 봐야 하나? A: 6.6 이전이면 CFS, 6.6 이후면 EEVDF. 단, 파일 이름은 둘 다 kernel/sched/fair.c. git blame과 changelog를 보는 것이 가장 정확하다.

Q: 게임 성능을 올리려면 어떤 스케줄러 설정이 좋나? A: 6.6+ 커널 + EEVDF + 게임 프로세스에 latency-nice 낮게 설정. 6.12+면 sched_ext의 scx_lavd도 시도해볼 만하다.

Q: 데이터베이스 워크로드는? A: 메모리 NUMA 핀 (cpuset.mems) + cpuset.cpus. CFS BWC throttling은 가급적 피하기. SCHED_BATCH도 도움이 된다.

Q: 컨테이너에서 throttling이 자꾸 일어난다. A: cpu.max를 충분히 풀어두거나 (또는 max), 가능하면 cpuset 핀으로 대체. JVM/Go 런타임은 GOMAXPROCS나 -XX:ActiveProcessorCount를 설정하라.

Q: PREEMPT_RT는 일반 데스크탑에 권장되나? A: 보통 아니다. 처리량이 떨어진다. 음악 워크스테이션이나 산업 제어 같은 진짜 실시간 워크로드에만.

Q: sched_ext는 안정적인가? A: 메인라인 머지가 6.12 (2024년 11월)이라 아직 신규다. Steam Deck처럼 잘 정의된 워크로드에는 좋지만, 일반 서버에 권장하기는 이르다.

Q: SCHED_DEADLINE을 쓰면 무엇이 좋은가? A: 어드미션 제어가 가장 큰 차이. 약속을 시스템이 검증해주고, 못 지킬 시스템에는 태스크 생성을 거부한다. 진짜 데드라인 보장이 필요한 경우에만.

부록 C — 미니 용어집

CFS: Completely Fair Scheduler. 2007-2023의 Linux 기본 스케줄러.
EEVDF: Earliest Eligible Virtual Deadline First. 2023+의 Linux 기본 스케줄러.
vruntime: virtual runtime. 가중치로 정규화된 실행 시간.
lag: 받았어야 할 양과 실제 받은 양의 차이.
slice: 한 태스크가 한 번에 받는 CPU 시간.
deadline: EEVDF의 가상 마감 시간.
sched_entity: 스케줄링 단위 (태스크 또는 그룹).
cfs_rq: CFS run queue. CPU별, cgroup별로 존재.
task_group: 같은 cgroup의 태스크들을 묶는 단위.
sched_domain: CPU 토폴로지를 표현하는 계층 구조.
NUMA: Non-Uniform Memory Access.
PREEMPT_RT: 실시간 패치 셋. 6.12에서 부분 메인라인.
CBS: Constant Bandwidth Server. SCHED_DEADLINE의 내부 알고리즘.
EAS: Energy Aware Scheduling. ARM big.LITTLE용.
uclamp: utilization clamp. 주파수 조절기에 주는 힌트.
sched_ext: BPF 기반 사용자 정의 스케줄러 인터페이스.
schedstats: 스케줄러 통계 (/proc/sched_debug).
CFS BWC: CFS Bandwidth Control. cgroups의 cpu.max 구현.

이 글이 시리즈의 세 번째이다. 첫 글 Linux 부팅 과정 딥다이브, 두 번째 글 io_uring 완벽 가이드와 함께 읽으면 Linux 커널의 핵심 경로 — 부팅, 스케줄링, I/O — 의 풍경 전체를 볼 수 있을 것이다. 다음에 다룰 메모리 관리와 블록 레이어가 이 시리즈를 완성할 것이다.

들어가며 — 스케줄러는 OS의 심장이다

1. 스케줄러의 기본 — 왜 어려운가

1.1 무엇을 결정해야 하나

1.2 좋은 스케줄러의 조건

2. 역사적 배경 — Linux 스케줄러의 진화

2.1 Linux 1.x — 진짜 단순한 라운드로빈

2.2 Linux 2.4 — 여전히 O(N), 더 정교해짐

2.3 Linux 2.6.0 — Ingo Molnar의 O(1) 스케줄러

2.4 Con Kolivas의 RSDL/SD — 외부의 도전

2.5 2007 — CFS의 등장

2.6 2023 — EEVDF로 교체

3. CFS의 핵심 개념

3.1 "완전히 공정한"의 의미

3.2 vruntime — 정규화된 실행 시간

3.3 nice → weight 변환 표

3.4 sched_entity와 task_group

3.5 cfs_rq — CPU별 실행 큐

4. CFS 알고리즘 — pick_next_task와 task_tick

4.1 다음 태스크 고르기

4.2 매 틱마다 일어나는 일

4.3 sched_period와 sched_min_granularity

4.4 깨어난 태스크의 vruntime — place_entity

5. CFS의 한계 — 왜 EEVDF로 옮겼나

5.1 지연 보장 부족

5.2 인터랙티브 휴리스틱

5.3 latency-nice 패치의 시도

5.4 EEVDF 논문의 재발견

6. EEVDF — Earliest Eligible Virtual Deadline First

6.1 핵심 아이디어 셋

6.2 Lag — 빚과 저축

6.3 Eligible Time

6.4 Virtual Deadline

6.5 EEVDF의 선택 함수

6.6 슬라이스가 응답성을 표현한다

7. 멀티코어 — sched domain과 로드 밸런싱

7.1 CPU별 큐

7.2 sched_domain 계층 구조

7.3 Periodic Load Balancing

7.4 Newly Idle Balancing

7.5 NUMA Balancing — AutoNUMA

7.6 CPU Capacity와 Big.LITTLE

8. 다른 스케줄링 클래스 — Linux는 단일 스케줄러가 아니다

8.1 SCHED_FIFO와 SCHED_RR (Real-Time)

8.2 SCHED_DEADLINE (CBS)

8.3 SCHED_IDLE과 SCHED_BATCH

8.4 우선순위 매트릭스

9. PREEMPT_RT — 진짜 실시간 Linux

10. cgroups CPU controller — 컨테이너의 스케줄링

10.1 cpu.weight (cgroup v2)

10.2 cpu.max — 하드 캡

10.3 throttling의 부작용

10.4 cpuset — CPU 핀

11. 관찰성 — 무엇을 어떻게 보나

11.1 schedstats

11.2 perf sched

11.3 ftrace의 sched 이벤트

11.4 bpftrace

12. 실전 튜닝 — 어떤 노브가 있나

12.1 sysctl 노브

12.2 CPU isolation (isolcpus)

12.3 uclamp — 동적 주파수 힌트

13. sched_ext — BPF로 스케줄러 작성

13.1 동기

13.2 작동 방식

13.3 활용 사례

14. ARM big.LITTLE과 EAS

15. 데드라인 워크로드 — 산업 자동화 사례

16. 안티패턴과 흔한 함정

16.1 SCHED_FIFO + sleep 없는 루프 = 시스템 행

16.2 멀티스레드 컨테이너 + cpu.max = throttling 폭탄

16.3 너무 작은 sched_min_granularity

16.4 isolcpus와 nohz_full을 잘못 조합

16.5 nice 값에 너무 의존

17. 비교 — 다른 OS와의 차이

17.1 Windows 스케줄러

17.2 macOS XNU

17.3 BSD 스케줄러

17.4 어떻게 다른가

18. 결론 — 스케줄러는 끝나지 않는다

부록 A — 참고 자료

12.2 CPU isolation (`isolcpus`)