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)는 1995년 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에 deadline 정렬과 min_vruntime·min_slice·max_slice 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) 반환 */
}

/* kernel/sched/fair.c — v7.3.1 pick_eevdf(), 핵심 경로만 발췌 */
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq, bool protect)
{
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    struct sched_entity *se = __pick_first_entity(cfs_rq);
    struct sched_entity *curr = cfs_rq->curr;
    struct sched_entity *best = NULL;

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

    /* PICK_BUDDY: yield_to_task()/cgroup 등이 지정한 next 후보 */
    if (sched_feat(PICK_BUDDY) && protect &&
        cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next))
        return cfs_rq->next;

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

    /* vprot: 현재 태스크가 보호 구간 안이면 계속 실행 */
    if (curr && protect && protect_slice(curr))
        return curr;

    /* leftmost가 eligible이면 즉시 선택 (fast path) */
    if (se && entity_eligible(cfs_rq, se)) {
        best = se;
        goto found;
    }

    /* min_vruntime augmentation으로 eligible 서브트리만 탐색 */
    while (node) {
        struct rb_node *left = node->rb_left;

        if (left && vruntime_eligible(cfs_rq,
                    __node_2_se(left)->min_vruntime)) {
            node = left;
            continue;
        }

        se = __node_2_se(node);

        /* 왼쪽 서브트리에 eligible이 없으면 현재 노드 검사 */
        if (entity_eligible(cfs_rq, se)) {
            best = se;   /* deadline 순서상 가장 이른 eligible */
            break;
        }

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

    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에 calc_delta_fair(slice, se)(= slice × NICE_0_LOAD / weight)를 더한 값입니다. 이 기한 안에 태스크의 서비스가 완료되어야 합니다. EEVDF는 eligible한 태스크 중 VD가 가장 이른 것을 선택합니다.
• lag — 서비스 편차: "이상적으로 받았어야 할 서비스"와 "실제로 받은 서비스"의 차이입니다. lag > 0이면 덜 받은 것, lag < 0이면 더 받은 것입니다. lag가 양수인 태스크만 eligible이 됩니다.

수식 정의

/* kernel/sched/fair.c — v7.3.1 avg_vruntime() */
u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    long weight = cfs_rq->sum_weight;
    s64 delta = 0;

    if (curr && !curr->on_rq)
        curr = NULL;

    if (weight) {
        s64 runtime = cfs_rq->sum_w_vruntime;

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

            runtime += entity_key(cfs_rq, curr) * w;
            weight += w;
        }

        /* 음수 구간에서 내림/올림 방향 보정 */
        if (runtime < 0)
            runtime -= (weight - 1);

        delta = div64_long(runtime, weight);
    }

    update_zero_vruntime(cfs_rq, delta);

    return cfs_rq->zero_vruntime;
}

/* V(t) = Σ((v_i - v0) × w_i) / Σw_i + v0
 *   v0 = cfs_rq->zero_vruntime
 *   Σ((v_i - v0) × w_i) = cfs_rq->sum_w_vruntime
 *   Σw_i               = cfs_rq->sum_weight
 * v7.3.1은 w_i로 계층 부하(h_load.weight)를 사용한다 */

