sched_ext — BPF 확장 스케줄러(Scheduler)

Linux 커널 6.12에 정식 머지된 sched_ext 프레임워크를 심층 분석합니다. BPF struct_ops를 통해 스케줄링 정책을 커널 재컴파일 없이 교체할 수 있는 혁신적인 아키텍처를 살펴봅니다. DSQ(Dispatch Queue) 계층, sched_ext_ops 콜백(Callback) 체인, 태스크(Task) 생명주기, CPU 선택 메커니즘, 에러 복구를 추적하고, scx_rusty, scx_lavd, scx_rustland 등 실전 스케줄러 구현과 나만의 BPF 스케줄러 작성 가이드를 포괄합니다.

sched_ext 개발 역사

sched_ext는 Linux 커널 스케줄러의 확장성 한계를 극복하기 위해 탄생했습니다. 전통적으로 스케줄링 정책을 변경하려면 커널 소스를 수정하고 재컴파일해야 했으며, 이는 프로덕션 환경에서 큰 부담이었습니다.

sched_ext의 개발 과정에서 가장 큰 기술적 도전은 안전성이었습니다. 스케줄러는 시스템의 심장부이므로, BPF 프로그램의 버그가 시스템 전체를 멈출 수 있습니다. 이를 해결하기 위해 watchdog 타이머(Timer), 자동 CFS 폴백, ops.exit() 정리 메커니즘이 설계되었습니다.

/* kernel/sched/ext.c — sched_ext 핵심 초기화 */
static struct sched_class ext_sched_class;

/* ext 클래스는 fair 아래, idle 위에 위치 */
/* 우선순위: stop > dl > rt > fair > ext > idle */
DEFINE_SCHED_CLASS(ext) = {
    .enqueue_task     = enqueue_task_scx,
    .dequeue_task     = dequeue_task_scx,
    .pick_next_task   = pick_next_task_scx,
    .put_prev_task    = put_prev_task_scx,
    .set_next_task    = set_next_task_scx,
    .task_tick        = task_tick_scx,
    .select_task_rq  = select_task_rq_scx,
    .check_preempt_curr = check_preempt_curr_scx,
};

기존 sched_class와의 관계

Linux 커널 스케줄러는 sched_class의 연결 리스트(Linked List)로 우선순위(Priority)를 정의합니다. 각 클래스는 pick_next_task를 구현하며, 가장 높은 우선순위 클래스부터 실행 가능한 태스크를 탐색합니다.

/* include/linux/sched/ext.h — sched_class 연결 */
/*
 * 클래스 탐색 순서 (pick_next_task):
 * stop → dl → rt → fair → ext → idle
 *
 * ext가 활성화되면 SCHED_NORMAL 태스크도 ext로 이동 가능
 * SCX_OPS_ENQ_LAST 플래그로 fair에서 남은 태스크를 ext가 흡수
 */
#define SCX_OPS_ENQ_LAST    (1U << 0)  /* fair 미처리 태스크를 ext가 수용 */
#define SCX_OPS_ENQ_EXITING (1U << 1)  /* exit 중인 태스크도 enqueue */
#define SCX_OPS_SWITCH_PARTIAL (1U << 2) /* 일부 태스크만 ext로 전환 */

sched_ext 전체 아키텍처

sched_ext는 크게 3개의 계층으로 구성됩니다. 커널 코어가 스케줄링 프레임워크를 제공하고, BPF 프로그램이 스케줄링 정책을 정의하며, 유저스페이스 로더가 BPF 프로그램을 관리합니다.

/* kernel/sched/ext.c — 핵심 자료구조 */
struct sched_ext_entity {
    struct scx_dispatch_q  *dsq;       /* 현재 소속 DSQ */
    struct list_head       dsq_list;  /* DSQ 내 연결 리스트 */
    u64                    dsq_vtime; /* 가상 시간 (WFQ용) */
    u64                    slice;     /* 남은 타임 슬라이스 */
    u32                    flags;     /* SCX_TASK_* 플래그 */
    u32                    weight;    /* 태스크 가중치 */
    s32                    sticky_cpu; /* CPU 고정 힌트 */
    u32                    kf_mask;   /* 허용된 kfunc 마스크 */
    atomic_long_t          ops_state; /* 태스크 상태 머신 */
};

struct scx_dispatch_q {
    raw_spinlock_t  lock;
    struct list_head list;          /* FIFO 태스크 리스트 */
    struct rb_root  priq;          /* vtime 기반 우선순위 큐 */
    u32             nr;            /* 큐 내 태스크 수 */
    u64             id;            /* DSQ ID */
    u64             vtime_now;     /* 현재 가상 시간 */
};

DSQ(Dispatch Queue) 계층

DSQ는 sched_ext의 핵심 추상화입니다. 태스크는 BPF 스케줄러에 의해 DSQ에 삽입되고, 커널 코어가 DSQ에서 태스크를 꺼내 CPU에 디스패치합니다. 3종류의 DSQ가 있습니다:

/* DSQ 기본 상수 */
#define SCX_DSQ_LOCAL     0         /* 현재 CPU의 Local DSQ */
#define SCX_DSQ_GLOBAL    1         /* 시스템 전체 Global DSQ */
#define SCX_DSQ_LOCAL_ON  2         /* 특정 CPU의 Local DSQ */
#define SCX_DSQ_INVALID   UINT64_MAX /* 무효 DSQ */

/* Custom DSQ 생성 및 사용 */
static int create_dsq(void)
{
    s32 ret;

    /* NUMA 노드 0 전용 DSQ 생성 */
    ret = scx_bpf_create_dsq(100, 0);  /* id=100, NUMA node=0 */
    if (ret)
        return ret;

    /* NUMA 노드 1 전용 DSQ 생성 */
    ret = scx_bpf_create_dsq(101, 1);  /* id=101, NUMA node=1 */
    return ret;
}

DSQ 내부 데이터 구조 상세

DSQ(Dispatch Queue)는 내부적으로 FIFO 리스트(list_head)와 RB-tree(rb_root_cached)의 이중 구조를 사용합니다. scx_bpf_dsq_insert()은 FIFO 리스트 꼬리에 태스크를 추가하고, scx_bpf_dsq_insert_vtime()은 vtime을 키로 RB-tree에 삽입합니다. 디스패치 시에는 FIFO 리스트가 항상 우선 소비되며, FIFO가 비어야 RB-tree에서 가장 작은 vtime의 태스크를 꺼냅니다.

/* kernel/sched/ext.c — DSQ 내부 구조체 (핵심 필드) */
struct scx_dispatch_q {
    raw_spinlock_t  lock;           /* DSQ 접근 보호 */
    struct list_head list;          /* FIFO 리스트 (scx_bpf_dsq_insert) */
    struct rb_root_cached priq;     /* RB-tree (scx_bpf_dsq_insert_vtime) */
    u32             nr;             /* 총 태스크 수 (FIFO + RB) */
    u64             id;             /* DSQ ID */
    struct rhashtable_head hash_node; /* ID 기반 해시 룩업용 */
    u64             vtime_now;      /* 현재 가상 시간 워터마크 */
    struct list_head all_node;      /* 전체 DSQ 리스트 연결 */
};

/* per-task DSQ 연결 정보 (task_struct→scx 내부) */
struct sched_ext_entity {
    struct scx_dispatch_q *dsq;     /* 현재 속한 DSQ */
    struct list_head dsq_list;     /* FIFO 리스트 노드 */
    struct rb_node   dsq_priq;     /* RB-tree 노드 */
    u64             dsq_vtime;     /* 삽입된 vtime 값 */
    u64             dsq_flags;     /* DSQ_FIFO / DSQ_PRIQ 플래그 */
    u32             flags;         /* SCX_TASK_* 상태 플래그 */
    u64             slice;         /* 잔여 타임 슬라이스 */
};

/* FIFO 삽입 경로: scx_bpf_dsq_insert() */
static void dsq_insert_fifo(struct scx_dispatch_q *dsq,
                            struct task_struct *p,
                            u64 enq_flags)
{
    unsigned long flags;

    raw_spin_lock_irqsave(&dsq->lock, flags);

    /* FIFO 리스트 꼬리에 삽입 */
    p->scx.dsq_flags = SCX_DSQ_FIFO;
    list_add_tail(&p->scx.dsq_list, &dsq->list);
    p->scx.dsq = dsq;
    dsq->nr++;

    raw_spin_unlock_irqrestore(&dsq->lock, flags);
}

/* vtime 삽입 경로: scx_bpf_dsq_insert_vtime() */
static void dsq_insert_vtime(struct scx_dispatch_q *dsq,
                             struct task_struct *p,
                             u64 vtime, u64 enq_flags)
{
    unsigned long flags;
    struct rb_node **link, *parent = NULL;
    bool leftmost = true;

    raw_spin_lock_irqsave(&dsq->lock, flags);

    /* vtime_now 워터마크 갱신 — 시간 역행 방지 */
    if (vtime_before(vtime, dsq->vtime_now))
        vtime = dsq->vtime_now;

    p->scx.dsq_vtime = vtime;
    p->scx.dsq_flags = SCX_DSQ_PRIQ;

    /* RB-tree에 vtime 순서로 삽입 */
    link = &dsq->priq.rb_root.rb_node;
    while (*link) {
        struct task_struct *curr;
        parent = *link;
        curr = rb_entry(parent, struct task_struct,
                        scx.dsq_priq);

        if (vtime_before(vtime, curr->scx.dsq_vtime)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;
        }
    }

    rb_link_node(&p->scx.dsq_priq, parent, link);
    rb_insert_color_cached(&p->scx.dsq_priq,
                           &dsq->priq, leftmost);
    p->scx.dsq = dsq;
    dsq->nr++;

    raw_spin_unlock_irqrestore(&dsq->lock, flags);
}

/* DSQ에서 태스크 꺼내기 — FIFO 우선, 이후 RB-tree */
static struct task_struct *dsq_pop(struct scx_dispatch_q *dsq)
{
    struct task_struct *p;

    lockdep_assert_held(&dsq->lock);

    /* 1) FIFO 리스트 우선 확인 */
    if (!list_empty(&dsq->list)) {
        p = list_first_entry(&dsq->list,
                             struct task_struct,
                             scx.dsq_list);
        list_del_init(&p->scx.dsq_list);
        goto found;
    }

    /* 2) RB-tree의 rb_leftmost (최소 vtime) — O(1) */
    if (!RB_EMPTY_ROOT(&dsq->priq.rb_root)) {
        struct rb_node *left;
        left = dsq->priq.rb_leftmost;
        p = rb_entry(left, struct task_struct,
                     scx.dsq_priq);
        rb_erase_cached(&p->scx.dsq_priq, &dsq->priq);

        /* vtime_now를 소비한 태스크의 vtime으로 갱신 */
        dsq->vtime_now = p->scx.dsq_vtime;
        goto found;
    }

    return NULL;

found:
    p->scx.dsq = NULL;
    dsq->nr--;
    return p;
}

/* vtime_now 추적 메커니즘 상세 */

/*
 * vtime_before() — wrapping-safe 가상 시간 비교
 *
 * vtime은 u64이지만, 커널 전체 수명에서 오버플로우가 발생할 수 있으므로
 * signed 비교를 통해 wrap-around를 안전하게 처리합니다.
 * 이는 jiffies 비교의 time_before()와 동일한 기법입니다.
 */
