Scheduler -3- (PELT)

<kernel v5.4>

Scheduler -3- (PELT)

리눅스 커널은 다음과 같이 시스템 운영 환경에 따라 스케줄러와 로드 추적을 구분하여 적용하고 있다.

  • SMP(Symmetric Multi Processing) 시스템
    • 스케줄러로 내장 커널 스케줄러를 사용한다.
    • PELT(Per-Entity Load Tracking)를 구성하여 사용한다.
  • AMP(Asymmetric Multi Processing) 시스템
    • 모바일 기기를 만드는 안드로이드 진영의 각 칩셋사에서 여러 모델을 시험적으로 사용하고 있고, 현재 가장 우수한 성능을 나타내는 조합은 다음과 같다.
    • 스케줄러로 IKS(In-Kernel Switcher), GTS(Global Task Scheduling) 또는 EAS(Energy Aware Scheduler)를 사용한다.
    • WALT(Window Assisted Load Tracking)
      • WALT는 PELT와 같이 사용할 수도 있고, 독립적으로 사용할 수도 있다.
      • 태스크의 로드 상승 및 하강에 대한 변화는 PELT에 비해 약 4배 정도 빠르게 상승하고, 하강은 8배 더 빠르다.
      • EAS(Energy Aware Scheduler) + schedutil이 기본적으로 같이 사용된다.
      • 참고:

 

big/little SoC

big/little migration을 위한 H/W 모델에 다음과 같은 것들이 사용된다.

  • 클러스터 마이그레이션 사용 모델
    • 클러스터들 중 하나만 사용되는 모델로, 오래된 big/little SoC 들에서 사용되었다.
  • CPU 마이그레이션 사용 모델
    • IKS(In-Kernel Switcher)를 통해 cpu별로 big/little cpu를 선택하여 가동하는 모델이다.
  • HMP(Heterogeneous Multi-Processing) 사용 모델
    • 가장 강력한 모델로 동시에 모든 프로세스를 사용하는 모델로, 최근 SoC들이 사용되는 방식이다.

 

PELT(Per-Entity Load Tracking)

  • 용도
    • 로드 밸런스
    • 그룹 스케줄링
    • sched util governor에서 주파수 선택
    • EAS(Energy Aware Scheduler) 에서 태스크의 cpu 선정
  • 커널 v3.8부터 다음 로드 평균을 산출하여 엔티티별 로드를 추적할 수 있다.
    • 로드 합계 및 평균 (load sum & average)
      • runnable% * load
    • 러너블 로드 합계 및 평균(runnable load sum & average)
      • 엔티티가 cpu에서 러너블(curr + 엔큐) 상태로 있었던 기간 평균
    • 유틸 로드 합계 및 평균(util load sum & average)
      • 엔티티가 cpu에서 수행한 기간 평균
      • running% * 1024
  • 스케줄 틱마다 그리고 태스크의 엔티티에 변화(enqueue, dequeue, migration 등)가 생길 때마다  갱신한다.
  • 로드 값은 1 period 단위 기간인 2^20ns(약 1024us) 마다 decay되며, 32번째 단위 시간이 될 때 정확히 절반으로 줄어드는 특성을 가진다.

커널의 PELT를 위한 지수 평활 계수는 다음과 같다.

  • 지수 함수 모델 k = a * (b ^ n)
    • a=1, b=0.5^(1/n)), n=32 또는 a=1, b=2^(-1/n), n=32
  • k=0.5^(1/32) 또는 k=2^(-1/32)
    • k 값은 32번 decay할 때 절반으로 줄어드는 특징이 있다. (k^32=0.5)
    •  k = 0.97857206…
  • 지수 평활 계수 k를 사용하여 로드 값은 다음과 같이 산출된다.
    • cpu 로드 값 = 기존 cpu 로드 값 * k + 새 cpu 로드 값 * k

 

엔티티들의 로드 합계와 평균을 구할 때마다 전체 엔티티를 스캔하는 방식은 많은 코스트를 사용해야 하므로 이러한 방법은 사용하지 않는다. 다음과 같은 타이밍에 엔티티들의 합과 평균을 구한다.

  • 스케줄 틱
    • 스케줄 틱마다 현재 러닝 중인 엔티티의 로드 합계와 평균을 갱신한다.
  • 엔티티의 변화
    • 엔티티의 attach/detach/migration 등 이벤트마다 해당 엔티티의 로드 합계와 평균을 갱신한다.

 

엔티티의 로드 합계와 평균을 산출한 후에는 다음 순서로 누적하고 상위에 보고한다.

  • 1단계: 엔티티 accumulate
    • 엔티티들의 로드를 모아 해당 cfs 런큐로 누적(accumulate)
  • 2단계: 상위 cfs 런큐 propagation
    • 최하위 cfs 런큐부터 최상위 cfs 런큐까지 전파(propagation)
  • 3단계: 태스크 그룹 contribution
    • per-cpu cfs 런큐의 로드를 태스크 그룹으로 글로벌 로드 값으로 변화분 기여(atomic add)

 

로드 평균 추적

로드 평균 추적을 위해 해당 태스크의 pid가 필요하다.  아래 bash 태스크의 pid를 알아온 후 cgroup 유저 세션의 tasks에 포함되었는지 확인해본다.

# ps
  PID TTY          TIME CMD
  471 ttyAMA0  00:00:00 login
  760 ttyAMA0  00:00:00 bash
  791 ttyAMA0  00:00:00 ps

# cat /sys/fs/cgroup/cpu/user.slice/user-0.slice/session-1.scope/tasks
471
760
949

 

다음은 /proc/<pid> 디렉토리에 진입한 후 해당 태스크의 스케줄 statistics 정보를 확인한다.

# cd /proc/760

# cat /proc/760$ cat schedstat
503102081 13905504 293

# cat /proc/760/sched
full_load (760, #threads: 1)
-------------------------------------------------------------------
se.exec_start                                :       3989409.638984
se.vruntime                                  :         17502.410171
se.sum_exec_runtime                          :           783.958340
se.nr_migrations                             :                    1
nr_switches                                  :                 1016
nr_voluntary_switches                        :                  935
nr_involuntary_switches                      :                   81
se.load.weight                               :              1048576
se.runnable_weight                           :              1048576
se.avg.load_sum                              :                 7971
se.avg.runnable_load_sum                     :                 7971
se.avg.util_sum                              :              8163624
se.avg.load_avg                              :                  167
se.avg.runnable_load_avg                     :                  167
se.avg.util_avg                              :                  167
se.avg.last_update_time                      :        3989409638400
se.avg.util_est.ewma                         :                   53
se.avg.util_est.enqueued                     :                  167
policy                                       :                    0
prio                                         :                  120
clock-delta                                  :                  292
mm->numa_scan_seq                            :                    0
numa_pages_migrated                          :                    0
numa_preferred_nid                           :                   -1
total_numa_faults                            :                    0
current_node=0, numa_group_id=0
numa_faults node=0 task_private=0 task_shared=0 group_private=0 group_shared=0

 

다음 명령을 사용하면 모든 태스크의 스케줄 statistics 정보를 한 번에 알아볼 수 있다. (소숫점 이상은 밀리세컨드이다.)

# cat /proc/sched_debug 

(...생략...)

runnable tasks:
 S           task   PID         tree-key  switches  prio     wait-time             sum-exec        sum-sleep
-----------------------------------------------------------------------------------------------------------
 S        systemd     1       128.556417      1435   120         0.000000      2532.278466         0.000000 0 0 /init.scope
 S       kthreadd     2      9007.043581       110   120         0.000000        38.206758         0.000000 0 0 /
 I         rcu_gp     3         7.075165         3   100         0.000000         0.017792         0.000000 0 0 /
 I     rcu_par_gp     4         8.587139         3   100         0.000000         0.023918         0.000000 0 0 /
 I   kworker/0:0H     6       372.048163         8   100         0.000000         6.427459         0.000000 0 0 /
 I   mm_percpu_wq     8        14.188365         3   100         0.000000         0.024208         0.000000 0 0 /
 S    ksoftirqd/0     9      9072.934585       312   120         0.000000        30.653868         0.000000 0 0 /
 S    migration/0    11         0.000000        73     0         0.000000        30.741958         0.000000 0 0 /
 S        cpuhp/0    12       337.602512        13   120         0.000000         1.789666         0.000000 0 0 /
 I    kworker/0:1    21      9068.975793       653   120         0.000000       173.940206         0.000000 0 0 /
 S        kauditd    23        64.560835         2   120         0.000000         0.137958         0.000000 0 0 /
 S     oom_reaper    24        70.621792         2   120         0.000000         0.060960         0.000000 0 0 /
 I      writeback    25        74.666295         2   100         0.000000         0.059208         0.000000 0 0 /
 S     kcompactd0    26        74.680295         2   120         0.000000         0.063125         0.000000 0 0 /
 I    kintegrityd    77       173.140036         2   100         0.000000         0.056583         0.000000 0 0 /
 I blkcg_punt_bio    79       179.192415         2   100         0.000000         0.067375         0.000000 0 0 /
 I     tpm_dev_wq    80       179.207188         3   100         0.000000         0.095500         0.000000 0 0 /
 I        ata_sff    81       179.208301         3   100         0.000000         0.158208         0.000000 0 0 /
 I     devfreq_wq    83       179.225743         3   100         0.000000         0.162542         0.000000 0 0 /
 I   kworker/u5:0    86       218.072428         3   100         0.000000         0.827083         0.000000 0 0 /
 I        xprtiod    87       218.102147         2   100         0.000000         0.223708         0.000000 0 0 /
 S        kswapd0   146       243.631141         3   120         0.000000         0.045208         0.000000 0 0 /
 I         nfsiod   147       231.757201         3   100         0.000000         0.177042         0.000000 0 0 /
 I       xfsalloc   148       237.636886         3   100         0.000000         0.097125         0.000000 0 0 /
 I   kworker/0:1H   155      9042.378580       127   100         0.000000        89.291426         0.000000 0 0 /
 I    kworker/0:3   187      5836.456951        50   120         0.000000         0.949960         0.000000 0 0 /
 S  systemd-udevd   207       676.417929       890   120         0.000000       762.019973         0.000000 0 0 /autogroup-13
 Ssystemd-network   240        10.659505        54   120         0.000000        89.746452         0.000000 0 0 /autogroup-21
 S          acpid   257         3.489799         8   120         0.000000         8.382792         0.000000 0 0 /autogroup-22
 S          gdbus   271       115.518683        38   120         0.000000         9.789205         0.000000 0 0 /autogroup-24
 S       rsyslogd   272        22.666138        29   120         0.000000        51.687122         0.000000 0 0 /autogroup-27
 S   rtkit-daemon   273        16.551777        19   121         0.000000        17.856413         0.000000 0 0 /autogroup-28
 S   rtkit-daemon   275        56.491989       225   120         0.000000        34.801951         0.000000 0 0 /autogroup-28
 S   rtkit-daemon   276         0.000000       111     0         0.000000        16.475375         0.000000 0 0 /autogroup-28
 S systemd-logind   279         3.639090       143   120         0.000000        73.653134         0.000000 0 0 /autogroup-32
 S NetworkManager   283       207.003587       235   120         0.000000       343.688449         0.000000 0 0 /autogroup-35
 S          gmain   328       222.841799       236   120         0.000000        58.477883         0.000000 0 0 /autogroup-35
 S        polkitd   301        34.343594        84   120         0.000000        34.283501         0.000000 0 0 /autogroup-37
 S          gmain   306        18.460635         5   120         0.000000         0.291958         0.000000 0 0 /autogroup-37
 S           bash   760      2480.890766       941   120         0.000000      2141.409558         0.000000 0 0 /user.slice/user-0.slice/session-1.scope
 S           ntpd   771       128.569616       776   120         0.000000       300.594067         0.000000 0 0 /autogroup-53
 I   kworker/u4:0   800      9013.026954       461   120         0.000000        24.093421         0.000000 0 0 /
 I   kworker/u4:1   847      9073.130002        56   120         0.000000         8.608543         0.000000 0 0 /
cpu#0
  .nr_running                    : 0
  .nr_switches                   : 33262
  .nr_load_updates               : 0
  .nr_uninterruptible            : 3
  .next_balance                  : 4295.902295
  .curr->pid                     : 0
  .clock                         : 4040095.934379
  .clock_task                    : 4021572.724115
  .avg_idle                      : 8881345
  .max_idle_balance_cost         : 5154074

cfs_rq[0]:/user.slice/user-0.slice/session-1.scope
  .exec_clock                    : 0.000000
  .MIN_vruntime                  : 0.000001
  .min_vruntime                  : 17534.518299
  .max_vruntime                  : 0.000001
  .spread                        : 0.000000
  .spread0                       : -15804.041501
  .nr_spread_over                : 0
  .nr_running                    : 0
  .load                          : 0
  .runnable_weight               : 0
  .load_sum                      : 2658005
  .load_avg                      : 56
  .runnable_load_sum             : 415
  .runnable_load_avg             : 0
  .util_sum                      : 2647676
  .util_avg                      : 55
  .util_est_enqueued             : 0
  .removed.load_avg              : 0
  .removed.util_avg              : 0
  .removed.runnable_sum          : 0
  .tg_load_avg_contrib           : 56
  .tg_load_avg                   : 1080
  .se->exec_start                : 4021516.525783
  .se->vruntime                  : 20945.789828
  .se->sum_exec_runtime          : 17480.214425
  .se->load.weight               : 156022
  .se->runnable_weight           : 2
  .se->avg.load_sum              : 2592
  .se->avg.load_avg              : 8
  .se->avg.util_sum              : 2647676
  .se->avg.util_avg              : 55
  .se->avg.runnable_load_sum     : 2592
  .se->avg.runnable_load_avg     : 0

(...생략...)

 


스케줄 틱

scheduler_tick()

kernel/sched/core.c

/*
 * This function gets called by the timer code, with HZ frequency.
 * We call it with interrupts disabled.
 */
void scheduler_tick(void)
{
        int cpu = smp_processor_id();
        struct rq *rq = cpu_rq(cpu);
        struct task_struct *curr = rq->curr;
        struct rq_flags rf;

        sched_clock_tick();

        rq_lock(rq, &rf);

        update_rq_clock(rq);
        curr->sched_class->task_tick(rq, curr, 0);
(...생략...)
}

스케줄 틱마다 런타임 처리 및 로드 평균 산출 등의 처리를 수행하고, 로드 밸런스 주기가 된 경우 SCHED softirq를 호출한다.

  • 코드 라인 3~5에서 현재 cpu의 런큐 및 현재 태스크를 알아온다.
  • 코드 라인 8에서 x86 및 ia64 아키텍처에 등에서 사용하는 unstable 클럭을 사용하는 중이면 per-cpu sched_clock_data 값을 현재 시각으로 갱신한다.
  • 코드 라인 10에서 런큐 정보를 수정하기 위해 런큐 락을 획득한다.
  • 코드 라인 12에서 런큐 클럭 값을 갱신한다.
    • rq->clock, rq->clock_task, rq->clock_pelt 클럭등을 갱신한다.
  • 코드 라인 13에서 현재 태스크의 스케줄링 클래스에 등록된 (*task_tick) 콜백 함수를 호출한다.
    • task_tick_fair(), task_tick_rt(), task_tick_dl()

 

스케줄링 클래스별 틱 처리

  • Real-Time 스케줄링 클래스
    • task_tick_rt()
  • Deadline 스케줄링 클래스
    • task_tick_dl()
  • Completly Fair 스케줄링 클래스
    • task_tick_fair()
  • Idle-Task 스케줄링 클래스
    • task_tick_idle() – 빈 함수
  • Stop-Task 스케줄링 클래스
    • task_tick_stop() – 빈 함수

 

task_tick_fair()

kernel/sched/fair.c

/*
 * scheduler tick hitting a task of our scheduling class.
 *
 * NOTE: This function can be called remotely by the tick offload that
 * goes along full dynticks. Therefore no local assumption can be made
 * and everything must be accessed through the @rq and @curr passed in
 * parameters.
 */
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
        struct cfs_rq *cfs_rq;
        struct sched_entity *se = &curr->se;

        for_each_sched_entity(se) {
                cfs_rq = cfs_rq_of(se);
                entity_tick(cfs_rq, se, queued);
        }
(...생략...)
}

현재 태스크에 대한 스케줄 틱 처리를 수행한다.

  • 코드 라인 6~9에서 최상위 그룹 엔티티까지 스케줄 틱에 대한 로드 평균 등의 산출을 수행한다.

 

static void
entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
        /*
         * Update run-time statistics of the 'current'.
         */
        update_curr(cfs_rq);

        /*
         * Ensure that runnable average is periodically updated.
         */
        update_load_avg(cfs_rq, curr, UPDATE_TG);
        update_cfs_group(curr);
(...생략...)
}

스케줄 틱에 대해 현재 엔티티에 대한 로드 평균 등을 갱신한다.

  • 코드 라인 7에서 런타임 등에 대해 처리한다.
  • 코드 라인 12에서 요청한 엔티티의 로드 평균을 갱신한다.
  • 코드 라인 13에서 그룹 엔티티 및 cfs 런큐에 대해 로드 평균을 갱신한다.

 

런큐 클럭

