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) 스케줄러입니다.

핵심 원칙

• 완전한 공정성(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 계산

/* 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;

    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 테이블

static int entity_before(struct sched_entity *a, struct sched_entity *b)
{
    return (s64)(a->vruntime - b->vruntime) < 0;
}

Red-Black Tree 구조

CFS는 각 CPU의 실행 큐(runqueue)에서 vruntime을 키로 하는 Red-Black Tree를 관리합니다.

sched_entity 구조체(Struct)

/* include/linux/sched.h */
struct sched_entity {
    struct load_weight   load;           /* 우선순위 가중치 */
    unsigned long        runnable_weight;
    struct rb_node        run_node;       /* RB 트리 노드 */
    u64                  exec_start;     /* 마지막 실행 시작 시각 */
    u64                  sum_exec_runtime; /* 누적 실행 시간 */
    u64                  vruntime;       /* 가상 런타임 */
    u64                  prev_sum_exec_runtime;

    struct sched_statistics statistics;
    struct sched_entity   *parent;        /* 그룹 스케줄링용 */
    struct cfs_rq         *cfs_rq;        /* 소속 CFS 런큐 */
    struct cfs_rq         *my_q;          /* 그룹인 경우 자식 런큐 */
};

트리 구조 시각화

다음 태스크 선택 (pick_next_task)

스케줄러의 핵심 동작은 가장 작은 vruntime을 가진 태스크를 선택하는 것입니다.

pick_next_entity 구현

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

    /* leftmost 노드 = RB 트리 최좌측 = 최소 vruntime */
    if (left) {
        se = left;
    }

    return se;
}

static struct sched_entity *
__pick_first_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);
}

스케줄링 흐름

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

타임슬라이스와 지연시간

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

핵심 파라미터

타임슬라이스 계산

/* kernel/sched/fair.c */
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% 할당
 */

부하 분산 (Load Balancing)

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

부하 분산 트리거

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

load_balance 핵심 로직

/* kernel/sched/fair.c */
static int load_balance(int this_cpu, struct rq *this_rq,
                         struct sched_domain *sd,
                         enum cpu_idle_type idle)
{
    struct rq *busiest;
    struct lb_env env = {
        .sd             = sd,
        .dst_cpu        = this_cpu,
        .dst_rq         = this_rq,
        .idle           = idle,
    };

    /* 1. 가장 바쁜 CPU 찾기 */
    busiest = find_busiest_queue(&env);
    if (!busiest)
        goto out_balanced;

    /* 2. 이동할 태스크 선택 */
    env.src_cpu = busiest->cpu;
    env.src_rq = busiest;
    detach_tasks(&env);

    /* 3. 태스크 이동 */
    if (!list_empty(&env.tasks))
        attach_tasks(&env);

    return 1;

out_balanced:
    return 0;
}

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 스케줄링 클래스의 tick 핸들러로, 모든 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을 갱신하고, check_preempt_tick()으로 선점 여부를 결정합니다.

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    /* vruntime 및 부하 가중치 갱신 */
    update_curr(cfs_rq);

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

    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr); /* 태스크가 2개 이상일 때만 */
}

깨우기 선점(Wakeup Preemption) 상세

태스크가 슬립 상태에서 깨어날 때(wake-up), CFS는 현재 실행 중인 태스크를 선점할지 결정합니다. 이 결정은 check_preempt_wakeup()에서 수행됩니다.

/* kernel/sched/fair.c — wakeup 선점 진입점 */
static void check_preempt_wakeup(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 = task_cfs_rq(curr);
    int scale = cfs_rq->nr_running >= sched_nr_latency;
    int next_buddy_marked = 0;

    /* 현재 태스크가 SCHED_IDLE이면 항상 선점 */
    if (unlikely(curr->policy == SCHED_IDLE) &&
        likely(p->policy != SCHED_IDLE))
        goto preempt;

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

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

    /* NEXT_BUDDY: 방금 깨어난 태스크를 다음 실행 후보로 힌트 */
    if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
        set_next_buddy(pse);
        next_buddy_marked = 1;
    }

    if (!wakeup_preempt_entity(se, pse))
        return;  /* 선점 조건 미충족 */

preempt:
    resched_curr(rq);           /* TIF_NEED_RESCHED 설정 */

    /* LAST_BUDDY: 선점된 현재 태스크를 나중 실행 후보로 힌트 */
    if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
        set_last_buddy(se);
}

wakeup_preempt_entity()는 두 엔티티의 vruntime 차이가 sysctl_sched_wakeup_granularity보다 클 때 선점을 허용합니다.

/* 깨어난 태스크(s)가 현재 태스크(curr)를 선점할 수 있는지 판단 */
static int
wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
    s64 gran, vdiff = curr->vruntime - se->vruntime;

    /* 깨어난 태스크의 vruntime이 더 작지 않으면 선점 불가 */
    if (vdiff <= 0)
        return 0;

    /* vruntime 차이가 granularity보다 커야 선점 허용 */
    gran = wakeup_gran(se);
    if (vdiff > gran)
        return 1;

    return 0;
}

모니터링

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    |

성능 튜닝

CFS 파라미터를 조정하여 워크로드에 맞게 최적화할 수 있습니다.

튜닝 파라미터

워크로드별 권장 설정

# 낮은 지연, 빠른 응답
echo 2000000 > /proc/sys/kernel/sched_latency_ns          # 2ms
echo 500000 > /proc/sys/kernel/sched_min_granularity_ns   # 0.5ms
echo 500000 > /proc/sys/kernel/sched_wakeup_granularity_ns # 0.5ms