static inline bool vtime_before(u64 a, u64 b)
{
    return (s64)(a - b) < 0;
}

/*
 * vtime_now 갱신 규칙:
 *
 * 1. 삽입 시: vtime이 vtime_now보다 과거면 vtime_now로 보정
 *    → 장기 sleep 후 깨어난 태스크가 과거 vtime으로
 *      무한히 우선 실행되는 것을 방지
 *
 * 2. 소비 시: 꺼낸 태스크의 vtime을 vtime_now에 반영
 *    → 시간이 단조 증가하도록 보장
 *
 * 3. BPF 스케줄러의 vtime 계산:
 *    stopping 콜백에서 실행 시간을 weight로 나눈 값을 누적
 *    → WFQ(Weighted Fair Queueing) 구현
 */

/* WFQ를 위한 vtime 갱신 — stopping 콜백에서 호출 */
SEC("struct_ops/stopping")
void BPF_PROG(wfq_stopping, struct task_struct *p, bool runnable)
{
    struct task_ctx *tctx;
    u64 delta, weighted_delta;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx)
        return;

    /* 실제 실행 시간 (ns) */
    delta = bpf_ktime_get_ns() - tctx->last_running;

    /* weight가 높은 태스크는 vtime이 느리게 증가 → 더 많이 실행됨
     * weight가 낮은 태스크는 vtime이 빠르게 증가 → 적게 실행됨
     *
     * 예: weight 200 태스크가 1ms 실행 → vtime += 0.5ms
     *     weight  50 태스크가 1ms 실행 → vtime += 2ms
     */
    weighted_delta = delta * 100 / tctx->weight;
    tctx->vtime += weighted_delta;
}

sched_ext_ops 콜백 상세

sched_ext_ops는 BPF 스케줄러가 구현해야 하는 콜백 함수 집합입니다. 모든 콜백은 선택적이며, 구현하지 않으면 커널이 기본 동작을 수행합니다.

/* include/linux/sched/ext.h — sched_ext_ops 구조체 (핵심 필드) */
struct sched_ext_ops {
    /* 태스크 enqueue 콜백 — 태스크가 runnable 될 때 호출 */
    void (*enqueue)(struct task_struct *p, u64 enq_flags);

    /* 태스크 dequeue 콜백 — 태스크가 sleep/exit 할 때 호출 */
    void (*dequeue)(struct task_struct *p, u64 deq_flags);

    /* dispatch 콜백 — Local DSQ가 비었을 때 호출 */
    void (*dispatch)(s32 cpu, struct task_struct *prev);

    /* CPU 선택 콜백 — wakeup 시 실행 CPU 결정 */
    s32 (*select_cpu)(struct task_struct *p, s32 prev_cpu, u64 wake_flags);

    /* 태스크가 CPU에서 실행 시작 */
    void (*running)(struct task_struct *p);

    /* 태스크가 CPU에서 실행 중단 */
    void (*stopping)(struct task_struct *p, bool runnable);

    /* 스케줄러 틱 */
    void (*tick)(struct task_struct *p);

    /* 이름, 플래그, 타임아웃 */
    char   name[SCX_OPS_NAME_LEN];
    u64    flags;
    u32    timeout_ms;   /* watchdog 타임아웃 (기본 30초) */
};

태스크 생명주기

sched_ext에서 관리되는 태스크는 명확한 상태 전이를 거칩니다. 각 전이 시점에 대응하는 ops 콜백이 호출됩니다.

/* 태스크 상태 플래그 */
#define SCX_TASK_QUEUED     (1U << 0)  /* DSQ에 삽입됨 */
#define SCX_TASK_DEQD_FOR_SLEEP (1U << 1) /* sleep을 위해 dequeue */
#define SCX_TASK_STATE_SHIFT    8
#define SCX_TASK_STATE_BITS     2
#define SCX_TASK_STATE_MASK     ((((1U << SCX_TASK_STATE_BITS) - 1) << SCX_TASK_STATE_SHIFT))

enum scx_task_state {
    SCX_TASK_NONE,      /* 초기 상태 */
    SCX_TASK_INIT,      /* init_task() 완료 */
    SCX_TASK_READY,     /* enable() 완료, 스케줄링 가능 */
    SCX_TASK_ENABLED,   /* 활성 상태 */
};

CPU 선택 메커니즘

태스크가 깨어날 때 가장 먼저 호출되는 콜백이 select_cpu입니다. 이 콜백은 태스크를 실행할 CPU를 결정하고, 선택적으로 해당 CPU의 Local DSQ에 직접 삽입할 수 있습니다.

/* BPF 스케줄러에서 select_cpu 구현 예시 */
SEC("struct_ops/select_cpu")
s32 BPF_PROG(my_select_cpu, struct task_struct *p,
                           s32 prev_cpu, u64 wake_flags)
{
    bool is_idle = false;
    s32 cpu;

    /* 기본 idle CPU 선택 알고리즘 사용 */
    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &is_idle);

    if (is_idle) {
        /* idle CPU 발견 — Local DSQ에 직접 삽입 (enqueue 스킵) */
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL,
                           0);
        return cpu;
    }

    /* idle CPU 없음 — prev_cpu 반환 후 enqueue에서 처리 */
    return prev_cpu;
}

로드 밸런싱

sched_ext에서 로드 밸런싱은 dispatch 콜백과 scx_bpf_consume() 헬퍼를 통해 구현됩니다. Local DSQ가 비었을 때 커널이 dispatch를 호출하면, BPF 스케줄러가 Custom/Global DSQ에서 태스크를 가져옵니다.

/* dispatch 콜백 구현 예시 */
SEC("struct_ops/dispatch")
void BPF_PROG(my_dispatch, s32 cpu, struct task_struct *prev)
{
    u64 dsq_id;

    /* 현재 CPU의 NUMA 노드에 해당하는 Custom DSQ에서 소비 */
    dsq_id = cpu_to_node(cpu);
    scx_bpf_consume(dsq_id);

    /* Custom DSQ가 비었으면 Global DSQ에서 소비 */
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

/* enqueue에서 적절한 DSQ에 삽입 */
SEC("struct_ops/enqueue")
void BPF_PROG(my_enqueue, struct task_struct *p, u64 enq_flags)
{
    u64 dsq_id;

    /* 태스크의 현재 CPU 기반으로 NUMA 노드 DSQ 선택 */
    dsq_id = cpu_to_node(scx_bpf_task_cpu(p));
    scx_bpf_dsq_insert(p, dsq_id, SCX_SLICE_DFL, 0);
}

Tick과 시간 슬라이스

sched_ext는 태스크에 타임 슬라이스(slice)를 부여하여 CPU 시간을 제어합니다. 매 스케줄러 틱마다 ops.tick이 호출되고, 슬라이스가 만료되면 태스크가 선점(Preemption)됩니다.

/* tick 콜백에서 커스텀 시간 슬라이스 관리 */
SEC("struct_ops/tick")
void BPF_PROG(my_tick, struct task_struct *p)
{
    /* 대화형 태스크에 짧은 슬라이스 */
    if (is_interactive(p))
        p->scx.slice = 5 * NSEC_PER_MSEC;
    else
        p->scx.slice = 20 * NSEC_PER_MSEC;
}

/* enqueue 시 슬라이스 설정 */
scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                   10 * NSEC_PER_MSEC,  /* 10ms 슬라이스 */
                   0);  /* enq_flags */

선점(Preemption)과 우선순위 제어

sched_ext에서의 선점(Preemption)은 전통적 CFS/EEVDF와 다르게 BPF 스케줄러가 직접 제어할 수 있습니다. 기본적으로 타임 슬라이스(slice) 만료에 의한 자연 선점이 발생하지만, scx_bpf_kick_cpu()와 SCX_KICK_PREEMPT 플래그를 통해 즉시 선점을 강제할 수도 있습니다.

대화형 태스크 감지와 우선순위 부스트(Priority Boost)는 sched_ext 스케줄러의 핵심 기능 중 하나입니다. 대화형 태스크는 짧은 CPU 버스트(burst) 후 자발적으로 블록되는 패턴을 보이며, 이를 감지하여 짧은 슬라이스와 즉시 선점을 부여합니다.

/* 대화형 태스크 감지 및 선점 제어 구현 */
struct task_ctx {
    u64 avg_runtime_ns;       /* EWMA 평균 실행 시간 */
    u64 avg_sleep_ns;         /* EWMA 평균 수면 시간 */
    u32 voluntary_switches;   /* 자발적 컨텍스트 전환 횟수 */
    u32 involuntary_switches; /* 비자발적 컨텍스트 전환 횟수 */
    bool is_interactive;     /* 대화형 태스크 여부 */
    u64 last_wake_at;        /* 마지막 깨어난 시각 */
    u64 last_run_at;         /* 마지막 실행 시작 시각 */
};

#define INTERACTIVE_RUNTIME_THRESH  (5 * NSEC_PER_MSEC)
#define INTERACTIVE_SLEEP_RATIO    4  /* sleep/run > 4이면 대화형 */
#define EWMA_WEIGHT               4  /* EWMA 가중치 (1/4) */

/* EWMA 업데이트 헬퍼 */
static u64 ewma_update(u64 old, u64 new)
{
    return (old * (EWMA_WEIGHT - 1) + new) / EWMA_WEIGHT;
}

/* 대화형 태스크 판별 */
static bool detect_interactive(struct task_ctx *tctx)
{
    /* 조건 1: 평균 실행 시간이 임계값 이하 */
    if (tctx->avg_runtime_ns > INTERACTIVE_RUNTIME_THRESH)
        return false;

    /* 조건 2: 수면/실행 비율이 충분히 높음 */
    if (tctx->avg_runtime_ns == 0)
        return false;
    if (tctx->avg_sleep_ns / tctx->avg_runtime_ns < INTERACTIVE_SLEEP_RATIO)
        return false;

    /* 조건 3: 자발적 전환이 비자발적보다 많음 */
    return tctx->voluntary_switches > tctx->involuntary_switches * 2;
}

/* enqueue 콜백: 대화형 태스크 감지 및 선점 */
SEC("struct_ops/enqueue")
void BPF_PROG(my_enqueue, struct task_struct *p, u64 enq_flags)
{
    struct task_ctx *tctx;
    u64 slice;
    u64 flags = enq_flags;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx) {
        scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
        return;
    }

    /* 대화형 태스크 판별 */
    tctx->is_interactive = detect_interactive(tctx);

    if (tctx->is_interactive) {
        /* 짧은 슬라이스 + 선점 플래그 */
        slice = 3 * NSEC_PER_MSEC;
        flags |= SCX_ENQ_PREEMPT;

        /* 현재 CPU에서 실행 중인 태스크가 있으면 선점 */
        scx_bpf_kick_cpu(scx_bpf_task_cpu(p), SCX_KICK_PREEMPT);
    } else {
        /* 일반 태스크: 기본 슬라이스 */
        slice = 20 * NSEC_PER_MSEC;
    }

    scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, slice, flags);
}

/* stopping 콜백: 실행 통계 업데이트 */
SEC("struct_ops/stopping")
void BPF_PROG(my_stopping, struct task_struct *p, bool runnable)
{
    struct task_ctx *tctx;
    u64 now = bpf_ktime_get_ns();
    u64 runtime;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx)
        return;

    runtime = now - tctx->last_run_at;
    tctx->avg_runtime_ns = ewma_update(tctx->avg_runtime_ns, runtime);

    if (runnable)
        tctx->involuntary_switches++;
    else
        tctx->voluntary_switches++;
}

