EEVDF 스케줄러(Scheduler)

Earliest Eligible Virtual Deadline First(EEVDF) 스케줄러는 Linux 6.6에서 CFS의 핵심 pick 로직을 대체한 공정 스케줄링 알고리즘입니다. 1996년 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보다 더 나은 지연 보장을 제공합니다.
 *
 * 핵심 변경:
 * - pick_next_entity()가 leftmost(min vruntime) 대신
 *   eligible 태스크 중 earliest deadline을 선택
 * - sched_entity에 deadline, slice 필드 추가
 * - RB-Tree에 min_deadline augmentation 추가
 * - 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의 스케줄링 결정을 완전히 결정합니다.

정의

/* 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) 판단하는 것입니다.

수학적 정의

논문에서 태스크 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 유지

/* avg_vruntime은 태스크 enqueue/dequeue 시 증분 업데이트 */
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)의 차이를 추적합니다.

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 계산의 기초가 됩니다.

/* 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에서 선점(preemption)은 두 가지 경로로 발생합니다: 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 비율)과 독립적으로 응답 지연(latency)을 제어합니다.

매핑(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: 태스크 기아(Starvation) 의심

# 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 흐름

/* enqueue_entity — EEVDF 필드 초기화 포함 */
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 태스크):
 *   CFS pick:   ~30ns (O(1) rb_first_cached)
 *   EEVDF pick:  ~80ns (O(log 100) ≈ O(7))
 *
 * 차이: ~50ns — 3ms slice 대비 0.002% 오버헤드
 * → 사실상 무시 가능 */

EEVDF vs SCHED_DEADLINE

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

/* sched_class 우선순위 계층에서의 위치:
 *
 * 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)
 *    → 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()
 *    → 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. 태스크 sleep: dequeue_task_fair()
 *    → 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 보존만으로 자연스럽게 빠른 응답을 얻습니다.

향후 개발 방향

참고 자료

• docs.kernel.org — EEVDF Scheduler — 커널 공식 EEVDF 스케줄러 문서입니다.
• docs.kernel.org — Scheduler — 커널 공식 스케줄러 문서 인덱스입니다.
• LWN: An EEVDF CPU scheduler for Linux — Peter Zijlstra의 EEVDF 패치 시리즈를 분석한 핵심 기사입니다.
• LWN: The EEVDF scheduler — EEVDF 스케줄러의 동작 원리와 CFS 대비 개선점을 상세히 설명합니다.
• LWN: Completing the EEVDF scheduler — EEVDF 도입 과정과 남은 과제를 다룬 후속 기사입니다.
• LWN: EEVDF and the latency-nice patch — latency_nice와 EEVDF slice 연동을 설명하는 기사입니다.
• Ion Stoica, Hussein Abdel-Wahab — Earliest Eligible Virtual Deadline First (1995) — 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로의 전환 과정에서 제거된 튜너블 관련 커밋입니다.
• kernel/sched/fair.c — Bootlin Elixir — EEVDF 핵심 구현이 포함된 CFS/EEVDF 통합 소스 코드입니다.
• include/linux/sched.h — Bootlin Elixir — struct sched_entity와 EEVDF 관련 필드 정의입니다.
• Phoronix: Linux 6.6 EEVDF — Linux 6.6에서 EEVDF 도입 시 벤치마크 결과를 다룬 기사입니다.

관련 문서

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

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