Earliest Eligible Virtual Deadline First

Introduction

CFS는 vruntime이 가장 작은 태스크를 선택하는 단순한 원칙으로 15년간 리눅스의 공정 스케줄링을 지탱했습니다. 그러나 "가장 적게 받은 태스크를 실행한다"는 원칙만으로는, 짧은 작업을 빠르게 처리해야 하는 대화형 워크로드의 지연 요구를 충족하기 어려웠습니다. Linux v6.6에서 CFS를 대체한 EEVDF(Earliest Eligible Virtual Deadline First)는 적격성과 가상 데드라인이라는 두 가지 개념을 도입하여 공정성과 지연 제어를 동시에 달성합니다. 이 글에서는 EEVDF의 이론적 배경부터 리눅스 커널에서의 실제 구현까지를 살펴봅니다.

CFS의 한계

[CFS](Completely Fair Scheduler.md)의 태스크 선택 원칙은 "레드-블랙 트리의 가장 왼쪽에 위치한 노드(최소 vruntime)를 고른다"로 요약된다. 이 원칙은 CPU 시간의 비례 배분이라는 목표를 달성하지만, 두 가지 구조적 약점을 가지고 있다.

지연 제어가 없다. CFS는 태스크가 "얼마나 빨리" 실행되어야 하는지에 대한 개념이 없다. vruntime은 태스크가 받은 누적 서비스만 추적할 뿐, 태스크의 요청이 짧든 길든 동일한 기준으로 선택한다. 짧은 요청을 가진 대화형 태스크¹가 긴 배치 태스크들과 경쟁하면, 부하가 높을 때 응답 지연이 예측 불가능하게 커질 수 있다.
선점 결정이 경험적 파라미터에 의존한다. CFS의 선점은 sched_latency_ns, sched_min_granularity_ns, sched_wakeup_granularity_ns 같은 튜닝 파라미터가 조합된 결과물이다. 이 파라미터들은 워크로드에 따라 적절한 값이 달라지고, 상호작용이 복잡하며, 형식적인 보장을 제공하지 않는다.

EEVDF는 이 두 약점을 이론적으로 해결하기 위해 설계된 알고리즘이다.

EEVDF의 기원

EEVDF는 1995년 Ion Stoica와 Hussein Abdel-Wahab이 발표한 비례 공유 자원 할당 알고리즘이다. 원래 네트워크 패킷 스케줄링을 위해 설계되었으나, 그 원리는 CPU 스케줄링에도 직접 적용 가능했다. 2023년 Peter Zijlstra가 리눅스 커널에 구현하여 Linux v6.6에서 CFS의 태스크 선택 로직을 전면 교체했다.

핵심적으로 변경된 것은 태스크 선택, 배치placement, 선점 결정이다. 반면 vruntime 계산, 가중치 모델, 레드-블랙 트리 자료구조, 스케줄링 클래스 우선순위, 로드 밸런싱, cgroup² 지원, 사용자 인터페이스(nice, sched_setattr() 등)는 그대로 유지되었다.

세 가지 핵심 개념

EEVDF의 동작은 지연lag, 적격성eligibility, 가상 데드라인virtual deadline이라는 세가지 개념으로 설명된다.

지연

지연lag은 태스크가 이상적인 CPU에서 받았을 서비스와 실제로 받은 서비스의 차이를 측정한다. 리눅스 커널에서는 다음과 같이 계산된다.

$\text{lag}_i = w_i \times (V - v_i)$

여기서 $V$ 는 런큐³에 있는 모든 태스크의 평균 가상 시간⁴이고, $v_i$ 는 해당 태스크의 vruntime, $w_i$ 는 가중치다. $V > v_i$ 이면 양의 지연 — 태스크가 자신의 공정한 몫보다 적은 서비스를 받았다는 뜻이고, $V < v_i$ 이면 음의 지연 — 초과 서비스를 받았다는 뜻이다.

[CFS](Completely Fair Scheduler.md)에서는 이 개념이 vruntime의 상대적 크기에 암묵적으로 녹아 있었던 반면, EEVDF는 이를 sched_entity->vlag 필드에 명시적으로 추적한다.

static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    s64 vlag, limit;
    vlag = avg_vruntime(cfs_rq) - se->vruntime;
    limit = calc_delta_fair(max_t(u64, 2*se->slice, TICK_NSEC), se);
    se->vlag = clamp(vlag, -limit, limit);
}

지연 값은 clamp()로 상한과 하한이 제한된다. 이는 오래 수면한 태스크가 극단적으로 큰 양의 지연을 축적하여 CPU를 독점하는 것을 방지한다.