런큐에는 다음과 같은 3가지 클럭이 사용된다.

  • rq->clock
    • 갱신할 때 마다 정확히 절대 스케줄 클럭을 사용하여 런타임을 누적한다.
  • rq->clock_task
    • irq 처리 및 vCPU 처리에 사용된 시간을 제외하고 순수하게 현재 cpu가 태스크에 소모한 런타임을 누적한다.
    • rq->clock 보다 약간 느리게 간다.
  • rq->clock_pelt
    • clock_task에 누적되는 시간에 cpu capacity를 적용하여 누적시킨 런타임이다.
      • big little 시스템에서 big cpu들이 1024(1.0)을 적용될 경우 little cpu들은 더 적은 capacity를 반영한다.
    • 런큐가 idle 상태인 경우에는 항상 rq->clock_task에 동기화된다.

 

위의 3가지 런큐 클럭은 다음 순서로 갱신한다.

  • update_rq_clock() -> update_rq_clock_task() -> update_rq_clock_pelt()

 

다음 그림은 3가지 런큐 클럭에 대한 차이를 보여준다.

  • rq->clock_task는 이전 타임의 irq 타임 + task 타임을 반영한다.

 

런큐 클럭 조회

rq_clock()

kernel/sched/sched.h

static inline u64 rq_clock(struct rq *rq)
{
        lockdep_assert_held(&rq->lock);
        assert_clock_updated(rq);

        return rq->clock;
}

런큐의 clock을 를 반환한다.

 

rq_clock_task()

kernel/sched/sched.h

static inline u64 rq_clock_task(struct rq *rq) 
{
        lockdep_assert_held(&rq->lock);
        return rq->clock_task;
}

런큐의 clock_task 를 반환한다.

 

rq_clock_pelt()

kernel/sched/pelt.h

static inline u64 rq_clock_pelt(struct rq *rq)
{
        lockdep_assert_held(&rq->lock);
        assert_clock_updated(rq);

        return rq->clock_pelt - rq->lost_idle_time;
}

런큐의 clock_pelt를 반환한다.

 

cfs_rq_clock_pelt()

kernel/sched/pelt.h

/* rq->task_clock normalized against any time this cfs_rq has spent throttled */
static inline u64 cfs_rq_clock_pelt(struct cfs_rq *cfs_rq)
{
        if (unlikely(cfs_rq->throttle_count))
                return cfs_rq->throttled_clock_task - cfs_rq->throttled_clock_task_time;

        return rq_clock_pelt(rq_of(cfs_rq)) - cfs_rq->throttled_clock_task_time;
}

런큐의 clock_pelt에서 cfs 런큐의 스로틀 시간을 뺀 시간을 반환한다. 이 클럭으로 로드 평균을 구할 때 사용한다.

  • cfs bandwidth를 설정하여 사용할 때 스로틀 시간에 관련된 다음 변수들이 있다.
    • 스로틀이 시작되면 cfs_rq->throttled_clock_task는 rq->clock_task로 동기화된다.
    • 스로틀이 종료되면 cfs_rq->throttled_clock_task_time에는 스로틀한 시간만큼을 누적시킨다.

 

런큐 클럭들의 갱신

update_rq_clock()

kernel/sched/core.c

void update_rq_clock(struct rq *rq)
{
        s64 delta;

        lockdep_assert_held(&rq->lock);

        if (rq->clock_update_flags & RQCF_ACT_SKIP)
                return;

#ifdef CONFIG_SCHED_DEBUG
        if (sched_feat(WARN_DOUBLE_CLOCK))
                SCHED_WARN_ON(rq->clock_update_flags & RQCF_UPDATED);
        rq->clock_update_flags |= RQCF_UPDATED;
#endif

        delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
        if (delta < 0)
                return;
        rq->clock += delta;
        update_rq_clock_task(rq, delta);
}

나노초로 동작하는 런큐 클럭을 갱신한다. (스케줄 틱 및 태스크(또는 엔티티)의 변동시 마다 호출된다)

  • 코드 라인 7~8에서 skip 요청을 받아들인 경우이다. 이때엔 런큐 클럭을 갱신하지 않고 그냥 함수를 빠져나간다.
  • 코드 라인 16~18에서 런큐 클럭이 갱신된 시간과 스케쥴 클럭의 시간 차이 delta를 얻어온다. 시간이 흐르지 않은 경우 클럭 갱신 없이 함수를 빠져나간다.
  • 코드 라인 19에서 런큐 클럭에 delta를 추가하여 갱신한다.
  • 코드 라인 20에서 rq->clock_task에 @delta를 전달하여 반영한다. (일부 시간이 빠짐)

 

update_rq_clock_task()

kernel/sched/core.c

static void update_rq_clock_task(struct rq *rq, s64 delta)
{
/*
 * In theory, the compile should just see 0 here, and optimize out the call
 * to sched_rt_avg_update. But I don't trust it...
 */
        s64 __maybe_unused steal = 0, irq_delta = 0;

#ifdef CONFIG_IRQ_TIME_ACCOUNTING
        irq_delta = irq_time_read(cpu_of(rq)) - rq->prev_irq_time;

        /*
         * Since irq_time is only updated on {soft,}irq_exit, we might run into
         * this case when a previous update_rq_clock() happened inside a
         * {soft,}irq region.
         *
         * When this happens, we stop ->clock_task and only update the
         * prev_irq_time stamp to account for the part that fit, so that a next
         * update will consume the rest. This ensures ->clock_task is
         * monotonic.
         *
         * It does however cause some slight miss-attribution of {soft,}irq
         * time, a more accurate solution would be to update the irq_time using
         * the current rq->clock timestamp, except that would require using
         * atomic ops.
         */
        if (irq_delta > delta)
                irq_delta = delta;

        rq->prev_irq_time += irq_delta;
        delta -= irq_delta;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
        if (static_key_false((&paravirt_steal_rq_enabled))) {
                steal = paravirt_steal_clock(cpu_of(rq));
                steal -= rq->prev_steal_time_rq;

                if (unlikely(steal > delta))
                        steal = delta;

                rq->prev_steal_time_rq += steal;
                delta -= steal;
        }
#endif

        rq->clock_task += delta;

#ifdef CONFIG_HAVE_SCHED_AVG_IRQ
        if ((irq_delta + steal) && sched_feat(NONTASK_CAPACITY))
                update_irq_load_avg(rq, irq_delta + steal);
#endif
        update_rq_clock_pelt(rq, delta);
}

나노초로 동작하는 rq->clock_task를 갱신한다. 커널 옵션들의 사용 유무에 따라 rq->clock과 동일할 수도 있고, irq 처리 및 vCPU에 사용된 시간을 빼고 순수하게 현재 cpu에서 동작한 태스크 시간만을 누적할 수 있다.

  • 코드 라인 9~32에서 irq 처리에 사용된 시간을 측정하기 위한 CONFIG_IRQ_TIME_ACCOUNTING 커널 옵션을 사용한 경우 인자로 전달받은 @delta 값을 그대로 사용하지 않고 irq 처리에 사용된 시간은 @delta에서 뺴고 순수 태스크 런타임만을 적용하도록 한다.
  • 코드 라인 33~44에서 CONFIG_PARAVIRT_TIME_ACCOUNTING 커널 옵션을 사용한 경우 vCPU에서 소모한 시간을 빼고 현재 cpu에서 사용된 시간만을 적용하도록 한다.
  • 코드 라인 46에서 rq->clock_task에 변화(약간 감소)된 delta 시간을 누적시킨다.
  • 코드 라인 48~51에서 irq 처리에 사용된 시간으로 로드 평균을 갱신한다.
    • CONFIG_HAVE_SCHED_AVG_IRQ 커널 옵션은 위의 두 커널 옵션 중 하나라도 설정된 SMP 시스템에서 enable된다.
  • 코드 라인 52에서 rq->clock_pelt에 @delta를 전달하여 반영한다. (cpu capacity 및 frequency에 따라 @delta 값이 증감된다.)

 

update_rq_clock_pelt()

kernel/sched/pelt.h

/*
 * The clock_pelt scales the time to reflect the effective amount of
 * computation done during the running delta time but then sync back to
 * clock_task when rq is idle.
 *
 *
 * absolute time   | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16
 * @ max capacity  ------******---------------******---------------
 * @ half capacity ------************---------************---------
 * clock pelt      | 1| 2|    3|    4| 7| 8| 9|   10|   11|14|15|16
 *
 */
static inline void update_rq_clock_pelt(struct rq *rq, s64 delta)
{
        if (unlikely(is_idle_task(rq->curr))) {
                /* The rq is idle, we can sync to clock_task */
                rq->clock_pelt  = rq_clock_task(rq);
                return;
        }

        /*
         * When a rq runs at a lower compute capacity, it will need
         * more time to do the same amount of work than at max
         * capacity. In order to be invariant, we scale the delta to
         * reflect how much work has been really done.
         * Running longer results in stealing idle time that will
         * disturb the load signal compared to max capacity. This
         * stolen idle time will be automatically reflected when the
         * rq will be idle and the clock will be synced with
         * rq_clock_task.
         */

        /*
         * Scale the elapsed time to reflect the real amount of
         * computation
         */
        delta = cap_scale(delta, arch_scale_cpu_capacity(cpu_of(rq)));
        delta = cap_scale(delta, arch_scale_freq_capacity(cpu_of(rq)));

        rq->clock_pelt += delta;
}

clock_pelt는 실행중인 @delta 시간을 cpu 성능에 따라 반감된 시간을 반영한다. 런큐가 idle 상태인 경우에는 clock_task 시각으로 동기화시킨다.

  • 코드 라인 3~7에서 런큐가 idle 상태인 경우 rq->clock_pelt는 rq->clock_task에 동기화된다.
  • 코드 라인 25에서 @delta 시간에서 cpu capacity 만큼 반감시킨다.
    • full capacity 상태인 경우 반감되지 않는다.
  • 코드 라인 26에서 다시 한 번 frequency 성능만큼 반감시킨다.
    • full frequency로 동작하는 상태인 경우 반감되지 않는다.
  • 코드 라인 28에서 위에서 cpu 성능(capacity 및 frequency)에 따라 감소된 delta를 rq->clock_pelt에 반영한다.

 

다음 그림은 rq->clock_pelt에 서로 다른 cpu capacity가 적용된 시간이 반영되는 모습을 보여준다.

 


엔티티 로드 평균 갱신

엔티티 로드 평균을 산출하는 update_load_avg() 함수는 다음과 같은 함수에서 호출된다.

  • entity_tick()
    • 스케줄 틱마다 호출될 때
  • enqueue_task_fair()
    • cfs 런큐에 태스크가 엔큐될 때
  • dequeue_task_fair()
    • cfs 런큐에 태스크가 디큐될 때
  • enqueue_entity()
    • cfs 런큐에 엔티티가 엔큐될 때
  • dequeue_entity()
    • cfs 런큐에서 엔티티가 디큐될 때
  • set_next_entity()
    • cfs 런큐의 다음 엔티티가 선택될 때
  • put_prev_entity()
    • 현재 동작 중인 엔티티를 런큐의 대기로 돌려질 때
  • update_blocked_averages()
    • blocked 평균을 갱신할 때
  • propagate_entity_cfs_rq()
    • cfs 런큐로의 전파가 필요할 때
  • detach_entity_cfs_rq()
    • cfs 런큐로부터 엔티티를 detach할 때
  • attach_entity_cfs_rq()
    • cfs 런큐로 엔티티를 attach할 때
  • sched_group_set_shares()
    • 그룹에 shares를 설정할 때

 

엔티티 로드 weight과 러너블 로드 weight

64비트 시스템에서는 엔티티에 대한 로드 weight과 러너블 로드 weight 값을 10비트 더 정확도를 올려 처리하기 위해 스케일 업(<< 10)한다.

  • 32비트 시스템
    • nice 0 엔티티에 대한 se->load_weight = 1,024
  • 64비트 시스템
    • nice 0 엔티티에 대한 se->load_weight = 1,024 << 10 = 1,048,576

 

se_weight()

kernel/sched/sched.h

static inline long se_weight(struct sched_entity *se)
{
        return scale_load_down(se->load.weight);
}

엔티티 로드 weight을 스케일 다운하여 반환한다.

 

se_runnable()

kernel/sched/sched.h

static inline long se_runnable(struct sched_entity *se)
{
        return scale_load_down(se->runnable_weight);
}

엔티티 러너블 로드 weight을 스케일 다운하여 반환한다.

 

틱 마다 스케줄 엔티티에 대한 PELT 갱신과 preemption 요청 체크

스케줄 틱마다 호출되는 scheduler_tick() 함수와 hr 틱마다 호출되는 hrtick()  함수는 현재 curr에서 동작하는 태스크의 스케줄러의 (*task_tick) 후크 함수를 호출한다. 예를 들어 현재 런큐의 curr가 cfs 태스크인 경우 task_tick_fair() 함수가 호출되는데 태스크와 관련된 스케줄 엔티티부터 최상위 스케줄 엔티티까지 entity_tick() 함수를 호출하여 PELT와 관련된 함수들을 호출한다. 그리고 스케줄 틱으로 호출된 경우 preemption 요청 여부를 체크하여 리스케줄 되는 것에 반해, hrtimer에 의해 정확히 러닝 타이밍 소진시 HR 틱이 발생되어 호출되는 경우에는 무조건 리스케줄 요청한다.

  • 함수 호출 경로 예)
    • 스케줄 틱: scheduler_tick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=0으로 호출된다.
    • HR 틱: hrtick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=1로 호출된다.
  • 참고: Scheduler -6- (CFS Scheduler) | 문c

 

엔티티의 로드 평균  갱신

 

다음 그림은 update_load_avg() 함수의 호출 과정을 보여준다.

 

update_load_avg()

kernel/sched/fair.c

/* Update task and its cfs_rq load average */
static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
        u64 now = cfs_rq_clock_pelt(cfs_rq);
        int decayed;

        /*
         * Track task load average for carrying it to new CPU after migrated, and
         * track group sched_entity load average for task_h_load calc in migration
         */
        if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
                __update_load_avg_se(now, cfs_rq, se);

        decayed  = update_cfs_rq_load_avg(now, cfs_rq);
        decayed |= propagate_entity_load_avg(se);

        if (!se->avg.last_update_time && (flags & DO_ATTACH)) {

                /*
                 * DO_ATTACH means we're here from enqueue_entity().
                 * !last_update_time means we've passed through
                 * migrate_task_rq_fair() indicating we migrated.
                 *
                 * IOW we're enqueueing a task on a new CPU.
                 */
                attach_entity_load_avg(cfs_rq, se, SCHED_CPUFREQ_MIGRATION);
                update_tg_load_avg(cfs_rq, 0);

        } else if (decayed && (flags & UPDATE_TG))
                update_tg_load_avg(cfs_rq, 0);
}

엔티티의 로드 평균 등을 갱신한다.

  • 코드 라인 4에서 cpu 성능이 적용된 런큐의 pelt 시각을 알아온다.
  • 코드 라인 11~12에서 SKIP_AGE_LOAD 플래그가 없는 경우 엔티티의 로드 평균을 갱신한다.
  • 코드 라인 14에서 cfs 런큐의 로드/유틸 평균을 갱신하고 decay 여부를 알아온다.
  • 코드 라인 15에서 cfs 런큐에 태스크가 attach/detach할 때 전파(propagate) 표시를 하여 다음 update에서 변경 사항을 상위 수준(cfs 런큐 및 엔티티)으로 전파하기 위해 cfs 런큐의 로드 등을 엔티티에 복사한다.그리고 decay 여부도 알아온다.
  • 코드 라인 17~27에서 태스크를 마이그레이션한 이후 엔티티에서 처음인 경우 로드 평균을 추가하고, 태스크 그룹 로드 평균을 갱신한다.
    • 처음 마이그레이션된 경우 last_update_time은 0으로 클리어되어 있다.
  • 코드 라인 29~30에서 decay 된 경우에 한해 태스크 그룹 로드 평균도 갱신한다.

 

스케줄 엔티티에 대한 로드 합계 및 평균을 산출

__update_load_avg_se()

kernel/sched/pelt.c

int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        if (___update_load_sum(now, &se->avg, !!se->on_rq, !!se->on_rq,
                                cfs_rq->curr == se)) {

                ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
                cfs_se_util_change(&se->avg);
                trace_pelt_se_tp(se);
                return 1;
        }

        return 0;
}

새롭게 반영해야 할 로드를 엔티티 로드 합계에 추가하고 그 과정에서 decay한 적이 있으면 로드 평균도 재산출한다. 반환 되는 값은 로드 평균의 재산출 여부이다. (로드 합계의 decay가 수행된 경우 로드 평균도 재산출되므로 1을 반환한다.)

  • 코드 라인 3~4에서 새롭게 반영해야 할 로드를 엔티티의 로드 합계에 추가하고, 그 과정에서 decay 한 적이 있으면
  • 코드 라인 6에서 로드 평균을 재산출한다.
  • 코드 라인 7~9에서 avg->util_est.enqueued의 UTIL_AVG_UNCHANGED 플래그가 설정되어 있는 경우 제거하여 로드 평균이 재산출되었음을 인식하게 한다. 그런 후 decay 하여 로드 평균이 재산출 되었음을 의미하는 1을 반환한다.
  • 코드 라인 12에서 decay 없어서 로드 평균이 재산출 되지 않았음을 의미하는 0을 반환한다.

 

cfs_se_util_change()

kernel/sched/pelt.h

