Scheduler -11- (Scheduling Domain)

 

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

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

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

 

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

다음과 같이 사용하는 스케줄러에 따라  로드밸런싱을 하는 방법이 달라진다.  cpu의 검색 순서는 스케줄러 모두 cpu affinity를 표현한 스케줄링 도메인을 사용한다.

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

 

cpu 토플로지

armv7 & armv8 시스템은 CPU 토플로지를 지원한다. armv7 시스템은 CONFIG_ARM_CPU_TOPOLOGY 커널 옵션을 사용하고, armv8 시스템은 항상 지원한다.

  • 디바이스 트리(arm64) 및 MPIDR 레지스터를 읽어 다음 단계를 구분한다.
    • thread_id
      • 아직 arm에서는 하드웨어 스레드를 지원하지 않아 항상 -1을 담는다.
    • core_id
    • socket_id
  • cpu topology 정보는 cpu 상태가 변경될 때마다 갱신된다.
  • cpu topology 정보는 스케줄 도메인과 PM(Power Management) 시스템에서 사용된다.
  • kernel v4.11-rc1에서 cpu topology 관련 코드들이 kernel/sched/topology.c 코드로 이전하였다.

 

arch/arm/boot/dts/hip04.dtsi

        cpus {
                #address-cells = <1>;
                #size-cells = <0>;

                cpu-map {
                        cluster0 {
                                core0 {
                                        cpu = <&CPU0>;
                                };
                                core1 {
                                        cpu = <&CPU1>;
                                };
                        };
                        cluster1 {
                                core0 {
                                        cpu = <&CPU2>;
                                };
                                core1 {
                                        cpu = <&CPU3>;
                                };
                        };
                CPU0: cpu@0 {
                        device_type = "cpu";
                        compatible = "arm,cortex-a15";
                        reg = <0>;
                };

                (...생략...)

 

cpu capacity scale management

코어별로 상대적 능력치를 저장해두어 로드밸런스에 사용한다. (32bit arm only)

  • 디바이스 트리의 cpu 노드에서 읽은 cpu 디바이스명으로 커널의 table_efficiency[] 테이블의 값과 매치한 efficiency 값을 “clock-frequency” 값을 메가(M, >> 20)단위로 변환한 후 곱하여 cpu_capacity(cpu)에 설정한다. 설정된 값들은 scale(1024) 값이 적용된 상태다.
  • cpu efficiency 값은 cpu별로 다음과 같다.
    • “arm,cortex-a15”, 3891
    • “arm,cortex-a7”, 2048
  • 예) compatible=”arm,cortex-a15″;   clock-frequency=<1500000000>; 의 cpu capacity 값과 middle_capacity 값은?
    • cpu_capacity = 3891 * (1,500,000,000 >> 20) = 5,564,130
  • 예) rpi2: compatible=”arm,cortex-a7″;   clock-frequency=<800000000>; 의 cpu capacity 값과 middle_capacity 값은?
    • cpu_capacity = 2048 * (800,000,000 >> 20) = 1,560,576

 

arch/arm/boot/dts/bcm2709.dtsi

       cpus {
                #address-cells = <0x1>;
                #size-cells = <0x0>;

                v7_cpu0: cpu@0 {
                        device_type = "cpu";
                        compatible = "arm,cortex-a7";
                        reg = <0xf00>;
                        clock-frequency = <800000000>;
                };

                (...생략...)

 

평균 capacity 값 산출

(4 * max) < (3 * (max + min))을 계산하였을 때 아래 결과로 결정된다.

  • true: (min + max) >> 11
  • false: (max / 3) >> 9 + 1

 

  • 예) 1500Mhz cortex-a15 x 4에서 평균 capacity는?
    • min=max=5,564,130
    • 11,128,260 >> 11 = 5433
  • 예) 800Mhz cortex-a7 x 4에서 평균 capacity는?
    • min=max=1,560,576
    • 3,121,152 >> 11 = 1524
  • 예) 1500Mhz cortex-a15 x 4, 800Mhz cortex-a7 x 4에서 평균 capacity는?
    • min=1,560,576    max=5,564,130
    • 5,564,130 / 3 = 1,854,710 >> 9 + 1 = 3623

 