/* entity_key: 가상 시간 좌표를 zero_vruntime 기준 상대값으로 변환 */
static inline s64 entity_key(struct cfs_rq *cfs_rq,
                       struct sched_entity *se)
{
    return vruntime_op(se->vruntime, "-", cfs_rq->zero_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 — v7.3.1 vruntime_eligible() */
static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 key, avg = cfs_rq->sum_w_vruntime;
    long load = cfs_rq->sum_weight;

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

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

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

    /* avg/load ≥ key ⇔ vruntime ≤ V(t) */
#ifdef CONFIG_64BIT
#ifdef CONFIG_ARCH_SUPPORTS_INT128
    return avg >= (__int128)key * load;
#else
    s64 rhs;

    /* 곱셈 오버플로 시 key 부호가 정답을 결정한다 */
    if (check_mul_overflow(key, load, &rhs))
        return key <= 0;

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

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

avg_vruntime 유지

/* kernel/sched/fair.c — v7.3.1, 간략화 */
static void sum_w_vruntime_add(struct cfs_rq *cfs_rq,
                                 struct sched_entity *se)
{
    unsigned long weight = avg_vruntime_weight(cfs_rq,
                                                se->h_load.weight);
    s64 key = entity_key(cfs_rq, se);

    cfs_rq->sum_w_vruntime += key * weight;
    cfs_rq->sum_weight += weight;
}

static void sum_w_vruntime_sub(struct cfs_rq *cfs_rq,
                                 struct sched_entity *se)
{
    unsigned long weight = avg_vruntime_weight(cfs_rq,
                                                se->h_load.weight);
    s64 key = entity_key(cfs_rq, se);

    cfs_rq->sum_w_vruntime -= key * weight;
    cfs_rq->sum_weight -= weight;
}

/* PARANOID_AVG=true이면 sum_shift를 올려 재계산하는
 * sum_w_vruntime_add_paranoid() 경로를 사용한다 (기본 false) */

Virtual Deadline 계산

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

계산 공식

VD = VE + calc_delta_fair(slice, se)
   = VE + slice × NICE_0_LOAD / weight

여기서:
  VD     = virtual deadline
  VE     = eligible time (= 현재 vruntime)
  slice  = 요청 실행 시간 (sysctl_sched_base_slice, 기본 0.7ms)
  weight = nice → sched_prio_to_weight[] 변환 값

예시 (sched_base_slice = 700,000 ns):
  nice 0  (weight 1024): VD = VE + 700,000 × 1024 / 1024 = VE + 700,000
  nice -5 (weight 3121): VD = VE + 700,000 × 1024 / 3121 = VE + 229,669
  nice 5  (weight 335):  VD = VE + 700,000 × 1024 / 335  = VE + 2,139,701

→ weight가 클수록 VD 간격이 짧아져 더 자주/먼저 선택됨

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

    /* 기본 slice는 sysctl, sched_runtime으로 지정한 값은 유지 */
    if (!se->custom_slice)
        se->slice = sysctl_sched_base_slice;

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

    /* 요청한 slice를 다 썼으므로 재스케줄링 필요 */
    return true;
}

/* se->slice: 실제 실행 시간 단위 (nanoseconds)
 * 기본값 = sysctl_sched_base_slice (v7.3.1: 0.7ms)
 * sched_setattr()의 sched_runtime으로 태스크별 재정의 가능
 *   → se->custom_slice = 1, 0.1ms ~ 100ms로 clamp */

Lag 추적 메커니즘

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

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

추상적인 수식보다 구체적인 예시로 먼저 lag의 직관을 잡겠습니다. 동일한 가중치(weight = 1024, nice = 0)를 가진 프로세스 A와 B 두 개가 실행 중인 상황을 가정합니다. 물리 CPU가 하나뿐이므로 이상적인 공정 분배라면 A와 B 각각이 50%씩 CPU를 받아야 합니다. 계산을 단순하게 보이기 위해 한 번의 slice를 3ms로 가정합니다(실제 기본값은 0.7ms이며, 비율 관계는 동일합니다).

이 예시에서 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 — entity_lag() (v7.3.1) */
static s64 entity_lag(struct cfs_rq *cfs_rq,
                        struct sched_entity *se, u64 avruntime)
{
    u64 max_slice = cfs_rq_max_slice(cfs_rq) + TICK_NSEC;
    s64 vlag, limit;

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

    /* 상한: |lag| <= (cfs_rq 최대 slice + 1 tick)의 가상 시간 */
    limit = calc_delta_fair(max_slice, se);
    return clamp(vlag, -limit, limit);
}

pick_next_entity() 구현

EEVDF의 핵심 함수인 pick_eevdf(cfs_rq, protect)는 eligible한 태스크 중 가장 이른 virtual deadline을 가진 태스크를 O(log N)에 찾습니다. RB-Tree는 deadline 순서로 정렬되어 있고, 각 노드는 서브트리의 min_vruntime을 유지하므로 eligible 후보가 없는 서브트리를 통째로 가지치기(pruning)할 수 있습니다.

/* kernel/sched/fair.c — v7.3.1 pick_eevdf()의 서브트리 pruning */
static struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq, bool protect)
{
    /* ... h_nr_queued == 1, PICK_BUDDY, curr/protect_slice fast path 생략 ... */

    /* 트리는 deadline 순서이므로, in-order에서 처음 만난
     * eligible 엔티티가 곧 earliest deadline이다 */
    while (node) {
        struct rb_node *left = node->rb_left;

        /* 왼쪽 서브트리의 최소 vruntime이 eligible이면
         * 그 안에 eligible 엔티티가 반드시 존재한다 */
        if (left && vruntime_eligible(cfs_rq,
                    __node_2_se(left)->min_vruntime)) {
            node = left;
            continue;
        }

        se = __node_2_se(node);

        /* 왼쪽에 eligible이 없으면 현재 노드 검사 */
        if (entity_eligible(cfs_rq, se)) {
            best = se;
            break;
        }

        node = node->rb_right;
    }

    /* eligible을 찾지 못하면 curr과 비교해 결정 */
    if (!best || (curr && entity_before(curr, best)))
        best = curr;

    return best;
}

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

    se = pick_eevdf(cfs_rq, protect);
    if (se->sched_delayed) {
        /* DELAY_DEQUEUE로 지연된 태스크는 지금 꺼낸다 */
        __dequeue_task(rq, task_of(se),
                       DEQUEUE_SLEEP | DEQUEUE_DELAYED);
        return NULL;
    }
    return se;
}

