CFS 스케줄러(Scheduler) 상세

Linux 커널의 CFS(Completely Fair Scheduler)를 vruntime 수식과 실행 큐(Runqueue) 동작 기준으로 심층 분석합니다. nice 가중치 기반 시간 분배, Red-Black Tree 스케줄링, wakeup preemption, PELT 부하 추적, cgroup 대역폭(Bandwidth) 제한, EEVDF와의 연계 변화, 성능 관측 지표와 튜닝 전략까지 실무 관점에서 다룹니다.

개요

CFS(Completely Fair Scheduler)는 2007년 Linux 2.6.23에서 기존 O(1) 스케줄러를 대체하며 도입된 프로세스(Process) 스케줄러입니다.

스케줄링이 필요한 이유

현대 OS는 수십~수백 개의 프로세스가 동시에 실행 대기 중인 환경에서 물리 CPU 코어는 소수에 불과합니다. 스케줄러(Scheduler)가 없다면 한 프로세스가 CPU를 독점하여 다른 프로세스들이 영원히 실행되지 못하는 기아(Starvation) 현상이 발생합니다. 과거 O(1) 스케줄러는 "대화형 태스크인지 판단하는 휴리스틱(Heuristic)"이 복잡하고 오류가 많아 공정성을 보장하지 못했습니다. CFS는 이를 해결하기 위해 모든 프로세스에게 이상적인 멀티태스킹(Multitasking)을 수학적으로 보장하는 구조를 도입하였습니다.

프로세스 상태와 스케줄러 역할

스케줄러는 아래 세 가지 상태 사이에서 태스크를 전환합니다. CFS가 실질적으로 관리하는 대상은 Runnable(실행 대기) 상태의 태스크들입니다.

CPU 런큐(Runqueue) 기본 개념

각 CPU 코어는 자신만의 런큐(Runqueue, struct rq)를 가집니다. 런큐는 현재 그 CPU에서 실행되기를 기다리는 태스크들의 집합입니다. CFS는 이 런큐 안에서 cfs_rq라는 별도 자료구조로 자신이 관리하는 태스크들을 Red-Black Tree에 정렬하여 유지합니다.

핵심 원칙

• 완전한 공정성(Fairness): 모든 프로세스가 CPU 시간을 공정하게 분배받음
• 가상 런타임(vruntime): 실제 실행 시간을 우선순위(Priority)로 가중 계산
• Red-Black Tree: O(log N) 시간 복잡도로 다음 태스크(Task) 선택
• 동적 타임슬라이스(Time Slice): 실행 가능한 프로세스 수에 따라 자동 조정

O(1) 스케줄러와의 차이

CFS 개발 역사

CFS는 2007년 Ingo Molnár가 리눅스 커널 2.6.23에 처음 도입한 이후 꾸준히 발전해 왔습니다. 아래 타임라인은 주요 이정표를 정리한 것입니다.

가상 런타임 (vruntime)

vruntime은 CFS의 핵심 메트릭으로, 실제 실행 시간을 nice 값(우선순위)으로 가중한 값입니다.

vruntime이 없다면 어떤 문제가 생기는가

단순히 "실제 실행 시간이 가장 짧은 태스크에게 CPU를 준다"면 어떻게 될까요? nice -20(고우선순위) 태스크와 nice +19(저우선순위) 태스크가 경쟁할 때, 두 태스크에게 같은 실제 시간을 주면 고우선순위 설정 자체가 무의미해집니다. 반대로 "우선순위에 따라 고정 시간 비율"을 주면 nice +19 태스크는 수십 배의 대기 후에야 CPU를 받게 되어 응답성이 극도로 저하됩니다.

vruntime은 이 문제를 "모든 태스크의 가상 시계를 같은 속도로 맞추는" 방식으로 해결합니다. nice 가중치가 높을수록 vruntime이 천천히 증가하므로, vruntime 최솟값을 고르면 자동으로 고우선순위 태스크가 더 자주 선택됩니다.

vruntime 계산

vruntime 갱신의 핵심 식은 버전과 무관하게 동일합니다: vruntime += calc_delta_fair(delta_exec, se). 아래 첫 번째 블록은 CFS(Linux 6.5 이하) 형태이고, 6.6 이후의 실제 구현은 update_curr() (v7.3.1)에서 다룹니다.

/* kernel/sched/fair.c — Linux 6.5 이하 */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;

    delta_exec = now - curr->exec_start;
    curr->exec_start = now;

    /* 실제 실행 시간을 우선순위로 가중 */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

/* vruntime = 실제시간 * (NICE_0_LOAD / 현재_weight) */
static u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

Nice 값과 Weight 테이블

/* kernel/sched/fair.c — Linux v7.3.1 */
#define vruntime_cmp(A, CMP_STR, B) ({             \
    int __res = 0;                              \
                                                    \
    if (!__builtin_strcmp(CMP_STR, "<")) {        \
        __res = ((s64)((A)-(B)) < 0);          \
    } else if (!__builtin_strcmp(CMP_STR, "<=")) {   \
        __res = ((s64)((A)-(B)) <= 0);         \
    } else if (!__builtin_strcmp(CMP_STR, ">")) {    \
        __res = ((s64)((A)-(B)) > 0);          \
    } else if (!__builtin_strcmp(CMP_STR, ">=")) {   \
        __res = ((s64)((A)-(B)) >= 0);         \
    } else {                                     \
        /* 알 수 없는 연산자는 링커 에러 */          \
        __BUILD_BUG_vruntime_cmp();              \
    }                                               \
                                                    \
    __res;                                          \
})

static inline bool entity_before(const struct sched_entity *a,
                                 const struct sched_entity *b)
{
    return vruntime_cmp(a->deadline, "<", b->deadline);
}

Red-Black Tree 구조

CFS는 각 CPU의 실행 큐(runqueue)에서 가상 시각을 키로 하는 Red-Black Tree를 관리합니다. 정렬 키는 CFS(6.5 이하)에서 vruntime, EEVDF(6.6 이상)에서 deadline입니다. 아래 설명은 이해를 돕기 위해 CFS 기준으로 서술하고, EEVDF와 다른 지점은 따로 표시합니다.

왜 Red-Black Tree인가

CFS가 매 스케줄링 사이클마다 수행하는 핵심 연산은 세 가지입니다: ① 다음 실행 태스크 선택(최솟값 조회), ② 태스크 인큐(삽입), ③ 태스크 디큐(삭제). 이 세 연산을 동시에 효율적으로 처리하려면 자료구조 선택이 중요합니다.

Red-Black Tree는 자가 균형(Self-balancing) 이진 탐색 트리(BST)로, 어떤 삽입·삭제 순서에도 트리 높이가 O(log N)을 넘지 않도록 회전(Rotation)과 색 변경으로 균형을 유지합니다. 트리 높이가 일정하므로 태스크 수가 수백 개로 늘어도 스케줄링 오버헤드(Overhead)가 예측 가능합니다.

sched_entity 구조체(Struct)

아래는 Linux v7.3.1의 실제 정의입니다. struct sched_entity는 CFS 시절과 마찬가지로 include/linux/sched.h에 그대로 남아 있고(태스크 구조체가 직접 포함), EEVDF 도입으로 deadline/vlag/vprot/slice 계열 필드가 추가되었습니다. 스케줄러 내부 전용 구조체인 struct cfs_rq는 kernel/sched/sched.h에 있습니다.

/* include/linux/sched.h — Linux v7.3.1 */
struct sched_entity {
    /* 부하 분산용 */
    struct load_weight  load;        /* nice 기반 가중치 */
    struct load_weight  h_load;      /* 계층 합산 가중치 */
    struct rb_node      run_node;    /* RB-tree 노드 (키: deadline) */

    u64 deadline;                     /* 가상 마감 시각 (EEVDF) */
    u64 min_vruntime;                  /* 서브트리 최소 vruntime (증강 필드) */
    u64 min_slice;                     /* 서브트리 최소 slice (증강 필드) */
    u64 max_slice;

    struct list_head    group_node;
    unsigned char       on_rq;
    unsigned char       sched_delayed;   /* 지연 디큐 상태 */
    unsigned char       rel_deadline;
    unsigned char       custom_slice;    /* sched_runtime 지정 여부 */

    u64 exec_start;                    /* 마지막 회계 시작 시각 */
    u64 sum_exec_runtime;              /* 누적 실행 시간 */
    u64 prev_sum_exec_runtime;
    u64 vruntime;                      /* 가상 런타임 */

    s64 vlag;                          /* 근사 가상 지연 (EEVDF 적격성) */
    u64 vprot;                         /* 슬라이스 보호 상한 */
    u64 slice;                         /* 이번 요청 크기 */

    u64 nr_migrations;

#ifdef CONFIG_FAIR_GROUP_SCHED
    int depth;
    struct sched_entity *parent;      /* 상위 그룹 */
    struct cfs_rq       *cfs_rq;      /* 소속 런큐 */
    struct cfs_rq       *my_q;        /* 그룹이 소유한 자식 런큐 */
    unsigned long        runnable_weight;
#endif

    struct sched_avg     avg;          /* PELT 부하 추적 (별도 캐시라인) */
};

트리 구조 시각화

다음 태스크 선택 (pick_next_task)

스케줄러의 핵심 동작은 다음에 실행할 태스크를 고르는 것입니다. CFS(6.5 이하)는 vruntime이 가장 작은 태스크를, EEVDF(6.6 이상)는 적격한 태스크 중 가상 마감(deadline)이 가장 이른 태스크를 선택합니다.

pick_next_entity와 pick_eevdf (Linux 6.6+)

Linux 6.5 이하 CFS에서 pick_next_entity(cfs_rq, curr)는 RB-tree의 leftmost 엔티티를 기본 후보로 삼은 뒤 cfs_rq->skip, next, last 세 가지 buddy 힌트를 차례로 검사하여 최종 후보를 보정했습니다. Linux 6.6에서 EEVDF가 병합되면서 buddy 힌트는 제거되었고, 현재 안정 커널(v7.3.1)에서는 pick_eevdf()가 적격성(Eligibility)과 가상 마감 시각(Virtual Deadline) 두 기준으로 후보를 고릅니다. 아래 코드는 v7.3.1 소스 그대로입니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static struct sched_entity *
pick_next_entity(struct rq *rq, bool protect)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    se = pick_eevdf(cfs_rq, protect);
    if (se->sched_delayed) {
        __dequeue_task(rq, task_of(se), DEQUEUE_SLEEP | DEQUEUE_DELAYED);
        /* Must not reference @se again, see __block_task(). */
        return NULL;
    }

    return se;
}

pick_eevdf() — 적격성 검사와 트리 탐색

RB-tree는 deadline을 키로 정렬되지만, EEVDF가 골라야 하는 것은 "마감이 가장 이른 태스크"가 아니라 "이미 받아야 할 서비스를 받지 못한(적격한) 태스크 중 마감이 가장 이른 태스크"입니다. 그래서 각 노드는 서브트리의 최소 min_vruntime과 최소 min_slice를 증강 필드로 유지하고, 적격 엔티티가 존재할 수 없는 서브트리는 통째로 건너뜁니다. 이 구조 덕분에 탐색은 여전히 O(log N)입니다.

static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq, bool protect)
{
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    struct sched_entity *curr = cfs_rq->curr;
    struct sched_entity *best = NULL;

    /* 엔티티가 하나뿐이면 적격성 검사를 생략 */
    if (cfs_rq->h_nr_queued == 1)
        return curr && curr->on_rq ? curr : se;

    /* ->next buddy 는 지연시간에만 영향을 주고 공정성은 해치지 않음 */
    if (sched_feat(PICK_BUDDY) && protect &&
        cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next)) {
        WARN_ON_ONCE(cfs_rq->next->sched_delayed);
        return cfs_rq->next;
    }

    if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
        curr = NULL;

    if (curr && protect && protect_slice(curr))
        return curr;

    /* leftmost 엔티티가 적격이면 즉시 확정 */
    if (se && entity_eligible(cfs_rq, se)) {
        best = se;
        goto found;
    }

    /* 적격 엔티티를 찾는 트리 탐색 */
    while (node) {
        struct rb_node *left = node->rb_left;

        /* 좌측 서브트리에 적격 엔티티가 있으면 항상 더 좋은 후보 */
        if (left && vruntime_eligible(cfs_rq,
                    __node_2_se(left)->min_vruntime)) {
            node = left;
            continue;
        }

        se = __node_2_se(node);

        /* 좌측에 적격자가 없으므로 현재 노드를 검사 */
        if (entity_eligible(cfs_rq, se)) {
            best = se;
            break;
        }

        node = node->rb_right;
    }
found:
    if (!best || (curr && entity_before(curr, best)))
        best = curr;

    return best;
}

적격성 판정의 수학

적격성은 "가중치 기반 지연(lag)이 0 이상인가"로 정의됩니다. 태스크 i의 지연은 lag_i = w_i * (V - v_i)이며(V는 런큐 평균 가중 vruntime, v_i는 태스크의 vruntime), lag_i >= 0이면 적격입니다. 구현은 나눗셈으로 인한 정밀도 손실을 피하기 위해 부등식을 양변에 sum_weight를 곱한 형태로 바꿔 정수 비교만 수행합니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 key, avg = cfs_rq->sum_w_vruntime;
    long load = cfs_rq->sum_weight;

    if (curr && curr->on_rq) {
        unsigned long weight = avg_vruntime_weight(cfs_rq, curr->h_load.weight);

        avg += entity_key(cfs_rq, curr) * weight;
        load += weight;
    }

    key = vruntime_op(vruntime, "-", cfs_rq->zero_vruntime);

    return avg >= (__int128)key * load;
}

int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    return vruntime_eligible(cfs_rq, se->vruntime);
}

스케줄링 흐름

schedule()
  └─ __schedule()
       ├─ pick_next_task()
       │    └─ pick_next_task_fair()  /* CFS */
       │         └─ pick_next_entity()
       │              └─ __pick_first_entity()  /* leftmost */
       └─ context_switch()

타임슬라이스와 지연시간

CFS는 고정 타임슬라이스 대신 동적으로 계산된 시간 할당을 사용합니다.

핵심 파라미터 (CFS, Linux 6.5 이하)

아래 세 파라미터는 CFS 시절 /proc/sys/kernel/ 아래에 노출되던 값입니다. 현재 커널에서는 모두 사라졌으므로, 구버전 시스템을 분석하거나 옛 문서를 읽을 때만 참고해야 합니다.

타임슬라이스 계산 (CFS, Linux 6.5 이하)

/* kernel/sched/fair.c — Linux 6.5 이하 (레거시 CFS) */
static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running);

    /* 프로세스의 가중치 비율로 분배 */
    slice *= se->load.weight;
    do_div(slice, cfs_rq->load.weight);

    return slice;
}

