EEVDF 스케줄러(Scheduler)

Earliest Eligible Virtual Deadline First(EEVDF) 스케줄러는 Linux 6.6에서 CFS의 핵심 pick 로직을 대체한 공정 스케줄링 알고리즘입니다. 1995년 Stoica와 Abdel-Wahab이 제안한 이론적 모델을 Peter Zijlstra가 커널에 구현한 과정, eligible 조건 판정, virtual deadline 계산, lag 추적, slice 기반 선점(Preemption) 메커니즘, augmented RB-Tree 구조, 그룹 스케줄링 상호작용, latency nice 확장, CFS 대비 성능 특성과 튜닝 전략을 커널 소스 기반으로 심층 분석합니다.

EEVDF 논문과 역사

EEVDF(Earliest Eligible Virtual Deadline First)는 1996년 Ion Stoica와 Hussein Abdel-Wahab이 발표한 비례 공유 자원 할당 알고리즘입니다. 원래 네트워크 패킷(Packet) 스케줄링(WFQ, WF2Q)의 맥락에서 제안되었으며, CPU 스케줄링에도 적용 가능한 범용 프레임워크입니다.

논문에서 커널까지의 타임라인

논문 이론 vs 커널 구현 차이

kernel/sched/fair.c의 EEVDF 도입 커밋 메시지 요약입니다 (2023, sched/fair: Add EEVDF scheduling).

EEVDF는 eligible 조건과 virtual deadline을 통해 CFS보다 더 나은 지연 보장을 제공합니다. 핵심 변경 사항은 다음과 같습니다.

1. pick_next_entity()가 leftmost(min vruntime) 대신 eligible 태스크 중 earliest deadline을 선택합니다.
2. sched_entity에 deadline, slice 필드가 추가되었습니다.
3. RB-Tree에 min_deadline augmentation이 추가되었습니다.
4. place_entity()에서 lag 기반 배치를 수행합니다.

CFS와의 핵심 차이점

EEVDF는 CFS의 인프라(vruntime, sched_entity, cfs_rq, PELT, cgroup bandwidth)를 그대로 활용하면서 태스크 선택 로직만 근본적으로 변경했습니다. CFS가 "가장 작은 vruntime"을 선택했다면, EEVDF는 "eligible한 태스크 중 가장 이른 deadline"을 선택합니다.

/* CFS의 pick_next_entity (v6.5 이전) — 단순화 */
static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    return rb_entry(left, struct sched_entity, run_node);
    /* → 항상 min vruntime (leftmost) 반환 */
}

/* EEVDF의 pick_eevdf (v6.6+) — 단순화 */
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq)
{
    /* eligible 조건을 만족하면서 deadline이 가장 이른 태스크 */
    struct sched_entity *best = NULL;
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;

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

        if (entity_eligible(cfs_rq, se)) {
            best = se;  /* 더 이른 deadline 후보 탐색 */
            node = node->rb_left;
        } else {
            node = node->rb_right;
        }
    }
    return best;
}

가상 시간 체계

EEVDF의 가상 시간 체계는 세 가지 핵심 요소로 구성됩니다: 가상 실행 시간(vruntime), 가상 마감 시간(virtual deadline), 자격 시간(eligible time). 이 세 값의 관계가 EEVDF의 스케줄링 결정을 완전히 결정합니다.

가상 시간이란 무엇인가

스케줄러가 "공정하게" CPU를 나누려면 서로 다른 가중치(priority)를 가진 태스크들의 진행 속도를 하나의 공통 척도로 비교할 방법이 필요합니다. 실제 물리적 시간(wall-clock time)을 쓰면, 가중치가 높은 태스크는 CPU를 더 많이 받으므로 단순 비교가 불가능합니다.

가상 시간(virtual time)은 이 문제를 해결하는 정규화된 시계입니다. 각 태스크는 CPU를 실제로 1ms 사용해도, 자신의 가중치에 반비례해 vruntime이 증가합니다. 가중치가 2배인 태스크는 같은 CPU 시간을 써도 vruntime이 절반만 늘어납니다. 이 덕분에 스케줄러는 vruntime을 비교하는 것만으로 "누가 자신의 공정한 몫보다 적게 받았는가"를 즉시 판단할 수 있습니다.

• V(t) — 시스템 가상 시간: 현재 실행 중인 모든 태스크의 vruntime 가중 평균값입니다. "시스템 전체가 가상 시간 기준으로 얼마나 진행되었는가"를 나타내는 공통 기준점입니다.
• VE (eligible time) — 자격 시작 시간: 태스크가 마지막 서비스를 받았던 시점의 V(t)입니다. 시스템 가상 시간이 이 값 이상이 되어야 해당 태스크가 선택 대상(eligible)이 됩니다.
• VD (virtual deadline) — 가상 마감 시간: VE에 slice / weight를 더한 값입니다. 이 기한 안에 태스크의 서비스가 완료되어야 합니다. EEVDF는 eligible한 태스크 중 VD가 가장 이른 것을 선택합니다.
• lag — 서비스 편차: "이상적으로 받았어야 할 서비스"와 "실제로 받은 서비스"의 차이입니다. lag > 0이면 덜 받은 것, lag < 0이면 더 받은 것입니다. lag가 양수인 태스크만 eligible이 됩니다.

수식 정의

/* kernel/sched/fair.c — avg_vruntime: 시스템 가상 시간의 가중 평균 */
static s64 avg_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 avg = cfs_rq->avg_vruntime;
    long load = cfs_rq->avg_load;

    if (curr && curr->on_rq) {
        unsigned long weight = scale_load_down(curr->load.weight);
        avg += entity_key(cfs_rq, curr) * weight;
        load += weight;
    }

    if (load)
        avg = div_s64(avg, load);

    return avg;
}

/* avg_vruntime = Σ(key_i × weight_i) / Σ(weight_i)
 * 여기서 key_i = se->vruntime - cfs_rq->min_vruntime
 * 이 값이 EEVDF의 V(t)에 해당 */

/* entity_key: RB-Tree 키 = vruntime - min_vruntime */
static s64 entity_key(struct cfs_rq *cfs_rq,
                       struct sched_entity *se)
{
    return (s64)(se->vruntime - cfs_rq->min_vruntime);
}

Eligible 조건 판정

EEVDF에서 태스크가 실행 대상이 되려면 먼저 eligible(자격) 조건을 충족해야 합니다. 이는 해당 태스크가 공정한 몫보다 적게 서비스를 받았는지(양의 lag) 판단하는 것입니다.

왜 Eligible 조건이 필요한가

EEVDF는 "deadline이 가장 이른 태스크를 선택"하는 알고리즘입니다. 그런데 eligible 조건 없이 무조건 deadline만 보면 어떤 문제가 생길까요?

예를 들어, 동일 가중치(weight)의 태스크 A, B, C 세 개가 있다고 합시다. B가 짧은 I/O 대기 후 막 깨어났고, 그동안 A와 C는 계속 CPU를 받았습니다. 깨어난 B는 새 deadline을 받는데, 이 값이 A나 C의 deadline보다 이를 수 있습니다. eligible 조건이 없다면 B는 깨어나자마자 A와 C를 밀어내고 CPU를 독점하게 됩니다. 이는 자다 깨어났다는 이유만으로 높은 우선순위를 얻는 셈이므로 공정하지 않습니다.

eligible 조건은 이 문제를 차단합니다. "지금까지 공정한 몫보다 실제로 적게 받은 태스크만" 선택 후보가 될 수 있습니다. B가 I/O 대기 중에는 CPU를 전혀 못 받았으므로 lag가 크게 양수가 되어 당연히 eligible입니다. 그러나 B가 이미 충분히 CPU를 받은 상황(lag < 0)이라면 deadline이 빨라도 선택되지 않습니다.

수학적 정의

논문에서 태스크 i가 eligible한 조건은:

V(t) >= VE_i    (시스템 가상 시간이 태스크의 eligible time 이상)

여기서:
  V(t) = 시스템 가상 시간 (모든 태스크의 가중 평균 vruntime)
  VE_i = 태스크 i의 마지막 서비스 종료 시점의 V(t)

동치 조건:
  lag_i = S_ideal_i(t) - S_actual_i(t) >= 0

즉, 공정한 몫보다 적게 받은 태스크만 eligible

커널 구현: entity_eligible()

/* kernel/sched/fair.c — EEVDF eligible 조건 판정
 *
 * 태스크가 eligible ↔ vruntime <= avg_vruntime
 *
 * avg_vruntime = Σ(key_i × w_i) / Σ(w_i)
 * key_i = se->vruntime - min_vruntime
 *
 * 정수 연산 최적화:
 * se->vruntime <= avg_vruntime
 * ↔ (se->vruntime - min_vruntime) × Σ(w_i) <= Σ(key_i × w_i)
 * ↔ entity_key(se) × load <= avg_vruntime_sum
 */
static int entity_eligible(struct cfs_rq *cfs_rq,
                           struct sched_entity *se)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 avg = cfs_rq->avg_vruntime;
    long load = cfs_rq->avg_load;

    if (curr && curr->on_rq) {
        unsigned long weight = scale_load_down(curr->load.weight);
        avg += entity_key(cfs_rq, curr) * weight;
        load += weight;
    }

    return entity_key(cfs_rq, se) * load <= avg;
}

avg_vruntime 유지

/* kernel/sched/fair.c — 간략화 */
static void avg_vruntime_add(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    unsigned long weight = scale_load_down(se->load.weight);
    s64 key = entity_key(cfs_rq, se);

    cfs_rq->avg_vruntime += key * weight;
    cfs_rq->avg_load += weight;
}

static void avg_vruntime_sub(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    unsigned long weight = scale_load_down(se->load.weight);
    s64 key = entity_key(cfs_rq, se);

    cfs_rq->avg_vruntime -= key * weight;
    cfs_rq->avg_load -= weight;
}

/* min_vruntime 업데이트 시에도 avg_vruntime 보정 필요:
 * key_i = se->vruntime - min_vruntime이므로
 * min_vruntime이 변하면 모든 key가 변함
 * → Σ(key_i × w_i) 보정 */