적격성

적격성eligibility은 지연에 기반한 필터다. 태스크의 vruntime이 평균 가상 시간 $V$ 이하인 경우, 즉 지연이 음이 아닌 경우에만 해당 태스크는 스케줄링 후보(적격 태스크)가 된다.

$\text{eligible} \iff V \geq v_i \iff \text{lag}_i \geq 0$

음의 지연을 가진 태스크 — 이미 자신의 몫 이상으로 CPU를 소비한 태스크 — 는 비적격ineligible 상태로, 다른 태스크들이 따라잡아 자신의 지연이 0 이상이 될 때까지 대기한다.

커널 구현에서는 나눗셈을 회피하기 위해 적격 조건 $V \geq v_i$ 를 다음과 같이 변환한다.

$\sum_j (v_j - v_0) \times w_j \geq (v_i - v_0) \times \sum_j w_j$

좌변은 cfs_rq->sum_w_vruntime, 우변의 $\sum w_j$ 는 cfs_rq->sum_weight에 유지되며, $v_0$ 은 오버플로 방지를 위한 기준점(cfs_rq->zero_vruntime)이다. 이 방식으로 정수 나눗셈 없이도 적격 여부를 정확하게 판별할 수 있다.

static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
    struct sched_entity *curr = cfs_rq->curr;
    s64 avg = cfs_rq->sum_w_vruntime;
    long load = cfs_rq->sum_weight;

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

    return avg >= (vruntime - cfs_rq->zero_vruntime) * load;
}

이 적격 필터는 CFS에서 min_vruntime 보정이 담당하던 역할을 구조적으로 대체한다. CFS의 min_vruntime이 기상 태스크의 vruntime을 사후 보정하는 방식이었다면, EEVDF의 적격성은 선택 단계에서 원천적으로 불공정한 태스크를 배제하는 방식이다.

가상 데드라인

적격 태스크들 사이의 우선순위는 가상 데드라인virtual deadline으로 결정된다. 태스크의 vruntime이 이전 데드라인에 도달하면, 새로운 데드라인이 다음과 같이 할당된다.

$VD_i = ve_i + \frac{r_i}{w_i}$

여기서 $ve_i$ 는 현재 vruntime, $r_i$ 는 요청 길이request size(타임 슬라이스⁵), $w_i$ 는 가중치다. 커널에서는 update_deadline() 함수가 이 계산을 수행한다.

static bool update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if (vruntime_cmp(se->vruntime, "<", se->deadline))
        return false;                          /* 데드라인 미도달 */

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

    return true;   /* 데드라인 갱신됨 — 슬라이스 소진 */
}

이 공식의 핵심 성질은 두 가지다.

짧은 요청은 이른 데드라인을 받는다. $r_i$ 가 작을수록 $VD_i$ 가 현재 vruntime에 가까워진다. 대화형 태스크가 짧은 슬라이스를 요청하면, 긴 슬라이스를 가진 배치 태스크보다 이른 데드라인을 받아 먼저 스케줄링된다. 이것이 CFS에서 부재했던 지연 제어를 제공하는 메커니즘이다.
가중치가 높은 태스크도 이른 데드라인을 받는다. 같은 물리적 슬라이스에 대해 $w_i$ 가 클수록 가상 시간 단위의 데드라인( $r_i / w_i$ )이 짧아진다. 우선순위가 높은 태스크가 자연스럽게 우대받는다.

태스크 선택: `pick_eevdf()`

EEVDF의 태스크 선택은 "적격 태스크 중 가상 데드라인이 가장 이른 태스크를 고른다"로 요약된다. 이를 효율적으로 수행하기 위해 CFS의 레드-블랙 트리가 증강augmented된다.

증강 레드-블랙 트리

CFS의 레드-블랙 트리는 vruntime을 키로 태스크를 정렬한다. EEVDF는 여기에 각 노드가 자신의 서브트리 내 최소 vruntime(min_vruntime)과 최소 슬라이스(min_slice)를 추가로 유지하도록 증강한다.

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    sum_w_vruntime_add(cfs_rq, se);
    update_zero_vruntime(cfs_rq);
    se->min_vruntime = se->vruntime;
    se->min_slice = se->slice;
    rb_add_augmented_cached(&se->run_node, &cfs_rq->tasks_timeline,
                            __entity_less, &min_vruntime_cb);
}