슬라이스 메커니즘

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는 태스크 수와 무관하게 고정됩니다 (기본값 sysctl_sched_base_slice = 700,000ns = 0.7ms). 선점 기준도 "타임슬라이스 소진"이 아니라 "현재 태스크의 deadline을 더 이른 deadline을 가진 eligible 태스크가 추월"하는 시점입니다.

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

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

결과: 태스크 수가 늘어도 slice 크기 불변.
      지연은 lag 상한(-r_max < lag < max(r_max, q))과
      deadline 간격으로 제한되며, 태스크 수에 선형 비례하지 않음

/* kernel/sched/fair.c — v7.3.1 */
unsigned int sysctl_sched_base_slice = 700000ULL;
static unsigned int normalized_sysctl_sched_base_slice = 700000ULL;

/* __setscheduler_params(): 태스크별 slice 결정 */
if (attr->sched_runtime) {
    se->custom_slice = 1;
    se->slice = clamp_t(u64, attr->sched_runtime,
                        100 * NSEC_PER_USEC,      /* 100us */
                        100 * NSEC_PER_MSEC);     /* 100ms */
} else {
    se->custom_slice = 0;
    se->slice = sysctl_sched_base_slice;
}

/* update_curr(): 실행 시간 회계 + deadline 갱신 + 선점 요청 */
static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->h_curr;
    struct rq *rq = rq_of(cfs_rq);
    s64 delta_exec;
    bool resched;

    if (unlikely(!curr))
        return;

    delta_exec = update_se(rq, curr);   /* exec_start 갱신 */
    if (unlikely(delta_exec <= 0))
        return;

    account_cfs_rq_runtime(cfs_rq, delta_exec);

    if (!entity_is_task(curr))
        return;

    cfs_rq = &rq->cfs;

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

    dl_server_update(&rq->fair_server, delta_exec);

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

    /* deadline을 넘었거나 보호 구간을 벗어나면 지연 선점 요청 */
    if (resched || !protect_slice(curr)) {
        resched_curr_lazy(rq);
        clear_buddies(cfs_rq, curr);
    }
}

EEVDF 선점 규칙

EEVDF에서 선점은 두 가지 경로로 발생합니다: tick 기반 선점(현재 태스크의 deadline 도달)과 wakeup 기반 선점(새로 깨어난 태스크가 더 이른 deadline을 가짐). v7.3.1 기준으로 tick 경로는 update_curr() → update_deadline()이 담당하고, wakeup 경로는 wakeup_preempt_fair()가 담당합니다. CFS의 check_preempt_tick()과 wakeup_gran 기반 판정은 더 이상 존재하지 않습니다.

선점 판단 규칙

선점 발생 조건 (v7.3.1):

1. Tick 경로 (update_curr → update_deadline):
   vruntime >= deadline
   → deadline을 새로 계산하고 resched_curr_lazy(rq) 요청
   단, cfs_rq->h_nr_queued == 1이면 경쟁자가 없으므로 생략
   RUN_TO_PARITY && protect_slice(curr)이면 선점을 보류
   CONFIG_SCHED_HRTICK이면 slice 경계에 맞춰 tick을 미리 설정

2. Wakeup 경로 (wakeup_preempt_fair):
   - p 또는 donor가 fair 클래스가 아니면 NONE
   - WAKEUP_PREEMPTION이 꺼져 있으면 NONE
   - idle entity ↔ non-idle entity 교체는 즉시 preempt
   - PREEMPT_SHORT && pse->slice < se->slice → PREEMPT_WAKEUP_SHORT
   - WF_FORK wakeup은 wakee 선점에서 제외
   - NEXT_BUDDY && set_preempt_buddy() → PICK (WF_SYNC면 RESCHED)
   - pick_next_entity(rq, protect) 결과가 pse이면 즉시 preempt
   - PREEMPT_SHORT && pse가 eligible이면 protection을 취소하고 preempt

3. CFS에서 제거된 조건:
   - check_preempt_tick()의 ideal_runtime 비교
   - sched_wakeup_granularity(wakeup_gran) 버퍼
   - sched_min_granularity 기반 최소 실행 보장
   (최소 실행 보장은 base_slice + protect_slice()/vprot로 대체)

