Scheduler -14- (Scheduling Domain -2-)

<kernel v5.4>

그룹 스케줄링과 스케줄 그룹은 단어 순서만 바뀌었지만 서로 다른 기술을 의미하므로 각별히 주의해야한다.

 

스케줄링 도메인과 스케줄 그룹

리눅스 커널이 적절한 로드밸런싱을 수행하기 위해 모든 cpu들이 동등한 조건으로 로드밸런싱을 할 수가 없다. 각 cpu들의 성능, 캐시 공유, 노드에 따른 메모리 대역폭이 달라 다른 성능을 나태낸다. 가장 로드밸런싱이 용이한 cpu들끼리 그루핑을하고, 그 다음 레벨의 cpu들과 그루핑하는 식으로 레벨별로 묶어 로드 밸런싱에 대한 우선 순위를 결정하기 위해 cpu 토플로지를 파악하고, 이를 통해 스케줄링 도메인 토플로지 레벨을 구성한다. 그런 후 최종 단계에서 스케줄링 도메인과 스케줄 그룹을 구성하면 로드 밸런싱에서 이들을 이용하게 된다.

 

스케줄링 도메인 토플로지

1) arm 스케줄링 도메인 토플로지

32bit arm cpu 토플로지를 만들때 다음과 같은 순서로 단계별로 구성한다.

  • GMC
    • core power 제어 가능한 그룹
    • CONFIG_SCHED_MC 커널 옵션 사용
  • MC
    • 그 다음으로 l2 캐시를 공유하는 클러스터 내의 cpu에 더 우선권을 준다.
    • CONFIG_SCHED_MC 커널 옵션 사용
  • DIE
    • 그 다음으로 (l3 캐시를 공유하는) 같은 die를 사용하는 cpu에 더 우선권을 준다.
  • NUMA
    • 같은 NUMA 노드를 사용하는 cpu에 더 우선권을 준다.
    • NUMA 노드에서 최단 거리 path를 사용하는 cpu에 더 우선권을 준다.
    • CONFIG_NUMA 커널 옵션 사용

 

2) arm64 및 디폴트 스케줄링 도메인 토플로지

ARM64 및 RISC-V 시스템의 토플로지를 만들때 다음과 같은 순서로 단계별로 구성한다.

  • SMT
    • l1 캐시를 공유하는 cpu에 대해 더 우선권을 준다. (virtual core)
    • 캐시를 플러시할 필요가 없으므로 가장 비용이 저렴하다. (relax 도메인)
    • arm64는 아직 활용하지 않는다.
    • CONFIG_SCHED_SMT 커널 옵션 사용
  • MC
    • 그 다음으로 l2 캐시를 공유하는 클러스터 내의 cpu에 더 우선권을 준다.
    • CONFIG_SCHED_MC 커널 옵션 사용
  • DIE
    • 그 다음으로 (l3 캐시를 공유하는) 같은 die를 사용하는 cpu에 더 우선권을 준다.
  • NUMA
    • NUMA 레벨은 NUMA distance 별로 여러 개의 레벨을 사용할 수 있다.
    • NUMA 노드에서 최단 거리 path를 사용하는 cpu에 더 우선권을 준다.
    • CONFIG_SCHED_NUMA 커널 옵션 사용

 

다음 그림 3가지는 시스템 구성에 따른 cpu topology를 나타낸다.

 

 

 

스케줄 도메인 플래그

  • SD_LOAD_BALANCE
    • 이 도메인에서 로드 밸런싱을 허용한다.
  • SD_BALANCE_NEWIDLE
    • 이 도메인에서 새롭게 idle로 진입하는 로드 밸런싱을 허용한다. (idle 밸런싱)
  • SD_BALANCE_EXEC
    • 이 도메인은 실행되는 태스크에 대해 로드 밸런싱을 허용한다. (exec 밸런싱)
  • SD_BALANCE_FORK
    • 이 도메인은 새롭게 fork한 태스크에 대해 로드 밸런싱을 허용한다. (fork 밸런싱)
  • SD_BALANCE_WAKE
    • 이 도메인은 idle 상태에서 깨어난 cpu에 대해 로드 밸런싱을 허용한다. (wake 밸런싱)
  • SD_WAKE_AFFINE
    • 이 도메인은 idle 상태에서 깨어난 cpu가 도메인내의 idle sibling cpu 선택을 허용한다.
  • SD_ASYM_CPUCAPACITY
    • 도메인 내의 멤버들이 다른 cpu 성능을 가진다.
  • SD_SHARE_CPUCAPACITY
    • 이 도메인은 cpu 성능을 공유한다.
    • 하드웨어 스레드들은 하나의 코어에 대한 성능을 공유한다.
    • x86(하이퍼 스레드)이나 powerpc의 SMT 도메인 토플로지 레벨에서 사용한다.
  • SD_SHARE_POWERDOMAIN
    • 이 도메인에서 파워를 공유한다.
    • 절전을 위해 클러스터 단위로 core들의 파워를 제어한다. (빅/리틀 클러스터 등)
    • 현재 arm/arm64의 GMC 도메인 토플로지 레벨에서 사용한다.
  • SD_SHARE_PKG_RESOURCES
    • 이 도메인에서 패키시 내의 각종 캐시 등의 리소스를 공유한다.
    • arm, arm64의 경우 보통 한 패키지(DIE) 안에 구성된 단위 클러스터내의 코어들이 캐시를 공유한다. (L2 캐시 등)
    • x86이나 powerpc 같은 경우 하드웨어 스레드(SMT)와 코어(MC)가 캐시를 공유한다. (L2 또는 L3 캐시까지)
  • SD_SERIALIZE
    • 이 도메인은 누마 시스템에서 싱글 로드밸런싱에서만 사용된다.
  • SD_ASYM_PACKING
    • 낮은 번호의 하드웨어 스레드가 높은 더 성능을 가진다. (비균형)
    • powerpc의 SMT 도메인 토플로지 레벨에서 사용한다.
  • SD_PREFER_SIBLING
    • sibling 도메인내에서 태스크를 수행할 수 있도록 권장한다.
    • SD_NUMA, SD_SHARE_PKG_RESOURCES(MC, SMT), SD_SHARE_CPUCAPACITY(SMT)가 설정되지 않은 도메인에서만 사용 가능하므로 주로 DIE 도메인에서 사용된다.
  • SD_OVERLAP
    • 도메인들 간에 오버랩되는 경우 사용한다.
  • SD_NUMA
    • 이 도메인이 누마 도메인이다.
    • NUMA distance 단계 수 만큼의 도메인 레벨을 구성하여 사용한다.

 

적절한 로드밸런싱을 위해 태스크의 migration 비용을 고려하여 언제 수행해야 할 지 다음의 항목들을 체크한다.

  • 스케줄러 특성에 따른 로드 밸런싱
  • cpu 토플로지 레벨에 따른 로드 밸런싱
    • cpu affinity별 로드 밸런싱을 수행해야 하기 때문에 단계별 cpu 토플로지를 만들어 사용한다.
    • cpu capacity(core 능력치 * freq)를 파악하여 코어별 로드 밸런싱에 사용한다.
    • 도메인 그룹 간 균형을 맞추기 위한 active 밸런싱

 

스케줄러 특성 별 로드 밸런싱

다음과 같이 사용하는 스케줄러에 따라  로드밸런싱을 하는 방법이 달라진다.  cpu의 검색 순서는 모든 스케줄러가 스케줄링 도메인 레벨을 차례 대로 사용한다.

  • Deadline 스케줄러
    • dl 태스크가 2 개 이상 동작해야 하는 경우 그 중 deadline이 가장 급한 dl 태스크를 제외하고 나머지들을 다른 cpu로 옮기려한다.
    • 다른 cpu들에서 dl 태스크가 수행되고 있지 않거나 deadline이 가장 큰 dl 태스크가 동작하는 cpu를 찾아 그 cpu로 dl 태스크를 migration 한다.
  • RT 스케줄러
    • rt 태스크가 2개 이상 동작해야 하는 경우 그 중 우선 순위가 가장 높은 rt 태스크를 제외한 나머지들을 다른 cpu로 옮기려한다.
    • 다른 cpu들에서 rt 태스크가 수행되고 있지 않거나 우선 순위가 가장 낮은 rt 태스크가 동작하는 cpu를 찾아 그 cpu로 rt 태스크를 migration 한다.
  • CFS 스케줄러
    • cpu 로드가 가장 낮은 cpu로 cfs 태스크를 migration 한다.
    • cpu 로드가 얼마 이상일 때 수행할지 여부

 


스케줄링 도메인 토플로지 레벨 with NUMA

kernel_init() -> kernel_init_freeable() -> sched_init_smp() 함수에서 호출된다.

 

sched_init_numa()

kernel/sched/topology.c -1/3-

void sched_init_numa(void)
{
        int next_distance, curr_distance = node_distance(0, 0);
        struct sched_domain_topology_level *tl;
        int level = 0;
        int i, j, k;

        sched_domains_numa_distance = kzalloc(sizeof(int) * (nr_node_ids + 1), GFP_KERNEL);
        if (!sched_domains_numa_distance)
                return;

        /* Includes NUMA identity node at level 0. */
        sched_domains_numa_distance[level++] = curr_distance;
        sched_domains_numa_levels = level;

        /*
         * O(nr_nodes^2) deduplicating selection sort -- in order to find the
         * unique distances in the node_distance() table.
         *
         * Assumes node_distance(0,j) includes all distances in
         * node_distance(i,j) in order to avoid cubic time.
         */
        next_distance = curr_distance;
        for (i = 0; i < nr_node_ids; i++) {
                for (j = 0; j < nr_node_ids; j++) {
                        for (k = 0; k < nr_node_ids; k++) {
                                int distance = node_distance(i, k);

                                if (distance > curr_distance &&
                                    (distance < next_distance ||
                                     next_distance == curr_distance))
                                        next_distance = distance;

                                /*
                                 * While not a strong assumption it would be nice to know
                                 * about cases where if node A is connected to B, B is not
                                 * equally connected to A.
                                 */
                                if (sched_debug() && node_distance(k, i) != distance)
                                        sched_numa_warn("Node-distance not symmetric");

                                if (sched_debug() && i && !find_numa_distance(distance))
                                        sched_numa_warn("Node-0 not representative");
                        }
                        if (next_distance != curr_distance) {
                                sched_domains_numa_distance[level++] = next_distance;
                                sched_domains_numa_levels = level;
                                curr_distance = next_distance;
                        } else break;
                }

                /*
                 * In case of sched_debug() we verify the above assumption.
                 */
                if (!sched_debug())
                        break;
        }
  • 코드 라인 8~10에서 numa distance 배열을 노드 수 + 1(for null finish) 만큼 할당한다.
  • 코드 라인 13~14에서 0번 레벨에 대한 값을 지정한다. 0번 레벨에는 from 0 to 0에 대한 distance 값으로 지정한다.
    • ARM64의 경우 디바이스 트리를 통한 numa_distance[] 배열의 초기화 및 파싱 함수는 다음과 같다.
  • 코드 라인 23~57에서 distance 순서대로 정렬하여 sched_domains_numa_distance[]을 구성한다.
    • 예) 총 5 레벨: [0]=10, [1]=15, [2]=20, [3]=25, [4]=30

 

kernel/sched/topology.c -2/3-

.       /*
         * 'level' contains the number of unique distances
         *
         * The sched_domains_numa_distance[] array includes the actual distance
         * numbers.
         */

        /*
         * Here, we should temporarily reset sched_domains_numa_levels to 0.
         * If it fails to allocate memory for array sched_domains_numa_masks[][],
         * the array will contain less then 'level' members. This could be
         * dangerous when we use it to iterate array sched_domains_numa_masks[][]
         * in other functions.
         *
         * We reset it to 'level' at the end of this function.
         */
        sched_domains_numa_levels = 0;

        sched_domains_numa_masks = kzalloc(sizeof(void *) * level, GFP_KERNEL);
        if (!sched_domains_numa_masks)
                return;

        /*
         * Now for each level, construct a mask per node which contains all
         * CPUs of nodes that are that many hops away from us.
         */
        for (i = 0; i < level; i++) {
                sched_domains_numa_masks[i] =
                        kzalloc(nr_node_ids * sizeof(void *), GFP_KERNEL);
                if (!sched_domains_numa_masks[i])
                        return;

                for (j = 0; j < nr_node_ids; j++) {
                        struct cpumask *mask = kzalloc(cpumask_size(), GFP_KERNEL);
                        if (!mask)
                                return;

                        sched_domains_numa_masks[i][j] = mask;

                        for_each_node(k) {
                                if (node_distance(j, k) > sched_domains_numa_distance[i])
                                        continue;

                                cpumask_or(mask, mask, cpumask_of_node(k));
                        }
                }
        }
  • 코드 라인 17에서sched_domains_numa_leves를 일단 0으로 리셋한다. 이 값은 함수 끝에서 다시 지정된다.
  • 코드 라인 19~21에서 sched_domains_numa_masks[]에 먼저 레벨 수 만큼 포인터 배열을 할당한다.
  • 코드 라인 27~47에서 sched_domains_numa_masks[][]에 레벨 * 노드 수 만큼 cpu 비트 마스크를 할당하고 소속된 cpu들을 설정한다.

 

