리눅스 6.6부터 CFS를 대체한 EEVDF 스케줄러의 vruntime/eligible time/deadline 같은 개념은 이 블로그의 이전 글에서 다뤘다. 이 글은 그 개념이 실제로 어떤 구조체와 함수로 구현되어 있는지, kernel/sched/fair.c(6.18 기준) 소스를 직접 따라가며 확인한다. 그리고 nice 값에 따라 vruntime 누적 속도가 실제로 달라지는지 두 프로세스를 같은 코어에 묶어 CPU 점유율로 검증한다.
핵심 자료구조: sched_entity와 cfs_rq
태스크 하나의 스케줄링 상태는 struct sched_entity에 담긴다.
struct sched_entity {
struct load_weight load;
struct rb_node run_node;
u64 deadline;
u64 min_vruntime;
u64 min_slice;
u64 max_slice;
u64 exec_start;
u64 sum_exec_runtime;
u64 prev_sum_exec_runtime;
u64 vruntime;
union {
s64 vlag; /* !on_rq일 때 */
u64 vprot; /* cfs_rq->curr == se일 때 */
};
u64 slice;
...
};vruntime은 누적 가상 실행 시간, deadline은 EEVDF가 태스크를 고를 기준이 되는 가상 데드라인이다. 이 엔티티들을 모아두는 실행 큐가 cfs_rq다.
struct cfs_rq {
struct load_weight load;
unsigned int nr_queued;
s64 sum_w_vruntime;
u64 sum_weight;
u64 zero_vruntime;
struct rb_root_cached tasks_timeline;
struct sched_entity *curr;
struct sched_entity *next;
...
};tasks_timeline이 실제 엔티티들을 담는 레드블랙 트리다. 트리 키는 vruntime(정확히는 deadline 비교)이라, 왼쪽으로 갈수록 우선순위가 높은 태스크가 위치한다.
vruntime 갱신과 다음 태스크 선택
태스크가 CPU를 쓰는 동안 update_curr()가 매 틱마다 vruntime을 누적시킨다.
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
s64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = update_se(rq_of(cfs_rq), curr);
if (unlikely(delta_exec <= 0))
return;
curr->vruntime += calc_delta_fair(delta_exec, curr);
resched = update_deadline(cfs_rq, curr);
...
}calc_delta_fair()가 실제 경과 시간을 load.weight로 나눠 가상 시간으로 환산한다 — 가중치가 낮은(= nice 값이 큰) 태스크일수록 vruntime이 더 빠르게 늘어나 우선순위가 빨리 떨어진다. 큐에서 다음에 실행할 엔티티는 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)
return curr && curr->on_rq ? curr : se;
if (curr && (!curr->on_rq || !entity_eligible(cfs_rq, curr)))
curr = NULL;
/* 가장 왼쪽(가장 이른 deadline) 엔티티가 eligible하면 바로 선택 */
if (se && entity_eligible(cfs_rq, se)) {
best = se;
goto found;
}
/* eligible하지 않으면 트리를 내려가며 조건을 만족하는 노드를 찾는다 */
while (node) {
struct rb_node *left = node->rb_left;
if (left && vruntime_eligible(cfs_rq, __node_2_se(left)->min_vruntime)) {
node = left;
continue;
}
se = __node_2_se(node);
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;
}entity_eligible()은 태스크의 vruntime이 큐 평균(zero_vruntime) 대비 아직 “빚”을 지지 않은 상태인지를 판정한다. 즉 EEVDF는 “가장 이른 deadline” 중에서도 “아직 자기 몫을 다 쓰지 않은” 태스크만 고른다.
실전: nice 값과 실제 CPU 점유율
같은 CPU 코어에 nice 0과 nice 15인 CPU 바운드 프로세스를 동시에 묶어 실제 점유율 차이를 측정했다.
#!/bin/bash
end=$((SECONDS+5))
x=0
while [ $SECONDS -lt $end ]; do x=$((x+1)); donetaskset -c 0 nice -n 0 ./busy.sh &
pid0=$!
taskset -c 0 nice -n 15 ./busy.sh &
pid15=$!
sleep 2
ps -o pid,ni,pcpu,time -p $pid0,$pid15 PID NI %CPU TIME
3746 0 96.5 00:00:01
3747 15 3.5 00:00:00같은 코어를 두고 경쟁했는데도 nice 0 프로세스가 96.5%, nice 15 프로세스가 3.5%를 가져갔다. nice 15는 load.weight가 nice 0 대비 훨씬 작아 calc_delta_fair()에서 vruntime이 그만큼 빠르게 증가하고, pick_eevdf()가 매번 더 작은 vruntime(더 이른 deadline)을 가진 nice 0 쪽을 고르기 때문이다.
주의사항
- 이 글의 소스는 로컬에 클론된 6.18.38 커널 트리 기준이다.
zero_vruntime같은 필드명은 EEVDF 이전 CFS 시절의min_vruntime에서 이름이 바뀐 것으로, 커널 버전에 따라 필드명이 다를 수 있다. - nice 값과
load.weight의 정확한 대응표는kernel/sched/core.c의sched_prio_to_weight[]에 있다. nice 0 = 1024이고 nice가 1 증가할 때마다 대략 10%씩 줄어드는 지수 스케일이다. - 위 실험은 CFQ 급 부하나 실시간 스케줄링 클래스(SCHED_FIFO/RR)와는 무관하다. SCHED_FIFO/RR 태스크는 아예 다른 스케줄링 클래스(
rt_rq)를 쓰므로 vruntime 기반 공정성 로직이 적용되지 않는다. - 이번 실험은 코어 1개에 강제로 묶어 경쟁을 인위적으로 만든 것이다. 코어가 남아도는 상황이라면 두 프로세스가 서로 다른 코어에서 각각 100%를 쓰므로 점유율 차이가 드러나지 않는다.
마무리
EEVDF의 eligible time/deadline 개념은 결국 sched_entity의 몇 개 필드와 cfs_rq의 레드블랙 트리, 그리고 update_curr()/pick_eevdf() 두 함수로 구현된다. nice 값 하나가 어떻게 실제 CPU 점유율 차이로 이어지는지도 같은 코어에 묶어 직접 확인했다. 다음에 스케줄링 관련 버그를 만나면 /proc/[pid]/sched나 chrt로 실제 값을 확인하는 것부터 시작하면 된다.