cpu_scale 산출

산출된 cpu_capacity 값을 평균 capacity로 나누어 각 cpu별로 cpu_scale을 산출한다.

  • 예) 1500Mhz cortex-a15 x 4개의 각 cpu capacity
    • 5,564,130 / 5433 = 1024 (1.0)
  • 예) 800Mhz cortex-a7 x 4개의 각 cpu capacity
    • 1,560,576 / 1524 = 1024 (1.0)
  • 예) 1500Mhz cortex-a15 x 4, 800Mhz cortex-a7 x 4
    • 5,564,130 / 3623 = 1535 (1.49) -> cortex-a15
    • 1,560,576 / 3623 = 430 (0.41) -> cortex-a7

 

스케줄링 도메인 토플로지

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 토플로지를 만들때 다음과 같은 순서로 단계별로 구성한다.

  • SMT
    • l1 캐시를 공유하는 cpu에 대해 더 우선권을 준다. (virtual core)
    • 캐시를 플러시할 필요가 없으므로 가장 비용이 저렴하다. (relax 도메인)
    • arm64는 아직 활용하지 않는다.
    • CONFIG_SCHED_SMT 커널 옵션 사용
  • MC
    • 그 다음으로 l2 캐시를 공유하는 클러스터 내의 cpu에 더 우선권을 준다.
    • CONFIG_SCHED_MC 커널 옵션 사용
  • DIE
    • 그 다음으로 (l3 캐시를 공유하는) 같은 die를 사용하는 cpu에 더 우선권을 준다.
  • NUMA
    • 같은 NUMA 노드를 사용하는 cpu에 더 우선권을 준다.
    • 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_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
    • 이 도메인이 누마 도메인이다.
    • 복잡도에 따라 1개 이상의 도메인 레벨을 구성할 수 있다.

 

cpu 토플로지 초기화

 

다음 그림은 cpu 토플로지를 초기화하는 모습을 보여준다. 커널 부트업 및 나머지 cpu들이 on될 때마다 store_cpu_topology() 함수가 호출된다.

 

init_cpu_topology()

arch/arm/kernel/topology.c

/*
 * init_cpu_topology is called at boot when only one cpu is running
 * which prevent simultaneous write access to cpu_topology array
 */
void __init init_cpu_topology(void)
{
        unsigned int cpu;

        /* init core mask and capacity */
        for_each_possible_cpu(cpu) {
                struct cputopo_arm *cpu_topo = &(cpu_topology[cpu]);

                cpu_topo->thread_id = -1;
                cpu_topo->core_id =  -1;
                cpu_topo->socket_id = -1;
                cpumask_clear(&cpu_topo->core_sibling);
                cpumask_clear(&cpu_topo->thread_sibling);

                set_capacity_scale(cpu, SCHED_CAPACITY_SCALE);
        }
        smp_wmb();

        parse_dt_topology();

        /* Set scheduler topology descriptor */
        set_sched_topology(arm_topology);
}

cpu_topology[]를 초기화하고 디바이스 트리의 cpu 노드를 파싱하여 cpu_capacity[]와 cpu_scale[]을 산출한다.

  • 코드 라인 10~17에서 possible cpu 수 만큼 순회하며 cpu_topology[]를 초기화한다.
  • 코드 라인 19에서 cpu_scale[]을 기본 값 1024로 초기화한다.
  • 코드 라인 23에서 디바이스 트리의 cpu 노드를 파싱하여 cpu_capacity[]와 middle_capacity를 산출하다.
    • arm64의 경우 cpu_map 노드를 파싱한다
  • 코드 라인 26에서 아래 arm_topology[]를 스케줄링 도메인 토플로지로 선택한다.

 