kernel/sched/topology.c -3/3-

        /* Compute default topology size */
        for (i = 0; sched_domain_topology[i].mask; i++);

        tl = kzalloc((i + level + 1) *
                        sizeof(struct sched_domain_topology_level), GFP_KERNEL);
        if (!tl)
                return;

        /*
         * Copy the default topology bits..
         */
        for (i = 0; sched_domain_topology[i].mask; i++)
                tl[i] = sched_domain_topology[i];

        /*
         * Add the NUMA identity distance, aka single NODE.
         */
        tl[i++] = (struct sched_domain_topology_level){
                .mask = sd_numa_mask,
                .numa_level = 0,
                SD_INIT_NAME(NODE)
        };

        /*
         * .. and append 'j' levels of NUMA goodness.
         */
        for (j = 1; j < level; i++, j++) {
                tl[i] = (struct sched_domain_topology_level){
                        .mask = sd_numa_mask,
                        .sd_flags = cpu_numa_flags,
                        .flags = SDTL_OVERLAP,
                        .numa_level = j,
                        SD_INIT_NAME(NUMA)
                };
        }

        sched_domain_topology = tl;

        sched_domains_numa_levels = level;
        sched_max_numa_distance = sched_domains_numa_distance[level - 1];

        init_numa_topology_type();
}
  • 코드 라인 2~7에서 디폴트 토플로지 수 + numa distance 레벨 수 + 1(for null terminate)만큼 tl(토플로지 레벨)을 할당한다.
    • 예) MC + DIE + NUMA(10) + NUMA(15) + NUMA(20) + NUMA(30) + NULL
  • 코드 라인 12~13에서 디폴트 토플로지의 값을 새로 할당한 tl로 옮긴다.
  • 코드 라인 18~22에서 NUMA 0 레벨을 추가한다.
  • 코드 라인 27~35에서 NUMA 1 레벨부터 마지막 레벨까지 초기화한다.
  • 코드 라인 37에서 스케줄러용 sched_domain_topology 변수에 새로 구성한 tl을 대입한다.
  • 코드 라인 39에서 sched_domains_numa_levels에 NUMA 레벨을 대입한다.
    • 예) 10, 15, 20, 30인 경우 레벨 수=4
  • 코드 라인 40에서 sched_max_numa_distance에 가장 거리가 먼 distance를 대입한다.
  • 코드 라인 42에서 numa topology 타입 3 가지 중 하나를 선택한다.

 

다음 그림은 NUMA 시스템의 도메인 토플로지 레벨을 구성하는 모습을 보여준다.

 

init_numa_topology_type()

kernel/sched/topology.c

/*
 * A system can have three types of NUMA topology:
 * NUMA_DIRECT: all nodes are directly connected, or not a NUMA system
 * NUMA_GLUELESS_MESH: some nodes reachable through intermediary nodes
 * NUMA_BACKPLANE: nodes can reach other nodes through a backplane
 *
 * The difference between a glueless mesh topology and a backplane
 * topology lies in whether communication between not directly
 * connected nodes goes through intermediary nodes (where programs
 * could run), or through backplane controllers. This affects
 * placement of programs.
 *
 * The type of topology can be discerned with the following tests:
 * - If the maximum distance between any nodes is 1 hop, the system
 *   is directly connected.
 * - If for two nodes A and B, located N > 1 hops away from each other,
 *   there is an intermediary node C, which is < N hops away from both
 *   nodes A and B, the system is a glueless mesh.
 */
static void init_numa_topology_type(void)
{
        int a, b, c, n;

        n = sched_max_numa_distance;

        if (sched_domains_numa_levels <= 2) {
                sched_numa_topology_type = NUMA_DIRECT;
                return;
        }

        for_each_online_node(a) {
                for_each_online_node(b) {
                        /* Find two nodes furthest removed from each other. */
                        if (node_distance(a, b) < n)
                                continue;

                        /* Is there an intermediary node between a and b? */
                        for_each_online_node(c) {
                                if (node_distance(a, c) < n &&
                                    node_distance(b, c) < n) {
                                        sched_numa_topology_type =
                                                        NUMA_GLUELESS_MESH;
                                        return;
                                }
                        }

                        sched_numa_topology_type = NUMA_BACKPLANE;
                        return;
                }
        }
}

다음 3가지 NUMA topology 타입 중 하나를 선택한다.

  • NUMA_DIRECT
    • 모든 노드 간에 1 hop으로 접근할 수 있는 경우이다.
  • NUMA_GLULESS_MESH
    • 모든 노드 간에 1 hop으로 접근할 수 없지만, 2 hop 이내에 접근 가능한 경우이다.
  • NUMA_BACKPLANE
    • 모든 노드 간에 2 hop 이내에서 접근 할 수 없는 경우이다.

 

다음 그림은 numa topology 타입을 보여준다.

 


스케줄링 도메인들 초기화

kernel_init() -> kernel_init_freeable() -> sched_init_smp(cpu_active_mask) 함수에서 최종 호출된다.

 

sched_init_domains() 함수 이후로 다음과 같은 함수들이 호출되어 처리한다.

 

sched_init_domains()

kernel/sched/topology.c

/*
 * Set up scheduler domains and groups.  For now this just excludes isolated
 * CPUs, but could be used to exclude other special cases in the future.
 */
int sched_init_domains(const struct cpumask *cpu_map)
{
        int err;

        zalloc_cpumask_var(&sched_domains_tmpmask, GFP_KERNEL);
        zalloc_cpumask_var(&sched_domains_tmpmask2, GFP_KERNEL);
        zalloc_cpumask_var(&fallback_doms, GFP_KERNEL);

        arch_update_cpu_topology();
        ndoms_cur = 1;
        doms_cur = alloc_sched_domains(ndoms_cur);
        if (!doms_cur)
                doms_cur = &fallback_doms;
        cpumask_and(doms_cur[0], cpu_map, housekeeping_cpumask(HK_FLAG_DOMAIN));
        err = build_sched_domains(doms_cur[0], NULL);
        register_sched_domain_sysctl();

        return err;
}

요청한 cpu 맵을 사용하여 스케줄 도메인들을 초기화한다.

  • 코드 라인 9에서 아키텍처가 지원하는 경우 cpu topology를 갱신한다. (arm, arm64는 지원하지 않음)
  • 코드 라인 10~13에서 스케줄 도메인의 수를 1로 지정하고 하나의 스케줄 도메인용 비트마스크를 할당해온다. 할당이 실패한 경우 싱글 cpumask로 이루어진 fallback 도메인을 사용한다.
  • 코드 라인 14에서 인수로 전달받은 cpu_map에서 cpu_isolated_map을 제외시킨 cpumask를 doms_cur[0]에 대입한다.
  • 코드 라인 15에서 산출된 cpumask 만큼 스케줄 도메인을 구성한다.
  • 코드 라인 16에서 스케줄 도메인들을 sysctl에 구성한다.

 

alloc_sched_domains()

kernel/sched/core.c

cpumask_var_t *alloc_sched_domains(unsigned int ndoms)
{
        int i;
        cpumask_var_t *doms;

        doms = kmalloc(sizeof(*doms) * ndoms, GFP_KERNEL);
        if (!doms)
                return NULL;
        for (i = 0; i < ndoms; i++) {
                if (!alloc_cpumask_var(&doms[i], GFP_KERNEL)) {
                        free_sched_domains(doms, i);
                        return NULL;
                }
        }
        return doms;
}

요청한 스케줄 도메인 수 만큼의 cpu 비트마스크 어레이를 할당하고 반환한다.

  • 코드 라인 6~8에서 요청한 스케줄 도메인 수 만큼 스케줄 도메인용 비트마스크를 할당한다.
  • 코드 라인 9~14에서 대단위 cpumask가  필요한 경우 할당받아온다.
    • 32bit 시스템에서는 cpu가 32개를 초과하는 경우,
    • 64bit 시스템에서는 cpu가 64개를 초과하는 경우 별도의 cpumask를 할당받는다.

 

“isolcpus=” 커널 파라메터

/* cpus with isolated domains */
static cpumask_var_t cpu_isolated_map;

/* Setup the mask of cpus configured for isolated domains */
static int __init isolated_cpu_setup(char *str)
{
        alloc_bootmem_cpumask_var(&cpu_isolated_map);
        cpulist_parse(str, cpu_isolated_map);
        return 1;
}

__setup("isolcpus=", isolated_cpu_setup);

아이솔레이티드 도메인들을 위해  지정된 cpu리스트들을 마스크한다.

  • 지정된 태스크들로 태스크들이 스케줄되지 않도록 분리시킨다. 이렇게 분리된 cpu에서도 인터럽트는 사용될 수 있다.
  • “cat /sys/devices/system/cpu/isolated”으로 확인할 수 있다.
  • 예) “isolcpus=0,1”
  • 참고: how to detect if isolcpus is activated? | Linux & Unix

 

build_sched_domains()

kernel/sched/topology.c -1/2-

/*
 * Build sched domains for a given set of CPUs and attach the sched domains
 * to the individual CPUs
 */
static int
build_sched_domains(const struct cpumask *cpu_map, struct sched_domain_attr *attr)
{
        enum s_alloc alloc_state = sa_none;
        struct sched_domain *sd;
        struct s_data d;
        struct rq *rq = NULL;
        int i, ret = -ENOMEM;
        struct sched_domain_topology_level *tl_asym;
        bool has_asym = false;

        if (WARN_ON(cpumask_empty(cpu_map)))
                goto error;

        alloc_state = __visit_domain_allocation_hell(&d, cpu_map);
        if (alloc_state != sa_rootdomain)
                goto error;

        tl_asym = asym_cpu_capacity_level(cpu_map);

        /* Set up domains for CPUs specified by the cpu_map: */
        for_each_cpu(i, cpu_map) {
                struct sched_domain_topology_level *tl;

                sd = NULL;
                for_each_sd_topology(tl) {
                        int dflags = 0;

                        if (tl == tl_asym) {
                                dflags |= SD_ASYM_CPUCAPACITY;
                                has_asym = true;
                        }

                        sd = build_sched_domain(tl, cpu_map, attr, sd, dflags, i);

                        if (tl == sched_domain_topology)
                                *per_cpu_ptr(d.sd, i) = sd;
                        if (tl->flags & SDTL_OVERLAP)
                                sd->flags |= SD_OVERLAP;
                        if (cpumask_equal(cpu_map, sched_domain_span(sd)))
                                break;
                }
        }

스케줄 도메인을 구성한다. 이 함수를 호출하는 루틴은 다음 두 개가 있다.

  • sched_init_domains() -> 커널 부트업 시 속성값을 null로 진입
  • partition_sched_domains() -> cpu on/off 시 진입된다.

 

  • 코드 라인 15~17에서 스케줄 도메인 토플로지의 자료 구조를 할당받고 초기화하고 루트 도메인을 할당받은 후 초기화한다.
  • 코드 라인 19에서 동일하지 않은 cpu capacity 성능을 가진 경우 해당 도메인을 알아온다.
  • 코드 라인 22에서 cpu_map 비트마스크에 설정된 cpu에 대해 순회한다.
  • 코드 라인 26~34에서 스케줄 도메인 계층 구조를 순회하며 스케줄 도메인을 구성한다. 또한 asym 토플로지 레벨에 대해서는 dflags에 SD_ASYM_CPUCAPACITY 플래그를 추가하여 둔다.
  • 코드 라인 36~37에서 순회중인 tl이 전역 스케줄 도메인 토플로지인 경우 s_data.sd의 현재 순회중인 cpu에 구성한 스케줄 도메인을 연결한다.
  • 코드 라인 38~39에서 토플로지 레벨 tl에 SDTL_OVERLAP 설정된 경우 스케줄 도메인에도 SD_OVERLAP 플래그를 추가한다.
  • 코드 라인 40~41에서 cpu_map과 스케줄 도메인의 span 구성이 동일한 경우 루프를 벗어난다.

 

kernel/sched/topology.c -2/2-

        /* Build the groups for the domains */
        for_each_cpu(i, cpu_map) {
                for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
                        sd->span_weight = cpumask_weight(sched_domain_span(sd));
                        if (sd->flags & SD_OVERLAP) {
                                if (build_overlap_sched_groups(sd, i))
                                        goto error;
                        } else {
                                if (build_sched_groups(sd, i))
                                        goto error;
                        }
                }
        }

        /* Calculate CPU capacity for physical packages and nodes */
        for (i = nr_cpumask_bits-1; i >= 0; i--) {
                if (!cpumask_test_cpu(i, cpu_map))
                        continue;

                for (sd = *per_cpu_ptr(d.sd, i); sd; sd = sd->parent) {
                        claim_allocations(i, sd);
                        init_sched_groups_capacity(i, sd);
                }
        }

        /* Attach the domains */
        rcu_read_lock();
        for_each_cpu(i, cpu_map) {
                rq = cpu_rq(i);
                sd = *per_cpu_ptr(d.sd, i);

                /* Use READ_ONCE()/WRITE_ONCE() to avoid load/store tearing: */
                if (rq->cpu_capacity_orig > READ_ONCE(d.rd->max_cpu_capacity))
                        WRITE_ONCE(d.rd->max_cpu_capacity, rq->cpu_capacity_orig);

                cpu_attach_domain(sd, d.rd, i);
        }
        rcu_read_unlock();

        if (has_asym)
                static_branch_inc_cpuslocked(&sched_asym_cpucapacity);

        if (rq && sched_debug_enabled) {
                pr_info("root domain span: %*pbl (max cpu_capacity = %lu)\n",
                        cpumask_pr_args(cpu_map), rq->rd->max_cpu_capacity);
        }

        ret = 0;
