요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
Runnable entity RB-tree와 min_vruntime
sched-design-CFS.rst:57-92Runqueue는 runnable sched_entity를 vruntime 순으로 RB-tree에 저장합니다. 왼쪽 entity가 가장 뒤처진 후보이고 min_vruntime은 rq가 지금까지 진행한 virtual timeline의 단조 기준점입니다.
Wakeup entity의 old vruntime을 그대로 쓰면 오래 sleep한 task가 무한 credit을 얻을 수 있으므로 현재 min_vruntime 근처에 placement합니다. Migration에서는 source와 destination rq의 virtual timeline 차이를 보정합니다.
Granularity, sleeper와 SMP balance
sched-design-CFS.rst:93-150매우 작은 vruntime 차이마다 context switch하면 fairness는 정교해지지만 cache와 switch overhead가 커집니다. Target latency와 minimum granularity가 실행 slice의 실용적 하한을 만들고 wakeup preemption granularity가 새 task의 즉시 선점을 제한합니다.
SCHED_NORMAL과 SCHED_BATCH는 fair class를 사용하지만 interactive wakeup 기대가 다릅니다. SCHED_IDLE은 매우 낮은 fair weight를 제공하며 CPU idle task와는 다른 policy입니다.
Scheduling class chain과 group entity
sched-design-CFS.rst:151-256Scheduler core는 stop, deadline, RT, fair, idle 같은 class를 priority chain으로 질의합니다. Fair class 안에서는 task와 cgroup task group이 모두 sched_entity로 표현될 수 있습니다.
Group scheduling은 root에서 child cfs_rq로 내려가는 계층마다 weight share를 적용합니다. Task nice 값만 보지 말고 ancestor cgroup weight, quota와 CPU topology를 함께 봐야 실제 runtime share를 이해할 수 있습니다.
현재 Linux fair scheduler의 선택 logic은 EEVDF로 발전했습니다. 이 문서는 vruntime과 CFS runqueue의 기반을 설명하며 실제 pick logic은 sched-eevdf 문서를 함께 봐야 합니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
.. _sched_design_CFS:
=============
CFS Scheduler
=============
1. OVERVIEW
============
CFS stands for "Completely Fair Scheduler," and is the "desktop" process
scheduler implemented by Ingo Molnar and merged in Linux 2.6.23. When
originally merged, it was the replacement for the previous vanilla
scheduler's SCHED_OTHER interactivity code. Nowadays, CFS is making room
for EEVDF, for which documentation can be found in
Documentation/scheduler/sched-eevdf.rst.
80% of CFS's design can be summed up in a single sentence: CFS basically models
an "ideal, precise multi-tasking CPU" on real hardware.
"Ideal multi-tasking CPU" is a (non-existent :-)) CPU that has 100% physical
power and which can run each task at precise equal speed, in parallel, each at
1/nr_running speed. For example: if there are 2 tasks running, then it runs
each at 50% physical power --- i.e., actually in parallel.
On real hardware, we can run only a single task at once, so we have to
introduce the concept of "virtual runtime." The virtual runtime of a task
specifies when its next timeslice would start execution on the ideal
multi-tasking CPU described above. In practice, the virtual runtime of a task
is its actual runtime normalized to the total number of running tasks.
2. FEW IMPLEMENTATION DETAILS
==============================
In CFS the virtual runtime is expressed and tracked via the per-task
p->se.vruntime (nanosec-unit) value. This way, it's possible to accurately
timestamp and measure the "expected CPU time" a task should have gotten.
Small detail: on "ideal" hardware, at any time all tasks would have the same
p->se.vruntime value --- i.e., tasks would execute simultaneously and no task
would ever get "out of balance" from the "ideal" share of CPU time.
CFS's task picking logic is based on this p->se.vruntime value and it is thus
very simple: it always tries to run the task with the smallest p->se.vruntime
value (i.e., the task which executed least so far). CFS always tries to split
up CPU time between runnable tasks as close to "ideal multitasking hardware" as
possible.
Most of the rest of CFS's design just falls out of this really simple concept,
with a few add-on embellishments like nice levels, multiprocessing and various
algorithm variants to recognize sleepers.
3. THE RBTREE
==============
CFS's design is quite radical: it does not use the old data structures for the
runqueues, but it uses a time-ordered rbtree to build a "timeline" of future
task execution, and thus has no "array switch" artifacts (by which both the
previous vanilla scheduler and RSDL/SD are affected).
CFS also maintains the rq->cfs.min_vruntime value, which is a monotonic
increasing value tracking the smallest vruntime among all tasks in the
runqueue. The total amount of work done by the system is tracked using
min_vruntime; that value is used to place newly activated entities on the left
side of the tree as much as possible.
The total number of running tasks in the runqueue is accounted through the
rq->cfs.load value, which is the sum of the weights of the tasks queued on the
runqueue.
CFS maintains a time-ordered rbtree, where all runnable tasks are sorted by the
p->se.vruntime key. CFS picks the "leftmost" task from this tree and sticks to it.
As the system progresses forwards, the executed tasks are put into the tree
more and more to the right --- slowly but surely giving a chance for every task
to become the "leftmost task" and thus get on the CPU within a deterministic
amount of time.
Summing up, CFS works like this: it runs a task a bit, and when the task
schedules (or a scheduler tick happens) the task's CPU usage is "accounted
for": the (small) time it just spent using the physical CPU is added to
p->se.vruntime. Once p->se.vruntime gets high enough so that another task
becomes the "leftmost task" of the time-ordered rbtree it maintains (plus a
small amount of "granularity" distance relative to the leftmost task so that we
do not over-schedule tasks and trash the cache), then the new leftmost task is
picked and the current task is preempted.
4. SOME FEATURES OF CFS
========================
CFS uses nanosecond granularity accounting and does not rely on any jiffies or
other HZ detail. Thus the CFS scheduler has no notion of "timeslices" in the
way the previous scheduler had, and has no heuristics whatsoever. There is
only one central tunable:
/sys/kernel/debug/sched/base_slice_ns
which can be used to tune the scheduler from "desktop" (i.e., low latencies) to
"server" (i.e., good batching) workloads. It defaults to a setting suitable
for desktop workloads. SCHED_BATCH is handled by the CFS scheduler module too.
In case CONFIG_HZ results in base_slice_ns < TICK_NSEC, the value of
base_slice_ns will have little to no impact on the workloads.
Due to its design, the CFS scheduler is not prone to any of the "attacks" that
exist today against the heuristics of the stock scheduler: fiftyp.c, thud.c,
chew.c, ring-test.c, massive_intr.c all work fine and do not impact
interactivity and produce the expected behavior.
The CFS scheduler has a much stronger handling of nice levels and SCHED_BATCH
than the previous vanilla scheduler: both types of workloads are isolated much
more aggressively.
SMP load-balancing has been reworked/sanitized: the runqueue-walking
assumptions are gone from the load-balancing code now, and iterators of the
scheduling modules are used. The balancing code got quite a bit simpler as a
result.
5. Scheduling policies
======================
CFS implements three scheduling policies:
- SCHED_NORMAL (traditionally called SCHED_OTHER): The scheduling
policy that is used for regular tasks.
- SCHED_BATCH: Does not preempt nearly as often as regular tasks
would, thereby allowing tasks to run longer and make better use of
caches but at the cost of interactivity. This is well suited for
batch jobs.
- SCHED_IDLE: This is even weaker than nice 19, but its not a true
idle timer scheduler in order to avoid to get into priority
inversion problems which would deadlock the machine.
SCHED_FIFO/_RR are implemented in sched/rt.c and are as specified by
POSIX.
The command chrt from util-linux-ng 2.13.1.1 can set all of these except
SCHED_IDLE.
6. SCHEDULING CLASSES
======================
The new CFS scheduler has been designed in such a way to introduce "Scheduling
Classes," an extensible hierarchy of scheduler modules. These modules
encapsulate scheduling policy details and are handled by the scheduler core
without the core code assuming too much about them.
sched/fair.c implements the CFS scheduler described above.
sched/rt.c implements SCHED_FIFO and SCHED_RR semantics, in a simpler way than
the previous vanilla scheduler did. It uses 100 runqueues (for all 100 RT
priority levels, instead of 140 in the previous scheduler) and it needs no
expired array.
Scheduling classes are implemented through the sched_class structure, which
contains hooks to functions that must be called whenever an interesting event
occurs.
This is the (partial) list of the hooks:
- enqueue_task(...)
Called when a task enters a runnable state.
It puts the scheduling entity (task) into the red-black tree and
increments the nr_running variable.
- dequeue_task(...)
When a task is no longer runnable, this function is called to keep the
corresponding scheduling entity out of the red-black tree. It decrements
the nr_running variable.
- yield_task(...)
This function is basically just a dequeue followed by an enqueue, unless the
compat_yield sysctl is turned on; in that case, it places the scheduling
entity at the right-most end of the red-black tree.
- wakeup_preempt(...)
This function checks if a task that entered the runnable state should
preempt the currently running task.
- pick_next_task(...)
This function chooses the most appropriate task eligible to run next.
- set_next_task(...)
This function is called when a task changes its scheduling class, changes
its task group or is scheduled.
- task_tick(...)
This function is mostly called from time tick functions; it might lead to
process switch. This drives the running preemption.
7. GROUP SCHEDULER EXTENSIONS TO CFS
=====================================
Normally, the scheduler operates on individual tasks and strives to provide
fair CPU time to each task. Sometimes, it may be desirable to group tasks and
provide fair CPU time to each such task group. For example, it may be
desirable to first provide fair CPU time to each user on the system and then to
each task belonging to a user.
CONFIG_CGROUP_SCHED strives to achieve exactly that. It lets tasks to be
grouped and divides CPU time fairly among such groups.
CONFIG_RT_GROUP_SCHED permits to group real-time (i.e., SCHED_FIFO and
SCHED_RR) tasks.
CONFIG_FAIR_GROUP_SCHED permits to group CFS (i.e., SCHED_NORMAL and
SCHED_BATCH) tasks.
These options need CONFIG_CGROUPS to be defined, and let the administrator
create arbitrary groups of tasks, using the "cgroup" pseudo filesystem. See
Documentation/admin-guide/cgroup-v1/cgroups.rst for more information about this filesystem.
When CONFIG_FAIR_GROUP_SCHED is defined, a "cpu.shares" file is created for each
group created using the pseudo filesystem. See example steps below to create
task groups and modify their CPU share using the "cgroups" pseudo filesystem::
# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu
# mkdir multimedia # create "multimedia" group of tasks
# mkdir browser # create "browser" group of tasks
# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group
# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares
# firefox & # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks
# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
CFS 개요와 이상적인 다중 작업 CPU
1-30CFS는 Completely Fair Scheduler의 약자다. Ingo Molnar가 구현했으며 Linux 2.6.23에 merge된 일반 “desktop” process scheduler다. 처음 merge될 때에는 이전 기본 scheduler의 SCHED_OTHER interactivity code를 대체했다. 현재 CFS는 EEVDF에 자리를 내주고 있으며 EEVDF는 Documentation/scheduler/sched-eevdf.rst에서 설명한다.
CFS 설계의 80%는 한 문장으로 요약할 수 있다. 실제 hardware 위에서 “이상적이고 정밀한 multi-tasking CPU”를 모형화한다.
이상적인 multi-tasking CPU는 현실에는 존재하지 않지만, 전체 physical power 100%를 runnable task 수로 정확히 나누어 모든 task를 동시에 같은 속도로 실행한다고 가정한 CPU다. 예를 들어 실행 중인 task가 두 개라면 각 task를 physical power의 50%로 실제 병렬 실행한다.
실제 단일 CPU에서는 한 순간에 task 하나만 실행할 수 있으므로 virtual runtime이라는 개념이 필요하다. Task의 virtual runtime은 이상적인 multi-tasking CPU에서 그 task의 다음 time slice가 언제 시작될지를 나타낸다. 실제 구현에서는 task의 실제 실행 시간을 전체 runnable task 수에 맞추어 정규화한 값이다.
p->se.vruntime과 task 선택
34-53CFS는 task마다 p->se.vruntime 값을 나노초 단위로 저장해 virtual runtime을 표현하고 추적한다. 이를 통해 task가 받아야 했던 “예상 CPU 시간”을 정확히 timestamp하고 측정할 수 있다.
이상적인 hardware에서는 어느 순간이든 모든 task의 p->se.vruntime이 같다. 모든 task가 동시에 실행되므로 어떤 task도 이상적인 CPU share에서 벗어나 불균형해지지 않는다.
CFS의 task 선택은 이 값만 보면 단순하다. 항상 p->se.vruntime이 가장 작은 task, 즉 지금까지 가장 적게 실행된 task를 실행하려 한다. Runnable task 사이의 CPU 시간을 이상적인 multitasking hardware에 최대한 가깝게 나누는 것이다.
CFS 설계의 나머지는 대부분 이 개념에서 자연스럽게 나온다. Nice level, multiprocessing, sleeper를 인식하기 위한 여러 algorithm variant 같은 기능이 그 위에 더해진다.
시간순 red-black tree
57-89CFS는 기존 runqueue data structure를 사용하지 않는다. 미래 task 실행의 timeline을 만들기 위해 시간순 red-black tree를 사용한다. 따라서 이전 기본 scheduler와 RSDL/SD에 있던 “array switch” artifact가 없다.
rq->cfs.min_vruntime은 runqueue에 있는 task 가운데 가장 작은 vruntime을 추적하는 단조 증가 값이다. System이 지금까지 수행한 전체 작업량을 min_vruntime으로 추적하며, 새로 활성화된 entity를 가능한 한 tree의 왼쪽에 배치할 때 이 값을 사용한다.
Runqueue에서 실행 중인 task의 전체 load는 rq->cfs.load로 계산한다. 이 값은 runqueue에 들어 있는 task weight의 합이다.
모든 runnable task는 p->se.vruntime을 key로 하여 시간순 red-black tree에 정렬된다. CFS는 tree에서 가장 왼쪽 task를 골라 실행한다. 실행한 task의 vruntime이 늘수록 tree의 오른쪽으로 이동하므로 모든 task가 차례로 leftmost task가 되어 제한된 시간 안에 CPU를 받을 기회를 얻는다.
Task가 잠시 실행한 뒤 schedule하거나 scheduler tick이 발생하면 방금 physical CPU를 사용한 짧은 시간을 p->se.vruntime에 더해 CPU 사용량을 accounting한다. 현재 task의 vruntime이 충분히 증가해 다른 task가 leftmost가 되고, cache를 훼손할 정도의 과도한 scheduling을 피하기 위한 작은 granularity 거리까지 충족하면 새 leftmost task를 선택하고 현재 task를 preempt한다.
CFS의 주요 특성
93-122CFS는 나노초 단위 accounting을 사용하며 jiffies나 다른 HZ 세부 사항에 의존하지 않는다. 이전 scheduler와 같은 의미의 고정 “timeslice” 개념이나 heuristic도 없다. 중심 조정값은 하나다.
/sys/kernel/debug/sched/base_slice_nsbase_slice_ns를 조절하면 scheduler를 낮은 latency가 중요한 desktop workload와 좋은 batching이 중요한 server workload 사이에서 조정할 수 있다. 기본값은 desktop workload에 적합하다. SCHED_BATCH도 CFS scheduler module이 처리한다.
CONFIG_HZ 설정 때문에 base_slice_ns가 TICK_NSEC보다 작아지면 이 값은 workload에 거의 영향을 주지 않는다.
설계상 CFS는 이전 기본 scheduler의 heuristic을 겨냥한 fiftyp.c, thud.c, chew.c, ring-test.c, massive_intr.c 같은 공격에 취약하지 않다. 이 workload들은 interactivity를 훼손하지 않고 예상대로 동작한다.
Nice level과 SCHED_BATCH 처리도 이전 scheduler보다 강해 두 종류의 workload를 훨씬 적극적으로 격리한다. SMP load balancing은 runqueue를 직접 순회한다는 가정을 없애고 scheduling module의 iterator를 사용하도록 정리되어 balancing code도 단순해졌다.
CFS가 구현하는 scheduling policy
126-147| policy | 동작 |
|---|---|
| SCHED_NORMAL | 전통적으로 SCHED_OTHER라고 불렀으며 일반 task에 사용하는 policy |
| SCHED_BATCH | 일반 task보다 훨씬 드물게 preempt하여 task를 오래 실행하고 cache를 더 잘 활용한다. Interactivity를 희생하므로 batch job에 적합하다. |
| SCHED_IDLE | nice 19보다도 약하지만 priority inversion으로 system이 deadlock되는 일을 피하기 위해 진정한 idle timer scheduler로 구현하지는 않는다. |
SCHED_FIFO와 SCHED_RR은 sched/rt.c에서 POSIX 명세에 따라 구현한다. util-linux-ng 2.13.1.1의 chrt command는 SCHED_IDLE을 제외한 policy를 설정할 수 있다.
Scheduling class 구조
151-168CFS는 확장 가능한 scheduler module 계층인 scheduling class를 도입하도록 설계되었다. 각 module은 scheduling policy의 세부 사항을 캡슐화한다. Scheduler core는 class 내부를 과도하게 가정하지 않고 이 module을 다룬다.
sched/fair.c는 앞에서 설명한 CFS를 구현한다. sched/rt.c는 SCHED_FIFO와 SCHED_RR 의미를 이전 기본 scheduler보다 단순하게 구현한다. 100개 RT priority level 각각에 하나씩 총 100개 runqueue를 사용하며, 이전 scheduler의 140개와 달리 expired array가 필요 없다.
Scheduling class는 sched_class structure로 구현한다. 이 structure는 scheduling과 관련된 event가 발생할 때 호출해야 하는 function hook을 담는다.
sched_class의 주요 hook
170-207| hook | 호출 시점과 역할 |
|---|---|
| enqueue_task(...) | task가 runnable state로 들어올 때 scheduling entity를 red-black tree에 넣고 nr_running을 증가시킨다. |
| dequeue_task(...) | task가 더 이상 runnable하지 않을 때 entity를 red-black tree에서 제거하고 nr_running을 감소시킨다. |
| yield_task(...) | 기본적으로 dequeue 후 enqueue한다. compat_yield sysctl이 켜져 있으면 entity를 red-black tree의 가장 오른쪽에 배치한다. |
| wakeup_preempt(...) | 새로 runnable state가 된 task가 현재 실행 중인 task를 preempt해야 하는지 검사한다. |
| pick_next_task(...) | 다음에 실행할 수 있는 task 가운데 가장 적합한 task를 선택한다. |
| set_next_task(...) | task의 scheduling class나 task group이 바뀌거나 task가 실제로 schedule될 때 호출한다. |
| task_tick(...) | 주로 time tick function에서 호출하며 process switch를 일으킬 수 있다. 실행 중인 task의 preemption을 구동한다. |
CFS group scheduler 확장
212-236일반적으로 scheduler는 개별 task를 대상으로 각 task에 공정한 CPU 시간을 제공한다. 경우에 따라 task를 묶고 각 task group에 공정한 CPU 시간을 제공해야 할 수 있다. 예를 들어 system의 각 user에게 먼저 CPU 시간을 공정하게 나누고, 다시 user에 속한 각 task 사이에 나눌 수 있다.
CONFIG_CGROUP_SCHED는 task를 group으로 묶고 group 사이에 CPU 시간을 공정하게 나누는 기능을 제공한다. CONFIG_RT_GROUP_SCHED는 SCHED_FIFO와 SCHED_RR 같은 real-time task의 grouping을 허용한다. CONFIG_FAIR_GROUP_SCHED는 SCHED_NORMAL과 SCHED_BATCH 같은 CFS task의 grouping을 허용한다.
이 option들은 CONFIG_CGROUPS가 필요하다. Administrator는 cgroup pseudo filesystem을 사용하여 원하는 task group을 만들 수 있다. 자세한 내용은 Documentation/admin-guide/cgroup-v1/cgroups.rst를 참조한다.
CONFIG_FAIR_GROUP_SCHED를 정의하면 pseudo filesystem으로 만든 각 group에 cpu.shares file이 생성된다.
cgroup v1에서 CPU share 설정 예
237-256# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu
# mkdir multimedia # "multimedia" task group 생성
# mkdir browser # "browser" task group 생성
# multimedia group이 browser group보다 두 배의 CPU bandwidth를 받도록 설정
# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares
# firefox를 실행하고 browser group으로 이동
# firefox &
# echo <firefox_pid> > browser/tasks
# gmplayer 또는 원하는 movie player를 실행한 뒤 multimedia group으로 이동
# echo <movie_player_pid> > multimedia/tasks
이상적인 multitasking CPU를 근사한다
sched-design-CFS.rst:4-56이상적인 fair CPU는 runnable task 모두를 동시에 같은 속도로 실행합니다. 실제 CPU는 한 task씩만 실행하므로 CFS는 각 sched_entity가 이상적인 share보다 얼마나 앞서거나 뒤처졌는지를 virtual runtime으로 기록합니다.
실제 실행 시간은 nice weight로 정규화되어 높은 weight entity의 vruntime이 더 천천히 증가합니다. 따라서 같은 wall time을 실행해도 높은 priority entity는 덜 앞서간 것으로 계산되어 더 많은 CPU share를 얻습니다.