/* running 콜백: 수면 시간 측정 */
SEC("struct_ops/running")
void BPF_PROG(my_running, struct task_struct *p)
{
    struct task_ctx *tctx;
    u64 now = bpf_ktime_get_ns();
    u64 sleep_time;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx)
        return;

    sleep_time = now - tctx->last_wake_at;
    tctx->avg_sleep_ns = ewma_update(tctx->avg_sleep_ns, sleep_time);
    tctx->last_run_at = now;
}

BPF struct_ops 프레임워크

sched_ext는 BPF struct_ops를 사용하여 커널 함수 포인터를 BPF 프로그램으로 교체합니다. SEC("struct_ops")와 SEC("struct_ops.s")(sleepable) 두 가지 모드가 있습니다.

/* 최소 BPF 스케줄러 구조 (struct_ops 등록) */
#include <scx/common.bpf.h>

SEC("struct_ops/enqueue")
void BPF_PROG(enqueue, struct task_struct *p, u64 enq_flags)
{
    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

SEC("struct_ops/dispatch")
void BPF_PROG(dispatch, s32 cpu, struct task_struct *prev)
{
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

SEC(".struct_ops.link")
struct sched_ext_ops my_ops = {
    .enqueue    = (void *)enqueue,
    .dispatch   = (void *)dispatch,
    .name       = "my_scheduler",
};

sched_ext BPF 헬퍼 함수

sched_ext는 BPF 프로그램에서 사용할 수 있는 전용 kfunc(커널 함수)을 제공합니다. 이 함수들은 DSQ 관리, CPU 제어, 태스크 정보 조회에 사용됩니다.

/* kfunc 선언 (include/linux/sched/ext.h) */
void scx_bpf_dsq_insert(struct task_struct *p, u64 dsq_id,
                        u64 slice, u64 enq_flags) __ksym;

void scx_bpf_dsq_insert_vtime(struct task_struct *p, u64 dsq_id,
                              u64 slice, u64 vtime,
                              u64 enq_flags) __ksym;

bool scx_bpf_consume(u64 dsq_id) __ksym;

s32 scx_bpf_select_cpu_dfl(struct task_struct *p,
                           s32 prev_cpu, u64 wake_flags,
                           bool *is_idle) __ksym;

void scx_bpf_kick_cpu(s32 cpu, u64 flags) __ksym;

s32 scx_bpf_create_dsq(u64 dsq_id, s32 node) __ksym;

BPF 맵과 데이터 공유

BPF 스케줄러는 BPF 맵을 통해 per-task 데이터, per-CPU 통계, 유저스페이스와의 통신을 관리합니다.

/* per-task 스토리지 (task_storage 맵) */
struct task_ctx {
    u64 last_run_at;     /* 마지막 실행 시작 시각 */
    u64 total_runtime;    /* 누적 실행 시간 */
    u64 vtime;            /* 가상 시간 (WFQ용) */
    u32 weight;           /* nice → 가중치 */
    bool interactive;     /* 대화형 태스크 여부 */
};

struct {
    __uint(type, BPF_MAP_TYPE_TASK_STORAGE);
    __uint(map_flags, BPF_F_NO_PREALLOC);
    __type(key, int);
    __type(value, struct task_ctx);
} task_data SEC(".maps");

/* per-CPU 스토리지 */
struct cpu_ctx {
    u64 nr_dispatched;   /* 디스패치된 태스크 수 */
    u64 nr_idle;         /* idle 진입 횟수 */
};

struct {
    __uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
    __uint(max_entries, 1);
    __type(key, u32);
    __type(value, struct cpu_ctx);
} cpu_data SEC(".maps");

/* 유저스페이스 ↔ BPF 통신 (ring buffer) */
struct {
    __uint(type, BPF_MAP_TYPE_RINGBUF);
    __uint(max_entries, 4096);
} events SEC(".maps");

/* per-task 스토리지 사용 예시 */
SEC("struct_ops/running")
void BPF_PROG(my_running, struct task_struct *p)
{
    struct task_ctx *tctx;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (tctx)
        tctx->last_run_at = bpf_ktime_get_ns();
}

SEC("struct_ops/stopping")
void BPF_PROG(my_stopping, struct task_struct *p, bool runnable)
{
    struct task_ctx *tctx;
    u64 delta;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (tctx) {
        delta = bpf_ktime_get_ns() - tctx->last_run_at;
        tctx->total_runtime += delta;
        /* vtime 갱신: 실행 시간 / 가중치 */
        tctx->vtime += delta / tctx->weight;
    }
}

BPF verifier와 sched_ext

BPF verifier는 sched_ext 프로그램에 대해 일반 BPF 프로그램보다 엄격한 검증을 수행합니다. 스케줄러는 커널의 핵심 경로에서 실행되므로, 잘못된 BPF 프로그램이 시스템 전체를 불안정하게 만들 수 있기 때문입니다. verifier는 각 ops 콜백의 컨텍스트(Context)에 따라 호출 가능한 kfunc를 제한하며, sleepable/non-sleepable 구분을 강제합니다.

SCX_KF_* kfunc 컨텍스트 마스크

sched_ext는 각 ops 콜백을 호출할 때 scx_kf_allowed 비트마스크를 설정합니다. kfunc 호출 시 이 마스크를 확인하여, 해당 콜백에서 허용된 kfunc만 호출할 수 있도록 강제합니다.

sleepable vs non-sleepable 콜백

sched_ext ops 콜백은 두 가지 모드로 나뉩니다. non-sleepable 콜백은 스케줄링 핫패스에서 실행되며 rq lock을 잡은 상태이므로 절대 sleep할 수 없습니다. sleepable 콜백은 SEC("struct_ops.s")로 선언하며, 초기화/정리 작업에 사용됩니다.

/* kernel/sched/ext.c — kfunc 컨텍스트 검증 */
#define SCX_KF_ENQUEUE     (1U << 0)
#define SCX_KF_DISPATCH    (1U << 1)
#define SCX_KF_CPU_RELEASE (1U << 2)
#define SCX_KF_SLEEPABLE   (1U << 3)
#define SCX_KF_TERMINAL    (1U << 4)

/*
 * kfunc 호출 시 컨텍스트 검증 함수
 * 각 kfunc는 allowed_mask를 선언하고,
 * 호출 시 현재 ops의 scx_kf_allowed와 AND 연산으로 검증
 */
static bool scx_kf_allowed_on_arg_tasks(
    u32 mask, struct task_struct *p)
{
    if (unlikely(!(mask & scx_kf_allowed())))
        return false;
    return true;
}

/*
 * scx_bpf_dsq_insert()는 SCX_KF_ENQUEUE | SCX_KF_DISPATCH에서만 허용
 * → select_cpu, enqueue, dispatch 콜백에서만 호출 가능
 */
__bpf_kfunc void scx_bpf_dsq_insert(
    struct task_struct *p, u64 dsq_id,
    u64 slice, u64 enq_flags)
{
    if (!scx_kf_allowed(SCX_KF_ENQUEUE | SCX_KF_DISPATCH))
        return;
    /* ... 실제 삽입 로직 ... */
}

/*
 * scx_bpf_create_dsq()는 SCX_KF_SLEEPABLE에서만 허용
 * → init() 콜백에서만 호출 가능 (메모리 할당 필요)
 */
__bpf_kfunc s32 scx_bpf_create_dsq(
    u64 dsq_id, s32 node)
{
    if (!scx_kf_allowed(SCX_KF_SLEEPABLE))
        return -EPERM;
    /* ... DSQ 생성 ... */
}

verifier 에러 예시와 해결

sched_ext BPF 프로그램을 로드할 때 자주 발생하는 verifier 에러와 해결 방법입니다.

/* 에러 예시 1: dispatch 외에서 consume 호출 — 거부됨 */
SEC("struct_ops/enqueue")  /* ✗ enqueue에서 consume 불가 */
void BPF_PROG(bad_enqueue, struct task_struct *p, u64 enq_flags)
{
    scx_bpf_consume(SCX_DSQ_GLOBAL);  /* verifier 에러! */
    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

/* 해결: consume은 dispatch에서만 사용 */
SEC("struct_ops/enqueue")  /* ✓ 올바른 enqueue */
void BPF_PROG(good_enqueue, struct task_struct *p, u64 enq_flags)
{
    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

SEC("struct_ops/dispatch")  /* ✓ consume은 여기서 */
void BPF_PROG(good_dispatch, s32 cpu, struct task_struct *prev)
{
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

/* 에러 예시 2: non-sleepable에서 DSQ 생성 — 거부됨 */
SEC("struct_ops/enqueue")  /* ✗ non-sleepable! */
void BPF_PROG(bad_enqueue2, struct task_struct *p, u64 enq_flags)
{
    scx_bpf_create_dsq(42, -1);  /* verifier 에러! */
}

/* 해결: DSQ 생성은 sleepable init에서 수행 */
SEC("struct_ops.s/init")  /* ✓ sleepable */
s32 BPF_PROG(good_init)
{
    return scx_bpf_create_dsq(42, -1);  /* 정상 */
}

/* 에러 예시 3: bounded loop 필요 */
SEC("struct_ops/dispatch")
void BPF_PROG(bad_dispatch, s32 cpu, struct task_struct *prev)
{
    /* ✗ 무한 루프 가능 → verifier 거부 */
    while (!scx_bpf_consume(SCX_DSQ_GLOBAL))
        ;  /* busy wait — 거부됨 */
}

/* 해결: bpf_loop 또는 단일 consume */
SEC("struct_ops/dispatch")
void BPF_PROG(good_dispatch, s32 cpu, struct task_struct *prev)
{
    /* ✓ 단일 consume 시도 */
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

에러 처리와 안전 장치

sched_ext의 가장 중요한 설계 원칙 중 하나는 안전한 실패(fail-safe)입니다. BPF 스케줄러에 문제가 발생하면 시스템이 자동으로 CFS/EEVDF로 복구됩니다.

/* 에러 종류와 exit_kind */
enum scx_exit_kind {
    SCX_EXIT_NONE,        /* 정상 */
    SCX_EXIT_DONE,        /* 정상 종료 */
    SCX_EXIT_UNREG,       /* 유저스페이스 요청 해제 */
    SCX_EXIT_UNREG_BPF,  /* BPF에서 요청 해제 */
    SCX_EXIT_UNREG_KERN, /* 커널에서 요청 해제 */
    SCX_EXIT_ERROR,       /* 일반 에러 */
    SCX_EXIT_ERROR_BPF,  /* BPF 프로그램 에러 */
    SCX_EXIT_ERROR_STALL, /* watchdog 스톨 감지 */
};

/* exit 콜백에서 종료 사유 처리 */
SEC("struct_ops/exit")
void BPF_PROG(my_exit, struct scx_exit_info *ei)
{
    /* 종료 사유를 링 버퍼로 유저스페이스에 전달 */
    bpf_printk("sched_ext exit: kind=%d reason=%s",
               ei->kind, ei->reason);
}

/* BPF 내부에서 스케줄러 자진 종료 */
if (error_condition)
    scx_bpf_exit(SCX_EXIT_ERROR, "fatal error: %d", err);

scx_simple (최소 구현, 학습용)

scx_simple은 sched_ext의 가장 기본적인 스케줄러입니다. 모든 태스크를 Global DSQ에 넣고, 어떤 CPU든 소비하는 단순한 구조로, sched_ext 학습의 출발점입니다.

/* scx_simple — 최소 BPF 스케줄러 */
#include <scx/common.bpf.h>

char _license[] SEC("license") = "GPL";

/* FIFO 모드: Global DSQ에 삽입 */
SEC("struct_ops/enqueue")
void BPF_PROG(simple_enqueue, struct task_struct *p,
                              u64 enq_flags)
{
    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL,
                       enq_flags);
}

/* dispatch: Global DSQ에서 소비 */
SEC("struct_ops/dispatch")
void BPF_PROG(simple_dispatch, s32 cpu,
                               struct task_struct *prev)
{
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

/* init: 간단한 초기화 */
SEC("struct_ops/init")
s32 BPF_PROG(simple_init)
{
    return 0;
}

SEC(".struct_ops.link")
struct sched_ext_ops simple_ops = {
    .enqueue    = (void *)simple_enqueue,
    .dispatch   = (void *)simple_dispatch,
    .init       = (void *)simple_init,
    .name       = "simple",
};

scx_rusty (Rust, NUMA-aware, 로드 밸런서)

scx_rusty는 Rust로 작성된 NUMA-aware 스케줄러입니다. NUMA 도메인별로 DSQ를 분리하고, 유저스페이스 로드 밸런서가 주기적으로 도메인 간 부하를 재분배합니다.

// scx_rusty — Rust 유저스페이스 로드 밸런서 (개요)
fn balance_domains(&mut self) {
    for dom in &self.domains {
        let load = dom.get_load();
        let avg = self.avg_load();

        if load > avg * 1.2 {
            // 과부하 도메인 → 유휴 도메인으로 이동
            let target = self.find_underloaded_domain();
            self.migrate_tasks(dom, target);
        }
    }
}

밸런싱 알고리즘 상세

scx_rusty의 로드 밸런싱은 하이스테리시스(Hysteresis) 기반으로 동작합니다. 도메인 간 부하 차이가 일정 임계값을 초과해야만 태스크 이동이 발생하며, 이동 후에도 안정 구간(dead zone)을 두어 불필요한 왕복 이동(ping-pong)을 방지합니다.

// scx_rusty — 상세 밸런싱 알고리즘
const LOAD_IMBAL_HIGH_RATIO: f64 = 1.2;
const LOAD_IMBAL_LOW_RATIO: f64 = 0.8;
const GREEDY_THRESHOLD: f64 = 1.5;
const MAX_MIGRATIONS: usize = 8;

struct Domain {
    id: usize,
    cpus: Vec<usize>,
    load: f64,            // 현재 로드 (EWMA)
    nr_running: u64,      // 실행 가능 태스크 수
    nr_cpus: u32,         // 도메인 내 CPU 수
    tasks: Vec<TaskStat>, // 태스크 통계
}

impl LoadBalancer {
    fn balance_step(&mut self) {
        let global_avg = self.calc_global_avg_load();

        // 1단계: 도메인별 부하 상태 분류
        let mut overloaded: Vec<&mut Domain> = Vec::new();
        let mut underloaded: Vec<&mut Domain> = Vec::new();

        for dom in &mut self.domains {
            let ratio = dom.load / global_avg;
            if ratio > LOAD_IMBAL_HIGH_RATIO {
                overloaded.push(dom);
            } else if ratio < LOAD_IMBAL_LOW_RATIO {
                underloaded.push(dom);
            }
            // 중간 영역(dead zone): 이동 없음
        }

        // 2단계: greedy 마이그레이션 (극심한 불균형)
        for src in &mut overloaded {
            if src.load / global_avg > GREEDY_THRESHOLD {
                // NUMA 거리 기반 가장 가까운 저부하 도메인 선택
                if let Some(dst) = self.nearest_underloaded(src) {
                    self.migrate_greedy(src, dst, MAX_MIGRATIONS);
                }
            }
        }

        // 3단계: 일반 밸런싱 (완만한 이동)
        for src in &mut overloaded {
            for dst in &mut underloaded {
                let migrate_count = self.calc_migrate_count(src, dst);
                self.migrate_tasks_sorted(src, dst, migrate_count);
            }
        }
    }

    // 로드 계산: 가중 평균 (CPU-bound 태스크에 높은 가중치)
    fn calc_global_avg_load(&self) -> f64 {
        let total: f64 = self.domains.iter()
            .map(|d| d.load).sum();
        total / self.domains.len() as f64
    }

    // 이동 태스크 정렬: LLC miss가 높은 태스크를 우선 이동
    fn migrate_tasks_sorted(
        &mut self,
        src: &mut Domain,
        dst: &mut Domain,
        count: usize,
    ) {
        // LLC miss가 높은 태스크 = 이동 비용 낮음
        src.tasks.sort_by(|a, b|
            b.llc_miss_rate.partial_cmp(&a.llc_miss_rate)
                .unwrap()
        );
        for task in src.tasks.drain(..min(count, src.tasks.len())) {
            self.push_migration(task.pid, dst.id);
        }
    }
}

BPF 맵 구조

scx_rusty는 BPF 맵을 통해 커널과 유저스페이스 간에 도메인 정보와 통계를 교환합니다.

/* scx_rusty BPF 맵 구조 */
/* CPU → 도메인 매핑 */
struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __type(key, u32);      /* CPU ID */
    __type(value, u32);    /* 도메인 ID */
    __uint(max_entries, 1024);
} cpu_dom_map SEC(".maps");

/* 도메인별 통계 */
struct dom_stat {
    u64 nr_running;       /* 실행 가능 태스크 수 */
    u64 load_sum;          /* 누적 로드 */
    u64 nr_migrations_in;  /* 유입된 태스크 수 */
    u64 nr_migrations_out; /* 유출된 태스크 수 */
};

struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __type(key, u32);             /* 도메인 ID */
    __type(value, struct dom_stat);
    __uint(max_entries, 64);
} dom_stats SEC(".maps");

/* 태스크 이동 요청 큐 (유저스페이스 → BPF) */
struct migration_req {
    u32 pid;
    u32 target_dom_id;
};

struct {
    __uint(type, BPF_MAP_TYPE_QUEUE);
    __type(value, struct migration_req);
    __uint(max_entries, 4096);
} migration_queue SEC(".maps");

/* enqueue에서 도메인 기반 DSQ 선택 */
SEC("struct_ops/enqueue")
void BPF_PROG(rusty_enqueue, struct task_struct *p, u64 enq_flags)
{
    s32 cpu = scx_bpf_task_cpu(p);
    u32 *dom_id;
    u64 dsq_id;

    dom_id = bpf_map_lookup_elem(&cpu_dom_map, &cpu);
    if (!dom_id) {
        scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
        return;
    }

    /* 도메인 ID를 DSQ ID로 사용 */
    dsq_id = (u64)*dom_id;
    scx_bpf_dsq_insert_vtime(p, dsq_id, SCX_SLICE_DFL,
                              p->scx.dsq_vtime, enq_flags);
}

scx_lavd (Latency-Aware Virtual Deadline)

scx_lavd는 지연 시간에 민감한 워크로드를 위한 스케줄러입니다. 가상 데드라인(Virtual Deadline)을 기반으로 대화형 태스크에 높은 우선순위를 부여하면서도, CPU-bound 태스크의 공정성(Fairness)을 유지합니다.

/* scx_lavd — 가상 데드라인 계산 핵심 로직 */
static u64 calc_virtual_deadline(struct task_ctx *tctx)
{
    u64 now = bpf_ktime_get_ns();
    u64 avg_runtime = tctx->avg_runtime;
    u64 lat_weight = tctx->latency_weight;

    /*
     * 대화형 태스크: lat_weight 작음 → deadline 빠름
     * CPU-bound:    lat_weight 큼   → deadline 늦음
     * → EDF(Earliest Deadline First) 순서로 실행
     */
    return now + (lat_weight * avg_runtime);
}

/* enqueue 시 vtime에 deadline을 설정 */
scx_bpf_dsq_insert_vtime(p, dsq_id, slice,
                         calc_virtual_deadline(tctx), 0);

latency_weight 계산 공식

latency_weight는 태스크의 지연 민감도를 나타내는 핵심 지표입니다. 대화형 태스크는 낮은 값을, CPU-bound 태스크는 높은 값을 갖습니다. 이 값은 여러 요인을 종합하여 계산됩니다.

/* scx_lavd — latency_weight 상세 계산 */
#define LAT_WEIGHT_BASE     1000   /* 기본 가중치 */
#define LAT_WEIGHT_MIN      100    /* 최소 (가장 대화형) */
#define LAT_WEIGHT_MAX      10000  /* 최대 (가장 CPU-bound) */
#define EWMA_DECAY          8      /* EWMA 감쇠 상수 (1/8) */

struct task_ctx {
    u64 avg_runtime;         /* EWMA 평균 실행 시간 (ns) */
    u64 avg_sleep_time;      /* EWMA 평균 수면 시간 (ns) */
    u64 avg_wait_time;       /* EWMA 평균 대기 시간 (ns) */
    u64 run_time_total;      /* 총 실행 시간 */
    u64 wall_time_total;     /* 총 경과 시간 */
    u32 voluntary_csw;       /* 자발적 전환 누적 */
    u32 total_csw;            /* 전체 전환 누적 */
    u64 latency_weight;      /* 계산된 지연 가중치 */
    u64 last_run_at;
    u64 last_sleep_at;
    u64 last_enqueue_at;
};

/*
 * EWMA(Exponentially Weighted Moving Average) 업데이트
 *   new_avg = old_avg * (1 - 1/DECAY) + sample * (1/DECAY)
 *           = old_avg - old_avg/DECAY + sample/DECAY
 *           = (old_avg * (DECAY - 1) + sample) / DECAY
 */
static inline u64 ewma(u64 old_avg, u64 sample)
{
    return (old_avg * (EWMA_DECAY - 1) + sample) / EWMA_DECAY;
}

/* latency_weight 계산: 여러 요인의 가중 합산 */
static u64 calc_latency_weight(struct task_ctx *tctx)
{
    u64 weight = LAT_WEIGHT_BASE;
    u64 vol_ratio, sleep_ratio, cpu_intensity;

    /* 요인 1: 자발적 전환 비율 (0~100) */
    if (tctx->total_csw > 0) {
        vol_ratio = tctx->voluntary_csw * 100 / tctx->total_csw;
        /* 자발적 전환이 많을수록 weight 감소 */
        weight = weight * (200 - vol_ratio) / 100;
    }

    /* 요인 2: 수면/실행 비율 */
    if (tctx->avg_runtime > 0) {
        sleep_ratio = tctx->avg_sleep_time * 100 /
                      (tctx->avg_sleep_time + tctx->avg_runtime);
        /* 수면 비율이 높을수록 weight 감소 */
        weight = weight * (200 - sleep_ratio) / 100;
    }

    /* 요인 3: CPU 집약도 */
    if (tctx->wall_time_total > 0) {
        cpu_intensity = tctx->run_time_total * 100 /
                        tctx->wall_time_total;
        /* CPU 집약도가 높을수록 weight 증가 */
        weight = weight * (100 + cpu_intensity) / 100;
    }

    /* 대기 시간 보상: 오래 기다린 태스크에 보너스 */
    if (tctx->avg_wait_time > 5 * NSEC_PER_MSEC)
        weight = weight * 80 / 100;  /* 20% 감소 */

    /* 범위 제한 */
    if (weight < LAT_WEIGHT_MIN) weight = LAT_WEIGHT_MIN;
    if (weight > LAT_WEIGHT_MAX) weight = LAT_WEIGHT_MAX;

    return weight;
}

/* stopping 콜백: 런타임/대기 시간 EWMA 업데이트 */
SEC("struct_ops/stopping")
void BPF_PROG(lavd_stopping, struct task_struct *p, bool runnable)
{
    struct task_ctx *tctx;
    u64 now = bpf_ktime_get_ns();
    u64 runtime;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx) return;

    runtime = now - tctx->last_run_at;
    tctx->avg_runtime = ewma(tctx->avg_runtime, runtime);
    tctx->run_time_total += runtime;
    tctx->wall_time_total += now - tctx->last_enqueue_at;

    tctx->total_csw++;
    if (!runnable)
        tctx->voluntary_csw++;

    /* latency_weight 재계산 */
    tctx->latency_weight = calc_latency_weight(tctx);
}

/* running 콜백: 수면/대기 시간 측정 */
SEC("struct_ops/running")
void BPF_PROG(lavd_running, struct task_struct *p)
{
    struct task_ctx *tctx;
    u64 now = bpf_ktime_get_ns();
    u64 sleep_time, wait_time;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx) return;

    /* 수면 시간: 마지막 블록 ~ 마지막 enqueue */
    if (tctx->last_sleep_at > 0 &&
        tctx->last_enqueue_at > tctx->last_sleep_at) {
        sleep_time = tctx->last_enqueue_at - tctx->last_sleep_at;
        tctx->avg_sleep_time = ewma(tctx->avg_sleep_time, sleep_time);
    }

    /* 대기 시간: enqueue ~ running */
    wait_time = now - tctx->last_enqueue_at;
    tctx->avg_wait_time = ewma(tctx->avg_wait_time, wait_time);

    tctx->last_run_at = now;
}

scx_rustland (유저스페이스 스케줄링)

scx_rustland는 BPF가 태스크를 유저스페이스 Rust 프로그램으로 전달하고, 유저스페이스에서 스케줄링 결정을 내리는 독특한 구조입니다. BPF는 태스크를 링 버퍼(Ring Buffer)로 전달하는 중개 역할만 합니다.

// scx_rustland — 유저스페이스 스케줄러 구조
struct Scheduler {
    bpf: BpfScheduler,
    task_pool: BTreeMap<u64, TaskInfo>,
}

impl Scheduler {
    fn dispatch_tasks(&mut self) {
        // BPF 링 버퍼에서 대기 태스크 수신
        while let Some(task) = self.bpf.dequeue_task() {
            let cpu = self.select_cpu(&task);
            let slice = self.calc_slice(&task);

            // 스케줄링 결정을 BPF에 전달
            self.bpf.dispatch_task(task.pid, cpu, slice);
        }
    }

    fn select_cpu(&self, task: &TaskInfo) -> i32 {
        // 이전 CPU 선호 (캐시 지역성)
        if self.is_cpu_idle(task.prev_cpu) {
            return task.prev_cpu;
        }
        // 같은 LLC 내 idle CPU 탐색
        self.find_idle_cpu_in_llc(task.prev_cpu)
    }
}

scx_rustland 내부 아키텍처

scx_rustland의 핵심은 이중 링 버퍼(Dual Ring Buffer) 아키텍처입니다. BPF enqueue 콜백이 태스크 정보를 enqueue_buf에 기록하면 유저스페이스 Rust 스케줄러가 이를 읽어 스케줄링 결정을 내리고, 결과를 dispatch_buf에 기록합니다. BPF dispatch 콜백이 이 결과를 읽어 해당 CPU의 Local DSQ에 태스크를 삽입합니다.

// scx_rustland — 유저스페이스 스케줄링 루프 상세
use std::collections::BTreeMap;

/// 태스크 메타데이터 (BPF에서 수신)
struct QueuedTask {
    pid: u64,           // 태스크 PID
    sum_exec_runtime: u64, // 누적 실행 시간 (ns)
    weight: u64,        // nice 기반 가중치
    prev_cpu: i32,      // 마지막 실행 CPU
    flags: u64,         // SCX_ENQ_* 플래그
}

/// 디스패치 결정 (유저스페이스 → BPF)
struct DispatchedTask {
    pid: u64,           // 대상 태스크 PID
    cpu: i32,           // 실행할 CPU (-1 = 임의)
    slice_ns: u64,      // 타임 슬라이스 (ns)
    flags: u64,         // 추가 플래그
}

struct Scheduler {
    bpf: BpfScheduler,
    // vruntime 기반 정렬 — BTreeMap<vruntime, Vec<pid>>
    task_pool: BTreeMap<u64, Vec<u64>>,
    task_map: HashMap<u64, TaskInfo>,
    min_vruntime: u64,
    nr_cpus: usize,
}

impl Scheduler {
    /// 메인 스케줄링 루프 — BPF에서 태스크를 수신하고 결정을 반환
    fn run(&mut self) -> Result<()> {
        loop {
            // 1단계: BPF 링 버퍼에서 새 태스크 수신
            self.drain_queued_tasks();

            // 2단계: vruntime 순서대로 태스크 디스패치
            self.dispatch_tasks();

            // 3단계: 처리할 태스크가 없으면 잠시 대기
            if self.task_pool.is_empty() {
                self.bpf.wait_for_tasks(100); // 100us timeout
            }
        }
    }

    /// BPF 링 버퍼에서 태스크를 읽어 task_pool에 삽입
    fn drain_queued_tasks(&mut self) {
        while let Some(task) = self.bpf.dequeue_task() {
            let vruntime = self.calc_vruntime(&task);

            // 새 태스크는 min_vruntime부터 시작 (기아 방지)
            let vruntime = vruntime.max(self.min_vruntime);

            self.task_pool
                .entry(vruntime)
                .or_default()
                .push(task.pid);

            self.task_map.insert(task.pid, TaskInfo {
                weight: task.weight,
                prev_cpu: task.prev_cpu,
                sum_exec: task.sum_exec_runtime,
            });
        }
    }

    /// vruntime이 가장 작은 태스크부터 디스패치
    fn dispatch_tasks(&mut self) {
        let budget = self.nr_cpus * 4; // CPU 수 x 4 배치

        for _ in 0..budget {
            let mut entry = match self.task_pool.first_entry() {
                Some(e) => e,
                None => break,
            };

            let vruntime = *entry.key();
            let pids = entry.get_mut();
            let pid = pids.pop().unwrap();

            if pids.is_empty() {
                entry.remove();
            }

            // min_vruntime 갱신
            self.min_vruntime = vruntime;

            let info = self.task_map.get(&pid).unwrap();
            let cpu = self.select_cpu(info);
            let slice = self.calc_slice(info);

            // BPF에 디스패치 결정 전달
            self.bpf.dispatch_task(pid, cpu, slice);
        }
    }

    /// CPU 선택: 캐시 지역성 최적화
    fn select_cpu(&self, info: &TaskInfo) -> i32 {
        // 이전 CPU가 idle이면 재사용 (L1/L2 캐시 활용)
        if self.bpf.is_cpu_idle(info.prev_cpu) {
            return info.prev_cpu;
        }
        // 같은 LLC 도메인 내 idle CPU 탐색
        if let Some(cpu) = self.bpf.find_idle_in_llc(info.prev_cpu) {
            return cpu;
        }
        // 전체 시스템에서 idle CPU 탐색
        self.bpf.find_any_idle_cpu().unwrap_or(-1)
    }

    /// 타임 슬라이스 계산: weight 비례
    fn calc_slice(&self, info: &TaskInfo) -> u64 {
        let base_slice: u64 = 5_000_000; // 5ms 기본
        base_slice * info.weight / 100
    }
}

기타 스케줄러

scx 저장소에는 다양한 목적의 스케줄러가 포함되어 있습니다.

scx_layered 상세

scx_layered는 워크로드를 레이어(Layer)로 분류하여 각 레이어에 독립적인 스케줄링 정책을 적용합니다. JSON 설정 파일로 레이어 매칭 규칙과 정책을 정의하며, 각 레이어는 자체 DSQ와 cpumask를 가집니다.

// scx_layered 설정 파일 예시 (layers.json)
{
  "layers": [
    {
      "name": "interactive",
      "comment": "대화형 프로세스: 짧은 슬라이스, 선점 허용",
      "matches": [
        [{ "CommPrefix": "Xorg" }],
        [{ "CommPrefix": "gnome-shell" }],
        [{ "NiceAbove": 0 }]
      ],
      "kind": {
        "Confined": {
          "cpus_range": [0, 7],
          "util_range": [0.0, 0.8]
        }
      },
      "idle_smt": true,
      "preempt": true,
      "slice_us": 1000,
      "weight": 200
    },
    {
      "name": "batch",
      "comment": "배치 처리: 긴 슬라이스, CPU 격리",
      "matches": [
        [{ "CommPrefix": "gcc" }],
        [{ "CommPrefix": "make" }],
        [{ "NiceBelow": 0 }]
      ],
      "kind": {
        "Grouped": {
          "cpus_range": [8, 15],
          "preempt": false
        }
      },
      "slice_us": 20000,
      "weight": 50
    },
    {
      "name": "default",
      "comment": "나머지 모든 태스크",
      "matches": [[{ "CgroupPrefix": "/" }]],
      "kind": { "Open": { "preempt": false } },
      "slice_us": 5000,
      "weight": 100
    }
  ]
}

scx_nest 상세 — 코어 컴팩팅

scx_nest는 CPU를 Primary(주 코어)와 Reserve(예비 코어)로 나누어, 부하가 낮을 때 Reserve 코어를 깊은 C-state로 진입시켜 전력을 절약합니다. 동시에 Primary 코어의 P-state가 높아져 단일 스레드 성능이 향상되는 효과도 있습니다.

/* scx_nest — 코어 컴팩팅 핵심 로직 */

/* CPU 마스크: primary와 reserve 분리 관리 */
static u64 primary_cpumask[MAX_CPUS / 64];
static u64 reserve_cpumask[MAX_CPUS / 64];

/* per-CPU 통계 */
struct pcpu_ctx {
    u64 last_used;       /* 마지막 태스크 실행 시점 */
    u32 nest_level;      /* 0=primary, 1=reserve */
    bool in_use;         /* 현재 태스크 실행 중 */
};

/* enqueue: primary 코어 우선, 부족 시 reserve 활성화 */
SEC("struct_ops/select_cpu")
s32 BPF_PROG(nest_select_cpu, struct task_struct *p,
                              s32 prev_cpu, u64 wake_flags)
{
    s32 cpu;

    /* 1단계: 이전 CPU가 primary이고 idle이면 재사용 */
    if (is_primary(prev_cpu) && scx_bpf_test_and_clear_cpu_idle(prev_cpu))
        return prev_cpu;

    /* 2단계: primary 마스크 내 idle CPU 탐색 */
    cpu = scx_bpf_pick_idle_cpu(primary_cpumask, 0);
    if (cpu >= 0)
        return cpu;

    /* 3단계: primary 포화 → reserve에서 CPU 승격 */
    cpu = scx_bpf_pick_idle_cpu(reserve_cpumask, 0);
    if (cpu >= 0) {
        promote_to_primary(cpu);
        return cpu;
    }

    return prev_cpu;
}

/* compact_timer: 주기적으로 idle primary를 reserve로 강등 */
static void compact_primary(void)
{
    u64 now = bpf_ktime_get_ns();
    s32 cpu;

    bpf_for(cpu, 0, nr_cpus) {
        struct pcpu_ctx *ctx = lookup_pcpu_ctx(cpu);
        if (!ctx || !is_primary(cpu))
            continue;

        /* 1초 이상 idle이면 reserve로 강등 */
        if (!ctx->in_use &&
            now - ctx->last_used > 1000000000ULL) {
            demote_to_reserve(cpu);
        }
    }
}

scx_central 상세 — 중앙 집중 스케줄링

scx_central은 하나의 전용 CPU가 시스템의 모든 스케줄링 결정을 내리는 실험적 모델입니다. 나머지 CPU는 스케줄링 오버헤드가 없이 순수하게 태스크만 실행합니다. 이 모델은 스케줄링 잠금 경합을 완전히 제거하지만, 중앙 CPU가 병목이 될 수 있습니다.

/* scx_central — 핵심 동작 원리 */

/* central CPU에서 주기적으로 실행되는 디스패치 타이머 */
static void central_dispatch_timer(void)
{
    s32 cpu;

    /* 모든 worker CPU의 Local DSQ를 확인하고 채움 */
    bpf_for(cpu, 0, nr_cpus) {
        if (cpu == central_cpu)
            continue;

        /* worker CPU의 Local DSQ가 비었으면 Global에서 이동 */
        if (scx_bpf_dsq_nr_queued(SCX_DSQ_LOCAL_ON | cpu) == 0) {
            scx_bpf_dsq_move_to_local(SCX_DSQ_GLOBAL);
            /* IPI로 worker CPU에 새 태스크 알림 */
            scx_bpf_kick_cpu(cpu, 0);
        }
    }
}

/* worker CPU에서는 tick을 비활성화하여 오버헤드 제거 */
/* SCX_OPS_ENQ_LAST 플래그로 마지막 태스크까지 처리 */

scx_flash 상세 — 최소 지연 FIFO

scx_flash는 순수 FIFO 스케줄링으로 최소 지연을 추구합니다. 모든 태스크를 도착 순서대로 실행하며, 복잡한 가중치 계산이나 vtime 관리가 없어 스케줄링 오버헤드가 극도로 낮습니다. 실시간에 가까운 응답성이 필요하지만 RT 스케줄러를 사용하기 어려운 환경에 적합합니다.

/* scx_flash — 최소 지연 FIFO 스케줄링 핵심 */

/* 모든 태스크를 FIFO로 Local DSQ에 직접 삽입 */
SEC("struct_ops/select_cpu")
s32 BPF_PROG(flash_select_cpu, struct task_struct *p,
                               s32 prev_cpu, u64 wake_flags)
{
    bool is_idle = false;
    s32 cpu;

    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &is_idle);
    if (is_idle) {
        /* idle CPU 발견 → Local DSQ에 직접 FIFO 삽입
         * Global DSQ 잠금 우회 → 최소 레이턴시 */
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL, SCX_SLICE_DFL, 0);
    }
    return cpu;
}