/*
 * When a task is dequeued, its estimated utilization should not be update if
 * its util_avg has not been updated at least once.
 * This flag is used to synchronize util_avg updates with util_est updates.
 * We map this information into the LSB bit of the utilization saved at
 * dequeue time (i.e. util_est.dequeued).
 */
#define UTIL_AVG_UNCHANGED 0x1
static inline void cfs_se_util_change(struct sched_avg *avg)
{
        unsigned int enqueued;

        if (!sched_feat(UTIL_EST))
                return;

        /* Avoid store if the flag has been already set */
        enqueued = avg->util_est.enqueued;
        if (!(enqueued & UTIL_AVG_UNCHANGED))
                return;

        /* Reset flag to report util_avg has been updated */
        enqueued &= ~UTIL_AVG_UNCHANGED;
        WRITE_ONCE(avg->util_est.enqueued, enqueued);
}

avg->util_est.enqueued의 UTIL_AVG_UNCHANGED 플래그가 설정되어 있는 경우 제거하여 로드 평균이 재산출되었음을 인식하게 한다.

 


로드 합계 및 평균 산출

로드 합계 산출

___update_load_sum()

kernel/sched/pelt.c

/*
 * We can represent the historical contribution to runnable average as the
 * coefficients of a geometric series.  To do this we sub-divide our runnable
 * history into segments of approximately 1ms (1024us); label the segment that
 * occurred N-ms ago p_N, with p_0 corresponding to the current period, e.g.
 *
 * [<- 1024us ->|<- 1024us ->|<- 1024us ->| ...
 *      p0            p1           p2
 *     (now)       (~1ms ago)  (~2ms ago)
 *
 * Let u_i denote the fraction of p_i that the entity was runnable.
 *
 * We then designate the fractions u_i as our co-efficients, yielding the
 * following representation of historical load:
 *   u_0 + u_1*y + u_2*y^2 + u_3*y^3 + ...
 *
 * We choose y based on the with of a reasonably scheduling period, fixing:
 *   y^32 = 0.5
 *
 * This means that the contribution to load ~32ms ago (u_32) will be weighted
 * approximately half as much as the contribution to load within the last ms
 * (u_0).
 *
 * When a period "rolls over" and we have new u_0`, multiplying the previous
 * sum again by y is sufficient to update:
 *   load_avg = u_0` + y*(u_0 + u_1*y + u_2*y^2 + ... )
 *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
 */
static __always_inline int
___update_load_sum(u64 now, struct sched_avg *sa,
                  unsigned long load, unsigned long runnable, int running)
{
        u64 delta;

        delta = now - sa->last_update_time;
        /*
         * This should only happen when time goes backwards, which it
         * unfortunately does during sched clock init when we swap over to TSC.
         */
        if ((s64)delta < 0) {
                sa->last_update_time = now;
                return 0;
        }

        /*
         * Use 1024ns as the unit of measurement since it's a reasonable
         * approximation of 1us and fast to compute.
         */
        delta >>= 10;
        if (!delta)
                return 0;

        sa->last_update_time += delta << 10;

        /*
         * running is a subset of runnable (weight) so running can't be set if
         * runnable is clear. But there are some corner cases where the current
         * se has been already dequeued but cfs_rq->curr still points to it.
         * This means that weight will be 0 but not running for a sched_entity
         * but also for a cfs_rq if the latter becomes idle. As an example,
         * this happens during idle_balance() which calls
         * update_blocked_averages()
         */
        if (!load)
                runnable = running = 0;

        /*
         * Now we know we crossed measurement unit boundaries. The *_avg
         * accrues by two steps:
         *
         * Step 1: accumulate *_sum since last_update_time. If we haven't
         * crossed period boundaries, finish.
         */
        if (!accumulate_sum(delta, sa, load, runnable, running))
                return 0;

        return 1;
}

로드 합계들을 구한다. 그리고 decay 여부를 반환한다.

  • 코드 라인 7에서 현재 시각에서 last_update_time 시각까지의 차이를 delta로 알아온다.
  • 코드 라인 12~15에서 unstable한 TSC 클럭을 사용하는 아키텍처등에서는 초기에 delta가 0보다 작아지는 경우도 발생한다. 이러한 경우에는 last_update_time만 현재 시각으로 갱신하고 그냥 0을 반환한다.
  • 코드 라인 21~23에서 나노초 단위인 delta를 PELT가 로드 값 산출에 사용하는 마이크로초 단위로 바꾸고, 이 값이 0인 경우 그냥 0을 반환한다.
  • 코드 라인 25에서 last_update_time에 마이크로초 이하를 절삭한 나노초로 변환하여 저장한다. PELT의 로드 산출에는 항상 마이크로초 이하의 나노초들은 적용하지 않고 보류한다.
  • 코드 라인 36~37에서 @load 값이 0인 경우 runnable과 running에는 0을 반환한다.
  • 코드 라인 46~47에서 delta 기간의 새 로드를 반영하여 여러 로드들의 합계들을 모두 구한다. 로드 합계 산출 후 기존 로드합계의 decay가 이루어지지 않은 경우 0을 반환한다.
  • 코드 라인 49에서 로드 산출에 decay 하였으므로 1을 반환한다. (decay가 되면 이 함수 이후에 산출된 로드 합계를 사용하여 로드 평균을 재산출해야 한다.)

 

period

PELT 시간 단위 기준은 다음과 같은 특성을 가진다.

  • PELT 클럭 값들은 ns 단위이다.
  • PELT 연산에 사용하는 시간 단위는 1024(ns)로 정렬하여 사용하고, 약 1(us)이다.
  • Period 단위는 1024 * 1024(ns)로 정렬하여 사용하고, 약 1(ms)이다.
    • Decay는 보통 Period 단위로 정렬된

 

다음 그림은 pelt와 관련된 시간 단위들을 시각적으로 표현하였다.

 

다음 그림은 ___update_load_sum() 함수에서 Step 1 구간의 Old 로드의 decay 부분 산출 과정을 보여준다.

  • decay 구간은 1024us 단위마다 수행하며, 각 구간마다 decay 적용률이 반영될때 현재 시각에 가까운 구간일 수록 더 높게 로드값을 반영하는 것을 알 수 있다.
    • C 시작 구간의 짤린 부분은 1 period로 포함시켜 decay 한다.
  • now가 있는 끝 구간의 짤린 부분은 decay 하지 않는다.

 

다음 그림은 Step 1부분의 Old 로드의 decay 기간과 New 로드의 반영되는 부분을 모두 보여준다.

 

예) old 로드 합계=20000, new 로드 값=2048로 최종 로드를 구해본다.

  • Step 1) decay_load(old 로드 합계, periods)
    • = decay_load(20000, 4)
  • Step 2) new 로드 * __accumalate_pelt_segments(periods, d1, d3)
    • 2048 * __accumalate_pelt_segments(4, 921, 200)

 

accumulate_sum()

kernel/sched/pelt.c

/*
 * Accumulate the three separate parts of the sum; d1 the remainder
 * of the last (incomplete) period, d2 the span of full periods and d3
 * the remainder of the (incomplete) current period.
 *
 *           d1          d2           d3
 *           ^           ^            ^
 *           |           |            |
 *         |<->|<----------------->|<--->|
 * ... |---x---|------| ... |------|-----x (now)
 *
 *                           p-1
 * u' = (u + d1) y^p + 1024 \Sum y^n + d3 y^0
 *                           n=1
 *
 *    = u y^p +                                 (Step 1)
 *
 *                     p-1
 *      d1 y^p + 1024 \Sum y^n + d3 y^0         (Step 2)
 *                     n=1
 */
static __always_inline u32
accumulate_sum(u64 delta, struct sched_avg *sa,
               unsigned long load, unsigned long runnable, int running)
{
        u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
        u64 periods;

        delta += sa->period_contrib;
        periods = delta / 1024; /* A period is 1024us (~1ms) */

        /*
         * Step 1: decay old *_sum if we crossed period boundaries.
         */
        if (periods) {
                sa->load_sum = decay_load(sa->load_sum, periods);
                sa->runnable_load_sum =
                        decay_load(sa->runnable_load_sum, periods);
                sa->util_sum = decay_load((u64)(sa->util_sum), periods);

                /*
                 * Step 2
                 */
                delta %= 1024;
                contrib = __accumulate_pelt_segments(periods,
                                1024 - sa->period_contrib, delta);
        }
        sa->period_contrib = delta;

        if (load)
                sa->load_sum += load * contrib;
        if (runnable)
                sa->runnable_load_sum += runnable * contrib;
        if (running)
                sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;

        return periods;
}

마이크로초 단위의 @delta 기간 동안 새 @load를 반영한 여러 로드 합계 및 평균들을 산출한다. 반환되는 값은 decay에 사용한 기간 수이다.

  • 코드 라인 5에서 contrib 값은 1024us 미만에서만 사용되는 값이다. 여기서 delta가 1024us 미만일 경우에만 사용하기 위해 delta를 contrib에 미리 대입한다.
  • 코드 라인 8에서 인자로 전달받은 @delta에 기존 갱신 타임에 1024us 미만이라 decay를 하지 않은 마이크로 단위의 기간 잔량 sa->period_contrib를 추가한다.
  • 코드 라인 9에서 1024us 단위로 decay하기 위해 delta를 1024로 나눈다.
    • 커널에서 하나의 period는 정확히 1024us이다. 그런데 사람은 오차를 포함하여 약 1ms라고 느끼면 된다.
  • 코드 라인 14~18에서 Step 1 루틴으로 과거 값을 먼저 decay 한다. 즉 기존 load_sum, runnable_load_sum 및 util_sum 값들을 periods 만큼 decay 한다.
    • old 로드는 1024us 단위로 정렬하여 decay하므로 나머지에 대해서는 decay하지 않는다.
  • 코드 라인 23~25에서 Step 1에서 decay하여 산출한 로드 값에 Step 2의 새로운 로드를 반영하기 위해 기여분(contrib)을 곱하여 산출한다.
    • 새 로드 값 =  old 로드 * decay + new 로드 * contrib
      • decay_load(old 로드, 1024us 단위 기간 수) + new 로드 * __accumulate_pelt_segments()
  • 코드 라인 27에서 1024us 단위 미만이라 decay 처리하지 못한 나머지 마이크로초 단위의 delta를 sa->period_contrib에 기록해둔다. 이 값은 추후 다음 갱신 기간 delta에 포함하여 활용한다.
  • 코드 라인 29~32에서 기존 로드 합계를 decay한 값에 새 load * contrib를 적용하여 로드합계를 산출한다.
  • 코드 라인 33~34에서 util_sum 값의 경우 1024 * contrib를 추가하여 산출한다.
  • 코드 라인 36에서 1024us 단위로 decay 산출한 기간 수(periods)를 반환한다.

 

기여분(contrib)

기여분은 최대 로드 기간인 LOAD_AVG_MAX(47748)를 초과할 수 없다.

  • avg.load_sum += load * contrib
    • 예) 기여분(contrib) = LOAD_AVG_MAX * 10% = 4774
  • avg.runnable_load_sum += runnable * contrib
  • avg.util_sum += contrib * 1024

 

로드 감쇠

decay_load()

kernel/sched/pelt.c

/*
 * Approximate:
 *   val * y^n,    where y^32 ~= 0.5 (~1 scheduling period)
 */
static u64 decay_load(u64 val, u64 n)
{
        unsigned int local_n;

        if (unlikely(n > LOAD_AVG_PERIOD * 63))
                return 0;

        /* after bounds checking we can collapse to 32-bit */
        local_n = n;

        /*
         * As y^PERIOD = 1/2, we can combine
         *    y^n = 1/2^(n/PERIOD) * y^(n%PERIOD)
         * With a look-up table which covers y^n (n<PERIOD)
         *
         * To achieve constant time decay_load.
         */
        if (unlikely(local_n >= LOAD_AVG_PERIOD)) {
                val >>= local_n / LOAD_AVG_PERIOD;
                local_n %= LOAD_AVG_PERIOD;
        }

        val = mul_u64_u32_shr(val, runnable_avg_yN_inv[local_n], 32);
        return val;
}

로드 값 @val을 @n 기간(1024us) 에 해당하는 감쇠 비율로 줄인다. n=0인 경우 감쇠 없는 1.0 요율이고, n=32인 경우 절반이 줄어드는 0.5 요율이다.

  • 코드 라인 5~6에서 기간 @n이 2016(32 * 63)을 초과하는 경우 많은 기간을 감쇠시켜 산출을 하더라도 0이 되므로 성능을 위해 연산 없이 곧장 0으로 반환한다.
  • 코드 라인 9에서 기간 @n을 32비트 타입으로 변환한다.
  • 코드 라인 18~21에서 기간 @n은 32 단위로 절반씩 줄어든다. 따라서 기간 @n이 32 이상인 경우 val 값을 n/32 만큼 시프트하고, local_n 값은 32로 나눈 나머지를 사용한다.
  • 코드 라인 23~24에서 미리 계산해둔 decay 요율을 inverse 형태로 담은 runnable_avg_yN_inv[]테이블에서 local_n 인덱스에 해당하는 mult 값을 val에 곱하고 정밀도 32비트를 우측 시프트하여 반환한다.

 

미리 만들어진 PELT용 decay factor

kernel/sched/fair.c

static const u32 runnable_avg_yN_inv[] __maybe_unused = {
        0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, 0xeac0c6e6, 0xe5b906e6,
        0xe0ccdeeb, 0xdbfbb796, 0xd744fcc9, 0xd2a81d91, 0xce248c14, 0xc9b9bd85,
        0xc5672a10, 0xc12c4cc9, 0xbd08a39e, 0xb8fbaf46, 0xb504f333, 0xb123f581,
        0xad583ee9, 0xa9a15ab4, 0xa5fed6a9, 0xa2704302, 0x9ef5325f, 0x9b8d39b9,
        0x9837f050, 0x94f4efa8, 0x91c3d373, 0x8ea4398a, 0x8b95c1e3, 0x88980e80,
        0x85aac367, 0x82cd8698,
};

#define LOAD_AVG_PERIOD 32
#define LOAD_AVG_MAX 47742

약 32ms(1024us * 32)까지 decay될 요율(factor)이 미리 계산되어 있는 runnable_avg_yN_inv[] 테이블은 나눗셈 연산을 하지 않게 하기 위해 decay 요율마다 mult 값이 다음 수식으로 만들어졌다.

  • n 번째 요율을 계산하는 수식(32bit shift 적용):
    • ‘y^n’은 항상 1.0 이하의 실수 값이다. 이 값에 32비트 정밀도를 적용하여 이진화 정수화한다.
      • ‘y^k * 2^32’ 수식을 사용한다.  (단 y^32=0.5)
    • y값을 먼저 구해보면
      • y=0.5^(1/32)=0.97852062…
    • 인덱스 값 n에 0부터 32까지 사용한 결과 값은? (테이블 구성은 0~31 까지)
      • 인덱스 n에 0을 주면 y^0 * 2^32 = 0.5^(1/32)^0 * (2^32) = 1.0 << 32 = 0x1_0000_0000 (32bit로 구성된 테이블 값은 0xffff_ffff 사용)
      • 인덱스 n에 1 을 주면 y^1 * 2^32 = 0.5^(1/32)^1 * (2^32) = 0.97852062 << 32 = 0xfa83_b2db
      • 인덱스 n에 2을 주면 y^2 * 2^32 = 0.5^(1/32)^2 * (2^32) = 0.957603281 << 32 = 0xf525_7d15
      • 인덱스 n에 31을 주면 y^2 * 2^32 = 0.5^(1/32)^31 * (2^32) = 0.510948574 << 32 = 0x82cd_8698
      • 인덱스 n에 32을 주면 y^2 * 2^32 = 0.5^(1/32)^31 * (2^32) = 0.5 << 32 = 0x7fff_ffff

 

__accumulate_pelt_segments()

kernel/sched/pelt.c

static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
{
        u32 c1, c2, c3 = d3; /* y^0 == 1 */

        /*
         * c1 = d1 y^p
         */
        c1 = decay_load((u64)d1, periods);

        /*
         *            p-1
         * c2 = 1024 \Sum y^n
         *            n=1
         *
         *              inf        inf
         *    = 1024 ( \Sum y^n - \Sum y^n - y^0 )
         *              n=0        n=p
         */
        c2 = LOAD_AVG_MAX - decay_load(LOAD_AVG_MAX, periods) - 1024;

        return c1 + c2 + c3;
}

새 로드에 곱하여 반영할 기여율(contrib)을 반환한다. 기여율을 산출하기 위해 @periods는 새 로드가 decay할 1024us 단위의 기간 수이며, 처리할 기간의 1024us 정렬되지 않는 1024us 미만의 시작 @d1 구간과 1024us 미만의 마지막 d3 구간을 사용한다.

  • 코드 라인 3에서 1024us 미만의 d3 구간은 y^0 구간을 적용받으므로 d3 * y^0 = d3이다. 그러므로 기여분에 그대로 d3 값을 사용하기 위해  c3에 대입한다.
  • 코드 라인 8에서 d1 구간에 대해 @periods 만큼 decay를 수행하여 c1을 구한다.
  • 코드 라인 19에서 d2 구간을 decay 하기 위한 변형된 수식을 사용하여 c2를 구한다.
  • 코드 라인 21에서 c1 + c2 + c3 한 값을 반환한다. 이 값은 새 로드에 곱하여 기여율(contrib)로 사용될 예정이다.

 