error:
        __free_domain_allocs(&d, alloc_state, cpu_map);

        return ret;
}
  • 코드 라인 2~3에서 cpu_map에 설정된 cpu를 순회하고 그 하위 루프에서 해당 cpu의 하위 스케줄 도메인부터 상위 스케줄 도메인까지 순회한다.
  • 코드 라인 4에서 스케줄 도메인의 span_weight 멤버에 도메인에 속한 cpu 수를 대입한다.
  • 코드 라인 5~7에서 NUMA 스케줄 도메인 단계에서는 overlap 스케줄 그룹을 구성한다.
  • 코드 라인 8~11에서 그 외의 경우 일반 스케줄 그룹을 구성한다.
  • 코드 라인 16~18에서 cpu 수 만큼 거꾸로 순회하며 cpu_map에 설정되지 않은 cpu는 skip 한다.
  • 코드 라인 20~23에서 하위 스케줄 도메인부터 상위 스케줄 도메인까지 순회하며 스케줄링 도메인 토플로지에 구성된 sd, sg, sgc 들에 null을 넣어 함수의 가장 마지막에서 삭제하지 않도록 만든다. 그리고 스케줄링 그룹의 capacity를 초기화한다.
  • 코드 라인 28~37에서 cpu_map에 설정된 cpu를 순회하며 도메인을 연결한다.
  • 코드 라인 40~41에서 asym cpu capacity가 적용되도록 활성화한다.
  • 코드 라인 50~52에서 스케줄링 도메인 토플로지에 구성된 sd, sg, sgc 멤버들에서 사용되지 않는 구조체 할당들을 모두 해제한다.

 


스케줄 도메인들 할당

__visit_domain_allocation_hell()

kernel/sched/topology.c

static enum s_alloc 
__visit_domain_allocation_hell(struct s_data *d, const struct cpumask *cpu_map)
{
        memset(d, 0, sizeof(*d));

        if (__sdt_alloc(cpu_map))
                return sa_sd_storage;
        d->sd = alloc_percpu(struct sched_domain *);
        if (!d->sd)
                return sa_sd_storage;
        d->rd = alloc_rootdomain();
        if (!d->rd)
                return sa_sd;

        return sa_rootdomain;
}

요청한 cpu_map 비트마스크를 사용하여 스케줄 도메인 토플로지의 자료 구조를 할당받고 초기화한다. 그리고 루트 도메인을 할당받은 후 초기화한다. 성공한 경우 sa_rootdomain(0)을 반환한다.

__sdt_alloc()

kernel/sched/topology.c

static int __sdt_alloc(const struct cpumask *cpu_map)
{
        struct sched_domain_topology_level *tl;
        int j;

        for_each_sd_topology(tl) {
                struct sd_data *sdd = &tl->data;

                sdd->sd = alloc_percpu(struct sched_domain *);
                if (!sdd->sd)
                        return -ENOMEM;

                sdd->sds = alloc_percpu(struct sched_domain_shared *);
                if (!sdd->sds)
                        return -ENOMEM;

                sdd->sg = alloc_percpu(struct sched_group *);
                if (!sdd->sg)
                        return -ENOMEM;

                sdd->sgc = alloc_percpu(struct sched_group_capacity *);
                if (!sdd->sgc)
                        return -ENOMEM;

                for_each_cpu(j, cpu_map) {
                        struct sched_domain *sd;
                        struct sched_domain_shared *sds;
                        struct sched_group *sg;
                        struct sched_group_capacity *sgc;

                        sd = kzalloc_node(sizeof(struct sched_domain) + cpumask_size(),
                                        GFP_KERNEL, cpu_to_node(j));
                        if (!sd)
                                return -ENOMEM;

                        *per_cpu_ptr(sdd->sd, j) = sd;

                        sds = kzalloc_node(sizeof(struct sched_domain_shared),
                                        GFP_KERNEL, cpu_to_node(j));
                        if (!sds)
                                return -ENOMEM;

                        *per_cpu_ptr(sdd->sds, j) = sds;

                        sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
                                        GFP_KERNEL, cpu_to_node(j));
                        if (!sg)
                                return -ENOMEM;

                        sg->next = sg;

                        *per_cpu_ptr(sdd->sg, j) = sg;

                        sgc = kzalloc_node(sizeof(struct sched_group_capacity) + cpumask_size(),
                                        GFP_KERNEL, cpu_to_node(j));
                        if (!sgc)
                                return -ENOMEM;

#ifdef CONFIG_SCHED_DEBUG
                        sgc->id = j;
#endif

                        *per_cpu_ptr(sdd->sgc, j) = sgc;
                }
        }

        return 0;
}

요청한 cpu_map 비트마스크로 스케줄 도메인 토플로지를 초기화한다.

  • 코드 라인 6에서 스케줄 도메인 단계만큼 순회한다.
    • arm의 경우 보통 1 단계 DIE 만을 구성하여 사용한다. 클러스터를 구성하여 사용하는 경우 2 단계로 구성한 DIE – MC(Multi core)로 구성한다. 또한 클러스터들 끼리 distance가 다른 경우 NUMA 구성을 추가하여 사용한다.
  • 코드 라인 9~23에서 스케줄 도메인의 sd_data에 sched_domain, sched_group, sched_group_capacity에 대한 포인터를 per-cpu로 할당하여 구성한다.
  • 코드 라인 25~65에서 cpu_map 비트마스크에 포함된 cpu들에 대해 sched_domain, sched_group, sched_group_capacity 구조체를 할당받은 후 sd_data에 연결한다.
  • 코드 라인 67에서 성공 값 0을 반환한다.

 

다음 그림은 cpu_map 비트마스크에 설정된 cpu들에 대해 관련 자료 구조 할당을 받아 스케줄 도메인 토플로지에 연결하는 모습을 보여준다.

 

for_each_sd_topology()

kernel/sched/core.c

#define for_each_sd_topology(tl)                        \
        for (tl = sched_domain_topology; tl->mask; tl++)

스케줄링 도메인 토플로지 레벨에 따라 순회한다.

  • tl->mask가 null인 경우 순회를 정지한다.

 

asym cpu capacity를 사용하는 토플로지 레벨

asym_cpu_capacity_level()

kernel/sched/topology.c

/*
 * Find the sched_domain_topology_level where all CPU capacities are visible
 * for all CPUs.
 */
static struct sched_domain_topology_level
*asym_cpu_capacity_level(const struct cpumask *cpu_map)
{
        int i, j, asym_level = 0;
        bool asym = false;
        struct sched_domain_topology_level *tl, *asym_tl = NULL;
        unsigned long cap;

        /* Is there any asymmetry? */
        cap = arch_scale_cpu_capacity(cpumask_first(cpu_map));

        for_each_cpu(i, cpu_map) {
                if (arch_scale_cpu_capacity(i) != cap) {
                        asym = true;
                        break;
                }
        }

        if (!asym)
                return NULL;

        /*
         * Examine topology from all CPU's point of views to detect the lowest
         * sched_domain_topology_level where a highest capacity CPU is visible
         * to everyone.
         */
        for_each_cpu(i, cpu_map) {
                unsigned long max_capacity = arch_scale_cpu_capacity(i);
                int tl_id = 0;

                for_each_sd_topology(tl) {
                        if (tl_id < asym_level)
                                goto next_level;

                        for_each_cpu_and(j, tl->mask(i), cpu_map) {
                                unsigned long capacity;

                                capacity = arch_scale_cpu_capacity(j);

                                if (capacity <= max_capacity)
                                        continue;

                                max_capacity = capacity;
                                asym_level = tl_id;
                                asym_tl = tl;
                        }
next_level:
                        tl_id++;
                }
        }

        return asym_tl;
}

asymetric cpu capacity를 사용하는 토플로지 레벨을 알아온다.

  • 코드 라인 10~20에서 @cpu_map의 첫 번째 cpu에 대한 cpu capacity를 알아온 후 이를 다른 cpu들의 cpu capacity와 비교하여 모두가 같지 않은 경우 asym=true를 설정한다. 모두가 동일한 경우엔 null을 반환한다.
  • 코드 라인 27~33에서 @cpu_map cpu들을 대상으로 순회하며 하위 루프에서 도메인 레벨을 순회한다. 그 중 asym 도메인 레벨 미만은 skip 한다.
  • 코드 라인 35~46에서 세 번째 루프인 cpu_map을 다시 순회하며 max_capacity를 초과하는 경우 갱신하게 하고, asym 도메인과 레벨도 갱신하게 한다.
  • 코드 라인 53에서 발견된 asym 도메인 레벨을 반환한다.
    • 예) 빅/리틀 클러스터로 구성된 시스템이 2 단계 MC 및 DIE 도메인을 구성한 경우 aysm 도메인 레벨은 DIE로 지정된다.

 

루트 도메인 할당 및 초기화

alloc_rootdomain()

kernel/sched/topology.c

static struct root_domain *alloc_rootdomain(void)
{
        struct root_domain *rd;

        rd = kmalloc(sizeof(*rd), GFP_KERNEL);
        if (!rd)
                return NULL;

        if (init_rootdomain(rd) != 0) {
                kfree(rd);
                return NULL;
        }

        return rd;
}

루트 도메인을 할당받고 초기화한다.

 

다음 그림은 루트도메인을 할당받고 초기화하는 모습을 보여준다.

 

–이하 수정 중–


스케줄 도메인 구성

build_sched_domain()

kernel/sched/topology.c

static struct sched_domain *build_sched_domain(struct sched_domain_topology_level *tl,
                const struct cpumask *cpu_map, struct sched_domain_attr *attr,
                struct sched_domain *child, int dflags, int cpu)
{
        struct sched_domain *sd = sd_init(tl, cpu_map, child, dflags, cpu);

        if (child) {
                sd->level = child->level + 1;
                sched_domain_level_max = max(sched_domain_level_max, sd->level);
                child->parent = sd;

                if (!cpumask_subset(sched_domain_span(child),
                                    sched_domain_span(sd))) {
                        pr_err("BUG: arch topology borken\n");
#ifdef CONFIG_SCHED_DEBUG
                        pr_err("     the %s domain not a subset of the %s domain\n",
                                        child->name, sd->name);
#endif
                        /* Fixup, ensure @sd has at least @child CPUs. */
                        cpumask_or(sched_domain_span(sd),
                                   sched_domain_span(sd),
                                   sched_domain_span(child));
                }

        }
        set_domain_attribute(sd, attr);

        return sd;
}

요청한 토플로지 레벨에 대한 스케줄 도메인을 구성한다.

  • 코드 라인 5에서 요청한 스케줄 도메인 토플로지 레벨 tl에 대한 스케줄 도메인을 초기화한다.
  • 코드 라인 7~10에서 @child 스케줄 도메인 토플로지 레벨이 있는 경우 현재 스케줄 도메인의 레벨을 child 보다 1 큰 값으로하고 부모 관계를 설정한다.
    • 전역 변수 sched_domain_level_max에는 최대 스케줄 도메인 레벨 값을 갱신한다.
  • 코드 라인 12~23에서 자식 스케줄 도메인에 속한 cpu가 요청한 스케줄 도메인에 포함되지 않은 경우 경고 메시지를 출력하고 해당 스케줄 도메인에 포함시킨다.
  • 코드 라인 26에서 스케줄링 도메인의 레벨이 요청한 relax 도메인 레벨보다 큰 경우 wake 및 newidle 플래그를 클리어하고 그렇지 않은 경우 설정한다. 요청한 relax 도메인 레벨이 없는 경우 디폴트 relax 도메인 레벨 값을 사용하여 판단한다.
  • 코드 라인 28에서 스케줄링 도메인을 반환한다.

 

다음 그림은 각 cpu에서 스케줄 도메인간의 계층구조를 보여준다.

 

다음 그림은 각 레벨의 스케줄 도메인에 소속된 cpu의 span 값을 표현하였다.

 

다음 그림도 위의 그림과 동일하지만 스케줄 도메인을 cpu별로 span 값이 같은것들 끼리 뭉쳐 표현하였다.

sd_init()

kernel/sched/topology.c -1/2-

static struct sched_domain *
sd_init(struct sched_domain_topology_level *tl,
        const struct cpumask *cpu_map,
        struct sched_domain *child, int dflags, int cpu)
{
        struct sd_data *sdd = &tl->data;
        struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
        int sd_id, sd_weight, sd_flags = 0;

#ifdef CONFIG_NUMA
        /*
         * Ugly hack to pass state to sd_numa_mask()...
         */
        sched_domains_curr_level = tl->numa_level;
#endif

        sd_weight = cpumask_weight(tl->mask(cpu));

        if (tl->sd_flags)
                sd_flags = (*tl->sd_flags)();
        if (WARN_ONCE(sd_flags & ~TOPOLOGY_SD_FLAGS,
                        "wrong sd_flags in topology description\n"))
                sd_flags &= ~TOPOLOGY_SD_FLAGS;

        /* Apply detected topology flags */
        sd_flags |= dflags;

        *sd = (struct sched_domain){
                .min_interval           = sd_weight,
                .max_interval           = 2*sd_weight,
                .busy_factor            = 32,
                .imbalance_pct          = 125,

                .cache_nice_tries       = 0,

                .flags                  = 1*SD_LOAD_BALANCE
                                        | 1*SD_BALANCE_NEWIDLE
                                        | 1*SD_BALANCE_EXEC
                                        | 1*SD_BALANCE_FORK
                                        | 0*SD_BALANCE_WAKE
                                        | 1*SD_WAKE_AFFINE
                                        | 0*SD_SHARE_CPUCAPACITY
                                        | 0*SD_SHARE_PKG_RESOURCES
                                        | 0*SD_SERIALIZE
                                        | 1*SD_PREFER_SIBLING
                                        | 0*SD_NUMA
                                        | sd_flags
                                        ,

                .last_balance           = jiffies,
                .balance_interval       = sd_weight,
                .max_newidle_lb_cost    = 0,
                .next_decay_max_lb_cost = jiffies,
                .child                  = child,
#ifdef CONFIG_SCHED_DEBUG
                .name                   = tl->name,
#endif
        };

스케줄링 도메인을 초기화한다.