SEC("struct_ops/enqueue")
void BPF_PROG(flash_enqueue, struct task_struct *p, u64 enq_flags)
{
    /* select_cpu에서 삽입 안 된 경우만 Global FIFO로 */
    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL, SCX_SLICE_DFL, enq_flags);
}

/* dispatch: Global → Local 이동만 수행 */
SEC("struct_ops/dispatch")
void BPF_PROG(flash_dispatch, s32 cpu,
                              struct task_struct *prev)
{
    scx_bpf_dsq_move_to_local(SCX_DSQ_GLOBAL);
}

/*
 * scx_flash 성능 특성:
 * - 스케줄링 오버헤드: ~50ns (vtime 계산 없음)
 * - 공정성: 없음 (순수 FIFO)
 * - 적합: 지연 민감 + 짧은 태스크 위주 워크로드
 * - 부적합: CPU-bound 혼합 (기아 발생 가능)
 */

개발 환경 설정

sched_ext 개발을 위해서는 v6.12 이상의 커널과 BPF 도구 체인이 필요합니다.

# 1. 커널 빌드 (sched_ext 활성화)
git clone --depth=1 https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git
cd linux

# 필수 커널 설정
make menuconfig
# General setup → BPF subsystem → [*] Enable bpf() system call
# General setup → Scheduler → [*] sched_ext extensible scheduler class