예) 새 로드 값=3072(3.0), periods=32, d1=512, d3=768인 경우 기여분(contrib)은?

  • y = 0.5^(1/32) = 0.978572…
  • c1 = d1 * y^periods = 500 * (0.5^(1/32))^32 = 250
  • c2 = 1024 * (y^1 + … + y^(periods-1)) = 22870
    • = 1024 * ((y ^ 0 + … + y^inf) – (y^periods + … + y^inf) – (y^0))
    • = 1024 * (y ^ 0 + … + y^inf) – 1024 * (y^periods + … + y^inf) – 1024 * y^0
    • = 47742 – decay_load(47742, 32) – 1024
    • = 47742 – 24359 – 1024 = 23336
  • c3 = 750
  • return = 256 + 22870 + 768 = 23894
    • 전체 로드 기간 LOAD_AVG_MAX(47742) 대비 50%를 기여분(contrib)으로 반환한다.

 

다음 그림은 새 로드가 반영될 때 사용할 기여분(contrib)을 산출할 때 사용되는 구간들을 보여준다.

 

로드 평균 산출

___update_load_avg()

kernel/sched/pelt.c

static __always_inline void
___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
{
        u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;

        /*
         * Step 2: update *_avg.
         */
        sa->load_avg = div_u64(load * sa->load_sum, divider);
        sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
        WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
}

@sa의 로드, 러너블 로드 및 유틸 평균들을 재산출한다.

  • 코드 라인 4에서 divider 값은 decay를 고려했을 떄의 최대 기간 값을 사용해야 하고, 이번 산출에서 decay에 반영하지 못할 기간은 제외해야 한다. LOAD_AVG_MAX는 모든 decay 로드 값을 더했을 때 최대값이 될 수 있는 값으로 이 값을 사용하여 최대 기간으로 사용한다. 그래서 어떤 로드 합계 / divider가 새 로드에 반영할 비율이 된다. 그런데 decay 산출할 때 마다 1024us 미만의 기간은 decay를 하지 않아야 하므로 최대 기간에서 빼야한다. 이렇게 제외시켜야할 기간은 다음과 같다.
    • 1024(us) – 기존 산출에서 decay 하지 않은 값(sa->period_contrib) = 새 산출에서 decay 하지 않아 제외 시켜야 할 값
      • 지난 산출에서 3993(921+1024+1024+1024+921)us 의 시간 중 3 기간에 대한 3072 us를 decay 하는데 사용하였고, 921 us는 사용하지 않았다. 이번 산출에서는 그 기존 분량은 decay에 사용하고, 나머지 103us는 decay에 사용하지 않는 기간이된다.
    • 참고: sched/cfs: Make util/load_avg more stable (2017, v
  • 코드 라인 9~10에서 @load 및 @runnable에 이 함수 진입 전에 산출해둔 로드 섬들을 divider로 나눈 비율을 곱하여 적용한다.
  • 코드 라인 11에서 유틸 평균은 유틸 합계를 divider로 나눈 값으로 갱신한다.

 

sa->period_contrib

period_contrib는 지난번 decay 되지 않았던 1 period(1024*1024us) 미만의 시간을 저장해둔다.

 

다음 그림은 period_contrib에 대한 정확한 위치를 보여준다.

 

LOAD_AVG_MAX

이 값은 하나의 nice-0 우선순위의 태스크에 대한 로드 weight(104)을 무한대 n번까지 decay한 값을 모두 더했을 때 나올 수 있는 최대 값으로 로드 평균 산출을 위한 최대 산출 기간으로 사용한다.

  • n=∞(무한)
  • 평활 계수 y를 32번 감쇠할 때 0.5일때, y 값의 산출은 다음과 같다.
    • y^32=0.5, y=0.5^(1/32) = 약 0.97852

예) decay 총합 = y^1  + y^2 + y^3 + … + y^n = 0.978572 + 0.957603 + 0.937084 + … 0.0000 = 약 46.62304688

  • 1ms 단위의 로드 값 1024(10비트 정확도)를 계속 n번 만큼 decay 한 수를 합하면?
    • = 1024 * y^1  + 1024 * y^2 + 1024 * y^3 + … + 1024 * y^n
    • = 1024 * (y^1  + y^2 + y^3 + … + y^n) =
    • = 1002 + 980 + 959 + … +  0
    • = 47742

 

다음 그림은 LOAD_AVG_MAX에 대한 값을 산출하는 과정을 보여준다.

 

다음과 같이 로드 값 1024를 y^n(1부터 32까지) 누적한 값을 산출해본다. (sum=23,382)

 

다음 그림은 ___update_load_avg() 함수가 하는 일중 로드 평균만 산출하는 과정을 보여준다.

 

다음 그림은 태스크용 엔티티의 로드 평균을 산출한 값들이다.

  • 1000HZ 틱을 10번 진행하였을 때의 로드 합계 및 평균을 보여준다.

 

다음 그림은 위의 조건으로 태스크용 엔티티의 로드 합계를 456틱까지 진행한 모습을 보여준다.

  • 201틱부터 ruunning을 0으로 하여 유틸 로드를 하향시켰다.
    • util_sum은 단위가 scale up(1024)되어 아래 그래프에는 표현하지 않았다.
  • 301틱부터 runnable을 0으로 하여 로드 및 러너블 로드를 하향시켰다.
  • 빨간색은 load_sum 및 runnable_sum

 

다음 그림은 위의 조건으로 태스크용 엔티티의 로드 평균을 456틱까지 진행한 모습을 보여준다.

  • 201틱부터 ruunning을 0으로 하여 유틸 로드를 하향시켰다.
  • 301틱부터 runnable을 0으로 하여 로드 및 러너블 로드를 하향시켰다.
  • 노란색은 util_avg
  • 빨간색은 load_avg 및 runnable_avg

 


cfs 런큐 로드 평균 갱신

엔티티의 로드 평균을 구했으면 다음은 cfs 런큐로 로드를 모으고 이에 대한 cfs 런큐 로드 평균을 구해야 한다.

 

update_cfs_rq_load_avg()

kernel/sched/fair.c

/**
 * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
 * @now: current time, as per cfs_rq_clock_pelt()
 * @cfs_rq: cfs_rq to update
 *
 * The cfs_rq avg is the direct sum of all its entities (blocked and runnable)
 * avg. The immediate corollary is that all (fair) tasks must be attached, see
 * post_init_entity_util_avg().
 *
 * cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.
 *
 * Returns true if the load decayed or we removed load.
 *
 * Since both these conditions indicate a changed cfs_rq->avg.load we should
 * call update_tg_load_avg() when this function returns true.
 */
static inline int
update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
{
        unsigned long removed_load = 0, removed_util = 0, removed_runnable_sum = 0;
        struct sched_avg *sa = &cfs_rq->avg;
        int decayed = 0;

        if (cfs_rq->removed.nr) {
                unsigned long r;
                u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;

                raw_spin_lock(&cfs_rq->removed.lock);
                swap(cfs_rq->removed.util_avg, removed_util);
                swap(cfs_rq->removed.load_avg, removed_load);
                swap(cfs_rq->removed.runnable_sum, removed_runnable_sum);
                cfs_rq->removed.nr = 0;
                raw_spin_unlock(&cfs_rq->removed.lock);

                r = removed_load;
                sub_positive(&sa->load_avg, r);
                sub_positive(&sa->load_sum, r * divider);

                r = removed_util;
                sub_positive(&sa->util_avg, r);
                sub_positive(&sa->util_sum, r * divider);

                add_tg_cfs_propagate(cfs_rq, -(long)removed_runnable_sum);

                decayed = 1;
        }

        decayed |= __update_load_avg_cfs_rq(now, cfs_rq);

#ifndef CONFIG_64BIT
        smp_wmb();
        cfs_rq->load_last_update_time_copy = sa->last_update_time;
#endif

        if (decayed)
                cfs_rq_util_change(cfs_rq, 0);

        return decayed;
}

cfs 런큐의 로드/유틸 평균을 갱신한다.

  • 코드 라인 7~29에서 cfs 런큐에서 엔티티가 detach되었을 때 cfs 런큐에서 로드 합계 및 평균을 직접 감산시키지 않고, cfs_rq->removed에 로드/유틸 평균 및 로드 합계 등을 감소시켜달라고 요청해두었었다. 성능을 높이기 위해 cfs 런큐의 락을 획득하지 않고 removed를 이용하여 atomic 명령으로 갱신한다. 다음은 cfs 로드 평균 갱신 시에 다음과 같이 처리한다.
    • cfs 런큐의 removed에서 이 값들을 로컬 변수로 읽어오고 0으로 치환한다.
    • cfs 런큐의 로드/유틸 합계와 평균에서 이들을 감소시킨다.
    • cfs 런큐에 러너블 합계를 전파하기 위해 추가한다.
  • 코드 라인 31에서 cfs 런큐의 로드 평균을 갱신한다.
  • 코드 라인 38~39에서 유틸 값이 바뀌면 cpu frequency 변경 기능이 있는 시스템의 경우 주기적으로 변경한다.

 

다음 그림은 cfs 런큐의 로드 평균을 산출한 값들이다.

  • 1000HZ 틱을 10번 진행하였을 때의 로드 합계 및 평균을 보여준다.
  • 최초 2개의 nice-0 태스크 2개가 동작하는 상태이다.

 

다음 그림은 위의 조건으로 cfs 런큐의 로드 합계를 456틱까지 진행한 모습을 보여준다.

  • 최초 구간부터 2개의 nice-0 태스크 2개가 동작시켰다.
  • 51틱 구간부터 1개의 태스크만 동작시켰다.
  • 101틱 구간부터 동작하는 태스크가 없다.
  • 201틱부터 다시 2개의 태스크를 동작시켰다.
  • 파란색은 load_sum
  • 빨간색은 runnable_sum
  • 노란색은 util_sum

 

다음 그림은 위의 조건으로 태스크용 엔티티의 로드 평균을 456틱까지 진행한 모습을 보여준다.

  • 파란색은 load_avg
  • 빨간색은 runnable_avg
  • 노란색은 util_avg

 

 

__update_load_avg_cfs_rq()

kernel/sched/pelt.c

int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
{
        if (___update_load_sum(now, &cfs_rq->avg,
                                scale_load_down(cfs_rq->load.weight),
                                scale_load_down(cfs_rq->runnable_weight),
                                cfs_rq->curr != NULL)) {

                ___update_load_avg(&cfs_rq->avg, 1, 1);
                trace_pelt_cfs_tp(cfs_rq);
                return 1;
        }

        return 0;
}

cfs 런큐의 로드 합계 및 평균을 갱신한다. 반환 되는 값은 cfs 런큐의 로드 평균의 재산출 여부이다.

  • 코드 라인 3~6에서 cfs 런큐의 로드 합계를 갱신한다. 그 과정에서 decay 한 적이 있으면
  • 코드 라인 8~10에서 cfs 런큐의 로드 평균을 갱신하고, 1을 반환한다.
  • 코드 라인 13에서 decay 없어서 cfs 런큐의 로드 평균이 재산출 되지 않았음을 의미하는 0을 반환한다.

 

태스크용 엔티티 -> CFS 런큐 -> 그룹 엔티티의 로드 관계

 

/*
 * sched_entity:
 *
 *   task:
 *     se_runnable() == se_weight()
 *
 *   group: [ see update_cfs_group() ]
 *     se_weight()   = tg->weight * grq->load_avg / tg->load_avg
 *     se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
 *
 *   load_sum := runnable_sum
 *   load_avg = se_weight(se) * runnable_avg
 *
 *   runnable_load_sum := runnable_sum
 *   runnable_load_avg = se_runnable(se) * runnable_avg
 *
 * XXX collapse load_sum and runnable_load_sum
 *
 * cfq_rq:
 *
 *   load_sum = \Sum se_weight(se) * se->avg.load_sum
 *   load_avg = \Sum se->avg.load_avg
 *
 *   runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
 *   runnable_load_avg = \Sum se->avg.runable_load_avg
 */

엔티티:

태스크용 엔티티:
  • se_runnable() == se_weight()
    • 태스크용 엔티티는 러너블과 러닝 비율이 항상 같으므로 러너블 가중치와 로드 가중치가 항상 같다.

 

그룹 엔티티:
  • update_cfs_group() -> calc_group_shares() – (3)번 참고:
    •                                                         grq->load_avg
    • se_weight() = tg->weight * ————————–
    •                                                           tg->load_avg
    •                                                                 grq->runnable_load_avg
    • se_runnable() = se_weight(se) * ————————————
    •                                                                          grq->load_avg

 

  • load_sum := runnable_sum
    • 태스크 엔티티등의 러너블 로드에 변화가 생길 때 상위 그룹에 러너블 합계를 전파한다. 상위 그룹에서는 전파한 러너블 합계 값을 더해 이 값을 적용한다. 단 이 값은 LOAD_AVG_MAX ~ running_sum 범위에서 clamp 한다.
    • 참고: update_tg_cfs_runnable()
  • load_avg = se_weight(se) * runnable_avg
    •                                      runnable_sum
    • runnable_avg = —————————–
    •                                   LOAD_AVG_MAX
  • runnable_load_sum := runnable_sum
    • 로드 합계와 동일하게 러너블 로드 합계에도 적용한다.
  • runnable_load_avg = se_runnable(se) * runnable_avg
    • 러너블 로드 평균은 그룹 엔티티의 러너블 가중치와 runnable_avg를 곱하여 산출한다.

 

 CFS 런큐:

  • load_sum = \Sum se_weight(se) * se->avg.load_sum
    • cfs 런큐에 엔큐된 엔티티들의 가중치와 로드 합계를 곱한 값들을 모두 더한 값이다.
  • load_avg = \Sum se->avg.load_avg
    • cfs 런큐에 엔큐된 엔티티들의 로드 평균을 모두 더한 값이다.
  • runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
    • cfs 런큐에 엔큐된 엔티티들의 러너블 가중치와 러너블 로드 합계를 곱한 값들을 모두 더한 값이다.
  • runnable_load_avg = \Sum se->avg.runable_load_avg
    • cfs 런큐에 엔큐된 엔티티들의 러너블 로드 평균을 모두 더한 값이다.

 

다음 그림은 루트 그룹에 두 개의 하위 그룹 A, B를 만들고 다음과 같은 설정을 하였을 때 예상되는 cpu utilization을 보고자 한다.

  • A 그룹
    • cpu.shares=1024 (default)
    • nice 0 태스크 (no sleep)
  • B 그룹
    • cpu.shares=2048
    • nice -10 태스크 (no sleep)
    • nice -13 태스크 (no sleep)

다음 그림은 A 그룹에서 1개의 태스크만을 가동하였을 때 load 평균등을 알아본다.

 

다음 그림은 A, B 그룹에서 각각 1개의 태스크를 가동하였을 때 load 평균등을 알아본다.

 

다음 그림은 A 그룹에 1개의 태스크, B 그룹에 2개의 태스크를 가동하였을 때 load 평균등을 알아본다.

실제 평균은 다음과 같이 확인할 수 있다.

  • 실제 다른 프로세스들이 약간 동작하고 있음을 감안하여야 한다.
  PID USER      PR  NI    VIRT    RES    SHR S %CPU %MEM     TIME+ COMMAND
----------------------------------------------------------------------------
 1032 root       7 -13    1608    324    256 R 41.3  0.0   0:21.67 full_load
  969 root      20   0    1608    356    288 R 31.3  0.0  29:24.63 full_load
 1011 root      10 -10    1608    368    304 R 21.0  0.0   6:52.56 full_load

 


PELT Migration Propagation

kernel/sched/fair.c

/*
 * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
 * propagate its contribution. The key to this propagation is the invariant
 * that for each group:
 *
 *   ge->avg == grq->avg                                                (1)
 *
 * _IFF_ we look at the pure running and runnable sums. Because they
 * represent the very same entity, just at different points in the hierarchy.
 *
 * Per the above update_tg_cfs_util() is trivial and simply copies the running
 * sum over (but still wrong, because the group entity and group rq do not have
 * their PELT windows aligned).
 *
 * However, update_tg_cfs_runnable() is more complex. So we have:
 *
 *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg          (2)
 *
 * And since, like util, the runnable part should be directly transferable,
 * the following would _appear_ to be the straight forward approach:
 *
 *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg       (3)
 *
 * And per (1) we have:
 *
 *   ge->avg.runnable_avg == grq->avg.runnable_avg
 *
 * Which gives:
 *
 *                      ge->load.weight * grq->avg.load_avg
 *   ge->avg.load_avg = -----------------------------------             (4)
 *                               grq->load.weight
 *
 * Except that is wrong!
 *
 * Because while for entities historical weight is not important and we
 * really only care about our future and therefore can consider a pure
 * runnable sum, runqueues can NOT do this.
 *
 * We specifically want runqueues to have a load_avg that includes
 * historical weights. Those represent the blocked load, the load we expect
 * to (shortly) return to us. This only works by keeping the weights as
 * integral part of the sum. We therefore cannot decompose as per (3).
 *
 * Another reason this doesn't work is that runnable isn't a 0-sum entity.
 * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
 * rq itself is runnable anywhere between 2/3 and 1 depending on how the
 * runnable section of these tasks overlap (or not). If they were to perfectly
 * align the rq as a whole would be runnable 2/3 of the time. If however we
 * always have at least 1 runnable task, the rq as a whole is always runnable.
 *
 * So we'll have to approximate.. :/
 *
 * Given the constraint:
 *
 *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
 *
 * We can construct a rule that adds runnable to a rq by assuming minimal
 * overlap.
 *
 * On removal, we'll assume each task is equally runnable; which yields:
 *
 *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
 *
 * XXX: only do this for the part of runnable > running ?
 *
 */

