EEVDF 스케쥴러란
EEVDF(Earliest Eligible Virtual Deadline First)는 리눅스 6.6부터 일반 태스크의 공정 스케줄링에서 기존 CFS(Completely Fair Scheduler)의 태스크 선택 방식을 대체하기 시작한 스케줄링 알고리즘이다.
CFS와 EEVDF는 모두 태스크의 가중치에 비례하여 CPU 시간을 공정하게 배분하는 것을 목표로 한다. 기존 CFS가 가상 런타임이 가장 작은 태스크를 중심으로 실행 순서를 결정했다면, EEVDF는 공정하게 받아야 할 CPU 시간과 실제로 받은 CPU 시간의 차이인 Lag로 실행 자격을 판단하고, 적격한 태스크 중 가상 데드라인이 가장 빠른 태스크를 선택한다.
Lag 추적 및 수식 계산
- 개념: Lag는 태스크가 공정하게 받아야 할 CPU 시간과 실제로 받은 CPU 시간의 차이를 의미한다.
- 저수준 작용: 공정성의 기준이 되는 가상 시간
V와 개별 태스크의 가상 런타임vruntime_i의 차이에 가중치w_i를 곱하여 표현한다.
아래 식에서 w_i는 nice 값이 0인 태스크의 가중치를 1로 정규화한 상대 가중치다. 변수의 _i는 i번째 태스크에 해당하는 값이라는 뜻이다.
Lag_i = (V - vruntime_i) * w_i
Lag_i > 0: 공정하게 받아야 할 시간보다 CPU를 덜 받은 상태다. 시스템이 해당 태스크에 CPU 시간을 빚지고 있다고 볼 수 있다.Lag_i = 0: 공정하게 받아야 할 CPU 시간과 실제로 받은 CPU 시간이 일치하는 상태다.Lag_i < 0: 공정하게 받아야 할 시간보다 CPU를 더 받은 상태다.
여기서 V는 해당 공정 실행 큐(runqueue)에서 관리하는 기준 가상 시간이며, 스케줄링 엔티티들의 가상 런타임을 가중 평균하여 계산한다.
적격성(Eligibility) 판정
- 개념: 현재 시점에 태스크가 CPU를 할당받을 자격이 있는지 판단하는 단계다.
- 저수준 작용: EEVDF의 기본 선택 규칙에서는 다음 조건을 만족하는 태스크를 실행 후보로 삼는다.
Lag_i >= 0
가중치 w_i는 양수이므로, 이 조건은 다음과 같다.
vruntime_i <= V
즉, 자신의 가상 런타임이 기준 가상 시간보다 작거나 같은 태스크가 적격한 태스크다.
공정 지분보다 CPU를 더 사용한 태스크는 Lag가 음수가 되어 선택 대상에서 제외된다. 이후 다른 태스크가 실행되면서 기준 가상 시간이 증가하면 다시 적격한 상태가 될 수 있다.
가상 데드라인(Virtual Deadline) 결정
- 개념: 적격한 태스크 중 가상 데드라인이 가장 빠른 태스크를 우선 실행한다.
- 저수준 작용: 태스크의 타임슬라이스
q_i를 가중치로 보정한 값을 가상 런타임에 더하여 가상 데드라인을 계산한다.
가상 데드라인을 D_i라고 하면 기본식은 다음과 같다.
D_i = vruntime_i + q_i / w_i
각 변수의 의미는 다음과 같다.
D_i: i번째 태스크의 가상 데드라인vruntime_i: 새로운 타임슬라이스의 데드라인을 설정하는 시점의 가상 런타임q_i: 해당 태스크의 타임슬라이스w_i: 해당 태스크의 정규화된 상대 가중치
이 식의 vruntime_i는 데드라인을 설정하는 시점의 값이다. 태스크가 실행되는 동안 가상 런타임이 증가한다고 해서, 데드라인도 매 순간 같은 양만큼 뒤로 밀리는 것은 아니다.
여기서 q_i는 한 번의 실행 요청에 해당하는 CPU 시간의 길이다. 태스크가 작업을 모두 끝내는 데 필요한 총시간을 예측한 값은 아니다.
지연 시간 제어
다른 조건이 같다면 타임슬라이스 q_i가 짧을수록 가상 데드라인이 앞당겨진다. 따라서 지연 시간에 민감한 태스크가 짧은 타임슬라이스를 사용하면, 적격한 태스크 사이에서 더 일찍 선택되어 응답성을 높일 수 있다.
다만 대화형 프로세스이거나 I/O 대기 후 깨어났다는 이유만으로 자동으로 매우 짧은 타임슬라이스를 요청하는 것은 아니다. 실제 선점 여부도 적격성, 가상 데드라인 비교, 커널의 선점 규칙 등에 따라 결정된다.
또한 이 데드라인은 실행 순서를 정하기 위한 가상 시간상의 기준이며, 특정 실제 시각까지 작업 완료를 보장하는 실시간 데드라인은 아니다.