  • 코드 라인 19~23에서 요청한 토플로지의 sd_flags() 함수 후크를 수행하여 sd_flags 값을 알아온다. sd_flags 값으로 다음 플래그 값들 이외의 플래그가 설정되어 있는 경우 경고 메시지를 출력하고 제거한다.
    • 허용: SD_SHARE_CPUCAPACITY | SD_SHARE_PKG_RESOURCES | SD_NUMA | SD_ASYM_PACKING | SD_SHARE_POWERDOMAIN
  • 코드 라인 26에서 토플로지 플래그들을 스케줄링 도메인 플래그에 추가한다.
  • 코드 라인 28~57에서 스케줄링 도메인의 초기값을 설정한다.
    • 사용자가 지정한 스케줄링 도메인의 초기 플래그 값 sd_flags 이외에 다음 플래그 값은 커널이 기본 플래그로 추가한다.
    • 추가: SD_LOAD_BALANCE | SD_BALANCE_NEWIDLE | SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE | SD_PREFER_SIBLING

 

kernel/sched/topology.c -2/2-

        cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
        sd_id = cpumask_first(sched_domain_span(sd));

        /*
         * Convert topological properties into behaviour.
         */

        if (sd->flags & SD_ASYM_CPUCAPACITY) {
                struct sched_domain *t = sd;

                /*
                 * Don't attempt to spread across CPUs of different capacities.
                 */
                if (sd->child)
                        sd->child->flags &= ~SD_PREFER_SIBLING;

                for_each_lower_domain(t)
                        t->flags |= SD_BALANCE_WAKE;
        }

        if (sd->flags & SD_SHARE_CPUCAPACITY) {
                sd->imbalance_pct = 110;

        } else if (sd->flags & SD_SHARE_PKG_RESOURCES) {
                sd->imbalance_pct = 117;
                sd->cache_nice_tries = 1;

#ifdef CONFIG_NUMA
        } else if (sd->flags & SD_NUMA) {
                sd->cache_nice_tries = 2;

                sd->flags &= ~SD_PREFER_SIBLING;
                sd->flags |= SD_SERIALIZE;
                if (sched_domains_numa_distance[tl->numa_level] > node_reclaim_distance) {
                        sd->flags &= ~(SD_BALANCE_EXEC |
                                       SD_BALANCE_FORK |
                                       SD_WAKE_AFFINE);
                }

#endif
        } else {
                sd->cache_nice_tries = 1;
        }

        /*
         * For all levels sharing cache; connect a sched_domain_shared
         * instance.
         */
        if (sd->flags & SD_SHARE_PKG_RESOURCES) {
                sd->shared = *per_cpu_ptr(sdd->sds, sd_id);
                atomic_inc(&sd->shared->ref);
                atomic_set(&sd->shared->nr_busy_cpus, sd_weight);
        }

        sd->private = sdd;

        return sd;
}
  • 코드 라인 1~2에서 @cpu_map & tl->mask() 값을 sd->span 비트마스크에 대입하고, sd_id에는 sd->span 중 첫 번째 cpu를 알아온다.
  • 코드 라인 8~19에서 arm의 빅/리틀 클러스터처럼 asym cpu capacity를 사용하는 스케줄링 도메인의 경우 다음 두 가지를 실행한다.
    • 자식 스케줄링 도메인의 플래그에서 SD_PREFER_SIBLING 플래그를 제거한다.
    • 하위 스케줄링 도메인의 플래그에 SD_BALANCE_WAKE 플래그를 추가한다.
  • 코드 라인 21~22에서 hw thread를 지원하는 경우 스케줄링 도메인의 경우 imbalance_pct 값을 110으로 조정한다.
  • 코드 라인 24~26에서 패키지 리소스(l2 캐시 등)을 공유하는 스케줄링 도메인의 경우 imbalance_pct 값을 117로 조정하고, cache_nice_tries 값을 1로 사용한다.
  • 코드 라인 29~38에서 numa 도메인들의 경우 다음과 같이 적용한다.
    • cache_nice_tries 값을 2로 사용
    • SD_PREFER_SIBLING 플래그 제거
    • SD_SERIALIZE 추가
    • distance가 멀어 reclaim을 금지 시킨 도메인의 경우 SD_BALANCE_EXEC, SD_BALANCE_FORK, SD_WAKE_AFFINE 플래그를 제거한다.
  • 코드 라인 41~43에서 그 외의 스케줄링 도메인의 경우 cache_nice_tries 값을 1로 사용한다.
  • 코드 라인 49~53에서 패키지 리소스를 공유하는 도메인의 경우 shared에 shared 도메인의 cpu에 해당하는 sdd->sds 를 지정한다. shared 도메인의 참조 카운트를 1 증가시키고, nr_busy_cpus에 도메인 멤버 cpu 수를 지정한다.
  • 코드 라인 55에서 sd->private에 스케줄링 도메인 데이터 sdd를 지정한다.

 

다음 그림은 스케줄링 도메인을 초기화하는 모습을 보여준다.

 

다음 그림은 스케줄 도메인 토플로지 레벨별로 플래그의 변화를 보여준다.

 

다음 그림은 arm64에서 토플로지에 설정된 sd_flags 값을 읽어 sd_init() 함수 호출 시 스케줄링 도메인의 플래그들 초기값을 보여준다.

 

다음 그림은 32bit arm 역시 토플로지도 유사함을 보여준다.

  • rpi2의 경우 DIE 레벨만 사용된다.
    • CONFIG_SCHED_MC를 설정하면 DIE – MC – GMC의 3 단계가 구성되는데 실제 도메인은 GMC와 MC만 사용한다.

 

Relax domain 레벨

전역 변수 default_relax_domain_level은 “relax_domain_level=” 커널 파라메터로 변경된다. domain 속성에 있는 때 relax_domain_level 값을 지정하지 않을 때 이 디폴트 값을 사용할 수 있다.

 

set_domain_attribute()

kernel/sched/topology.c

static void set_domain_attribute(struct sched_domain *sd,
                                 struct sched_domain_attr *attr)
{
        int request;

        if (!attr || attr->relax_domain_level < 0) {
                if (default_relax_domain_level < 0)
                        return;
                else
                        request = default_relax_domain_level;
        } else
                request = attr->relax_domain_level;
        if (request < sd->level) {
                /* turn off idle balance on this domain */
                sd->flags &= ~(SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
        } else {
                /* turn on idle balance on this domain */
                sd->flags |= (SD_BALANCE_WAKE|SD_BALANCE_NEWIDLE);
        }
}

스케줄링 도메인의 레벨이 요청한 relax 도메인 레벨보다 큰 경우 wake 및 newidle 플래그를 클리어하고 그렇지 않은 경우 설정한다. 요청한 relax 도메인 레벨이 없는 경우 디폴트 relax 도메인 레벨 값을 사용하여 판단한다.

  • 코드 라인 6~10에서 부트업 과정에서 이 함수에 진입 시에는 attr 값이 null로 진입한다. null로 진입하거나 속성에 부여된 레벨 값이 0보다 작은 경우 default_relax_domain_level 값이 설정되지 않았으면 함수를 빠져나간다. 만일 default_relax_domain_level 값이 이미 설정된 경우 그 값을 기준으로 삼기 위해 request에 대입한다.
  • 코드 라인 11~12에서 속성값이 주어진 경우 request에 대입한다.
  • 코드 라인 13~15에서 스케줄링 도메인의 레벨이 요청한 레벨보다 큰 경우 이 도메인에서 SD_BALANCE_WAKE와 SD_BALANCE_NEWIDLE 플래그를 제거한다.
  • 코드 라인 16~19에서 그 외의 경우 이 도메인에 SD_BALANCE_WAKE와 SD_BALANCE_NEWIDLE 플래그를 설정한다.

 

setup_relax_domain_level()

kernel/sched/topology.c

static int default_relax_domain_level = -1;
int sched_domain_level_max;

static int __init setup_relax_domain_level(char *str)
{
        if (kstrtoint(str, 0, &default_relax_domain_level))
                pr_warn("Unable to set relax_domain_level\n");

        return 1;
}
__setup("relax_domain_level=", setup_relax_domain_level);

“relax_domain_level=” 값을 파싱하여 전역 변수 default_relax_domain_level에 대입한다. (초기 값은 -1)

 


스케줄 그룹 구성

 

build_sched_groups()

kernel/sched/topology.c

/*
 * build_sched_groups will build a circular linked list of the groups
 * covered by the given span, will set each group's ->cpumask correctly,
 * and will initialize their ->sgc.
 *
 * Assumes the sched_domain tree is fully constructed
 */
static int
build_sched_groups(struct sched_domain *sd, int cpu)
{
        struct sched_group *first = NULL, *last = NULL;
        struct sd_data *sdd = sd->private;
        const struct cpumask *span = sched_domain_span(sd);
        struct cpumask *covered;
        int i;

        lockdep_assert_held(&sched_domains_mutex);
        covered = sched_domains_tmpmask;

        cpumask_clear(covered);

        for_each_cpu_wrap(i, span, cpu) {
                struct sched_group *sg;

                if (cpumask_test_cpu(i, covered))
                        continue;

                sg = get_group(i, sdd);

                cpumask_or(covered, covered, sched_group_span(sg));

                if (!first)
                        first = sg;
                if (last)
                        last->next = sg;
                last = sg;
        }
        last->next = first;
        sd->groups = first;

        return 0;
}

 

 

kernel/sched/core.c

/*
 * build_sched_groups will build a circular linked list of the groups
 * covered by the given span, and will set each group's ->cpumask correctly,
 * and ->cpu_capacity to 0.
 *
 * Assumes the sched_domain tree is fully constructed
 */
static int
build_sched_groups(struct sched_domain *sd, int cpu)
{
        struct sched_group *first = NULL, *last = NULL;
        struct sd_data *sdd = sd->private;
        const struct cpumask *span = sched_domain_span(sd);
        struct cpumask *covered;
        int i;

        get_group(cpu, sdd, &sd->groups);
        atomic_inc(&sd->groups->ref);

        if (cpu != cpumask_first(span))
                return 0;

        lockdep_assert_held(&sched_domains_mutex);
        covered = sched_domains_tmpmask;

        cpumask_clear(covered);

        for_each_cpu(i, span) {
                struct sched_group *sg;
                int group, j;

                if (cpumask_test_cpu(i, covered))
                        continue;

                group = get_group(i, sdd, &sg);
                cpumask_setall(sched_group_mask(sg));

                for_each_cpu(j, span) {
                        if (get_group(j, sdd, NULL) != group)
                                continue;

                        cpumask_set_cpu(j, covered);
                        cpumask_set_cpu(j, sched_group_cpus(sg));
                }

                if (!first)
                        first = sg;
                if (last)
                        last->next = sg;
                last = sg;
        }
        last->next = first;

        return 0;
}

요청한 스케줄도메인 레벨의 첫 번째 cpu 번호가 주어진 경우 해당 스케줄 그룹들을 구성한다.

  • 코드 라인 13에서 요청한 스케줄 도메인의 span cpu 비트마스크를 알아온다.
  • 코드 라인 17에서 요청한 cpu의 스케줄 도메인을 스케줄그룹과 연결하고 연결된 스케줄 그룹의 cpu 번호를 알아온다.
    • 예) rpi2: 4개의 cpu에 대해 이 함수를 매번 호출하면 cpu#0~cpu#3까지 스케줄 도메인 모두 cpu#0의 스케줄 그룹과 연결된다.
  • 코드 라인 18에서 요청한 도메인 내에서 요청한 cpu가 사용할 스케줄 그룹의 참조 카운터를 1 증가시킨다.
    • 예) rpi2: 4개의 cpu에 대해 이 루틴을 반복하면 모두 cpu#0의 스케줄 그룹을 사용하므로 참조카운터는 4가된다.
  • 코드 라인 20~21에서 현재 도메인의 첫 번째 cpu에 대해서만 설정을 허용한다.
    • 예) rpi2: cpu#0만 허용한다.
  • 코드 라인 24~26에서 임시로 사용할 cpu 비트마스크인 covered를 클리어한다.
  • 코드 라인 28~33에서 도메인에 속한 cpu를 순회하는데 covered에 설정된 cpu는 skip한다.
    • 예) rpi2: 모든 cpu가 스케줄 그룹이 따로 따로 만들어지므로 skip하지 않는다.
  • 코드 라인 35~36에서 cpu에 해당하는 도메인과 연결된 스케줄 그룹을 알아오고 스케줄 그룹 캐패시티의 cpumask를 cpu 수만큼 설정한다.
    • 예) rpi2: 모든 cpu가 스케줄 그룹을 각각 가지고 있고 해당 스케줄 그룹 캐피시티의 cpumask를 0xf(4개 cpu)로 설정한다.
  • 코드 라인 38~44에서 도메인에 해당하는 cpu 수만큼 순회할 때 같은 스케줄링 그룹을 사용하는 cpu가 아니면 skip한다.  skip하지 않은 경우 covered 및 스케줄 그룹의 cpumas 에 해당 cpu 비트를 설정한다.
  • 코드 라인 46~50서 도메인내의 각 스케줄 그룹을 연결한다.
    • rpi2: 4개의 스케줄 그룹을 연결한다.
  • 코드 라인 52에서 단방향 환형 리스트로 연결한다.

 

다음 그림은 build_sched_groups() 함수가 각 도메인에 대해 처리되는 모습을 보여준다.

  • cpu#0에 대해 요청할 때 4개의 스케줄 그룹이 구성된다. 그 외 cpu#1~#3번까지는 참조 카운터만 증가시킨다.

 

다음 그림은 도메인과 스케줄 그룹간의 관계를 보여준다.

 

get_group()

kernel/sched/core.c

static int get_group(int cpu, struct sd_data *sdd, struct sched_group **sg)
{
        struct sched_domain *sd = *per_cpu_ptr(sdd->sd, cpu);
        struct sched_domain *child = sd->child;

        if (child)
                cpu = cpumask_first(sched_domain_span(child));

        if (sg) {
                *sg = *per_cpu_ptr(sdd->sg, cpu);
                (*sg)->sgc = *per_cpu_ptr(sdd->sgc, cpu);
                atomic_set(&(*sg)->sgc->ref, 1); /* for claim_allocations */
        }

        return cpu;
}

