[번역] scheduler/sched-domains.txt

각각의 CPU는 기본 스케쥴링 도메인(struct sched_domain)을 가지고 있다. 도메인계층도는 parent 포인터를 통해 base domain에서부터 구축이 시작된다. parent 포인터는 NULL로 끝나야한다(계층도의 마지막 도메인의 parent은 NULL이여야 한다는 의미). 도메인 구조체는 lock없이 갱신되기 위해 cpu마다 가지고 있다.

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.

각 스케줄링 도메인은 여러개의 CPU로 이루어져 있다.(도메인에 속해있는 cpu list가 span 필드가 가리키는 비트맵에 저장되어있음)  부모 도메인의 span은 자식 도메인들의 span의 전체 집합이 되어야 한다(이 제한은 해제될 수 있음). CPU i의 기본 domain은 최소한 CPU i를 span에 가지고 있어야 한다.

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. 

비록 반드시 그래야만 하는건 아니지만, 각 CPU의 top domain은 시스템의 모든 CPU로 span된다. 그렇지 않으면 cpu_allowed 마스크에 허용된 몇몇 CPU가 태스크를 받을 수 없는 경우로 이어질 수 있다. 도메인의 span은 프로세스의 로드가  span에 기록된 cpu list 사이에서 balancing된다는 것을 의미한다.

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".

각 스케줄링 도메인은 1개 이상의 스케줄링 그룹(struct sched_group)을 가져야 한다. 도메인 내의 모든 스케쥴링 그룹은 groups 포인터를 통해 원형 단일 연결 리스트로 이루어져 있다.  스케줄링 그룹의 cpumask합은 반드시 그룹이 속한 도메인의 span과 동일해야 한다.  도메인 내의 어떤 두 그룹은 겹치는 cpu를 가지고 있으면 안된다.(도메인내의 각 그룹은 서로 다른 cpu로 이루어진 cpumask를 가져야 한다는 뜻) groups 포인터가 가리키는 그룹은 도메인에 속한 CPU를 포함하고 있어야 한다. 그룹들은 그룹이 생성된 이후부터 자기가 포함하고 있는 CPU들 사이에서 공유되는 읽기전용 데이터를 가지고있다.

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 intersection of cpumasks from any two of these groups MUST be the empty set. 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.

스케줄링 도메인 안에서의 로드 밸런싱은 그룹간에 발생한다. 이 말은 각 스케줄링 그룹은 하나의 엔티티로 취급된다는 것을 의미한다. 그룹의 로드는 그룹의 멤버 CPU들의 load 합으로 정의된다. 그리고 그룹 사이의 로드의 불균형이 일어날 때 그룹 사이에서 태스크가 이동한다. 

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.

kernel/sched/core.c에 있는 trigger_load_balance()는 scheduler_tick()를 통해 각 CPU에서 주기적으로 수행된다.  trigger_load_balance()는 current cpu의 런큐를 위한 정기적인 로드밸런싱을 수행할 때가 되면 softirq(SCHED_SOFTIRQ)를 raise한다.  실질적인 로드밸런싱을 수행하는 run_rebalance_domains() -> rebalance_domains()는 softirq context에서 수행된다.

In kernel/sched/core.c, trigger_load_balance() is run periodically on each CPU through scheduler_tick(). It raises a softirq after the next regularly scheduled rebalancing event for the current runqueue has arrived. The actual load balancing workhorse, run_rebalance_domains()->rebalance_domains(), is then run in softirq context (SCHED_SOFTIRQ).

rebalance_domains()는 두개의 인자를 갖는다:

두 인자는 현재 CPU id와 scheduler_tick() 함수가 idle상태에서 호출되었는지 여부이다. CPU가 속한 모든 도메인을 기본 domain에서 시작해서 parent 포인터를 이용해서 반복한다. 이 과정을 수행하면서 현재 도메인이 rebalance interval이 지났는지를 체크한다. 만약 그렇다면 도메인에 대한 load_balance()를 수행한다. 도메인이 부모도메인을 가지고 있다면 순차적으로 이 과정을 반복한다.