# 또는 직접 .config 수정
cat >> .config <<EOF
CONFIG_BPF=y
CONFIG_BPF_SYSCALL=y
CONFIG_BPF_JIT=y
CONFIG_DEBUG_INFO_BTF=y
CONFIG_SCHED_CLASS_EXT=y
EOF

make -j$(nproc)
sudo make modules_install install

# 2. scx 저장소 클론 및 빌드
git clone https://github.com/sched-ext/scx.git
cd scx

# 의존성 설치 (Ubuntu/Debian)
sudo apt install clang llvm libelf-dev libbpf-dev \
                 cargo rustc meson ninja-build

# Rust 빌드 (scx_rusty, scx_lavd 등)
cargo build --release

# C 빌드 (scx_simple, scx_central 등)
meson setup build
meson compile -C build

# 3. 스케줄러 실행
# scx_simple 실행
sudo ./build/scheds/c/scx_simple

# scx_rusty 실행 (Rust)
sudo ./target/release/scx_rusty

# scx_lavd 실행
sudo ./target/release/scx_lavd

# 스케줄러 상태 확인
cat /sys/kernel/sched_ext/root/ops
cat /sys/kernel/sched_ext/root/enable
cat /sys/kernel/sched_ext/nr_rejected

나만의 BPF 스케줄러 작성