/* 실행 가능한 프로세스 수에 따라 period 조정 */
static u64 __sched_period(unsigned long nr_running)
{
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

예제 계산

타임슬라이스 계산 시뮬레이션 (코드)

/* CFS 타임슬라이스 계산 시뮬레이터 */
#include <stdio.h>

/* 커널 기본 값 */
#define SCHED_LATENCY_NS  6000000    /* 6ms */
#define MIN_GRANULARITY_NS 750000   /* 0.75ms */
#define NICE_0_LOAD        1024

/* Nice 값 → Weight 변환 테이블 (일부) */
const unsigned long sched_prio_to_weight[] = {
    88761,  /* nice -20 */
    71755, 56483, 46273, 36291,
    29154, 23254, 18705, 14949, 11916,  /* -10 */
    9548, 7620, 6100, 4904, 3906,
    3121, 2501, 1991, 1586, 1277,
    1024,   /* nice 0 (기준) */
    820, 655, 526, 423,
    335, 272, 215, 172, 137,
    110, 87, 70, 56, 45,
    36, 29, 23, 18, 15,  /* nice +19 */
};

/* 타임슬라이스 계산 */
void calculate_timeslice(int *nice_values, int nr_tasks)
{
    unsigned long total_weight = 0;
    unsigned long period;
    int i;

    /* 1. 총 가중치 계산 */
    for (i = 0; i < nr_tasks; i++) {
        int nice = nice_values[i];
        total_weight += sched_prio_to_weight[nice + 20]; /* nice -20 ~ +19 → 인덱스 0~39 */
    }

    /* 2. Period 결정 (nr_latency 고려) */
    int nr_latency = SCHED_LATENCY_NS / MIN_GRANULARITY_NS; /* 8 */
    if (nr_tasks > nr_latency)
        period = nr_tasks * MIN_GRANULARITY_NS; /* 태스크 많으면 확장 */
    else
        period = SCHED_LATENCY_NS;

    printf("\n=== CFS 타임슬라이스 시뮬레이션 ===\n");
    printf("프로세스 수: %d, Period: %lu ns (%.2f ms)\n",
           nr_tasks, period, period / 1000000.0);
    printf("총 가중치: %lu\n\n", total_weight);

    /* 3. 각 태스크의 타임슬라이스 계산 */
    for (i = 0; i < nr_tasks; i++) {
        int nice = nice_values[i];
        unsigned long weight = sched_prio_to_weight[nice + 20];
        unsigned long slice_ns = (period * weight) / total_weight;

        printf("Task %d: nice=%d, weight=%lu, 타임슬라이스=%lu ns (%.2f ms)\n",
               i, nice, weight, slice_ns, slice_ns / 1000000.0);
        printf("        → Period 대비 %.1f%% 할당\n\n",
               (double)slice_ns * 100 / period);
    }
}

int main(void)
{
    /* 시나리오 1: 모두 nice 0 */
    int scenario1[] = {0, 0, 0, 0};
    calculate_timeslice(scenario1, 4);

    /* 시나리오 2: nice -10, 0, 0, 0 (우선순위 혼재) */
    int scenario2[] = {-10, 0, 0, 0};
    calculate_timeslice(scenario2, 4);

    /* 시나리오 3: 극단적 차이 (nice -20, +19) */
    int scenario3[] = {-20, 19};
    calculate_timeslice(scenario3, 2);

    return 0;
}

/* 출력 예시:
 *
 * === CFS 타임슬라이스 시뮬레이션 ===
 * 프로세스 수: 4, Period: 6000000 ns (6.00 ms)
 * 총 가중치: 4096
 *
 * Task 0: nice=0, weight=1024, 타임슬라이스=1500000 ns (1.50 ms)
 *         → Period 대비 25.0% 할당
 *
 * Task 1: nice=0, weight=1024, 타임슬라이스=1500000 ns (1.50 ms)
 *         → Period 대비 25.0% 할당
 * ...
 *
 * === 시나리오 2 ===
 * Task 0: nice=-10, weight=9548, 타임슬라이스=4539810 ns (4.54 ms)
 *         → Period 대비 75.7% 할당 ← 높은 우선순위!
 *
 * Task 1: nice=0, weight=1024, 타임슬라이스=486730 ns (0.49 ms)
 *         → Period 대비 8.1% 할당
 */

Linux 6.6+ EEVDF의 타임슬라이스

EEVDF는 "전체 주기를 태스크 수로 나누는" CFS의 계산을 버리고, 태스크마다 요청 크기(request size) r_i를 부여합니다. 태스크는 r_i만큼 실행할 권리를 갖고, 그 권리를 다 쓰면 가상 마감 시각이 갱신됩니다. 가상 시간의 기울기는 여전히 nice 가중치 w_i가 결정하므로, nice의 의미(가중치 비율)는 그대로 유지됩니다.

update_deadline() — 슬라이스 소진과 마감 갱신

EEVDF에서 "슬라이스를 다 썼는가"는 현재 vruntime이 마감을 넘었는가로 판정합니다. 넘었다면 슬라이스를 기본값으로 재설정하고 새 마감을 계산합니다. 아래는 v7.3.1의 실제 구현입니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static bool update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if (vruntime_cmp(se->vruntime, "<", se->deadline))
        return false;

    /* 요청 크기는 base_slice, 커스텀 슬라이스면 그대로 유지 */
    if (!se->custom_slice)
        se->slice = sysctl_sched_base_slice;

    /* EEVDF: vd_i = ve_i + r_i / w_i */
    se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
    avg_vruntime(cfs_rq);

    return true;
}

update_curr() — 틱마다 호출되는 vruntime 갱신

/* kernel/sched/fair.c — Linux v7.3.1 */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->h_curr;
    struct rq *rq = rq_of(cfs_rq);
    s64 delta_exec;
    bool resched;

    if (unlikely(!curr))
        return;

    delta_exec = update_se(rq, curr);
    if (unlikely(delta_exec <= 0))
        return;

    account_cfs_rq_runtime(cfs_rq, delta_exec);

    if (!entity_is_task(curr))
        return;

    cfs_rq = &rq->cfs;

    curr->vruntime += calc_delta_fair(delta_exec, curr);
    resched = update_deadline(cfs_rq, curr);

    /* 공정 서버(fair_server) 회계 */
    dl_server_update(&rq->fair_server, delta_exec);

    if (cfs_rq->h_nr_queued == 1)
        return;

    if (resched || !protect_slice(curr)) {
        resched_curr_lazy(rq);
        clear_buddies(cfs_rq, curr);
    }
}

슬라이스 보호(vprot) — 잦은 스위치 방지

EEVDF는 "적격하고 마감이 이른 태스크"를 고르지만, 매번 컨텍스트 스위치를 하면 오버헤드가 커집니다. 그래서 현재 엔티티에 vprot(virtual protection)까지의 실행 권한을 부여하고, 그 구간에서는 다른 후보가 나타나도 계속 실행합니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static inline void set_protect_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = normalized_sysctl_sched_base_slice;
    u64 vprot = se->deadline;

    if (sched_feat(RUN_TO_PARITY))
        slice = cfs_rq_min_slice(cfs_rq);

    slice = min(slice, se->slice);

    /* 더 짧은 슬라이스를 가진 엔티티가 있으면 보호 구간을 줄임 */
    if (slice != se->slice) {
        if (sched_feat(PREEMPT_SHORT))
            vprot = min_vruntime(vprot, ineligible_vruntime(cfs_rq));
        else
            vprot = min_vruntime(vprot, se->vruntime + calc_delta_fair(slice, se));
    }

    se->vprot = vprot;
}

static inline bool protect_slice(struct sched_entity *se)
{
    return vruntime_cmp(se->vruntime, "<", se->vprot);
}

base_slice 관측과 조정

v7.3.1에서 sysctl_sched_base_slice의 기본값은 700us(700000ULL)입니다. 6.14까지는 750us였고 6.15에서 700us로 낮아졌습니다. 이 값은 CONFIG_SCHED_DEBUG가 켜진 커널에서 debugfs로 노출됩니다.

# 현재 값 확인 (root, CONFIG_SCHED_DEBUG)
cat /sys/kernel/debug/sched/base_slice_ns

# 1ms로 조정 (지연에 민감한 워크로드)
echo 1000000 > /sys/kernel/debug/sched/base_slice_ns

# 태스크 단위로 슬라이스 직접 지정 (sched_runtime, us)
chrt -d --sched-runtime 2000000 --sched-period 10000000 --sched-deadline 10000000 0 ./workload

부하 분산 (Load Balancing)

멀티코어 시스템에서 CFS는 CPU 간 태스크를 균등하게 분배합니다.

부하 분산 트리거

• Periodic balancing: 주기적 타이머 (1-100ms 간격)
• Idle balancing: CPU가 유휴 상태(Idle State)로 전환될 때
• Fork balancing: 새 태스크 생성 시 (wake_up_new_task)
• Exec balancing: execve() 호출 시

sched_balance_rq() 핵심 로직 (Linux 6.10+)

CPU 간 부하를 맞추는 본체 함수는 Linux 6.9까지 load_balance()라는 이름이었고, Linux 6.10에서 sched_balance_rq()로 개명되었습니다. 같은 시기 find_busiest_queue()는 sched_balance_find_src_rq(), newidle_balance()는 sched_balance_newidle()로 함께 이름이 바뀌었습니다. 구버전 문서나 트레이스에서 load_balance가 보인다면 6.9 이하 커널입니다.

/* kernel/sched/fair.c — Linux v7.3.1 (일부 오류 처리 생략) */
static int sched_balance_rq(int this_cpu, struct rq *this_rq,
                        struct sched_domain *sd, enum cpu_idle_type idle,
                        int *continue_balancing)
{
    int ld_moved, cur_ld_moved, active_balance = 0;
    struct sched_domain *sd_parent = sd->parent;
    struct sched_group *group;
    struct rq *busiest;
    struct rq_flags rf;
    struct cpumask *cpus = this_cpu_cpumask_var_ptr(load_balance_mask);
    struct lb_env env = {
        .sd       = sd,
        .dst_cpu  = this_cpu,
        .dst_rq   = this_rq,
        .idle     = idle,
        .loop_max = min(sysctl_sched_nr_migrate, 1),
    };

    sched_balance_update_blocked_averages(this_cpu);

    for_each_domain(this_cpu, sd) {
        /* 1. 가장 바쁜 그룹 선택 */
        group = find_busiest_group(&env);
        if (!group)
            continue;

        /* 2. 그룹 안에서 가장 바쁜 런큐 선택 */
        busiest = sched_balance_find_src_rq(&env, group);
        if (!busiest)
            continue;

        env.src_cpu   = busiest->cpu;
        env.src_rq    = busiest;
        env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);

        /* 3. 태스크 분리(detach) - 반복 이동 */
        cur_ld_moved = detach_tasks(&env);
        ld_moved += cur_ld_moved;
        if (cur_ld_moved)
            break;
    }
    /* 4. 분리한 태스크를 목적 런큐에 부착(attach) */
    if (ld_moved)
        attach_tasks(&env);

    return ld_moved;
}

PELT (Per-Entity Load Tracking)

PELT는 각 태스크와 CPU의 부하를 시간 감쇠 평균으로 추적하는 메커니즘입니다.

PELT 메트릭

감쇠 계산

/* kernel/sched/pelt.c */
/* 32ms 주기로 절반으로 감쇠 (half-life) */
#define LOAD_AVG_PERIOD 32
#define LOAD_AVG_MAX    47742

static void __update_load_avg_se(u64 now, struct sched_entity *se)
{
    u64 delta = now - se->avg.last_update_time;

    /* Geometric series로 감쇠 적용 */
    se->avg.load_sum = decay_load(se->avg.load_sum, delta);
    se->avg.util_sum = decay_load(se->avg.util_sum, delta);

    se->avg.load_avg = se->avg.load_sum / LOAD_AVG_MAX;
    se->avg.util_avg = se->avg.util_sum / LOAD_AVG_MAX;
}

grep "avg\." /proc/self/sched
# se.avg.load_avg                  :          512
# se.avg.util_avg                  :          480
# se.avg.runnable_avg              :          490

스케줄러 클래스

CFS는 여러 스케줄러 클래스 중 하나입니다.

스케줄러 클래스 우선순위

sched_class 구조체

/* kernel/sched/sched.h */
struct sched_class {
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
    struct task_struct *(*pick_next_task)(struct rq *rq);
    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    /* ... */
};

const struct sched_class fair_sched_class = {
    .enqueue_task       = enqueue_task_fair,
    .dequeue_task       = dequeue_task_fair,
    .pick_next_task     = pick_next_task_fair,
    .task_tick          = task_tick_fair,
    /* ... */
};

CFS 그룹 스케줄링

그룹 스케줄링은 프로세스 그룹(cgroup) 단위로 CPU 시간을 공정하게 분배합니다.

그룹 스케줄링 구조

task_group (cgroup)
  ├─ cfs_rq[CPU0]  ← CPU0의 그룹 런큐
  │    ├─ Task A (vruntime=100)
  │    └─ Task B (vruntime=150)
  └─ cfs_rq[CPU1]  ← CPU1의 그룹 런큐
       └─ Task C (vruntime=80)

sched_entity (그룹 대표)
  ├─ vruntime: 그룹 전체의 가상 런타임
  └─ load: 그룹 내 태스크 부하 합

설정 방법

# cgroup v2에서 CPU 시간 제한
mkdir /sys/fs/cgroup/mygroup
echo "100000 1000000" > /sys/fs/cgroup/mygroup/cpu.max
# 100ms / 1000ms = 10% CPU 시간 제한

echo $$ > /sys/fs/cgroup/mygroup/cgroup.procs

선점 메커니즘

CFS는 다음 조건에서 현재 실행 중인 태스크를 선점합니다.

선점 조건

• Tick 기반 선점: scheduler_tick()에서 check_preempt_tick() 호출
• Wake-up 선점: 깨어난 태스크의 vruntime이 현재 태스크보다 충분히 작을 때
• 실시간 태스크: 실시간 태스크가 깨어나면 즉시 선점

check_preempt_tick 구현

/* kernel/sched/fair.c */
static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;

    ideal_runtime = sched_slice(cfs_rq, curr);
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

    /* 타임슬라이스 소진 */
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }

    /* leftmost 태스크와 vruntime 차이 확인 */
    se = __pick_first_entity(cfs_rq);
    delta_exec = curr->vruntime - se->vruntime;

    if (delta_exec > sysctl_sched_wakeup_granularity)
        resched_curr(rq_of(cfs_rq));
}

scheduler_tick → task_tick_fair 경로

타이머 인터럽트(Timer Interrupt)가 발생하면 scheduler_tick()이 호출되고, 이 함수가 현재 실행 중인 태스크의 타임슬라이스 소진 여부를 점검합니다. 아래는 전체 호출 경로입니다.

scheduler_tick()의 핵심 코드입니다.

/* kernel/sched/core.c */
void scheduler_tick(void)
{
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;
    struct rq_flags rf;

    sched_clock_tick();  /* 스케줄러 클럭 갱신 */

    rq_lock(rq, &rf);
    update_rq_clock(rq); /* rq->clock 갱신 */

    /* 현재 스케줄링 클래스의 task_tick 호출 */
    curr->sched_class->task_tick(rq, curr, 0);

    calc_global_load_tick(rq); /* 전역 부하 평균 갱신 */
    psi_task_tick(rq);          /* PSI(Pressure Stall Info) 갱신 */
    rq_unlock(rq, &rf);

    perf_event_task_tick();
}

task_tick_fair()는 CFS 스케줄링 클래스(Scheduling Class)의 tick 핸들러(Handler)로, 모든 sched_entity 계층을 순회하며 갱신합니다.

/* kernel/sched/fair.c */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    /* 태스크 그룹(cgroup) 계층 전체를 bottom-up으로 순회 */
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued); /* 각 레벨에서 tick 처리 */
    }

    if (static_branch_unlikely(&sched_numa_balancing))
        task_tick_numa(rq, curr);   /* NUMA 밸런싱 tick */

    update_misfit_status(curr, rq); /* asymmetric CPU 불균형 감지 */
    update_overutilized_status(task_rq(curr));
}

entity_tick()은 update_curr()로 vruntime을 갱신하고, 이때 update_deadline()이 현재 태스크의 슬라이스(가상 마감) 소진 여부를 검사합니다. 기존 CFS(≤6.5)에서는 check_preempt_tick()이 vruntime 차이로 선점을 결정했습니다.

/* kernel/sched/fair.c — 간략화 */
static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    /* vruntime 갱신 — 내부에서 update_deadline()이 슬라이스 소진 검사 */
    update_curr(cfs_rq);

    /* PELT: 지수 이동 평균으로 부하 추적 */
    update_load_avg(cfs_rq, curr, UPDATE_TG);
    update_cfs_group(curr);
}

깨우기(Wakeup) 선점(Wakeup Preemption) 상세

태스크가 슬립(Sleep) 상태에서 깨어날 때(wake-up), CFS는 현재 실행 중인 태스크를 선점할지 결정합니다. 전통적 CFS(≤6.5)에서는 wakeup_preempt_entity()가 vruntime 차이로 판단했지만, EEVDF(6.6+)에서는 pick_eevdf()가 고른 가장 이른 deadline(가장 적격, most eligible) 태스크가 깨어난 태스크인지로 판단합니다. 결정 함수 이름은 버전에 따라 check_preempt_wakeup()(≤6.13) → check_preempt_wakeup_fair()(6.14+) → wakeup_preempt_fair()(최신)로 바뀌었으며, 내부 판단 로직은 동일합니다.