The latter function takes two arguments:

the current CPU and whether it was idle at the time the scheduler_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 load_balance() on that domain. It then checks the parent sched_domain (if it exists), and the parent of the parent and so forth.

처음에는 load_balance()는 현재 스케줄링 도메인에서 가장 바쁜 그룹을 찾는다. 그런 다음 그룹 내의 가장 바쁜 런큐를 찾는다. 바쁜 런큐가 있다면 해당 런큐와 current CPU의 런큐를 잠근 다음 바쁜 런큐에서 current CPU의 런큐로 태스크를 옮긴다. 옮긴 태스크의 갯수의 합계는 스케쥴링 도메인에 속한 그룹들을 돌며 계산된 로드 불균형(imbalance)과 같다.  

Initially, load_balance() 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.

*** 스케쥴링 도메인 구현 ***

기본 domain은 도메인 계층도의 첫 레벨이다. SMT level의  도메인은 physical cpu의 모든 sibling을 span으로 갖는다. 이때 virtual cpu(hyperthreading)는 하나의 그룹이 된다.

*** 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.

SMP에서는 기본 domain의 부모도메인은 node의 모든 physical cpu를 span으로 갖는다. 각 그룹은 하나의 physical cpu를 갖는다. NUMA에서는 SMP 도메인의 부모 도메인은 머신의 전체 CPU를 span으로 갖는다, 이때 각 그룹은 각각의 노드를 span으로 갖는다. 혹은 mult-level NUMA나 Opteron의 경우 하나의 NUMA 레벨을 전부 커버하는 하나의 도메인을 갖게 될 것이다.

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.

도메인 계층도를 구현하려는 사람은  구체적인 사항과 무엇을 조절해야하는지에 대한 아이디어를 얻기 위해 include/linux/sched.h의 구조체 sched_domain의 필드인 SD_FLAG_*, SD_*_INIT의 코멘트를 읽어야 한다.

The implementor should read comments in include/linux/sched.h:

struct sched_domain fields, SD_FLAG_*, SD_*_INIT to get an idea of the specifics and what to tune.

아키텍처가 만약 기존의 domain build 과정을 사용해서 SMT->SMP->NUMA topology (혹은 이구조의 부분집합만)을 계속 유지하면서 기본적인 SD_*_INIT은 무시하고 싶을수가 있다. 이 경우는 ARCH_HAS_SCHED_TUNE 정의를 추가하면 된다.

Architectures may retain the regular override the default SD_*_INIT flags while using the generic domain builder in kernel/sched/core.c if they wish to retain the traditional SMT->SMP->NUMA topology (or some subset of that). This can be done by #define'ing ARCH_HASH_SCHED_TUNE.

아니면 아키텍쳐가 완전히  기존의 도메인 구축을 무시하길 원한다면 ARCH_HAS_SCHED_DOMAIN을 정의하면 된다. 그리고 arch_init_sched_domains()를 구현하면 된다. 이 함수는 cpu_attach_domain()를 사용해서 도메인을 모든 cpu에 연결해준다.

Alternatively, the architecture may completely override the generic domain builder by #define'ing ARCH_HASH_SCHED_DOMAIN, and exporting our arch_init_sched_domains function. This function will attach domains to all CPUs using cpu_attach_domain.

스케줄링 도메인의 디버깅 설비는 CONFIG_SCHED_DEBUG를 활성화하면 사용할 수 있다. 이 기능은 스케줄링 도메인을 파싱할 때의 에러검사를 활성화해서 발생가능한 에러를 잡을 수 있게 해준다. 또한 시각적인 방식으로 도메인 구조를 출력해준다.

The sched-domains debugging infrastructure can be enabled by enabling CONFIG_SCHED_DEBUG. 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.

참고

1) linux kernel 4.6 기준으로 ARCH_HAS_SCHED_{TUNE, DOMAIN}, arch_init_sched_domains() 관련된 코드는 존재하지 않음. 현재 새로운 스케줄링 도메인 계층도는 set_sched_topology()를 통해 등록하고 있는것으로 보임.