CFS라는 이름 뒤의 EEVDF

핵심 질문

runnable task가 여러 개일 때 fair scheduler는 누가 CPU를 덜 받았는지와 누구의 현재 요청을 먼저 끝낼지를 어떻게 동시에 판단할까요? 답은 eligibility와 virtual deadline 두 축에 있습니다.

먼저 10분짜리 개념 설명과 줄별 해설 보기

1. 쉬운 모델: 식당 대기열이 아니라 빚 장부

FIFO 대기열이라면 먼저 온 사람을 고르면 됩니다. fair scheduler는 다릅니다. task마다 CPU 지분이 다르고, 잠들었다가 깨어나며, 한 번에 요청하는 실행 시간도 달라집니다. 그래서 커널은 실제 시간만 저장하지 않고 가중치를 반영한 가상 시간 장부를 유지합니다.

여기서 V는 실행 큐의 평균 가상 시간, v_i는 entity의 vruntime, w_i는 load weight입니다. EEVDF는 덜 받은 후보를 먼저 만들고 그 집합 안에서 가상 마감이 빠른 요청을 고릅니다.

2. 무엇이 어디에 저장되는가

3. 한 번의 선택이 만들어지는 호출 경로

1. 실행 시간 계측update_curr()가 현재 entity가 실제로 사용한 시간을 구하고 vruntime을 증가시킵니다.
2. 요청 소진 확인update_deadline()이 vruntime < deadline인지 검사합니다. 요청을 다 썼다면 새 slice와 deadline을 만듭니다.
3. 재스케줄 요청다른 후보가 있고 slice 보호 조건이 끝났다면 resched_curr_lazy()로 다음 scheduling point를 요청합니다.
4. 계층별 후보 선택pick_task_fair()가 root cfs_rq에서 시작해 group cfs_rq를 내려가며 pick_next_entity()를 반복합니다.
5. EEVDF 탐색pick_eevdf()가 eligible 후보 중 earliest virtual deadline entity를 augmented rb-tree에서 찾습니다.
6. 실제 task 도달더 내려갈 group cfs_rq가 없으면 task_of(se)로 최종 task를 얻습니다.

3.1 CPU, group, task는 서로 다른 층이다

rq는 CPU별 전체 실행 상태이고 cfs_rq는 그중 fair 후보의 장부입니다. group scheduling을 켜면 root 장부의 후보가 task가 아니라 group일 수 있습니다. pick_task_fair()는 선택한 entity의 group_cfs_rq(se)로 내려가 다시 선택합니다. 모든 task를 하나의 전역 deadline 순서로 정렬하는 것이 아닙니다.

실행 중 entity는 tree 밖에 있을 수 있습니다. vruntime_eligible()이 curr && curr->on_rq를 따로 더하는 이유가 여기에 있습니다. tree의 노드 수만 세거나 weighted sum만 읽고 현재 task를 빠뜨리면 V 자체가 달라집니다. 반대로 put_prev_entity()는 아직 on_rq인 이전 entity를 tree로 돌려보냅니다. curr 포인터, tree membership, on_rq는 같은 뜻이 아닙니다.

4. 실제 코드로 확인하기

아래 코드는 사이트에 보존한 Linux v6.18.37 kernel/sched/fair.c에서 가져온 짧은 발췌입니다. 줄 번호와 함수 signature를 고정해 설명과 원문이 어긋나는지 다시 검사할 수 있게 했습니다.

가중치가 실제 시간을 가상 시간으로 바꾸는 곳 · fair.c 290–296

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

nice 0의 weight라면 실제 실행 시간과 가상 실행 시간이 같은 비율로 움직입니다. weight가 작을수록 같은 실제 시간을 실행했을 때 vruntime이 더 많이 증가하므로, 낮은 우선순위 task가 장부상 더 빨리 서비스를 소비한 것으로 기록됩니다.

나눗셈 없이 eligibility를 검사하는 곳 · fair.c 797–816

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_op(vruntime, "-", cfs_rq->zero_vruntime) * load;
}

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