/* kernel/sched/fair.c — wakeup 선점 진입점 (EEVDF, 최신 커널 간략화) */
static void
wakeup_preempt_fair(struct rq *rq, struct task_struct *p, int wake_flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;
    struct cfs_rq *cfs_rq;

    if (unlikely(se == pse))
        return;

    /* 이미 선점이 예약되어 있으면 추가 판단 불필요 */
    if (test_tsk_need_resched(curr))
        return;

    /* WAKEUP_PREEMPTION 기능 비활성 시 선점 안 함 */
    if (!sched_feat(WAKEUP_PREEMPTION))
        return;

    find_matching_se(&se, &pse);  /* 같은 cgroup 레벨로 올라감 */

    /* SCHED_IDLE 엔티티는 비유휴 엔티티에게 항상 선점당함 */
    if (se_is_idle(se) && !se_is_idle(pse))
        goto preempt;
    if (se_is_idle(se) != se_is_idle(pse))
        return;

    /* BATCH/IDLE 정책 태스크는 선점하지 않음 (tick이 선점을 담당) */
    if (unlikely(!normal_policy(p->policy)))
        return;

    cfs_rq = cfs_rq_of(se);
    update_curr(cfs_rq);           /* 현재 태스크 vruntime 갱신 */

    /* EEVDF 핵심 판단: 깨어난 태스크가 가장 이른 deadline이면 선점 */
    if (pick_eevdf(cfs_rq) == pse)
        goto preempt;

    return;

preempt:
    resched_curr(rq);  /* TIF_NEED_RESCHED 설정 (6.14+에서는 lazy) */
}

place_entity()는 깨어난 태스크가 enqueue될 때 lag(지연)을 복원하고 가상 마감(deadline)을 설정합니다. EEVDF의 wakeup 선점은 이 deadline을 기준으로, 깨어난 태스크가 현재 실행 중인 태스크보다 가장 이른 deadline(가장 적격)일 때만 선점합니다.

/* kernel/sched/fair.c — EEVDF deadline 계산 (place_entity() 핵심, 간략화) */
se->slice = sysctl_sched_base_slice;       /* base_slice: 기본 750µs (6.15+ 700µs) */
vslice = calc_delta_fair(se->slice, se);   /* r_i / w_i */
se->vruntime = vruntime - lag;             /* vlag(lag) 복원 */
se->deadline = se->vruntime + vslice;      /* vd_i = ve_i + r_i/w_i */

/* wakeup 선점: 깨어난 태스크(pse)가 cfs_rq에서 가장 이른 deadline이면 선점 */
if (pick_eevdf(cfs_rq) == pse)
    resched_curr(rq);  /* TIF_NEED_RESCHED 설정 */

모니터링

CFS 스케줄러의 동작을 관찰하고 디버깅(Debugging)하는 방법입니다.

/proc 인터페이스

# 프로세스별 스케줄링 통계
cat /proc/1234/sched
# se.sum_exec_runtime    : 누적 실행 시간
# se.vruntime            : 가상 런타임
# se.nr_migrations       : CPU 이동 횟수
# nr_voluntary_switches  : 자발적 컨텍스트 스위치
# nr_involuntary_switches: 비자발적 컨텍스트 스위치

# 전체 스케줄러 디버그 정보
cat /proc/sched_debug
# CPU별 런큐 상태, 부하, 태스크 목록

schedstats 활성화

# CONFIG_SCHEDSTATS=y로 커널 빌드 시 사용 가능
cat /proc/schedstat

# 또는 동적 활성화 (커널 4.6+)
echo 1 > /proc/sys/kernel/sched_schedstats

perf 도구

# 스케줄링 이벤트 추적
perf sched record -- sleep 10
perf sched latency

# 출력 예:
#  Task                  |   Runtime ms  | Switches | Avg delay ms | Max delay ms |
#  my_app:1234           |    1245.123   |   512    |    0.123     |    12.456    |

성능 튜닝

스케줄러 파라미터를 조정해 워크로드 특성에 맞출 수 있습니다. 값에 따른 변화 폭은 하드웨어·워크로드마다 다르므로, 아래 수치는 출발점으로만 쓰고 대상 시스템에서 다시 측정합니다.

튜닝 파라미터

7.x에서 스케줄러 튜닝 값은 /proc/sys/kernel이 아니라 debugfs의 /sys/kernel/debug/sched/ 아래에 있습니다(sched_init_debug(), kernel/sched/debug.c). CONFIG_SCHED_DEBUG가 켜져 있고 debugfs가 마운트(Mount)되어 있어야 합니다.

이 가운데 sched_cfs_bandwidth_slice_us만 fair.c의 sysctl 테이블(sched_fair_sysctls)에 남아 있고, 나머지는 debugfs 항목입니다. 태스크 단위 슬라이스는 sysctl이 아니라 sched_setattr()로 요청합니다.

워크로드별 권장 설정

대화형 데스크톱

# 짧은 슬라이스 + 낮은 이동 비용 → 응답성 우선
echo 500000 > /sys/kernel/debug/sched/base_slice_ns        # 0.5ms
echo 250000 > /sys/kernel/debug/sched/migration_cost_ns   # 0.25ms

배치 처리 서버

# 긴 슬라이스 + 높은 이동 비용 → 처리량·캐시 친화 우선
echo 3000000 > /sys/kernel/debug/sched/base_slice_ns        # 3ms
echo 5000000 > /sys/kernel/debug/sched/migration_cost_ns   # 5ms
echo 128 > /sys/kernel/debug/sched/nr_migrate

전역 값을 건드리지 않고 특정 태스크에만 슬라이스를 지정하려면 sched_setattr()의 sched_runtime을 사용합니다. 커널은 이 값을 100us~100ms로 클램프하고 se->custom_slice를 세웁니다.

/* Linux 6.6+ EEVDF: 태스크별 슬라이스 요청 */
#include <linux/sched/types.h>
#include <sys/syscall.h>
#include <unistd.h>

struct sched_attr attr = {
    .size          = sizeof(attr),
    .sched_policy  = SCHED_NORMAL,
    .sched_nice    = 0,
    .sched_runtime = 500000,   /* 0.5ms 요청 */
};

syscall(SYS_sched_setattr, 0, &attr, 0);

CPU Affinity 설정

# taskset으로 CPU 고정 (부하 분산 비활성화)
taskset -c 0-3 ./my_app

# C API
#include <sched.h>
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(0, &cpuset);
sched_setaffinity(0, sizeof(cpuset), &cpuset);

CFS Bandwidth Control

cgroup을 통해 그룹의 CPU 사용량을 제한할 수 있습니다.

설정 예제

# cgroup v2
mkdir /sys/fs/cgroup/limited
echo "50000 100000" > /sys/fs/cgroup/limited/cpu.max
# quota=50ms, period=100ms → 50% CPU 제한

echo $$ > /sys/fs/cgroup/limited/cgroup.procs

# cgroup v1
echo 100000 > /sys/fs/cgroup/cpu/limited/cpu.cfs_period_us
echo 50000 > /sys/fs/cgroup/cpu/limited/cpu.cfs_quota_us

다른 스케줄러와 비교

vruntime 타임라인

vruntime은 CFS의 공정성을 보장하는 핵심 메트릭입니다. 이 섹션에서는 min_vruntime의 진행 방식, 새 태스크의 vruntime 초기화, 그리고 타임라인 전체를 시각적으로 추적합니다.

min_vruntime 진행

min_vruntime은 CFS 런큐에서 모든 태스크의 vruntime 중 최솟값을 단조 증가하며 추적하는 변수입니다. 새로 진입하는 태스크나 슬립(Sleep) 후 복귀하는 태스크의 vruntime 초기화 기준점 역할을 합니다.

/* kernel/sched/fair.c */
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);
    u64 vruntime = cfs_rq->min_vruntime;

    if (curr) {
        if (curr->on_rq)
            vruntime = curr->vruntime;
        else
            curr = NULL;
    }

    if (leftmost) {
        struct sched_entity *se = rb_entry(leftmost,
                                           struct sched_entity,
                                           run_node);
        if (!curr)
            vruntime = se->vruntime;
        else
            vruntime = min_vruntime(vruntime, se->vruntime);
    }

    /* min_vruntime은 단조 증가만 허용 */
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

새 태스크 vruntime 초기화

fork()로 생성된 새 태스크는 place_entity()에서 vruntime이 초기화됩니다. 기본적으로 min_vruntime을 기준으로 설정하되, sched_child_runs_first 옵션에 따라 부모/자식의 실행 순서가 결정됩니다.

/* kernel/sched/fair.c */
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);

    /* 슬립 복귀 시 보상: thresh만큼 뒤로 당김 */
    if (!initial) {
        unsigned long thresh = sysctl_sched_latency;
        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;  /* 절반만 보상 */
        vruntime -= thresh;
    }

    /* min_vruntime보다 뒤로 가지 않도록 보장 */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

슬립/웨이크업 시 vruntime 보상

오랫동안 슬립한 태스크가 깨어났을 때, vruntime이 너무 작으면 다른 태스크를 장시간 선점할 수 있습니다. CFS는 GENTLE_FAIR_SLEEPERS 기능으로 이를 제한합니다.

Linux 6.6+ EEVDF의 기준선: zero_vruntime과 avg_vruntime

6.6에서 EEVDF가 병합되면서 cfs_rq->min_vruntime과 update_min_vruntime()은 제거되었습니다. v7.3.1에서 min_vruntime은 sched_entity의 RB-tree 증강 필드로만 남아 있고, 런큐의 시간 기준선은 다음 네 값으로 유지됩니다.

가중 평균 V는 avg_vruntime()이 V = Σ(v_i − v0)·w_i / Σw_i + v0로 계산합니다. vruntime이 d만큼 전진하면 모든 편차가 d만큼 줄어들므로, sum_w_vruntime에서 d × sum_weight를 빼는 O(1) 갱신으로 끝납니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static inline
void update_zero_vruntime(struct cfs_rq *cfs_rq, s64 delta)
{
    /*
     * v' = v + d ==> sum_w_vruntime' = sum_w_vruntime - d*sum_weight
     */
    cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta;
    cfs_rq->zero_vruntime += delta;
}

적격성(Eligibility)은 lag_i = w_i(V − v_i) ≥ 0, 즉 V ≥ v_i입니다. 나눗셈으로 V를 구하면 정밀도가 손실되므로, 커널은 양변에 Σw_i를 곱한 정수 비교를 사용합니다.

/* kernel/sched/fair.c — Linux v7.3.1 */
static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 key, avg = cfs_rq->sum_w_vruntime;
    long load = cfs_rq->sum_weight;

    if (curr && curr->on_rq) {
        unsigned long weight = avg_vruntime_weight(cfs_rq, curr->h_load.weight);

        avg += entity_key(cfs_rq, curr) * weight;
        load += weight;
    }

    key = vruntime_op(vruntime, "-", cfs_rq->zero_vruntime);

#ifdef CONFIG_64BIT
#ifdef CONFIG_ARCH_SUPPORTS_INT128
    /* This often results in simpler code than __builtin_mul_overflow(). */
    return avg >= (__int128)key * load;
#else
    s64 rhs;
    /*
     * On overflow, the sign of key tells us the correct answer: a large
     * positive key means vruntime >> V, so not eligible; a large negative
     * key means vruntime << V, so eligible.
     */
    if (check_mul_overflow(key, load, &rhs))
        return key <= 0;

    return avg >= rhs;
#endif
#else /* 32bit */
    return avg >= key * load;
#endif
}

int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    return vruntime_eligible(cfs_rq, se->vruntime);
}

새 태스크와 슬립 복귀 태스크는 place_entity()가 avg_vruntime()을 기준으로 배치합니다. 슬라이스는 se->slice = sysctl_sched_base_slice(기본 700,000ns)를 calc_delta_fair()로 가상 시간으로 환산하고, 마감은 deadline = vruntime + vslice로 정해집니다. 이때 sched_feat(PLACE_LAG)가 켜져 있으면 디큐 시점의 vlag를 보존하도록 lag을 부풀려 배치하고(가중 평균이 이동하는 효과를 보정), sched_feat(PLACE_DEADLINE_INITIAL)과 ENQUEUE_INITIAL 조합에서는 새 태스크를 vslice/2만큼 앞당겨 초기 응답성을 확보합니다.

그룹 스케줄링

CFS 그룹 스케줄링은 task_group 계층 구조를 통해 CPU 시간을 계층적으로 분배합니다. 각 그룹은 독립적인 sched_entity와 cfs_rq를 가지며, 상위 그룹의 런큐에 스케줄링 엔티티로 참여합니다.

task_group 계층 구조

/* kernel/sched/sched.h */
struct task_group {
    struct cgroup_subsys_state css;

    /* 각 CPU별 스케줄링 엔티티와 CFS 런큐 */
    struct sched_entity  **se;     /* se[cpu] — 상위 cfs_rq에 참여 */
    struct cfs_rq        **cfs_rq; /* cfs_rq[cpu] — 그룹 내부 런큐 */

    unsigned long        shares;   /* cpu.shares (비율 기반 분배) */
    struct rcu_head       rcu;
    struct list_head      list;
    struct task_group     *parent;
    struct list_head      siblings;
    struct list_head      children;
};

shares 분배 알고리즘

cpu.shares 값은 형제 그룹 간의 상대적 CPU 시간 비율을 결정합니다. 기본값은 1024 (= NICE_0_LOAD)입니다.

/* 그룹 A: shares=2048, 그룹 B: shares=1024인 경우 */
/* 그룹 A는 그룹 B보다 2배의 CPU 시간을 할당받음 */

/* kernel/sched/fair.c — shares → weight 변환 */
static void update_cfs_group(struct sched_entity *se)
{
    struct cfs_rq *gcfs_rq = group_cfs_rq(se);
    unsigned long shares;

    if (!gcfs_rq)
        return;

    shares = calc_group_shares(gcfs_rq);
    reweight_entity(cfs_rq_of(se), se, shares);
}

/* shares 계산: 그룹 내 부하 비율에 따라 CPU별로 분배 */
static long calc_group_shares(struct cfs_rq *cfs_rq)
{
    long tg_weight, tg_shares, load, shares;
    struct task_group *tg = cfs_rq->tg;

    tg_shares = READ_ONCE(tg->shares);
    load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
    tg_weight = atomic_long_read(&tg->load_avg);

    shares = (tg_shares * load) / tg_weight;
    return clamp_t(long, shares, MIN_SHARES, tg_shares);
}

cgroup v2에서의 그룹 스케줄링 설정

# 그룹 생성 및 shares 설정
mkdir -p /sys/fs/cgroup/webserver
mkdir -p /sys/fs/cgroup/batch

# cpu.weight (cgroup v2, 기본값 100)
echo 200 > /sys/fs/cgroup/webserver/cpu.weight  # 높은 비율
echo 50 > /sys/fs/cgroup/batch/cpu.weight      # 낮은 비율

# 프로세스 배치
echo $$ > /sys/fs/cgroup/webserver/cgroup.procs

# 현재 weight 확인
cat /sys/fs/cgroup/webserver/cpu.weight
# 200

EEVDF vs CFS 비교

Linux 6.6부터 CFS는 EEVDF(Earliest Eligible Virtual Deadline First) 알고리즘으로 대체되었습니다. EEVDF는 CFS의 공정성 원칙을 유지하면서 지연시간 보장을 추가합니다.

핵심 개념: Eligible과 Virtual Deadline

Lag (지연) 기반 선택

EEVDF에서 lag은 태스크가 받아야 할 CPU 시간과 실제 받은 CPU 시간의 차이입니다.

/* kernel/sched/fair.c (Linux 6.6+) */
/* lag = 기대 서비스 시간 - 실제 서비스 시간 */
/* lag > 0: CPU를 덜 받은 태스크 (eligible) */
/* lag < 0: CPU를 더 받은 태스크 (not eligible) */

static void update_entity_lag(struct cfs_rq *cfs_rq,
                               struct sched_entity *se)
{
    s64 lag, limit;

    SCHED_WARN_ON(!se->on_rq);
    lag = avg_vruntime(cfs_rq) - se->vruntime;

    limit = calc_delta_fair(max_t(u64,
        2 * se->slice, TICK_NSEC), se);
    se->vlag = clamp(lag, -limit, limit);
}