static void avg_vruntime_update(struct cfs_rq *cfs_rq, s64 delta)
{
    /* min_vruntime이 delta만큼 전진 →
     * 모든 key가 -delta → Σ(key×w)가 -delta×Σw */
    cfs_rq->avg_vruntime -= cfs_rq->avg_load * delta;
}

Virtual Deadline 계산

Virtual deadline은 태스크의 서비스 완료 기한을 나타냅니다. weight가 큰(우선순위(Priority) 높은) 태스크일수록 더 짧은 간격(이른 deadline)을 갖게 되어 자주 선택됩니다.

계산 공식

VD = VE + slice / weight

여기서:
  VD    = virtual deadline
  VE    = eligible time (= 현재 vruntime, 대략적으로)
  slice = 요청 실행 시간 (sched_base_slice_ns 기반)
  weight = nice → sched_prio_to_weight[] 변환 값

예시 (sched_base_slice_ns = 3ms = 3,000,000 ns):
  nice 0 (weight 1024):  VD = VE + 3,000,000 / 1024 = VE + 2,929
  nice -5 (weight 3121): VD = VE + 3,000,000 / 3121 = VE + 961
  nice 5 (weight 335):   VD = VE + 3,000,000 / 335  = VE + 8,955

→ nice -5 태스크는 VD가 VE에 가까워 더 자주/먼저 선택됨

/* kernel/sched/fair.c — deadline 설정 (slice/weight 계산) */
static void update_deadline(struct cfs_rq *cfs_rq,
                            struct sched_entity *se)
{
    if ((s64)(se->vruntime - se->deadline) >= 0) {
        /* 이전 deadline을 넘겼으면 새 deadline 설정 */
        se->deadline = se->vruntime +
                       calc_delta_fair(se->slice, se);
        /*
         * calc_delta_fair(delta, se) = delta * NICE_0_LOAD / se->load.weight
         * → slice를 weight로 나눈 가상 시간 단위
         * → weight가 클수록 deadline이 가까워짐
         */
    }
}

/* se->slice: 실제 실행 시간 단위 (nanoseconds)
 * 기본값 = sysctl_sched_base_slice (기본 3ms)
 * latency_nice에 의해 조정 가능 */

Lag 추적 메커니즘

Lag는 EEVDF의 공정성 척도입니다. 각 태스크의 이상적 서비스(ideal service)와 실제 서비스(actual service)의 차이를 추적합니다.

A/B 두 프로세스로 이해하는 Lag

추상적인 수식보다 구체적인 예시로 먼저 lag의 직관을 잡겠습니다. 동일한 가중치(weight = 1024, nice = 0)를 가진 프로세스 A와 B 두 개가 실행 중인 상황을 가정합니다. 물리 CPU가 하나뿐이므로 이상적인 공정 분배라면 A와 B 각각이 50%씩 CPU를 받아야 합니다.

이 예시에서 lag가 하는 역할을 명확히 볼 수 있습니다.

• A가 연속으로 3ms를 받고 나면 lag가 음수(-1.5ms)가 됩니다. A는 이미 공정한 몫 이상을 받았으므로 ineligible이 되어 스케줄러가 선택하지 않습니다.
• B는 그 3ms 동안 한 번도 CPU를 못 받았으므로 lag가 양수(+1.5ms)입니다. B는 eligible이 되어 다음 실행 대상으로 선택됩니다.
• B가 3ms를 받고 나면 두 태스크의 lag가 다시 0으로 돌아옵니다. 공정성이 자동으로 회복됩니다.

이제 가중치가 다른 경우도 생각해 봅시다. A의 가중치가 B의 2배라면, A는 CPU의 2/3을, B는 1/3을 받아야 공정합니다. 1ms 동안 A가 실행되면 A의 vruntime은 상대적으로 더 느리게 증가하고, B의 lag는 1/3 × 1ms = 0.33ms만 증가합니다. 가중치가 반영된 비율로 lag가 쌓이므로, 가중치가 다르더라도 동일한 eligible 판정 공식이 공정하게 작동합니다.

Lag 정의

lag_i(t) = S_ideal_i(t) - S_actual_i(t)

S_ideal_i(t) = w_i / W × (t - t_0)    (공정 비율 × 경과 시간)
S_actual_i(t) = se->vruntime 기반      (실제 받은 서비스)

lag > 0 : 태스크가 공정 몫보다 적게 받음 → eligible (우선 서비스)
lag = 0 : 정확히 공정하게 받음
lag < 0 : 태스크가 공정 몫보다 많이 받음 → ineligible (대기)

EEVDF의 보장:
  |lag_i(t)| <= r_max    (r_max = 최대 요청 크기)
  → lag가 무한히 커지지 않음, 기아(starvation) 방지

/* kernel/sched/fair.c — lag 계산 */
static s64 entity_lag(u64 avruntime, struct sched_entity *se)
{
    s64 vlag, limit;

    /* lag = avg_vruntime - se->vruntime
     * 양수 = 평균보다 뒤처짐 = 덜 받음 = eligible
     * 음수 = 평균보다 앞섬 = 더 받음 = ineligible */
    vlag = avruntime - se->vruntime;

    /* lag 상한 제한: |lag| <= slice */
    limit = calc_delta_fair(se->slice, se);
    return clamp(vlag, -limit, limit);
}

pick_next_entity() 구현

EEVDF의 핵심 함수인 pick_eevdf()는 eligible한 태스크 중 가장 이른 virtual deadline을 가진 태스크를 O(log N)에 찾습니다. 이를 위해 augmented RB-Tree의 min_deadline 보조 키를 활용합니다.

/* kernel/sched/fair.c — pick_eevdf 전체 구현 */
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 *se = __pick_first_entity(cfs_rq);
    struct sched_entity *curr = cfs_rq->curr;
    struct sched_entity *best = NULL;

    /* cfs_rq->curr가 eligible하고 deadline이 빠르면 유지 */
    if (curr && curr->on_rq &&
        entity_eligible(cfs_rq, curr))
        best = curr;

    /* leftmost가 eligible이면 이것이 최선일 가능성 높음 */
    if (se && entity_eligible(cfs_rq, se) &&
        (!best || deadline_gt(best, se)))
        best = se;

    if (best) {
        /* best의 deadline이 서브트리 min보다 작으면 탐색 불필요 */
        if (!node || deadline_gt(__node_2_se(node), best))
            goto found;
    }

    /* Augmented RB-Tree 탐색: eligible + earliest deadline */
    while (node) {
        struct sched_entity *se = __node_2_se(node);

        /* 왼쪽 서브트리에 더 이른 min_deadline이 있으면 왼쪽으로 */
        if (node->rb_left &&
            vruntime_eligible(cfs_rq,
                __node_2_se(node->rb_left)->min_deadline)) {
            node = node->rb_left;
            continue;
        }

        if (entity_eligible(cfs_rq, se)) {
            if (!best || deadline_gt(best, se))
                best = se;
        }

        node = node->rb_right;
    }

found:
    return best;
}

/* pick_next_entity — EEVDF를 사용하는 최상위 선택 함수 */
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq)
{
    /* skip이 설정된 경우 (yield) 건너뛰기 */
    if (cfs_rq->skip)
        return pick_eevdf(cfs_rq);  /* skip 처리 포함 */

    return pick_eevdf(cfs_rq);
}

슬라이스 메커니즘

EEVDF에서 slice는 태스크가 한 번에 실행할 수 있는 시간 단위입니다. CFS의 동적 타임슬라이스(sched_latency / nr_running)와 달리, EEVDF의 slice는 태스크별로 고정되며 deadline 계산의 기초가 됩니다.

CFS의 문제: 태스크가 늘수록 길어지는 지연

CFS에서는 타임슬라이스가 sched_latency_ns / nr_running으로 계산됩니다. 기본 sched_latency_ns가 6ms이고 실행 가능한 태스크가 6개라면 각 태스크의 타임슬라이스는 1ms입니다. 여기까지는 좋습니다. 그런데 태스크가 60개라면 어떻게 될까요?

CFS 타임슬라이스 = sched_latency_ns / nr_running

nr_running =  6: 타임슬라이스 = 6ms / 6  = 1.0ms
nr_running = 20: 타임슬라이스 = 6ms / 20 = 0.3ms  (sched_min_granularity_ns 하한 발동)
nr_running = 60: 타임슬라이스 = 6ms / 60 = 0.1ms  → 하한 클램핑 → 실제 지연 증가

결과: 태스크 60개 × 하한 0.75ms = 45ms 주기 → 1회 서비스 대기 최대 44ms

태스크 수가 늘면 한 바퀴 돌아오는 데 걸리는 시간(스케줄링 지연)이 그에 비례해 늘어납니다. 이는 대화형 태스크나 실시간성이 필요한 워크로드에서 응답 지연이 예측 불가하게 커지는 원인이 됩니다.

EEVDF의 해법: 고정 slice + deadline 기반 선점

EEVDF에서 slice는 태스크 수와 무관하게 고정됩니다 (기본값 sched_base_slice_ns = 3ms). 선점 기준도 "타임슬라이스 소진"이 아니라 "현재 태스크의 deadline을 더 이른 deadline을 가진 eligible 태스크가 추월"하는 시점입니다.

EEVDF 선점 조건:
  새 태스크의 VD  <  현재 실행 중 태스크의 VD  (deadline 역전)
  AND 새 태스크가 eligible

태스크 수에 따른 변화:
  nr_running =  6: 각 태스크 slice = 3ms (고정)
  nr_running = 60: 각 태스크 slice = 3ms (고정) ← CFS와 다름

결과: 태스크 수가 늘어도 slice 크기 불변, 지연 상한은 O(log N) 수준으로 유지

/* kernel/sched/fair.c — slice 기반 deadline 및 선점 */

/* sched_base_slice_ns: 기본 실행 슬라이스 */
unsigned int sysctl_sched_base_slice = 3000000ULL;  /* 3ms */

/* 태스크의 slice 초기화 */
static void init_entity_runnable_average(struct sched_entity *se)
{
    se->slice = sysctl_sched_base_slice;
    /* latency_nice가 설정되면 slice 조정 */
}

/* slice 소진 확인 — tick에서 호출 */
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->sum_exec_runtime += delta_exec;
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    /* EEVDF: vruntime이 deadline을 넘으면 새 deadline 설정 */
    update_deadline(cfs_rq, curr);

    update_min_vruntime(cfs_rq);
}