아키텍처별 cpu 토플로지 레벨

kernel/sched/core.c

struct sched_domain_topology_level *sched_domain_topology = default_topology;
  • arm은 default_topology를 사용하지 않고 arm_topology를 사용한다.

 

default_topology[]

kernel/sched/core.c

/*      
 * Topology list, bottom-up.
 */
static struct sched_domain_topology_level default_topology[] = {
#ifdef CONFIG_SCHED_SMT
        { cpu_smt_mask, cpu_smt_flags, SD_INIT_NAME(SMT) },
#endif
#ifdef CONFIG_SCHED_MC
        { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif
        { cpu_cpu_mask, SD_INIT_NAME(DIE) },
        { NULL, },
};

디폴트 토플로지는 최대 3단계인 SMT -> MC -> DIE 레벨까지 구성할 수 있다. (numa는 별도 구성)

 

arm_topology[]

arch/arm/kernel/topology.c

static struct sched_domain_topology_level arm_topology[] = {
#ifdef CONFIG_SCHED_MC
        { cpu_corepower_mask, cpu_corepower_flags, SD_INIT_NAME(GMC) },
        { cpu_coregroup_mask, cpu_core_flags, SD_INIT_NAME(MC) },
#endif
        { cpu_cpu_mask, SD_INIT_NAME(DIE) },
        { NULL, },
};

arm 토플로지는 최대 3단계인 GMC -> MC -> DIE 레벨까지 구성할 수 있다. (numa는 별도 구성)