엔티티의 마이그레이션 시 엔티티가 PELT 계층 구조에 가입/탈퇴할 때 그 기여도를 전파(propagate)해야 한다. 이 전파의 핵심은 불변성이다.

  • 다음 약자를 혼동하지 않도록 한다.
    • tg: 태스크 그룹 (struct task_group *)
    • ge: 그룹 엔티티 (struct sched_entity *)
    • grq: 그룹 cfs 런큐 (struct cfs_rq *)

 

  • (1) ge->avg == grq->avg
    • 그룹을 대표하는 그룹 엔티티의 로드 통계와 그룹 cfs 런큐의 통계는 같다.
    • 순수(pure) 러닝 합계와 순수(pure) 러너블 합계를 검토한다. 왜냐하면 그들은 계층의 서로 다른 지점에서 매우 동일한 엔티티를 표현하고 있기 때문이다.
    • update_tg_cfs_util()은 간단하게 러닝 합계를 상위로 복사한다.
      • 복사한 값은 서로 다른 PELT 계층 구조에서 윈도우가 정렬되어 있지 않기 때문에 약간 다르므로 잘못되었다.
      • 추후 커널 v5.8-rc1에서 그룹 엔티티와 그룹 cfs 런큐 사이의 PELT window를 정렬하여 약간의 잘못된 점을 바로 잡았다.
  • (2) ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg
    • 그룹 엔티티의 로드 평균은 그룹 엔티티의 러너블 평균에 가중치(weight)를 곱한 값이다.
  • (3) grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg
    • util과 마찬가지로, 러너블 파트는 직접 이전할 수 있어야 하므로 직선적 전진 접근방식이 될 것이다
  • (4) ge->avg.load_avg = ge->load.weight * grq->avg.load_avg / grq->load.weight
    • (2)번 수식을 사용하고 싶지만, 엔티티의 러너블 평균 대신 (3)번과 같이 cfs 런큐의 러너블 평균을 사용한다.
    • (1) 번에서 말한 것처럼 ge->avg.runnable_avg == grq->avg.runnable_avg 이다. 이를 이용하여 (4)번 수식이 성립한다.

 

다만 위의 접근식에는 다음과 같은 잘못된 점이 있다.

  • historical weights는 중요하지 않지만 cfs 런큐는 순수한 러너블 로드를 산출할 수 없어 historical weights를 고려한다는 점
  • cfs 런큐의 historical weights를 포함하는 로드 평균은 블럭드 로드(uninterruptible 상태의 슬립 태스크지만 금방 깨어날거라 예상)를 포함한다는 점 때문에 (3)번으로 해결할 수 없다. 산술적으로 슬립상태의 태스크를 로드로 계산해야 하므로 정확히 산출할 수 없다.
  • 또 다른 이유로 러너블 기간이 얼마나 중복되는지를 정확히 알 수 없다.
    • 러너블이 0-sum 엔티티가 아니다.
    • 각각 2/3가 러너블한 2개의 작업이 포함된 rq를 상상해 보자. 그런 다음, rq 자체는 이러한 작업의 러너블 섹션이 어떻게 겹치는지에 따라 2/3와 1 사이의 어느 곳에서나 실행될 수 있다(또는 그렇지 않다). 만약 전체적으로 rq를 완벽하게 정렬한다면, 그 시간의 2/3가 실행될 수 있을 것이다.
    • 최소 하나의 실행 가능한 작업을 가지고 있다면, rq 전체는 항상 러너블 상태이다.

 

그래서 제약 조건을 주면 :

  • ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  • 러너블을 추가 시 최소한의 중복(overlap)을 가정한다.
    • 얼마 기간이 겹쳤는지 모른다. 이러한 경우에는 최소한의 중복(overlap) 기간만을 사용한다.
  • 제거시 각 작업을 동일하게 실행할 수 있다고 가정한다.
    • grq-> avg.runnable_sum = grq-> avg.load_sum / grq-> load.weight

 

다음 그림은 그룹 엔티티와 cfs 런큐의 로드 평균에 대해 이론적으로 동일하다는 것을 보여준다.

 

다음은 그룹 엔티티와 cfs 런큐의 로드 평균이 실제로는 약간 다른 것을 보여준다.

cfs_rq[5]:/B
  .exec_clock                    : 143287629.494567
  .MIN_vruntime                  : 0.000001
  .min_vruntime                  : 143287628.829813
  .max_vruntime                  : 0.000001
  .spread                        : 0.000000
  .spread0                       : -625159177.736145
  .nr_spread_over                : 0
  .nr_running                    : 1
  .load                          : 1024
  .load_avg                      : 1004
  .runnable_load_avg             : 1004
  .util_avg                      : 459
  .removed_load_avg              : 0
  .removed_util_avg              : 0
  .tg_load_avg_contrib           : 1007
  .tg_load_avg                   : 1007
  .throttled                     : 0
  .throttle_count                : 0
  .se->exec_start                : 1193546377.026124
  .se->vruntime                  : 179287288.570602
  .se->sum_exec_runtime          : 143287629.494567
  .se->statistics.wait_start     : 0.000000
  .se->statistics.sleep_start    : 0.000000
  .se->statistics.block_start    : 0.000000
  .se->statistics.sleep_max      : 0.000000
  .se->statistics.block_max      : 0.000000
  .se->statistics.exec_max       : 1.007417
  .se->statistics.slice_max      : 10.040917
  .se->statistics.wait_max       : 22.002458
  .se->statistics.wait_sum       : 5636994.599562
  .se->statistics.wait_count     : 19461708
  .se->load.weight               : 1024
  .se->avg.load_avg              : 1007
  .se->avg.util_avg              : 460

 

다음 그림은 태스크가 있는 태스크 그룹내에서 로드 평균을 관리하는 모습을 보여준다.

  • 엔티티  —(add)—> cfs 런큐  —(sum)—> 태스크 그룹

 

다음 그림은 attach 또는 detach 태스크 시 상위로 러너블 합계를 전파하기 위해 설정하는 모습을 보여준다.

 

다음 그림은 attach 또는 detach 태스크되는 그룹의 상위 그룹에서 그룹 엔티티와 cfs 런큐의 로드 평균이 갱신되는 과정을 보여준다.

 

 

다음 그림은 attach/detach된 엔티티의 +-load_sum을 상위 cfs 런큐로 전파(propagate)한 후 변화된 로드에 대해 그룹 엔티티 및 cfs 런큐의 로드 평균들을 재산출하는 경로를 보여준다.

  • attach_entity_load_avg() 또는 detach_entity_load_avg()
    • attach/detach된 엔티티의 load_sum을 —–> 소속 cfs 런큐의 prop_runnable_sum에 기록해둔다.
  • update_tg_cfs_runnable()
    • 정규 그룹 엔티티 갱신시 하위의 그룹 cfs 런큐에서 전파 값을 읽어온 후 그룹 엔티티 및 cfs 런큐의 로드 평균들을 재산출한다.

 

태스크 그룹 유틸 갱신

update_tg_cfs_util()

kernel/sched/fair.c

static inline void
update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
{
        long delta = gcfs_rq->avg.util_avg - se->avg.util_avg;

        /* Nothing to update */
        if (!delta)
                return;

        /*
         * The relation between sum and avg is:
         *
         *   LOAD_AVG_MAX - 1024 + sa->period_contrib
         *
         * however, the PELT windows are not aligned between grq and gse.
         */

        /* Set new sched_entity's utilization */
        se->avg.util_avg = gcfs_rq->avg.util_avg;
        se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;

        /* Update parent cfs_rq utilization */
        add_positive(&cfs_rq->avg.util_avg, delta);
        cfs_rq->avg.util_sum = cfs_rq->avg.util_avg * LOAD_AVG_MAX;
}

태스크 그룹 유틸을 갱신한다. (새 엔티티 attach 후 상위 태스크 그룹(그룹 엔티티 및 cfs 런큐) 갱신을 위해 진입하였다.)

  • 코드 라인 4에서 그룹 cfs 런큐 @gcfs_rq의 유틸 평균에서 그룹 엔티티 @se의 유틸 평균을 뺀 delta를 구한다.
  • 코드 라인 7~8에서 변화가 없으면 그냥 함수를 빠져나간다.
  • 코드 라인 19에서 새 그룹 엔티티의 유틸 평균은 그룹 cfs 런큐의 유틸 평균을 그대로 사용한다.
  • 코드 라인 20에서 새 그룹 엔티티의 유틸 합계를 갱신한다.
    • 유틸 합계 = 유틸 평균 * 최대 로드 평균 기간
  • 코드 라인 23에서 그룹 엔티티의 부모 cfs 런큐의 유틸 평균에 delta를 추가한다.
  • 코드 라인 24에서 그룹 엔티티의 부모 cfs 런큐의 유틸 합계를 갱신한다.
    • 유틸 합계 = 유틸 평균 * 최대 로드 평균 기간

 

다음 그림은 태스크 그룹에 대한 유틸을 산출하는 과정을 보여준다.

 

러너블 합계 상위 전파(propagate)

propagate_entity_load_avg()

kernel/sched/fair.c

/* Update task and its cfs_rq load average */
static inline int propagate_entity_load_avg(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq, *gcfs_rq;

        if (entity_is_task(se))
                return 0;

        gcfs_rq = group_cfs_rq(se);
        if (!gcfs_rq->propagate)
                return 0;

        gcfs_rq->propagate = 0;

        cfs_rq = cfs_rq_of(se);

        add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum);

        update_tg_cfs_util(cfs_rq, se, gcfs_rq);
        update_tg_cfs_runnable(cfs_rq, se, gcfs_rq);

        trace_pelt_cfs_tp(cfs_rq);
        trace_pelt_se_tp(se);

        return 1;
}

attach/detach에 따라 러너블 로드의 상위 전파를 위한 값이 있으면 이를 현재 그룹 엔티티와 cfs 런큐에 반영하고, 상위에도 전파한다. 전파할 값이 있어 갱신된 경우 1을 반환하고, 전파할 값이 없어 갱신하지 않은 경우 0을 반환한다.

  • 코드 라인 6~7에서 태스크용 엔티티인 경우 이 함수를 수행할 필요가 없으므로 0을 반환한다.
  • 코드 라인 9~11에서 그룹 cfs 런큐에 propagate가 설정되지 않은 경우 0을 반환한다.
  • 코드 라인 13에서 먼저 그룹 cfs 런큐에서 propagate를 클리어하고, 상위 cfs 런큐에 prop_runnable_sum을 전파한다.
  • 코드 라인 15에서 그룹 엔티티와 cfs 런큐에서 util 로드를 갱신한다.
  • 코드 라인 16에서 그룹 엔티티와 cfs 런큐에서 로드 및 러너블 로드를 갱신한다.
  • 코드 라인 21에서 갱신을 하였으므로 1을 반환한다.

 

add_tg_cfs_propagate()

kernel/sched/fair.c

static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum)
{
        cfs_rq->propagate = 1;
        cfs_rq->prop_runnable_sum += runnable_sum;
}

엔티티가 attach/detach 되거나 최상위 태스크 그룹까지 러너블 합계를 전파하도록 요청한다.

  • 추후 update_tg_cfs_runnable() 함수에서 이 값을 읽어들여 사용한다. 읽어들인 후에는 이 값은 0으로 변경된다.

 

태스크 그룹 러너블 갱신

update_tg_cfs_runnable()

kernel/sched/fair.c

static inline void
update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
{
        long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
        unsigned long runnable_load_avg, load_avg;
        u64 runnable_load_sum, load_sum = 0;
        s64 delta_sum;

        if (!runnable_sum)
                return;

        gcfs_rq->prop_runnable_sum = 0;

        if (runnable_sum >= 0) {
                /*
                 * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
                 * the CPU is saturated running == runnable.
                 */
                runnable_sum += se->avg.load_sum;
                runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
        } else {
                /*
                 * Estimate the new unweighted runnable_sum of the gcfs_rq by
                 * assuming all tasks are equally runnable.
                 */
                if (scale_load_down(gcfs_rq->load.weight)) {
                        load_sum = div_s64(gcfs_rq->avg.load_sum,
                                scale_load_down(gcfs_rq->load.weight));
                }

                /* But make sure to not inflate se's runnable */
                runnable_sum = min(se->avg.load_sum, load_sum);
        }

        /*
         * runnable_sum can't be lower than running_sum
         * Rescale running sum to be in the same range as runnable sum
         * running_sum is in [0 : LOAD_AVG_MAX <<  SCHED_CAPACITY_SHIFT]
         * runnable_sum is in [0 : LOAD_AVG_MAX]
         */
        running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
        runnable_sum = max(runnable_sum, running_sum);

        load_sum = (s64)se_weight(se) * runnable_sum;
        load_avg = div_s64(load_sum, LOAD_AVG_MAX);

        delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
        delta_avg = load_avg - se->avg.load_avg;

        se->avg.load_sum = runnable_sum;
        se->avg.load_avg = load_avg;
        add_positive(&cfs_rq->avg.load_avg, delta_avg);
        add_positive(&cfs_rq->avg.load_sum, delta_sum);

        runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
        runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
        delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
        delta_avg = runnable_load_avg - se->avg.runnable_load_avg;

        se->avg.runnable_load_sum = runnable_sum;
        se->avg.runnable_load_avg = runnable_load_avg;

        if (se->on_rq) {
                add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
                add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
        }
}

하위 그룹 cfs 런큐에서 전파 받은 러너블 합계가 있는 경우 그룹 엔티티 및 cfs 런큐의 로드 평균을 갱신한다.

  • 코드 라인 4~12에서 그룹 cfs 런큐에서 전파 받은 러너블 섬을 알아온 후 클리어해둔다. 이 값이 0이면 갱신이 필요 없으므로 그냥 함수를 빠져나간다.
    • 전파 받은 gcfs_rq->prop_runnable_sum이 존재하는 경우 하위 그룹에서 엔티티가 attach(양수) 또는 detach(음수)된 상황이다.
attach/detach 엔티티로부터 propagate된 러너블 합계를 사용한 로드들 산출
  • 코드 라인 14~20에서 하위 그룹에서 엔티티가 attach되어 전파 받은 러너블 합계에 현재 그룹 엔티티의 로드 합계를 추가한다. 단 이 값이 최대치 LOAD_AVG_MAX를 넘을 수는 없다.
    • attach: runnable_sum = gcfs_rq->prop_runnable_sum + se->avg.load_sum
      • 엔티티의 러너블 합계 증가 시 최고 LOAD_AVG_MAX를 초과할 수 없다.
      • runnable_sum <= LOAD_AVG_MAX(47742)
  • 코드 라인 21~33에서 하위 그룹에서 엔티티가 detach되어 전파 받은 러너블 섬이 음수이면 이 값을 사용하지 않는다. 대신 하위 그룹 런큐에서 엔티티 평균 러너블 합계를 사용한다.
    • 그룹 cfs 런큐의 로드 합계를 그룹 cfs 런큐의 로드 weight 값으로 나눈 값으로 대략적인 러너블 합계를 구한다. 단 이 값은 엔티티의 로드 합보다 더 커질 수는 없다.(detach되었는데 더 커지는 상황은 어울리지 않는다.)
    • detach: runnable_sum = gcfs_rq->avg.load_sum / scale_load_down(gcfs_rq->load.weight)
      • 엔티티의 러너블 합계 감소 시 엔티티의 로드 합계보다 작아질 수 없다.
      • se->avg.load_sum <= runnable_sum
  • 코드 라인 41~42에서 그룹에서 엔티티의 유틸 합계를 SCHED_CAPACITY_SHIFT(10) 비트만큼 스케일을 낮춰 러닝 합계를 구한다. 단 이 값은 러너블 합계보다 작지 않아야 한다.
    • running_sum = se->avg.util_sum >> 10
      • runnable_sum이 running_sum보다 작을 수는 없으므로 클립한다.
      • running_sum <= runnable_sum
  • 코드 라인 44~45에서 attach/detach 상황을 포함한 runnable_sum이 구해졌으므로 먼저 다음과 같이 runnable_sum에 엔티티의 로드 weight을 곱하여 반영된 로드 합계를 산출하고, 로드 평균은 최대 로드 평균 기간으로 나누어 산출한다.
    • load_sum(weight 반영 상태) = se_weight(se) * runnable_sum
    • load_avg = load_sum / LOAD_AVG_MAX(최대 로드 평균 기간)
그룹 엔티티에 새 로드 합계와 평균 반영
  • 코드 라인 47~48에서 attach/detach 상황에서 산출한 로드 합계와 평균으로 기존 엔티티의 로드합계와 평균 사이의 차이(delta) 값을 구한다.
    • delta_sum(weight 반영 상태) = load_sum – se_weight(se) * se->avg.load_sum
    • delta_avg = load_avg – se->avg.load_avg
  • 코드 라인 50~51에서 엔티티에 새롭게 산출된 로드 합계(weight 제거된)와 평균을 대입한다.
    • se->avg.load_sum = runnable_sum
    • se->avg.load_avg = load_avg