/* kernel/sched/fair.c — tick 경로 (v7.3.1, 단순화) */
static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    update_curr(cfs_rq);
    update_load_avg(cfs_rq, curr, UPDATE_TG);
    update_cfs_group(curr);

#ifdef CONFIG_SCHED_HRTICK
    if (queued) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
#endif
}

/* update_curr()의 선점 판단 부분 */
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    resched = update_deadline(cfs_rq, curr);

    /* ... fair_server 회계 ... */

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

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

/* kernel/sched/fair.c — wakeup_preempt_fair() (v7.3.1, 단순화) */
static void wakeup_preempt_fair(struct rq *rq, struct task_struct *p, int wake_flags)
{
    enum preempt_wakeup_action preempt_action = PREEMPT_WAKEUP_PICK;
    struct task_struct *donor = rq->donor;
    struct sched_entity *nse, *se = &donor->se, *pse = &p->se;
    struct cfs_rq *cfs_rq = &rq->cfs;

    if (p->sched_class != &fair_sched_class ||
        donor->sched_class != &fair_sched_class)
        return;

    if (!sched_feat(WAKEUP_PREEMPTION))
        return;

    update_curr_fair(rq);

    /* idle ↔ non-idle 교체는 즉시 선점 */
    if (se_is_idle(se) && !se_is_idle(pse))
        goto preempt;

    /* p의 slice가 더 짧고 eligible이면 curr의 slice 보호를 무시 */
    if (sched_feat(PREEMPT_SHORT) && (pse->slice < se->slice)) {
        preempt_action = PREEMPT_WAKEUP_SHORT;
        goto pick;
    }

    if (wake_flags & WF_FORK)
        goto update;

    if (sched_feat(NEXT_BUDDY) && set_preempt_buddy(cfs_rq, pse)) {
        if (wake_flags & WF_SYNC)
            preempt_action = preempt_sync(rq, wake_flags, pse, se);
    }

pick:
    if (cfs_rq->h_nr_queued) {
        nse = pick_next_entity(rq, preempt_action != PREEMPT_WAKEUP_SHORT);
        if (unlikely(!nse))
            goto pick;
        if (nse == pse)
            goto preempt;
    }

    if (preempt_action == PREEMPT_WAKEUP_SHORT && entity_eligible(cfs_rq, pse))
        goto preempt;
update:
    if (sched_feat(RUN_TO_PARITY))
        update_protect_slice(cfs_rq, se);
    return;

preempt:
    cancel_protect_slice(se);
    if (preempt_action == PREEMPT_WAKEUP_SHORT)
        set_short_buddy(cfs_rq, pse);
    resched_curr_lazy(rq);
}

Augmented RB-Tree

EEVDF의 효율적 구현을 위해 기존 CFS의 RB-Tree에 세 가지 보조 키가 추가되었습니다: min_vruntime, min_slice, max_slice. 트리는 deadline 순서로 정렬되지만, "eligible 여부"는 vruntime으로 판정하므로 서브트리의 최소 vruntime을 알면 eligible 후보가 존재하는지 O(1)에 판단할 수 있습니다. min_slice/max_slice는 cfs_rq_min_slice()와 slice 보호(protect_slice) 계산에 사용됩니다.

/* kernel/sched/fair.c — v7.3.1 RB-Tree augmentation */

/* 자식의 보조 키와 비교해 더 작은 값으로 갱신 */
static inline void __min_vruntime_update(struct sched_entity *se,
                                            struct rb_node *node)
{
    if (node) {
        struct sched_entity *rse = __node_2_se(node);

        if (vruntime_cmp(se->min_vruntime, ">", rse->min_vruntime))
            se->min_vruntime = rse->min_vruntime;
    }
}

/* se->min_vruntime = min(se->vruntime, {left,right}->min_vruntime) */
static inline bool min_vruntime_update(struct sched_entity *se, bool exit)
{
    u64 old_min_vruntime = se->min_vruntime;
    u64 old_min_slice = se->min_slice;
    u64 old_max_slice = se->max_slice;
    struct rb_node *node = &se->run_node;

    se->min_vruntime = se->vruntime;
    __min_vruntime_update(se, node->rb_right);
    __min_vruntime_update(se, node->rb_left);

    se->min_slice = se->slice;
    __min_slice_update(se, node->rb_right);
    __min_slice_update(se, node->rb_left);

    se->max_slice = se->slice;
    __max_slice_update(se, node->rb_right);
    __max_slice_update(se, node->rb_left);

    return se->min_vruntime == old_min_vruntime &&
           se->min_slice == old_min_slice &&
           se->max_slice == old_max_slice;
}