  • rpi2: DIE 단계만 사용한다.

 

디바이스 트리 파싱

parse_dt_topology()

arch/arm/kernel/topology.c

/*
 * Iterate all CPUs' descriptor in DT and compute the efficiency
 * (as per table_efficiency). Also calculate a middle efficiency
 * as close as possible to  (max{eff_i} - min{eff_i}) / 2
 * This is later used to scale the cpu_capacity field such that an
 * 'average' CPU is of middle capacity. Also see the comments near
 * table_efficiency[] and update_cpu_capacity().
 */
static void __init parse_dt_topology(void)
{
        const struct cpu_efficiency *cpu_eff;
        struct device_node *cn = NULL;
        unsigned long min_capacity = ULONG_MAX;
        unsigned long max_capacity = 0;
        unsigned long capacity = 0;
        int cpu = 0;

        __cpu_capacity = kcalloc(nr_cpu_ids, sizeof(*__cpu_capacity),
                                 GFP_NOWAIT);

        for_each_possible_cpu(cpu) {
                const u32 *rate;
                int len;

                /* too early to use cpu->of_node */
                cn = of_get_cpu_node(cpu, NULL);
                if (!cn) {
                        pr_err("missing device node for CPU %d\n", cpu);
                        continue;
                }

                for (cpu_eff = table_efficiency; cpu_eff->compatible; cpu_eff++)
                        if (of_device_is_compatible(cn, cpu_eff->compatible))
                                break;

                if (cpu_eff->compatible == NULL)
                        continue;

디바이스 트리의 cpu 노드를 파싱하여 cpu_capacity[]와 middle_capacity를 산출하다.

  • 코드 라인 18~19에서 cpu 수 만큼 배열로 사용할 수 있도록 __cpu_capacity를 할당한다.
  • 코드 라인 21~30에서 possible cpu 수 만큼 순회하며 cpu 노드를 알아온다.
  • 코드 라인 32~37에서 table_efficiency[]를 순회하며 cpu 디바이스명(compatible)과 매치되는 항목을 찾는다. 없으면 skip 한다.

 

                rate = of_get_property(cn, "clock-frequency", &len);
                if (!rate || len != 4) {
                        pr_err("%s missing clock-frequency property\n",
                                cn->full_name);
                        continue;
                }

                capacity = ((be32_to_cpup(rate)) >> 20) * cpu_eff->efficiency;

                /* Save min capacity of the system */
                if (capacity < min_capacity)
                        min_capacity = capacity;

                /* Save max capacity of the system */
                if (capacity > max_capacity)
                        max_capacity = capacity;
         
                cpu_capacity(cpu) = capacity;
        }

        /* If min and max capacities are equals, we bypass the update of the
         * cpu_scale because all CPUs have the same capacity. Otherwise, we
         * compute a middle_capacity factor that will ensure that the capacity
         * of an 'average' CPU of the system will be as close as possible to
         * SCHED_CAPACITY_SCALE, which is the default value, but with the
         * constraint explained near table_efficiency[].
         */
        if (4*max_capacity < (3*(max_capacity + min_capacity)))
                middle_capacity = (min_capacity + max_capacity)
                                >> (SCHED_CAPACITY_SHIFT+1);
        else
                middle_capacity = ((max_capacity / 3)
                                >> (SCHED_CAPACITY_SHIFT-1)) + 1;

}
  • 코드 라인 1~6에서 “clock-frequency” 속성을 읽어온다. 없으면 skip 한다.
  • 코드 라인 8에서 읽어온 값을 메가(M)단위로 변환하기 위해 20bit를 우측 시프트하여 제거한 후 efficiency 값과 곱한다.
    • 예) rpi2: rate = 800000000 (800Mhz), efficiency=2048
      • capacity = 800000000 / 1048576 *  2048 = 762 * 2048 = 1,560,576
  • 코드 라인 11~12에서 최소 capacity 값을 갱신한다.
  • 코드 라인 15~16에서 최대 capacity 값을 갱신한다.
  • 코드 라인 18에서 cpu_capacity[]에 산출된 capacity 값을 대입한다.
  • 코드 라인 28~30에서 min 값과 max 값이 차이가 3배 이하인 경우 min과 max의 중간 값을 scale(1024) 만큼 나눈다.
    • 예) middle_capacity = 5933775(1.6G cortex-a15) + 2342912(1.2G cortex-a7) / 2 / 1024 = 4041
  • 코드 라인 31~33에서 min 값과 max 값이 3배를 초과한 경우 max 값의 2/3배 값을 scale(1024) 만큼 나눈다.
    • 예) middle_capacity = 5933775(1.6G cortex-a15) * (2/3) / 1024 + 1 = 3864

 

set_sched_topology()

kernel/sched/core.c

void set_sched_topology(struct sched_domain_topology_level *tl)
{
        sched_domain_topology = tl;
}

스케줄 도메인 토플로지를 설정한다.

 

부팅된 cpu의 토플로지 적용

store_cpu_topology()

arch/arm/kernel/topology.c

/*
 * store_cpu_topology is called at boot when only one cpu is running
 * and with the mutex cpu_hotplug.lock locked, when several cpus have booted,
 * which prevents simultaneous write access to cpu_topology array
 */