cfs 런큐에 엔티티 로드 변화분(delta)을 반영
  • 코드 라인 52~53에서 cfs 런큐의 로드 평균과 로드 합계에 위에서 산출한 델타 평균과 합계를 추가한다.
    • cfs_rq->avg.load_sum(weight 반영 상태) += delta_sum
    • cfs_rq->avg.load_avg += delta_avg
그룹 엔티티에 러너블 로드 합계와 평균 반영
  • 코드 라인 55~56에서 러너블 로드 합계와 평균을 산출한다.
    • runnable_load_sum(weight 반영 상태) = se->runnable(se) * runnable_sum
    • runnable_load_avg = runnable_load_sum / LOAD_AVG_MAX(최대 로드 평균 기간)
  • 코드 라인 57~58에서 재산출된 러너블 로드 합계와 평균에서 기존 엔티티의 러너블 로드 합계와 평균 사이의 차이(delta) 값을 구한다.
    • delta_sum = runnable_load_sum – se_weight(se) * se->avg.runnable_load_sum
    • delta_avg = runnable_load_avg – se->avg.runnable_load_avg
  • 코드 라인 60~61에서 엔티티의 러너블 로드 합계 및 평균에 산출해둔 러너블 로드 합계와 러너블 로드 평균을 대입한다.
    • se->avg.runnable_load_sum(weight 미반영 상태) = runnable_sum
    • se->avg.runnable_load_avg = runnable_load_avg
cfs 런큐에 러너블 로드 합계와 평균 변화분 추가
  • 코드 라인 63~66에서 엔티티가 런큐에 있어 러너블 상태인 경우 cfs 런큐의 러너블 로드 합계와 평균에 위에서 산출해둔 델타 합계와 평균을 추가한다.
    • cfs_rq->avg.runnable_load_sum += delta_sum
    • cfs_rq->avg.runnable_load_avg += delta_avg

 

다음 그림은 엔티티 attach 상황에서 상위 그룹의 로드 평균을 갱신하는 과정을 보여준다.

 

다음 그림은 엔티티 attach 상황에서 상위 그룹의 로드 평균을 갱신하는 과정을 보여준다.

 


태스크 그룹 로드 평균 갱신

update_tg_load_avg()

kernel/sched/fair.c

/**
 * update_tg_load_avg - update the tg's load avg
 * @cfs_rq: the cfs_rq whose avg changed
 * @force: update regardless of how small the difference
 *
 * This function 'ensures': tg->load_avg := \Sum tg->cfs_rq[]->avg.load.
 * However, because tg->load_avg is a global value there are performance
 * considerations.
 *
 * In order to avoid having to look at the other cfs_rq's, we use a
 * differential update where we store the last value we propagated. This in
 * turn allows skipping updates if the differential is 'small'.
 *
 * Updating tg's load_avg is necessary before update_cfs_share().
 */
static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
{
        long delta = cfs_rq->avg.load_avg - cfs_rq->tg_load_avg_contrib;

        /*
         * No need to update load_avg for root_task_group as it is not used.
         */
        if (cfs_rq->tg == &root_task_group)
                return;

        if (force || abs(delta) > cfs_rq->tg_load_avg_contrib / 64) {
                atomic_long_add(delta, &cfs_rq->tg->load_avg);
                cfs_rq->tg_load_avg_contrib = cfs_rq->avg.load_avg;
        }
}

태스크 그룹 로드 평균을 갱신한다.

  • 코드 라인 3에서 cfs 런큐의 로드 평균과 지난번 마지막에 태스크 그룹에 기록한 로드 평균의 차이를 delta로 알아온다.
  • 코드 라인 8~9에서 루트 태스크 그룹의 로드 평균은 사용하지 않으므로 산출하지 않고 함수를 빠져나간다.
  • 코드 라인 11~14에서 cfs 로드 평균이 일정량 이상 변화가 있는 경우에만 태스크 그룹의 로드 평균에 추가한다. 태스크 그룹에 기록해둔 값은 다음 산출을 위해 cfs_rq->tg_load_avg_contrib에 기록해둔다.
    • cfs 런큐의 tg_load_avg_contrib 값의 1/64보다 델타 값이 큰 경우 또는 @force 요청이 있는 경우 다음과 같이 갱신한다.
    • 델타 값을 cfs 런큐가 가리키는 태스크 그룹의 로드 평균에 추가한다.
    • cfs 런큐의 tg_load_avg_contrib 는 cfs 런큐의 로드 평균으로 싱크한다.

 

tg->load_avg

태스크 그룹의 로드 평균은 cpu별로 동작하는 cfs 런큐들의 로드 평균을 모두 모아 반영한 글로벌 값이다.

 

cfs_rq->tg_load_avg_contrib

태스크 그룹에 대한 이 cfs 런큐 로드 평균의 기여분이다.

  • cfs 런큐의 로드 평균을 태스크 그룹에 추가한 후에, 이 멤버 변수에도 저장해둔다.
  • 이 값은 다음 갱신 시의 cfs 런큐의 로드 평균과 비교하기 위해 사용된다.

 

tg->load_avg 갱신 조건

글로벌인 태스크 그룹의 로드 평균 값을 변경하려면 atomic 연산을 사용해야 하는데 빈번한 갱신은 성능을 떨어뜨린다. 따라서 다음 조건에서만 갱신을 허용한다.

  • delta = 이번 cfs 런큐의 로드 평균과 지난번 태스크 그룹에 기여한 cfs 런큐의 로드 평균의 절대 차이 값
  • 지난번 cfs 런큐의 로드 평균을 태스크 그룹에 기여한 값의 1/64 보다 큰 변화(delta)가 있을 경우에만 갱신한다.

 

다음 그림은 각 cpu의 cfs 런큐가 태스크 그룹에 기여하는 로드 평균을 보여준다.

 

다음 그림은 update_tg_load_avg() 함수가 요청한 cfs 런큐의 로드 평균을 태스크 그룹의 로드 평균에 추가하는 과정을 보여준다.

 


그룹 엔티티 갱신

update_cfs_group()

kernel/sched/fair.c

/*
 * Recomputes the group entity based on the current state of its group
 * runqueue.
 */
static void update_cfs_group(struct sched_entity *se)
{
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
        long shares, runnable;

        if (!gcfs_rq)
                return;

        if (throttled_hierarchy(gcfs_rq))
                return;

#ifndef CONFIG_SMP
        runnable = shares = READ_ONCE(gcfs_rq->tg->shares);

        if (likely(se->load.weight == shares))
                return;
#else
        shares   = calc_group_shares(gcfs_rq);
        runnable = calc_group_runnable(gcfs_rq, shares);
#endif

        reweight_entity(cfs_rq_of(se), se, shares, runnable);
}

태스크 그룹에 설정된 shares(디폴트: 1024) 값에 cfs 런큐 로드 비율을 적용하여 그룹 엔티티의로드 weight을 재산출하여 갱신한다.

  • 코드 라인 3~7에서 그룹 엔티티의 그룹 cfs 런큐를 알아온다.
  • 코드 라인 9~10에서 그룹 cfs 런큐가 스로틀 중인 경우 함수를 빠져나간다.
그룹 엔티티의 로드 weight 재산출
  • 코드 라인 13~16에서 UP 시스템에서 태스크 그룹의 shares 값과 스케줄 엔티티의 로드 값이 동일하면 최대치를 사용하는 중이므로 함수를 빠져나간다.
  • 코드 라인 18에서 SMP 시스템에서 설정된 태스크 그룹의 shares 값을 전체 cpu 대비 해당 cpu의 cfs 런큐가 가진 가중치(weight) 비율만큼 곱하여 반환한다.
    •                                              해당 cpu의 cfs 런큐에 load.weight
    • shares = tg->shares =  ———————————————
    •                                                   태스크 그룹의 weight
  • 코드 라인 19에서 위에서 산출된 shares를 해당 cfs 런큐의 로드 평균 대비 러너블 로드 평균 비율만큼 곱하여 runnable 값으로 알아온다.
    •                                                  그룹 cfs 런큐의 러너블 로드 평균
    • runnable = shares * 비율 = ——————————————
    •                                                      그룹 cfs 런큐의 로드 평균
  • 코드 라인 22에서 산출된 shares 및 runnable 값으로 그룹 엔티티의 로드 weight과 러너블 로드 weight 값을 재계산한다

 

Shares에 따른 그룹 엔티티 로드 weight 산출

calc_group_shares()

kernel/sched/fair.c

/*
 * All this does is approximate the hierarchical proportion which includes that
 * global sum we all love to hate.
 *
 * That is, the weight of a group entity, is the proportional share of the
 * group weight based on the group runqueue weights. That is:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (1)
 *                        \Sum grq->load.weight
 *
 * Now, because computing that sum is prohibitively expensive to compute (been
 * there, done that) we approximate it with this average stuff. The average
 * moves slower and therefore the approximation is cheaper and more stable.
 *
 * So instead of the above, we substitute:
 *
 *   grq->load.weight -> grq->avg.load_avg                         (2)
 *
 * which yields the following:
 *
 *                     tg->weight * grq->avg.load_avg
 *   ge->load.weight = ------------------------------              (3)
 *                              tg->load_avg
 *
 * Where: tg->load_avg ~= \Sum grq->avg.load_avg
 *
 * That is shares_avg, and it is right (given the approximation (2)).
 *
 * The problem with it is that because the average is slow -- it was designed
 * to be exactly that of course -- this leads to transients in boundary
 * conditions. In specific, the case where the group was idle and we start the
 * one task. It takes time for our CPU's grq->avg.load_avg to build up,
 * yielding bad latency etc..
 *
 * Now, in that special case (1) reduces to:
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = ----------------------------- = tg->weight   (4)
 *                          grp->load.weight
 *
 * That is, the sum collapses because all other CPUs are idle; the UP scenario.
 *
 * So what we do is modify our approximation (3) to approach (4) in the (near)
 * UP case, like:
 *
 *   ge->load.weight =
 *
 *              tg->weight * grq->load.weight
 *     ---------------------------------------------------         (5)
 *     tg->load_avg - grq->avg.load_avg + grq->load.weight
 *
 * But because grq->load.weight can drop to 0, resulting in a divide by zero,
 * we need to use grq->avg.load_avg as its lower bound, which then gives:
 *
 *
 *                     tg->weight * grq->load.weight
 *   ge->load.weight = -----------------------------               (6)
 *                              tg_load_avg'
 *
 * Where:
 *
 *   tg_load_avg' = tg->load_avg - grq->avg.load_avg +
 *                  max(grq->load.weight, grq->avg.load_avg)
 *
 * And that is shares_weight and is icky. In the (near) UP case it approaches
 * (4) while in the normal case it approaches (3). It consistently
 * overestimates the ge->load.weight and therefore:
 *
 *   \Sum ge->load.weight >= tg->weight
 *
 * hence icky!
 */

이 모든 작업은 우리 모두가 싫어하는 global 합계를 포함하는 계층적 비율에 가깝다.

즉, 그룹 엔티티의 가중치(weight)는 태스크 그룹에 설정된 weight 곱하기 전체 cpu 중 해당 cpu의 그룹 런큐 가중치 비율만큼으로 다음 수식과 같다.

  •                                                                         grq->load.weight
  • (1) ge->load.weight = tg->weight * ——————————–
  •                                                                    \Sum grq->load.weight
  •                                                                     해당 cpu의 그룹 런큐->load.weight
  •                                     = tg->weight * ——————————————————-
  •                                                                     전체 cpu들의 그룹 런큐->load.weight 총합

위와 같이 전체 cpu의 그룹 런큐 가중치(weight)를 모두 합하는 것은 매우 비싼 코스트이다. 어짜피 평균은 천천히 움직이므로 대략 산출하는 것이 값싸고, 더 안정적이다. 그래서 위의 그룹 런큐의 load.weight 대신 그룹 런큐의 로드 평균으로 대체한다.

  • (2) grq->load.weight -> grq->avg.load_avg

결과는 다음과 같다.

  •                                                                     grq->avg.load_avg
  • (3) ge->load.weight = tg->weight * —————————
  •                                                                          tg->load_avg
  •                                                                     해당 cpu의 그룹 런큐 로드 평균
  •                                      = tg->weight * ——————————————-
  •                                                                           태스크 그룹의 로드 평균

여기: tg->load_avg ~= \Sum grq->avg.load_avg

태스크 그룹의 로드 평균에는 이미 모든 cpu의 그룹 런큐에서 일정량 이상의 큰 변화들은 집계된다.(적은 변화는 성능을 위해 추후 모아 변화량이 커질때에만 처리한다.)

그런데 평균은 느린 문제가 있다. 이로 인해 경계 조건에서 과도 현상이 발생한다. 구체적으로, 그룹이 idle 상태이고 하나의 작업을 시작하는 경우이다. cpu의 grq-> avg.load_avg가 쌓이는 데 시간이 걸리고 지연 시간이 나빠진다.

이제 특별한 경우 (1)번 케이스는 다음과 같이 축소한다.

  •                                                                      grq->load.weight
  • (4)                               = tg->weight * ————————– = tg->weight
  •                                                                      grq->load.weight

위의 시나리오에선 다른 모든 cpu가 idle 상태일 때 합계가 축소된다. 그래서 다음과 같이 UP(Uni Processor) 케이스에서 (4)에 접근하도록 다음과 같이 근사값 (3)을 수정하였다.

  •                                                                                                    grq->load.weight
  • (5)                               = tg->weight * ——————————————————————–
  •                                                                    tg->load_avg – grq->avg.load_avg + grq->load.weight

그러나 grq-> load.weight이 0으로 떨어질 수 있고 결과적으로 0으로 나눌 수 있으므로 grq-> avg.load_avg를 하한값으로 사용해야 한다.

  •                                                                      grq->load.weight
  • (6)                               = tg->weight * —————————–
  •                                                                         tg_load_avg’
  • tg_load_avg’ = tg->load_avg – grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg)

UP(Uni Processor)의 경우 (4)번 방식을 사용하고, 정상적인 경우 (3)번 방식을 사용한다. ge-> load.weight를 지속적으로 과대 평가하므로 다음과 같다.

  • \Sum ge->load.weight >= tg->weight

 

static long calc_group_shares(struct cfs_rq *cfs_rq)
{
        long tg_weight, tg_shares, load, shares;
        struct task_group *tg = cfs_rq->tg;

        tg_shares = READ_ONCE(tg->shares);

        load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

        tg_weight = atomic_long_read(&tg->load_avg);

        /* Ensure tg_weight >= load */
        tg_weight -= cfs_rq->tg_load_avg_contrib;
        tg_weight += load;

        shares = (tg_shares * load);
        if (tg_weight)
                shares /= tg_weight;

        /*
         * MIN_SHARES has to be unscaled here to support per-CPU partitioning
         * of a group with small tg->shares value. It is a floor value which is
         * assigned as a minimum load.weight to the sched_entity representing
         * the group on a CPU.
         *
         * E.g. on 64-bit for a group with tg->shares of scale_load(15)=15*1024
         * on an 8-core system with 8 tasks each runnable on one CPU shares has
         * to be 15*1024*1/8=1920 instead of scale_load(MIN_SHARES)=2*1024. In
         * case no task is runnable on a CPU MIN_SHARES=2 should be returned
         * instead of 0.
         */
        return clamp_t(long, shares, MIN_SHARES, tg_shares);
}

태스크 그룹의 shares 값을 전체 cpu 대비 해당 cpu의 cfs 런큐가 가진 가중치(weight) 비율만큼 곱하여 반환한다.

  • 코드 라인 4~6에서 그룹 런큐가 소속된 태스크 그룹에 설정된 shares 값을 알아온다.
    • 예) 루트 태스크 그룹의 디폴트 share 값(/sys/fs/cgroup/cpu/cpu.shares) = 1024
  • 코드 라인 8~18에서 다음 수식과 같이 shares 값을 산출한다.
    •                                                                  max(grq->load.weight, grq->avg.load_avg)
    • = tg->shares * ———————————————————————————————————–
    •                              tg->load_avg – grq->tg_load_avg_contrib + max(grq->load.weight, grq->avg.load_avg)
  • 코드 라인 32에서 산출한 shares 값은 MIN_SHARES(2) ~ tg->shares 범위를 벗어나는 경우 clamp하여 반환한다.

 

예) tg->shares=1024, cpu#0의 qrq->load.weight=1024, cpu#1의 qrq->load.weight=2048

  • cpu#0: 1024 * 1024 / 3072 = 341
  • cpu#1: 1024 * 2048 / 3072 = 682

 

Shares에 따른 그룹 엔티티 러너블 weight 재산출

 

/*
 * This calculates the effective runnable weight for a group entity based on
 * the group entity weight calculated above.
 *
 * Because of the above approximation (2), our group entity weight is
 * an load_avg based ratio (3). This means that it includes blocked load and
 * does not represent the runnable weight.
 *
 * Approximate the group entity's runnable weight per ratio from the group
 * runqueue:
 *
 *                                           grq->avg.runnable_load_avg
 *   ge->runnable_weight = ge->load.weight * -------------------------- (7)
 *                                               grq->avg.load_avg
 *
 * However, analogous to above, since the avg numbers are slow, this leads to
 * transients in the from-idle case. Instead we use:
 *
 *   ge->runnable_weight = ge->load.weight *
 *
 *              max(grq->avg.runnable_load_avg, grq->runnable_weight)
 *              -----------------------------------------------------   (8)
 *                    max(grq->avg.load_avg, grq->load.weight)
 *
 * Where these max() serve both to use the 'instant' values to fix the slow
 * from-idle and avoid the /0 on to-idle, similar to (6).
 */