/* Virtual Deadline 계산 */
/* deadline = vruntime + (slice / weight) * NICE_0_LOAD */
static u64 vruntime_deadline(struct sched_entity *se)
{
    return se->vruntime + calc_delta_fair(se->slice, se);
}

EEVDF 선택 과정

/* pick_eevdf(): eligible 태스크 중 가장 이른 deadline 선택 */
static struct sched_entity *
pick_eevdf(struct cfs_rq *cfs_rq)
{
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    struct sched_entity *best = NULL;

    while (node) {
        struct sched_entity *se = __node_2_se(node);

        /* eligible 조건: vruntime <= avg_vruntime */
        if (entity_eligible(cfs_rq, se)) {
            /* deadline이 가장 이른 eligible 태스크 선택 */
            if (!best || deadline_gt(best, se))
                best = se;
            node = node->rb_left;
        } else {
            node = node->rb_right;
        }
    }
    return best;
}

EEVDF 실무 활용

EEVDF에서 태스크의 slice 값을 조정하면 지연시간 특성을 제어할 수 있습니다.

/* EEVDF에서 태스크 slice 설정 (Linux 6.14+ — sched_runtime이 slice로 해석됨) */
#include <sched.h>
#include <linux/sched.h>

struct sched_attr attr = {
    .size = sizeof(struct sched_attr),
    .sched_policy = SCHED_NORMAL,
    .sched_nice = 0,
    /* sched_runtime은 EEVDF의 slice로 해석됨 */
    .sched_runtime = 3000000,  /* 3ms slice → 짧은 deadline */
};

/* 짧은 slice = 짧은 deadline = 더 빠른 스케줄링 */
/* 긴 slice = 긴 deadline = 더 큰 타임슬라이스 */
sched_setattr(0, &attr, 0);

CFS 대역폭 제어

CFS Bandwidth Control은 cgroup 단위로 CPU 사용량을 하드 리밋합니다. quota와 period 파라미터로 동작하며, quota가 소진되면 그룹 전체가 스로틀링됩니다.

대역폭 제어 핵심 구조체

/* kernel/sched/sched.h */
struct cfs_bandwidth {
    raw_spinlock_t   lock;
    ktime_t          period;         /* 주기 (기본 100ms) */
    u64              quota;          /* 주기당 허용 CPU 시간 */
    u64              runtime;        /* 남은 런타임 */
    u64              burst;          /* 버스트 허용량 (Linux 5.14+) */
    s64              hierarchical_quota;

    u8               idle;
    u8               period_active;
    struct hrtimer    period_timer;   /* 주기 리셋 타이머 */
    struct hrtimer    slack_timer;    /* 여유 런타임 회수 */

    struct list_head  throttled_cfs_rq;
    int              nr_periods;     /* 통계: 총 주기 수 */
    int              nr_throttled;   /* 통계: 스로틀 횟수 */
    u64              throttled_time; /* 통계: 스로틀 시간 합 */
};

스로틀링 메커니즘

/* kernel/sched/fair.c — quota 소진 시 스로틀링 */
static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
    if (!cfs_bandwidth_used())
        return false;

    if (likely(!cfs_rq->runtime_enabled ||
               cfs_rq->runtime_remaining > 0))
        return false;

    /* 글로벌 풀에서 런타임 보충 시도 */
    if (cfs_rq_throttled(cfs_rq))
        return true;

    throttle_cfs_rq(cfs_rq);
    return true;
}

/* 스로틀 해제: period 타이머가 런타임 리필 */
static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b,
                                      int overrun)
{
    /* 새 period 시작: quota 리필 */
    cfs_b->runtime = cfs_b->quota;

    /* 스로틀된 cfs_rq에 런타임 분배 */
    while (throttled) {
        distribute_cfs_runtime(cfs_b);
        unthrottle_cfs_rq(cfs_rq);
    }
    return 0;
}

멀티코어 환경에서의 Quota 소비

CFS bandwidth의 quota는 모든 CPU에서 공유됩니다. 멀티코어에서 2개 스레드(Thread)가 동시 실행되면 quota가 2배 속도로 소비됩니다.

# 예: cpu.max = "100000 100000" (100ms quota / 100ms period)
# 1 CPU 사용 시: 100ms 동안 실행 가능 → 100% CPU
# 2 CPU 사용 시: 50ms 동안 실행 → 각 CPU 50ms → 합계 100ms = 100% CPU
# 4 CPU 사용 시: 25ms 동안 실행 → 각 CPU 25ms → 합계 100ms = 100% CPU

# 4 CPU를 모두 활용하려면:
echo "400000 100000" > /sys/fs/cgroup/myapp/cpu.max
# quota=400ms → 4코어 × 100ms = 400% CPU (= 4코어 전부 사용 가능)

Burst 기능 (Linux 5.14+)

cpu.max.burst는 사용하지 않은 quota를 누적하여 일시적으로 제한을 초과할 수 있게 합니다.

# 버스트 설정 (미사용 quota를 최대 20ms까지 누적)
echo "50000 100000" > /sys/fs/cgroup/myapp/cpu.max
echo 20000 > /sys/fs/cgroup/myapp/cpu.max.burst

# 통계 확인
cat /sys/fs/cgroup/myapp/cpu.stat
# usage_usec 12345678
# nr_periods 1500
# nr_throttled 42
# throttled_usec 2100000
# nr_bursts 15
# burst_usec 150000

pick_next_task_fair() 코드 워크스루

pick_next_task_fair()는 CFS 스케줄러의 핵심 진입점(Entry Point)으로, 다음에 실행할 태스크를 선택합니다. 이 함수는 최적화 경로(simple path)와 그룹 스케줄링 경로를 분리하여 성능을 극대화합니다.

전체 흐름

/* kernel/sched/fair.c */
static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev,
                    struct rq_flags *rf)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    struct task_struct *p;
    int new_tasks;

again:
    if (!sched_fair_runnable(rq))
        goto idle;

#ifdef CONFIG_FAIR_GROUP_SCHED
    if (!prev || prev->sched_class != &fair_sched_class)
        goto simple;

    /* 이전 태스크가 CFS였으면 put_prev 처리 */
    do {
        struct sched_entity *curr = cfs_rq->curr;
        if (curr && curr->on_rq)
            update_curr(cfs_rq);
        else
            curr = NULL;

        if (unlikely(check_cfs_rq_runtime(cfs_rq))) {
            cfs_rq = &rq->cfs;
            if (!cfs_rq->nr_running)
                goto idle;
            goto simple;
        }
    } while (cfs_rq);

    p = task_of(se);

simple:
#endif
    if (prev)
        put_prev_task(rq, prev);

    /* rb_first_cached: O(1)으로 leftmost 노드 접근 */
    do {
        se = pick_next_entity(cfs_rq);
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);

done: __maybe_unused;
    return p;

idle:
    /* CFS 태스크 없음 → 다른 클래스 시도 또는 idle */
    new_tasks = newidle_balance(rq, rf);
    if (new_tasks > 0)
        goto again;

    return NULL;
}

skip/next/last 힌트

pick_next_entity()에서는 leftmost 외에 skip, next, last 힌트를 통해 선택을 조정합니다.

/* kernel/sched/fair.c */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    /* leftmost가 기본 후보 */
    se = left;

    /* skip: 특정 엔티티를 건너뛰라는 힌트 */
    if (cfs_rq->skip == se) {
        struct sched_entity *second = __pick_next_entity(se);
        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    /* last: 마지막으로 깨운 엔티티 (캐시 친화성) */
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    /* next: wakeup으로 다음에 실행해야 할 엔티티 */
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    clear_buddies(cfs_rq, se);
    return se;
}

set_next_entity

/* 선택된 엔티티를 현재 실행 엔티티로 설정 */
static void set_next_entity(struct cfs_rq *cfs_rq,
                            struct sched_entity *se)
{
    /* RB-tree에서 제거 (현재 실행 중이므로 트리에 없어도 됨) */
    if (se->on_rq) {
        __dequeue_entity(cfs_rq, se);
        update_load_avg(cfs_rq, se, UPDATE_TG);
    }

    update_stats_curr_start(cfs_rq, se);
    cfs_rq->curr = se;

    se->prev_sum_exec_runtime = se->sum_exec_runtime;
}

로드 밸런싱

멀티코어 시스템에서 CFS의 로드 밸런싱은 sched_domain 계층 구조를 통해 단계적으로 수행됩니다. CPU 토폴로지(Topology)(SMT, MC, NUMA)에 따라 밸런싱 주기와 비용이 달라집니다.

sched_domain 계층

/* include/linux/sched/topology.h */
struct sched_domain {
    struct sched_domain *parent;   /* 상위 도메인 */
    struct sched_domain *child;    /* 하위 도메인 */
    struct sched_group *groups;    /* 도메인 내 CPU 그룹 */

    unsigned long min_interval;    /* 최소 밸런싱 간격 */
    unsigned long max_interval;    /* 최대 밸런싱 간격 */
    unsigned int  busy_factor;     /* 바쁠 때 간격 확장 배율 */
    unsigned int  imbalance_pct;   /* 불균형 임계값 (%) */
    unsigned int  cache_nice_tries;
    unsigned long flags;
    int           level;           /* 도메인 레벨 */
    char          *name;           /* SMT, MC, NUMA 등 */
};

Pull vs Push 마이그레이션

select_task_rq_fair: 최적 CPU 선택

/* kernel/sched/fair.c */
static int select_task_rq_fair(struct task_struct *p,
                               int prev_cpu, int wake_flags)
{
    int new_cpu = prev_cpu;
    int want_affine = 0;
    struct sched_domain *sd;

    /* 1. 친화성: 깨운 CPU와 같은 도메인 선호 */
    if (wake_flags & WF_TTWU) {
        int waker_cpu = smp_processor_id();
        want_affine = cpumask_test_cpu(waker_cpu,
                                         p->cpus_ptr);
    }

    /* 2. sched_domain 탐색: 가장 에너지 효율적인 CPU */
    for_each_domain(prev_cpu, sd) {
        if (want_affine && cpumask_test_cpu(prev_cpu,
                              sched_domain_span(sd)))
            break;
    }

    /* 3. 유휴 CPU가 있으면 우선 선택 */
    new_cpu = find_idlest_cpu(sd, p, prev_cpu, new_cpu);

    return new_cpu;
}

select_idle_sibling / Wake-Affine 상세

select_task_rq_fair()가 wake-affine 경로를 선택하면 select_idle_sibling()을 호출해 동일 LLC(Last-Level Cache) 도메인 내에서 유휴 CPU를 찾습니다. 이 함수는 캐시 친화성을 최대로 유지하면서 불필요한 마이그레이션 비용을 줄이는 핵심 로직입니다.

/* kernel/sched/fair.c (단순화) */
static int select_idle_sibling(struct task_struct *p, int prev, int target)
{
    struct sched_domain *sd;
    int i, recent_used_cpu;

    /* ① 이전 CPU가 유휴 상태이면 즉시 반환 (캐시 친화성 최적) */
    if (idle_cpu(target) && asym_fits_cpu(p, target))
        return target;

    /* ② 최근 사용 CPU가 유휴인지 확인 */
    recent_used_cpu = p->recent_used_cpu;
    if (recent_used_cpu != prev && recent_used_cpu != target
        && cpumask_test_cpu(recent_used_cpu, p->cpus_ptr)
        && idle_cpu(recent_used_cpu)
        && cpus_share_cache(recent_used_cpu, target))
        return recent_used_cpu;

    /* ③ LLC 공유 도메인 내에서 유휴 CPU 스캔 (SIS_PROP) */
    sd = rcu_dereference(per_cpu(sd_llc, target));
    if (sd) {
        i = select_idle_cpu(p, sd, has_idle_core(sd), target);
        if ((unsigned)int i <= (unsigned)nr_cpumask_bits)
            return i;
    }

    return target;
}

SIS_PROP(Proportional Idle Scanning)는 탐색 비용을 최근 유휴 시간에 비례해 제한합니다. CPU가 자주 유휴라면 더 많이 탐색하고, 바쁜 시스템에서는 탐색을 조기 종료해 오버헤드를 줄입니다.

/* select_idle_cpu — SIS_PROP 비례 스캔 */
static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd,
                            bool has_idle_core, int target)
{
    u64 avg_cost, avg_idle, time, cost;
    int cpu, nr = 32; /* SIS_PROP 비활성 시 최대 탐색 횟수 */

    if (sched_feat(SIS_PROP)) {
        avg_idle = this_rq()->avg_idle;      /* 평균 유휴 시간 (ns) */
        avg_cost = sd->avg_scan_cost + 1;    /* 평균 탐색 비용 (ns) */
        nr = div64_u64(avg_idle, avg_cost);  /* 허용 탐색 횟수 비례 계산 */
        nr = clamp(nr, 1U, (unsigned)llc_weight(sd));
    }

    for_each_cpu_wrap(cpu, sched_domain_span(sd), target + 1) {
        if (!--nr)
            break;
        if (idle_cpu(cpu))
            return cpu;
    }

    return -1;
}

wake_affine()는 태스크를 깨운 CPU(waker)와 이전에 실행되던 CPU(prev) 중 어느 쪽으로 배치할지 결정합니다. 두 CPU의 예상 대기 시간(Latency)을 비교해 더 빠를 쪽을 선택합니다.

/* kernel/sched/fair.c — 간략화 */
static int wake_affine(struct sched_domain *sd, struct task_struct *p,
                       int this_cpu, int prev_cpu, int sync)
{
    int ret = wake_affine_idle(this_cpu, prev_cpu, sync);
    if (ret == nr_cpumask_bits)
        ret = wake_affine_weight(sd, p, this_cpu, prev_cpu, sync);

    schedstat_inc(sd->ttwu_move_affine);
    return (ret == this_cpu) ? WA_AFFINE : WA_IDLE;
}

Energy Aware Scheduling (EAS)

ARM big.LITTLE 같은 이기종 CPU 시스템에서 CFS는 EAS(Energy Aware Scheduling)를 통해 성능과 전력 소비를 최적화합니다.

/* kernel/sched/fair.c — EAS CPU 선택 */
static int find_energy_efficient_cpu(struct task_struct *p,
                                     int prev_cpu)
{
    unsigned long best_delta = ULONG_MAX;
    int best_cpu = -1;
    struct perf_domain *pd;

    /* 각 성능 도메인(big/LITTLE)별로 에너지 계산 */
    for_each_perf_domain(pd) {
        unsigned long cur_delta;
        int cpu;

        for_each_cpu(cpu, perf_domain_span(pd)) {
            /* 태스크 배치 시 에너지 증분 계산 */
            cur_delta = compute_energy(p, cpu, pd);
            if (cur_delta < best_delta) {
                best_delta = cur_delta;
                best_cpu = cpu;
            }
        }
    }
    return best_cpu;
}

# EAS 활성화 확인
cat /proc/sys/kernel/sched_energy_aware
# 1 (활성), 0 (비활성)

# 성능 도메인 확인
ls /sys/devices/system/cpu/cpu*/cpufreq/
# 각 CPU의 주파수 도메인 확인

# EAS 비활성화 (서버에서는 불필요)
echo 0 > /proc/sys/kernel/sched_energy_aware

sched_entity/cfs_rq 구조체 분석

CFS 스케줄러의 내부 동작을 이해하려면 sched_entity와 cfs_rq 구조체의 필드별 역할과 상호 관계를 파악해야 합니다.

sched_entity 상세 분석

/* 개념 요약 — 정확한 필드 순서·타입은 위 "sched_entity 구조체" 절 참조 */
struct sched_entity {
    /* === 부하/가중치 === */
    struct load_weight      load;          /* nice → weight 변환값 */
    struct sched_avg         avg;           /* PELT 메트릭 */

    /* === RB-tree 관련 === */
    struct rb_node           run_node;      /* RB-tree 노드 */
    unsigned int            on_rq;         /* 런큐에 있는지 여부 */

    /* === 실행 시간 추적 === */
    u64                     exec_start;    /* 현재 스케줄 시작 시각 */
    u64                     sum_exec_runtime; /* 누적 실행 시간 */
    u64                     prev_sum_exec_runtime;
    u64                     vruntime;      /* 가상 런타임 */