void store_cpu_topology(unsigned int cpuid)
{
        struct cputopo_arm *cpuid_topo = &cpu_topology[cpuid];
        unsigned int mpidr;

        /* If the cpu topology has been already set, just return */
        if (cpuid_topo->core_id != -1)
                return;

        mpidr = read_cpuid_mpidr();

        /* create cpu topology mapping */
        if ((mpidr & MPIDR_SMP_BITMASK) == MPIDR_SMP_VALUE) {
                /*
                 * This is a multiprocessor system
                 * multiprocessor format & multiprocessor mode field are set
                 */

                if (mpidr & MPIDR_MT_BITMASK) {
                        /* core performance interdependency */
                        cpuid_topo->thread_id = MPIDR_AFFINITY_LEVEL(mpidr, 0);
                        cpuid_topo->core_id = MPIDR_AFFINITY_LEVEL(mpidr, 1);
                        cpuid_topo->socket_id = MPIDR_AFFINITY_LEVEL(mpidr, 2);
                } else {
                        /* largely independent cores */
                        cpuid_topo->thread_id = -1;
                        cpuid_topo->core_id = MPIDR_AFFINITY_LEVEL(mpidr, 0);
                        cpuid_topo->socket_id = MPIDR_AFFINITY_LEVEL(mpidr, 1);
                }
        } else {
                /*
                 * This is an uniprocessor system
                 * we are in multiprocessor format but uniprocessor system
                 * or in the old uniprocessor format
                 */
                cpuid_topo->thread_id = -1;
                cpuid_topo->core_id = 0;
                cpuid_topo->socket_id = -1;
        }

        update_siblings_masks(cpuid);

        update_cpu_capacity(cpuid);

        pr_info("CPU%u: thread %d, cpu %d, socket %d, mpidr %x\n",
                cpuid, cpu_topology[cpuid].thread_id,
                cpu_topology[cpuid].core_id,
                cpu_topology[cpuid].socket_id, mpidr);
}

요청한 cpu에 대한 cpu_topology[]에 구성한다.

  • 코드 라인 12~13에서 core_id가 이미 설정된 경우 함수를 빠져나간다.
  • 코드 라인 15에서 cpu affinity 레벨을 파악하기 위해 mpidr 레지스터 값을 읽어온다.
  • 코드 라인 18에서 mpidr 값에서 smp 시스템을 인식한 경우
  • 코드 라인 24~28에서 mpidr.mt에서 h/w 멀티스레드를 인식한 경우 3단계 affinity 값들을 모두 반영한다.
    • arm 및 arm64는 아직 h/w 멀티스레드가 적용되지 않았다. (cortex-a72,73,75까지도)
  • 코드 라인 29~34에서 2단계 affinity 값들을 반영한다.
  • 코드 라인 35~44에서 UP 시스템인 경우 1개의 cpu만 core_id에 반영한다.
  • 코드 라인 46에서 요청 cpu에 대한 thread_sibling과 core_sibling cpumask를 갱신한다.
  • 코드 라인 48에서 요청 cpu에 대한 cpu capacity를 갱신한다.
  • 코드 라인 50~53에서 로그 정보를 출력한다.
    • 예) rpi2:
      • CPU0: thread -1, cpu 0, socket 15, mpidr 80000f00
      • CPU3: thread -1, cpu 3, socket 15, mpidr 80000f03

 

update_siblings_masks()

arch/arm/kernel/topology.c

static void update_siblings_masks(unsigned int cpuid)
{
        struct cputopo_arm *cpu_topo, *cpuid_topo = &cpu_topology[cpuid];
        int cpu;

        /* update core and thread sibling masks */
        for_each_possible_cpu(cpu) {
                cpu_topo = &cpu_topology[cpu];

                if (cpuid_topo->socket_id != cpu_topo->socket_id)
                        continue;

                cpumask_set_cpu(cpuid, &cpu_topo->core_sibling);
                if (cpu != cpuid)
                        cpumask_set_cpu(cpu, &cpuid_topo->core_sibling);

                if (cpuid_topo->core_id != cpu_topo->core_id)
                        continue;

                cpumask_set_cpu(cpuid, &cpu_topo->thread_sibling);
                if (cpu != cpuid)
                        cpumask_set_cpu(cpu, &cpuid_topo->thread_sibling);
        }
        smp_wmb();
}