scx_simple을 기반으로 자신만의 BPF 스케줄러를 작성하는 과정을 단계별로 안내합니다.

/* my_scheduler.bpf.c — 가중치 기반 공정 스케줄러 */
#include <scx/common.bpf.h>

char _license[] SEC("license") = "GPL";

/* per-CPU DSQ ID: 각 CPU마다 하나의 DSQ */
#define CPU_DSQ_BASE  100
#define MAX_CPUS      256

/* per-task 가상 시간 */
struct task_ctx {
    u64 vtime;
    u32 weight;
};

struct {
    __uint(type, BPF_MAP_TYPE_TASK_STORAGE);
    __uint(map_flags, BPF_F_NO_PREALLOC);
    __type(key, int);
    __type(value, struct task_ctx);
} task_data SEC(".maps");

/* 전역 vtime 추적 */
u64 vtime_now;

SEC("struct_ops/init")
s32 BPF_PROG(my_init)
{
    s32 i;

    /* 각 CPU마다 DSQ 생성 */
    for (i = 0; i < MAX_CPUS; i++) {
        if (scx_bpf_create_dsq(CPU_DSQ_BASE + i, -1) < 0)
            break;
    }
    return 0;
}

SEC("struct_ops/init_task")
s32 BPF_PROG(my_init_task, struct task_struct *p,
                            struct scx_init_task_args *args)
{
    struct task_ctx *tctx;

    tctx = bpf_task_storage_get(&task_data, p, 0,
                                  BPF_LOCAL_STORAGE_GET_F_CREATE);
    if (!tctx)
        return -ENOMEM;

    tctx->vtime = vtime_now;
    tctx->weight = p->scx.weight;
    return 0;
}

SEC("struct_ops/select_cpu")
s32 BPF_PROG(my_select_cpu, struct task_struct *p,
                            s32 prev_cpu, u64 wake_flags)
{
    bool is_idle = false;
    s32 cpu;

    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags,
                                  &is_idle);
    if (is_idle)
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
    return cpu;
}

SEC("struct_ops/enqueue")
void BPF_PROG(my_enqueue, struct task_struct *p,
                          u64 enq_flags)
{
    struct task_ctx *tctx;
    s32 cpu;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (!tctx) {
        scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL,
                           SCX_SLICE_DFL, enq_flags);
        return;
    }

    /* per-CPU DSQ에 vtime 기반 삽입 */
    cpu = scx_bpf_task_cpu(p);
    scx_bpf_dsq_insert_vtime(p, CPU_DSQ_BASE + cpu,
                              SCX_SLICE_DFL,
                              tctx->vtime, enq_flags);
}

SEC("struct_ops/dispatch")
void BPF_PROG(my_dispatch, s32 cpu,
                            struct task_struct *prev)
{
    /* 현재 CPU의 DSQ에서 소비 */
    scx_bpf_consume(CPU_DSQ_BASE + cpu);

    /* 비었으면 Global DSQ에서 소비 */
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

SEC("struct_ops/stopping")
void BPF_PROG(my_stopping, struct task_struct *p,
                            bool runnable)
{
    struct task_ctx *tctx;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (tctx) {
        /* vtime 갱신: 사용한 슬라이스 / 가중치 */
        tctx->vtime += (SCX_SLICE_DFL - p->scx.slice)
                       / tctx->weight;
    }
}

SEC(".struct_ops.link")
struct sched_ext_ops my_ops = {
    .init       = (void *)my_init,
    .init_task  = (void *)my_init_task,
    .select_cpu = (void *)my_select_cpu,
    .enqueue    = (void *)my_enqueue,
    .dispatch   = (void *)my_dispatch,
    .stopping   = (void *)my_stopping,
    .name       = "my_scheduler",
};

/* my_scheduler.c — 유저스페이스 로더 */
#include <bpf/libbpf.h>
#include <signal.h>
#include <stdio.h>

static volatile bool running = true;

static void sigint_handler(int sig)
{
    running = false;
}

int main(int argc, char **argv)
{
    struct my_scheduler_bpf *skel;
    struct bpf_link *link;

    signal(SIGINT, sigint_handler);

    /* BPF 스켈레톤 로드 */
    skel = my_scheduler_bpf__open_and_load();
    if (!skel)
        return 1;

    /* struct_ops 등록 */
    link = bpf_map__attach_struct_ops(skel->maps.my_ops);
    if (!link)
        goto cleanup;

    printf("스케줄러 활성화됨. Ctrl+C로 종료.\n");

    while (running)
        sleep(1);

cleanup:
    bpf_link__destroy(link);
    my_scheduler_bpf__destroy(skel);
    return 0;
}

# Makefile — BPF 스케줄러 빌드
BPF_CLANG = clang
BPF_CFLAGS = -target bpf -O2 -g -Wall

all: my_scheduler.bpf.o my_scheduler

my_scheduler.bpf.o: my_scheduler.bpf.c
	$(BPF_CLANG) $(BPF_CFLAGS) -c $< -o $@

my_scheduler.skel.h: my_scheduler.bpf.o
	bpftool gen skeleton $< > $@

my_scheduler: my_scheduler.c my_scheduler.skel.h
	gcc -O2 -o $@ $< -lbpf -lelf -lz

디버깅(Debugging)과 트레이싱

sched_ext 스케줄러의 디버깅에는 sysfs 인터페이스, bpftool, ftrace, perf를 활용합니다.

# sysfs 상태 확인
cat /sys/kernel/sched_ext/root/ops      # 현재 활성 스케줄러 이름
cat /sys/kernel/sched_ext/root/enable   # 활성화 상태 (1/0)
cat /sys/kernel/sched_ext/nr_rejected   # 거부된 태스크 수

# bpftool로 BPF 프로그램 상태 확인
sudo bpftool prog list | grep struct_ops
sudo bpftool struct_ops list
sudo bpftool struct_ops dump name my_ops

# ftrace로 스케줄링 이벤트 추적
echo 1 > /sys/kernel/debug/tracing/events/sched_ext/enable
cat /sys/kernel/debug/tracing/trace_pipe

# sched_ext tracepoint 목록
ls /sys/kernel/debug/tracing/events/sched_ext/
# sched_ext_enqueue, sched_ext_dispatch, sched_ext_cpu_*

# perf로 스케줄링 레이턴시 측정
sudo perf sched record -- sleep 10
sudo perf sched latency --sort max

# BPF 프로그램 로그 확인
sudo cat /sys/kernel/debug/tracing/trace_pipe | grep bpf_trace_printk

/* BPF 프로그램 내 디버깅 출력 */
SEC("struct_ops/enqueue")
void BPF_PROG(debug_enqueue, struct task_struct *p,
                              u64 enq_flags)
{
    /* bpf_printk로 trace_pipe에 출력 */
    bpf_printk("enqueue: pid=%d comm=%s cpu=%d",
               p->pid, p->comm,
               scx_bpf_task_cpu(p));

    scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL,
                       SCX_SLICE_DFL, enq_flags);
}