개념식 V ≥ v_i를 그대로 나누면 정수 정밀도가 손실됩니다. 구현은 양변에 전체 weight를 곱한 형태를 유지해 비교합니다. 현재 실행 entity가 tree 밖에 있어도 on_rq라면 평균에 다시 더합니다.

두 조건으로 후보를 고르는 곳 · fair.c 995–1013, 1040–1078

/*
 * EEVDF selects the best runnable task from two criteria:
 *  1) the task must be eligible (must be owed service)
 *  2) from those tasks that meet 1), we select the one
 *     with the earliest virtual deadline.
 */
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);
	...
	if (se && entity_eligible(cfs_rq, se)) {
		best = se;
		goto found;
	}
	...
found:
	if (!best || (curr && entity_before(curr, best)))
		best = curr;

	return best;
}

tree는 deadline 순으로 정렬되고 subtree마다 최소 vruntime을 보조 정보로 둡니다. 왼쪽 subtree에 eligible entity가 없으면 그 구간을 통째로 건너뛸 수 있어 모든 task를 선형 순회하지 않습니다. protect가 참이고 현재 entity의 slice가 보호되는 경우에는 현재 entity가 유지될 수도 있습니다.

실행량을 누적하고 deadline을 갱신하는 곳 · fair.c 1281–1303

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	struct rq *rq = rq_of(cfs_rq);
	s64 delta_exec;
	bool resched;

	if (unlikely(!curr))
		return;

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

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

이 버전의 주석은 proxy execution 때문에 cfs_rq->curr가 실제로 CPU 위에서 실행 중인 rq->curr와 반드시 같은 task는 아니라고 경고합니다. scheduler를 고칠 때 current라는 이름만 보고 같은 객체라고 단정하면 accounting 오류를 만들 수 있습니다.

5. 숫자로 보는 nice와 deadline

설명을 단순하게 만들기 위해 task A의 weight를 1024(nice 0), task B의 weight를 335(nice 5)라고 하겠습니다. 두 task가 각각 실제 CPU 1 ms를 사용하면 calc_delta_fair()의 비율은 다음과 같습니다.

따라서 B가 낮은 weight인데도 실제 시간만 보고 A와 번갈아 1 ms씩 계속 실행시키면 지분이 맞지 않습니다. B의 vruntime과 virtual deadline이 더 빨리 앞으로 가므로 eligible 집합과 선택 순서가 조정됩니다. 단, 이 표는 wakeup placement, group scheduling, slice protection, capacity scaling을 생략한 한 단계 계산입니다.

같은 weight여도 최소 vruntime task가 선택되지 않는 예

세 task의 weight를 같게 놓고, 이미 만들어진 요청을 관찰합니다. A는 (v=0, d=3), B는 (v=1, d=2), C는 (v=2, d=4)입니다. V는 1이므로 A와 B가 eligible입니다. A의 vruntime이 가장 작지만, deadline이 더 이른 B를 고릅니다. 공정성을 위한 자격과 요청 지연을 위한 순서를 분리한 효과입니다.

1 ms는 설명을 위한 관찰 간격이며 커널 tick이나 slice가 항상 1 ms라는 뜻은 아닙니다. B가 request를 다 쓰면 update_deadline()은 vruntime + calc_delta_fair(slice, se)로 새 deadline을 만듭니다. A는 v가 3에 도달하지 않았으므로 d=3을 유지합니다. 매 선택마다 모든 deadline을 V 기준으로 다시 만드는 알고리즘으로 구현하면 이 결과를 재현할 수 없습니다.

5.1 pick_eevdf()의 분기를 끝까지 읽기

선택 원리를 이해한 다음에는 Linux가 그 앞에 붙인 빠른 경로를 읽어야 합니다. nr_queued는 group와 delayed entity 때문에 사용자가 생각하는 단순 runnable task 수와 같다고 가정할 수 없습니다. 아래는 함수의 실제 검사 순서이며 먼저 통과한 분기가 결과를 바꿉니다.

왼쪽 subtree를 통째로 생략해도 되는 이유