EEVDF 선점 규칙

EEVDF에서 선점은 두 가지 경로로 발생합니다: tick 기반 선점(현재 태스크의 slice 소진)과 wakeup 기반 선점(새로 깨어난 태스크의 deadline이 더 이름).

선점 판단 규칙

선점 발생 조건:

1. Tick 선점:
   curr->vruntime >= curr->deadline
   → 현재 태스크가 자신의 slice를 소진

2. Wakeup 선점:
   new->deadline < curr->deadline
   AND entity_eligible(cfs_rq, new)
   → 새 태스크가 eligible하고 deadline이 더 이름

3. CFS에서 제거된 조건:
   - buddy 기반 선점 (next/last buddy) → 제거
   - sched_min_granularity 기반 최소 실행 보장 → 제거
   - wakeup_gran 기반 보너스 → 제거

/* kernel/sched/fair.c — tick 기반 선점 확인 */
static void
check_preempt_tick(struct cfs_rq *cfs_rq,
                   struct sched_entity *curr)
{
    /* EEVDF: curr의 vruntime이 deadline을 넘었으면 선점 */
    if ((s64)(curr->vruntime - curr->deadline) >= 0) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
}

/* kernel/sched/fair.c — wakeup 기반 선점 확인 */
static void
check_preempt_wakeup_fair(struct rq *rq,
                          struct task_struct *p, int wake_flags)
{
    struct sched_entity *se = &p->se;
    struct sched_entity *curr_se = &rq->curr->se;

    /* 같은 cfs_rq 레벨까지 탐색 */
    while (se && curr_se) {
        if (se == curr_se)
            break;
        /* ... hierarchy walk ... */
    }

    /* EEVDF: new가 eligible하고 deadline이 curr보다 이르면 선점 */
    if (entity_eligible(cfs_rq, se) &&
        (s64)(curr_se->deadline - se->deadline) > 0)
        resched_curr(rq);
}

Augmented RB-Tree

EEVDF의 효율적 구현을 위해 기존 CFS의 RB-Tree에 min_deadline 보조 키가 추가되었습니다. 이 augmentation을 통해 서브트리 내 최소 deadline을 O(1)에 조회할 수 있어, pick_eevdf()가 O(log N)에 동작할 수 있습니다.

/* kernel/sched/fair.c — RB-Tree augmentation: min_deadline 전파 */

/* 노드의 min_deadline을 자식으로부터 갱신 */
static inline bool
__update_min_deadline(struct sched_entity *se, struct rb_node *node)
{
    struct sched_entity *rse = __node_2_se(node);
    if (deadline_gt(se, rse)) {
        se->min_deadline = rse->min_deadline;
        return true;
    }
    return false;
}

/* RB-Tree 콜백: 회전/삽입/삭제 시 augmentation 업데이트 */
RB_DECLARE_CALLBACKS(static, min_deadline_cb,
    struct sched_entity, run_node, min_deadline,
    min_deadline_update);

static void min_deadline_update(struct sched_entity *se,
                                struct rb_node *node)
{
    /* se->min_deadline = 자기 자신의 deadline으로 초기화 */
    se->min_deadline = se->deadline;

    /* 왼쪽 자식의 min_deadline과 비교 */
    if (node->rb_left)
        __update_min_deadline(se, node->rb_left);

    /* 오른쪽 자식의 min_deadline과 비교 */
    if (node->rb_right)
        __update_min_deadline(se, node->rb_right);
}

sched_entity EEVDF 관련 필드 상세

EEVDF 도입으로 struct sched_entity에 여러 필드가 추가되었습니다.

/* include/linux/sched.h — sched_entity EEVDF 관련 필드 */
struct sched_entity {
    /* === CFS 기존 필드 === */
    struct load_weight    load;           /* nice → weight 변환 */
    struct rb_node        run_node;       /* RB-Tree 노드 */
    unsigned int         on_rq;          /* enqueued 여부 */
    u64                  exec_start;     /* 현재 실행 시작 시각 */
    u64                  sum_exec_runtime; /* 총 실행 시간 */
    u64                  prev_sum_exec_runtime;
    u64                  vruntime;       /* 가상 실행 시간 */

    /* === EEVDF 추가 필드 === */
    u64                  deadline;       /* virtual deadline */
    u64                  min_deadline;   /* augmented: 서브트리 최소 deadline */
    unsigned int         slice;          /* 요청 실행 시간 (ns) */

    /* === 공통 === */
    s64                  vlag;           /* lag 값 (place_entity용) */
    u64                  migrate_deadline; /* 마이그레이션 deadline */

    /* ... PELT, cgroup 필드 생략 ... */
};

/* cfs_rq의 EEVDF 관련 필드 */
struct cfs_rq {
    /* === 기존 === */
    struct load_weight    load;
    unsigned int         nr_running;
    u64                  min_vruntime;
    struct rb_root_cached tasks_timeline;

    /* === EEVDF 추가 === */
    s64                  avg_vruntime;   /* Σ(key_i × w_i) */
    u64                  avg_load;       /* Σ(w_i) */

    /* ... */
};

place_entity() 분석

place_entity()는 태스크가 enqueue될 때(fork, wakeup, migrate) vruntime과 deadline을 적절히 배치하는 핵심 함수입니다. EEVDF에서는 lag 보존이 핵심 원칙입니다.

배치 시나리오별 동작

/* kernel/sched/fair.c — place_entity (EEVDF, 단순화) */
static void
place_entity(struct cfs_rq *cfs_rq,
             struct sched_entity *se, int flags)
{
    u64 vruntime = avg_vruntime(cfs_rq);
    s64 lag = 0;

    if (!(flags & ENQUEUE_INITIAL)) {
        /* wakeup/migrate: 저장된 lag 복원 */
        lag = se->vlag;

        /* lag 상한 제한: 과도한 boost 방지 */
        s64 limit = calc_delta_fair(se->slice, se);
        lag = clamp(lag, -limit, limit);
    }

    /* vruntime 배치: avg에서 lag만큼 뒤로 */
    se->vruntime = vruntime - lag;

    /* 새 deadline 설정 */
    se->deadline = se->vruntime +
                   calc_delta_fair(se->slice, se);
}

/* dequeue 시 lag 저장 — 나중에 place_entity에서 복원 */
static void
dequeue_entity(struct cfs_rq *cfs_rq,
               struct sched_entity *se, int flags)
{
    /* ... */

    /* 현재 lag를 vlag에 저장 */
    se->vlag = entity_lag(avg_vruntime(cfs_rq), se);

    __dequeue_entity(cfs_rq, se);
    /* ... */
}

update_curr() 변경점

update_curr()는 현재 실행 중인 태스크의 vruntime을 갱신하는 핵심 함수로, EEVDF에서 deadline 갱신 로직이 추가되었습니다.

/* kernel/sched/fair.c — update_curr (EEVDF 변경점 포함) */
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;
    curr->sum_exec_runtime += delta_exec;

    /* 1. vruntime 갱신 (CFS와 동일) */
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    /* 2. EEVDF: deadline 갱신 (추가됨) */
    update_deadline(cfs_rq, curr);

    /* 3. min_vruntime 갱신 */
    update_min_vruntime(cfs_rq);

    /* 4. avg_vruntime은 min_vruntime 변화에 의해 암시적 갱신 */

    /* 5. PELT 부하 갱신 */
    account_cfs_rq_runtime(cfs_rq, delta_exec);
}

update_deadline() 상세

/* deadline은 slice를 다 쓸 때만 갱신됨 */
static void update_deadline(struct cfs_rq *cfs_rq,
                            struct sched_entity *se)
{
    /* vruntime이 deadline을 넘었는가? */
    if ((s64)(se->vruntime - se->deadline) >= 0) {
        /*
         * 이전 slice를 소진 → 새 deadline 할당
         * deadline = vruntime + calc_delta_fair(slice, se)
         *          = vruntime + slice * NICE_0_LOAD / weight
         *
         * 높은 weight → 짧은 가상 시간 간격 → 이른 deadline
         * 낮은 weight → 긴 가상 시간 간격 → 늦은 deadline
         */
        se->deadline = se->vruntime +
                       calc_delta_fair(se->slice, se);

        /* RB-Tree에 있으면 min_deadline augmentation 갱신 */
        if (se->on_rq)
            update_min_deadline(se);
    }
}

tick 기반 선점 판단

EEVDF의 tick 기반 선점은 CFS보다 단순합니다. CFS는 ideal_runtime 계산과 sched_min_granularity 확인이 필요했지만, EEVDF는 단순히 deadline 초과 여부만 확인합니다.

/* kernel/sched/fair.c — entity_tick (단순화) */
static void
entity_tick(struct cfs_rq *cfs_rq,
            struct sched_entity *curr, int queued)
{
    /* 1. 현재 태스크의 vruntime 갱신 */
    update_curr(cfs_rq);

    /* 2. 다른 runnable 태스크가 있으면 선점 확인 */
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);
}

static void
check_preempt_tick(struct cfs_rq *cfs_rq,
                   struct sched_entity *curr)
{
    /* EEVDF: slice 소진 = deadline 초과 */
    if ((s64)(curr->vruntime - curr->deadline) >= 0) {
        resched_curr(rq_of(cfs_rq));
        return;
    }

    /* 최소 실행 보장: HZ에 기반한 최소 tick (선택적) */
    if (delta_exec < sysctl_sched_min_granularity)
        return;
}

wakeup 선점 판단

Wakeup 선점은 sleep 상태의 태스크가 깨어날 때 현재 실행 중인 태스크를 선점할지 결정합니다. EEVDF에서는 deadline 비교가 핵심입니다.

/* kernel/sched/fair.c — wakeup 선점 (EEVDF) */
static void
check_preempt_wakeup_fair(struct rq *rq,
                          struct task_struct *p,
                          int wake_flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &p->se;
    struct sched_entity *pse = &curr->se;
    struct cfs_rq *cfs_rq;

    /* RT/DL 클래스가 FAIR보다 높으면 바로 리턴 */
    if (unlikely(p->sched_class != &fair_sched_class))
        return;

    /* 같은 그룹 레벨까지 올라감 */
    find_matching_se(&se, &pse);
    cfs_rq = cfs_rq_of(pse);

    update_curr(cfs_rq);

    /* EEVDF 선점 조건:
     * 1. 새 태스크가 eligible
     * 2. 새 태스크의 deadline < 현재 태스크의 deadline */
    if (entity_eligible(cfs_rq, se) &&
        (s64)(pse->deadline - se->deadline) > 0)
        resched_curr(rq);
}