# 높은 처리량, 지연 허용
echo 24000000 > /proc/sys/kernel/sched_latency_ns          # 24ms
echo 3000000 > /proc/sys/kernel/sched_min_granularity_ns   # 3ms
echo 4000000 > /proc/sys/kernel/sched_wakeup_granularity_ns # 4ms

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 기능으로 이를 제한합니다.

그룹 스케줄링

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.6+) */
#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 토폴로지(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의 예상 대기 시간을 비교해 더 빠를 쪽을 선택합니다.

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 상세 분석

/* include/linux/sched.h (Linux 6.x) */
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 구조체 분석

/* kernel/sched/sched.h */
struct cfs_rq {
    /* === 부하 정보 === */
    struct load_weight   load;          /* 런큐 내 총 가중치 */
    unsigned int        nr_running;     /* 실행 가능 태스크 수 */
    unsigned int        h_nr_running;   /* 계층적 총 태스크 수 */

    /* === 실행 시간 === */
    u64                 exec_clock;     /* 런큐 누적 실행 시간 */
    u64                 min_vruntime;   /* 최소 vruntime 추적 */

    /* === RB-tree === */
    struct rb_root_cached tasks_timeline; /* 태스크 트리 */

    /* === 현재 실행 엔티티 === */
    struct sched_entity  *curr;          /* 현재 실행 중 */
    struct sched_entity  *next;          /* 다음 실행 힌트 */
    struct sched_entity  *last;          /* 마지막 깨운 엔티티 */
    struct sched_entity  *skip;          /* 건너뛸 엔티티 */

    /* === PELT === */
    struct sched_avg     avg;

    /* === Bandwidth Control === */
    int                 runtime_enabled;
    s64                 runtime_remaining; /* 남은 quota */
    int                 throttled;         /* 스로틀 여부 */
    int                 throttle_count;

    /* === 그룹 스케줄링 === */
    struct task_group    *tg;             /* 소속 task_group */
};

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은 다른 태스크를 장시간 기아 상태로 만들 수 있기 때문에 적절한 패널티/보상 메커니즘이 필요합니다.

/* 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() — 페이지 테이블 전환

x86_64에서 페이지 테이블 전환은 CR3 레지스터를 새 태스크의 PGD(Page Global Directory) 물리 주소로 덮어쓰는 것으로 이루어집니다. CR3 쓰기는 자동으로 TLB 전체 플러시를 유발합니다(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()는 어셈블리 매크로로 구현된 __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)에 대한 정리를 수행합니다.

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 모니터링 등)

sysctl 튜닝 파라미터 상세

CFS의 동작을 세밀하게 조정하는 모든 sysctl 파라미터를 정리합니다. 각 파라미터의 기본값, 효과, 워크로드별 권장값을 포함합니다.

핵심 CFS 파라미터

워크로드별 튜닝 프로파일

## 프로파일 1: 대화형 데스크톱 (최소 지연)
sysctl -w kernel.sched_latency_ns=3000000           # 3ms
sysctl -w kernel.sched_min_granularity_ns=300000    # 0.3ms
sysctl -w kernel.sched_wakeup_granularity_ns=500000 # 0.5ms
sysctl -w kernel.sched_migration_cost_ns=250000    # 0.25ms

## 프로파일 2: 처리량 최적화 서버 (HPC/배치)
sysctl -w kernel.sched_latency_ns=24000000          # 24ms
sysctl -w kernel.sched_min_granularity_ns=3000000   # 3ms
sysctl -w kernel.sched_wakeup_granularity_ns=4000000 # 4ms
sysctl -w kernel.sched_migration_cost_ns=5000000   # 5ms
sysctl -w kernel.sched_nr_migrate=128               # 대량 마이그레이션

## 프로파일 3: 데이터베이스 서버 (균형)
sysctl -w kernel.sched_latency_ns=12000000          # 12ms
sysctl -w kernel.sched_min_granularity_ns=1500000   # 1.5ms
sysctl -w kernel.sched_wakeup_granularity_ns=2000000 # 2ms
sysctl -w kernel.sched_migration_cost_ns=1000000   # 1ms

## 프로파일 4: 가상화 호스트 (VM 간 공정성)
sysctl -w kernel.sched_latency_ns=10000000          # 10ms
sysctl -w kernel.sched_min_granularity_ns=2000000   # 2ms
sysctl -w kernel.sched_migration_cost_ns=500000    # 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 파라미터를 자동으로 조정합니다.

# 현재 스케일링 모드 확인
cat /proc/sys/kernel/sched_tunable_scaling
# 1 (log2 모드)

# 64코어 시스템에서의 자동 스케일링 예:
# log2(64) = 6, factor = 1 + 6 = 7
# sched_latency = 6ms × 7 = 42ms
# sched_min_granularity = 0.75ms × 7 = 5.25ms

# 수동 튜닝 시 자동 스케일링 비활성화 권장
echo 0 > /proc/sys/kernel/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

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가 더 균등하게 분배되지만 락 경합 약간 증가

참고 링크

커널 문서

• CFS Scheduler Design — CFS의 설계 철학, vruntime 개념, 공정성 원칙을 설명하는 커널 공식 문서입니다
• 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의 코어 스케줄링 보안 기능을 설명합니다

커널 소스

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

관련 문서

• EEVDF 스케줄러 — CFS를 대체한 EEVDF 알고리즘과 구현
• sched_ext — BPF 확장 스케줄러 — BPF 기반 커스텀 스케줄러
• 프로세스 스케줄러 — 스케줄러 전체 개요
• 프로세스 관리 — 프로세스 생명주기
• Context Switching — 프로세스 전환 메커니즘
• 실시간 스케줄링 — SCHED_FIFO, SCHED_RR, SCHED_DEADLINE
• CPU Sets — CPU 파티셔닝
• Control Groups — 리소스 제어
• Preempt Count — 선점 카운터와 스케줄링 판단