위 함수에서 산출한 그룹 엔티티 가중치(weight)를 기반으로 그룹 엔티티의 유효 러너블 가중치(weight)를 산출한다.

위의 근사치 (2)번을 이유로, 그룹 엔티티 가중치(weight)는 (3)의 로드 평균 기반 비율이다. 이는 러너블 가중치(weight)를 나타내게 한 게 아니라, blocked 로드를 포함함을 의미한다. (가중치 비율이 아닌 로드 평균 비율을 사용하면 러너블과 blocked 로드 둘다 포함한다.)

그룹 런큐별 그룹 엔티티의 러너블 가중치(weight)를 대략적으로 산출한다.

  •                                                                                        grq->avg.runnable_load_avg
  • (7) ge->runnable_weight = ge->load.weight * —————————————–
  •                                                                                                 grq->avg.load_avg
그러나 위와 유사하게 평균 숫자가 느리기 때문에 idle 상태에서 과도 현상이 발생한다. 대신 다음을 사용한다.
  •                                                                                         max(grq->avg.runnable_load_avg, grq->runnable_weight)
  • (8)                                          = ge->load.weight * —————————————————————————
  •                                                                                                    max(grq->avg.load_avg, grq->load.weight)
max()는 ‘인스턴트’값을 사용하여 다음 두 문제를 피하는데 모두 사용한다. (6)
  • idle로 시작하는 느림을 교정
  • idle 상태에서 0으로 나누는 문제

calc_group_runnable()

kernel/sched/fair.c

static long calc_group_runnable(struct cfs_rq *cfs_rq, long shares)
{
        long runnable, load_avg;

        load_avg = max(cfs_rq->avg.load_avg,
                       scale_load_down(cfs_rq->load.weight));

        runnable = max(cfs_rq->avg.runnable_load_avg,
                       scale_load_down(cfs_rq->runnable_weight));

        runnable *= shares;
        if (load_avg)
                runnable /= load_avg;

        return clamp_t(long, runnable, MIN_SHARES, shares);
}

@shares를 전체 cpu 대비 해당 cpu의 러너블 비율만큼 곱한 runnable 값을 반환한다.

  • 코드 라인 5~13에서 다음과 같이 runnable 값을 산출한다.
    •                         max(grq->avg.runnable_avg, grq->runnable.weight)
    • = shares * ———————————————————————
    •                                 max(grq->avg.load_avg, grq->load.weight)
  • 코드 라인 15에서 산출한 runnable 값은 MIN_SHARES(2) ~ @shares 범위를 벗어나는 경우 clamp하여 반환한다.

 

그룹 엔티티의 weight 재설정

reweight_entity()

kernel/sched/fair.c

static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
                            unsigned long weight, unsigned long runnable)
{
        if (se->on_rq) {
                /* commit outstanding execution time */
                if (cfs_rq->curr == se)
                        update_curr(cfs_rq);
                account_entity_dequeue(cfs_rq, se);
                dequeue_runnable_load_avg(cfs_rq, se);
        }
        dequeue_load_avg(cfs_rq, se);

        se->runnable_weight = runnable;
        update_load_set(&se->load, weight);

#ifdef CONFIG_SMP
        do {
                u32 divider = LOAD_AVG_MAX - 1024 + se->avg.period_contrib;

                se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
                se->avg.runnable_load_avg =
                        div_u64(se_runnable(se) * se->avg.runnable_load_sum, divider);
        } while (0);
#endif

        enqueue_load_avg(cfs_rq, se);
        if (se->on_rq) {
                account_entity_enqueue(cfs_rq, se);
                enqueue_runnable_load_avg(cfs_rq, se);
        }
}

엔티티의 로드 및 러너블 weight 값을 재설정한다.

엔티티의 기존 가중치 관련 빼기
  • 코드 라인 4~10에서 엔티티가 cfs 런큐에 존재하는 경우 cfs 런큐에서 기존 가중치 및 로드등을 빼기 위해 다음을 수행한다.
    • 엔티티가 현재 러닝 중인 경우 현재 엔티티에 대해 로드 등을 갱신한다.
    • cfs 런큐에서 엔티티의 기존 가중치를 뺀다.
    • cfs 런큐에서 엔티티의 기존 러너블 가중치를 뺀다.
  • 코드 라인 11에서 cfs 런큐에서 엔티티의 기존 로드 합계 및 평균을 뺀다.
엔티티의 새 가중치 재설정
  • 코드 라인 13~14에서 엔티티에 인자로 전달 받은 새 @runnable과 @weight를 적용한다.
엔티티의 새 가중치 더하기
  • 코드 라인 18~22에서 엔티티의 새 가중치로 로드 평균과 러너블 평균을 재산출한다.
  • 코드 라인 26에서 cfs 런큐에 새 가중치 값을 가진 엔티티의 로드 합계 및 평균을 더한다.
  • 코드 라인 27~30에서 엔티티가 cfs 런큐에 존재하는 경우 cfs 런큐에 새 가중치 및 로드등을 더하기 위해 다음을 수행한다.
    • cfs 런큐에 엔티티의 새 가중치를 더한다.
    • cfs 런큐에 엔티티의 새 러너블 가중치를 더한다.

 

update_load_set()

kernel/sched/fair.c

static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
        lw->weight = w;
        lw->inv_weight = 0;
}

로드 weight 걊을 설정하고 inv_weight 값은 0으로 리셋한다.

 


엔큐 & 디큐 엔티티 시 PELT

엔큐 엔티티

enqueue_entity()

kernel/sched/fair.c

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
(...생략...)
        /*
         * When enqueuing a sched_entity, we must:
         *   - Update loads to have both entity and cfs_rq synced with now.
         *   - Add its load to cfs_rq->runnable_avg
         *   - For group_entity, update its weight to reflect the new share of
         *     its group cfs_rq
         *   - Add its new weight to cfs_rq->load.weight
         */
        update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
        update_cfs_group(se);
        enqueue_runnable_load_avg(cfs_rq, se);
        account_entity_enqueue(cfs_rq, se);
(...생략...)
}

엔티티를 cfs 런큐에 엔큐한다.

  • 코드 라인 13에서 요청 엔티티를 갱신한다.
    • UPDATE_TG 플래그는 태스크 그룹까지 갱신을 요청한다.
    • DO_ATTACH 플래그는 migration에 의해 attach된 태스크가 있는 경우 이의 처리를 요청한다.
  • 코드 라인 14에서 그룹 엔티티 및 cfs 런큐를 갱신한다.
  • 코드 라인 15에서 엔큐할 엔티티의 로드 평균 등을 cfs 런큐에 추가한다.
  • 코드 라인 16에서 cfs 런큐에 엔티티가 엔큐될 때의 account를 처리한다.

 

엔큐 엔티티 시 로드 평균

enqueue_load_avg()

kernel/sched/fair.c

static inline void
enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        cfs_rq->avg.load_avg += se->avg.load_avg;
        cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
}

엔티티 로드 평균을 cfs 런큐에 추가한다.

  • 코드 라인 4에서 엔티티 로드 평균을 cfs 런큐에 추가한다.
  • 코드 라인 5에서 엔티티의 weight에 로드 합계를 곱해 cfs 런큐에 추가한다.

 

엔큐 엔티티 시 러너블 로드 평균

enqueue_runnable_load_avg()

kernel/sched/fair.c

static inline void
enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        cfs_rq->runnable_weight += se->runnable_weight;

        cfs_rq->avg.runnable_load_avg += se->avg.runnable_load_avg;
        cfs_rq->avg.runnable_load_sum += se_runnable(se) * se->avg.runnable_load_sum;
}

엔티티 러너블 로드 평균을 cfs 런큐에 추가한다.

  • 코드 라인 4에서 엔티티 러너블 weight를 cfs 런큐에 추가한다.
  • 코드 라인 6에서 엔티티 러너블 로드 평균을 cfs 런큐에 추가한다.
  • 코드 라인 7에서 엔티티 러너블 수와 러너블 로드 합계를 곱해 cfs 런큐에 추가한다.

 

엔큐 엔티티 시 account

account_entity_enqueue()

kernel/sched/fair.c

static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        update_load_add(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
        if (entity_is_task(se)) {
                struct rq *rq = rq_of(cfs_rq);

                account_numa_enqueue(rq, task_of(se));
                list_add(&se->group_node, &rq->cfs_tasks);
        }
#endif
        cfs_rq->nr_running++;
}

cfs 런큐에 엔티티가 엔큐될 때의 account를 처리한다.

  • 코드 라인 4에서 cfs 런큐에 엔티티의 로드를 추가한다.
  • 코드 라인 6~11에서 태스크용 엔티티가 enqueue된 경우 런큐의 NUMA 카운터를 갱신하고, 태스크를 런큐의 cfs_tasks 리스트에 추가한다.
  • 코드 라인 13에서 cfs 런큐에서 엔티티 수를 담당하는 nr_running 카운터를 1 증가시킨다.

 

account_numa_enqueue()

kernel/sched/fair.c

static void account_numa_enqueue(struct rq *rq, struct task_struct *p)
{
        rq->nr_numa_running += (p->numa_preferred_nid != NUMA_NO_NODE);
        rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
}

태스크가 enqueue된 경우에 호출되며, 런큐의 NUMA 카운터를 갱신한다.

  • rq->nr_numa_running++ (태스크의 권장 누마 노드가 지정된 경우에만)
  • rq->nr_preferred_running++ (태스크의 노드가 권장 누마 노드와 동일한 경우에만)

 

디큐 엔티티

dequeue_entity()

kernel/sched/fair.c

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
(...생략...) 
        /*
         * When dequeuing a sched_entity, we must:
         *   - Update loads to have both entity and cfs_rq synced with now.
         *   - Subtract its load from the cfs_rq->runnable_avg.
         *   - Subtract its previous weight from cfs_rq->load.weight.
         *   - For group entity, update its weight to reflect the new share
         *     of its group cfs_rq.
         */
        update_load_avg(cfs_rq, se, UPDATE_TG);
        dequeue_runnable_load_avg(cfs_rq, se);
(...생략...)
        account_entity_dequeue(cfs_rq, se);
(...생략...)
        update_cfs_group(se);
(...생략...) 
}

엔티티를 cfs 런큐로부터 디큐한다.

  • 코드 라인 13에서 요청 엔티티를 갱신한다.
    • UPDATE_TG 플래그는 태스크 그룹까지 갱신을 요청한다.
  • 코드 라인 14에서 디큐할 엔티티의 로드 평균 등을 cfs 런큐로부터 감산한다.
  • 코드 라인 16에서 cfs 런큐로부터 엔티티가 디큐될 때의 account를 처리한다.
  • 코드 라인 18에서 그룹 엔티티 및 cfs 런큐를 갱신한다.

 

디큐 엔티티 시 로드 평균

dequeue_load_avg()

kernel/sched/fair.c

static inline void
dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
        sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
}

엔티티 로드 평균만큼을 cfs 런큐에서 감소시킨다.

  • 코드 라인 4에서 엔티티 로드 평균만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 5에서 엔티티의 weight에 로드 합계를 곱한 만큼을 cfs 런큐에서 감소시킨다.

 

디큐 엔티티 시 러너블 로드 평균

dequeue_runnable_load_avg()

kernel/sched/fair.c

static inline void
dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        cfs_rq->runnable_weight -= se->runnable_weight;

        sub_positive(&cfs_rq->avg.runnable_load_avg, se->avg.runnable_load_avg);
        sub_positive(&cfs_rq->avg.runnable_load_sum,
                     se_runnable(se) * se->avg.runnable_load_sum);
}

엔티티 러너블 로드 평균만큼을 cfs 런큐에서 감소시킨다.

  • 코드 라인 4에서 엔티티 러너블 weight 만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 6에서 엔티티 러너블 로드 평균 만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 7~8에서 엔티티 러너블 수와 러너블 로드 합계를 곱한 만큼을 cfs 런큐에서 감소시킨다.

 

디큐 엔티티 시 account

account_entity_dequeue()

kernel/sched/fair.c

static void
account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        update_load_sub(&cfs_rq->load, se->load.weight);
#ifdef CONFIG_SMP
        if (entity_is_task(se)) {
                account_numa_dequeue(rq_of(cfs_rq), task_of(se));
                list_del_init(&se->group_node);
        }
#endif
        cfs_rq->nr_running--;
}

cfs 런큐에 엔티티가 디큐될 때의 account를 처리한다.

  • 코드 라인 4에서 엔티티의 로드 weight 값을 cfs 런큐에서 차감한다.
  • 코드 라인 6~9에서 태스크용 엔티티의 경우 런큐의 누마 관련 카운터 값을 감소시키고, 런큐의 cfs_tasks 리스트에서 태스크를 제거한다.
  • 코드 라인 11에서 cfs 런큐에서 엔티티 수를 담당하는 nr_running을 1 감소시킨다.

 

account_numa_dequeue()

kernel/sched/fair.c

static void account_numa_dequeue(struct rq *rq, struct task_struct *p)
{
        rq->nr_numa_running -= (p->numa_preferred_nid != NUMA_NO_NODE);
        rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
}

태스크가 디큐된 경우에 호출되며, 런큐의 NUMA 카운터를 갱신한다.

  • rq->nr_numa_running– (태스크의 권장 누마 노드가 지정된 경우에만)
  • rq->nr_preferred_running– (태스크의 노드가 권장 누마 노드와 동일한 경우에만)

 


Attach & Detach 엔티티 시 PELT

Attach 엔티티

attach_entity_cfs_rq()

kernel/sched/fair.c

static void attach_entity_cfs_rq(struct sched_entity *se)
{
(...생략...)
        /* Synchronize entity with its cfs_rq */
        update_load_avg(cfs_rq, se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD);
        attach_entity_load_avg(cfs_rq, se, 0);
        update_tg_load_avg(cfs_rq, false);
        propagate_entity_cfs_rq(se);
}

마이그레이션에 의해 cfs 런큐에 엔티티를 attach 한다.

  • 코드 라인 5에서 엔티티의 로드 평균 등을 갱신한다.
    • 단 ATTACH_AGE_LOAD feature가 없는 경우 엔티티의 로드 평균 갱신만 skip 하고 cfs 런큐의 로드 평균 및 propagation 등은 수행한다.
  • 코드 라인 6에서 엔티티 attach 시 CFS 런큐에  로드 평균을 추가한다.
  • 코드 라인 7에서 cfs 런큐의 로드가 추가되었으므로 태스크 그룹에 대한 로드 평균도 갱신한다.
  • 코드 라인 8에서 최상위 그룹 엔티티까지 전파된 러너블 로드를 추가하여 각 그룹을 재산출한다.

 

attach 엔티티 시 로드 평균

attach_entity_load_avg()

kernel/sched/fair.c

/**
 * attach_entity_load_avg - attach this entity to its cfs_rq load avg
 * @cfs_rq: cfs_rq to attach to
 * @se: sched_entity to attach
 * @flags: migration hints
 *
 * Must call update_cfs_rq_load_avg() before this, since we rely on
 * cfs_rq->avg.last_update_time being current.
 */
static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
        u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;

        /*
         * When we attach the @se to the @cfs_rq, we must align the decay
         * window because without that, really weird and wonderful things can
         * happen.
         *
         * XXX illustrate
         */
        se->avg.last_update_time = cfs_rq->avg.last_update_time;
        se->avg.period_contrib = cfs_rq->avg.period_contrib;

        /*
         * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
         * period_contrib. This isn't strictly correct, but since we're
         * entirely outside of the PELT hierarchy, nobody cares if we truncate
         * _sum a little.
         */
        se->avg.util_sum = se->avg.util_avg * divider;

        se->avg.load_sum = divider;
        if (se_weight(se)) {
                se->avg.load_sum =
                        div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
        }

        se->avg.runnable_load_sum = se->avg.load_sum;

        enqueue_load_avg(cfs_rq, se);
        cfs_rq->avg.util_avg += se->avg.util_avg;
        cfs_rq->avg.util_sum += se->avg.util_sum;

        add_tg_cfs_propagate(cfs_rq, se->avg.load_sum);

        cfs_rq_util_change(cfs_rq, flags);

        trace_pelt_cfs_tp(cfs_rq);
}

엔티티 attach 시 CFS 런큐에  로드 평균을 추가한다.

  • 코드 라인 3에서 divider는 로드 평균 산출에 사용할 기간을 구한다.
  • 코드 라인 12에서 엔티티의 cfs 런큐의 last_update_time을 엔티티에 대입한다.
  • 코드 라인 13에서 cfs 런큐의 decay하지 않은 period_contrib를 엔티티에 대입한다.
  • 코드 라인 21에서 엔티티의 유틸 평균에 기간 divider를 곱하여 유틸 합계를 구한다.
  • 코드 라인 23~27에서 엔티티의 로드 합계에 로드 평균 * 기간 divider / weight 결과를 대입한다.
  • 코드 라인 29에서 러너블 로드 합계에도 로드 합계를 대입한다.
  • 코드 라인 31에서 cfs 런큐에 로드 평균을 추가한다.
  • 코드 라인 32~33에서 cfs 런큐의 유틸 합계 및 평균에 엔티티의 유틸 합계 및 평균을 추가한다.
  • 코드 라인 35에서 태스크 그룹에 대한 전파를 한다.
  • 코드 라인 37에서 유틸 값이 바뀌면 cpu frequency 변경 기능이 있는 시스템의 경우 주기적으로 변경한다.