child 스케줄링 그룹이 없으면 요청한 cpu, child 스케줄링 그룹이 있는 경우 해당 스케줄링 도메인에 소속된 첫 cpu에 해당하는 스케줄링 그룹을 알아와서 출력 인수에 대입하고 cpu 번호를 반환한다.

  • 코드 라인 3~4에서 요청한 cpu의 스케줄링 도메인과 child 도메인을 알아온다.
  • 코드 라인 6~7에서 child 도메인이 있는 경우 child 도메인에 소속된 첫 번째 cpu를 알아온다.
  • 코드 라인 9~13에서 출력 인수 스케줄링 그룹이 지정된 경우 요청한 cpu의 스케줄링 그룹을 알아와서 출력 인수에 저장한다. 그런 후 스케줄링 그룹의 capacity도 지정하고 참조 카운터를 1 증가시킨다.

 

다음 그림은 2단계의 스케줄 도메인 토플로지가 구성된 상태에서 하위 단계부터 상위 단계까지 get_group()을 모두 호출한 경우를 보여준다.

 

claim_allocations()

/*
 * NULL the sd_data elements we've used to build the sched_domain and
 * sched_group structure so that the subsequent __free_domain_allocs()
 * will not free the data we're using.
 */
static void claim_allocations(int cpu, struct sched_domain *sd)
{
        struct sd_data *sdd = sd->private;

        WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
        *per_cpu_ptr(sdd->sd, cpu) = NULL;

        if (atomic_read(&(*per_cpu_ptr(sdd->sds, cpu))->ref))
                *per_cpu_ptr(sdd->sds, cpu) = NULL;

        if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
                *per_cpu_ptr(sdd->sg, cpu) = NULL;

        if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
                *per_cpu_ptr(sdd->sgc, cpu) = NULL;
}

 

 

kernel/sched/core.c

/*
 * NULL the sd_data elements we've used to build the sched_domain and
 * sched_group structure so that the subsequent __free_domain_allocs()
 * will not free the data we're using.
 */
static void claim_allocations(int cpu, struct sched_domain *sd)
{
        struct sd_data *sdd = sd->private;

        WARN_ON_ONCE(*per_cpu_ptr(sdd->sd, cpu) != sd);
        *per_cpu_ptr(sdd->sd, cpu) = NULL;

        if (atomic_read(&(*per_cpu_ptr(sdd->sg, cpu))->ref))
                *per_cpu_ptr(sdd->sg, cpu) = NULL;

        if (atomic_read(&(*per_cpu_ptr(sdd->sgc, cpu))->ref))
                *per_cpu_ptr(sdd->sgc, cpu) = NULL;
}

스케줄링 도메인 트리에서 이미 구성하여 사용할 요청한 pcu의 sd, sg, sgc 등에 대해 나중에 삭제하지 못하게 null을 대입한다.

 


Overlap 스케줄 그룹 구성

 

/*
 * NUMA topology (first read the regular topology blurb below)
 *
 * Given a node-distance table, for example:
 *
 *   node   0   1   2   3
 *     0:  10  20  30  20
 *     1:  20  10  20  30
 *     2:  30  20  10  20
 *     3:  20  30  20  10
 *
 * which represents a 4 node ring topology like:
 *
 *   0 ----- 1
 *   |       |
 *   |       |
 *   |       |
 *   3 ----- 2
 *
 * We want to construct domains and groups to represent this. The way we go
 * about doing this is to build the domains on 'hops'. For each NUMA level we
 * construct the mask of all nodes reachable in @level hops.
 *
 * For the above NUMA topology that gives 3 levels:
 *
 * NUMA-2       0-3             0-3             0-3             0-3
 *  groups:     {0-1,3},{1-3}   {0-2},{0,2-3}   {1-3},{0-1,3}   {0,2-3},{0-2}
 *
 * NUMA-1       0-1,3           0-2             1-3             0,2-3
 *  groups:     {0},{1},{3}     {0},{1},{2}     {1},{2},{3}     {0},{2},{3}
 *
 * NUMA-0       0               1               2               3
 *
 *
 * As can be seen; things don't nicely line up as with the regular topology.
 * When we iterate a domain in child domain chunks some nodes can be
 * represented multiple times -- hence the "overlap" naming for this part of
 * the topology.
 *
 * In order to minimize this overlap, we only build enough groups to cover the
 * domain. For instance Node-0 NUMA-2 would only get groups: 0-1,3 and 1-3.
 *
 * Because:
 *
 *  - the first group of each domain is its child domain; this
 *    gets us the first 0-1,3
 *  - the only uncovered node is 2, who's child domain is 1-3.
 *
 * However, because of the overlap, computing a unique CPU for each group is
 * more complicated. Consider for instance the groups of NODE-1 NUMA-2, both
 * groups include the CPUs of Node-0, while those CPUs would not in fact ever
 * end up at those groups (they would end up in group: 0-1,3).
 *
 * To correct this we have to introduce the group balance mask. This mask
 * will contain those CPUs in the group that can reach this group given the
 * (child) domain tree.
 *
 * With this we can once again compute balance_cpu and sched_group_capacity
 * relations.
 *
 * XXX include words on how balance_cpu is unique and therefore can be
 * used for sched_group_capacity links.
 *
 *
 * Another 'interesting' topology is:
 *
 *   node   0   1   2   3
 *     0:  10  20  20  30
 *     1:  20  10  20  20
 *     2:  20  20  10  20
 *     3:  30  20  20  10
 *
 * Which looks a little like:
 *
 *   0 ----- 1
 *   |     / |
 *   |   /   |
 *   | /     |
 *   2 ----- 3
 *
 * This topology is asymmetric, nodes 1,2 are fully connected, but nodes 0,3
 * are not.
 *
 * This leads to a few particularly weird cases where the sched_domain's are
 * not of the same number for each CPU. Consider:
 *
 * NUMA-2       0-3                                             0-3
 *  groups:     {0-2},{1-3}                                     {1-3},{0-2}
 *
 * NUMA-1       0-2             0-3             0-3             1-3
 *
 * NUMA-0       0               1               2               3
 *
 */

 

build_overlap_sched_groups()

kernel/sched/topology.c

static int
build_overlap_sched_groups(struct sched_domain *sd, int cpu)
{
        struct sched_group *first = NULL, *last = NULL, *sg;
        const struct cpumask *span = sched_domain_span(sd);
        struct cpumask *covered = sched_domains_tmpmask;
        struct sd_data *sdd = sd->private;
        struct sched_domain *sibling;
        int i;

        cpumask_clear(covered);

        for_each_cpu_wrap(i, span, cpu) {
                struct cpumask *sg_span;

                if (cpumask_test_cpu(i, covered))
                        continue;

                sibling = *per_cpu_ptr(sdd->sd, i);

                /*
                 * Asymmetric node setups can result in situations where the
                 * domain tree is of unequal depth, make sure to skip domains
                 * that already cover the entire range.
                 *
                 * In that case build_sched_domains() will have terminated the
                 * iteration early and our sibling sd spans will be empty.
                 * Domains should always include the CPU they're built on, so
                 * check that.
                 */
                if (!cpumask_test_cpu(i, sched_domain_span(sibling)))
                        continue;

                sg = build_group_from_child_sched_domain(sibling, cpu);
                if (!sg)
                        goto fail;

                sg_span = sched_group_span(sg);
                cpumask_or(covered, covered, sg_span);

                init_overlap_sched_group(sd, sg);

                if (!first)
                        first = sg;
                if (last)
                        last->next = sg;
                last = sg;
                last->next = first;
        }
        sd->groups = first;

        return 0;

fail:
        free_sched_groups(first, 0);

        return -ENOMEM;
}

 

build_group_from_child_sched_domain()

kernel/sched/topology.c

/*
 * XXX: This creates per-node group entries; since the load-balancer will
 * immediately access remote memory to construct this group's load-balance
 * statistics having the groups node local is of dubious benefit.
 */
static struct sched_group *
build_group_from_child_sched_domain(struct sched_domain *sd, int cpu)
{
        struct sched_group *sg;
        struct cpumask *sg_span;

        sg = kzalloc_node(sizeof(struct sched_group) + cpumask_size(),
                        GFP_KERNEL, cpu_to_node(cpu));

        if (!sg)
                return NULL;

        sg_span = sched_group_span(sg);
        if (sd->child)
                cpumask_copy(sg_span, sched_domain_span(sd->child));
        else
                cpumask_copy(sg_span, sched_domain_span(sd));

        atomic_inc(&sg->ref);
        return sg;
}

 

init_overlap_sched_group()

kernel/sched/topology.c

static void init_overlap_sched_group(struct sched_domain *sd,
                                     struct sched_group *sg)
{
        struct cpumask *mask = sched_domains_tmpmask2;
        struct sd_data *sdd = sd->private;
        struct cpumask *sg_span;
        int cpu;

        build_balance_mask(sd, sg, mask);
        cpu = cpumask_first_and(sched_group_span(sg), mask);

        sg->sgc = *per_cpu_ptr(sdd->sgc, cpu);
        if (atomic_inc_return(&sg->sgc->ref) == 1)
                cpumask_copy(group_balance_mask(sg), mask);
        else
                WARN_ON_ONCE(!cpumask_equal(group_balance_mask(sg), mask));

        /*
         * Initialize sgc->capacity such that even if we mess up the
         * domains and no possible iteration will get us here, we won't
         * die on a /0 trap.
         */
        sg_span = sched_group_span(sg);
        sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
        sg->sgc->min_capacity = SCHED_CAPACITY_SCALE;
        sg->sgc->max_capacity = SCHED_CAPACITY_SCALE;
}

 

build_balance_mask()

kernel/sched/topology.c

/*
 * Build the balance mask; it contains only those CPUs that can arrive at this
 * group and should be considered to continue balancing.
 *
 * We do this during the group creation pass, therefore the group information
 * isn't complete yet, however since each group represents a (child) domain we
 * can fully construct this using the sched_domain bits (which are already
 * complete).
 */
static void
build_balance_mask(struct sched_domain *sd, struct sched_group *sg, struct cpumask *mask)
{
        const struct cpumask *sg_span = sched_group_span(sg);
        struct sd_data *sdd = sd->private;
        struct sched_domain *sibling;
        int i;

        cpumask_clear(mask);

        for_each_cpu(i, sg_span) {
                sibling = *per_cpu_ptr(sdd->sd, i);

                /*
                 * Can happen in the asymmetric case, where these siblings are
                 * unused. The mask will not be empty because those CPUs that
                 * do have the top domain _should_ span the domain.
                 */
                if (!sibling->child)
                        continue;

                /* If we would not end up here, we can't continue from here */
                if (!cpumask_equal(sg_span, sched_domain_span(sibling->child)))
                        continue;

                cpumask_set_cpu(i, mask);
        }

        /* We must not have empty masks here */
        WARN_ON_ONCE(cpumask_empty(mask));
}

 


스케줄 그룹 Capacity

init_sched_groups_capacity()

kernel/sched/topology.c

/*
 * Initialize sched groups cpu_capacity.
 *
 * cpu_capacity indicates the capacity of sched group, which is used while
 * distributing the load between different sched groups in a sched domain.
 * Typically cpu_capacity for all the groups in a sched domain will be same
 * unless there are asymmetries in the topology. If there are asymmetries,
 * group having more cpu_capacity will pickup more load compared to the
 * group having less cpu_capacity.
 */
static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
{
        struct sched_group *sg = sd->groups;

        WARN_ON(!sg);

        do {
                int cpu, max_cpu = -1;

                sg->group_weight = cpumask_weight(sched_group_span(sg));

                if (!(sd->flags & SD_ASYM_PACKING))
                        goto next;

                for_each_cpu(cpu, sched_group_span(sg)) {
                        if (max_cpu < 0)
                                max_cpu = cpu;
                        else if (sched_asym_prefer(cpu, max_cpu))
                                max_cpu = cpu;
                }
                sg->asym_prefer_cpu = max_cpu;

next:
                sg = sg->next;
        } while (sg != sd->groups);

        if (cpu != group_balance_cpu(sg))
                return;

        update_group_capacity(sd, cpu);
}

 

 

kernel/sched/core.c

/*
 * Initialize sched groups cpu_capacity.
 *
 * cpu_capacity indicates the capacity of sched group, which is used while
 * distributing the load between different sched groups in a sched domain.
 * Typically cpu_capacity for all the groups in a sched domain will be same
 * unless there are asymmetries in the topology. If there are asymmetries,
 * group having more cpu_capacity will pickup more load compared to the
 * group having less cpu_capacity.
 */
static void init_sched_groups_capacity(int cpu, struct sched_domain *sd)
{
        struct sched_group *sg = sd->groups;

        WARN_ON(!sg);

        do {
                sg->group_weight = cpumask_weight(sched_group_cpus(sg));
                sg = sg->next;
        } while (sg != sd->groups);

        if (cpu != group_balance_cpu(sg))
                return;

        update_group_capacity(sd, cpu);
        atomic_set(&sg->sgc->nr_busy_cpus, sg->group_weight);
}

요청한 cpu의 스케줄링 도메인에 대한 스케줄링 그룹 capacity를 초기화한다.

  • 코드 라인 17~20에서 연결된 스케줄링 그룹들을 순회하며 스케줄링 그룹에 참여하는 cpu들 수를 sg->group_weight에 대입한다.
  • 코드 라인 22~23에서 그룹의 첫 번째 cpu가 아니면 함수를 빠져나간다.
  • 코드 라인 25에서 스케줄링 그룹 capacity를 최초 설정한다.
  • 코드 라인 26에서 스케줄링 그룹에 소속된 cpu 수를 스케줄링 그룹 capacity의 멤버 nr_busy_cpus에 대입한다.

 

 

sched_asym_prefer()

kernel/sched/sched.h