RB_DECLARE_CALLBACKS_MULTI(static, min_vruntime_cb, struct sched_entity,
                          run_node, min_vruntime_copy, min_vruntime_update);

sched_entity EEVDF 관련 필드 상세

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

/* include/linux/sched.h — sched_entity EEVDF 관련 필드 (v7.3.1) */
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_vruntime;   /* augmented: 서브트리 최소 vruntime */
    u64                  min_slice;      /* augmented: 서브트리 최소 slice */
    u64                  max_slice;      /* augmented: 서브트리 최대 slice */
    unsigned char        sched_delayed;  /* 지연 dequeue 상태 */
    unsigned char        rel_deadline;   /* deadline이 상대값인 동안 1 */
    unsigned char        custom_slice;   /* sched_runtime으로 slice 재정의 */

    /* === 공통 === */
    s64                  vlag;           /* 가상 lag (dequeue 시 저장) */
    u64                  vprot;          /* slice 보호용 virtual deadline */
    u64                  slice;          /* 요청 실행 시간 (ns) */

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

/* kernel/sched/sched.h — cfs_rq의 EEVDF 관련 필드 (v7.3.1) */
struct cfs_rq {
    /* === 기존 === */
    struct load_weight    load;
    unsigned int         nr_queued;
    struct rb_root_cached tasks_timeline;

    /* === EEVDF 추가 === */
    s64                  sum_w_vruntime; /* Σ((v_i - v0) × w_i) */
    u64                  sum_weight;     /* Σ(w_i) */
    u64                  zero_vruntime;  /* 가중 평균의 기준점 v0 */
    unsigned int         sum_shift;      /* 정밀도 보정 시프트 */

    /* ... */
};

place_entity() 분석

place_entity()는 태스크가 enqueue될 때(fork, wakeup, migrate) vruntime과 deadline을 배치하는 핵심 함수입니다. EEVDF에서는 lag 보존이 핵심 원칙이며, v7.3.1 구현은 lag 팽창(lag inflation), 상대 deadline 마이그레이션, 새 태스크의 반 slice 시작을 모두 반영합니다.

배치 시나리오별 동작

/* kernel/sched/fair.c — place_entity() (v7.3.1, 단순화) */
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    u64 vslice, vruntime = avg_vruntime(cfs_rq);
    unsigned int nr_queued = cfs_rq->h_nr_queued;
    bool update_zero = false;
    s64 lag = 0;

    if (!se->custom_slice)
        se->slice = sysctl_sched_base_slice;
    vslice = calc_delta_fair(se->slice, se);

    if (flags & ENQUEUE_QUEUED)
        nr_queued -= 1;

    /* PLACE_LAG: 새 엔티티가 가중 평균을 끌어내리는 효과를 보정 */
    if (sched_feat(PLACE_LAG) && nr_queued && se->vlag) {
        long load, weight;

        lag = se->vlag;

        load = cfs_rq->sum_weight;
        if (curr && curr->on_rq)
            load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
        if (WARN_ON_ONCE(!load))
            load = 1;
        weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);

        /* lag_i = (W + w_i) * vlag_i / W */
        lag += div64_long(lag * weight, load);

        if (weight > load)
            update_zero = true;
    }

    se->vruntime = vruntime - lag;

    if (update_zero)
        update_zero_vruntime(cfs_rq, -lag);

    /* 마이그레이션: deadline을 상대값으로 옮긴 뒤 종료 */
    if (sched_feat(PLACE_REL_DEADLINE) && se->rel_deadline) {
        se->deadline += se->vruntime;
        se->rel_deadline = 0;
        return;
    }

    /* 새 태스크는 평균적으로 slice 중간에서 시작하므로 반 slice */
    if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
        vslice /= 2;

    se->deadline = se->vruntime + vslice;
}

/* dequeue 시 lag 저장 — 다음 enqueue의 place_entity()에서 복원 */
static bool __dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
    struct sched_entity *se = &p->se;
    struct cfs_rq *cfs_rq = &rq->cfs;

    clear_buddies(cfs_rq, se);
    update_curr_eevdf(cfs_rq);
    update_entity_lag(cfs_rq, se);   /* se->vlag = entity_lag(...) */
    /* ... DELAY_DEQUEUE 판단 ... */
}

/* entity_lag(): max_slice + TICK_NSEC를 상한으로 클램프 */
static s64 entity_lag(struct cfs_rq *cfs_rq,
                        struct sched_entity *se, u64 avruntime)
{
    u64 max_slice = cfs_rq_max_slice(cfs_rq) + TICK_NSEC;
    s64 vlag, limit;

