요약·해설과 원문, 전문 번역을 서로 분리했습니다. API 이름, symbol, source path는 원문 표기를 사용합니다.
1. 요약·해설
원문의 핵심 논리와 kernel programming 관점의 보충 설명입니다. 아래의 전문 번역과는 별도로 작성했습니다.
domain을 구현할 때 지켜야 할 불변식
sched-domains.rst:55-81- child span은 parent span의 부분집합이어야 하며 최상위 domain은 partition을 덮어야 합니다.
- 같은 level의 group은 domain span을 빠짐없이 덮고 겹침 규칙을 지켜야 합니다.
- SD_* flag는 topology 특성과 balancing 정책을 연결하므로 단순히 성능 실험값으로 켜면 안 됩니다.
- hotplug와 cpuset partition 변경 시 domain을 재구성하므로 RCU lifetime과 per-CPU pointer 교체 순서를 지켜야 합니다.
2. 영어 원문 전체
번역 기준이 된 Linux v6.18.37 원문입니다. 줄 번호는 이 버전의 파일 좌표입니다.
원문 전체 펼치기
=================
Scheduler Domains
=================
Each CPU has a "base" scheduling domain (struct sched_domain). The domain
hierarchy is built from these base domains via the ->parent pointer. ->parent
MUST be NULL terminated, and domain structures should be per-CPU as they are
locklessly updated.
Each scheduling domain spans a number of CPUs (stored in the ->span field).
A domain's span MUST be a superset of it child's span (this restriction could
be relaxed if the need arises), and a base domain for CPU i MUST span at least
i. The top domain for each CPU will generally span all CPUs in the system
although strictly it doesn't have to, but this could lead to a case where some
CPUs will never be given tasks to run unless the CPUs allowed mask is
explicitly set. A sched domain's span means "balance process load among these
CPUs".
Each scheduling domain must have one or more CPU groups (struct sched_group)
which are organised as a circular one way linked list from the ->groups
pointer. The union of cpumasks of these groups MUST be the same as the
domain's span. The group pointed to by the ->groups pointer MUST contain the CPU
to which the domain belongs. Groups may be shared among CPUs as they contain
read only data after they have been set up. The intersection of cpumasks from
any two of these groups may be non empty. If this is the case the SD_OVERLAP
flag is set on the corresponding scheduling domain and its groups may not be
shared between CPUs.
Balancing within a sched domain occurs between groups. That is, each group
is treated as one entity. The load of a group is defined as the sum of the
load of each of its member CPUs, and only when the load of a group becomes
out of balance are tasks moved between groups.
In kernel/sched/core.c, sched_balance_trigger() is run periodically on each CPU
through sched_tick(). It raises a softirq after the next regularly scheduled
rebalancing event for the current runqueue has arrived. The actual load
balancing workhorse, sched_balance_softirq()->sched_balance_domains(), is then run
in softirq context (SCHED_SOFTIRQ).
The latter function takes two arguments: the runqueue of current CPU and whether
the CPU was idle at the time the sched_tick() happened and iterates over all
sched domains our CPU is on, starting from its base domain and going up the ->parent
chain. While doing that, it checks to see if the current domain has exhausted its
rebalance interval. If so, it runs sched_balance_rq() on that domain. It then checks
the parent sched_domain (if it exists), and the parent of the parent and so
forth.
Initially, sched_balance_rq() finds the busiest group in the current sched domain.
If it succeeds, it looks for the busiest runqueue of all the CPUs' runqueues in
that group. If it manages to find such a runqueue, it locks both our initial
CPU's runqueue and the newly found busiest one and starts moving tasks from it
to our runqueue. The exact number of tasks amounts to an imbalance previously
computed while iterating over this sched domain's groups.
Implementing sched domains
==========================
The "base" domain will "span" the first level of the hierarchy. In the case
of SMT, you'll span all siblings of the physical CPU, with each group being
a single virtual CPU.
In SMP, the parent of the base domain will span all physical CPUs in the
node. Each group being a single physical CPU. Then with NUMA, the parent
of the SMP domain will span the entire machine, with each group having the
cpumask of a node. Or, you could do multi-level NUMA or Opteron, for example,
might have just one domain covering its one NUMA level.
The implementor should read comments in include/linux/sched/sd_flags.h:
SD_* to get an idea of the specifics and what to tune for the SD flags
of a sched_domain.
Architectures may override the generic domain builder and the default SD flags
for a given topology level by creating a sched_domain_topology_level array and
calling set_sched_topology() with this array as the parameter.
The sched-domains debugging infrastructure can be enabled by 'sched_verbose'
to your cmdline. If you forgot to tweak your cmdline, you can also flip the
/sys/kernel/debug/sched/verbose knob. This enables an error checking parse of
the sched domains which should catch most possible errors (described above). It
also prints out the domain structure in a visual format.
3. 한국어 전문 번역
영어 원문의 문단 순서와 의미를 유지한 전체 번역입니다. 코드, 함수명, symbol과 URL은 원문 표기를 유지합니다.
Scheduling domain hierarchy
1-29각 CPU에는 struct sched_domain으로 표현되는 base scheduling domain이 있다. Domain hierarchy는 base domain의 ->parent pointer를 따라 구성된다. ->parent chain은 반드시 NULL로 끝나야 한다. Domain 구조체는 lock 없이 갱신되므로 per-CPU로 두어야 한다.
각 scheduling domain은 ->span field에 저장된 여러 CPU를 포함한다. Parent domain의 span은 child span의 superset이어야 하고, CPU i의 base domain은 최소한 CPU i를 포함해야 한다. 일반적으로 각 CPU의 top domain은 system의 모든 CPU를 포함한다.
Top domain이 모든 CPU를 포함하지 않으면 allowed CPU mask를 명시하지 않은 일부 CPU에는 실행할 task가 배정되지 않을 수 있다. Sched domain span의 의미는 해당 CPU들 사이에서 process load를 balance한다는 것이다.
각 scheduling domain에는 struct sched_group 하나 이상이 있어야 한다. Group은 ->groups pointer에서 시작하는 단방향 circular linked list로 구성된다. Group cpumask의 union은 domain span과 같아야 하며 ->groups가 가리키는 group에는 해당 domain이 속한 CPU가 포함되어야 한다.
Setup 이후 group data는 read-only이므로 CPU끼리 group을 공유할 수 있다. 두 group의 cpumask intersection이 비어 있지 않을 수도 있다. 이 경우 해당 domain에 SD_OVERLAP flag를 set하며 group을 CPU 사이에서 공유할 수 없다.
Domain 안의 load balancing
31-62Sched domain 내부 balancing은 group 사이에서 수행한다. 각 group을 하나의 entity로 취급하고 group load는 member CPU load의 합으로 정의한다. Group load가 불균형해질 때만 group 사이에서 task를 이동한다.
kernel/sched/core.c의 sched_balance_trigger()는 각 CPU에서 sched_tick()을 통해 주기적으로 실행된다. 현재 runqueue의 다음 정기 rebalance event가 도착하면 softirq를 raise한다. 실제 load balancing은 SCHED_SOFTIRQ context에서 sched_balance_softirq()->sched_balance_domains()가 수행한다.
sched_balance_domains()는 현재 CPU의 runqueue와 sched_tick() 당시 CPU가 idle이었는지를 인자로 받는다. Base domain부터 ->parent chain을 따라 올라가면서 CPU가 속한 모든 sched domain을 순회한다.
각 domain의 rebalance interval이 만료되었으면 sched_balance_rq()를 실행하고, 이어서 parent domain을 같은 방식으로 확인한다.
sched_balance_rq()는 먼저 현재 domain에서 가장 busy한 group을 찾는다. 성공하면 해당 group의 CPU runqueue 가운데 가장 busy한 runqueue를 찾고, 현재 CPU runqueue와 그 runqueue를 모두 lock한 뒤 busy runqueue에서 현재 runqueue로 task를 옮긴다. 이동할 task 수는 group을 순회하면서 미리 계산한 imbalance에 따라 정해진다.
Sched domain 구현
64-80Base domain은 hierarchy의 첫 level을 span한다. SMT system에서는 physical CPU의 모든 sibling을 포함하고 각 group은 virtual CPU 하나로 구성된다.
SMP에서는 base domain의 parent가 node의 모든 physical CPU를 포함하며 각 group은 physical CPU 하나다. NUMA에서는 SMP domain의 parent가 machine 전체를 포함하고 각 group은 node의 cpumask를 가진다. Multi-level NUMA도 가능하며, Opteron처럼 NUMA level 하나를 domain 하나가 포괄할 수도 있다.
구현자는 include/linux/sched/sd_flags.h의 SD_* comment를 읽어 sched_domain flag의 의미와 조정 방법을 이해해야 한다.
Architecture override와 검증
82-94Architecture는 sched_domain_topology_level array를 만들고 set_sched_topology()에 전달해 generic domain builder와 topology level별 기본 SD flag를 override할 수 있다.
Kernel command line에 sched_verbose를 추가하면 sched-domain debugging infrastructure를 활성화할 수 있다. Command line을 바꾸지 못했다면 /sys/kernel/debug/sched/verbose knob을 변경할 수도 있다.
이 기능은 sched domain을 parsing하며 앞에서 설명한 대부분의 구성 오류를 검사하고 domain 구조를 시각적인 형식으로 출력한다.
domain, group, span
sched-domains.rst:1-54아래 domain의 span은 위 domain span에 포함됩니다. 각 단계의 sched_group은 다음 load-balancing 후보 범위를 만들며 마지막 단계가 partition 전체를 덮습니다.
sched_domain은 현재 CPU에서 어느 범위까지 부하를 비교할지 나타내는 계층 노드입니다. span은 domain이 포함하는 CPU mask이고 parent로 올라갈수록 범위가 넓어집니다. sched_group은 같은 단계의 CPU를 topology 단위로 묶어 어느 group에서 task를 가져올지 비교하는 대상이 됩니다.
모든 CPU는 자신을 기준으로 한 domain 체인을 갖습니다. 같은 물리 topology를 표현하더라도 group list의 시작점은 CPU마다 다를 수 있습니다. 이 per-CPU 관점 덕분에 local group과 remote group을 빠르게 구분할 수 있습니다.