tatic inline bool sched_asym_prefer(int a, int b)
{
        return arch_asym_cpu_priority(a) > arch_asym_cpu_priority(b);
}

 

 

group_balance_cpu()

kernel/sched/topology.c

/*
 * Return the canonical balance CPU for this group, this is the first CPU
 * of this group that's also in the balance mask.
 *
 * The balance mask are all those CPUs that could actually end up at this
 * group. See build_balance_mask().
 *
 * Also see should_we_balance().
 */
int group_balance_cpu(struct sched_group *sg)
{
        return cpumask_first(group_balance_mask(sg));
}

 

 

kernel/sched/core.c

/*
 * Return the canonical balance cpu for this group, this is the first cpu
 * of this group that's also in the iteration mask.
 */
int group_balance_cpu(struct sched_group *sg)
{
        return cpumask_first_and(sched_group_cpus(sg), sched_group_mask(sg));
}

스케줄링 그룹과 스케줄링 그룹 capacity의 cpumask에 포함된 cpu들 중 가장 첫 cpu를 반환한다.

 

update_group_capacity()

kernel/sched/fair.c

void update_group_capacity(struct sched_domain *sd, int cpu)
{
        struct sched_domain *child = sd->child;
        struct sched_group *group, *sdg = sd->groups;
        unsigned long capacity, min_capacity, max_capacity;
        unsigned long interval;

        interval = msecs_to_jiffies(sd->balance_interval);
        interval = clamp(interval, 1UL, max_load_balance_interval);
        sdg->sgc->next_update = jiffies + interval;

        if (!child) {
                update_cpu_capacity(sd, cpu);
                return;
        }

        capacity = 0;
        min_capacity = ULONG_MAX;
        max_capacity = 0;

        if (child->flags & SD_OVERLAP) {
                /*
                 * SD_OVERLAP domains cannot assume that child groups
                 * span the current group.
                 */

                for_each_cpu(cpu, sched_group_span(sdg)) {
                        struct sched_group_capacity *sgc;
                        struct rq *rq = cpu_rq(cpu);

                        /*
                         * build_sched_domains() -> init_sched_groups_capacity()
                         * gets here before we've attached the domains to the
                         * runqueues.
                         *
                         * Use capacity_of(), which is set irrespective of domains
                         * in update_cpu_capacity().
                         *
                         * This avoids capacity from being 0 and
                         * causing divide-by-zero issues on boot.
                         */
                        if (unlikely(!rq->sd)) {
                                capacity += capacity_of(cpu);
                        } else {
                                sgc = rq->sd->groups->sgc;
                                capacity += sgc->capacity;
                        }

                        min_capacity = min(capacity, min_capacity);
                        max_capacity = max(capacity, max_capacity);
                }
        } else  {
                /*
                 * !SD_OVERLAP domains can assume that child groups
                 * span the current group.
                 */

                group = child->groups;
                do {
                        struct sched_group_capacity *sgc = group->sgc;

                        capacity += sgc->capacity;
                        min_capacity = min(sgc->min_capacity, min_capacity);
                        max_capacity = max(sgc->max_capacity, max_capacity);
                        group = group->next;
                } while (group != child->groups);
        }

        sdg->sgc->capacity = capacity;
        sdg->sgc->min_capacity = min_capacity;
        sdg->sgc->max_capacity = max_capacity;
}

 

 

 

void update_group_capacity(struct sched_domain *sd, int cpu)
{
        struct sched_domain *child = sd->child;
        struct sched_group *group, *sdg = sd->groups;
        unsigned long capacity, capacity_orig;
        unsigned long interval;

        interval = msecs_to_jiffies(sd->balance_interval);
        interval = clamp(interval, 1UL, max_load_balance_interval);
        sdg->sgc->next_update = jiffies + interval;

        if (!child) {
                update_cpu_capacity(sd, cpu);
                return;
        }

        capacity_orig = capacity = 0;

        if (child->flags & SD_OVERLAP) {
                /*
                 * SD_OVERLAP domains cannot assume that child groups
                 * span the current group.
                 */

                for_each_cpu(cpu, sched_group_cpus(sdg)) {
                        struct sched_group_capacity *sgc;
                        struct rq *rq = cpu_rq(cpu);

                        /*
                         * build_sched_domains() -> init_sched_groups_capacity()
                         * gets here before we've attached the domains to the
                         * runqueues.
                         *
                         * Use capacity_of(), which is set irrespective of domains
                         * in update_cpu_capacity().
                         *
                         * This avoids capacity/capacity_orig from being 0 and
                         * causing divide-by-zero issues on boot.
                         *
                         * Runtime updates will correct capacity_orig.
                         */
                        if (unlikely(!rq->sd)) {
                                capacity_orig += capacity_of(cpu);
                                capacity += capacity_of(cpu);
                                continue;
                        }

                        sgc = rq->sd->groups->sgc;
                        capacity_orig += sgc->capacity_orig;
                        capacity += sgc->capacity;
                }
        } else  {
                /*
                 * !SD_OVERLAP domains can assume that child groups
                 * span the current group.
                 */

                group = child->groups;
                do {
                        capacity_orig += group->sgc->capacity_orig;
                        capacity += group->sgc->capacity;
                        group = group->next;
                } while (group != child->groups);
        }

        sdg->sgc->capacity_orig = capacity_orig;
        sdg->sgc->capacity = capacity;
}

요청한 cpu의 스케줄링 도메인에 해당하는 스케줄 그룹 capacity를 갱신한다.

  • 코드 라인 8~10에서 스케줄링 도메인의 로드 밸런싱 주기(ms)를 jiffies 단위로 변환하고 이 값이 1 ~ 0.1초에 해당하는 jiffies 범위로 제한시킨 후 다음 갱신 주기로 설정한다.
  • 코드 라인 12~15에서 child 스케줄링 도메인이 없는 최하위 스케줄링 도메인의 경우 cpu capacity를 갱신하고 함수를 빠져나간다.
  • 코드 라인 19~25에서 child 스케줄링 도메인에 SD_OVERLAP 플래그가 설정된 경우(NUMA) 스케줄링 그룹의 cpu들을 대상으로 순회한다.
  • 코드 라인 42~46에서 해당 cpu의 런큐에 스케줄링 도메인이 지정되지 않은 경우 rq->cpu_capacity 값을 더한다.
  • 코드 라인 48~50에서 해당 cpu의 런큐가 가리키는 스케줄링 도메인에서 스케줄 그룹 capacity 값들을 더한다.
  • 코드 라인 52~64에서 그 외의 경우 child 도메인의 그룹부터 최하위까지 capacity_orig와 capacity 값들을 모두 더해온다.
  • 코드 라인 66~67에서 요청한 cpu의 도메인에 대한 스케줄링 그룹 capacity에 대입한다.

 

update_cpu_capacity()

kernel/sched/fair.c

static void update_cpu_capacity(struct sched_domain *sd, int cpu)
{
        unsigned long capacity = scale_rt_capacity(sd, cpu);
        struct sched_group *sdg = sd->groups;

        cpu_rq(cpu)->cpu_capacity_orig = arch_scale_cpu_capacity(cpu);

        if (!capacity)
                capacity = 1;

        cpu_rq(cpu)->cpu_capacity = capacity;
        sdg->sgc->capacity = capacity;
        sdg->sgc->min_capacity = capacity;
        sdg->sgc->max_capacity = capacity;
}

 

 

 

static void update_cpu_capacity(struct sched_domain *sd, int cpu)
{
        unsigned long capacity = SCHED_CAPACITY_SCALE;
        struct sched_group *sdg = sd->groups;

        if (sched_feat(ARCH_CAPACITY))
                capacity *= arch_scale_cpu_capacity(sd, cpu);
        else
                capacity *= default_scale_cpu_capacity(sd, cpu);

        capacity >>= SCHED_CAPACITY_SHIFT;

        sdg->sgc->capacity_orig = capacity;

        if (sched_feat(ARCH_CAPACITY))
                capacity *= arch_scale_freq_capacity(sd, cpu);
        else
                capacity *= default_scale_capacity(sd, cpu);

        capacity >>= SCHED_CAPACITY_SHIFT;

        capacity *= scale_rt_capacity(cpu);
        capacity >>= SCHED_CAPACITY_SHIFT;

        if (!capacity)
                capacity = 1;

        cpu_rq(cpu)->cpu_capacity = capacity;
        sdg->sgc->capacity = capacity;
}

cpu 런큐 및 스케줄 그룹에 cpu capacity를 대입한다.

  • 코드 라인 6~13에서 아키텍처의 성능에 따른 현재 capacity 값을 산출하여 스케줄링 그룹의 capacity_orig에 대입한다.
    • CAPACITY feature에 따라 처리 방법이 다르다. (이 기능은 4.4 이후에서 사용하지 않는다.)
    • arm: 디바이스 트리를 파싱하고 아키텍처별 capacity 값을 찾아 사용한다.
    • arm64의 경우 디바이스 트리의 “capacity-dmips-mhz”  값에서 직접 capacity 값을 파싱하여 사용한다.
    • 그 외의 아키텍처: 기본값인 1024를 사용하는데 SMT 도메인의 경우 1024에서 15% 향상된 1178을 스레드 수 만큼 나눈 값을 사용한다.
      • SD_SHARE_CPUCAPACITY 플래그가 적용된 SMT 스케줄 도메인에서 smt_gain(1178) / span_weight를 사용한다.
  • 코드 라인 15~20에서 capacity 값에 다시 한 번 scale capacity를 적용하는데 현재 커널에서는 아무런 영향을 끼치지 않는다.
    • 왜 이러한 코드가 남아 있는지 확인이 필요한다.
  • 코드 라인 22~23에서 capacity에 rt에 사용한 시간 비율 만큼을 줄여서 적용한다.
    • rt 타임: irq 처리에 사용한 시간 + rt 태스크 수행 시간 + deadline 태스크 수행시간
  • 코드 라인 25~26에서 capacity 값이 0인 경우 1을 대입한다. (1로 나눌 때 방지하기 위한)
  • 코드 라인 28~29에서 산출된 capacity를 런큐 및 스케줄 그룹의 capacity 값에 대입한다.

 

scale_rt_capacity()

kernel/sched/fair.c

static unsigned long scale_rt_capacity(struct sched_domain *sd, int cpu)
{
        struct rq *rq = cpu_rq(cpu);
        unsigned long max = arch_scale_cpu_capacity(cpu);
        unsigned long used, free;
        unsigned long irq;

        irq = cpu_util_irq(rq);

        if (unlikely(irq >= max))
                return 1;

        used = READ_ONCE(rq->avg_rt.util_avg);
        used += READ_ONCE(rq->avg_dl.util_avg);

        if (unlikely(used >= max))
                return 1;

        free = max - used;

        return scale_irq_capacity(free, irq, max);
}

 

 

 

static unsigned long scale_rt_capacity(int cpu)
{
        struct rq *rq = cpu_rq(cpu);
        u64 total, available, age_stamp, avg;
        s64 delta;

        /*
         * Since we're reading these variables without serialization make sure
         * we read them once before doing sanity checks on them.
         */ 
        age_stamp = ACCESS_ONCE(rq->age_stamp);
        avg = ACCESS_ONCE(rq->rt_avg);
        delta = __rq_clock_broken(rq) - age_stamp;

        if (unlikely(delta < 0))
                delta = 0;

        total = sched_avg_period() + delta;

        if (unlikely(total < avg)) {
                /* Ensures that capacity won't end up being negative */
                available = 0;
        } else {
                available = total - avg;
        }

        if (unlikely((s64)total < SCHED_CAPACITY_SCALE))
                total = SCHED_CAPACITY_SCALE;

        total >>= SCHED_CAPACITY_SHIFT; 

        return div_u64(available, total);
}

rt를 제외한 비율을 최대 1024의 capacity 단위로 반환한다. (1024=1.0)

  • total = 0.5초 + delta(rq->clock – rq->age_stamp)
  • return = (total – rq->rt_avg) / (total / 1024))

 

  • 코드 라인 11~13에서 런큐의 현재 시각과 age_stamp의 차를 delta로 구한다. rt_avg에는 irq 타임과 rt 및 dl 태스크에 사용한 시간이 누적되어 있다.
  • 코드 라인 15~16에서 delta가 0보다 작은 경우 0으로 대입한다.
  • 코드 라인 18에서 스케줄 평균 타임값으로 500,000,000 (0.5초) + delta를 total에 대입한다.
    • 디폴트 값: “/proc/sys/kernel/sysctl_sched_time_avg_ms”=1000 기간의 절반을 평균 값으로 사용한다.
  • 코드 라인 20~25에서 available = tatal – avg (최소 값은 0으로 제한)
  • 코드 라인 27~30에서 total = total / 1024 (최소 값은 1로 제한)
  • 코드 라인 32에서 available / total 값을 반환한다.

 

다음 그림은 rt를 제외한 순수 cfs 태스크에 사용한 비율을 알아내는 모습을 보여준다

  • rt time = irq time + rt task time + dl task time

 

 


cpu를 스케줄 도메인에 연결

cpu_attach_domain()

kernel/sched/topology.c

/*
 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
 * hold the hotplug lock.
 */