    vlag = avruntime - se->vruntime;
    limit = calc_delta_fair(max_slice, se);

    return clamp(vlag, -limit, limit);
}

update_curr() 변경점

update_curr()는 현재 실행 중인 태스크의 vruntime을 갱신하고, deadline 도달 시 선점을 요청하는 핵심 함수입니다. v7.3.1에서는 cfs_rq->curr 대신 cfs_rq->h_curr를 사용하고, update_se()·protect_slice()·resched_curr_lazy()가 추가되었습니다.

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

    if (unlikely(!curr))
        return;

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

    account_cfs_rq_runtime(cfs_rq, delta_exec);

    if (!entity_is_task(curr))
        return;

    cfs_rq = &rq->cfs;

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

    dl_server_update(&rq->fair_server, delta_exec);

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

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

update_deadline() 상세

/* kernel/sched/fair.c — update_deadline() (v7.3.1) */
static bool update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    /* 아직 deadline에 도달하지 않았으면 그대로 둔다 */
    if (vruntime_cmp(se->vruntime, "<", se->deadline))
        return false;

    /* custom_slice가 아니면 base slice로 재설정 */
    if (!se->custom_slice)
        se->slice = sysctl_sched_base_slice;

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

    /* zero_vruntime를 최신 상태로 갱신 (반환값은 사용하지 않음) */
    avg_vruntime(cfs_rq);

    /* slice를 소진했으므로 재스케줄 필요 */
    return true;
}

tick 기반 선점 판단

v7.3.1의 tick 경로에는 CFS의 check_preempt_tick()이 없습니다. task_tick_fair() → entity_tick() → update_curr()가 실행되고, update_deadline()이 deadline 도달을 알리면 resched_curr_lazy()가 선점을 요청합니다.

/* kernel/sched/fair.c — task_tick_fair() / entity_tick() (v7.3.1, 단순화) */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct sched_entity *se = &curr->se;

    if (se->on_rq) {
        struct cfs_rq *cfs_rq;

        for_each_sched_entity(se) {
            cfs_rq = cfs_rq_of(se);
            entity_tick(cfs_rq, se, queued);
        }
        /* ... reweight_eevdf() ... */
    }
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    update_curr(cfs_rq);
    update_load_avg(cfs_rq, curr, UPDATE_TG);
    update_cfs_group(curr);

#ifdef CONFIG_SCHED_HRTICK
    if (queued) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
#endif
}

wakeup 선점 판단

wakeup 경로는 wakeup_preempt_fair()가 담당합니다. CFS의 wakeup_gran 버퍼 대신 PREEMPT_SHORT, NEXT_BUDDY, WF_SYNC, slice 보호(protect_slice())가 선점 여부를 결정합니다.