tree의 검색 키는 deadline이지만 eligibility는 vruntime으로 결정됩니다. 보조 정보 없이 deadline만 따라가면 ineligible 노드를 하나씩 확인해야 할 수 있습니다. 그래서 각 node에 subtree의 최소 vruntime을 저장합니다. min_vruntime > V이면 그 subtree에는 eligible entity가 없습니다. 최소값이 V 이하라면 적어도 하나가 존재합니다.

왼쪽 subtree가 eligible이면 먼저 그쪽으로 내려갑니다. 그 안의 모든 deadline은 현재 node보다 앞서므로 현재 node를 먼저 고를 이유가 없습니다. 왼쪽에 답이 없다면 현재 node를 검사하고, 그마저 ineligible일 때 오른쪽으로 이동합니다. rb-tree의 높이가 O(log n)이고 한 번에 한 경로만 내려가므로 선형 전수 검색이 필요하지 않습니다. 삽입·삭제 시 augmentation 갱신이 틀리면 가지치기가 올바른 후보를 버릴 수 있습니다.

짧은 요청이 계속 끼어드는 경우

protect_slice()는 vruntime < vprot를 검사합니다. 현재 entity도 eligible이어야 하고 호출자가 protect를 허용해야 조기 반환합니다. 무조건 현재 task의 전체 slice를 보장하는 것은 아닙니다. update_protect_slice()가 실행 큐의 최소 slice를 반영해 보호 끝을 줄일 수 있으며, 상위 scheduling class나 CPU 이동까지 차단하는 lock도 아닙니다. fairness, request latency, 잦은 선점 비용을 함께 다루는 정책 경계입니다.

5.2 잠들었다 깨어난 task의 장부는 어디에 놓이는가

sleep 중 wall-clock 시간이 흘렀다고 같은 양의 CPU 서비스를 적립해 주지는 않습니다. 중요한 것은 이전 경쟁 집합에서 남긴 lag와 새 집합에 들어갈 위치입니다. 서비스 lag는 w × (V-v)이지만 구현의 se->vlag는 weight를 곱하지 않은 가상 시간 차이를 보관합니다. 두 값을 같은 단위로 계산하면 placement가 틀어집니다.

보정 조건은 PLACE_LAG, nr_queued, se->vlag입니다. 그 뒤 rel_deadline이 있으면 상대 deadline을 새 vruntime에 더하고 일찍 반환합니다. 그렇지 않은 새 entity의 ENQUEUE_INITIAL 경로는 PLACE_DEADLINE_INITIAL이 켜져 있을 때 첫 virtual slice를 절반으로 줄입니다. fork 초기 배치와 기존 task의 wakeup을 같은 표 하나로 설명할 수 없는 이유입니다.

pick_next_entity()는 delayed entity를 정리한 직후 다시 참조하지 말라는 주석을 남깁니다. 로깅을 위해 dequeue 뒤에 task_of(se)를 읽는 것조차 lifetime 규칙을 깨뜨릴 수 있습니다. 필요한 진단 정보는 유효한 참조와 적절한 락이 있는 시점에 확보해야 합니다. 이는 알고리즘 설명을 실제 커널 수정으로 옮길 때 생기는 중요한 차이입니다.

6. 실무에서 깨뜨리면 안 되는 조건

• rq lock 범위: 이 함수들이 스스로 락을 잡는다고 가정하지 않습니다. 호출자는 해당 CPU runqueue의 락과 interrupt 상태를 scheduler 규약에 맞게 유지해야 합니다.
• entity와 cfs_rq의 소속: 다른 cfs_rq의 entity를 비교하거나 잘못된 계층에서 task_of()를 호출하면 group scheduling의 의미가 무너집니다.
• 현재 entity의 별도 취급: curr는 tree에서 빠져 있을 수 있지만 on_rq 상태로 평균과 선택에 참여합니다.
• 빈 큐 처리: pick_task_fair()는 nr_queued를 먼저 확인합니다. pick_eevdf()를 임의 위치에서 빈 큐에 호출하는 API로 보면 안 됩니다.
• delayed dequeue 후 포인터: pick_next_entity()는 sched_delayed entity를 dequeue한 뒤 다시 참조하지 말라고 명시하며 NULL을 반환합니다.
• clock과 accounting 순서: vruntime, PELT, bandwidth accounting은 서로 다른 갱신 지점을 가집니다. 한 필드만 직접 수정해 실험하면 나머지 통계와 불일치합니다.