그룹 스케줄링과 EEVDF

리눅스 커널의 그룹 스케줄링(cgroup cpu controller)은 EEVDF에서도 동일하게 동작합니다. 각 task_group은 자체 cfs_rq를 가지며, 그룹 수준과 태스크 수준에서 독립적으로 EEVDF 알고리즘이 적용됩니다.

/* 그룹 스케줄링 + EEVDF: 계층적 pick */
static struct task_struct *
pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    do {
        /* 각 레벨에서 EEVDF pick */
        se = pick_next_entity(cfs_rq);
        if (!se)
            return NULL;

        /* 태스크가 아닌 그룹이면 내부 cfs_rq로 진입 */
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    return task_of(se);
}

/* 그룹의 weight는 cpu.weight (또는 cpu.shares) 설정에 의해 결정
 * 예: A 그룹 weight=2048, B 그룹 weight=1024
 * → A가 B의 2배 CPU 시간 할당 */

CFS 대역폭 제한과 EEVDF

cgroup v2의 cpu.max (또는 cgroup v1의 cpu.cfs_quota_us)를 통한 대역폭 제한은 EEVDF에서도 동일하게 동작합니다. 쓰로틀링은 EEVDF의 pick 로직과 독립적으로 cfs_rq 수준에서 적용됩니다.

/* cpu.max 설정 예시: 50ms 주기 중 20ms 허용 */
/* → 최대 40% CPU 사용 */

/* kernel/sched/fair.c — 대역폭 쓰로틀링 */
static bool
check_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
    if (!cfs_bandwidth_used())
        return false;

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

    if (cfs_rq->runtime_remaining > 0)
        return false;

    /* 할당량 소진 → 쓰로틀링
     * EEVDF의 pick과 무관하게 cfs_rq 전체를 비활성화 */
    throttle_cfs_rq(cfs_rq);
    return true;
}

# cgroup v2 CPU 대역폭 설정 예시
echo "20000 50000" > /sys/fs/cgroup/mygroup/cpu.max  # 20ms/50ms = 40%
echo "100000 100000" > /sys/fs/cgroup/mygroup/cpu.max # 100ms/100ms = 100% (제한 없음)
echo "max 100000" > /sys/fs/cgroup/mygroup/cpu.max    # 무제한

# EEVDF에서 동작 확인
cat /proc/sched_debug | grep -A5 "cfs_rq\[mygroup\]"

sysctl 튜닝 파라미터

EEVDF 도입 후 일부 CFS 파라미터가 제거되고 새 파라미터가 추가되었습니다.

# EEVDF 튜닝 파라미터 확인
sysctl kernel.sched_base_slice_ns
# kernel.sched_base_slice_ns = 3000000

# slice 줄이기: 더 짧은 deadline → 더 빠른 응답, 더 잦은 선점
sysctl -w kernel.sched_base_slice_ns=1000000  # 1ms

# slice 늘리기: 더 긴 deadline → 더 나은 처리량, 더 적은 선점
sysctl -w kernel.sched_base_slice_ns=10000000  # 10ms

# 현재 EEVDF 관련 sched 디버그 정보
cat /proc/sched_debug | head -30

Latency Nice

Latency nice는 EEVDF와 함께 도입된 새로운 태스크 속성으로, nice 값(CPU 비율)과 독립적으로 응답 지연을 제어합니다.

매핑(Mapping) 규칙

latency_nice 범위: -20 ~ 19 (nice와 동일 범위)

매핑:
  latency_nice → latency_offset

  latency_nice = -20 → 가장 짧은 slice → 가장 이른 deadline → 최소 지연
  latency_nice =   0 → 기본 slice (sched_base_slice_ns)
  latency_nice =  19 → 가장 긴 slice → 가장 늦은 deadline → 최대 지연 허용

관계:
  nice: CPU 시간 "비율" 제어 (weight)
  latency_nice: 응답 "속도" 제어 (slice → deadline)

예시:
  nice=0, latency_nice=-10 → 공정한 CPU 비율이지만 빠른 응답 (짧은 deadline)
  nice=0, latency_nice=+10 → 공정한 CPU 비율이지만 느린 응답 허용 (배치 워크로드)

/* kernel/sched/core.c — latency_nice → slice 변환 */

/* latency_nice 설정 API */
void set_latency_nice(struct task_struct *p, long nice)
{
    int old_prio = p->latency_prio;

    p->latency_prio = NICE_TO_PRIO(nice);

    if (old_prio != p->latency_prio)
        set_latency_offset(p);
}

/* latency_offset 계산 — slice에 반영 */
static void set_latency_offset(struct task_struct *p)
{
    long nice = PRIO_TO_NICE(p->latency_prio);

    /* nice=-20 → 매우 짧은 slice
     * nice=19  → 매우 긴 slice
     * 기본 slice에 가중치를 곱하여 조정 */
    p->se.slice = sysctl_sched_base_slice *
                  sched_latency_to_slice[nice + 20];
}

# latency_nice 설정 (sched_setattr 시스템 콜)
# chrt 명령으로는 아직 미지원, schedtool 또는 직접 syscall

# C 코드 예시:
# struct sched_attr attr = {
#     .size = sizeof(attr),
#     .sched_flags = SCHED_FLAG_UTIL_CLAMP | SCHED_FLAG_LATENCY_NICE,
#     .sched_latency_nice = -10,  // 빠른 응답
# };
# sched_setattr(pid, &attr, 0);

# 확인
cat /proc//sched | grep latency

워크로드별 성능 분석

EEVDF는 워크로드 유형에 따라 CFS와 다른 성능 특성을 보입니다.

대화형 워크로드

배치 워크로드

혼합 워크로드

시나리오: 4 CPU-bound + 1 interactive (주기적 1ms burst)

CFS:
  - interactive가 wakeup 시 wakeup_gran(1ms) 후에야 선점
  - next/last buddy로 CPU-bound가 캐시 재사용
  - interactive 응답 시간: ~2-5ms (변동)

EEVDF:
  - interactive가 wakeup 시 즉시 eligible (lag > 0)
  - deadline 비교로 확정적 선점
  - interactive 응답 시간: ~0.5-1ms (안정적)

→ 혼합 워크로드에서 EEVDF가 더 예측 가능한 지연을 제공

벤치마크 비교

CFS와 EEVDF의 성능을 다양한 벤치마크로 비교합니다.

# 직접 벤치마크 실행하기

# hackbench: IPC 처리량
hackbench -g 20 -l 10000 --pipe

# schbench: 스케줄러 지연 측정
schbench -m 2 -t 8 -r 30  # 2 메시지 그룹, 8 스레드, 30초

# tbench: 처리량
tbench_srv &
tbench -t 60 $(nproc) 127.0.0.1

# cyclictest: 실시간 지연
cyclictest -m -p 80 -i 1000 -l 100000

# perf로 스케줄러 이벤트 측정
perf sched record -- sleep 10
perf sched latency

ftrace/perf로 EEVDF 관측

EEVDF의 동작을 런타임에 관측하기 위한 도구와 방법을 소개합니다.

관련 tracepoint

# ftrace로 스케줄러 이벤트 기록
cd /sys/kernel/debug/tracing
echo 0 > tracing_on
echo sched_switch sched_wakeup > set_event

# 특정 프로세스만 추적
echo $PID > set_ftrace_pid

echo 1 > tracing_on
sleep 5
echo 0 > tracing_on
cat trace | head -50

# perf로 스케줄러 지연 분석
perf sched record -- sleep 10
perf sched latency --sort max

# perf로 EEVDF 관련 함수 프로파일링
perf probe --add 'pick_eevdf'
perf stat -e 'probe:pick_eevdf' -- sleep 10

# bpftrace로 deadline 분포 관측
bpftrace -e '
kprobe:pick_eevdf {
    @pick_count = count();
}
kretprobe:pick_eevdf {
    @pick_lat = hist(nsecs - @start[tid]);
}
'

# /proc/sched_debug에서 EEVDF 정보 확인
cat /proc/sched_debug | grep -A20 "cfs_rq\[0\]"

# 출력 예시 (EEVDF 관련 필드):
# cfs_rq[0]:/
#   .nr_running                    : 3
#   .min_vruntime                  : 1234567.890123
#   .avg_vruntime                  : 456789
#   .avg_load                      : 3072

# 특정 태스크의 스케줄링 정보
cat /proc/$PID/sched | grep -E "vruntime|deadline|slice|lag"

# 출력 예시:
# se.vruntime                      : 1234567.890123
# se.deadline                      : 1234570.819846
# se.slice                         : 3000000
# se.vlag                          : 0

디버깅 시나리오

시나리오 1: 태스크 기아 의심

# 1. 대상 태스크의 스케줄링 정보 확인
cat /proc/$PID/sched

# 2. lag 확인: vlag가 큰 양수이면 덜 받고 있음
cat /proc/$PID/sched | grep vlag

# 3. eligible 여부 간접 확인:
#    vruntime < avg_vruntime → eligible
#    vruntime > avg_vruntime → ineligible

# 4. EEVDF에서 starvation은 이론적으로 불가능
#    (lag bounded by r_max)
#    실제로 발생하면 버그이므로 커널 로그 확인
dmesg | grep -i sched

시나리오 2: 높은 스케줄링 지연

# 1. perf로 wakeup-to-run 레이턴시 측정
perf sched record -- sleep 30
perf sched latency --sort max | head -20

# 2. slice가 너무 큰지 확인
sysctl kernel.sched_base_slice_ns
# 3ms 이상이면 줄여보기
sysctl -w kernel.sched_base_slice_ns=1000000

# 3. cgroup bandwidth throttling 확인
cat /sys/fs/cgroup/*/cpu.max
cat /sys/fs/cgroup/*/cpu.stat | grep throttled

# 4. RT 태스크가 FAIR를 밀어내고 있는지 확인
ps -eo pid,cls,pri,comm | grep -E "RR|FF"