static void
cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
{
        struct rq *rq = cpu_rq(cpu);
        struct sched_domain *tmp;

        /* Remove the sched domains which do not contribute to scheduling. */
        for (tmp = sd; tmp; ) {
                struct sched_domain *parent = tmp->parent;
                if (!parent)
                        break;

                if (sd_parent_degenerate(tmp, parent)) {
                        tmp->parent = parent->parent;
                        if (parent->parent)
                                parent->parent->child = tmp;
                        /*
                         * Transfer SD_PREFER_SIBLING down in case of a
                         * degenerate parent; the spans match for this
                         * so the property transfers.
                         */
                        if (parent->flags & SD_PREFER_SIBLING)
                                tmp->flags |= SD_PREFER_SIBLING;
                        destroy_sched_domain(parent);
                } else
                        tmp = tmp->parent;
        }

        if (sd && sd_degenerate(sd)) {
                tmp = sd;
                sd = sd->parent;
                destroy_sched_domain(tmp);
                if (sd)
                        sd->child = NULL;
        }

        sched_domain_debug(sd, cpu);

        rq_attach_root(rq, rd);
        tmp = rq->sd;
        rcu_assign_pointer(rq->sd, sd);
        dirty_sched_domain_sysctl(cpu);
        destroy_sched_domains(tmp);

        update_top_cache_domain(cpu);
}

 

 

kernel/sched/core.c

/*
 * Attach the domain 'sd' to 'cpu' as its base domain. Callers must
 * hold the hotplug lock.
 */
static void
cpu_attach_domain(struct sched_domain *sd, struct root_domain *rd, int cpu)
{
        struct rq *rq = cpu_rq(cpu);
        struct sched_domain *tmp;

        /* Remove the sched domains which do not contribute to scheduling. */
        for (tmp = sd; tmp; ) {
                struct sched_domain *parent = tmp->parent;
                if (!parent)
                        break;

                if (sd_parent_degenerate(tmp, parent)) {
                        tmp->parent = parent->parent;
                        if (parent->parent)
                                parent->parent->child = tmp;
                        /*
                         * Transfer SD_PREFER_SIBLING down in case of a
                         * degenerate parent; the spans match for this
                         * so the property transfers.
                         */
                        if (parent->flags & SD_PREFER_SIBLING)
                                tmp->flags |= SD_PREFER_SIBLING;
                        destroy_sched_domain(parent, cpu);
                } else
                        tmp = tmp->parent;
        }

        if (sd && sd_degenerate(sd)) {
                tmp = sd;
                sd = sd->parent;
                destroy_sched_domain(tmp, cpu);
                if (sd)
                        sd->child = NULL;
        }

        sched_domain_debug(sd, cpu);

        rq_attach_root(rq, rd);
        tmp = rq->sd;
        rcu_assign_pointer(rq->sd, sd);
        destroy_sched_domains(tmp, cpu);

        update_top_cache_domain(cpu);
}

요청한 도메인 트리에서 스케줄링에 참여할 필요가 없는 스케줄링 도메인들은 해제하고 루트 도메인에 현재 cpu의 런큐를 연결한다.

  • 코드 라인 12~15에서 요청한 스케줄 도메인부터 최상위 스케줄 도메인까지 순회한다.
  • 코드 라인 17~28에서 부모 스케줄 도메인이 스케줄링에 참여할 필요가 없는 경우 부모 스케줄 도메인을 제거한다. 부모의 플래그에 SD_PREFER_SIBLING이 있는 경우 자식에게 물려준다. (조부모 스케줄 도메인과 자식 도메인을 연결한다)
  • 코드 라인 33~39에서 요청한 자식 스케줄링 도메인도 스케줄링에 참여할 필요가 없는 경우 제거한다.
  • 코드 라인 43에서 요청한 cpu의 런큐를 루트 도메인에 연결한다.
  • 코드 라인 44~45에서 기존 런큐에 연결되어 있었던 스케줄 도메인을 tmp에 대입하고 요청한 스케줄 도메인을 런큐에 연결한다.
  • 코드 라인 46에서 기존 런큐에 연결되어 있었던 스케줄 도메인부터 최상위까지 모두 rcu 방법으로 제거한다.
  • 코드 라인 48에서 최상위 캐시 도메인을 갱신한다.

 

sd_parent_degenerate()

kernel/sched/topology.c

static int
sd_parent_degenerate(struct sched_domain *sd, struct sched_domain *parent)
{
        unsigned long cflags = sd->flags, pflags = parent->flags;

        if (sd_degenerate(parent))
                return 1;

        if (!cpumask_equal(sched_domain_span(sd), sched_domain_span(parent)))
                return 0;

        /* Flags needing groups don't count if only 1 group in parent */
        if (parent->groups == parent->groups->next) {
                pflags &= ~(SD_LOAD_BALANCE |
                                SD_BALANCE_NEWIDLE |
                                SD_BALANCE_FORK |
                                SD_BALANCE_EXEC |
                                SD_SHARE_CPUCAPACITY |
                                SD_SHARE_PKG_RESOURCES |
                                SD_PREFER_SIBLING |
                                SD_SHARE_POWERDOMAIN);
                if (nr_node_ids == 1)
                        pflags &= ~SD_SERIALIZE;
        }
        if (~cflags & pflags)
                return 0;

        return 1;
}

요청한 스케줄 도메인 또는 부모 스케줄 도메인이 스케줄링에 참여할 필요가 없는 경우 true(1)를 반환한다. (true인 경우 바깥 루틴에서 이 스케줄링 도메인을 제거한다)

  • 코드 라인 4에서 자식 스케줄 도메인의 플래그와, 부모 스케줄 도메인의 플래그를 알아온다.
  • 코드 라인 6~7에서 부모 스케줄 도메인이 스케줄링에 참여할 필요가 없는 경우 true(1)를 반환한다.
  • 코드 라인 9~10에서 부모 스케줄 도메인과 자식 스케줄 도메인에 참여한 cpu 들이 같은 경우 false(0)를 반환한다.
  • 코드 라인 13~21에서 부모 스케줄 도메인에 그룹이 하나밖에 없는 경우 부모 플래그에서 밸런싱에 관련된 플래그를 모두 제거한다.
  • 코드 라인 22~23에서 그리고 노드가 1개인 경우 NUMA 로드밸런싱에서 사용하는 SD_SERIALIZE 플래그도 제거한다.
  • 코드 라인 25~26에서 자식 스케줄 도메인용 플래그에 없는 설정이 부모 플래그에 있는 경우 false(0)를 반환한다.
  • 코드 라인 28에서 true(1)를 반환한다.

 

sd_degenerate()

kernel/sched/topology.c

static int sd_degenerate(struct sched_domain *sd)
{
        if (cpumask_weight(sched_domain_span(sd)) == 1)
                return 1;

        /* Following flags need at least 2 groups */
        if (sd->flags & (SD_LOAD_BALANCE |
                         SD_BALANCE_NEWIDLE |
                         SD_BALANCE_FORK |
                         SD_BALANCE_EXEC |
                         SD_SHARE_CPUCAPACITY |
                         SD_ASYM_CPUCAPACITY |
                         SD_SHARE_PKG_RESOURCES |
                         SD_SHARE_POWERDOMAIN)) {
                if (sd->groups != sd->groups->next)
                        return 0;
        }

        /* Following flags don't use groups */
        if (sd->flags & (SD_WAKE_AFFINE))
                return 0;

        return 1;
}

스케줄 도메인에 속한 cpu가 1개이거나 스케줄링에 참여를 할 수 없는 상태인 경우 true(1)를 반환한다. (true인 경우 바깥 루틴에서 이 스케줄링 도메인을 제거한다)

  • 코드 라인 3~4에서 요청한 스케줄링 도메인에 속한 cpu가 1개뿐이면 true(1)를 반환한다.
  • 코드 라인 7~17에서 스케줄 도메인의 플래그가 밸런싱을 요구하는데 다음 그룹이 있으면 false(0)을 반환한다.
  • 코드 라인 20~21에서 스케줄 도메인에서 SD_WAKE_AFFINE 플래그가 사용된 경우 false(0)을 반환한다.
  • 코드 라인 23에서 true(1)를 반환한다.

 

캐시 스케줄링 도메인 갱신

update_top_cache_domain()

kernel/sched/topology.c

static void update_top_cache_domain(int cpu)
{
        struct sched_domain_shared *sds = NULL;
        struct sched_domain *sd;
        int id = cpu;
        int size = 1;

        sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
        if (sd) {
                id = cpumask_first(sched_domain_span(sd));
                size = cpumask_weight(sched_domain_span(sd));
                sds = sd->shared;
        }

        rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
        per_cpu(sd_llc_size, cpu) = size;
        per_cpu(sd_llc_id, cpu) = id;
        rcu_assign_pointer(per_cpu(sd_llc_shared, cpu), sds);

        sd = lowest_flag_domain(cpu, SD_NUMA);
        rcu_assign_pointer(per_cpu(sd_numa, cpu), sd);

        sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
        rcu_assign_pointer(per_cpu(sd_asym_packing, cpu), sd);

        sd = lowest_flag_domain(cpu, SD_ASYM_CPUCAPACITY);
        rcu_assign_pointer(per_cpu(sd_asym_cpucapacity, cpu), sd);
}

 

 

kernel/sched/core.c

static void update_top_cache_domain(int cpu)
{
        struct sched_domain *sd;
        struct sched_domain *busy_sd = NULL;
        int id = cpu;
        int size = 1;

        sd = highest_flag_domain(cpu, SD_SHARE_PKG_RESOURCES);
        if (sd) {
                id = cpumask_first(sched_domain_span(sd));
                size = cpumask_weight(sched_domain_span(sd));
                busy_sd = sd->parent; /* sd_busy */
        }
        rcu_assign_pointer(per_cpu(sd_busy, cpu), busy_sd);

        rcu_assign_pointer(per_cpu(sd_llc, cpu), sd);
        per_cpu(sd_llc_size, cpu) = size;
        per_cpu(sd_llc_id, cpu) = id;

        sd = lowest_flag_domain(cpu, SD_NUMA);
        rcu_assign_pointer(per_cpu(sd_numa, cpu), sd);

        sd = highest_flag_domain(cpu, SD_ASYM_PACKING);
        rcu_assign_pointer(per_cpu(sd_asym, cpu), sd);
}

캐시 스케줄링 도메인들을 갱신한다. (sd_busy, sd_llc, sd_numa, sd_asym)

  • 코드 라인 8~18에서 SD_SHARE_PKG_RESOURCES 플래그가 설정된 가장 상위의 스케줄링 도메인을 알아와서 요청한 cpu의 sd_llc에 찾은 스케줄링 도메인을 대입한다. 그 부모 스케줄링 도메인을 요청한 cpu의 sd_busy에 대입한다.
  • 코드 라인 17~18에서 요청한 cpu의 sd_llc_size 및 sd_llc_id에 sd_llc 도메인이 커버하는 cpu 수와 첫 cpu 번호를 대입한다.
  • 코드 라인 20~21에서 SD_NUMA 플래그가 설정된 가장 하위의 스케줄 도메인을 알아와서 요청한 cpu의 sd_numa에 찾은 하위 스케줄 도메인을 대입한다.
  • 코드 라인 23~24에서 SD_ASYM_PACKING 플래그가 설정된 가장 상위의 스케줄 도메인을 알아와서 요청한 cpu의 sd_asym에 찾은 스케줄 도메인을 대입한다.
    • powerpc 아키텍처에서만 사용한다.

 

다음 그림은 캐시 스케줄링 도메인들을 갱신하는 모습을 보여준다.

 

highest_flag_domain()

kernel/sched/sched.h

/**
 * highest_flag_domain - Return highest sched_domain containing flag.
 * @cpu:        The cpu whose highest level of sched domain is to
 *              be returned.
 * @flag:       The flag to check for the highest sched_domain
 *              for the given cpu.
 *
 * Returns the highest sched_domain of a cpu which contains the given flag.
 */
static inline struct sched_domain *highest_flag_domain(int cpu, int flag)
{
        struct sched_domain *sd, *hsd = NULL;

        for_each_domain(cpu, sd) {
                if (!(sd->flags & flag))
                        break;
                hsd = sd;
        }

        return hsd;
}

요청한 플래그가 설정된 가장 상위의 스케줄 도메인을 반환한다.

 

lowest_flag_domain()

kernel/sched/sched.h

static inline struct sched_domain *lowest_flag_domain(int cpu, int flag)
{
        struct sched_domain *sd;

        for_each_domain(cpu, sd) {
                if (sd->flags & flag)
                        break;
        }

        return sd;
}

요청한 플래그가 설정된 가장 하위의 스케줄 도메인을 반환한다.

 


sysctl for sched_domain

다음은 rock960(4 little + 2 big) 보드가 2 단계 MC+DIE 스케줄 도메인 토플로지 레벨을 사용한 모습을 알아볼 수 있다.

$ cd /proc/sys/kernel/sched_domain
$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 .
dr-xr-xr-x 1 root root 0 Nov  4  2016 ..
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu1
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu2
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu3
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu4
dr-xr-xr-x 1 root root 0 Nov 27 21:39 cpu5

$ cd cpu0
$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 .
dr-xr-xr-x 1 root root 0 Nov 27 21:39 ..
dr-xr-xr-x 1 root root 0 Nov 27 21:39 domain0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 domain1

$ cd domain0
$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 .
dr-xr-xr-x 1 root root 0 Nov 27 21:39 ..
-rw-r--r-- 1 root root 0 Nov 27 21:39 busy_factor
-rw-r--r-- 1 root root 0 Nov 27 21:39 busy_idx
-rw-r--r-- 1 root root 0 Nov 27 21:39 cache_nice_tries
-rw-r--r-- 1 root root 0 Nov 27 21:39 flags
-rw-r--r-- 1 root root 0 Nov 27 21:39 forkexec_idx
dr-xr-xr-x 1 root root 0 Nov 27 21:39 group0
dr-xr-xr-x 1 root root 0 Nov 27 21:39 group1
dr-xr-xr-x 1 root root 0 Nov 27 21:39 group2
dr-xr-xr-x 1 root root 0 Nov 27 21:39 group3
-rw-r--r-- 1 root root 0 Nov 27 21:39 idle_idx
-rw-r--r-- 1 root root 0 Nov 27 21:39 imbalance_pct
-rw-r--r-- 1 root root 0 Nov 27 21:39 max_interval
-rw-r--r-- 1 root root 0 Nov 27 21:39 max_newidle_lb_cost
-rw-r--r-- 1 root root 0 Nov 27 21:39 min_interval
-r--r--r-- 1 root root 0 Nov 27 21:39 name
-rw-r--r-- 1 root root 0 Nov 27 21:39 newidle_idx
-rw-r--r-- 1 root root 0 Nov 27 21:39 wake_idx