이 증강 정보 덕분에, 트리를 탐색할 때 어떤 서브트리에 적격 태스크가 존재하는지를 서브트리의 min_vruntime과 평균 가상 시간 $V$ 를 비교하여 빠르게 판별할 수 있다. 적격 태스크가 없는 서브트리는 통째로 건너뛸 수 있으므로(가지치기pruning), 탐색의 실질적 비용이 크게 줄어든다.

선택 알고리즘

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

    if (cfs_rq->nr_queued == 1)                      /* 태스크 1개: 즉시 반환 */
        return curr && curr->on_rq ? curr : se;

    if (sched_feat(PICK_BUDDY) &&
        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;
    if (curr && protect && protect_slice(curr))
        return curr;                                 /* 슬라이스 보호 */

    if (se && entity_eligible(cfs_rq, se)) {
        best = se;                                   /* 최좌측 = 적격이면 최선 */
        goto found;
    }

    while (node) {                                   /* 증강 트리 탐색 */
        struct rb_node *left = node->rb_left;

        if (left && vruntime_eligible(cfs_rq, __node_2_se(left)->min_vruntime)) {
            node = left;                             /* 좌측 서브트리에 적격 태스크 존재 */
            continue;
        }

        se = __node_2_se(node);
        if (entity_eligible(cfs_rq, se)) {
            best = se;                               /* 적격 태스크 발견 */
            break;
        }

        node = node->rb_right;                       /* 우측 서브트리 시도 */
    }

found:
    if (!best || (curr && entity_before(curr, best)))
        best = curr;

    return best;
}

알고리즘의 흐름을 정리하면 다음과 같다. 태스크가 하나뿐이면 즉시 반환한다. PICK_BUDDY 기능이 활성화되어 있고 버디 태스크가 적격이면 반환한다. 현재 태스크가 적격이면서 슬라이스 보호⁶ 중이면 현재 태스크를 유지한다. 최좌측 노드(최소 vruntime)가 적격이면 이것이 최선이다 — vruntime 기준 정렬과 적격성이 합치되는 경우이므로 가장 이른 데드라인을 가질 가능성이 높다. 이 모든 빠른 경로가 실패하면 증강 트리 탐색으로 적격 태스크 중 최소 데드라인을 찾는다.

선점과 슬라이스 보호

CFS에서 선점은 기상 태스크의 vruntime이 현재 태스크의 vruntime보다 sched_wakeup_granularity_ns 이상 작을 때 발생했다. EEVDF에서는 이 파라미터가 제거되고, 데드라인 비교로 대체되었다.

기상한 태스크의 가상 데드라인이 현재 태스크의 가상 데드라인보다 이르면 선점이 발생한다.

$VD_{\text{waker}} < VD_{\text{current}} \implies \text{선점}$

이 데드라인 기반 선점은 CFS의 파라미터 기반 선점보다 직관적이다. 짧은 요청을 가진 태스크는 이른 데드라인을 받으므로, 긴 배치 태스크를 실행 중일 때 대화형 태스크가 기상하면 자연스럽게 선점이 발생한다.

한편 EEVDF는 슬라이스 보호slice protection 메커니즘(protect_slice())을 도입하여, 태스크가 할당된 슬라이스의 최소량을 실행하기 전에 과도하게 선점되는 것을 방지한다. 이는 CFS의 sched_min_granularity_ns가 담당하던 역할을 데드라인 체계 안에서 수행한다.

튜닝 파라미터

CFS는 sched_latency_ns, sched_min_granularity_ns, sched_wakeup_granularity_ns 등 여러 파라미터를 조합해야 했다. EEVDF에서는 이들이 단일 파라미터로 단순화되었다.

파라미터	기본값	경로	의미
`base_slice_ns`	700,000 (0.7ms)	`/sys/kernel/debug/sched/base_slice_ns`	태스크의 기본 타임 슬라이스

base_slice_ns는 데드라인 계산에서 $r_i$ 값의 기본값으로 사용된다. 값이 작을수록 데드라인이 짧아져 지연이 줄지만, [컨텍스트 스위치](Context Switch.md) 빈도가 증가한다. 반대로 값이 클수록 처리량throughput이 올라가지만 지연이 커진다.

이 파라미터는 CPU 수에 따라 자동 스케일링된다. 기본 설정인 대수logarithmic 스케일링에서, 64코어 머신의 실제 슬라이스는 $700{,}000 \times (1 + \lfloor\log_2 64\rfloor) = 700{,}000 \times 7 = 4.9\text{ms}$ 가 된다.

