← Documents Documentation/scheduler/sched-eevdf.rst GitHub 원문 ↗

Linux 6.18.37 · Scheduler

EEVDF fair scheduler

Lag로 eligibility를 판단하고 virtual deadline이 가장 이른 entity를 선택하는 EEVDF의 fair-share와 latency 모델을 설명합니다.

Source pathDocumentation/scheduler/sched-eevdf.rst
Source versionLinux v6.18.37
TranslationDUJINLABS 전문 번역 + 해설

요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.

1. 요약·해설

원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.

받아야 할 service와 실제 service의 차이

sched-eevdf.rst:1-18

EEVDF는 entity가 이상적인 weighted share로 받아야 했던 service와 실제 받은 service의 차이를 lag로 봅니다. Positive lag인 entity는 service가 부족해 eligible하고 negative lag이면 이미 앞서 있어 잠시 기다립니다.

Eligibility 조건이 없으면 작은 deadline을 반복 부여한 entity가 fair share를 넘어 실행될 수 있습니다. Lag는 장기 fairness 제약이고 deadline은 eligible 집합 안에서 latency 순서를 정합니다.

Eligible entity 중 earliest virtual deadline

sched-eevdf.rst:19-33

각 request에는 virtual start와 slice에서 계산한 virtual deadline이 있습니다. Scheduler는 lag가 허용하는 entity 중 deadline이 가장 이른 것을 선택합니다. 짧은 requested slice는 이른 deadline을 받아 latency-sensitive task가 빨리 응답할 수 있게 합니다.

Task가 sleep하며 runqueue를 떠날 때 lag를 즉시 버리면 sleep/wakeup으로 fairness를 조작할 수 있습니다. Linux는 deferred dequeue와 lag decay를 사용해 service debt와 credit을 보존하면서 장기 sleeper를 정리합니다.

Kernel trace에서 볼 값

sched-eevdf.rst:1-43
  • vruntime과 min_vruntime: virtual timeline 위치
  • vlag: eligibility를 결정하는 service deficit
  • slice와 virtual deadline: latency ordering
  • enqueue/dequeue flag: wakeup, migration과 delayed dequeue 이유

2. 영어 원문 전체

번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.

원문 전체 펼치기
1 ===============
2 EEVDF Scheduler
3 ===============
4
5 The "Earliest Eligible Virtual Deadline First" (EEVDF) was first introduced
6 in a scientific publication in 1995 [1]. The Linux kernel began
7 transitioning to EEVDF in version 6.6 (as a new option in 2024), moving
8 away from the earlier Completely Fair Scheduler (CFS) in favor of a version
9 of EEVDF proposed by Peter Zijlstra in 2023 [2-4]. More information
10 regarding CFS can be found in
11 Documentation/scheduler/sched-design-CFS.rst.
12
13 Similarly to CFS, EEVDF aims to distribute CPU time equally among all
14 runnable tasks with the same priority. To do so, it assigns a virtual run
15 time to each task, creating a "lag" value that can be used to determine
16 whether a task has received its fair share of CPU time. In this way, a task
17 with a positive lag is owed CPU time, while a negative lag means the task
18 has exceeded its portion. EEVDF picks tasks with lag greater or equal to
19 zero and calculates a virtual deadline (VD) for each, selecting the task
20 with the earliest VD to execute next. It's important to note that this
21 allows latency-sensitive tasks with shorter time slices to be prioritized,
22 which helps with their responsiveness.
23
24 There are ongoing discussions on how to manage lag, especially for sleeping
25 tasks; but at the time of writing EEVDF uses a "decaying" mechanism based
26 on virtual run time (VRT). This prevents tasks from exploiting the system
27 by sleeping briefly to reset their negative lag: when a task sleeps, it
28 remains on the run queue but marked for "deferred dequeue," allowing its
29 lag to decay over VRT. Hence, long-sleeping tasks eventually have their lag
30 reset. Finally, tasks can preempt others if their VD is earlier, and tasks
31 can request specific time slices using the new sched_setattr() system call,
32 which further facilitates the job of latency-sensitive applications.
33
34 REFERENCES
35 ==========
36
37 [1] https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564
38
39 [2] https://lore.kernel.org/lkml/a79014e6-ea83-b316-1e12-2ae056bda6fa@linux.vnet.ibm.com/
40
41 [3] https://lwn.net/Articles/969062/
42
43 [4] https://lwn.net/Articles/925371/
44

3. 한국어 전문 번역

영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.

EEVDF scheduler의 도입

1-12

Earliest Eligible Virtual Deadline First, 즉 EEVDF는 1995년 학술 논문에서 처음 소개되었다. Linux kernel은 6.6에서 EEVDF로 전환하기 시작했으며, 2024년에 새 option으로 도입해 기존 Completely Fair Scheduler에서 Peter Zijlstra가 2023년에 제안한 EEVDF 변형으로 이동했다. CFS에 관한 추가 설명은 Documentation/scheduler/sched-design-CFS.rst에 있다.

Lag와 virtual deadline을 이용한 선택

14-25

CFS와 마찬가지로 EEVDF는 우선순위가 같은 runnable task 모두에게 CPU 시간을 균등하게 분배하려 한다. 이를 위해 각 task에 virtual runtime을 부여하고, task가 공정한 몫의 CPU 시간을 받았는지를 판단할 수 있는 lag 값을 만든다.

Lag가 양수이면 해당 task가 CPU 시간을 더 받아야 한다는 뜻이고, 음수이면 자기 몫을 초과했다는 뜻이다. EEVDF는 lag가 0 이상인 eligible task를 고른 뒤 각 task의 virtual deadline, 즉 VD를 계산하고 VD가 가장 이른 task를 다음 실행 대상으로 선택한다.

이 방식에서는 짧은 time slice를 가진 latency-sensitive task가 우선될 수 있으므로 응답성을 높이는 데 도움이 된다.

Sleeping task의 lag와 preemption

27-43

특히 sleeping task의 lag를 어떻게 관리할지는 계속 논의 중이다. 이 문서가 작성된 시점의 EEVDF는 virtual runtime에 기반한 decay mechanism을 사용한다. Task가 잠깐 sleep해 음수 lag를 초기화하는 방식으로 scheduler를 악용하지 못하게 하기 위해서다.

Task가 sleep하면 run queue에 남아 있지만 deferred dequeue 상태로 표시되고, lag는 virtual runtime의 진행에 따라 감소한다. 따라서 오래 sleep한 task의 lag는 결국 초기화된다.

Task는 자신의 VD가 현재 실행 중인 task보다 이르면 그 task를 preempt할 수 있다. 또한 새 sched_setattr() system call을 통해 특정 time slice를 요청할 수 있어 latency-sensitive application을 더 잘 지원한다.

참고문헌: 1995년 EEVDF 논문, LKML EEVDF 논의, LWN의 EEVDF와 scheduler 관련 기사. 원문의 [1]부터 [4]까지 URL을 그대로 참조한다.