# 5. bpftrace로 pick_eevdf 호출 빈도 및 레이턴시
bpftrace -e 'kprobe:pick_eevdf { @start[tid] = nsecs; }
kretprobe:pick_eevdf /@start[tid]/ {
    @us = hist((nsecs - @start[tid]) / 1000);
    delete(@start[tid]);
}'

시나리오 3: 불공정 CPU 분배

# 1. CPU 사용률 확인 (동일 nice 태스크가 동일 비율인지)
pidstat -u 1 10

# 2. /proc/sched_debug에서 vruntime 편차 확인
cat /proc/sched_debug | grep -A50 "cfs_rq\[0\]"

# 3. NUMA 밸런싱이 불공정을 유발하는지
numastat -p $PID
cat /proc/$PID/numa_maps

# 4. EEVDF에서는 |lag| <= r_max 보장이므로
#    불공정이 r_max를 넘으면 구현 버그
cat /proc/$PID/sched | grep -E "sum_exec|vruntime|deadline"

관련 커널 설정 옵션

# EEVDF 관련 커널 설정 (make menuconfig)

# 기본 활성화 (v6.6+ 기본)
CONFIG_SCHED_CLASS_FAIR=y           # FAIR 스케줄러 클래스

# 디버깅
CONFIG_SCHED_DEBUG=y                # /proc/sched_debug, /proc/PID/sched
CONFIG_SCHEDSTATS=y                 # 스케줄러 통계 수집

# 선점 모델 (EEVDF와 독립적이지만 동작에 영향)
CONFIG_PREEMPT_NONE=y               # 서버 (최소 선점)
CONFIG_PREEMPT_VOLUNTARY=y          # 데스크톱 (중간, 기본)
CONFIG_PREEMPT=y                    # 실시간 (최대 선점)
CONFIG_PREEMPT_RT=y                 # PREEMPT_RT (실시간)

# 그룹 스케줄링 (EEVDF + cgroup 연동)
CONFIG_CGROUP_SCHED=y               # cgroup 스케줄러 지원
CONFIG_FAIR_GROUP_SCHED=y           # FAIR 그룹 스케줄링
CONFIG_CFS_BANDWIDTH=y              # cpu.max 대역폭 제한

# PELT (EEVDF와 함께 동작)
CONFIG_SMP=y                        # 멀티프로세서 (PELT 필요)

# sched_ext (BPF 확장)
CONFIG_SCHED_CLASS_EXT=y            # BPF 스케줄러 확장

CFS→EEVDF 마이그레이션 가이드

커널 6.5 이전(CFS)에서 6.6 이후(EEVDF)로 업그레이드할 때 고려해야 할 사항들입니다.

마이그레이션 체크리스트

[ ] 1. 제거된 sysctl 파라미터 확인
      - sched_wakeup_granularity_ns → 제거 (EEVDF deadline으로 대체)
      - sched_child_runs_first → 제거 (lag 기반으로 불필요)
      - sched_nr_latency → 제거 (동적 타임슬라이스 불필요)
      → 이 파라미터를 설정하는 스크립트/설정 정리

[ ] 2. sched_base_slice_ns 설정
      - 기본 3ms
      - 데스크톱: 1~2ms (더 나은 응답)
      - 서버/HPC: 3~10ms (더 나은 처리량)

[ ] 3. 벤치마크 비교
      - 기존 워크로드로 CFS vs EEVDF 성능 비교
      - 특히 tail latency (p99, p999) 개선 확인

[ ] 4. buddy 의존성 제거
      - CFS의 next/last buddy에 의존하는 워크로드 패턴 확인
      - EEVDF에서는 deadline이 결정적이므로 buddy 불필요

[ ] 5. latency_nice 도입 검토
      - 오디오/영상 처리: latency_nice=-10~-20
      - 일반: latency_nice=0
      - 배치/빌드: latency_nice=10~19

[ ] 6. cgroup 설정 확인
      - cpu.weight, cpu.max는 변경 없이 동작
      - EEVDF와 bandwidth throttling은 독립적

[ ] 7. 모니터링 갱신
      - /proc/PID/sched에서 deadline, slice, vlag 필드 확인
      - perf sched latency로 정기 측정

Virtual Time 타임라인 상세

여러 태스크의 vruntime과 virtual deadline이 시간에 따라 어떻게 진행되는지를 시각화합니다.

/* vruntime 증가율과 weight의 관계 */
/*
 * calc_delta_fair(delta, se):
 *   return delta * NICE_0_LOAD / se->load.weight
 *
 * 예시 (1ms 실제 실행):
 *   nice 0  (w=1024): vruntime += 1ms * 1024/1024 = 1ms
 *   nice -5 (w=3121): vruntime += 1ms * 1024/3121 = 0.328ms
 *   nice 5  (w=335):  vruntime += 1ms * 1024/335  = 3.057ms
 *
 * → 높은 weight = 느린 vruntime 증가 = avg 아래 유지 = eligible
 * → 낮은 weight = 빠른 vruntime 증가 = avg 위로 = ineligible
 */

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;
}

내부 구현 세부 사항

min_vruntime 갱신

/* kernel/sched/fair.c — min_vruntime 갱신
 * EEVDF에서도 CFS와 동일한 min_vruntime 메커니즘 사용
 * avg_vruntime 계산의 기준점 역할 */
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 = __node_2_se(leftmost);
        if (!curr)
            vruntime = se->vruntime;
        else
            vruntime = min_vruntime(vruntime, se->vruntime);
    }

    /* min_vruntime은 단조 증가만 허용 */
    u64 delta = vruntime - cfs_rq->min_vruntime;
    if ((s64)delta > 0) {
        avg_vruntime_update(cfs_rq, delta);
        cfs_rq->min_vruntime = vruntime;
    }
}

enqueue/dequeue 흐름

/* kernel/sched/fair.c — 간략화 */
static void
enqueue_entity(struct cfs_rq *cfs_rq,
               struct sched_entity *se, int flags)
{
    /* 1. EEVDF: vruntime/deadline 배치 */
    if (!(flags & ENQUEUE_WAKEUP) || !(flags & ENQUEUE_MIGRATED))
        se->vlag = 0;

    place_entity(cfs_rq, se, flags);

    /* 2. RB-Tree 삽입 */
    __enqueue_entity(cfs_rq, se);

    /* 3. avg_vruntime 업데이트 */
    avg_vruntime_add(cfs_rq, se);

    se->on_rq = 1;
    cfs_rq->nr_running++;
}

/* __enqueue_entity — RB-Tree 삽입 + augmentation */
static void __enqueue_entity(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    /* vruntime 기반 정렬 삽입 */
    rb_add_augmented_cached(&se->run_node,
                            &cfs_rq->tasks_timeline,
                            __entity_less,
                            &min_deadline_cb);
    /* augmented 삽입이므로 min_deadline이 자동 전파됨 */
}

yield_to()의 EEVDF 구현

/* yield — 현재 태스크의 deadline을 무시하고 양보 */
static void yield_task_fair(struct rq *rq)
{
    struct sched_entity *se = &rq->curr->se;
    struct cfs_rq *cfs_rq = cfs_rq_of(se);

    /* EEVDF: skip 설정으로 pick_eevdf에서 건너뛰기 */
    if (cfs_rq->nr_running > 1) {
        cfs_rq->skip = se;
        set_skip_buddy(se);
    }
}

/* pick_eevdf에서 skip 처리:
 * skip이 설정된 태스크는 eligible + earliest deadline이어도
 * 다음 후보를 선택 */

NUMA 밸런싱과 EEVDF

NUMA(Non-Uniform Memory Access) 시스템에서 태스크가 CPU 간 마이그레이션(Migration)될 때, 각 CPU의 cfs_rq는 독립적인 avg_vruntime과 min_vruntime을 가집니다. EEVDF는 vlag(lag 값)을 보존하여 마이그레이션 후에도 공정성을 유지합니다.

/* NUMA 마이그레이션 시 lag 보존
 * 태스크가 CPU A → CPU B로 이동할 때:
 * 1. dequeue: vlag = entity_lag(avg_vruntime_A, se)
 * 2. enqueue: place_entity에서 vlag를 CPU B의 avg_vruntime에 적용
 *
 * 이를 통해 NUMA 마이그레이션 후에도 공정성이 유지됨 */

/* v6.12: migrate_deadline 필드 추가 */
static void migrate_task_rq_fair(struct task_struct *p, int new_cpu)
{
    struct sched_entity *se = &p->se;

    /* lag 저장 (dequeue에서 이미 설정됨) */
    /* se->vlag는 이미 dequeue_entity에서 설정 */

    /* deadline 상대값 보존 */
    se->migrate_deadline = se->deadline - se->vruntime;
}

sched_ext와 EEVDF의 관계

Linux 6.12에서 도입된 sched_ext(BPF 확장 스케줄러)는 EEVDF와 독립적으로 동작하는 별도의 sched_class입니다.

sched_class 우선순위는 다음과 같습니다 (높은 것이 먼저 선택됩니다).

stop_sched_class > dl_sched_class > rt_sched_class
  > fair_sched_class (EEVDF) > ext_sched_class > idle_sched_class

sched_ext는 fair(EEVDF)보다 낮은 우선순위이므로, EEVDF 태스크가 있으면 sched_ext는 실행되지 않습니다. sched_ext는 자체 BPF 프로그램으로 pick 로직을 구현합니다. 그러나 sched_ext가 FAIR 클래스의 태스크를 "가져오면" EEVDF 대신 BPF 로직이 적용됩니다.

EEVDF의 한계와 알려진 이슈

EEVDF pick 비용 분석은 다음과 같습니다.

최선

O(1) — leftmost가 eligible이면서 earliest deadline인 경우

평균

O(log N) — RB-Tree 루트에서 한 경로를 탐색합니다

최악

O(log N) — 트리 전체 높이를 탐색합니다

실측 (4 CPU, 100 태스크) 결과:

차이는 약 50ns로, 3ms slice 대비 0.002% 오버헤드이며 사실상 무시 가능합니다.

EEVDF vs SCHED_DEADLINE

EEVDF와 SCHED_DEADLINE은 모두 "deadline" 개념을 사용하지만, 목적과 구현이 완전히 다릅니다.