7. 실행 중인 커널에서 무엇을 볼 수 있나

• 스케줄 전환: sudo perf sched record -- sleep 5 후 sudo perf sched timehist로 wakeup과 switch 지연을 시간순으로 봅니다.
• tracepoint: tracefs의 sched:sched_wakeup, sched:sched_switch, sched:sched_migrate_task를 함께 켜야 enqueue, CPU 이동, 실제 전환을 구분할 수 있습니다.
• runqueue 상태: 해당 빌드의 scheduler debugfs와 task별 /proc/<pid>/sched를 함께 확인합니다. mount, CONFIG_SCHED_DEBUG와 권한을 먼저 확인하고 과거 커널의 경로를 그대로 가정하지 않습니다.
• 기능 토글: /sys/kernel/debug/sched/features는 빌드와 커널 버전에 따라 항목이 다릅니다. 실험 전후 값을 반드시 함께 기록합니다.
• 재현 조건: CPU affinity, cgroup, nice, governor, IRQ 부하를 고정하지 않으면 EEVDF 효과와 CPU capacity 차이를 혼동하기 쉽습니다.

관찰 결과를 원인에 연결하는 순서

먼저 두 CPU-bound 프로세스를 같은 CPU에 묶고 nice만 달리하여 긴 구간의 task-clock을 비교합니다. 이상적인 두 task 모델에서는 nice 0과 nice 5의 비율이 1024:335에 접근하지만 cgroup 제한이나 RT task가 있으면 전체 CPU의 그 비율을 기대할 수 없습니다. 다음에는 한 task를 주기적으로 sleep/wakeup시키고 wakeup-to-run 분포를 비교합니다. 평균 throughput과 짧은 요청의 응답 지연은 서로 다른 관찰값입니다.

Linux 실험 환경에서 수집할 최소 정보 · 실행 예시, 결과는 미측정

uname -a
cat /proc/cmdline
taskset -pc <PID>
cat /proc/<PID>/cgroup
cat /proc/<PID>/sched
sudo perf sched record -a -- sleep 10
sudo perf sched timehist
sudo perf stat -p <PID> -e task-clock,context-switches,cpu-migrations -- sleep 10

record와 timehist는 같은 데이터 파일을 대상으로 사용합니다. CPU affinity와 nice 외의 조건을 고정한 뒤 한 변수만 바꿉니다. 기대 비율과 다르면 cgroup의 cpu.max·cpu.stat, CPU migration, IRQ 부하부터 확인합니다. 내부 후보 탈락 이유까지 입증하려면 관련 field를 동기화된 시점에 수집하는 별도 instrumentation이 필요합니다.

8. v6.6 설명을 그대로 가져오면 안 되는 이유

큰 개념이 같아도 함수 signature, 책임 위치, 필드 이름은 달라집니다. scheduler 글에서는 최신 커널도 대략 이럴 것이라는 설명보다 분석한 tag와 줄 좌표를 고정하는 것이 중요합니다.

9. 이 글이 설명하지 않는 범위

또한 EEVDF의 학술적 증명 전체를 재현하지 않습니다. 여기의 수식은 Linux 구현을 읽기 위한 최소 모델이며, upstream 코드가 사용하는 정수 산술, lag clamp, tree augmentation이 최종 동작을 결정합니다.

원문과 검증 범위

• 사이트에 보존한 Linux v6.18.37 kernel/sched/fair.c 원문
• 줄 번호가 붙은 원문 보기: pick_eevdf()
• Linux stable v6.18.37 fair.c
• Linux stable v6.18.37 struct cfs_rq
• Linux v6.6 update_deadline 비교 설명