    /* === EEVDF 관련 (6.6+) === */
    s64                     vlag;          /* 지연 (lag) */
    u64                     deadline;      /* 가상 데드라인 */
    u64                     slice;         /* 요청 슬라이스 */

    /* === 그룹 스케줄링 === */
    struct sched_entity     *parent;       /* 상위 그룹 엔티티 */
    struct cfs_rq           *cfs_rq;       /* 소속 런큐 */
    struct cfs_rq           *my_q;         /* 그룹이면 자식 런큐 */

    int                     depth;         /* 그룹 계층 깊이 */
};

cfs_rq 구조체 분석

아래는 Linux v7.3.1의 실제 정의(주요 필드)입니다. CFS 시절의 nr_running, exec_clock, min_vruntime은 더 이상 존재하지 않습니다. EEVDF는 가중 평균 vruntime을 정확히 계산하기 위해 sum_w_vruntime/sum_weight/zero_vruntime 세 필드로 대체했고, 지연 디큐와 프록시 실행을 위해 h_curr가 추가되었습니다.

/* kernel/sched/sched.h — Linux v7.3.1 */
struct cfs_rq {
    /* === 부하 정보 === */
    struct load_weight  load;            /* 런큐 내 총 가중치 */
    unsigned int       nr_queued;        /* 직접 큐잉된 엔티티 수 */
    unsigned int       h_nr_queued;      /* 계층 합산 큐 길이 */
    unsigned int       h_nr_runnable;    /* 실행 가능(러너블) 수 */
    unsigned int       h_nr_idle;        /* SCHED_IDLE 수 */

    /* === EEVDF 가중 평균 vruntime === */
    s64                sum_w_vruntime;   /* 가중 vruntime 합 */
    u64                sum_weight;       /* 가중치 합 */
    u64                zero_vruntime;    /* 평균 계산 기준점 */
    unsigned int       sum_shift;        /* 합 스케일 보정 시프트 */
#ifdef CONFIG_SCHED_CORE
    unsigned int       forceidle_seq;
    u64                zero_vruntime_fi; /* force-idle 전용 영점 */
#endif

    /* === RB-tree === */
    struct rb_root_cached tasks_timeline; /* 키: deadline, leftmost 캐시 */

    /* === 현재/다음 엔티티 === */
    struct sched_entity *curr;           /* 스케줄러가 선택한 엔티티 */
    struct sched_entity *next;           /* wakeup buddy 힌트 */
    struct sched_entity *h_curr;         /* 계층 기준 현재 엔티티 */

    /* === PELT === */
    struct sched_avg     avg;
    struct {
        raw_spinlock_t  lock ____cacheline_aligned;
        int             nr;
        unsigned long   load_avg;
        unsigned long   util_avg;
        unsigned long   runnable_avg;
    } removed;                            /* 디큐된 엔티티의 잔여 기여분 */

#ifdef CONFIG_FAIR_GROUP_SCHED
    /* === 그룹 스케줄링 === */
    unsigned long       h_load;
    struct rq          *rq;              /* 소속 CPU 런큐 */
    struct list_head    leaf_cfs_rq_list;
    struct task_group  *tg;              /* 소유 task_group */
    int                idle;

# ifdef CONFIG_CFS_BANDWIDTH
    /* === Bandwidth Control === */
    int                runtime_enabled;
    s64                runtime_remaining; /* 남은 quota */
    bool               throttled;         /* 스로틀 여부 */
    int                throttle_count;
    struct list_head    throttled_list;
# endif
#endif
};

Weight/Load 계산 체계

enqueue/dequeue 흐름

태스크가 실행 가능 상태가 되면 enqueue_entity()로 CFS 런큐에 삽입되고, 슬립하거나 종료하면 dequeue_entity()로 제거됩니다.

/* kernel/sched/fair.c — 엔큐 핵심 로직 */
static void enqueue_entity(struct cfs_rq *cfs_rq,
                           struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP) ||
                  (flags & ENQUEUE_MIGRATED);

    /* 1. vruntime 정규화 (마이그레이션 시) */
    if (renorm && curr)
        se->vruntime += cfs_rq->min_vruntime;

    /* 2. PELT 부하 업데이트 */
    update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
    update_cfs_group(se);

    /* 3. 부하 가중치 업데이트 */
    account_entity_enqueue(cfs_rq, se);

    /* 4. vruntime 초기화 (새 태스크/슬립 복귀) */
    if (flags & ENQUEUE_WAKEUP)
        place_entity(cfs_rq, se, 0);

    /* 5. RB-tree에 삽입 */
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
    se->on_rq = 1;
}

/* RB-tree 삽입: vruntime을 키로 정렬 */
static void __enqueue_entity(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    bool leftmost = true;

    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false; /* leftmost 캐시 갱신 */
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node,
                           &cfs_rq->tasks_timeline, leftmost);
}

/* 디큐 핵심 로직 */
static void dequeue_entity(struct cfs_rq *cfs_rq,
                           struct sched_entity *se, int flags)
{
    /* 1. vruntime 업데이트 */
    update_curr(cfs_rq);

    /* 2. PELT 부하 업데이트 */
    update_load_avg(cfs_rq, se, UPDATE_TG);

    /* 3. 부하 가중치 제거 */
    account_entity_dequeue(cfs_rq, se);

    /* 4. RB-tree에서 제거 */
    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);
    se->on_rq = 0;

    /* 5. vruntime 비정규화 (마이그레이션 대비) */
    if (!(flags & DEQUEUE_SLEEP))
        se->vruntime -= cfs_rq->min_vruntime;

    update_min_vruntime(cfs_rq);
    update_cfs_group(se);
}

핵심 호출 체인: enqueue_task_fair → update_curr → pick_next_entity

태스크가 런큐에 진입하는 순간부터 다음 실행 태스크가 결정되기까지의 전체 호출 체인을 커널 소스 수준에서 추적합니다. 이 경로는 스케줄러 hot path(자주 실행되는 경로)이므로 성능에 직접 영향을 미칩니다.

호출 체인 개요

/* 태스크 깨어남 → 스케줄링 전체 흐름 */
try_to_wake_up()                    /* kernel/sched/core.c */
  └─ ttwu_do_activate()
       └─ activate_task()
            └─ enqueue_task()
                 └─ enqueue_task_fair()   /* fair.c: CFS 진입점 */
                      ├─ enqueue_entity()
                      │    ├─ update_curr()     /* vruntime 갱신 */
                      │    ├─ place_entity()   /* 초기 vruntime 배치 */
                      │    └─ __enqueue_entity() /* RB-tree 삽입 */
                      └─ hrtick_update()        /* 타이머 갱신 */

schedule()                          /* kernel/sched/core.c */
  └─ __schedule()
       ├─ put_prev_task_fair()       /* 현재 태스크 RB-tree 재삽입 */
       ├─ pick_next_task_fair()      /* 다음 태스크 선택 */
       │    └─ pick_next_entity()   /* leftmost 노드 반환 */
       └─ context_switch()           /* 실제 전환 */

enqueue_task_fair() 소스 분석

enqueue_task_fair()는 그룹 스케줄링 계층을 역방향으로 순회하며 각 레벨의 sched_entity를 해당 cfs_rq에 삽입합니다.

/* kernel/sched/fair.c */
static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;
    int idle_h_nr_running = task_has_idle_policy(p);
    int task_new = !(flags & ENQUEUE_WAKEUP);

    /* SCHED_IDLE 태스크의 경우 활성화 시 알림 */
    if (p->in_iowait)
        cpufreq_update_util(rq, SCHED_CPUFREQ_IOWAIT);

    /* 그룹 스케줄링 계층을 leaf → root 방향으로 순회 */
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);

        if (cfs_rq->nr_running) {
            update_load_avg(cfs_rq, se, UPDATE_TG);
            se_update_runnable(se);
        }

        enqueue_entity(cfs_rq, se, flags);

        cfs_rq->h_nr_running++;
        cfs_rq->idle_h_nr_running += idle_h_nr_running;

        if (cfs_rq_is_idle(cfs_rq))
            idle_h_nr_running = 1;

        /* 이미 런큐에 있었다면 상위 계층은 갱신 불필요 */
        if (cfs_rq->nr_running == 1)
            list_add_leaf_cfs_rq(cfs_rq);

        flags = ENQUEUE_WAKEUP;
    }

    add_nr_running(rq, 1);
    hrtick_update(rq);
}

update_curr() 상세 분석

update_curr()는 스케줄러에서 가장 자주 호출되는 함수 중 하나입니다. 현재 실행 중인 태스크의 실제 실행 시간을 vruntime으로 변환하여 공정성을 유지합니다.

/* kernel/sched/fair.c */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec;

    if (unlikely(!curr))
        return;

    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
        return;

    curr->exec_start = now;

    schedstat_set(curr->statistics.exec_max,
                  max(delta_exec, curr->statistics.exec_max));

    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq->exec_clock, delta_exec);

    /* 실제 실행 시간 → 가중 vruntime으로 변환 */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);

    if (entity_is_task(curr)) {
        struct task_struct *curtask = task_of(curr);
        trace_sched_stat_runtime(curtask, delta_exec,
                                  curr->vruntime);
        cgroup_account_cputime(curtask, delta_exec);
        account_group_exec_runtime(curtask, delta_exec);
    }

    account_cfs_rq_runtime(cfs_rq, delta_exec);
}

pick_next_entity() 상세 분석

CFS의 pick_next_entity()는 RB-tree leftmost 노드(최소 vruntime)를 기반으로 next/last/skip 힌트 시스템을 적용하여 최적의 다음 태스크를 선택합니다.

/* kernel/sched/fair.c (Linux 6.x, EEVDF 이전 기준) */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;

    /* curr도 후보: leftmost보다 작은 vruntime이면 curr 유지 */
    if (!left || (curr && entity_before(curr, left)))
        left = curr;

    se = left; /* 기본 선택: 최소 vruntime */

    /* skip 힌트: sched_yield()로 건너뛰라고 지정된 엔티티 */
    if (cfs_rq->skip && cfs_rq->skip == se) {
        struct sched_entity *second;
        if (se == curr) {
            second = __pick_first_entity(cfs_rq);
        } else {
            second = __pick_next_entity(se);
            if (!second || (curr && entity_before(curr, second)))
                second = curr;
        }
        if (second && wakeup_preempt_entity(second, left) < 1)
            se = second;
    }

    /* next 힌트: wakeup preemption이 결정한 다음 실행 엔티티 */
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;

    /* last 힌트: 캐시 친화성을 위해 마지막으로 깨운 태스크 선호 */
    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;

    clear_buddies(cfs_rq, se);
    return se;
}

place_entity() 상세 분석

place_entity()는 태스크가 처음 생성되거나 슬립에서 깨어날 때 vruntime을 공정하게 초기화합니다. 너무 작은 vruntime은 다른 태스크를 장시간 기아(Starvation) 상태로 만들 수 있기 때문에 적절한 패널티/보상 메커니즘이 필요합니다.

/* kernel/sched/fair.c */
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
             int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;

    /* 신규 태스크: START_DEBIT 패널티 — 한 주기분 vruntime 선납 */
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);

    /* 슬립 복귀: GENTLE_FAIR_SLEEPERS 보상 — 절반 주기 되돌려줌 */
    if (!initial) {
        unsigned long thresh;

        if (se_is_idle(se))
            thresh = sysctl_sched_min_granularity;
        else
            thresh = sysctl_sched_latency;

        if (sched_feat(GENTLE_FAIR_SLEEPERS))
            thresh >>= 1;         /* 절반만 보상 */

        vruntime -= thresh;
    }

    /* 기존 vruntime과 비교하여 더 큰 값(뒤처지지 않는 값) 사용 */
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

sched_entity 필드별 한국어 주석

CFS 동작의 핵심 자료구조인 sched_entity의 모든 주요 필드를 역할별로 그룹화하여 설명합니다.

/* include/linux/sched.h (Linux 6.x 기준) */
struct sched_entity {
    /* ── 부하/가중치 그룹 ── */
    struct load_weight     load;          /* nice → weight 변환값 (weight + inv_weight) */
    struct sched_avg       avg;           /* PELT: util_avg, load_avg, runnable_avg */

    /* ── RB-tree 위치 그룹 ── */
    struct rb_node         run_node;      /* RB-tree 삽입 노드 (vruntime 키) */
    unsigned int           on_rq;         /* 1=런큐에 있음, 0=슬립/종료 */

    /* ── 시간 추적 그룹 ── */
    u64                    exec_start;    /* update_curr() 마지막 호출 시각 (ns) */
    u64                    sum_exec_runtime; /* 총 누적 실행 시간 (ns) */
    u64                    prev_sum_exec_runtime; /* 이전 스케줄 주기 기준값 */
    u64                    vruntime;      /* 가상 런타임 (RB-tree 정렬 키) */

    /* ── EEVDF 그룹 (Linux 6.6+) ── */
    s64                    vlag;          /* 지연량 = avg_vruntime - vruntime */
    u64                    deadline;      /* 가상 데드라인 = vruntime + slice/weight */
    u64                    slice;         /* 요청 타임슬라이스 (sched_attr.sched_runtime) */

    /* ── 그룹 스케줄링 그룹 ── */
    struct sched_entity   *parent;       /* 상위 그룹의 sched_entity (루트면 NULL) */
    struct cfs_rq         *cfs_rq;       /* 이 엔티티가 속한 cfs_rq */
    struct cfs_rq         *my_q;         /* 그룹이면 내부 cfs_rq, 개별 태스크면 NULL */
    int                    depth;         /* 그룹 계층 깊이 (루트=0) */
};

cfs_rq 필드별 한국어 주석

cfs_rq는 CPU별로 존재하는 CFS 런큐입니다. 그룹 스케줄링 시에는 각 task_group마다 CPU별로 추가 런큐가 생성됩니다.

/* kernel/sched/sched.h */
struct cfs_rq {
    /* ── 부하 합산 그룹 ── */
    struct load_weight     load;           /* 런큐 내 모든 se의 weight 합 */
    unsigned int           nr_running;     /* 현재 레벨 실행 가능 태스크 수 */
    unsigned int           h_nr_running;   /* 하위 그룹 포함 총 태스크 수 */
    unsigned int           idle_h_nr_running; /* SCHED_IDLE 태스크 수 (계층 포함) */

    /* ── vruntime 기준 그룹 ── */
    u64                    exec_clock;     /* 런큐 누적 실행 시간 (schedstat용) */
    u64                    min_vruntime;   /* 단조 증가 최소 vruntime (새 태스크 기준점) */
    u64                    avg_vruntime;   /* EEVDF eligible 판정 기준선 */

    /* ── RB-tree 그룹 ── */
    struct rb_root_cached  tasks_timeline; /* vruntime 정렬 트리 + leftmost 캐시 */

    /* ── 현재 실행 힌트 그룹 ── */
    struct sched_entity   *curr;          /* 현재 실행 중인 엔티티 (트리 밖) */
    struct sched_entity   *next;          /* wakeup preemption 우선 후보 */
    struct sched_entity   *last;          /* 캐시 친화성 우선 후보 */
    struct sched_entity   *skip;          /* sched_yield() 건너뛰기 대상 */

    /* ── PELT 그룹 ── */
    struct sched_avg       avg;           /* 런큐 전체 PELT 평균 부하 */
    u64                    avg_load;       /* 런큐 평균 부하 (부하 분산용) */

    /* ── Bandwidth Control 그룹 ── */
    int                    runtime_enabled;   /* cfs_bandwidth 활성 여부 */
    s64                    runtime_remaining; /* 남은 실행 쿼터 (소진 시 throttle) */
    u64                    throttled_clock;   /* 스로틀 시작 시각 */
    u64                    throttled_clock_pelt; /* PELT 기준 스로틀 시각 */
    int                    throttled;         /* 현재 스로틀 상태 */
    int                    throttle_count;    /* 중첩 스로틀 깊이 */

    /* ── 그룹 스케줄링 그룹 ── */
    struct task_group     *tg;            /* 소속 task_group (루트이면 &root_task_group) */
    struct list_head       leaf_cfs_rq_list; /* 리프 런큐 순회 리스트 */
};

컨텍스트 스위치 내부 구조

CFS가 선점 결정을 내린 후 실제 태스크 교체는 context_switch()에서 이루어집니다. 이 함수는 메모리 공간 전환과 CPU 레지스터 교체라는 두 가지 핵심 작업을 수행합니다.