요청 cpu에 대한 thread_sibling과 core_sibling cpumask를 갱신한다.

  •  rpi2:
    • cpu#0 -> thread_sibling=0x1, core_sibling=0xf
    • cpu#3 -> thread_sibling=0x8, core_sibling=0xf

 

  • 코드 라인 7~11에서 possible cpu 수 만큼 순회하며 socket_id가 동일하지 않은 경우 skip 한다.
  • 코드 라인 13에서 요청한 cpuid에 대한 cpu_topology의 core_sibling의 cpuid에 해당하는 비트를 설정한다.
  • 코드 라인 14~15에서 순회중인 cpu에 대한 cpu_topology의 core_sibling의 순회중인 cpu에 해당하는 비트를 설정한다.
  • 코드 라인 17~18에서 core_id가 동일하지 않은 경우 skip 한다.
  • 코드 라인 20에서 요청한 cpuid에 대한 cpu_topology의 thread_sibling의 cpuid에 해당하는 비트를 설정한다.
  • 코드 라인 21~22에서 순회중인 cpu에 대한 cpu_topology의 thread_sibling의 순회중인 cpu에 해당하는 비트를 설정한다.

 

update_cpu_capacity()

arch/arm/kernel/topology.c

/*
 * Look for a customed capacity of a CPU in the cpu_capacity table during the
 * boot. The update of all CPUs is in O(n^2) for heteregeneous system but the
 * function returns directly for SMP system.
 */
static void update_cpu_capacity(unsigned int cpu)
{
        if (!cpu_capacity(cpu))
                return;

        set_capacity_scale(cpu, cpu_capacity(cpu) / middle_capacity);

        pr_info("CPU%u: update cpu_capacity %lu\n",
                cpu, arch_scale_cpu_capacity(NULL, cpu));
}

cpu별 산출된 capacity 값을 middle_capacity로 나눈 후 cpu별 cpu_scale에 설정한다.

  • rpi2: freq(800Mhz >> 20) * efficiency(2048) / middle_capacity(1524) = 1,560,576 / 1524 = 1024
    • 4개의 cpu 코어에 사용된 주파수가 모두 동일하고 아키텍처도 동일하므로 1024가 반영됨.
    • 예) rpi2:
      • CPU0: update cpu_capacity 1024
      • CPU3: update cpu_capacity 1024

 

arch_scale_cpu_capacity() & set_capacity_scale()

arch/arm/kernel/topology.c

 * cpu capacity table
 * This per cpu data structure describes the relative capacity of each core.
 * On a heteregenous system, cores don't have the same computation capacity
 * and we reflect that difference in the cpu_capacity field so the scheduler
 * can take this difference into account during load balance. A per cpu
 * structure is preferred because each CPU updates its own cpu_capacity field
 * during the load balance except for idle cores. One idle core is selected
 * to run the rebalance_domains for all idle cores and the cpu_capacity can be
 * updated during this sequence.
 */
static DEFINE_PER_CPU(unsigned long, cpu_scale);

unsigned long arch_scale_cpu_capacity(struct sched_domain *sd, int cpu)
{
        return per_cpu(cpu_scale, cpu);
}

static void set_capacity_scale(unsigned int cpu, unsigned long capacity)
{
        per_cpu(cpu_scale, cpu) = capacity;
}

전역 per-cpu 변수 cpu_scale에 산출된 cpu capacity 값을 저장한다.

 

스케줄링 도메인들 초기화

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

 

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

 

init_sched_domains()

kernel/sched/core.c

/*
 * Set up scheduler domains and groups. Callers must hold the hotplug lock.
 * For now this just excludes isolated cpus, but could be used to
 * exclude other special cases in the future.
 */
static int init_sched_domains(const struct cpumask *cpu_map)
{
        int err;

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

        return err;
}

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

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

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

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

kernel/sched/core.c – 1/1