sched_class 우선순위 계층에서 EEVDF의 위치는 다음과 같습니다.

dl_sched_class (SCHED_DEADLINE)
  ↑ 더 높은 우선순위
  |
rt_sched_class (SCHED_FIFO, SCHED_RR)
  |
fair_sched_class (SCHED_NORMAL — EEVDF)
  |
  ↓ 더 낮은 우선순위
idle_sched_class (SCHED_IDLE)

EEVDF의 virtual deadline은 fair_sched_class 내에서만 유효하며, SCHED_DEADLINE 태스크가 있으면 항상 먼저 실행됩니다.

전체 코드 워크스루

태스크가 wakeup되어 선점하고, 실행되고, 다시 schedule되는 전체 과정을 EEVDF 관점에서 추적합니다.

전체 EEVDF 경로 워크스루는 다음과 같습니다.

1. try_to_wake_up(p) — Wakeup 경로
   • ttwu_queue(p, cpu)
   • ttwu_do_activate(rq, p)
   • activate_task(rq, p, ENQUEUE_WAKEUP)
   • enqueue_task_fair(rq, p, ENQUEUE_WAKEUP)
   • enqueue_entity(cfs_rq, se, ENQUEUE_WAKEUP)
   • place_entity(cfs_rq, se, ENQUEUE_WAKEUP) — vruntime = avg_vruntime - se->vlag (lag 복원), deadline = vruntime + slice/weight
   • __enqueue_entity(cfs_rq, se) — RB-Tree 삽입 + min_deadline 전파
   • avg_vruntime_add(cfs_rq, se) — avg_vruntime 갱신
2. check_preempt_wakeup_fair(rq, p) — 선점 판단
   • entity_eligible(cfs_rq, se) — se의 vruntime <= avg인지 확인
   • deadline 비교: se->deadline < curr->deadline인지 확인
   • resched_curr(rq) — 선점 예약
3. schedule() → __schedule() — 태스크 선택
   • pick_next_task_fair(rq)
   • pick_next_entity(cfs_rq)
   • pick_eevdf(cfs_rq) — eligible 필터링 + earliest deadline 선택
   • context_switch(rq, prev, next)
4. scheduler_tick() — 실행 중 tick 처리
   • task_tick_fair(rq, p)
   • entity_tick(cfs_rq, curr)
   • update_curr(cfs_rq) — vruntime += calc_delta_fair(delta_exec, curr), update_deadline(cfs_rq, curr)
   • check_preempt_tick(cfs_rq, curr) — vruntime >= deadline이면 resched_curr 호출
5. dequeue_task_fair() — 태스크 sleep
   • dequeue_entity(cfs_rq, se)
   • se->vlag = entity_lag(avg_vruntime, se) — lag 저장
   • __dequeue_entity(cfs_rq, se)
   • avg_vruntime_sub(cfs_rq, se)

수치 시뮬레이션 예제

EEVDF의 스케줄링 결정 과정을 구체적 숫자로 추적합니다. 3개 태스크(A: nice=0, B: nice=-5, C: nice=5)가 동시에 실행 대기 중인 상황에서 EEVDF가 어떻게 선택하는지 단계별로 시뮬레이션합니다.

초기 조건

시스템 설정:
  sched_base_slice_ns = 3,000,000 (3ms)
  NICE_0_LOAD = 1024

태스크 초기 상태 (모두 동시에 enqueue):
  A: nice=0,  weight=1024, vruntime=0, slice=3ms
  B: nice=-5, weight=3121, vruntime=0, slice=3ms
  C: nice=5,  weight=335,  vruntime=0, slice=3ms

VD(Virtual Deadline) 계산:
  VD = vruntime + slice × NICE_0_LOAD / weight

  A: VD = 0 + 3,000,000 × 1024/1024 = 3,000,000
  B: VD = 0 + 3,000,000 × 1024/3121 = 984,300   ← 가장 이른 deadline
  C: VD = 0 + 3,000,000 × 1024/335  = 9,171,642

avg_vruntime 초기값:
  avg = Σ(key_i × w_i) / Σ(w_i)
  = (0×1024 + 0×3121 + 0×335) / (1024+3121+335)
  = 0

Step 1: 최초 pick (t=0)

eligible 판정 (vruntime <= avg_vruntime?):
  A: 0 <= 0 → eligible ✓
  B: 0 <= 0 → eligible ✓
  C: 0 <= 0 → eligible ✓

earliest deadline 선택:
  A.VD=3,000,000  B.VD=984,300  C.VD=9,171,642
                      ↑ 최소!

→ pick_eevdf() 선택: 태스크 B (nice=-5)

Step 2: B가 1ms 실행 후 (t=1ms)

update_curr() — B의 vruntime 갱신:
  delta_exec = 1,000,000 ns (1ms 실제 실행)
  vruntime 증가 = delta × NICE_0_LOAD / weight
                = 1,000,000 × 1024 / 3121
                = 328,100 (가상 시간)

  B.vruntime = 0 + 328,100 = 328,100

avg_vruntime 갱신:
  avg = (0×1024 + 328,100×3121 + 0×335) / (1024+3121+335)
      = 1,023,840,100 / 4,480
      = 228,536

eligible 판정:
  A: 0 <= 228,536 → eligible ✓ (vruntime이 avg보다 낮음 = 덜 받음)
  B: 328,100 > 228,536 → INELIGIBLE ✗ (avg보다 높음 = 더 받음)
  C: 0 <= 228,536 → eligible ✓

B는 아직 slice(VD=984,300)를 소진하지 않았지만 (vruntime=328,100 < VD),
여전히 ineligible이므로 선점 검사에서 다른 태스크가 선택될 수 있음.

그러나 tick 선점은 vruntime >= deadline 일 때만 발생하므로,
B는 계속 실행 (tick에서 deadline 미초과)

Step 3: B가 3ms(slice) 실행 완료 후 (t=3ms)

update_curr() — B의 vruntime 갱신:
  B.vruntime = 3,000,000 × 1024 / 3121 = 984,300

deadline 확인: B.vruntime(984,300) >= B.VD(984,300) → 같음!
→ update_deadline(): B.VD = 984,300 + 984,300 = 1,968,600
→ resched_curr() — 선점 예약!

avg_vruntime:
  avg = (0×1024 + 984,300×3121 + 0×335) / 4,480
      = 3,072,060,300 / 4,480
      = 685,728

eligible 판정:
  A: 0 <= 685,728 → eligible ✓
  B: 984,300 > 685,728 → INELIGIBLE ✗
  C: 0 <= 685,728 → eligible ✓

pick_eevdf() — eligible 태스크 중 earliest VD:
  A.VD = 3,000,000
  C.VD = 9,171,642

→ 선택: 태스크 A (VD=3,000,000이 더 이름)

Step 4: A가 3ms 실행 후 (t=6ms)

A.vruntime = 3,000,000 × 1024/1024 = 3,000,000
A.vruntime(3,000,000) >= A.VD(3,000,000) → deadline 도달!
→ A.VD = 3,000,000 + 3,000,000 = 6,000,000

avg_vruntime:
  avg = (3,000,000×1024 + 984,300×3121 + 0×335) / 4,480
      = (3,072,000,000 + 3,072,060,300) / 4,480
      = 6,144,060,300 / 4,480
      = 1,371,442

eligible:
  A: 3,000,000 > 1,371,442 → INELIGIBLE ✗
  B: 984,300 <= 1,371,442 → eligible ✓ (다시 eligible!)
  C: 0 <= 1,371,442 → eligible ✓

pick_eevdf():
  B.VD = 1,968,600
  C.VD = 9,171,642

→ 선택: 태스크 B (VD=1,968,600이 더 이름)
  B가 다시 선택됨 — weight가 높아 자주 스케줄링!

누적 실행 시간 (실제):
  A: 3ms (1회), B: 3ms (1회), C: 0ms (0회)
  이상적 비율: A=1024, B=3121, C=335 → A:22.8%, B:69.7%, C:7.5%
  실제 비율: A:50%, B:50%, C:0% → 아직 수렴 전

Step 5: B가 다시 3ms 실행 후 (t=9ms)

B.vruntime = 984,300 + 984,300 = 1,968,600
B.VD = 1,968,600 + 984,300 = 2,952,900

avg_vruntime ≈ 2,057,171

eligible:
  A: 3,000,000 > 2,057,171 → INELIGIBLE ✗
  B: 1,968,600 <= 2,057,171 → eligible ✓ (아직 eligible!)
  C: 0 <= 2,057,171 → eligible ✓

pick_eevdf():
  B.VD = 2,952,900
  C.VD = 9,171,642

→ 선택: 태스크 B (VD가 더 이름)

... B가 한 번 더 실행됩니다.

Step 6: B 세 번째 slice 완료 후 (t=12ms)

B.vruntime = 1,968,600 + 984,300 = 2,952,900
B.VD = 2,952,900 + 984,300 = 3,937,200

avg_vruntime ≈ 2,742,899

eligible:
  A: 3,000,000 > 2,742,899 → INELIGIBLE ✗
  B: 2,952,900 > 2,742,899 → INELIGIBLE ✗ (드디어 ineligible!)
  C: 0 <= 2,742,899 → eligible ✓ (유일한 eligible)

→ 선택: 태스크 C (유일한 eligible 태스크)

  C가 드디어 실행됩니다!

누적 실행 (실제): A=3ms, B=9ms, C=0ms → 비율 25:75:0
이상적 비율: 22.8:69.7:7.5
→ C가 0ms 받은 상태 → lag가 크게 양수 → eligible 우선 처리

Interactive 태스크 시뮬레이션

시나리오: A(CPU-bound, nice=0), I(Interactive, nice=0, 주기적 1ms burst)
  둘 다 weight=1024

상태: A가 10ms 동안 실행 중, I는 sleep 중

