CFS

총 실행된 시간. vruntime가 가장 작은 프로세스를 실행시키는 것.
실행 요청을 한 프로세스의 vruntime과 이미 런큐에 등록된 프로세스들의 vruntime을 비교 한 후, Red-Black Tree에 삽입한다.

선점 스케줄링

선점 스케줄링은

1. 인터럽트 핸들링 후
2. 시스템 콜 핸들링 후

이 두가지 상황에서만 시작한다.

왜 시스템 콜 이후 선점 스케줄링?

① 프로세스들의 우선순위 판도가 방금 막 바뀐 시점이면서,

② 커널 코드가 다 끝나서 프로세스를 교체해도 하드웨어적으로 가장 안전한 타이밍이자,

③ 유저 프로세스가 워낙 자주 호출해 주니 공짜로 스케줄링 기회를 얻을 수 있는 최적의 길목이기 때문

EEVDF

Overview

CFS는 vruntime만을 기준으로, CPU scheduling을 수행한다.
즉 CPU Fairness만을 기준으로 수행한다. deadline 에 대한 개념이 없기 때문에 빨리 수행되어야하는 태스크에 대한 동작이 없음.

Earliest Eligible Virtual Deadline First (EEVDF) 스케줄링 알고리즘은,

1. virtual run time 을 기준으로 하는 "Lag" 값을 기준으로 CPU Fairness를 보장하고

Lag = (태스크가 받아야 할 공평한 CPU 시간) - (태스크가 실제로 사용한 CPU 시간)

음수면 CPU를 초과해서 사용한것.

Lag값이 0이상인 애들을 스케줄링 후보로 두고, virtual Deadline을 계산한다.

2. virtual Deadline(VD)가 가장 적은 것을 스케줄링한다.

Task의 Eligible 자격 확인

kernel/sched/fair.c

A task is eligible if its vruntime is at or behind the weighted average vruntime of the runqueue.

해당 런큐의 평균 런타임보다 적거나 같다면 eligible.

$(vruntime - min\_vruntime) \le \frac{avg}{load}$

절대적인 vruntime을 고려하는것이 아니라, 해당 런큐에서 가장 작은 vruntime 값을 빼주어, 상대적인 vruntime을 구한다.

각 가중치를 반영하기 위해서 load 값을 나눠줘야한다. 하지만, 나누기 연산은 오래 걸리니까...양변에 load를 곱하는것으로 변경시킴.

virtual Deadline

kernel/sched/fair.c

1023 줄이 deadline을 설정하는 부분임.

This means: "I want to run for slice worth of virtual time starting from my current vruntime." The deadline is the end of that window.

A task with a short slice gets an early deadline and runs sooner. A task with a long slice gets a later deadline and may wait.

내가 가지고 있는 vruntime으로부터 slice 만큼 실행하고 싶은데....그 끝을 deadline으로 삼는다. 그 deadline이 가장 작은 놈을 우선적으로 실행한다.

즉, 빠르게 끝날 수 있는 놈 부터 실행시킨다.

$\text{Virtual Deadline (VD)} = \text{현재 내 vruntime} + \text{내가 요청한 Slice}$

vlag

average - current vruntime

$\text{새로운 } vruntime = min\_vruntime - vlag$

커널은 깨어나는 태스크에게 현재 min_vruntime - 잔여 vlag 라는 공식을 적용함으로써,

1. 오래 잔 놈은 vlag만큼 주소를 낮춰줘서 빨리 구제(Starving 방지)하고,

2. 잠깐 잔 놈은 마이너스 vlag로 주소를 높여버려서 독점을 방지(Bursting 방지)하는 완벽한 밸런싱을 성립시키는 것

CFS의 경우,
$\text{새로운 } vruntime = \max(se\rightarrow vruntime, \ min\_vruntime - \text{Latency\_Target})$

이기 때문에, 잠깐 잔놈도 계속 min runtime을 가질 수 있었다. 하지만, EEVDF 에서는 vlag사용을 통해 잠들기전 runtime을 고려하는것.

Selection

The algorithm walks the RB-tree, finds all eligible tasks, and returns the one with the earliest (smallest) deadline. Non-eligible tasks are skipped. The tree traversal is pruned using cached min_deadline subtree values for efficiency.

deadline 을 기준으로 RB Tree로 select

CFS와의 비교

CFS: vruntime 기준 정렬이라 맨 왼쪽 구석탱이 포인터만 가져오면 끝 ($O(1)$ 컴포넌트 탐색).

EEVDF: vruntime으로 정렬된 트리 안에서 엉뚱한 곳에 숨은 최적의 마감일($VD$)을 찾아내야 함.

결론: 이를 해결하기 위해 각 부모 노드에 자식들의 마감일 힌트(min_deadline)를 적어두는 확장형 RB-Tree를 도입했고, 이 덕분에 최악의 상황에서도 전체 노드를 뒤지지 않고 트리의 높이만큼만 스캔하는 $O(\log n)$을 사수해 낸 것입니다.