/* kernel/sched/fair.c — wakeup_preempt_fair() (v7.3.1, 단순화) */
static void wakeup_preempt_fair(struct rq *rq, struct task_struct *p, int wake_flags)
{
    enum preempt_wakeup_action preempt_action = PREEMPT_WAKEUP_PICK;
    struct task_struct *donor = rq->donor;
    struct sched_entity *nse, *se = &donor->se, *pse = &p->se;
    struct cfs_rq *cfs_rq = &rq->cfs;

    if (p->sched_class != &fair_sched_class ||
        donor->sched_class != &fair_sched_class)
        return;

    if (!sched_feat(WAKEUP_PREEMPTION))
        return;

    update_curr_fair(rq);

    /* idle ↔ non-idle 교체는 즉시 선점 */
    if (se_is_idle(se) && !se_is_idle(pse))
        goto preempt;

    /* wakee의 slice가 더 짧고 eligible이면 curr의 보호를 무시 */
    if (sched_feat(PREEMPT_SHORT) && (pse->slice < se->slice)) {
        preempt_action = PREEMPT_WAKEUP_SHORT;
        goto pick;
    }

    if (wake_flags & WF_FORK)
        goto update;

    if (sched_feat(NEXT_BUDDY) && set_preempt_buddy(cfs_rq, pse)) {
        if (wake_flags & WF_SYNC)
            preempt_action = preempt_sync(rq, wake_flags, pse, se);
    }

pick:
    if (cfs_rq->h_nr_queued) {
        nse = pick_next_entity(rq, preempt_action != PREEMPT_WAKEUP_SHORT);
        if (unlikely(!nse))
            goto pick;
        if (nse == pse)
            goto preempt;
    }

    if (preempt_action == PREEMPT_WAKEUP_SHORT && entity_eligible(cfs_rq, pse))
        goto preempt;

update:
    if (sched_feat(RUN_TO_PARITY))
        update_protect_slice(cfs_rq, se);
    return;

preempt:
    cancel_protect_slice(se);
    if (preempt_action == PREEMPT_WAKEUP_SHORT)
        set_short_buddy(cfs_rq, pse);
    resched_curr_lazy(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 slice 확인 (debugfs, 단위 ns)
cat /sys/kernel/debug/sched/base_slice_ns
# 700000

# slice 줄이기: 더 짧은 deadline → 더 빠른 응답, 더 잦은 선점
echo 1000000 > /sys/kernel/debug/sched/base_slice_ns  # 1ms

# slice 늘리기: 더 긴 deadline → 더 나은 처리량, 더 적은 선점
echo 10000000 > /sys/kernel/debug/sched/base_slice_ns  # 10ms

# sched_debug에서 cfs_rq별 slice/deadline 통계 확인
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 (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/<PID>/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가 너무 큰지 확인 (debugfs, ns)
cat /sys/kernel/debug/sched/base_slice_ns
# 기본값 700000(0.7ms)보다 크면 줄여보기
echo 700000 > /sys/kernel/debug/sched/base_slice_ns

# 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. base_slice_ns 설정 (debugfs)
      - 기본 0.7ms
      - 데스크톱: 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 — avg_vruntime() / update_zero_vruntime() (v7.3.1) */
void update_zero_vruntime(struct cfs_rq *cfs_rq, s64 delta)
{
    /* v0를 delta만큼 옮기면 sum_w_vruntime은 -delta*sum_weight만큼 보정 */
    cfs_rq->sum_w_vruntime -= cfs_rq->sum_weight * delta;
    cfs_rq->zero_vruntime += delta;
}

u64 avg_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    long weight = cfs_rq->sum_weight;
    s64 delta = 0;

    if (curr && !curr->on_rq)
        curr = NULL;

    if (weight) {
        s64 runtime = cfs_rq->sum_w_vruntime;

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

            runtime += entity_key(cfs_rq, curr) * w;
            weight += w;
        }

        /* 음수일 때 floor/ceiling을 뒤집어 left bias 확보 */
        if (runtime < 0)
            runtime -= (weight - 1);

        delta = div64_long(runtime, weight);
    } else if (curr) {
        delta = curr->vruntime - cfs_rq->zero_vruntime;
    }

    update_zero_vruntime(cfs_rq, delta);

    return cfs_rq->zero_vruntime;
}

enqueue/dequeue 흐름

/* kernel/sched/fair.c — enqueue_task_fair()의 배치/삽입 순서 (v7.3.1, 단순화) */
static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct sched_entity *se = &p->se;
    struct cfs_rq *cfs_rq = &rq->cfs;
    unsigned long weight;
    bool curr;

    update_curr_eevdf(cfs_rq);

    curr = (cfs_rq->curr == se);
    if (curr)
        place_entity(cfs_rq, se, flags);

    if (se->on_rq && se->sched_delayed)
        requeue_delayed_entity(cfs_rq, se);

    weight = enqueue_hierarchy(p, flags);

    if (!curr) {
        reweight_eevdf(cfs_rq, se, weight, false);
        place_entity(cfs_rq, se, flags | ENQUEUE_QUEUED);
        __enqueue_entity(cfs_rq, se);
    }

    add_nr_running(rq, 1);
}

static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    /* PELT/cgroup 가중치 갱신 + 회계. RB-Tree 삽입은 하지 않는다. */
    update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
    se_update_runnable(se);
    update_cfs_group(se);
    account_entity_enqueue(cfs_rq, se);
    se->on_rq = 1;
}

/* __enqueue_entity — deadline 정렬 RB-Tree 삽입 + augmentation (v7.3.1) */
static void __enqueue_entity(struct cfs_rq *cfs_rq,
                              struct sched_entity *se)
{
    sum_w_vruntime_add(cfs_rq, se);
    se->min_vruntime = se->vruntime;
    se->min_slice = se->slice;
    se->max_slice = se->slice;

    rb_add_augmented_cached(&se->run_node,
                            &cfs_rq->tasks_timeline,
                            __entity_less,
                            &min_vruntime_cb);
    /* 세 augmented 키가 회전/삽입 시 자동 전파됨 */
}

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 태스크) 결과:

이 차이는 slice 길이에 비해 무시할 수 있는 수준이며, 실무적으로 체감되지 않습니다.

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)
   • reweight_eevdf(cfs_rq, se, weight, false)
   • place_entity(cfs_rq, se, flags | ENQUEUE_QUEUED) — vruntime = avg_vruntime - lag(lag 복원), deadline = vruntime + calc_delta_fair(slice, se)
   • __enqueue_entity(cfs_rq, se) — RB-Tree 삽입 + min_vruntime/min_slice/max_slice 전파
   • enqueue_entity(cfs_rq, se, flags) — PELT/cgroup 회계, on_rq = 1