Detach 엔티티

detach_entity_cfs_rq()

kernel/sched/fair.c

static void detach_entity_cfs_rq(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);

        /* Catch up with the cfs_rq and remove our load when we leave */
        update_load_avg(cfs_rq, se, 0);
        detach_entity_load_avg(cfs_rq, se);
        update_tg_load_avg(cfs_rq, false);
        propagate_entity_cfs_rq(se);
}

마이그레이션에 의해 cfs 런큐로부터 엔티티를 detach 한다.

  • 코드 라인 6에서 엔티티의 로드 평균 등을 갱신한다.
  • 코드 라인 7에서 엔티티 detach 시 CFS 런큐로부터 로드 평균을 감산한다.
  • 코드 라인 8에서 cfs 런큐에 로드가 감소하였으므로 태스크 그룹에 대한 로드 평균도 갱신한다.
  • 코드 라인 9에서 최상위 그룹 엔티티까지 전파하여 각 그룹의 로드 평균을 재산출한다.

 

Detach 엔티티 시 로드 평균

detach_entity_load_avg()

kernel/sched/fair.c

/**
 * detach_entity_load_avg - detach this entity from its cfs_rq load avg
 * @cfs_rq: cfs_rq to detach from
 * @se: sched_entity to detach
 *
 * Must call update_cfs_rq_load_avg() before this, since we rely on
 * cfs_rq->avg.last_update_time being current.
 */
static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
        dequeue_load_avg(cfs_rq, se);
        sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
        sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);

        add_tg_cfs_propagate(cfs_rq, -se->avg.load_sum);

        cfs_rq_util_change(cfs_rq, 0);

        trace_pelt_cfs_tp(cfs_rq);
}

엔티티 detach 시 CFS 런큐에  로드 평균을 감소시킨다.

  • 코드 라인 3에서 엔티티 로드 평균만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 4에서 엔티티 유틸 평균만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 5에서 엔티티 유틸 합계 만큼을 cfs 런큐에서 감소시킨다.
  • 코드 라인 7에서 태스크 그룹에 대한 전파를 한다.
  • 코드 라인 9에서 유틸 값이 바뀌면 cpu frequency 변경 기능이 있는 시스템의 경우 주기적으로 변경한다.

 

엔티티 로드 평균 제거

remove_entity_load_avg()

kernel/sched/fair.c

/*
 * Task first catches up with cfs_rq, and then subtract
 * itself from the cfs_rq (task must be off the queue now).
 */
static void remove_entity_load_avg(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        unsigned long flags;

        /*
         * tasks cannot exit without having gone through wake_up_new_task() ->
         * post_init_entity_util_avg() which will have added things to the
         * cfs_rq, so we can remove unconditionally.
         */

        sync_entity_load_avg(se);

        raw_spin_lock_irqsave(&cfs_rq->removed.lock, flags);
        ++cfs_rq->removed.nr;
        cfs_rq->removed.util_avg        += se->avg.util_avg;
        cfs_rq->removed.load_avg        += se->avg.load_avg;
        cfs_rq->removed.runnable_sum    += se->avg.load_sum; /* == runnable_sum */
        raw_spin_unlock_irqrestore(&cfs_rq->removed.lock, flags);
}

cfs 런큐에서 엔티티의 로드를 감소시키도록 요청하고, 추후 cfs 로드 평균을 갱신할 때 효과를 본다.

  • 코드 라인 12에서 엔티티 로드 평균을 갱신한다.
  • 코드 라인 14~19에서 cfs 런큐의 removed에 엔티티의 유틸/로드 평균 및 로드 합계를 추가한다.

 


유틸 변경에 따른 cpu frequency 변경

cfs_rq_util_change()

kernel/sched/fair.c

static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq, int flags)
{
        struct rq *rq = rq_of(cfs_rq);

        if (&rq->cfs == cfs_rq || (flags & SCHED_CPUFREQ_MIGRATION)) {
                /*
                 * There are a few boundary cases this might miss but it should
                 * get called often enough that that should (hopefully) not be
                 * a real problem.
                 *
                 * It will not get called when we go idle, because the idle
                 * thread is a different class (!fair), nor will the utilization
                 * number include things like RT tasks.
                 *
                 * As is, the util number is not freq-invariant (we'd have to
                 * implement arch_scale_freq_capacity() for that).
                 *
                 * See cpu_util().
                 */
                cpufreq_update_util(rq, flags);
        }
}

유틸 값이 바뀌면 cpu frequency를 바꿀 수 있는 기능을 가진 런큐인 경우 cpu frequency를 변경 시도를 한다.

 

cpufreq_update_util()

kernel/sched/sched.h

/**
 * cpufreq_update_util - Take a note about CPU utilization changes.
 * @rq: Runqueue to carry out the update for.
 * @flags: Update reason flags.
 *
 * This function is called by the scheduler on the CPU whose utilization is
 * being updated.
 *
 * It can only be called from RCU-sched read-side critical sections.
 *
 * The way cpufreq is currently arranged requires it to evaluate the CPU
 * performance state (frequency/voltage) on a regular basis to prevent it from
 * being stuck in a completely inadequate performance level for too long.
 * That is not guaranteed to happen if the updates are only triggered from CFS
 * and DL, though, because they may not be coming in if only RT tasks are
 * active all the time (or there are RT tasks only).
 *
 * As a workaround for that issue, this function is called periodically by the
 * RT sched class to trigger extra cpufreq updates to prevent it from stalling,
 * but that really is a band-aid.  Going forward it should be replaced with
 * solutions targeted more specifically at RT tasks.
 */
static inline void cpufreq_update_util(struct rq *rq, unsigned int flags)
{
        struct update_util_data *data;

        data = rcu_dereference_sched(*per_cpu_ptr(&cpufreq_update_util_data,
                                                  cpu_of(rq)));
        if (data)
                data->func(data, rq_clock(rq), flags);
}

유틸 평균이 바뀌면 cpu frequency를 바꿀 수 있도록 해당 후크 함수를 호출한다.

  • 각 드라이버에서 hw 특성으로 인해 cpu frequency를 변경하는 cost가 있어 각각의 정책에 따라 최소 수ms 또는 수십~수백 ms 주기마다 frequency를 설정한다.
  • cpufreq_add_update_util_hook() API 함수를 사용하여 후크 함수를 등록하고, 현재 커널에 등록된 후크 함수들은 다음과같다.
    • 기본 cpu frequency governors util
      • kernel/sched/cpufreq_schedutil.c – sugov_start()
    • CPUFREQ governors 서브시스템
      • drivers/cpufreq/cpufreq_governor.c – dbs_update_util_handler()
    • 인텔 x86 드라이버
      • drivers/cpufreq/intel_pstate.c – intel_pstate_update_util_hwp() 또는 intel_pstate_update_util()

 


기타

entity_is_task()

kernel/sched/sched.h

/* An entity is a task if it doesn't "own" a runqueue */
#define entity_is_task(se)      (!se->my_q)

스케줄 엔티티가 태스크인지 여부를 반환한다.

  • 태스크인 경우 se->cfs_rq를 사용하고 태스크 그룹을 사용하는 경우 se->my_q를 사용한다.

 

group_cfs_rq()

kernel/sched/fair.c

/* runqueue "owned" by this group */
static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
{
        return grp->my_q;
}

스케줄 엔티티의 런큐를 반환한다.

 


구조체

sched_avg 구조체

include/linux/sched.h

/*
 * The load_avg/util_avg accumulates an infinite geometric series
 * (see __update_load_avg() in kernel/sched/fair.c).
 *
 * [load_avg definition]
 *
 *   load_avg = runnable% * scale_load_down(load)
 *
 * where runnable% is the time ratio that a sched_entity is runnable.
 * For cfs_rq, it is the aggregated load_avg of all runnable and
 * blocked sched_entities.
 *
 * [util_avg definition]
 *
 *   util_avg = running% * SCHED_CAPACITY_SCALE
 *
 * where running% is the time ratio that a sched_entity is running on
 * a CPU. For cfs_rq, it is the aggregated util_avg of all runnable
 * and blocked sched_entities.
 *
 * load_avg and util_avg don't direcly factor frequency scaling and CPU
 * capacity scaling. The scaling is done through the rq_clock_pelt that
 * is used for computing those signals (see update_rq_clock_pelt())
 *
 * N.B., the above ratios (runnable% and running%) themselves are in the
 * range of [0, 1]. To do fixed point arithmetics, we therefore scale them
 * to as large a range as necessary. This is for example reflected by
 * util_avg's SCHED_CAPACITY_SCALE.
 *
 * [Overflow issue]
 *
 * The 64-bit load_sum can have 4353082796 (=2^64/47742/88761) entities
 * with the highest load (=88761), always runnable on a single cfs_rq,
 * and should not overflow as the number already hits PID_MAX_LIMIT.
 *
 * For all other cases (including 32-bit kernels), struct load_weight's
 * weight will overflow first before we do, because:
 *
 *    Max(load_avg) <= Max(load.weight)
 *
 * Then it is the load_weight's responsibility to consider overflow
 * issues.
 */
struct sched_avg {
        u64                             last_update_time;
        u64                             load_sum;
        u64                             runnable_load_sum;
        u32                             util_sum;
        u32                             period_contrib;
        unsigned long                   load_avg;
        unsigned long                   runnable_load_avg;
        unsigned long                   util_avg;
        struct util_est                 util_est;
} ____cacheline_aligned;
  • last_update_time
    • 마지막 갱신된 시각
    • 태스크 마이그레이션으로 인해 엔티티가 cfs 런큐에 attach/detach된 경우 이 값은 0으로 리셋된다.
  • load_sum
    • 로드 합계
  • runnable_load_sum
    • 러너블 로드 합계는 러너블(curr + rb 트리에서 대기) 상태의 기간 합계이다.
  • util_sum
    • 엔티티 또는 cfs 런큐가 running(실제 cpu를 잡고 수행한) 상태였던 기간 합계
  • period_contrib
    • 1 기간(period) 기여값
  • load_avg
    • 로드 평균
    • = runnable% * scale_load_down(load)
      • runnable% = cfs 런큐에서 runnable한 시간 비율로 0~100%까지이다.
        • runnable과 blocked 엔티티들을 모두 합친 비율이다.
      • scale_load_down(load) = 10bit 정밀도의 이진화 정수 로드 값
    • 엔티티 가중치와 frequency 스케일링이 러너블 타임에 곱해져서 적용된다.
    • cfs 런큐에서 사용될 떄 이 값은 그룹 스케줄링에서 사용된다.
  • runnable_load_avg
    • 러너블 로드 평균
    • cfs 런큐에서 사용될 떄 이 값은 로드 밸런스에서 사용된다.
  • util_avg
    • 유틸 평균
    • = running% * SCHED_CAPACITY_SCALE(1024)
      • running% = 하나의 cpu에서 러닝중인 엔티티의 시간 비율로 0~100%까지이다.
    • cpu effiency와 frequency 스케일링이 러닝 타임에 곱해져서 적용된다.
    • 엔티티에서 사용될 때 이 값은 EAS(Energy Aware Scheduler)에서 에너지 효과적인 cpu를 선택하는 용도로 사용된다.
    • cfs 런큐에서 사용될 때 이 값은 schedutil governor에서 주파수 선택 시 사용된다.

 

태스크용 엔티티
  • load.weight
    • nice 우선 순위에 따른 로드 가중치(weight)
    • 예) nice 0 태스크
      • 1048576
    • 예) nice -10 태스크
      • 9777152
  • runnable_weight
    • load.weight와 동일
  • load_sum & load_avg
    • 예) nice 0 태스크
      • load_sum = 46,872
      • load_avg = load_sum * se_weight() / LOAD_AVG_MAX = 1,005
    • 예) nice -10 태스크
      • load_sum = 47,742
      • load_avg = load_sum / se_weight() / LOAD_AVG_MAX = 9,483
  • runnable_load_sum & runnable_load_avg
    • 태스크용 엔티티의 경우 load_sum & load_avg와 동일하다.
  • util_sum & util_avg
    • 예) 3개의 nice 0 태스크, 1 개의 nice-10 태스크
      • nice 0 태스크
        • util_sum = 6,033,955
        • util_avg = util_sum / 약 LOAD_AVG_MAX = 126
      • nice -10 태스크
        • util_sum = 36,261,788
        • util_avg = util_sum / 약 LOAD_AVG_MAX = 759

 

그룹 엔티티

예) A 그룹, cpu.shares=1024, 3개의 nice 0 태스크, 1 개의 nice-10 태스크

  • load.weight
    • load.weight=12,922,880 <- A 그룹에 많은 로드 가중치(9548 + 1024 + 1024 + 1024)가 걸린 상태이다.
  • runnable_weight
    • runnable_weight=12,922,880
  • load_sum & load_avg
    • load_sum = 598,090,350
    • load_avg = 12,620
  • runnable_sum & runnable_avg
    • load_sum & load_avg와 비슷하다.
  • util_sum & util_avg
    • util_sum = 48529673
    • util_avg = util_sum / 약 LOAD_AVG_MAX = 1024        <– A 그룹에서 100% 유틸 로드가 걸린 상태이다.

 

cfs 런큐

예) A 그룹, cpu.shares=1024, 3개의 nice 0 태스크, 1 개의 nice-10 태스크

  • load.weight
    • 예) load.weight = 12,922,880                <- A 그룹 로드를 이 cpu가 모두 다 사용하는 상태이다.
  • runnable_weight
    • 예) runnable_weight = 12,922,880     <- A 그룹 러너블 로드를 이 cpu가 모두 다 사용하는 상태이다.
  • load_sum & load_avg
    • 예) load_sum = 12,903,424
    • 예) load_avg = load_sum / se_weight() = 12601 <- A 그룹내 엔티티들의 로드 평균 총합과 비슷
  • .runnable_load_sum & runnable_load_avg
    • load_sum & load_avg와 비슷하다.
  • util_sum & util_avg
    • 예) util_sum =48,529,673
    • 예) util_avg = util_sum / LOAD_AVG_MAX = 1024 <- A 그룹내에서 util 로드를 이 cpu가 모두 다 사용하는 상태이다.

 

task_group 구조체

kernel/sched/sched.h

/* Task group related information */
struct task_group {
        struct cgroup_subsys_state css;

#ifdef CONFIG_FAIR_GROUP_SCHED
        /* schedulable entities of this group on each CPU */
        struct sched_entity     **se;
        /* runqueue "owned" by this group on each CPU */
        struct cfs_rq           **cfs_rq;
        unsigned long           shares;

#ifdef  CONFIG_SMP
        /*
         * load_avg can be heavily contended at clock tick time, so put
         * it in its own cacheline separated from the fields above which
         * will also be accessed at each tick.
         */
        atomic_long_t           load_avg ____cacheline_aligned;
#endif
#endif

#ifdef CONFIG_RT_GROUP_SCHED
        struct sched_rt_entity  **rt_se;
        struct rt_rq            **rt_rq;

        struct rt_bandwidth     rt_bandwidth;
#endif

        struct rcu_head         rcu;
        struct list_head        list;

        struct task_group       *parent;
        struct list_head        siblings;
        struct list_head        children;

#ifdef CONFIG_SCHED_AUTOGROUP
        struct autogroup        *autogroup;
#endif

        struct cfs_bandwidth    cfs_bandwidth;

#ifdef CONFIG_UCLAMP_TASK_GROUP
        /* The two decimal precision [%] value requested from user-space */
        unsigned int            uclamp_pct[UCLAMP_CNT];
        /* Clamp values requested for a task group */
        struct uclamp_se        uclamp_req[UCLAMP_CNT];
        /* Effective clamp values used for a task group */
        struct uclamp_se        uclamp[UCLAMP_CNT];
#endif

};
  • css
    • cgroup 서브시스템 상태
  • rcu
    • 미사용?
  • list
    • 전역 task_groups 리스트에 연결될 때 사용하는 노드이다.
  • *parent
    • 부모 태스크 그룹
  • siblings
    • 부모 태스크 그룹의 children 리스트에 연결될 떄 사용된다.
  • children
    • 자식 태스크 그룹들이 연결될  리스트이다.
  • cfs_bandwidth
    • cfs 관련 밴드폭 정보
  • cfs 그룹 스케줄링 관련
    • **se
      • cpu 수 만큼 그룹용 cfs 스케줄 엔티티가 할당되어 연결된다.
    • **cfs_rq
      • cpu 수 만큼 cfs 런큐가 할당되어 연결된다.
    • shares
      • 그룹에 적용할 로드 weight 비율
    • load_avg
      • cfs 런큐의 로드 평균을 모두 합한 값으로 결국 그룹 cfs 런큐들의 로드 평균을 모두 합한 값이다.
  • rt 그룹 스케줄링 관련
    • **rt_se
      • cpu 수 만큼 그룹용 rt 스케줄 엔티티가 할당되어 연결된다.
    • **rt_rq
      • cpu 수 만큼 rt 런큐가 할당되어 연결된다.
    • rt_bandwidth
      • cfs 관련 밴드폭 정보
  • autogroup 관련
    • *autogroup

 

참고

 

댓글 남기기

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