/*
 * 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;
        struct sched_domain *sd;
        struct s_data d;
        int i, ret = -ENOMEM;

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

        /* 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) {
                        sd = build_sched_domain(tl, cpu_map, attr, sd, i);
                        if (tl == sched_domain_topology)
                                *per_cpu_ptr(d.sd, i) = sd;
                        if (tl->flags & SDTL_OVERLAP || sched_feat(FORCE_SD_OVERLAP))
                                sd->flags |= SD_OVERLAP;
                        if (cpumask_equal(cpu_map, sched_domain_span(sd)))
                                break;
                }
        }
  • 코드 라인 13~15에서 스케줄 도메인 토플로지의 자료 구조를 할당받고 초기화하고 루트 도메인을 할당받은 후 초기화한다.
  • 코드 라인 18에서 cpu_map 비트마스크에 설정된 cpu에 대해 순회한다.
  • 코드 라인 22~23에서 스케줄 도메인 계층 구조를 순회하며 스케줄 도메인을 구성한다.
  • 코드 라인 24~25에서 순회중인 tl이 전역 스케줄 도메인 토플로지인 경우 s_data.sd의 현재 순회중인 cpu에 구성한 스케줄 도메인을 연결한다.
  • 코드 라인 26~27에서 tl에 SDTL_OVERLAP 설정된 경우 스케줄 도메인에도 SD_OVERLAP 플래그를 추가한다.
  • 코드 라인 28~29에서 cpu_map과 스케줄 도메인의 span 구성이 동일한 경우 루프를 벗어난다.

 

kernel/sched/core.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) {
                sd = *per_cpu_ptr(d.sd, i); 
                cpu_attach_domain(sd, d.rd, i);
        }
        rcu_read_unlock();

        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~31에서 cpu_map에 설정된 cpu를 순회하며 도메인을 연결한다.
  • 코드 라인 36에서 스케줄링 도메인 토플로지에 구성된 sd, sg, sgc 멤버들에서 사용되지 않는 구조체 할당들을 모두 해제한다.

 

__visit_domain_allocation_hell()

kernel/sched/core.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/core.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->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_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;

                        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;

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

        return 0;
}

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

  • 코드 라인 6에서 스케줄 도메인 단계만큼 순회한다.
    • arm의 경우 보통 1 단계 DIE 만을 구성하여 사용한다. 클러스터를 구성하여 사용하는 경우 2 단계로 구성한 DIE – MC(Multi core) 또는 3 단계로 구성한 NODE – DIE – MC 등을 사용할 수도 있다.
  • 코드 라인 9~19에서 스케줄 도메인의 sd_data에 sched_domain, sched_group, sched_group_capacity에 대한 포인터를 per-cpu로 할당하여 구성한다.
  • 코드 라인 21~48에서 cpu_map 비트마스크에 포함된 cpu들에 대해 sched_domain, sched_group, sched_group_capacity 구조체를 할당받은 후 sd_data에 연결한다.

 

다음 그림은 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에 cpu가 설정되지 않은 경우 순회를 정지한다.

 

루트 도메인

alloc_rootdomain()

kernel/sched/core.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/core.c

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 cpu)
{
        struct sched_domain *sd = sd_init(tl, cpu);
        if (!sd)
                return child;

        cpumask_and(sched_domain_span(sd), cpu_map, tl->mask(cpu));
        if (child) {
                sd->level = child->level + 1;
                sched_domain_level_max = max(sched_domain_level_max, sd->level);
                child->parent = sd;
                sd->child = child;

                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~7에서 요청한 스케줄 도메인 토플로지 레벨 tl에 대한 스케줄 도메인을 초기화한다.
  • 코드 라인 9에서 cpu_map과 스케줄 도메인 토플로지 레벨에 해당하는 cpumask 둘을 만족하는 결과를 sd->span에 대입한다.
  • 코드 라인 10~14에서 child 스케줄 도메인 토플로지 레벨이 있는 경우 현재 스케줄 도메인의 레벨을 child 보다 1 큰 값으로하고 부모 관계를 설정한다.
    • 전역 변수 sched_domain_level_max에는 최대 스케줄 도메인 레벨 값을 갱신한다.
  • 코드 라인 16~27에서 자식 스케줄 도메인에 속한 cpu가 요청한 스케줄 도메인에 포함되지 않은 경우 경고 메시지를 출력하고 해당 스케줄 도메인에 포함시킨다.
  • 코드 라인 30에서 스케줄링 도메인의 레벨이 요청한 relax 도메인 레벨보다 큰 경우 wake 및 newidle 플래그를 클리어하고 그렇지 않은 경우 설정한다. 요청한 relax 도메인 레벨이 없는 경우 디폴트 relax 도메인 레벨 값을 사용하여 판단한다.

 

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

 

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

 

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

sd_init()

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

kernel/sched/core.c – 1/2

static struct sched_domain *
sd_init(struct sched_domain_topology_level *tl, int cpu)
{
        struct sched_domain *sd = *per_cpu_ptr(tl->data.sd, cpu);
        int 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;

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

                .cache_nice_tries       = 0,
                .busy_idx               = 0,
                .idle_idx               = 0,
                .newidle_idx            = 0,
                .wake_idx               = 0,
                .forkexec_idx           = 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
                                        | 0*SD_PREFER_SIBLING
                                        | 0*SD_NUMA
                                        | sd_flags
                                        ,

                .last_balance           = jiffies,
                .balance_interval       = sd_weight,
                .smt_gain               = 0,
                .max_newidle_lb_cost    = 0,
                .next_decay_max_lb_cost = jiffies,
#ifdef CONFIG_SCHED_DEBUG
                .name                   = tl->name,
#endif
        };
  • 코드 라인 16~17에서 요청한 토플로지의 sd_flags() 함수 후크를 수행하여 sd_flags 값을 알아온다.
  • 코드 라인 18~20에서 sd_flags 값으로 다음 플래그 값들 이외의 플래그가 설정되어 있는 경우 경고 메시지를 출력하고 제거한다.
    • 허용: SD_SHARE_CPUCAPACITY | SD_SHARE_PKG_RESOURCES | SD_NUMA | SD_ASYM_PACKING | SD_SHARE_POWERDOMAIN
  • 코드 라인 35~46에서 스케줄링 도메인의 초기 플래그 값에 다음 플래그 값과 읽어온 sd_flags를 포함하여 설정한다.
    • 추가: SD_LOAD_BALANCE | SD_BALANCE_NEWIDLE | SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE

 

kernel/sched/core.c – 2/2

        /*
         * Convert topological properties into behaviour.
         */

        if (sd->flags & SD_SHARE_CPUCAPACITY) {
                sd->imbalance_pct = 110;
                sd->smt_gain = 1178; /* ~15% */

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

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

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

#endif
        } else {
                sd->flags |= SD_PREFER_SIBLING;
                sd->cache_nice_tries = 1;
                sd->busy_idx = 2;
                sd->idle_idx = 1;
        }

        sd->private = &tl->data;

        return sd;
}

 

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

 

다음 그림은 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/core.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/core.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/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()

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을 대입한다.

 

스케줄 그룹 Capacity

init_sched_groups_capacity()

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에 대입한다.

 

 

group_balance_cpu()

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, 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 = 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(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/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/core.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/core.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_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~16에서 스케줄 도메인의 플래그가 밸런싱을 요구하는데 다음 그룹이 있으면 false(0)을 반환한다.
  • 코드 라인 19~20에서 스케줄 도메인에서 SD_WAKE_AFFINE 플래그가 사용된 경우 false(0)을 반환한다.
  • 코드 라인 22에서 true(1)를 반환한다.

 

캐시 스케줄링 도메인 갱신

update_top_cache_domain()

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;
}

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

 

구조체

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 *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를 하게 하기 위해 사용한다.

 

#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];
};
  • *name
    • 도메인 명
  • *private
    • 생성 시 sd_data를 가리킨다.
  • *rcu
    • 해제 시 rcu 링크로 사용한다.
  • span_weight
    • 도메인에 포함된 cpu 수
  • span[0]
    • 도메인에 포함된 cpu 비트마스크

 

참고

 

 

답글 남기기

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