성능 벤치마크

sched_ext 스케줄러의 성능은 워크로드에 따라 크게 달라집니다. 아래는 대표적인 벤치마크 결과입니다.

# 벤치마크 실행 예시

# hackbench — 스케줄러 지연 벤치마크
sudo hackbench -g 20 -l 1000

# schbench — 스케줄러 벤치마크 (p99 지연)
sudo schbench -m 8 -t 16 -s 30000

# kernbench — 커널 빌드 처리량
kernbench -M -H -O -n 5

# CFS와 scx_rusty 비교
# 1. CFS로 벤치마크 (기본)
sudo hackbench -g 20 -l 1000 2>&1 | tee cfs_result.txt

# 2. scx_rusty 로드
sudo scx_rusty &

# 3. scx_rusty로 벤치마크
sudo hackbench -g 20 -l 1000 2>&1 | tee rusty_result.txt

# 4. 결과 비교
diff cfs_result.txt rusty_result.txt

schbench 결과 해석 가이드

schbench는 스케줄러의 꼬리 지연(Tail Latency)을 측정하는 대표적인 도구입니다. 메시지 전달 패턴을 시뮬레이션하여 실제 서버 워크로드와 유사한 부하를 생성합니다.

# schbench 기본 실행 (-m: 메시지 스레드 그룹, -t: 그룹당 스레드, -s: 실행 시간 μs)
sudo schbench -m 8 -t 16 -s 30000

# 출력 예시:
# Latency percentiles (usec)
#        50.0th: 12
#        75.0th: 18
#        90.0th: 26
#        99.0th: 48    ← p99: 요청의 99%가 48μs 이내 완료
#        99.9th: 112   ← p99.9: 극단적 꼬리 지연
#        max:    580

워크로드별 스케줄러 추천

워크로드 특성에 따라 적합한 sched_ext 스케줄러가 다릅니다. 아래 표는 대표적인 시나리오별 추천을 정리한 것입니다.

perf stat으로 스케줄러 성능 비교

perf stat을 사용하면 컨텍스트 스위치(Context Switch) 횟수, 캐시 미스(Cache Miss) 비율 등 스케줄러의 저수준 동작을 정량적으로 비교할 수 있습니다.

# 1. CFS 기준 측정
sudo perf stat -e context-switches,cpu-migrations,cache-misses,cache-references,\
instructions,cycles -a -- hackbench -g 20 -l 1000 2>&1 | tee perf_cfs.txt

# 2. scx_rusty 로드 후 측정
sudo scx_rusty &
sudo perf stat -e context-switches,cpu-migrations,cache-misses,cache-references,\
instructions,cycles -a -- hackbench -g 20 -l 1000 2>&1 | tee perf_rusty.txt

# 3. scx_lavd 로드 후 측정
sudo scx_lavd --performance &
sudo perf stat -e context-switches,cpu-migrations,cache-misses,cache-references,\
instructions,cycles -a -- hackbench -g 20 -l 1000 2>&1 | tee perf_lavd.txt

# 캐시 미스율 비교 스크립트
for f in perf_cfs.txt perf_rusty.txt perf_lavd.txt; do
    echo "=== $f ==="
    misses=$(grep 'cache-misses' "$f" | awk '{print $1}' | tr -d ',')
    refs=$(grep 'cache-references' "$f" | awk '{print $1}' | tr -d ',')
    ctx=$(grep 'context-switches' "$f" | awk '{print $1}' | tr -d ',')
    mig=$(grep 'cpu-migrations' "$f" | awk '{print $1}' | tr -d ',')
    echo "  컨텍스트 스위치: $ctx"
    echo "  CPU 마이그레이션: $mig"
    echo "  캐시 미스율: $(echo "scale=2; $misses * 100 / $refs" | bc)%"
done

실제 사용 사례

sched_ext는 이미 여러 대규모 환경에서 프로덕션 또는 실험적으로 사용되고 있습니다.

커널 설정 옵션

sched_ext를 활성화하기 위한 커널 설정 옵션들입니다.

# 현재 커널에서 sched_ext 지원 여부 확인
grep CONFIG_SCHED_CLASS_EXT /boot/config-$(uname -r)

# BPF 관련 설정 일괄 확인
grep -E 'CONFIG_(SCHED_CLASS_EXT|BPF|BTF)' /boot/config-$(uname -r)

# CONFIG_SCHED_CLASS_EXT=y
# CONFIG_BPF=y
# CONFIG_BPF_SYSCALL=y
# CONFIG_BPF_JIT=y
# CONFIG_DEBUG_INFO_BTF=y

enqueue_task_scx 내부 구현

커널 코어의 enqueue_task_scx()는 태스크가 runnable 상태가 될 때 호출됩니다. 이 함수는 BPF ops의 select_cpu와 enqueue 콜백을 순차적으로 호출하며, 태스크 상태 머신을 관리합니다.

/* kernel/sched/ext.c — enqueue_task_scx 핵심 경로 (간략화) */
static void enqueue_task_scx(struct rq *rq,
                              struct task_struct *p, int flags)
{
    struct sched_ext_entity *scx = &p->scx;
    u64 enq_flags = 0;

    /* 태스크 상태를 QUEUED로 전환 */
    WARN_ON_ONCE(scx->flags & SCX_TASK_QUEUED);
    scx->flags |= SCX_TASK_QUEUED;

    /* wakeup인 경우 select_cpu 콜백 호출 */
    if (flags & ENQUEUE_WAKEUP) {
        s32 cpu;

        if (SCX_HAS_OP(select_cpu)) {
            cpu = SCX_CALL_OP_RET(SCX_KF_SELECT_CPU,
                                   select_cpu, p,
                                   task_cpu(p),
                                   flags);
            /* select_cpu에서 직접 DSQ에 삽입한 경우 */
            if (scx->dsq)
                return;
        }
    }

    /* enqueue 콜백 호출 */
    if (SCX_HAS_OP(enqueue)) {
        SCX_CALL_OP(SCX_KF_ENQUEUE, enqueue, p, enq_flags);
    } else {
        /* enqueue 미구현 시 Global DSQ로 */
        scx_bpf_dsq_insert(p, SCX_DSQ_GLOBAL,
                           SCX_SLICE_DFL, enq_flags);
    }
}

pick_next_task_scx 내부

pick_next_task_scx()는 CPU에서 다음에 실행할 태스크를 선택합니다. Local DSQ를 먼저 확인하고, 비어있으면 dispatch 콜백을 호출합니다.

/* kernel/sched/ext.c — pick_next_task_scx (간략화) */
static struct task_struct *
pick_next_task_scx(struct rq *rq)
{
    struct task_struct *p;

retry:
    /* 1단계: Local DSQ에서 태스크 확인 */
    p = first_local_task(rq);
    if (p)
        return p;

    /* 2단계: dispatch 콜백 호출 (Custom/Global → Local) */
    if (SCX_HAS_OP(dispatch)) {
        SCX_CALL_OP(SCX_KF_DISPATCH, dispatch,
                    cpu_of(rq), rq->curr);
    } else {
        scx_bpf_consume(SCX_DSQ_GLOBAL);
    }

    /* dispatch에서 Local DSQ에 태스크를 넣었을 수 있음 */
    p = first_local_task(rq);
    if (p)
        return p;

    /* 태스크 없음 — idle로 진입 */
    return NULL;
}

/* scx_bpf_consume 내부 — DSQ 간 태스크 이동 */
bool scx_bpf_consume(u64 dsq_id)
{
    struct scx_dispatch_q *dsq;
    struct task_struct *p;

    dsq = find_dsq_for_dispatch(this_rq(), dsq_id, 0);
    if (!dsq)
        return false;

    /* FIFO 모드: 리스트 head에서 꺼냄 */
    if (!list_empty(&dsq->list)) {
        p = list_first_entry(&dsq->list,
                              struct task_struct,
                              scx.dsq_list);
        move_task_to_local_dsq(p);
        return true;
    }

    /* vtime 모드: RB-tree min에서 꺼냄 */
    if (dsq->priq.rb_node) {
        p = rb_entry(rb_first(&dsq->priq),
                      struct task_struct,
                      scx.dsq_priq);
        move_task_to_local_dsq(p);
        return true;
    }

    return false;
}

cgroup 지원

sched_ext는 cgroup v2와 통합하여 컨테이너 환경에서도 BPF 스케줄러를 사용할 수 있습니다. BPF 스케줄러는 태스크의 cgroup 정보를 조회하여 컨테이너별로 차별화된 스케줄링 정책을 적용할 수 있습니다.

/* cgroup-aware 스케줄링 예시 */
SEC("struct_ops/enqueue")
void BPF_PROG(cgroup_enqueue, struct task_struct *p,
                              u64 enq_flags)
{
    struct cgroup *cgrp;
    u64 cgrp_id;
    u64 dsq_id;

    /* 태스크의 cgroup ID 조회 */
    cgrp = scx_bpf_task_cgroup(p);
    if (cgrp) {
        cgrp_id = cgrp->kn->id;
        bpf_cgroup_release(cgrp);
    } else {
        cgrp_id = 0;
    }

    /* cgroup ID를 DSQ ID로 매핑 */
    dsq_id = cgrp_id % NUM_DSQS;

    /* cgroup 가중치 기반 vtime 삽입 */
    scx_bpf_dsq_insert_vtime(p, dsq_id, SCX_SLICE_DFL,
                              calc_vtime(p), enq_flags);
}

/* scx_flatcg — cgroup 계층을 flat하게 처리 */
/*
 * scx_flatcg는 cgroup 계층의 가중치를 단일 레벨로
 * 평탄화(flatten)하여 WFQ를 수행합니다.
 *
 * 예: /A (weight=100) / /A/B (weight=50)
 * → B의 실효 가중치 = 100 * 50 / sum = 계층 반영
 */

토폴로지 인식 스케줄링

현대 서버는 복잡한 CPU 토폴로지(SMT, LLC, NUMA)를 가집니다. sched_ext는 BPF 스케줄러가 토폴로지를 인식하여 최적의 CPU를 선택할 수 있도록 헬퍼를 제공합니다.