$ cat name
MC

$ cat ../domain1/name
DIE

 

다음은 rpi4(4 big) 보드가 1 단계 DIE 스케줄 도메인 토플로지 레벨만을 사용한 모습을 알아볼 수 있다.

  • rpi2~4 보드와 같이 동일한 cpu capacity를 사용하는 경우 CONFIG_SCHED_MC 커널 옵션에 따라 다음과 같다.
    • 사용하지 않는 경우 DIE 단계만을 구성한다.
    • 사용한 경우 MC 단계만을 구성한다.
$ cd /proc/sys/kernel/sched_domain
$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:52 .
dr-xr-xr-x 1 root root 0 Jan 29  2018 ..
dr-xr-xr-x 1 root root 0 Nov 27 21:52 cpu0
dr-xr-xr-x 1 root root 0 Nov 27 21:52 cpu1
dr-xr-xr-x 1 root root 0 Nov 27 21:52 cpu2
dr-xr-xr-x 1 root root 0 Nov 27 21:52 cpu3

$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:52 .
dr-xr-xr-x 1 root root 0 Nov 27 21:52 ..
dr-xr-xr-x 1 root root 0 Nov 27 21:52 domain0

$ ls -la
total 0
dr-xr-xr-x 1 root root 0 Nov 27 21:52 .
dr-xr-xr-x 1 root root 0 Nov 27 21:52 ..
-rw-r--r-- 1 root root 0 Nov 27 21:52 busy_factor
-rw-r--r-- 1 root root 0 Nov 27 21:52 busy_idx
-rw-r--r-- 1 root root 0 Nov 27 21:52 cache_nice_tries
-rw-r--r-- 1 root root 0 Nov 27 21:52 flags
-rw-r--r-- 1 root root 0 Nov 27 21:52 forkexec_idx
-rw-r--r-- 1 root root 0 Nov 27 21:52 idle_idx
-rw-r--r-- 1 root root 0 Nov 27 21:52 imbalance_pct
-rw-r--r-- 1 root root 0 Nov 27 21:52 max_interval
-rw-r--r-- 1 root root 0 Nov 27 21:52 max_newidle_lb_cost
-rw-r--r-- 1 root root 0 Nov 27 21:52 min_interval
-r--r--r-- 1 root root 0 Nov 27 21:52 name
-rw-r--r-- 1 root root 0 Nov 27 21:52 newidle_idx
-rw-r--r-- 1 root root 0 Nov 27 21:52 wake_idx

$ cat name
DIE

 


구조체

sched_domain_topology_level 구조체

struct sched_domain_topology_level {
        sched_domain_mask_f mask;
        sched_domain_flags_f sd_flags;
        int                 flags;
        int                 numa_level;
        struct sd_data      data;
#ifdef CONFIG_SCHED_DEBUG
        char                *name;
#endif
};
  • mask
    • cpumask 값을 읽어오는 함수
  • sd_flags
    • 스케줄 도메인 플래그를 읽어오는 함수
  • flags
    • 플래그
  • numa_level
    • 누마 레벨. NUMA가 아닌 경우 0
  • data
    • sd_data 구조체
  • *name
    • arm 도메인 단계명(“GMC” -> “MC” -> “DIE” -> “NUMA”)
      • rpi2: 1단계로 구성하고 “DIE”만 사용한다.
    • arm64  및 디폴트 도메인 단계명(“SMT” -> “MC” -> “DIE” -> “NUMA”)

 

sched_domain 구조체

include/linux/sched.h

struct sched_domain {
        /* These fields must be setup */
        struct sched_domain __rcu *parent;      /* top domain must be null terminated */
        struct sched_domain __rcu *child;       /* bottom domain must be null terminated */
        struct sched_group *groups;     /* the balancing groups of the domain */
        unsigned long min_interval;     /* Minimum balance interval ms */
        unsigned long max_interval;     /* Maximum balance interval ms */
        unsigned int busy_factor;       /* less balancing by factor if busy */
        unsigned int imbalance_pct;     /* No balance until over watermark */
        unsigned int cache_nice_tries;  /* Leave cache hot tasks for # tries */

        int nohz_idle;                  /* NOHZ IDLE status */
        int flags;                      /* See SD_* */
        int level;

        /* Runtime fields. */
        unsigned long last_balance;     /* init to jiffies. units in jiffies */
        unsigned int balance_interval;  /* initialise to 1. units in ms. */
        unsigned int nr_balance_failed; /* initialise to 0 */

        /* idle_balance() stats */
        u64 max_newidle_lb_cost;
        unsigned long next_decay_max_lb_cost;

        u64 avg_scan_cost;              /* select_idle_sibling */

#ifdef CONFIG_SCHEDSTATS
        /* load_balance() stats */
        unsigned int lb_count[CPU_MAX_IDLE_TYPES];
        unsigned int lb_failed[CPU_MAX_IDLE_TYPES];
        unsigned int lb_balanced[CPU_MAX_IDLE_TYPES];
        unsigned int lb_imbalance[CPU_MAX_IDLE_TYPES];
        unsigned int lb_gained[CPU_MAX_IDLE_TYPES];
        unsigned int lb_hot_gained[CPU_MAX_IDLE_TYPES];
        unsigned int lb_nobusyg[CPU_MAX_IDLE_TYPES];
        unsigned int lb_nobusyq[CPU_MAX_IDLE_TYPES];

        /* Active load balancing */
        unsigned int alb_count;
        unsigned int alb_failed;
        unsigned int alb_pushed;

        /* SD_BALANCE_EXEC stats */
        unsigned int sbe_count;
        unsigned int sbe_balanced;
        unsigned int sbe_pushed;

        /* SD_BALANCE_FORK stats */
        unsigned int sbf_count;
        unsigned int sbf_balanced;
        unsigned int sbf_pushed;

        /* try_to_wake_up() stats */
        unsigned int ttwu_wake_remote;
        unsigned int ttwu_move_affine;
        unsigned int ttwu_move_balance;
#endif
#ifdef CONFIG_SCHED_DEBUG
        char *name;
#endif
        union {
                void *private;          /* used during construction */
                struct rcu_head rcu;    /* used during destruction */
        };
        struct sched_domain_shared *shared;

        unsigned int span_weight;
        /*
         * Span of all CPUs in this domain.
         *
         * NOTE: this field is variable length. (Allocated dynamically
         * by attaching extra space to the end of the structure,
         * depending on how many CPUs the kernel has booted up with)
         */
        unsigned long span[0];
};

 

 

struct sched_domain {
        /* These fields must be setup */
        struct sched_domain *parent;    /* top domain must be null terminated */
        struct sched_domain *child;     /* bottom domain must be null terminated */
        struct sched_group *groups;     /* the balancing groups of the domain */
        unsigned long min_interval;     /* Minimum balance interval ms */
        unsigned long max_interval;     /* Maximum balance interval ms */
        unsigned int busy_factor;       /* less balancing by factor if busy */
        unsigned int imbalance_pct;     /* No balance until over watermark */
        unsigned int cache_nice_tries;  /* Leave cache hot tasks for # tries */
        unsigned int busy_idx;
        unsigned int idle_idx;
        unsigned int newidle_idx;
        unsigned int wake_idx;
        unsigned int forkexec_idx;
        unsigned int smt_gain;

        int nohz_idle;                  /* NOHZ IDLE status */
        int flags;                      /* See SD_* */
        int level;

        /* Runtime fields. */
        unsigned long last_balance;     /* init to jiffies. units in jiffies */
        unsigned int balance_interval;  /* initialise to 1. units in ms. */
        unsigned int nr_balance_failed; /* initialise to 0 */

        /* idle_balance() stats */
        u64 max_newidle_lb_cost;
        unsigned long next_decay_max_lb_cost;
  • *parent
    • 부모 스케줄 도메인. 더 이상 부모가 없는 최상위는 null
  • *child
    • 자식 스케줄 도메인. 더 이상 자식이 없는 최하위는 null
  • *groups
    • 로드 밸런싱에 참여하는 스케줄 그룹
  • min_interval
    • 최소 밸런싱 주기(ms)
  • max_interval
    • 최대 밸런싱 주기(ms)
  • busy_factor
    • 디폴트로 32를 사용한다.
  • imbalance_pct
    • 로컬과 기존 cpu의 로드 비교 시 둘 중 하나의 cpu 로드에 imbalance_pct 가중치를 부여한다. 밸런싱 목적에 따라 imbalance_pct 가중치가 붙는 cpu가 달라진다.
    • 디폴트로 125(%)를 사용한다.
    • SD_SHARE_CPUCAPACITY 플래그를 사용하는 SMT 도메인에서 110(%)을 사용한다.
    • SD_SHARE_PKG_RESOURCES 플래그를 사용하여 패키지 내에서 캐시를 공유하는 MC및 SMT 도메인에서 117(%)을 사용한다.
  • cache_nice_tries
    • SD_SHARE_PKG_RESOURCES 플래그를 사용하여 패키지 내에서 캐시를 공유하는 MC및 SMT 도메인에서 1을 사용한다.
    • 디폴트 값은 0이다.
  • busy_idx
    • 정규 스케줄 틱마다 로드밸런스 산출 시 busy cpu에 대해 사용하는 cpu_load[]에 사용할 인덱스
  • ilde_idx
    • 정규 스케줄 틱마다 로드밸런스 산출 시 busy cpu에 대해 사용하는 cpu_load[]에 사용할 인덱스
  • newidle_idx
    • idle 진입 시 사용하는 cpu_load[]에 사용할 인덱스
  • wake_idx
    • wake된 경우 사용하는 cpu_load[]에 사용할 인덱스
  • forkexec_idx
    • fork 되거나 실행 시 사용하는 cpu_load[]에 사용할 인덱스
  • smt_gain
    • h/w 스레드를 사용하는 SMT 도메인에서 SD_SHARE_CPUCAPACITY 플래그를 사용하여 상위 MC 도메인의 core 성능을 그 하위 도메인에서 cpu 성능을 공유하여 사용하는데 원래 값의 115%를 사용하게한다.
      • x86또는 powerpc 등이 사용하고 아직 arm, arm64는 h/w 스레드를 지원하지 않고 있다.
    • 현재 cpu 로드 값 1024를 기준으로 15%를 향상시켜 1178을 사용한다.
  • nohz_idle
    • nohz idle 밸런싱에 사용한다. nohz idle인 경우 1이고 그 외의 경우 0이다.
  • flags
    • 도메인 특성을 나타내는 플래그들로 이 글의 앞 부분에서 별도로 설명하였다.
  • level
    • 최하위 도메인은 0부터 시작. (SMT -> MC -> DIE -> NUMA)
  • last_balance
    • 밸런싱을 수행한 마지막 시각(jiffies)
  • balance_interval
    • 밸런싱 인터벌. 초기값 1(ms)
  • nr_balance_failed
    • 실패한 밸런싱 수
  • max_newidle_lb_cost
    • 도메인에 대해 idle 밸런싱을 시도 할 때마다 소요된 최대 idle 밸런싱 시간이 갱신된다.
    • 이 값은 1초에 1%씩 감소(decay) 한다.
    • 평균 idle 시간이 이 값보다 작은 경우 밸런싱을 시도하지 않게한다.
  • next_decay_max_lb_cost
    • 1초에 한 번씩 max_newidle_lb_cost를 decay를 하게 하기 위해 사용한다.
  • *name
    • 도메인 명
  • *private
    • 생성 시 sd_data를 가리킨다.
  • *rcu
    • 해제 시 rcu 링크로 사용한다.
  • span_weight
    • 도메인에 포함된 cpu 수
  • span[0]
    • 도메인에 포함된 cpu 비트마스크

 

 

#ifdef CONFIG_SCHEDSTATS
        /* load_balance() stats */
        unsigned int lb_count[CPU_MAX_IDLE_TYPES];
        unsigned int lb_failed[CPU_MAX_IDLE_TYPES];
        unsigned int lb_balanced[CPU_MAX_IDLE_TYPES];
        unsigned int lb_imbalance[CPU_MAX_IDLE_TYPES];
        unsigned int lb_gained[CPU_MAX_IDLE_TYPES];
        unsigned int lb_hot_gained[CPU_MAX_IDLE_TYPES];
        unsigned int lb_nobusyg[CPU_MAX_IDLE_TYPES];
        unsigned int lb_nobusyq[CPU_MAX_IDLE_TYPES];

        /* Active load balancing */
        unsigned int alb_count;
        unsigned int alb_failed;
        unsigned int alb_pushed;

        /* SD_BALANCE_EXEC stats */
        unsigned int sbe_count;
        unsigned int sbe_balanced;
        unsigned int sbe_pushed;

        /* SD_BALANCE_FORK stats */
        unsigned int sbf_count;
        unsigned int sbf_balanced;
        unsigned int sbf_pushed;

        /* try_to_wake_up() stats */
        unsigned int ttwu_wake_remote;
        unsigned int ttwu_move_affine;
        unsigned int ttwu_move_balance;
#endif
#ifdef CONFIG_SCHED_DEBUG
        char *name;
#endif
        union {
                void *private;          /* used during construction */
                struct rcu_head rcu;    /* used during destruction */
        };

        unsigned int span_weight;
        /*
         * Span of all CPUs in this domain.
         *
         * NOTE: this field is variable length. (Allocated dynamically
         * by attaching extra space to the end of the structure,
         * depending on how many CPUs the kernel has booted up with)
         */
        unsigned long span[0];
};

 

 

 

참고

 

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다