2. wakeup_preempt_fair(rq, p, wake_flags) — 선점 판단
   • PREEMPT_SHORT/NEXT_BUDDY/WF_SYNC로 preempt_action 결정
   • pick_next_entity(rq, protect) — pick_eevdf()로 실제 후보 확인
   • resched_curr_lazy(rq) — 선점 예약
3. schedule() → __schedule() — 태스크 선택
   • pick_next_task_fair(rq)
   • pick_next_entity(rq, protect)
   • pick_eevdf(cfs_rq, protect) — 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)
   • update_deadline(cfs_rq, curr) — vruntime >= deadline이면 resched_curr_lazy 요청
5. dequeue_task_fair() — 태스크 sleep
   • dequeue_entity(cfs_rq, se)
   • update_entity_lag(cfs_rq, se) — se->vlag에 lag 저장 (entity_lag()로 클램프)
   • __dequeue_entity(cfs_rq, se)
   • sum_w_vruntime_sub(cfs_rq, se)

수치 시뮬레이션 예제

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

초기 조건

시스템 설정:
  slice = 3ms (계산 편의를 위한 가정, 실제 기본값 0.7ms)
  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(cfs_rq, I, avg)
     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_rq.nr_running → nr_queued 개명

Linux 6.14(2025-03)에서 cfs_rq.nr_running이 nr_queued로 개명되었습니다(v6.12 sched.h에는 nr_running만, v6.14에는 nr_queued·h_nr_queued가 존재). 실행 중인 태스크가 아니라 "큐에 올라 대기 중인 엔티티"를 센다는 EEVDF의 의미를 이름에 반영한 변경입니다.

문서도 함께 정비되었습니다. EEVDF 설명 문서(Documentation/scheduler/sched-eevdf.rst)는 v6.12에 추가되었고, 기존 sched-design-CFS.rst는 별도 문서로 계속 유지됩니다. 즉 CFS라는 용어가 삭제된 것이 아니라, EEVDF 문서가 나란히 추가된 것입니다.

# nr_queued 개명 확인 — v6.14부터 nr_running → nr_queued
grep -m5 "nr_queued" /proc/sched_debug
# EEVDF 전환 후 사라진 CFS 튜너블 확인 (목록에 없음)
ls /proc/sys/kernel/sched_latency_ns /proc/sys/kernel/sched_wakeup_granularity_ns 2>/dev/null || echo "CFS tunables removed"

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

Linux 6.15(2025-05)는 EEVDF와 sched_ext 하이브리드 환경의 관측성을 크게 높입니다. sched_ext에 내부 이벤트 카운터가 추가되어 BPF 스케줄러의 미세한 동작을 /sys/kernel/sched_ext/root/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 옵션이 제거되어 릴리스 커널에서도 항상 사용 가능
grep -m1 "base_slice" /proc/sched_debug

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

Linux 6.17 — Proxy Execution, SMP 전용 컴파일, run-to-parity 정비

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

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

둘째, 단일 프로세서 전용 코드 경로가 제거되어 스케줄러가 SMP 전제로만 컴파일됩니다(sched/smp: Make SMP unconditional). 이에 따라 CONFIG_SMP 분기가 줄고 코드베이스가 단순해졌습니다.

셋째, run-to-parity slice 보호가 Vincent Guittot의 패치 시리즈로 정비되었습니다. 6.16까지는 pick 시점의 deadline을 vlag에 임시로 복사해 두었고, 소스 주석에도 "HACK"으로 표기되어 있었습니다. 6.17에서 sched_entity에 전용 vprot 필드가 추가되고, 보호 구간이 "현재 태스크의 slice 전체"가 아니라 enqueue된 엔티티 중 가장 짧은 slice로 제한되었습니다. 짧은 slice를 가진 태스크가 긴 slice 태스크의 보호 구간 때문에 오래 기다리며 lag가 커지는 문제를 줄이는 변경입니다. RUN_TO_PARITY와 PREEMPT_SHORT는 v6.17에서도 기본 활성(SCHED_FEAT(..., true))입니다.

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

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

    slice = min(slice, se->slice);
    if (slice != se->slice)
        vprot = min_vruntime(vprot, se->vruntime +
                            calc_delta_fair(slice, se));

    se->vprot = vprot;
}

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 및 선점 모델 재편을 포함합니다.