context_switch() 코드 분석

/* kernel/sched/core.c */
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
               struct task_struct *next, struct rq_flags *rf)
{
    prepare_task_switch(rq, prev, next); /* 아키텍처 준비 작업 */

    /*
     * 커널 스레드(mm == NULL)는 active_mm만 빌려 씀.
     * 사용자 태스크는 switch_mm_irqs_off()로 페이지 테이블 전환.
     */
    if (!next->mm) {
        /* 커널 스레드: lazy TLB 모드 — 현재 mm 유지 */
        next->active_mm = prev->active_mm;
        if (prev->mm)
            mmgrab(prev->active_mm);
        enter_lazy_tlb(prev->active_mm, next);
    } else {
        /* 사용자 태스크: 페이지 테이블 교체 + TLB 플러시 */
        switch_mm_irqs_off(prev->active_mm, next->mm, next);
    }

    rq_unpin_lock(rq, rf);
    spin_release(&rq->lock.dep_map, _THIS_IP_);

    /* CPU 레지스터(스택 포인터, 명령 포인터) 전환 — 이 줄 이후 prev가 복귀 */
    switch_to(prev, next, prev);
    barrier();

    return finish_task_switch(prev); /* 전환 완료 정리 */
}

switch_mm_irqs_off() — 페이지 테이블(Page Table) 전환

x86_64에서 페이지 테이블 전환은 CR3 레지스터를 새 태스크의 PGD(Page Global Directory) 물리 주소(Physical Address)로 덮어쓰는 것으로 이루어집니다. CR3 쓰기는 자동으로 TLB 전체 플러시(Flush)를 유발합니다(PCID 기능이 없을 경우).

/* arch/x86/mm/tlb.c (단순화) */
void switch_mm_irqs_off(struct mm_struct *prev, struct mm_struct *next,
                        struct task_struct *tsk)
{
    unsigned long new_cr3;

    if (prev == next)   /* 같은 mm이면 전환 불필요 */
        return;

    new_cr3 = build_cr3(next->pgd, tsk->mm_cid); /* PCID 포함 CR3 구성 */

    /* CR3 재로드 → TLB 플러시 (PCID 없이는 전체 flush) */
    write_cr3(new_cr3);

    /* mmu_notifier 콜백 및 lazy TLB flush list 처리 */
    switch_ldt(prev, next);
}

switch_to() — CPU 레지스터 저장/복원

x86_64에서 switch_to()는 어셈블리(Assembly) 매크로로 구현된 __switch_to_asm()을 호출합니다. 커널 스택 포인터(RSP)를 교체하고 다음 태스크의 saved RIP로 점프합니다.

/* arch/x86/entry/entry_64.S (단순화) */
SYM_FUNC_START(__switch_to_asm)
    /* 비-휘발성 레지스터를 prev의 커널 스택에 저장 */
    pushq %rbp
    pushq %rbx
    pushq %r12
    pushq %r13
    pushq %r14
    pushq %r15

    /* prev의 RSP를 task_struct->thread.sp에 저장 */
    movq %rsp, TASK_threadsp(%rdi)

    /* next의 RSP를 복원 → 스택 전환 완료 */
    movq TASK_threadsp(%rsi), %rsp

    /* next의 저장된 레지스터 복원 */
    popq %r15
    popq %r14
    popq %r13
    popq %r12
    popq %rbx
    popq %rbp

    /* __switch_to() C 함수 호출 후 next 태스크의 저장 RIP로 ret */
    jmp __switch_to
SYM_FUNC_END(__switch_to_asm)

finish_task_switch() — 전환 완료 정리

switch_to()에서 반환된 후에는 next 태스크의 컨텍스트에서 실행되고 있습니다. finish_task_switch()는 이전 태스크(prev)에 대한 정리를 수행합니다.

/* kernel/sched/core.c — 간략화 */
static struct rq * finish_task_switch(struct task_struct *prev)
{
    struct rq *rq = this_rq();
    struct mm_struct *mm = rq->prev_mm;
    long prev_state;

    rq->prev_mm = NULL;

    /* prev의 mm 참조 카운트 해제 (커널 스레드가 빌렸던 경우) */
    if (mm)
        mmdrop_sched(mm);

    prev_state = READ_ONCE(prev->__state);

    /* prev가 TASK_DEAD이면 task_struct 메모리 해제 */
    if (unlikely(prev_state == TASK_DEAD)) {
        if (prev->sched_class->task_dead)
            prev->sched_class->task_dead(prev);
        put_task_struct_rcu_user(prev);
    }

    tick_nohz_task_switch();       /* NO_HZ 상태 갱신 */
    finish_lock_switch(rq);        /* rq 락 재획득 */
    perf_event_task_sched_in(prev, current());
    return rq;
}

ftrace/perf/bpftrace 스케줄러 분석

CFS 스케줄러의 동작을 실시간으로 분석하는 세 가지 핵심 도구를 다룹니다.

ftrace sched 이벤트

ftrace의 sched 관련 tracepoint를 활용하여 스케줄링 이벤트를 추적합니다.

# 사용 가능한 sched 이벤트 확인
ls /sys/kernel/debug/tracing/events/sched/
# sched_switch        — 컨텍스트 스위치
# sched_wakeup        — 태스크 wake-up
# sched_wakeup_new    — 새 태스크 wake-up
# sched_migrate_task  — CPU 마이그레이션
# sched_stat_runtime  — 실행 시간 통계
# sched_stat_wait     — 런큐 대기 시간

# sched_switch 이벤트 추적
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
cat /sys/kernel/debug/tracing/trace_pipe | head -20

# 출력 예:
# <idle>-0 [002] 1234.567: sched_switch:
#   prev_comm=swapper/2 prev_pid=0 prev_state=R ==>
#   next_comm=my_app next_pid=1234 next_prio=120

# 특정 PID만 필터링
echo 'common_pid == 1234' > /sys/kernel/debug/tracing/events/sched/sched_switch/filter

# 스케줄 지연 측정 (wakeup → switch 시간)
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_stat_wait/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_stat_runtime/enable

perf sched 분석

# 10초간 스케줄링 이벤트 기록
perf sched record -- sleep 10

# 태스크별 지연시간 분석
perf sched latency --sort max
# ─────────────────────────────────────────────────────
# Task            │ Runtime ms │ Switches │ Max delay ms
# ─────────────────────────────────────────────────────
# my_app:1234     │   3456.12  │   2048   │    15.234
# worker:5678     │    123.45  │    512   │     3.456

# CPU별 타임라인 시각화
perf sched timehist --summary
# ─────────────────────────────────────────────────────
# CPU 0: busy 78.5%  idle 21.5%  migrations: 42
# CPU 1: busy 65.2%  idle 34.8%  migrations: 38

# 마이그레이션 추적
perf sched map

bpftrace 런큐 모니터링

# 런큐 대기 시간 히스토그램
bpftrace -e '
tracepoint:sched:sched_switch
{
    @runq_lat[args->next_comm] = hist(nsecs - @start[args->next_pid]);
    @start[args->next_pid] = nsecs;
}

tracepoint:sched:sched_wakeup,
tracepoint:sched:sched_wakeup_new
{
    @start[args->pid] = nsecs;
}

END { clear(@start); }
'

# CFS vruntime 분포 추적 (kprobe)
bpftrace -e '
kprobe:update_curr
{
    $se = (struct sched_entity *)arg1;
    @vruntime = hist($se->vruntime);
}
'

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

interval:s:1
{
    printf("cs/s: %d\n", @switches);
    clear(@switches);
}
'

# CPU 마이그레이션 추적
bpftrace -e '
tracepoint:sched:sched_migrate_task
{
    printf("%s[%d] CPU %d -> %d\n",
        args->comm, args->pid,
        args->orig_cpu, args->dest_cpu);
}
'

스케줄러 디버깅 체크리스트

CFS 관련 성능 문제 발생 시 다음 순서로 조사합니다.

PSI (Pressure Stall Information)

Linux 4.20+에서 도입된 PSI는 CPU/메모리/IO 자원 부족으로 태스크가 대기한 시간 비율을 제공합니다.

# 시스템 전체 CPU 압력
cat /proc/pressure/cpu
# some avg10=2.45 avg60=3.12 avg300=2.89 total=12345678
# full avg10=0.00 avg60=0.00 avg300=0.00 total=0

# cgroup별 CPU 압력
cat /sys/fs/cgroup/myapp/cpu.pressure
# some avg10=15.23 avg60=12.45 avg300=10.89 total=98765432

# 해석:
# some: 하나 이상의 태스크가 CPU를 기다리는 시간 비율 (%)
# full: 모든 태스크가 CPU를 기다리는 시간 비율 (CPU는 some만)
# avg10/60/300: 10초/60초/300초 이동 평균

# PSI 기반 알람 설정 (5초간 CPU 압력 25% 초과 시)
echo "some 250000 5000000" > /proc/pressure/cpu
# poll()로 감시 가능 (systemd-oomd, cgroup PSI 모니터링 등)

스케줄러 튜닝 파라미터 상세

스케줄러 동작을 조정하는 파라미터를 기본값·범위·효과까지 정리합니다.

핵심 스케줄러 파라미터

워크로드별 튜닝 프로파일

아래 값은 출발점 예시입니다. 슬라이스를 늘리면 처리량이, 줄이면 응답성이 유리해지는 방향만 참고하고, 최종 값은 대상 시스템에서 측정해 결정합니다.

## 프로파일 1: 대화형 데스크톱 (최소 지연)
echo 500000 > /sys/kernel/debug/sched/base_slice_ns        # 0.5ms
echo 250000 > /sys/kernel/debug/sched/migration_cost_ns   # 0.25ms

## 프로파일 2: 처리량 최적화 서버 (HPC/배치)
echo 3000000 > /sys/kernel/debug/sched/base_slice_ns        # 3ms
echo 5000000 > /sys/kernel/debug/sched/migration_cost_ns   # 5ms
echo 128 > /sys/kernel/debug/sched/nr_migrate               # 대량 마이그레이션

## 프로파일 3: 데이터베이스 서버 (균형)
echo 1200000 > /sys/kernel/debug/sched/base_slice_ns        # 1.2ms
echo 1000000 > /sys/kernel/debug/sched/migration_cost_ns   # 1ms

## 프로파일 4: 가상화 호스트 (VM 간 공정성)
echo 2000000 > /sys/kernel/debug/sched/base_slice_ns        # 2ms
echo 500000 > /sys/kernel/debug/sched/migration_cost_ns    # 0.5ms (기본값)

sched_autogroup 자동 그룹화

데스크톱 환경에서 CONFIG_SCHED_AUTOGROUP은 TTY 세션별로 자동 task_group을 생성하여, 빌드 같은 CPU 집약 작업이 대화형 세션에 미치는 영향을 최소화합니다.

# autogroup 활성화 여부 확인
cat /proc/sys/kernel/sched_autogroup_enabled
# 1

# 프로세스의 autogroup nice 조정
echo 10 > /proc/self/autogroup  # 현재 세션 그룹 우선순위 낮춤

# autogroup 비활성화 (서버 환경 권장)
sysctl -w kernel.sched_autogroup_enabled=0

sched_tunable_scaling 자동 스케일링

sched_tunable_scaling은 CPU 수가 증가할 때 CFS 파라미터를 자동으로 조정합니다.

# 현재 스케일링 모드 확인 (debugfs)
cat /sys/kernel/debug/sched/tunable_scaling
# 1 (log2 모드)

# CPU 8개 이상 + log2 모드일 때: factor = 1 + ilog2(8) = 4
# sched_base_slice = 0.7ms × 4 = 2.8ms

# 수동 튜닝 시 자동 스케일링 비활성화 권장
echo 0 > /sys/kernel/debug/sched/tunable_scaling

sched_features — 런타임 기능 토글

/sys/kernel/debug/sched/features 파일은 CFS의 내부 기능 플래그를 런타임에 확인하고 변경할 수 있는 인터페이스입니다. 각 플래그는 SCHED_FEAT(이름, 기본값) 매크로로 정의됩니다.

# 현재 활성화된 features 확인 (대문자 = 활성, NO_ 접두사 = 비활성)
cat /sys/kernel/debug/sched/features
# GENTLE_FAIR_SLEEPERS START_DEBIT NEXT_BUDDY NO_LAST_BUDDY CACHE_HOT_BUDDY
# WAKEUP_PREEMPTION NO_NEXT_BUDDY SIS_PROP ...

# 특정 feature 비활성화
echo NO_WAKEUP_PREEMPTION > /sys/kernel/debug/sched/features

# 다시 활성화
echo WAKEUP_PREEMPTION > /sys/kernel/debug/sched/features

활용도 고정(Utilization Clamping, uclamp)

활용도 고정(Utilization Clamping, uclamp)은 태스크와 cgroup이 "최소한 이만큼의 성능은 보장해 달라"와 "이 이상은 쓰지 말아 달라"는 두 가지 힌트를 스케줄러에 전달하는 인터페이스입니다. nice 값이 태스크 사이의 상대 비중만 조절하는 것과 달리, uclamp는 CPU 용량(Capacity) 대비 절대적인 요구 수준을 표현합니다. Linux 5.3에서 도입되었고, 태스크 단위 sched_setattr(2) 인터페이스와 cgroup v2의 cpu.uclamp.min/cpu.uclamp.max를 함께 제공합니다.

왜 필요한가: PELT 활용도의 한계

PELT로 계산한 util_avg는 "과거에 얼마나 바빴는가"의 지수 감쇠 평균입니다. 따라서 다음과 같은 요구를 표현하지 못합니다.

• 짧게 깨어나는 태스크: 오래 잠들다가 수 ms만 실행하는 태스크는 util_avg가 낮게 잡혀 소형 코어나 낮은 주파수에 배치되기 쉽습니다. 실제로는 그 짧은 구간에서 최대 성능이 필요할 수 있습니다.
• 절대 성능 요구: "다른 태스크보다 2배"가 아니라 "CPU 용량의 50% 이상"을 요구하는 경우, nice 값으로는 표현할 수 없습니다.
• 전력 상한: 반대로 "이 태스크는 CPU 용량의 30%를 넘지 않게" 제한하고 싶은 경우도 있습니다.

uclamp는 이 요구를 UCLAMP_MIN/UCLAMP_MAX 두 개의 스칼라(0~1024)로 표현하고, 에너지 인지 스케줄링(Energy Aware Scheduling, EAS)의 util_fits_cpu() 판정과 effective_cpu_util()의 주파수 계산에 반영합니다.

두 개의 값과 유효값 계산

값은 세 계층을 거쳐 유효값으로 정해집니다. 우선순위가 높은(더 제한적인) 쪽이 최종적으로 적용됩니다.

1. 태스크 요청 — task_struct.uclamp_req[UCLAMP_CNT]. sched_setattr(2)로 설정합니다.
2. cgroup 제한 — task_group.uclamp[UCLAMP_CNT]. 태스크 요청값을 [tg_min, tg_max] 범위로 clamp()합니다. 루트 태스크 그룹과 autogroup 소속 태스크에는 적용되지 않습니다.
3. 시스템 기본값 — uclamp_default[UCLAMP_CNT]. kernel.sched_util_clamp_min/max sysctl로 정해지며, 요청값이 이 상한을 넘으면 상한으로 잘립니다.

계산된 유효값은 task_struct.uclamp[UCLAMP_CNT]에 캐시되고, 태스크가 런큐에 등록될 때 버킷(struct uclamp_bucket)에 참조 카운트(Reference Count)로 집계됩니다. 런큐의 struct uclamp_rq는 실행 가능한 태스크들의 값을 MAX 집계하므로, uclamp.min이 높은 태스크가 하나라도 깨어 있으면 그 CPU 전체가 그만큼의 성능을 요구합니다.

인터페이스

세 인터페이스 모두 CONFIG_UCLAMP_TASK가 필요하고, cgroup 파일은 CONFIG_UCLAMP_TASK_GROUP이 추가로 필요합니다. cgroup v2의 cpu.uclamp.* 파일은 루트 cgroup에는 생성되지 않습니다(CFTYPE_NOT_ON_ROOT).

태스크 단위 설정