t=10ms: I가 wakeup! (이전에 sleep 상태로 dequeue됨)

  1. dequeue 시 저장된 I.vlag = entity_lag(avg, I)
     I가 10ms 동안 sleep → lag가 크게 양수 (덜 받음)
     I.vlag ≈ 5,000,000 (약 5ms 분량의 lag)

  2. place_entity(cfs_rq, I, ENQUEUE_WAKEUP):
     I.vruntime = avg_vruntime - I.vlag
               = 10,000,000 - 5,000,000
               = 5,000,000

     I.VD = 5,000,000 + 3,000,000 = 8,000,000

  3. check_preempt_wakeup_fair():
     entity_eligible(I): I.vruntime(5M) <= avg(10M) → eligible ✓
     I.VD(8,000,000) < A.VD(12,000,000) → deadline 비교 통과!
     → resched_curr() → I가 A를 즉시 선점!

  4. I가 1ms burst 실행 후 자발적 sleep:
     I.vruntime += 1,000,000 × 1024/1024 = 1,000,000
     I.vruntime = 6,000,000
     dequeue 시 I.vlag = avg(≈10.5M) - 6M = 4,500,000
     → 다음 wakeup에서도 lag 보존!

핵심: I는 별도의 대화형 휴리스틱 없이
      lag 보존만으로 자연스럽게 빠른 응답을 얻습니다.

Linux 6.12+ EEVDF 개선 사항 (6.12 ~ 6.19)

EEVDF는 Linux 6.6 머지 이후에도 계속 다듬어지고 있습니다. 6.12에서는 짧은 슬립 패턴의 공정성을 보존하는 DELAY_DEQUEUE가 추가되었고, 6.13에서는 PREEMPT_LAZY 모델이 도입되어 EEVDF의 deadline 기반 선점과 새롭게 상호작용합니다. 운영 환경에서 6.6 ~ 6.13 커널을 함께 다루는 경우, 알고리즘 동작의 미묘한 차이를 이해해야 정확한 튜닝이 가능합니다.

DELAY_DEQUEUE — 슬립 직전 lag 보존

기존 EEVDF는 태스크가 슬립하면 즉시 RB-Tree에서 제거하면서 vlag를 마지막에 갱신했습니다. 그런데 짧게 슬립하고 곧 깨어나는 대화형 워크로드(예: GUI 이벤트 루프(Event Loop))는 슬립(Sleep) 동안 avg_vruntime이 진행되어 깨어날 때 큰 양의 lag을 갖게 되고, 결과적으로 다른 태스크보다 부당하게 자주 선택되는 부작용이 있었습니다. Peter Zijlstra가 v6.12에 머지한 DELAY_DEQUEUE는 이 문제를 해결하기 위해 dequeue 자체를 지연시킵니다.

/* kernel/sched/fair.c (v6.12+, 단순화) */
static bool
dequeue_entity(struct cfs_rq *cfs_rq,
               struct sched_entity *se, int flags)
{
    /* DEQUEUE_SLEEP: voluntary sleep 경로 */
    if (sched_feat(DELAY_DEQUEUE) &&
        (flags & DEQUEUE_SLEEP) &&
        entity_eligible(cfs_rq, se)) {
        /* eligible 상태에서 슬립 → 즉시 제거하지 않음 */
        se->sched_delayed = 1;       /* 트리에는 남기되 실행은 안 됨 */
        return false;
    }

    /* not-eligible(lag < 0)이거나 강제 dequeue: 기존 경로 */
    update_curr(cfs_rq);
    update_entity_lag(cfs_rq, se);  /* 마지막 vlag 기록 */
    __dequeue_entity(cfs_rq, se);
    se->on_rq = 0;
    return true;
}

/* wake-up 시: sched_delayed 플래그가 있으면 트리 재삽입 없이 활성화 */
static void
enqueue_entity(struct cfs_rq *cfs_rq,
               struct sched_entity *se, int flags)
{
    if (se->sched_delayed) {
        se->sched_delayed = 0;     /* lag 그대로 보존된 채 재실행 */
        return;
    }
    place_entity(cfs_rq, se, flags);
    __enqueue_entity(cfs_rq, se);
    se->on_rq = 1;
}

DELAY_DEQUEUE 효과 측정

# DELAY_DEQUEUE 활성화 여부 확인 (v6.12+)
cat /sys/kernel/debug/sched/features | tr ' ' '\n' | grep DELAY_DEQUEUE
# 출력: DELAY_DEQUEUE (활성) 또는 NO_DELAY_DEQUEUE (비활성)

# 비활성화하여 회귀 테스트
echo NO_DELAY_DEQUEUE > /sys/kernel/debug/sched/features

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

# sched_delayed 상태인 태스크 확인 (디버깅용)
cat /proc/sched_debug | grep -A2 sched_delayed

PREEMPT_LAZY와 EEVDF 선점 상호작용 (Linux 6.13+)

Linux 6.13에서 추가된 PREEMPT_LAZY는 SCHED_NORMAL(EEVDF) 태스크에 대해서는 협력적 선점만 적용하고, RT 태스크에는 즉시 선점을 적용하는 하이브리드 모델입니다. EEVDF의 입장에서 보면, deadline 비교로 다른 태스크가 선택되어도 현재 실행 중 EEVDF 태스크는 다음 schedule() 지점까지 계속 실행됩니다.

/* kernel/sched/fair.c (v6.13+ 단순화) */
static void
check_preempt_wakeup_fair(struct rq *rq,
                          struct task_struct *p, int wake_flags)
{
    struct sched_entity *se = &rq->curr->se;
    struct sched_entity *pse = &p->se;

    /* deadline 비교: 새 태스크가 더 이른 deadline인가? */
    if (pick_eevdf(cfs_rq) != se) {
        /* PREEMPT_LAZY: SCHED_NORMAL은 즉시 선점하지 않고 NEED_RESCHED_LAZY 마킹 */
        resched_curr_lazy(rq);
        /* 다음 syscall 반환, 명시적 cond_resched(), tick 경계에서 선점 */
        return;
    }
}

/* RT 태스크가 깨어나면 PREEMPT_LAZY와 무관하게 즉시 선점 */
static void check_preempt_curr_rt(struct rq *rq, ...)
{
    resched_curr(rq);  /* NEED_RESCHED — 즉시 선점 */
}

base_slice_ns 디버그 인터페이스 (v6.7+)

EEVDF의 기본 slice 값은 /sys/kernel/debug/sched/base_slice_ns로 조정할 수 있습니다(v6.7부터 노출). 이 값은 sched_attr.sched_runtime을 명시하지 않은 모든 태스크의 deadline 계산에 사용됩니다.

# 현재 base_slice 확인 (HZ=1000 기준 기본 750000ns = 0.75ms)
cat /sys/kernel/debug/sched/base_slice_ns

# 대화형 워크로드 우선: slice 짧게 (500us)
echo 500000 > /sys/kernel/debug/sched/base_slice_ns

# 처리량 우선: slice 길게 (3ms)
echo 3000000 > /sys/kernel/debug/sched/base_slice_ns

# 효과 측정 — 컨텍스트 스위치 빈도가 비례
vmstat 1 5 | awk 'NR>2 {print $12}'
# 짧은 slice → cs/s 증가, 긴 slice → cs/s 감소

Linux 6.14 — CFS 용어 공식 폐기 및 로드 밸런서 개선

Linux 6.14(2025-03)는 EEVDF 도입의 법적·문서적 완성 단계입니다. 커널 공식 문서에서 CFS(Completely Fair Scheduler)라는 용어가 폐기되고 EEVDF가 fair_sched_class의 기본 알고리즘으로 명시되었습니다. 코드 수준에서는 cfs_rq.nr_running이 nr_queued로 이름이 변경되어 EEVDF의 "eligible 대기" 의미를 더 정확하게 반영합니다.

로드 밸런서는 eligible 태스크를 우선적으로 마이그레이션하도록 개선되어, EEVDF의 eligible 조건과 로드 밸런싱이 더 일관되게 작동합니다. NUMA 밸런싱에서 불필요한 통계 계산을 건너뛰는 최적화도 포함되었습니다.

# nr_queued 이름 변경 확인 — v6.14부터 nr_running → nr_queued
grep -r "nr_queued" /proc/sched_debug | head -5
# CFS 용어 폐기: sched_latency_ns, sched_wakeup_granularity_ns 등은 더 이상 유효한 튜너블이 아닙니다
ls /proc/sys/kernel/sched_*

Linux 6.15 — sched_ext 관측성 강화 및 디버그 무조건화