/* 토폴로지 인식 CPU 선택 */
SEC("struct_ops/select_cpu")
s32 BPF_PROG(topo_select_cpu, struct task_struct *p,
                              s32 prev_cpu, u64 wake_flags)
{
    bool is_idle = false;
    s32 cpu;

    /*
     * scx_bpf_select_cpu_dfl()은 내부적으로 다음 순서로 탐색:
     * 1. prev_cpu 자체가 idle인지 확인
     * 2. prev_cpu와 같은 SMT 코어의 sibling idle 확인
     * 3. prev_cpu와 같은 LLC의 다른 코어 idle 확인
     * 4. 같은 NUMA 노드의 idle CPU 확인
     * 5. 전체 시스템에서 idle CPU 확인
     */
    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags,
                                  &is_idle);

    if (is_idle) {
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
    }

    return cpu;
}

/* 커스텀 토폴로지 맵 (BPF 맵으로 구성) */
struct cpu_topo {
    s32 llc_id;      /* Last-Level Cache ID */
    s32 numa_id;     /* NUMA 노드 ID */
    s32 core_id;     /* 물리 코어 ID */
    s32 smt_id;      /* SMT 스레드 ID */
};

struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(max_entries, 1024);
    __type(key, u32);
    __type(value, struct cpu_topo);
} cpu_topology SEC(".maps");

CPU 토폴로지 계층 구조

다음 다이어그램은 2 NUMA 노드, 노드당 2 LLC, LLC당 4 물리 코어, 코어당 2 SMT 스레드로 구성된 32-CPU 시스템의 토폴로지 계층을 보여줍니다. scx_bpf_select_cpu_dfl()은 이 계층을 아래에서 위로 순회하며, 캐시 지역성이 높은 CPU를 우선 선택합니다.

/* 토폴로지 기반 커스텀 CPU 선택 — LLC 친화성 최적화 */

/* LLC별 cpumask를 미리 계산 (init에서) */
struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(max_entries, 16);   /* 최대 16 LLC */
    __type(key, u32);
    __type(value, struct bpf_cpumask);
} llc_cpumasks SEC(".maps");

/* CPU → LLC ID 매핑 */
struct {
    __uint(type, BPF_MAP_TYPE_ARRAY);
    __uint(max_entries, 1024);
    __type(key, u32);
    __type(value, u32);
} cpu_to_llc SEC(".maps");

SEC("struct_ops/select_cpu")
s32 BPF_PROG(topo_llc_select_cpu, struct task_struct *p,
                                   s32 prev_cpu, u64 wake_flags)
{
    u32 *llc_id;
    struct bpf_cpumask *llc_mask;
    s32 cpu;
    bool is_idle = false;

    /* 1단계: prev_cpu 직접 확인 (최적 — 캐시 hit) */
    if (scx_bpf_test_and_clear_cpu_idle(prev_cpu)) {
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
        return prev_cpu;
    }

    /* 2단계: prev_cpu의 LLC 내에서 idle CPU 탐색 */
    llc_id = bpf_map_lookup_elem(&cpu_to_llc, &prev_cpu);
    if (!llc_id)
        goto fallback;

    llc_mask = bpf_map_lookup_elem(&llc_cpumasks, llc_id);
    if (!llc_mask)
        goto fallback;

    cpu = scx_bpf_pick_idle_cpu((const struct cpumask *)llc_mask,
                                0);
    if (cpu >= 0) {
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
        return cpu;
    }

fallback:
    /* 3단계: 기본 탐색 (NUMA → 전체) */
    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags,
                                  &is_idle);
    if (is_idle)
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
    return cpu;
}

/* init에서 토폴로지 맵 초기화 (유저스페이스 로더에서 수행) */
/*
 * /sys/devices/system/cpu/cpuN/cache/indexN/shared_cpu_list
 * /sys/devices/system/cpu/cpuN/topology/core_id
 * /sys/devices/system/cpu/cpuN/topology/physical_package_id
 * 에서 읽어 BPF 맵을 채움
 */

향후 로드맵

sched_ext는 v6.12 머지 이후에도 활발하게 개발이 진행 중입니다. 주요 계획은 다음과 같습니다:

/* 향후 기대되는 kfunc 예시 (아직 미구현) */

/* CPU 캐시 상태 조회 */
u64 scx_bpf_cpu_cache_occupancy(s32 cpu) __ksym;

/* CPU 전력 상태 조회 */
u32 scx_bpf_cpu_freq_cur(s32 cpu) __ksym;

/* cgroup 가중치 조회 */
u32 scx_bpf_cgroup_weight(struct task_struct *p) __ksym;

공통 실수와 모범 사례

sched_ext 스케줄러를 개발할 때 자주 발생하는 실수와 이를 방지하는 모범 사례를 정리합니다. 아래 표의 문제들은 실제 개발 과정에서 빈번하게 보고된 사례입니다.

흔한 실수 테이블

BPF verifier 에러 대처 체크리스트

성능 최적화 체크리스트

모범 사례 코드 패턴

/* 모범 사례 1: 안전한 enqueue — 모든 경로에서 dsq_insert 보장 */
SEC("struct_ops/enqueue")
void BPF_PROG(safe_enqueue, struct task_struct *p, u64 enq_flags)
{
    struct task_ctx *tctx;
    u64 dsq_id = SCX_DSQ_GLOBAL;  /* 기본 폴백 */
    u64 slice = SCX_SLICE_DFL;

    tctx = bpf_task_storage_get(&task_data, p, 0, 0);
    if (tctx) {
        /* 커스텀 로직: DSQ 선택, 슬라이스 조정 */
        dsq_id = select_dsq(tctx);
        slice = calc_slice(tctx);
    }

    /* ✓ 어떤 경우든 반드시 dsq_insert 호출 */
    scx_bpf_dsq_insert(p, dsq_id, slice, enq_flags);
}

/* 모범 사례 2: dispatch 폴백 체인 */
SEC("struct_ops/dispatch")
void BPF_PROG(safe_dispatch, s32 cpu, struct task_struct *prev)
{
    /* 1순위: 커스텀 DSQ 소비 */
    if (scx_bpf_consume(my_dsq_id))
        return;

    /* 2순위: Local DSQ (같은 CPU의 태스크) */
    if (scx_bpf_consume(SCX_DSQ_LOCAL))
        return;

    /* 3순위: Global DSQ (최종 폴백) */
    scx_bpf_consume(SCX_DSQ_GLOBAL);
}

/* 모범 사례 3: vtime 정규화로 오버플로우 방지 */
static u64 vtime_base;  /* 전역 vtime 기준점 */

static u64 normalize_vtime(u64 vtime)
{
    /*
     * vtime이 기준점보다 너무 뒤처지면 기준점으로 당김
     * → 장시간 sleep 후 복귀한 태스크의 과도한 우대 방지
     */
    if (vtime_before(vtime, vtime_base - SCX_SLICE_DFL))
        return vtime_base - SCX_SLICE_DFL;
    return vtime;
}

/* 모범 사례 4: 안전한 init — 에러 처리 */
SEC("struct_ops.s/init")
s32 BPF_PROG(safe_init)
{
    s32 ret;
    int i;

    /* DSQ 생성: 실패 시 에러 반환 → 안전한 폴백 */
    for (i = 0; i < nr_domains; i++) {
        ret = scx_bpf_create_dsq(i, -1);
        if (ret) {
            scx_bpf_error("DSQ %d 생성 실패: %d", i, ret);
            return ret;  /* CFS로 폴백 */
        }
    }
    return 0;
}

/* 모범 사례 5: select_cpu에서 idle CPU 최적화 */
SEC("struct_ops/select_cpu")
s32 BPF_PROG(safe_select_cpu, struct task_struct *p,
                              s32 prev_cpu, u64 wake_flags)
{
    bool is_idle = false;
    s32 cpu;

    /* 기본 idle CPU 선택 (커널 내장 로직 활용) */
    cpu = scx_bpf_select_cpu_dfl(p, prev_cpu, wake_flags, &is_idle);

    if (is_idle) {
        /* idle CPU를 찾았으면 직접 Local DSQ에 삽입 (빠른 경로) */
        scx_bpf_dsq_insert(p, SCX_DSQ_LOCAL,
                           SCX_SLICE_DFL, 0);
    }

    return cpu;
}

참고 자료

커널 공식 문서

• Extensible Scheduler Class (sched_ext) — 커널 공식 sched_ext 문서로, 아키텍처 개요와 사용법을 설명합니다
• BPF Documentation — BPF 서브시스템 공식 문서로, struct_ops 등 sched_ext의 기반 기술을 다룹니다
• Scheduler Documentation — 리눅스 스케줄러 전반의 공식 문서 인덱스입니다

LWN.net 기사

• The extensible scheduler class — sched_ext의 초기 설계 동기와 아키텍처를 소개하는 기사입니다
• Scheduler extensibility is headed for the mainline — sched_ext가 메인라인에 병합되기까지의 과정을 다룹니다
• BPF-based scheduling with sched_ext — BPF struct_ops 기반 스케줄러 확장의 기술적 세부사항을 분석합니다
• Pulling sched_ext into 6.12 — 리눅스 6.12에 sched_ext가 최종 병합된 과정을 설명합니다

GitHub 저장소

• sched-ext/scx — sched_ext 공식 사용자 공간 스케줄러 모음(scx_rusty, scx_lavd, scx_rustland 등)입니다
• scx_rusty — Rust 기반 NUMA 인식 스케줄러로, 부하 분산과 캐시 친화적 배치를 구현합니다
• scx_lavd — Latency-criticality Aware Virtual Deadline 스케줄러로, 대화형 워크로드에 최적화되어 있습니다
• scx_rustland — 사용자 공간에서 스케줄링 결정을 내리는 실험적 스케줄러입니다

커널 소스

• kernel/sched/ext.c — sched_ext 코어 구현, DSQ 관리, BPF ops 디스패치 로직
• kernel/sched/ext.h — sched_ext 내부 헤더, 구조체 및 인라인 함수 정의
• include/linux/sched/ext.h — sched_ext 공개 헤더, task_struct 확장 필드
• tools/sched_ext/ — sched_ext BPF 스케줄러 예제 및 테스트 도구
• kernel/sched/core.c — sched_class 등록 및 스케줄러 코어 통합 지점
• kernel/bpf/bpf_struct_ops.c — BPF struct_ops 프레임워크, sched_ext ops 등록 기반

발표 및 블로그

• sched_ext: scalable BPF CPU scheduler (LPC 2023) — Linux Plumbers Conference에서 발표된 sched_ext 설계 및 성능 분석입니다
• sched_ext: A BPF-Extensible Scheduler Class — sched_ext 핵심 개발자의 기술 블로그 시리즈로, 내부 동작을 상세히 설명합니다

관련 문서

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

• 프로세스 스케줄러 — sched_class 계층과 전체 아키텍처
• CFS 스케줄러 상세 — CFS/EEVDF 내부 구현과 vruntime
• BPF/eBPF/XDP — BPF 프레임워크와 struct_ops 기반
• Real-Time Linux — RT 스케줄링과 PREEMPT_RT
• cpusets & CPU Isolation — CPU 격리와 affinity
• preempt_count & 선점 모델 — 선점 카운터와 스케줄링 시점
• Context Switching — 프로세스 전환 메커니즘
• NUMA — NUMA 토폴로지와 메모리 정책(Memory Policy)