#define _GNU_SOURCE
#include <linux/sched/types.h>
#include <sys/syscall.h>
#include <unistd.h>
#include <string.h>

int set_uclamp_min(pid_t pid, unsigned int util_min)
{
    struct sched_attr attr;

    memset(&attr, 0, sizeof(attr));
    attr.size = sizeof(attr);
    attr.sched_flags = SCHED_FLAG_KEEP_PARAMS | SCHED_FLAG_UTIL_CLAMP_MIN;
    attr.sched_util_min = util_min;   /* 0 ~ 1024 */

    return syscall(SYS_sched_setattr, pid, &attr, 0);
}

cgroup v2 설정

# cgroup v2 (unified hierarchy) 기준
mkdir -p /sys/fs/cgroup/latency
echo 50.00 > /sys/fs/cgroup/latency/cpu.uclamp.min
echo 80.00 > /sys/fs/cgroup/latency/cpu.uclamp.max
cat /sys/fs/cgroup/latency/cpu.uclamp.min

# 대상 프로세스를 그룹으로 이동
echo $$ > /sys/fs/cgroup/latency/cgroup.procs

cgroup 값은 구성원 태스크의 상한/하한 범위로 동작합니다. 예를 들어 cpu.uclamp.min=50.00이면 구성원이 요청한 min 값은 512 미만으로 내려가지 않고, cpu.uclamp.max=80.00이면 819를 넘지 않습니다. 값은 백분율로 쓰지만 커널 내부에서는 percent << SCHED_CAPACITY_SHIFT를 UCLAMP_PERCENT_SCALE로 나눈 0~1024 스케일로 변환됩니다.

시스템 기본값

기본값이 모두 1024라는 것은 "아무 제한도 걸지 않는다"는 뜻입니다. 따라서 uclamp는 명시적으로 설정하기 전까지 스케줄링에 영향을 주지 않습니다.

주의사항과 트러블슈팅

• 힌트이지 보장이 아닙니다. uclamp.min을 1024로 올려도 해당 CPU가 다른 태스크로 포화 상태라면 즉시 100% 성능을 받는다는 보장은 없습니다. 배치·주파수 판단의 입력으로만 쓰입니다.
• min 상향은 overutilized를 유발합니다. 런큐의 uclamp.min이 커지면 util_fits_cpu()가 "맞지 않음"으로 판정해 EAS의 에너지 최적 배치를 포기하고, 주파수를 높이는 방향으로 동작합니다. 지연에 민감한 소수 태스크에만 제한적으로 적용하세요.
• max 하향은 지연을 늘립니다. 발열·전력 제어에는 유용하지만, 대화형 응답성이 나빠질 수 있습니다. cpu.uclamp.max는 루트가 아닌 cgroup에만 존재하므로, 시스템 전체 상한은 sysctl로 설정합니다.
• 적용 여부 확인: sched_setattr()가 실패하면 errno를 확인합니다. CONFIG_UCLAMP_TASK가 꺼져 있거나 권한이 없으면 요청이 거부됩니다. cgroup 파일이 보이지 않으면 CONFIG_UCLAMP_TASK_GROUP과 unified hierarchy 사용 여부를 확인하세요.
• RT 태스크: RT 정책에는 per-task uclamp가 없고 sched_util_clamp_min_rt_default가 일괄 적용됩니다. RT 스레드의 지연을 낮추려면 이 값을 조정합니다.

NUMA 밸런싱

CFS의 NUMA 밸런싱은 태스크의 메모리 접근 패턴을 분석하여 태스크를 가장 많이 접근하는 메모리가 있는 NUMA 노드로 자동 마이그레이션합니다.

자동 페이지(Page) 마이그레이션 원리

커널은 주기적으로 태스크의 페이지 테이블(Page Table) 엔트리에서 접근 비트(Accessed bit)를 클리어하여, 이후 접근 시 페이지 폴트(Page Fault)를 유발합니다. 이 폴트 핸들러(Handler)에서 접근 통계(numa_faults)를 수집합니다.

/* kernel/sched/fair.c */
struct task_struct {
    /* ... */
    int                      numa_scan_seq;
    unsigned int             numa_scan_period;    /* 스캔 주기 (ms) */
    unsigned int             numa_scan_period_max;
    int                      numa_preferred_nid;  /* 선호 NUMA 노드 */
    unsigned long            numa_migrate_retry;
    u64                      node_stamp;

    /* NUMA 폴트 통계: [노드][CPU/MEM][PRIVATE/SHARED] */
    unsigned long            *numa_faults;
    unsigned long            total_numa_faults;
    struct numa_group        *numa_group;
};

/* NUMA 폴트 핸들러 */
static void task_numa_fault(int last_cpupid,
                            int mem_node, int pages, int flags)
{
    struct task_struct *p = current;
    int cpu_node = task_node(p);
    int priv;

    /* 로컬 vs 원격 폴트 구분 */
    priv = (cpu_node == mem_node);

    /* numa_faults 통계 업데이트 */
    p->numa_faults[task_faults_idx(NUMA_MEM, mem_node, priv)] += pages;
    p->numa_faults[task_faults_idx(NUMA_CPU, cpu_node, priv)] += pages;

    /* 선호 노드 재계산 */
    task_numa_placement(p);
}

NUMA 밸런싱 결정 과정

/* kernel/sched/fair.c — 선호 노드 결정 */
static void task_numa_placement(struct task_struct *p)
{
    int nid, max_nid = NUMA_NO_NODE;
    unsigned long max_faults = 0;

    /* 각 노드별 폴트 수 비교 */
    for_each_online_node(nid) {
        unsigned long faults;
        faults = p->numa_faults[task_faults_idx(NUMA_MEM, nid, 0)]
               + p->numa_faults[task_faults_idx(NUMA_MEM, nid, 1)];

        if (faults > max_faults) {
            max_faults = faults;
            max_nid = nid;
        }
    }

    /* 선호 노드가 변경되면 마이그레이션 트리거 */
    if (max_nid != p->numa_preferred_nid) {
        p->numa_preferred_nid = max_nid;
        p->numa_migrate_retry = jiffies + HZ;
    }
}

NUMA 밸런싱 제어

# NUMA 밸런싱 활성화/비활성화
echo 1 > /proc/sys/kernel/numa_balancing          # 활성화
echo 0 > /proc/sys/kernel/numa_balancing          # 비활성화

# 스캔 주기 (ms) — 폴트 빈도 조절
cat /proc/sys/kernel/numa_balancing_scan_period_min_ms  # 기본: 1000
cat /proc/sys/kernel/numa_balancing_scan_period_max_ms  # 기본: 60000

# 한 번에 스캔할 페이지 크기 (MB)
cat /proc/sys/kernel/numa_balancing_scan_size_mb        # 기본: 256

# NUMA 통계 확인
numastat -p 1234
# Per-node process memory usage (in MBs)
# Node 0: 512.00    Node 1: 1024.00

# NUMA 폴트 카운터 확인
grep numa /proc/vmstat
# numa_hit 15234567
# numa_miss 234567
# numa_foreign 234567
# numa_interleave 12345
# numa_local 14567890
# numa_other 456789

numa_group: 그룹 단위 마이그레이션

공유 메모리를 사용하는 태스크들은 numa_group으로 자동 묶여, 그룹 단위로 최적 노드를 결정합니다. 이는 멀티스레드 애플리케이션의 NUMA 성능을 크게 개선합니다.

/* kernel/sched/fair.c */
struct numa_group {
    refcount_t       refcount;
    spinlock_t       lock;
    int              nr_tasks;
    pid_t            gid;           /* 그룹 대표 PID */
    int              active_nodes;  /* 사용 중인 노드 수 */

    /* 그룹 전체의 NUMA 폴트 통계 */
    unsigned long    total_faults;
    unsigned long    max_faults_cpu;
    unsigned long    faults[];      /* [노드 수 * 2] */
};

/* 같은 페이지에 접근하는 태스크를 자동으로 그룹화 */
static void task_numa_group(struct task_struct *p,
                            int cpupid, int flags,
                            int *priv)
{
    struct task_struct *grp_leader = find_task_by_vpid(cpupid);
    if (grp_leader && grp_leader->numa_group) {
        /* 같은 페이지에 접근 → 그룹 합류 */
        do_numa_group_merge(p, grp_leader->numa_group);
    }
}

NUMA 밸런싱 파라미터 종합

NUMA 밸런싱 실전 사례

# 사례 1: 데이터베이스 서버 — NUMA 밸런싱 최적화
# 빠른 감지 + 작은 스캔 크기 (오버헤드 최소화)
echo 500 > /proc/sys/kernel/numa_balancing_scan_period_min_ms
echo 30000 > /proc/sys/kernel/numa_balancing_scan_period_max_ms
echo 128 > /proc/sys/kernel/numa_balancing_scan_size_mb

# 사례 2: JVM 애플리케이션 — 힙 크기가 큰 경우
# 큰 스캔 크기로 빠른 수렴
echo 2000 > /proc/sys/kernel/numa_balancing_scan_period_min_ms
echo 60000 > /proc/sys/kernel/numa_balancing_scan_period_max_ms
echo 512 > /proc/sys/kernel/numa_balancing_scan_size_mb

# 사례 3: 명시적 NUMA 바인딩 사용 시 — 비활성화
numactl --cpunodebind=0 --membind=0 ./my_app
# 이 경우 자동 밸런싱은 불필요 (명시적 정책 우선)
echo 0 > /proc/sys/kernel/numa_balancing

# NUMA 효과 전후 비교
perf stat -e 'node-loads,node-load-misses,node-stores,node-store-misses' ./benchmark
# node-load-misses가 감소하면 NUMA 밸런싱 효과 있음

# 실시간 NUMA 마이그레이션 모니터링
watch -n 5 'grep -E "numa_(hit|miss|foreign)" /proc/vmstat'
# numa_hit이 증가하고 numa_miss가 감소하면 수렴 중

실전 트러블슈팅 사례

CFS 스케줄러와 관련된 실제 운영 환경의 문제를 진단하고 해결하는 방법을 살펴봅니다.

사례 1: Kubernetes CPU 스로틀링(Throttling) 디버깅

원인: CFS 대역폭 제어(Bandwidth Control)의 100ms 기간(period) 내에 할당된 quota가 소진되면 파드 내 모든 스레드가 그 기간이 끝날 때까지 강제로 슬립됩니다. CPU 요청량을 낮게 설정하거나 burst 트래픽이 발생할 때 자주 나타납니다.

진단 방법:

# 스로틀 비율 확인 (cgroupv2)
cat /sys/fs/cgroup/kubepods/burstable/pod<uid>/cpu.stat
# nr_throttled: 스로틀 발생 횟수
# throttled_usec: 총 스로틀 시간 (마이크로초)

# 스로틀 비율 계산
awk '/nr_periods/{p=$2} /nr_throttled/{t=$2} END{print t/p*100 "% throttled"}' \
    /sys/fs/cgroup/kubepods/.../cpu.stat

# 실시간 모니터링
watch -n 1 "cat /sys/fs/cgroup/kubepods/burstable/pod*/cpu.stat | grep throttled"

해결책:

# Kubernetes Pod spec — CPU request/limit 조정
resources:
  requests:
    cpu: "500m"    # 실제 평균 사용량에 맞게 증가
  limits:
    cpu: "2000m"   # burst 여유를 위해 limit을 request의 4배로

# CFS bandwidth burst 활성화 (커널 5.14+, cgroupv2)
echo 50000 > /sys/fs/cgroup/kubepods/.../cpu.max.burst
# burst 허용량: 50ms — 순간적 스파이크를 budget에서 빌려 처리

# 또는 period를 줄여 granularity 향상 (기본 100ms → 10ms)
echo "200000 10000" > /sys/fs/cgroup/.../cpu.max
# quota 200ms / period 10ms → 20코어 상당

사례 2: 대화형 애플리케이션 지연 스파이크 분석

원인: 배치 작업(Batch job)의 vruntime이 충분히 쌓여 대화형 태스크가 스케줄링되지 못하는 경우, 또는 wakeup preemption이 너무 소극적으로 설정된 경우 발생합니다.

진단 방법:

# p99 스케줄링 지연 측정
perf sched latency -p <pid> -- sleep 10
# Task  | Runtime ms | Switches | Average delay ms | Maximum delay ms

# 런큐 대기 시간 분포 (bpftrace)
bpftrace -e '
tracepoint:sched:sched_wakeup { @ts[args->pid] = nsecs; }
tracepoint:sched:sched_switch {
  if (@ts[args->next_pid]) {
    @us = hist((nsecs - @ts[args->next_pid]) / 1000);
    delete(@ts[args->next_pid]);
  }
}'

# 비자발적 컨텍스트 스위치 빈도 확인
pidstat -w -p <pid> 1
# nvcswch/s 열: 높으면 배치 작업에 의해 선점 빈번

해결책:

# 대화형 태스크를 배치 작업보다 우선: nice 값 조정
renice -n -10 -p <interactive-pid>
renice -n 19  -p <batch-pid>

# 또는 cgroup을 이용해 CPU weight 설정
echo 1024 > /sys/fs/cgroup/interactive/cpu.weight  # 기본 100의 10배
echo 1    > /sys/fs/cgroup/batch/cpu.weight         # 최소 weight

# wakeup granularity 감소 → 더 적극적 선점 (기본 1ms → 0.5ms)
echo 500000 > /proc/sys/kernel/sched_wakeup_granularity_ns

사례 3: NUMA 불균형 해결

진단 방법:

# NUMA 통계 확인
numastat -p <pid>
# numa_hit: 로컬 노드에서 할당된 페이지 수
# numa_miss: 원격 노드에서 할당된 페이지 수 (높으면 문제)

# 프로세스별 NUMA 밸런싱 통계
grep numa /proc/<pid>/sched
# numa_migrations: NUMA 마이그레이션 횟수
# node_0, node_1: 각 노드에서의 실행 시간

# NUMA 밸런싱 이벤트 추적
perf stat -e sched:sched_migrate_task,migrate:mm_migrate_pages -- sleep 10

해결책:

# 특정 NUMA 노드에 프로세스 고정
numactl --cpunodebind=0 --membind=0 ./my_app

# 실행 중인 프로세스의 NUMA 친화성 변경
migratepages <pid> 1 0  # 노드 1 메모리를 노드 0으로 이동

# NUMA 자동 밸런싱 스캔 주기 조정 (ms)
echo 5000 > /proc/sys/kernel/numa_balancing_scan_period_min_ms
echo 60000 > /proc/sys/kernel/numa_balancing_scan_period_max_ms

# 메모리 접근 패턴이 균일하면 interleave 정책 사용
numactl --interleave=all ./my_app

사례 4: CFS 대역폭 과도한 스로틀링

원인: CFS 대역폭 제어는 런큐 단위로 quota를 분배합니다. 많은 CPU를 가진 시스템에서 각 CPU가 조금씩 소비하면 전체 quota가 빠르게 소진될 수 있습니다(bandwidth slack 문제).

진단 방법:

# cgroup별 CPU 대역폭 설정 확인 (cgroupv2)
cat /sys/fs/cgroup/<group>/cpu.max
# "200000 100000" → 100ms 기간에 200ms quota (2 CPU 상당)

# 스로틀 상세 통계
cat /sys/fs/cgroup/<group>/cpu.stat
# nr_periods 1000
# nr_throttled 450   ← 45% 스로틀링 발생!
# throttled_usec 22500000

# 스로틀링 이벤트 실시간 추적
perf trace -e sched:sched_cfs_throttle_cpu -- sleep 5

해결책:

# 1. quota 증가 — 평균 사용량의 1.5~2배 설정 권장
echo "400000 100000" > /sys/fs/cgroup/<group>/cpu.max

# 2. period 단축 — 스로틀 지속 시간 감소 (100ms → 10ms)
echo "40000 10000" > /sys/fs/cgroup/<group>/cpu.max

# 3. burst 허용 (커널 5.14+) — 순간 스파이크를 budget에서 차용
echo 100000 > /sys/fs/cgroup/<group>/cpu.max.burst

# 4. cgroup quota slack 최소화 — bandwidth_slice 크기 축소
echo 1000 > /proc/sys/kernel/sched_cfs_bandwidth_slice_us
# 기본 5000us → 1000us: 런큐당 미리 할당하는 slice 감소
# 효과: quota가 더 균등하게 분배되지만 락 경합 약간 증가