사용자는 sched_setattr() 시스템 콜을 통해 태스크별로 커스텀 슬라이스를 설정할 수도 있다. 커스텀 슬라이스가 설정된 태스크는 se->custom_slice 플래그가 켜져 base_slice_ns 대신 사용자 지정 값이 데드라인 계산에 사용된다. 이를 통해 지연에 민감한 특정 태스크에 짧은 슬라이스를 부여하여 우선적으로 처리되도록 할 수 있다.

EEVDF의 공정성 보장

EEVDF는 CFS보다 형식적으로 강한 공정성 보장을 제공한다. Stoica와 Abdel-Wahab의 원 논문에 따르면, EEVDF의 서비스 오차service error는 최대 요청 크기에 의해 상한이 결정된다.

$|\text{received\_service} - \text{entitled\_service}| \leq r_{\max}$

이는 어떤 태스크도 자신의 공정한 몫에서 최대 하나의 타임 슬라이스 이상 벗어나지 않는다는 뜻이다. CFS도 실무적으로 유사한 수준의 공정성을 달성했지만, 이러한 형식적 보장은 제공하지 못했다.

기아starvation⁷ 방지도 구조적으로 보장된다. 계속 요청을 보내는(실행 가능 상태를 유지하는) 태스크는 적격 상태가 반복적으로 돌아오므로 반드시 서비스를 받는다. 지연 값은 clamp()로 제한되어 오래 수면한 태스크가 극단적인 양의 지연을 축적하는 것을 방지하고, 기상 시 적격 태스크들 사이에서 공정하게 경쟁하도록 한다.

출처

Stoica, I. and Abdel-Wahab, H. (1995) 'Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation', Technical Report TR-95-22, Old Dominion University.
Silberschatz, A., Galvin, P. B., and Gagne, G. (2018) Operating System Concepts. 10th ed. Hoboken, NJ: Wiley.
Love, R. (2010) Linux Kernel Development. 3rd ed. Upper Saddle River, NJ: Addison-Wesley.
Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th ed. Cambridge, MA: MIT Press.
Bovet, D. P. and Cesati, M. (2008) Understanding the Linux Kernel. 3rd ed. Sebastopol, CA: O'Reilly.
Linux kernel source v6.19 — kernel/sched/fair.c, kernel/sched/sched.h.
Linux kernel documentation — Documentation/scheduler/sched-eevdf.rst.

대화형 태스크interactive task는 사용자 입력에 즉각 반응해야 하는 태스크로, GUI 애플리케이션, 웹 서버, 데이터베이스의 쿼리 처리 스레드 등이 대표적이다. 이러한 태스크는 짧은 CPU 버스트를 자주 보이며, 응답 지연에 민감하다. ↩
cgroup(control group)은 리눅스 커널의 프로세스 그룹 자원 제어 메커니즘이다. CPU, 메모리, I/O 등의 자원을 그룹 단위로 할당하고 제한할 수 있다. CFS/EEVDF는 CONFIG_FAIR_GROUP_SCHED를 통해 그룹 단위의 공정 스케줄링을 지원한다. ↩
런큐runqueue는 특정 CPU에서 실행 대기 중인 태스크들을 관리하는 per-CPU 자료구조다. 리눅스에서는 struct rq로 구현되며, 스케줄링 클래스별 서브큐(cfs_rq, rt_rq 등)를 포함한다. ↩
평균 가상 시간 $V$ 는 런큐에 있는 모든 태스크의 가중 평균 vruntime이다. $V = \frac{\sum_j (v_j \times w_j)}{\sum_j w_j}$ 로 정의되지만, 커널에서는 정수 나눗셈을 피하기 위해 분자(sum_w_vruntime)와 분모(sum_weight)를 별도로 유지하고 비교 시에만 교차 곱셈을 사용한다. ↩
sysctl_sched_base_slice는 EEVDF 시대의 핵심 튜닝 파라미터로, 태스크의 기본 타임 슬라이스를 나노초 단위로 지정한다. 기본값은 700,000ns(0.7ms)이며, CPU 수에 따라 대수적으로 스케일링된다. ↩
슬라이스 보호slice protection(protect_slice())는 태스크가 할당된 슬라이스의 최소한을 소비하기 전에 선점되는 것을 방지하는 메커니즘이다. 이를 통해 과도한 선점으로 인한 [컨텍스트 스위치](Context Switch.md) 오버헤드를 제한한다. ↩
기아starvation란 특정 태스크가 자원(여기서는 CPU 시간)을 무기한으로 받지 못하는 상태를 말한다. ↩