Linux 6.15(2025-05)는 EEVDF와 sched_ext 하이브리드 환경의 관측성을 크게 높입니다. sched_ext에 내부 이벤트 카운터가 추가되어 BPF 스케줄러의 미세한 동작을 /sys/kernel/sched_ext/*/events를 통해 실시간으로 관찰할 수 있게 되었습니다.

또한 CONFIG_SCHED_DEBUG가 무조건 컴파일되도록 변경되어, 릴리스 커널에서도 /proc/sched_debug와 /sys/kernel/debug/sched/의 EEVDF 진단 인터페이스를 항상 사용할 수 있습니다. sched_ext에는 SCX_OPS_ALLOW_QUEUED_WAKEUP 플래그가 추가되어 BPF 스케줄러가 복잡한 하드웨어 토폴로지에서 ttwu_queue를 선택적으로 활성화할 수 있습니다.

# v6.15+: CONFIG_SCHED_DEBUG 무조건화로 릴리스 커널에서도 사용 가능
cat /proc/sched_debug | grep "sched_base_slice"

# sched_ext 이벤트 카운터 (v6.15+, sched_ext 활성화 시)
cat /sys/kernel/sched_ext/global/stats 2>/dev/null || echo "sched_ext not active"

Linux 6.17 — Proxy Execution 및 Lag-Parity 개선

Linux 6.17(2025-09)은 EEVDF 인프라 측면에서 두 가지 중요한 변화를 포함합니다.

첫째, proxy execution의 초기 구현이 추가되었습니다(CONFIG_EXPERT 필요). 뮤텍스(mutex)를 보유한 태스크가 더 높은 우선순위의 waiter를 막고 있을 때, waiter의 스케줄링 컨텍스트(slice, deadline)를 mutex 보유 태스크에 전파하여 우선순위 역전(priority inversion)을 완화합니다. 현재는 단일 run-queue 구성으로 제한됩니다.

둘째, fair scheduler에서 lag와 slice parity를 함께 관리하는 방식이 개선되었습니다. 서로 다른 slice 크기를 가진 태스크들이 혼재할 때 lag 누적이 예상치 않게 커지는 문제가 보완되었습니다.

SMP 코드가 무조건 컴파일되어(단일 프로세서 전용 `#ifdef` 제거), 스케줄러 코드베이스가 단순화되었습니다.

Linux 6.19 — NEXT_BUDDY 재도입 및 sched_avg 회귀 수정

Linux 6.19(2026-02)는 EEVDF에 두 가지 중요한 변화를 도입했습니다.

첫째, NEXT_BUDDY가 재도입되었습니다. EEVDF 초기 구현(6.6)에서는 CFS의 buddy 메커니즘이 제거되었으나, wakeup 선점 시 waker와 wakee가 캐시를 공유하는 경우 마지막 wakee를 더 빨리 스케줄하면 성능이 향상된다는 분석 결과에 따라 NEXT_BUDDY 로직이 EEVDF에 맞게 재설계되어 복귀했습니다. 특히 producer-consumer 패턴의 대화형 워크로드에서 wakeup latency가 개선됩니다.

둘째, sched_avg fold의 se_weight() 누락 회귀가 수정되었습니다. 스케줄링 엔티티의 평균 이용률(sched_avg) 접기(fold) 과정에서 weight 인수가 빠진 커밋이 포함되어 Intel Kernel Test Robot이 schbench 99.9th percentile latency 52.4% 회귀를 보고했으며, tip/sched/core 브랜치에 수정이 합쳐졌습니다.

# NEXT_BUDDY 효과 확인 — wakeup latency 측정 (v6.19+)
perf sched latency -s max | grep "Average"

# sched_avg 정상 여부 확인 — schbench로 99.9th percentile 검증
schbench -m 2 -t 16 -r 30 -p 99.9

v6.6 ~ v6.19 EEVDF 변경 요약

Linux 7.0 — RSEQ Time Slice Extension과 EEVDF 선점 상호작용

Linux 7.0에서 병합된 RSEQ Time Slice Extension은 EEVDF의 deadline 기반 선점 결정과 직접 상호작용합니다. EEVDF는 현재 실행 중인 태스크의 virtual deadline이 만료되거나 더 이른 deadline을 가진 eligible 태스크가 나타나면 선점을 요청합니다. 그런데 RSEQ Time Slice Extension이 활성화된 임계 구간에서는 SCHED_NORMAL 태스크에 한해 선점이 일시 억제됩니다. RT/DEADLINE 태스크는 여전히 즉시 선점합니다.

이 메커니즘은 약 10년간 개발된 기능으로, rseq(2) 시스템 콜(System Call)에 슬라이스 확장 요청 인터페이스를 추가합니다. 임계 구간에서 기회적(opportunistic) 선점 방지를 얻는 것이 목적이며, 실제 우선순위 천장(Priority Ceiling) 프로토콜과 달리 보장보다는 확률적 개선을 추구합니다.

커널 7.0부터: RSEQ Time Slice Extension이 추가되었습니다. 기본값은 5µs, 최대 50µs입니다. 이 값을 크게 설정할수록 최소 스케줄링 지연에 영향을 주므로 워크로드에 따라 조정이 필요합니다.

향후 개발 방향

참고자료

커널 공식 문서

• docs.kernel.org — EEVDF Scheduler — 커널 공식 EEVDF 스케줄러 문서로 알고리즘 개요와 튜너블을 설명합니다.
• docs.kernel.org — Scheduler — 커널 공식 스케줄러 문서 인덱스입니다.
• Documentation/scheduler/sched-eevdf.rst — 커널 소스 트리의 EEVDF RST 원본 문서로, 최신 커널과 함께 업데이트됩니다.
• docs.kernel.org — CFS Bandwidth Control — cgroup 기반 quota/period/burst 공식 문서입니다.
• docs.kernel.org — Scheduler Statistics — /proc/schedstat 해석과 스케줄러 통계 수집 방법을 설명합니다.

LWN 기사

• LWN: An EEVDF CPU scheduler for Linux — Peter Zijlstra의 EEVDF 패치 시리즈를 분석한 핵심 기사입니다.
• LWN: Completing the EEVDF scheduler — EEVDF 완성 과정(v6.12 기준)과 DELAY_DEQUEUE 도입을 다룹니다.
• LWN: The EEVDF scheduler (follow-up) — EEVDF 도입 과정과 남은 과제를 다룬 후속 기사입니다.
• LWN: EEVDF and the latency-nice patch — latency_nice와 EEVDF slice 연동을 설명합니다.
• LWN: Lazy preemption — Linux 6.13 PREEMPT_LAZY의 설계 동기와 EEVDF/RT 태스크 처리 차이를 다룹니다.
• LWN: Delayed dequeue for EEVDF — DELAY_DEQUEUE가 짧은 슬립 태스크의 공정성을 어떻게 보존하는지 분석합니다.
• LWN: Scheduling for the age of heterogeneous computing — EEVDF 이후 P/E 코어 환경에서의 스케줄러 진화 방향을 정리합니다.

논문과 학술 자료

• Ion Stoica, Hussein Abdel-Wahab — Earliest Eligible Virtual Deadline First (1995) — EEVDF 알고리즘을 최초로 제안한 원본 학술 논문입니다.
• Linux Magazine — A Fair Slice: EEVDF — EEVDF의 동작 원리를 개발자 관점에서 정리한 기고 기사입니다.

커널 커밋과 패치 시리즈

• 커밋: sched/fair: Add cfs_rq::avg_vruntime — EEVDF의 기반이 되는 avg_vruntime 도입 커밋입니다.
• 커밋: sched/fair: Implement EEVDF — EEVDF 핵심 로직을 구현한 메인 커밋입니다.
• 커밋: sched/fair: Remove CFS bandwidth slice tunable — CFS→EEVDF 전환 과정에서 제거된 튜너블 관련 커밋입니다.
• LKML: [PATCH 00/24] Complete EEVDF — v6.12 DELAY_DEQUEUE/ENQUEUE_DELAYED를 포함한 EEVDF 완성 패치 시리즈입니다.
• LKML: [GIT PULL] Scheduler changes for v6.12 — Linus에게 보낸 v6.12 스케줄러 PR 요약으로, DELAY_DEQUEUE와 sched_runtime 재해석이 포함됩니다.

소스 코드 탐색

• kernel/sched/fair.c — Bootlin Elixir — EEVDF 핵심 구현이 포함된 CFS/EEVDF 통합 소스 코드입니다.
• include/linux/sched.h — Bootlin Elixir — struct sched_entity와 EEVDF 관련 필드 정의입니다.
• kernel/sched/sched.h — Bootlin Elixir — cfs_rq, rq 구조체(Struct)와 스케줄러 매크로 정의입니다.

벤치마크와 릴리스 노트

• Phoronix: Linux 6.6 EEVDF — Linux 6.6에서 EEVDF 도입 시 초기 벤치마크 결과를 다룹니다.
• Phoronix: EEVDF Scheduler On The Verge Of Being "Complete" — v6.12 직전의 Complete EEVDF 패치 시리즈 소개 기사입니다.
• Phoronix: Linux 6.12 Scheduler Code Adds SCHED_DEADLINE Servers & Complete EEVDF — v6.12에서 머지된 DELAY_DEQUEUE와 SCHED_DEADLINE 서버를 정리합니다.
• Phoronix: Lazy Preemption Merged For Linux 6.13 — v6.13 PREEMPT_LAZY 머지와 벤치마크 관점의 분석입니다.
• KernelNewbies: Linux 6.12 — v6.12 릴리스 요약으로 EEVDF 완성 항목을 포함합니다.
• heise online: Linux 6.12 Scheduler expandable and EEVDF complete — sched_ext와 EEVDF 완성을 함께 다룬 릴리스 기사입니다.
• KernelNewbies: Linux 6.14 — v6.14 릴리스 요약으로 CFS 용어 폐기, nr_queued 이름 변경, 로드 밸런서 개선 항목을 포함합니다.
• KernelNewbies: Linux 6.15 — v6.15 릴리스 요약으로 sched_ext 이벤트 카운터 및 CONFIG_SCHED_DEBUG 무조건화를 포함합니다.
• KernelNewbies: Linux 6.17 — v6.17 릴리스 요약으로 proxy execution 초기 구현과 SMP 무조건 컴파일을 포함합니다.
• KernelNewbies: Linux 6.19 — v6.19 릴리스 요약으로 NEXT_BUDDY 재도입과 sched_avg 회귀 수정을 포함합니다.
• Phoronix: Linux 6.19 52.4% Scheduler Regression Fix — sched_avg fold에서 se_weight() 누락으로 발생한 52.4% schbench 회귀와 수정 과정을 다룹니다.
• Phoronix: Linux 7.0 Scheduler Updates Land Time Slice Extension, Performance & Scalability Work — RSEQ Time Slice Extension 병합과 스케줄러 확장성 개선을 정리합니다.
• LWN: Scheduler time slice extension — RSEQ 기반 타임슬라이스 확장 메커니즘의 설계 배경과 EEVDF 선점과의 상호작용을 설명합니다.
• Phoronix: Linux 7.0 To Focus Just On Full & Lazy Preemption Models For Up-To-Date CPU Archs — PREEMPT_NONE 폐기와 PREEMPT_FULL/LAZY 이분화를 설명합니다.
• Phoronix: AWS Engineer Reports PostgreSQL Performance Halved By Linux 7.0 — PREEMPT_LAZY와 스핀락 집약 워크로드의 충돌 및 RSEQ 해결책을 다룹니다.
• LWN: Improved load balancing with machine learning — sched_ext 기반 ML 부하 분산 스케줄러의 EEVDF 연계 동작을 설명합니다.
• KernelNewbies: Linux 7.0 — v7.0 릴리스 요약으로 RSEQ Time Slice Extension 및 선점 모델 재편을 포함합니다.

관련 문서

EEVDF 스케줄러와 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• 프로세스 스케줄러 — sched_class 계층과 스케줄러 아키텍처
• CFS 스케줄러 상세 — CFS의 vruntime과 로드 밸런싱
• Context Switching — 프로세스 전환 메커니즘
• preempt_count & 선점 모델 — 선점 카운터와 모델
• Real-Time Linux — RT 스케줄링과 PREEMPT_RT
• cpusets & CPU Isolation — CPU 격리(Isolation)와 친화도
• 프로세스 관리 — task_struct와 생명주기