사례 5: EEVDF 환경에서의 꼬리 지연(Tail Latency) 튜닝

Linux 6.6 이후 EEVDF로 전환하면서 기존 CFS의 sched_wakeup_granularity_ns 튜닝이 무효화되어, 일부 대화형 워크로드에서 p99 지연이 증가하는 사례가 보고됩니다. EEVDF에서는 태스크의 slice 값이 deadline을 결정하므로, slice를 통한 명시적 제어가 필요합니다.

# 1. 증상 확인 — wakeup latency 측정 (perf sched timehist)
perf sched record -- sleep 10
perf sched timehist --summary | awk '$NF > 1.0 {print}'
# wait time이 1ms 이상인 태스크 식별

# 2. EEVDF 기본 slice 확인 (Linux 6.6+ 노출)
cat /sys/kernel/debug/sched/base_slice_ns
# 정규화 기본값 750000 (0.75ms). CONFIG_SCHED_TUNABLE_SCALING(LOG) 시
# 2CPU=1.5ms, 4CPU=2.25ms, 8CPU=3ms 로 CPU 수에 따라 스케일되어 표시됨
# 6.15+ 정규화 기본값은 700000 (0.7ms)으로 축소

# 3. 대화형 태스크에 대해 slice를 명시적으로 짧게 설정 (Linux 6.14+)
#    sched_setattr(2)의 sched_runtime이 EEVDF slice로 해석됨 (0.1ms~100ms)
chrt --other --sched-runtime 500000 -p $PID
# 500us slice → 더 이른 deadline → 더 빠른 선점

# 4. DELAY_DEQUEUE 기능 확인 (Linux 6.12+) — 슬립 직전 태스크 lag 보존
cat /sys/kernel/debug/sched/features | grep DELAY_DEQUEUE
# DELAY_DEQUEUE 활성: 짧게 슬립하는 태스크의 vruntime 패널티 완화

# 5. PREEMPT_LAZY (Linux 6.13+) — full preemption 없이 응답성 확보
cat /sys/kernel/debug/sched/preempt
# none / voluntary / full / lazy 중 lazy 선택 시 처리량 손실 최소화

Linux 6.6–7.x 최신 커널 동향

CFS는 Linux 6.6에서 EEVDF로 대체된 이후에도 계속 진화하고 있습니다. kernel/sched/fair.c는 여전히 동일 파일이지만, 알고리즘 동작과 sysctl/디버그 인터페이스가 크게 변경되었습니다. 2026년 4월 Linux 7.0이 출시되며 sched_ext가 핵심 인프라로 자리잡았습니다. 운영 환경에서 신구 커널을 함께 다루려면 다음 변경 사항을 숙지해야 합니다.

제거/추가된 튜닝 인터페이스

DELAY_DEQUEUE — 짧은 슬립 태스크의 공정성 보존

Peter Zijlstra가 Linux 6.12에 머지한 기능으로, 태스크가 슬립할 때 즉시 RB-tree에서 제거하는 대신 lag 정보를 유지합니다. 이를 통해 대화형 워크로드가 짧게 슬립한 뒤 깨어날 때 vruntime이 과도하게 보상되어 다른 태스크를 부당하게 선점하는 문제를 완화합니다.

/* kernel/sched/fair.c (Linux 6.12+, 단순화) */
static bool dequeue_entity(struct cfs_rq *cfs_rq,
                            struct sched_entity *se, int flags)
{
    if (sched_feat(DELAY_DEQUEUE) && (flags & DEQUEUE_SLEEP) &&
        entity_eligible(cfs_rq, se)) {
        /* eligible 상태로 슬립 → 실제 제거를 지연시켜 lag 보존 */
        se->sched_delayed = 1;
        return false;
    }
    /* ... 기존 dequeue 경로 ... */
    __dequeue_entity(cfs_rq, se);
    return true;
}

PREEMPT_LAZY — 처리량과 지연의 절충

Linux 6.13에서 메인라인에 들어온 새로운 선점 모델입니다. 기존 모델은 다음 4가지였습니다.

• PREEMPT_NONE — 시스템 콜(System Call) 반환과 명시적 schedule()에서만 선점(처리량 우선)
• PREEMPT_VOLUNTARY — 일부 might_sleep() 지점에서 추가 선점
• PREEMPT_FULL — 커널 코드 어디서든 선점 가능(저지연 우선)
• PREEMPT_RT — 실시간 스케줄링 보장

PREEMPT_LAZY는 SCHED_NORMAL 태스크에 대해서는 협력적(voluntary)으로 동작하고, SCHED_FIFO/SCHED_RR/SCHED_DEADLINE 같은 RT 태스크에 대해서는 즉시 선점하는 하이브리드입니다. 처리량 손실 없이 RT 응답성을 확보하려는 방향으로 주목받고 있지만, 이를 일반 서버 커널의 확정된 새 기본값으로 단정하기는 어렵습니다. 실제 선택은 커널 설정과 배포판 정책에 좌우됩니다.

sched_ext — BPF 확장 스케줄러의 안정화

Linux 6.12에서 sched_ext(SCX)가 정식 머지되어 BPF 프로그램으로 스케줄러를 작성·교체할 수 있게 되었습니다. CFS/EEVDF를 우회하는 별도 스케줄러 클래스(ext_sched_class)로 동작하며, 런타임에 SCX 프로그램을 로드/언로드할 수 있습니다.

# sched_ext 활성화 여부 확인
cat /sys/kernel/sched_ext/state
# disabled / enabling / enabled 중 하나

# 현재 로드된 BPF 스케줄러 이름
cat /sys/kernel/sched_ext/root/ops

# scx_simple, scx_rusty, scx_lavd 등 참조 구현은 scx 저장소에서 제공
# https://github.com/sched-ext/scx

버전별 변경 요약

6.6 이후 EEVDF 계열의 진화

프록시 실행(Proxy Execution) — Linux 6.17

우선순위 역전은 낮은 우선순위 태스크가 뮤텍스(Mutex)를 보유한 상태에서 높은 우선순위 태스크가 그 뮤텍스를 기다리며 블록될 때 발생합니다. 높은 우선순위 태스크는 뮤텍스를 기다리는 동안 런큐에서 빠지고, 정작 뮤텍스를 풀어 줄 낮은 우선순위 태스크는 CPU를 얻지 못해 시스템 전체가 느려집니다.

전통적인 해법은 우선순위 상속(Priority Inheritance, PI)입니다. rt_mutex가 소유자의 우선순위를 일시적으로 끌어올려 빨리 실행되게 합니다. 프록시 실행은 접근이 다릅니다. 소유자의 우선순위를 바꾸지 않고, 대기자의 스케줄링 컨텍스트(Scheduling Context)를 소유자에게 빌려주어 소유자가 대기자의 우선순위로 실행되게 합니다.

/* kernel/sched/sched.h — Linux v7.3.1 */
struct rq {
    /* ... */
    struct task_struct __rcu *curr;    /* 실제로 CPU를 점유한 태스크 */
    struct task_struct __rcu *donor;   /* 스케줄링 컨텍스트 제공자 */
    /* ... */
};

static inline void rq_set_donor(struct rq *rq, struct task_struct *t)
{
    rcu_assign_pointer(rq->donor, t);
}

/* kernel/sched/sched.h — CONFIG_SCHED_PROXY_EXEC */
DECLARE_STATIC_KEY_TRUE(__sched_proxy_exec);

static inline bool sched_proxy_exec(void)
{
    return static_branch_likely(&__sched_proxy_exec);
}

캐시 인지 로드 밸런싱(SCHED_CACHE) — Linux 7.2

멀티코어 서버에서 같은 프로세스(같은 주소 공간)의 스레드가 서로 다른 LLC(Last Level Cache)에 흩어지면, 공유 데이터가 캐시 간에 복사되며 캐시 미스와 일관성 트래픽이 늘어납니다. CONFIG_SCHED_CACHE는 같은 프로세스의 태스크를 가능하면 하나의 LLC 도메인에 모으는 로드 밸런싱 정책입니다. Kconfig에서 default y, SMP 의존이므로 일반 멀티코어 커널에서는 기본으로 켜집니다.

/* kernel/sched/fair.c — Linux v7.3.1, CONFIG_SCHED_CACHE */
#define EPOCH_PERIOD                (HZ / 100)  /* 10 ms */
#define EPOCH_LLC_AFFINITY_TIMEOUT  5          /* 50 ms */

unsigned int llc_aggr_tolerance         = 1;
unsigned int llc_epoch_period           = EPOCH_PERIOD;
unsigned int llc_epoch_affinity_timeout = EPOCH_LLC_AFFINITY_TIMEOUT;
unsigned int llc_imb_pct                = 20;   /* 불균형 판정 % */
unsigned int llc_overaggr_pct           = 50;  /* 과집적 판정 % */

static inline bool sched_cache_enabled(void)
{
    return static_branch_unlikely(&sched_cache_active);
}

로드 밸런싱 쪽은 두 함수로 나뉩니다. record_sg_llc_stats()는 각 sched_group의 LLC 선호 통계를 sd_llc_shared에 기록하는데, CPU_NEWLY_IDLE 밸런싱에서는 건너뛰고 자식 도메인이 sd_llc인 경우(=여러 LLC를 가로지르는 도메인)에만 동작합니다. 실제 이동 판단을 하는 llc_balance()는 다음 조건을 모두 만족할 때만 참을 반환합니다.

• sched_cache_enabled()가 참일 것(기능 활성)
• 도메인에 SD_SHARE_LLC가 없을 것 — 같은 LLC 내부 도메인은 캐시 집적을 고려할 필요가 없습니다
• SD_ASYM_CPUCAPACITY 도메인에서 misfit 태스크가 있으면 분산을 우선하고 집적은 포기
• nr_balance_failed가 cache_nice_tries + 1 이상이면 태스크 이주 폭주를 막기 위해 중단

# 기능 활성 여부와 파라미터
ls /sys/kernel/debug/sched/llc_balancing/
cat /sys/kernel/debug/sched/llc_balancing/enabled

# 집적 허용 오차와 불균형 임계값 조정
echo 0 > /sys/kernel/debug/sched/llc_balancing/aggr_tolerance
echo 30 > /sys/kernel/debug/sched/llc_balancing/imb_pct

# 기능 끄기 (기본 로드 밸런싱으로 복귀)
echo 0 > /sys/kernel/debug/sched/llc_balancing/enabled

참고자료

커널 문서

• CFS Scheduler Design — CFS의 설계 철학, vruntime 개념, 공정성 원칙을 설명하는 커널 공식 문서입니다
• EEVDF Scheduler — Linux 6.6 이후 기본 스케줄러인 EEVDF의 lag/eligibility/virtual deadline 원리를 설명하는 공식 문서입니다
• Scheduler 문서 인덱스 — 리눅스 커널 스케줄러 관련 공식 문서 전체 목록입니다
• Nice Design — nice 값과 가중치(weight) 매핑 설계를 설명하는 공식 문서입니다
• CFS Bandwidth Control — cgroup 기반 CFS 대역폭 제어(quota, period, burst)의 공식 문서입니다
• Scheduler Statistics — /proc/schedstat 및 스케줄러 통계 수집 방법을 설명하는 공식 문서입니다
• Scheduler Domains — NUMA 토폴로지 기반 로드 밸런싱 도메인 구조를 설명하는 공식 문서입니다
• Energy Aware Scheduling — CFS와 연동되는 에너지 인식 스케줄링(EAS) 공식 문서입니다

LWN 기사

• LWN: Schedulers — the plot thickens — Ingo Molnár가 CFS를 처음 제안한 배경과 O(1) 스케줄러와의 비교를 다루는 기사입니다
• LWN: An EEVDF CPU scheduler for Linux — CFS를 대체하는 EEVDF 알고리즘 도입 과정과 기존 CFS와의 차이를 분석합니다
• LWN: Per-entity load tracking — PELT(Per-Entity Load Tracking) 도입으로 CFS 로드 밸런싱이 개선된 과정을 설명합니다
• LWN: CFS group scheduling — cgroup 기반 그룹 스케줄링과 공정성 계층 구조를 다루는 기사입니다
• LWN: CFS bandwidth control — CFS 대역폭 제어 메커니즘의 설계와 구현을 설명하는 기사입니다
• LWN: Latency-nice as a replacement for autogroups — latency-nice 파라미터를 통한 CFS 지연 시간 튜닝을 논의합니다
• LWN: Fixing the CFS scheduler — CFS 초기 도입 이후 발견된 공정성 문제와 수정 사항을 다룹니다
• LWN: The many faces of "latency nice" — CFS 태스크의 지연 시간 우선순위 제어 논의를 정리합니다
• LWN: Core scheduling — SMT 환경에서 CFS의 코어 스케줄링 보안 기능을 설명합니다
• LWN: The extensible scheduler class — Linux 6.12에 머지된 sched_ext의 설계와 BPF 기반 스케줄러 작성 방법을 다룹니다
• LWN: Scheduling for the age of heterogeneous computing — EEVDF 이후 이종 코어(P/E core) 환경에서의 CFS 진화 방향을 정리합니다
• LWN: Lazy preemption — Linux 6.13의 PREEMPT_LAZY 모델 도입 배경과 처리량/지연 트레이드오프를 분석합니다
• LWN: Delayed dequeue for EEVDF — DELAY_DEQUEUE 기능이 EEVDF의 공정성을 어떻게 개선하는지 설명합니다
• Phoronix: Linux 6.8 Scheduler Changes — EEVDF Fast Path(O(1) task selection) 추가 및 추가 스케줄러 튜닝 내용을 다룹니다
• Phoronix: Sched_Ext Changes for Linux 6.15 — ttwu_queue 선택적 토글, 내부 이벤트 카운터 추가 등 6.15 sched_ext 변경 사항을 정리합니다
• Phoronix: Sched_Ext CPU Selection Improvements in Linux 6.16 — scx_bpf_select_cpu_and() 추가와 계층형 스케줄러 기반 작업을 다룹니다
• Phoronix: Linux 6.18 sched_ext Cgroup Sub-Scheduler Prep — cgroup 서브스케줄러 준비 작업과 새 BPF 헬퍼 추가를 설명합니다
• Phoronix: Linux 7.1 sched_ext Cgroup Sub-Scheduler Groundwork — 계층형 SCX 구현을 위한 7.1 내부 구조 재편을 다룹니다
• Phoronix: Linux 7.0 Scheduler Updates Land Time Slice Extension, Performance & Scalability Work — RSEQ Time Slice Extension 병합과 스케줄러 확장성 개선을 정리합니다
• LWN: Scheduler time slice extension — RSEQ 기반 타임슬라이스 확장 메커니즘의 설계와 구현을 설명하는 기사입니다
• Phoronix: Linux 7.0 To Focus Just On Full & Lazy Preemption Models For Up-To-Date CPU Archs — 최신 아키텍처에서 PREEMPT_NONE/VOLUNTARY 제거 과정을 설명합니다
• Phoronix: AWS Engineer Reports PostgreSQL Performance Halved By Linux 7.0 — Linux 7.0 선점 모델 변경으로 인한 PostgreSQL 성능 저하 보고 및 분석입니다
• LWN: Improved load balancing with machine learning — sched_ext 기반 ML 부하 분산 스케줄러의 설계와 동작을 설명하는 기사입니다
• KernelNewbies: Linux 7.0 — v7.0 릴리스 요약으로 RSEQ Time Slice Extension 및 선점 모델 재편을 포함합니다

커널 소스

• kernel/sched/fair.c — CFS 핵심 구현 코드입니다. enqueue/dequeue, pick_next_task, vruntime 계산 등이 포함됩니다
• kernel/sched/core.c — 스케줄러 코어 로직으로 schedule(), context_switch() 등이 구현되어 있습니다
• kernel/sched/sched.h — cfs_rq, rq 등 스케줄러 내부 자료구조가 정의되어 있습니다
• kernel/sched/pelt.c — PELT(Per-Entity Load Tracking) 부하 추적 알고리즘 구현 코드입니다
• include/linux/sched.h — task_struct와 스케줄링 관련 필드 정의가 포함된 헤더 파일입니다