Scheduler -2- (cpu load & PELT)

 

Scheduler -2- (cpu load)

 

커널 v3.11-rc1에서 kernel/sched/core.c의 cpu 로드 관련 함수 들을 kernel/sched/proc.c 로 옮겼고,

다시 커널 v4.2-rc1에서 kernel/sched/loadavg.c 파일로 옮겼다. 아래 코드는 커널 v4.0 기준이므로 kernel/sched/proc.c 파일에 존재한다.

 

 

추세 관련 사전 산술 지식

주식 시장에서 주가 흐름에 단순이동평균(SMA), 가중이동평균(WMA), 지수이동평균(EMA) 등을 사용하여 기간별 평균흐름을 나타내는데 먼저 머리를 정리하기 위해 다음과 같은 방법이 있음을 미리 산출해보자.

  • 예) 최근 6일간 종가(raw data): 1020, 1030, 1000, 1010, 1020, 1060일 때
    • 3일 단순 이동 평균(SMA: Simple Moving Average)
      • 과거 데이터와 최근 데이터를 고르게 반영
      • = (1010 + 1020 + 1060) / 3
      • = 1030
    • 3일 가중 이동 평균(WMA; Weighted Moving Average)
      • 최근 데이터에 높은 가중치를 주는 방법 (예: w1=1/6, w2=2/6, w3=3/6)
      • = 1010 * w1 + 1020 * w2 + 1060 * w3
      • = 168 + 340 + 530
      • = 1038
    • 3일 지수 이동 평균(EMA: Exponential Moving Average 또는 EWMA: Exponential Weighted Moving Average)
      • 최근 데이터에 더 높은 가중치를 주는 방법 (예: n=3일, k=2/(n+1)=0.5)
      • =전일 기준 3일 EMA(없으면 SMA) * (1-k) + 1040 * k
      • =1010 * 0.5 + 1060 * 0.5
      • =1035

 

리눅스 커널에서는 cpu 로드 산출에 필요한 모든 raw 데이터를 저장하지 않는다. 따라서 조금 다른 방법으로 지수 평활법(ES: Exponential Smoothing) 중 하나인 지수 감소 평균(EDA)을 사용한다. 먼저 1개의 cpu가 있는 시스템에서 태스크 1개가 동작 중인 경우 cpu 로드 값은 1.0이 된다. cpu가 4개가 동작하는 시스템에서는 이 값을 4로 나누게 되므로 0.25의 cpu 로드 값이 된다. 단 cpu 로드 값 1.0에 대응하여 리눅스 코드에서 사용되는 cpu load 값은 1024 및 2048이 사용되고 있다. (고정 소숫점 1.0 = 1,024 또는 2,048)

  • 지수 감소 평균(EDA: Exponential Decaying Average, EDMA: Exponential Damped Moving Average)
    • 기존 cpu 로드 값 * k + 새 cpu 로드 값 * (1 – k)
    • 리눅스 구현 로직에서는 avenrun[] 및 cpu_load[] 산출에 대한 k 값은 각각의 구현 항목에서 살펴본다.

 

cpu 로드 산출식

지정된 기간에 어떠한 일을 cpu가 쉬지 않고 일을 한 경우 그 값을 1.0이라고 한다. 만일 지정된 기간에 절반 동안 idle 상태에 빠져 있으면 0.5라고 한다. 그런데 밀려 있는 일이 있으면 그 량만큼 더해 산정하여 1을 초과하게 된다.

예) 1분 동안 같은 양의 작업을 10개를 수행하는 cpu가 있다 할 때 1분 동안 30개의 작업이 주어지면 10개는 처리를 하고 20개는 처리하지 못한 상태가 된다. 이러한 경우 cpu 로드는 3.0이라 한다.

예) 위와 동일한 조건으로 cpu가 2개 준비된 경우 cpu 로드는 1.5라 한다.

 

리눅스에서는 TASK_RUNNING 및 TASK_UNINTERRUPTIBLE 상태에 있는 태스크, 즉 active 태스크의 수를 어느 일정 기간 범위에서 주어진 간격으로 probe한 값을 사용하며 지수 평활법으로 연결하여 cpu 로드 값을 산출한다.

 

A. 글로벌 로드 평균 (1min ~ 15min)

최근 1분, 5분, 15분 간의 평균 cpu 로드 값을 산출하여 avenrun[]에 저장하고 글로벌 로드 평균(global load average)라고도 불린다.

  • “uptime” 명령의 load average 필드의 3개의 값을 참고한다.
  • 또한 “/proc/loadavg” 파일을 확인하여 최초 3개의 값을 통해서도 확인할 수 있다.
$ uptime
 20:41:18 up  1:09,  2 users,  load average: 0.57, 0.15, 0.11
$ cat /proc/loadavg 
0.55 0.28 0.16 1/318 2112
  • nr_active = 각 cpu의 런큐에 있는 running 및 uninterruptible 태스크의 수를 더한다.
  • avenrun[0] = avenrun[0]*e1 + nr_active*(1-e1) + 0.5      <- 1분
  • avenrun[1] = avenrun[1]*e2 + nr_active*(1-e2) + 0.5      <- 5분
  • avenrun[2] = avenrun[2]*e3 + nr_active*(1-e3) + 0.5      <- 15분

 

B. 런큐 로드 평균 (1 tick ~ 16 ticks)

  • 매 tick 마다 평균 cpu 로드를 산출하여 rq->cpu_load[5]에 저장하고 로드밸런스를 위해 사용된다.
  • rq->cpu_load[]에 5개의 cpu 로드가 저장되는데 각각의 기간은 2배씩 커진다.
    • cpu_load[0] <- 1 tick 기간
    • cpu_load[1] <- 2 ticks 기간
    • cpu_load[1] <- 4 ticks 기간
    • cpu_load[3] <- 8 ticks 기간
    • cpu_load[4] <- 16 ticks 기간
  • “/proc/sched_debug” 파일을 확인하여
# cat /proc/sched_debug 
Sched Debug Version: v0.11, 4.4.11-v7+ #888
ktime                                   : 4393169013.219659
sched_clk                               : 4393169057.443466
cpu_clk                                 : 4393169057.443935
jiffies                                 : 439286901

sysctl_sched
  .sysctl_sched_latency                    : 18.000000
  .sysctl_sched_min_granularity            : 2.250000
  .sysctl_sched_wakeup_granularity         : 3.000000
  .sysctl_sched_child_runs_first           : 0
  .sysctl_sched_features                   : 44859
  .sysctl_sched_tunable_scaling            : 1 (logaritmic)

cpu#0
  .nr_running                    : 0
  .load                          : 0
  .nr_switches                   : 145928196
  .nr_load_updates               : 57706792
  .nr_uninterruptible            : -324009
  .next_balance                  : 439.286901
  .curr->pid                     : 0
  .clock                         : 4393169054.864143
  .clock_task                    : 4393169054.864143
  .cpu_load[0]                   : 81
  .cpu_load[1]                   : 41
  .cpu_load[2]                   : 21
  .cpu_load[3]                   : 11
  .cpu_load[4]                   : 6

 

C. PELT(Per Entity Lod Tracking)

  • 러너블 로드 평균(runnable load average) 및 블럭드 로드 평균(blocked load average)라고도 불린다.
  • 커널 v3.8부터 사용되었다.
  • task가 enqueue/dequeue 될 때마다 갱신한다.
  • 단위 기간은 1ms(1024us)이고 로드는 단위 시간마다 decay된다.
    • 현재 시간으로부터 단위 기간이 점점 흘러가는 경우 점점 decay 되는 양이 커진다.
    • = + × + × + × + ⋯
    • 32번째 단위 시간에 대해 decay 값은 절반으로 한다.
      • y^32=0.5
      • y = 약 0.97857206
# cat /proc/sched_debug 

(...생략...)

cfs_rq[0]:/autogroup-677
  .exec_clock                    : 0.000000
  .MIN_vruntime                  : 0.000001
  .min_vruntime                  : 1599.476675
  .max_vruntime                  : 0.000001
  .spread                        : 0.000000
  .spread0                       : -121602963.722830
  .nr_spread_over                : 0
  .nr_running                    : 0
  .load                          : 0
  .load_avg                      : 7
  .runnable_load_avg             : 3
  .util_avg                      : 7
  .removed_load_avg              : 0
  .removed_util_avg              : 0
  .tg_load_avg_contrib           : 7
  .tg_load_avg                   : 7

 

 

A. 글로벌 로드 평균 – avenrun[] 산출 – (1, 5, 15분)

글로벌 로드 평균은 매 스케줄 틱에서 호출되지만 산출 주기(calc_load_update: 기본 5초)에 한 번씩 갱신한다. 엄밀히 말하자면 산출 주기가 도래하면 그 후 10틱의 시간이 지난 후에 갱신한다.

calc_global_load()

kernel/sched/loadavg.c

/*
 * calc_load - update the avenrun load estimates 10 ticks after the
 * CPUs have updated calc_load_tasks.
 */
void calc_global_load(unsigned long ticks) 
{
        long active, delta;

        if (time_before(jiffies, calc_load_update + 10))
                return;

        /*
         * Fold the 'old' idle-delta to include all NO_HZ cpus.
         */ 
        delta = calc_load_fold_idle();
        if (delta)
                atomic_long_add(delta, &calc_load_tasks);

        active = atomic_long_read(&calc_load_tasks);
        active = active > 0 ? active * FIXED_1 : 0;

        avenrun[0] = calc_load(avenrun[0], EXP_1, active);
        avenrun[1] = calc_load(avenrun[1], EXP_5, active);
        avenrun[2] = calc_load(avenrun[2], EXP_15, active);

        calc_load_update += LOAD_FREQ;

        /*
         * In case we idled for multiple LOAD_FREQ intervals, catch up in bulk.
         */
        calc_global_nohz();
}

cpu 로드 산출 주기(5초) 이후 10 틱이 지난 후에 최근 1분, 5분, 15분 간의 cpu 로드를 산출하여 avenrun[]에 대입한다.

  • 코드 라인 9~10에서 현재 시각(jiffies)이 cpu 로드 산출 주기(5초)+10 이전이면 함수를 빠져나간다.
  • 코드 라인 15~17에서 현재 cpu에 대해 active 태스크 수의 변화분 delta를 얻어와서 calc_load_tasks에 반영한다.
  • 코드 라인 19~20에서 active 태스크가 있는 경우 그 수에 cpu 로드 1.0에 해당하는 값 2048을 곱한다.
    • 예) active=4096인 경우 cpu 로드는 2.0이다.
  • 코드 라인 22~24에서 기존 cpu 로드 값과 avenrun[]과 새 cpu 로드 값인 active 값으로 각각 1분, 5분, 15분에 해당하는 지수 팩터 EXP_n을 사용하여 cpu 로드를 산출한 후 avenrun[]에 대입한다.
  • 코드 라인 26에서 다음 cpu 로드 산출 주기를 위해 5초를 더한다.
  • 코드 라인 31에서 nohz idle로 인해 다음 cpu 로드 산출 주기를 이미 초과한 경우 miss된 cpu 로드 갱신 주기 수만큼 적용하여 cpu 로드를 산출하여 avenrun[]을 다시 갱신한다.
    • 예) 20여초 nohz idle로 인해 cpu 로드를 갱신하지 못한 경우 처음 5초에 해당하는 시간의 cpu 로드가 이미 갱신되었으므로 나머지 3번에 해당하는 cpu 로드를 산출하도록 한다.

 

Fake cpu 로드 계산을 위한 11비트 지수 상수 값

/*
 * These are the constant used to fake the fixed-point load-average
 * counting. Some notes:
 *  - 11 bit fractions expand to 22 bits by the multiplies: this gives
 *    a load-average precision of 10 bits integer + 11 bits fractional
 *  - if you want to count load-averages more often, you need more
 *    precision, or rounding will get you. With 2-second counting freq,
 *    the EXP_n values would be 1981, 2034 and 2043 if still using only
 *    11 bit fractions.
 */
extern unsigned long avenrun[];         /* Load averages */
extern void get_avenrun(unsigned long *loads, unsigned long offset, int shift);

#define FSHIFT          11              /* nr of bits of precision */
#define FIXED_1         (1<<FSHIFT)     /* 1.0 as fixed-point */
#define LOAD_FREQ       (5*HZ+1)        /* 5 sec intervals */
#define EXP_1           1884            /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5           2014            /* 1/exp(5sec/5min) */ 
#define EXP_15          2037            /* 1/exp(5sec/15min) */
  • FSHIFT
    • 11비트 정확도를 사용하는데 필요한 비트 수
  • FIXED_1
    • 11비트 정확도 값 (2048)
    • 고정 소숫점 형태인 cpu 로드 1.0은 리눅스 구현에서는 2048이라는 정수로 표현한다.
  • LOAD_FREQ
    • 디폴트 5초 주기 산출
  • EXP_1
    • 마지막 1분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 92%를 적용하여 반영한다.
    • 1/(exp(1/12)) * FIXED_1 = 92.00% * 2048 = 1884
  • EXP_5
    • 마지막 5분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 98%를 적용하여 반영한다.
    • 1/(exp(1/60)) * FIXED_1 = 98.35% * 2048 = 2014
  • EXP_15
    • 마지막 15분 동안의 cpu 로드를 산출하기 위해 11비트 정확도 값 2048의 약 99%를 적용하여 반영한다.
    • 1/(exp(1/60)) * FIXED_1 = 99.45% * 2048 = 2037

 

다음 그림은 1분, 5분, 15분에 해당하는 지수 팩터 EXP_1, EXP_5, EXP_15가 어떻게 산출되었는지를 보여준다.

  • k(12) = EXP_1 = 0.9200 (=1884)
  • k(60) = EXP_5 = 0.9835 (=2014)
  • k(180) = EXP_15 = 0.9945 (=2037)

 

다음 그림은 위의 지수 팩터를 사용하여 리눅스에서 구현된 cpu 로드 산출 식이다.

 

다음 그림은 처음 cpu 로드 0.5에서 출발하여 매 5초 마다 cpu 로드가 산출되는 과정을 보여주며 마지막에서는 nohz idle로 인해 20초간 틱이 발생되지 않아 밀려 있는 cpu 로드 계산이 한꺼번에 이루어지는 것을 보여준다.

 

active 태스크 수

cpu 로드를 산출하기 위해 active 태스크 수를 파악해야 하는데 산출할 때 마다 각 cpu의 런큐를 뒤지지 않고 전역 변수에 필요 시마다 전파하여 사용하는 방식을 사용하여 조금이라도 빠르게 산출되게 하였다. nohz idle을 위해 중간 단계에 calc_load_idle[2] 변수를 사용하였다.

 

calc_load_fold_idle()

kernel/sched/loadavg.c

static long calc_load_fold_idle(void)
{
        int idx = calc_load_read_idx();
        long delta = 0;
        
        if (atomic_long_read(&calc_load_idle[idx]))
                delta = atomic_long_xchg(&calc_load_idle[idx], 0);

        return delta;
}

현재 cpu의 런큐에서 다시 계산된 active 태스크 수의 변경된 값 delta를 얻어온다.

  • 코드 라인 3에서 calc_load_idle[] 배열 중 어떤 값을 사용할지 인덱스 값을 알아온다.
  • 코드 라인 6에서 인덱스에 해당하는 calc_load_idle[] 값이 존재하는 경우 이 값을 0으로 초기화하고 저장되었던 값을 반환한다.

 

/*
 * Handle NO_HZ for the global load-average.
 *
 * Since the above described distributed algorithm to compute the global
 * load-average relies on per-cpu sampling from the tick, it is affected by
 * NO_HZ.
 *
 * The basic idea is to fold the nr_active delta into a global idle-delta upon
 * entering NO_HZ state such that we can include this as an 'extra' cpu delta
 * when we read the global state.
 *
 * Obviously reality has to ruin such a delightfully simple scheme:
 *
 *  - When we go NO_HZ idle during the window, we can negate our sample
 *    contribution, causing under-accounting.
 *
 *    We avoid this by keeping two idle-delta counters and flipping them
 *    when the window starts, thus separating old and new NO_HZ load.
 *
 *    The only trick is the slight shift in index flip for read vs write.
 *
 *        0s            5s            10s           15s
 *          +10           +10           +10           +10
 *        |-|-----------|-|-----------|-|-----------|-|
 *    r:0 0 1           1 0           0 1           1 0
 *    w:0 1 1           0 0           1 1           0 0
 *
 *    This ensures we'll fold the old idle contribution in this window while
 *    accumlating the new one.
 *
 *  - When we wake up from NO_HZ idle during the window, we push up our
 *    contribution, since we effectively move our sample point to a known
 *    busy state.
 *
 *    This is solved by pushing the window forward, and thus skipping the
 *    sample, for this cpu (effectively using the idle-delta for this cpu which
 *    was in effect at the time the window opened). This also solves the issue
 *    of having to deal with a cpu having been in NOHZ idle for multiple
 *    LOAD_FREQ intervals.
 *
 * When making the ILB scale, we should try to pull this in as well.
 */
static atomic_long_t calc_load_idle[2];
static int calc_load_idx;

 

nohz idle 영향으로 인해 변경된 해당 cpu의 active 태스크 수 delta 값을 calc_load_idle[2]에 저장을 하는데 저장 위치는 5초 갱신 주기마다 교대로 바뀐다. 이러한 delta 값을 읽어내는 루틴에서는 매 5초 + 10 틱마다 지난 5초 이내에 변동된 delta 값을 읽어낸다. 읽어내는 시점의 10 tick 범위는 다음에 읽도록 한다.

  • calc_load_read_idx() 함수를 통해 calc_load_idx 값의 하위 1비트만 읽어서 0과 1의 인덱스 값으로 calc_load_idle[] 값을읽어온다.
  • 매 5초+10틱에서 calc_load_idx 값을 증가시킨다.
  • calc_load_write_idx() 함수를 통해 calc_load_idx 값의 하위 1비트만 읽어내는데 10 tick 구간은 flip 시킨다. 이렇게 알아온 0과 1의 인덱스 값으로 calc_load_idle[] 값을읽어온다.

 

calc_load()

kernel/sched/proc.c

/*
 * a1 = a0 * e + a * (1 - e)
 */
static unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
        load *= exp;
        load += active * (FIXED_1 - exp);
        load += 1UL << (FSHIFT - 1);
        return load >> FSHIFT;
}

지수 active 태스크 수에 대한 지수 감소 평균(EDA)을 사용하여 산출한다.

 

예) 기존 1,5,15분간 cpu 로드=0.5이고 이번 틱에 active 태스크=2인 상태로 3번의 틱 만큼 진행을 하면

  • 산출 전:
    • avenrun[0]=1024, active=4096
    • avenrun[1]=1024, active=4096
    • avenrun[2]=1024,active=4096
  • 1st 틱:
    • avenrun[0]=(1024 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1271
    • avenrun[1]=(1024 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1076
    • avenrun[2]=(1024 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1041
  • 2nd 틱:
    • avenrun[0]=(1271 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1498
    • avenrun[1]=(1076 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1127
    • avenrun[2]=(1041 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1058
  • 3rd 틱:
    • avenrun[0]=(1498 * 1884 + 4096 * (2048-1884) + 1024) / 2048 = 1707
    • avenrun[1]=(1127 * 2014 + 4096 * (2048-2014) + 1024) / 2048 = 1177
    • avenrun[2]=(1058 * 2037 + 4096 * (2048-2037) + 1024) / 2048 = 1075

 

calc_global_nohz()

kernel/sched/proc.c

/*
 * NO_HZ can leave us missing all per-cpu ticks calling
 * calc_load_account_active(), but since an idle CPU folds its delta into
 * calc_load_tasks_idle per calc_load_account_idle(), all we need to do is fold
 * in the pending idle delta if our idle period crossed a load cycle boundary.
 *
 * Once we've updated the global active value, we need to apply the exponential
 * weights adjusted to the number of cycles missed.
 */
static void calc_global_nohz(void)
{
        long delta, active, n;

        if (!time_before(jiffies, calc_load_update + 10)) {
                /*
                 * Catch-up, fold however many we are behind still
                 */
                delta = jiffies - calc_load_update - 10;
                n = 1 + (delta / LOAD_FREQ);

                active = atomic_long_read(&calc_load_tasks);
                active = active > 0 ? active * FIXED_1 : 0;

                avenrun[0] = calc_load_n(avenrun[0], EXP_1, active, n);
                avenrun[1] = calc_load_n(avenrun[1], EXP_5, active, n);
                avenrun[2] = calc_load_n(avenrun[2], EXP_15, active, n);

                calc_load_update += n * LOAD_FREQ;
        }

        /*
         * Flip the idle index...
         *
         * Make sure we first write the new time then flip the index, so that
         * calc_load_write_idx() will see the new time when it reads the new
         * index, this avoids a double flip messing things up.
         */
        smp_wmb();
        calc_load_idx++;
}

nohz idle로 인해 갱신이 밀려 있는 경우 그 밀려 있는 횟수 만큼 한 번에 산출을 하여 avenrun[]에 대입한다.

  • 코드 라인 14에서 현재 시간(jiffies)이 갱신 주기+10틱보다 뒤에 있는 경우 즉, 갱신이 밀려 있는 경우
  • 코드 라인 18~19에서 몇 번 밀려 있는지 횟수를 산출한다.
    • 예) jiffies와ㅓ calc_load_update의 차이가 21초인 경우 21/5+1 = 정수 5가된다.
  • 코드 라인 21~22에서 현재 active 태스크 수를 읽어와서 그 값에 FIXED_1(2048)을 곱한다.
  • 코드 라인 24~28에서 avenrun[] 값을 갱신하고 갱신 주기도 update한다.
  • 코드 라인 39에서 calc_load_idx를 증가시켜 새로운 인덱스를 사용하도록 한다.

 

calc_load_n()

kernel/sched/proc.c

/*
 * a1 = a0 * e + a * (1 - e)
 *
 * a2 = a1 * e + a * (1 - e)
 *    = (a0 * e + a * (1 - e)) * e + a * (1 - e)
 *    = a0 * e^2 + a * (1 - e) * (1 + e)
 *
 * a3 = a2 * e + a * (1 - e)
 *    = (a0 * e^2 + a * (1 - e) * (1 + e)) * e + a * (1 - e)
 *    = a0 * e^3 + a * (1 - e) * (1 + e + e^2)
 *
 *  ...
 *
 * an = a0 * e^n + a * (1 - e) * (1 + e + ... + e^n-1) [1]
 *    = a0 * e^n + a * (1 - e) * (1 - e^n)/(1 - e)
 *    = a0 * e^n + a * (1 - e^n)
 *
 * [1] application of the geometric series:
 *
 *              n         1 - x^(n+1)
 *     S_n := \Sum x^i = -------------
 *             i=0          1 - x
 */
static unsigned long
calc_load_n(unsigned long load, unsigned long exp,
            unsigned long active, unsigned int n)
{

        return calc_load(load, fixed_power_int(exp, FSHIFT, n), active);
}

기존 load 값에 새 active 값이 exp(간격)으로 FSHIFT(2048) 정확도로 산출한다.

  • 예) exp=1884(1분 주기), FSHIFT=2048(정확도), load=1024, active=2048, n=4
    • = load * (exp / FSHIFT) + (active * (FSHIFT – exp) / 2048) + 0.5 를 4번 수행
    • = load * (exp^n / 2048^n) + (active * (1 – (exp^n / 2048^n)) + 0.5와 동일
    • = 1024 * (1884^4 / 2048^4) + (active * (1 – (1884^4) / 2048^4) + 0.5
    • = 1896

 

active 태스크 수가 변함 없이 n 번의 횟수만큼 계산되는 결과와 동일하다.

 

fixed_power_int()

kernel/sched/proc.c

/**
 * fixed_power_int - compute: x^n, in O(log n) time
 *
 * @x:         base of the power
 * @frac_bits: fractional bits of @x
 * @n:         power to raise @x to.
 *
 * By exploiting the relation between the definition of the natural power
 * function: x^n := x*x*...*x (x multiplied by itself for n times), and
 * the binary encoding of numbers used by computers: n := \Sum n_i * 2^i,
 * (where: n_i \elem {0, 1}, the binary vector representing n),
 * we find: x^n := x^(\Sum n_i * 2^i) := \Prod x^(n_i * 2^i), which is
 * of course trivially computable in O(log_2 n), the length of our binary
 * vector.
 */
static unsigned long
fixed_power_int(unsigned long x, unsigned int frac_bits, unsigned int n)
{
        unsigned long result = 1UL << frac_bits;

        if (n) for (;;) {
                if (n & 1) {
                        result *= x;
                        result += 1UL << (frac_bits - 1);
                        result >>= frac_bits;
                }
                n >>= 1;
                if (!n)
                        break;
                x *= x;
                x += 1UL << (frac_bits - 1);
                x >>= frac_bits;
        }

        return result;
}

(x^n) / (2^frac_bits)^(n-1) 를 산출한다. 산출 시 n번 만큼 반복하지 않고 O(log2 n)번으로 산출되는 것이 특징으로 n 값이 클 때 효과적이다.

  • 예) x=1884 (EXP_1), frac_bits=11 (11비트 정밀도), n=5
    • = (1884 * 1884 * 1884 * 1884 * 1884) / (2048 * 2048 * 2048 * 2048) = 1,349

 

B. 런큐 로드 평균 – rq->cpu_load[] 산출 – (1, 2, 4, 8, 16 ticks)

update_cpu_load_active()

kernel/sched/proc.c

/*
 * Called from scheduler_tick()
 */
void update_cpu_load_active(struct rq *this_rq)
{
        unsigned long load = get_rq_runnable_load(this_rq);
        /*
         * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
         */
        this_rq->last_load_update_tick = jiffies;
        __update_cpu_load(this_rq, load, 1);

        calc_load_account_active(this_rq);
}

요청한 런큐의 cpu 로드 active를 갱신한다.

  • 코드 라인 6에서 런큐의 load 평균 값을 알아온다.
  • 코드 라인 10에서 현재 시각(jiffies)으로 cpu 로드가 산출되었음을 기록한다.
  • 코드 라인 11에서 cpu 로드를 산출한다.
  • 코드 라인 13에서 5초 간격으로 전역 calc_load_tasks 값을 갱신한다.
    • 매 스케줄 tick 마다 nr_active를 산출하지 않기 위해 5초 간격으로 nr_active를 산출하여 그 차이 값 만큼만 calc_load_tasks에 반영한다.

 

다음 그림은 런큐의 cpu 로드가 산출되기 위해 처리되는 흐름을 보여준다.

 

get_rq_runnable_load()

kernel/sched/proc.c

#ifdef CONFIG_SMP
static inline unsigned long get_rq_runnable_load(struct rq *rq)
{
        return rq->cfs.runnable_load_avg;
}
#else
static inline unsigned long get_rq_runnable_load(struct rq *rq)
{
        return rq->load.weight;
}
#endif

런큐의 로드 평균 값을 반환한다.

  • enqueue_entity_load_avg(), dequeue_entity_load_avg(), update_entity_load_avg() 함수 등에서 cfs 태스크들의 load 평균이 산출된다.

 

__update_cpu_load()

kernel/sched/proc.c

/*
 * Update rq->cpu_load[] statistics. This function is usually called every
 * scheduler tick (TICK_NSEC). With tickless idle this will not be called
 * every tick. We fix it up based on jiffies.
 */
static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
                              unsigned long pending_updates)
{
        int i, scale;

        this_rq->nr_load_updates++;

        /* Update our load: */
        this_rq->cpu_load[0] = this_load; /* Fasttrack for idx 0 */
        for (i = 1, scale = 2; i < CPU_LOAD_IDX_MAX; i++, scale += scale) {
                unsigned long old_load, new_load;

                /* scale is effectively 1 << i now, and >> i divides by scale */

                old_load = this_rq->cpu_load[i];
                old_load = decay_load_missed(old_load, pending_updates - 1, i);
                new_load = this_load;
                /*
                 * Round up the averaging division if load is increasing. This
                 * prevents us from getting stuck on 9 if the load is 10, for
                 * example.
                 */
                if (new_load > old_load)
                        new_load += scale - 1;

                this_rq->cpu_load[i] = (old_load * (scale - 1) + new_load) >> i;
        }

        sched_avg_update(this_rq);
}

jiffies 기반 tick 마다 런큐의 cpu 로드를 갱신한다.

  • 코드 라인 11에서 nr_load_updates 카운터를 1 증가시킨다. (단순 카운터)
  • 코드 라인 14에서 cpu_load[0]에는 load 값을 100% 반영한다.
  • 코드 라인 15에서 cpu_load[1] ~ cpu_load[4]까지 갱신하기 위해 루프를 돈다. 루프를 도는 동안 scale 값은 2, 4, 8, 16과 같이 2배씩 커진다.
  • 코드 라인 20~21에서 4개 배열에 있는 기존 cpu 로드값들은 지연 틱 값에 의해 미리 준비된 테이블의 값을 참고하여 decay load 값으로 산출된다.
    • decay_load = old_load * miss 틱을 사용한 decay factor
  • 코드 라인28~29에서 새 로드가 기존 로드보다 큰 경우에 한하여 즉, 로드가 상승되는 경우 올림을 할 수 있도록 새 로드에 scale-1을 추가한다.
  • 코드 라인 31에서 기존 로드에 (2^i-1)/2^i 의 비율을 곱하고 새 로드에 1/(2^i) 비율을 곱한 후 더한다.
    •  i=1:
      • cpu_load[1] = decay_load * 1/2 + new_load * 1/2
    • i=2:
      • cpu_load[2] = decay_load * 3/4 + new_load * 1/4
    • i=3:
      • cpu_load[3] = decay_load * 7/8 + new_load * 1/8
    • i=4
      • cpu_load[4] = decay_load * 15/16 + new_load * 1/16
  • 코드 라인 34에서 런큐의 age_stamp와 rt_avg 값을 갱신한다.

 

 

다음 그림은 cpu_load[]를 산출하는 식이다.

 

다음 그림은 런큐의 cpu_load[] 값이 매 tick 마다 변화되는 모습을 보여준다.

 

decay_load_missed()

kernel/sched/proc.c

/*
 * Update cpu_load for any missed ticks, due to tickless idle. The backlog
 * would be when CPU is idle and so we just decay the old load without
 * adding any new load.
 */
static unsigned long
decay_load_missed(unsigned long load, unsigned long missed_updates, int idx)
{
        int j = 0;

        if (!missed_updates)
                return load;

        if (missed_updates >= degrade_zero_ticks[idx])
                return 0;

        if (idx == 1)
                return load >> missed_updates;

        while (missed_updates) {
                if (missed_updates % 2)
                        load = (load * degrade_factor[idx][j]) >> DEGRADE_SHIFT;

                missed_updates >>= 1;
                j++;
        }
        return load;
}

nohz idle 기능이 동작하여 tick이 발생하지 않은 횟수를 사용하여 미리 계산된 테이블에서 load 값을 산출한다.

  • 코드 라인 11~12에서 miss 틱이 없는 경우 그냥 load 값을 그대로 반환한다.
  • 코드 라인 14~15에서 miss 틱이 idx 순서대로 8, 32, 64, 128 값 이상인 경우 너무 작은 load 값을 반영해봤자 미미하므로 load 값으로 0을 반환한다.
  • 코드 라인 17~18에서 인덱스 값이 1인 경우 load 값을 miss 틱 만큼 우측으로 쉬프트한다.
  • 코드 라인 20~26에서 missed_updates 값의 하위 비트부터 설정된 경우 이 위치에 해당하는 테이블에서 값을 곱하고 128로 나눈다.

 

다음 그림은 idx=2, miss 틱=13이 주어졌고 이에 해당하는 decay 로드 값을 구하는 모습을 보여준다.

 

/*
 * The exact cpuload at various idx values, calculated at every tick would be
 * load = (2^idx - 1) / 2^idx * load + 1 / 2^idx * cur_load
 *
 * If a cpu misses updates for n-1 ticks (as it was idle) and update gets called
 * on nth tick when cpu may be busy, then we have:
 * load = ((2^idx - 1) / 2^idx)^(n-1) * load
 * load = (2^idx - 1) / 2^idx) * load + 1 / 2^idx * cur_load
 *
 * decay_load_missed() below does efficient calculation of
 * load = ((2^idx - 1) / 2^idx)^(n-1) * load
 * avoiding 0..n-1 loop doing load = ((2^idx - 1) / 2^idx) * load
 *
 * The calculation is approximated on a 128 point scale.
 * degrade_zero_ticks is the number of ticks after which load at any
 * particular idx is approximated to be zero.
 * degrade_factor is a precomputed table, a row for each load idx.
 * Each column corresponds to degradation factor for a power of two ticks,
 * based on 128 point scale.
 * Example:
 * row 2, col 3 (=12) says that the degradation at load idx 2 after
 * 8 ticks is 12/128 (which is an approximation of exact factor 3^8/4^8).
 *
 * With this power of 2 load factors, we can degrade the load n times
 * by looking at 1 bits in n and doing as many mult/shift instead of
 * n mult/shifts needed by the exact degradation.
 */
#define DEGRADE_SHIFT           7
static const unsigned char
                degrade_zero_ticks[CPU_LOAD_IDX_MAX] = {0, 8, 32, 64, 128};

idx별로 miss 틱에 대한 반영 비율을 적용할 지 여부를 확인하기 위한 테이블이다.

  • miss 틱 수가 idx에 따른 테이블 값 이상으로 오래된 경우 기존 load 값을 사용할 필요 없다.
  • 예) idx=2, miss 틱=33인 경우 기존 cpu 로드 값을 0으로 간주하게 한다.

 

static const unsigned char
                degrade_factor[CPU_LOAD_IDX_MAX][DEGRADE_SHIFT + 1] = {
                                        {0, 0, 0, 0, 0, 0, 0, 0},
                                        {64, 32, 8, 0, 0, 0, 0, 0},
                                        {96, 72, 40, 12, 1, 0, 0},
                                        {112, 98, 75, 43, 15, 1, 0},
                                        {120, 112, 98, 76, 45, 16, 2} };

idx 별로 miss 틱에 대한 decay_load를 구하기 위한 테이블이다. (각 값은 x/128에 해당하는 분자 값이다.)

  • 예) idx=2, miss 틱=6, load=1024 일 때
    • 분모가 128이고, miss 틱에 대한 비트에 해당하는 72와 40에 해당하는 분자 값을 사용한다.
    • decay_load = 1024 * 72/128 * 40/128 = 1024 * 2880 / 16384 = 180

 

평균 스케쥴 갱신

sched_avg_update()

kernel/sched/core.c

void sched_avg_update(struct rq *rq)
{
        s64 period = sched_avg_period();

        while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
                /*
                 * Inline assembly required to prevent the compiler
                 * optimising this loop into a divmod call.
                 * See __iter_div_u64_rem() for another example of this.
                 */
                asm("" : "+rm" (rq->age_stamp));
                rq->age_stamp += period;
                rq->rt_avg /= 2;
        }
}

런큐의 age_stamp와 rt_avg 값을 갱신한다.

  • 코드 라인 3에서 평균 스케줄 타임(ns)의 절반을 가져와서 period에 대입한다.
  • 코드 라인 5~14에서 런큐 클럭에서 age_stamp를 뺀 간격이 period보다 큰 경우에 한해 계속 루프를 돌며 age_stamp를 period만큼 더하고 rt_avg 값은 절반으로 나눈다.

 

sched_avg_period()

kernel/sched/sched.h

static inline u64 sched_avg_period(void)
{
        return (u64)sysctl_sched_time_avg * NSEC_PER_MSEC / 2;
}

평균 스케줄 타임(ns)의 절반을 가져온다.

 

5초 간격으로 active 태스크 수 산출

calc_load_account_active()

kernel/sched/proc.c

/*
 * Called from update_cpu_load() to periodically update this CPU's
 * active count.
 */
static void calc_load_account_active(struct rq *this_rq)
{
        long delta;

        if (time_before(jiffies, this_rq->calc_load_update))
                return;

        delta  = calc_load_fold_active(this_rq);
        if (delta)
                atomic_long_add(delta, &calc_load_tasks);

        this_rq->calc_load_update += LOAD_FREQ;
}

로드 산출 주기(5초) 간격으로 active 태스크 수를 전역 calc_load_tasks에 갱신한다.

  • 코드 라인 9~10에서 지정된 5초 만료시간이 안된 경우 함수를 빠져나간다.
  • 코드 라인 12~14에서 기존 active 태스크 수와 현재 산출한 active 태스크 수의 차이를 알아와서 calc_load_tasks에 추가하여 갱신한다.
  • 코드 라인 16에서 다음 산출할 시간을 위해 5초를 더한다.

 

다음 그림은 런큐의 active 태스크 수를 런큐와 전역 변수에 갱신하는 것을 보여준다.

 

calc_load_fold_active()

kernel/sched/proc.c

long calc_load_fold_active(struct rq *this_rq)
{
        long nr_active, delta = 0;

        nr_active = this_rq->nr_running;
        nr_active += (long) this_rq->nr_uninterruptible;

        if (nr_active != this_rq->calc_load_active) {
                delta = nr_active - this_rq->calc_load_active;
                this_rq->calc_load_active = nr_active;
        }

        return delta;
}

요청한 런큐의 기존 active 태스크 수와 현재 산출한 active 태스크 수의 차이를 산출한다.

  • 코드 라인 5~6에서 요청한 런큐의 active 태스크 수를 알아온다.
  • 코드 라인 8~13에서 런큐의 calc_load_active와 다른 경우 이 값을 갱신하고 그 차이를 delta 값으로 하여 반환한다.

 

C. PELT: Per-Entity Load Tracking

 

enqueue_entity_load_avg()

kernel/sched/fair.c

/* Add the load generated by se into cfs_rq's child load-average */
static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
                                                  struct sched_entity *se,
                                                  int wakeup)
{       
        /*
         * We track migrations using entity decay_count <= 0, on a wake-up
         * migration we use a negative decay count to track the remote decays
         * accumulated while sleeping.
         *
         * Newly forked tasks are enqueued with se->avg.decay_count == 0, they
         * are seen by enqueue_entity_load_avg() as a migration with an already
         * constructed load_avg_contrib.
         */
        if (unlikely(se->avg.decay_count <= 0)) {
                se->avg.last_runnable_update = rq_clock_task(rq_of(cfs_rq));
                if (se->avg.decay_count) {
                        /*
                         * In a wake-up migration we have to approximate the
                         * time sleeping.  This is because we can't synchronize
                         * clock_task between the two cpus, and it is not
                         * guaranteed to be read-safe.  Instead, we can
                         * approximate this using our carried decays, which are
                         * explicitly atomically readable.
                         */
                        se->avg.last_runnable_update -= (-se->avg.decay_count)
                                                        << 20;
                        update_entity_load_avg(se, 0);
                        /* Indicate that we're now synchronized and on-rq */
                        se->avg.decay_count = 0;
                }
                wakeup = 0;
        } else {
                __synchronize_entity_decay(se);
        }

        /* migrated tasks did not contribute to our blocked load */
        if (wakeup) {
                subtract_blocked_load_contrib(cfs_rq, se->avg.load_avg_contrib);
                update_entity_load_avg(se, 0);
        }

        cfs_rq->runnable_load_avg += se->avg.load_avg_contrib;
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !wakeup);
}

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

  • 코드 라인 15~32에서 낮은 확률로 decay_count가 0이하인 경우 avg.last_runnable_update에서 음수 decay_count 만큼의 ms 단위의 기간을 감소시키고 decay_count는 0으로 변경한다. 그리고 엔티티 로드 평균을 구하고 wakeup 요청을 0으로 한다.
    • 처음 태스크가 fork된 경우 decay_count 값은 0이하 이다.
  • 코드 라인 33~35에서 엔티티 decay를 동기화시킨다.
  • 코드 라인 38~41에서 wakeup 요청이 있는 경우 migrate된 태스크들은 blocked 로드에서 기여 값을 빼고 엔티티 로드 평균을 구한다.
  • 코드 라인 43~44에서 cfs-_rq->runnable_load_avg에 기여 값을 더하고 blocked 로드 평균 산출을 갱신한다.

 

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 를 반환한다.

 

update_entity_load_avg()

kernel/sched/fair.c

/* Update a sched_entity's runnable average */
static inline void update_entity_load_avg(struct sched_entity *se,
                                          int update_cfs_rq)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        long contrib_delta;
        u64 now;

        /*
         * For a group entity we need to use their owned cfs_rq_clock_task() in
         * case they are the parent of a throttled hierarchy.
         */
        if (entity_is_task(se))
                now = cfs_rq_clock_task(cfs_rq);
        else
                now = cfs_rq_clock_task(group_cfs_rq(se));

        if (!__update_entity_runnable_avg(now, &se->avg, se->on_rq))
                return;

        contrib_delta = __update_entity_load_avg_contrib(se);

        if (!update_cfs_rq)
                return;

        if (se->on_rq)
                cfs_rq->runnable_load_avg += contrib_delta;
        else
                subtract_blocked_load_contrib(cfs_rq, -contrib_delta);
}

엔티티 러너블 평균을 갱신한다.

  • 코드 라인 13~16에서 스케줄 엔티티가 태스크인 경우 now에 클럭 태스크 값을 대입하고 그렇지 않은 경우 스케줄 엔티티가 가리키는 cfs_rq의 클럭 태스크 값을 대입한다.
  • 코드 라인 18~19에서 엔티티 러너블 평균 갱신을 수행하고 실패한 경우 함수를 빠져나간다.
  • 코드 라인 21에서 엔티티 로드 평균 기여값을 갱신하고 그 delta 값을 controb_delta에 대입한다.
  • 코드 라인 23~24에서 인수 update_cfs_rq가 0인 경우 함수를 빠져나간다.
  • 코드 라인 26~29에서 스케줄 엔티티가 런큐에 있는 경우 러너블 로드 평균 값에 contrib_delta 값을 더하고 그렇지 않은 경우 blocked 로드 기여 값에 contrib_delta 값을 추가한다.

 

kernel/sched/fair.c

/* 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를 사용한다.

 

cfs_rq_clock_task()

kernel/sched/fair.c

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

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

스로틀 카운트가 있는 경우 cfs->throttled_clock_task를 반환하고 그렇지 않은 경우 cfs_rq->clock_task에서 스로틀 클럭 태스크 시간을 뺀 값을 반환한다.

 

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

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

 

update_rq_runnable_avg()

kernel/sched/fair.c

static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
{
        __update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
        __update_tg_runnable_avg(&rq->avg, &rq->cfs);
}

엔티티 러너블 평균과 태스크 그룹 러너블 평균을 산출한다.

 

__update_entity_runnable_avg()

kernel/sched/fair.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_entity_runnable_avg(u64 now,
                                                        struct sched_avg *sa,
                                                        int runnable)
{
        u64 delta, periods;
        u32 runnable_contrib;
        int delta_w, decayed = 0;

        delta = now - sa->last_runnable_update;
        /*
         * 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_runnable_update = 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_runnable_update = now;

엔티티 러너블 평균을 산출한다.

  • rq->runnable_avg_sum
    • 태스크가 런큐에 있거나 동작중 일때의 러너블 평균 합
    • runnable load.on_rq=1
  • rq->runnable_avg_period
    • 태스크의 동작 유무와 관련 없이 러너블 평균 기간

 

  • 코드 라인 37에서 현재 시각 now에서 마지막 러너블 업데이트 갱신 시각을 뺀 값을 delta에 대입한다.
  • 코드 라인 42~45에서 delta가 음수인 경우 시간이 거꾸로 되돌려 졌다고 판단하고 예외 케이스로 last_runnable_update를 갱신하고 함수를 빠져나온다.
    • 부트업 타임에 발생할 가능성이 있다.
  • 코드 라인 51~53에서 PELT(Per Entity Load Tracking)의 스케쥴링 시간 처리 최소 단위는 1024ns(1us)이다 따라서 delta를 최소 단위 us단위로 바꾸고 만일 1us도 안되는 경우 함수를 빠져나간다.
  • 코드 라인 54에서 last_runnable_update에 현재 시각(ns)을 기록한다.

 

        /* delta_w is the amount already accumulated against our next period */
        delta_w = sa->runnable_avg_period % 1024;
        if (delta + delta_w >= 1024) {
                /* period roll-over */
                decayed = 1;

                /*
                 * Now that we know we're crossing a period boundary, figure
                 * out how much from delta we need to complete the current
                 * period and accrue it.
                 */
                delta_w = 1024 - delta_w;
                if (runnable)
                        sa->runnable_avg_sum += delta_w;
                sa->runnable_avg_period += delta_w;

                delta -= delta_w;

                /* Figure out how many additional periods this update spans */
                periods = delta / 1024;
                delta %= 1024;

                sa->runnable_avg_sum = decay_load(sa->runnable_avg_sum,
                                                  periods + 1);
                sa->runnable_avg_period = decay_load(sa->runnable_avg_period,
                                                     periods + 1);

                /* Efficiently calculate \sum (1..n_period) 1024*y^i */
                runnable_contrib = __compute_runnable_contrib(periods);
                if (runnable)
                        sa->runnable_avg_sum += runnable_contrib;
                sa->runnable_avg_period += runnable_contrib;
        }

        /* Remainder of delta accrued against u_0` */
        if (runnable)
                sa->runnable_avg_sum += delta;
        sa->runnable_avg_period += delta;

        return decayed;
}

PELT(Per-Entity Load Tracking)에 사용되는 러너블 평균 합계(sa->runnable_avg_sum)와 러너블 평균 기간(sa->runnable_avg_period)을 갱신한다.

  • 코드 라인 2에서 기존 산출된 평균 기간 runnable_avg_period를 1024us(약 1ms) 단위로 잘라 남는 기간을 delta_w에 대입한다.
  • 코드 라인 3~5에서 delta와 delta_w 값이 1ms 이상인 경우 decay 처리 한다.
    • PELT에서 1 스케쥴링(1ms)이 지나면 과거 로드에 그 기간만큼 decay 요율을 곱해서 산출한다.
  • 코드 라인 12에서 1024(약 1ms) PELT 스케쥴링 단위에서 delta_w를 빼면 남은 기간(us)이 산출된다. 이를 다시 delta_w에 대입한다.
  • 코드 라인 13~15에서 sa->runnable_avg_sum 및 sa->runnable_avg_period에 delta_w 값을 추가하여 PELT 스케줄링 최소 단위로 정렬하게 한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.
  • 코드 라인 17에서 delta 값에서 방금 처리한 delta_w를 감소시킨다.
  • 코드 라인 20~21에서 delta에 몇 개의 1ms 단위가 있는지 그 횟수를 periods에 대입한다. 이 값은 decay 횟수로 사용된다. 그리고 delta 값도 나머지 값만 사용한다.
  • 코드 라인 23~24에서 sa->runnable_avg_sum에 periods+1 만큼의 decay 횟수를 적용하여 다시 갱신한다.
  • 코드 라인 25~26에서 sa->runnable_avg_period에 periods+1 만큼의 decay 횟수를 적용하여 다시 갱신한다.
  • 코드 라인 29~32에서 runnable_contrib를 산출하여 sa->runnable_avg_sum 및 runnable_avg_period에 더해 갱신한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.
  • 코드 라인 36~40에서 남은 delta를 sa->runnable_avg_sum 및 runnable_avg_period에 더해 갱신하고 decay 여부를 반환한다. 만일 인수 runnable이 0인 경우에는 sa->runnable_avg_sum은 갱신하지 않는다.

 

다음 그림은 갱신 기간이 1ms가 못되어 decay를 수행하지 않는 경우의 모습을 보여준다.

 

다음 그림은 갱신 기간이 1ms를 초과하여 decay를 수행하는 경우의 모습을 보여준다.

 

decay_load()

kernel/sched/fair.c

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

        if (!n)
                return val;
        else 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 *= runnable_avg_yN_inv[local_n];
        /* We don't use SRR here since we always want to round down. */
        return val >> 32;
}

n 스케줄링 기간으로 감소 비율을 산정하여 val 값에 곱하여 산출한다. n=0인 경우  1.0 요율이고, n=32인 경우 약 0.5에 가까운 요율을 가진다.

  • 코드 라인 9~10에서 n이 0인 경우 val 값을 그대로 사용하는 것으로 반환한다.
  • 코드 라인 11~12에서 n이 1356(32 * 63)을 초과하는 경우 너무 오래된 기간이므로 0을 반환한다.
  • 코드 라인 24~27에서 n이 32 이상인 경우 val 값을 n/32 만큼 시프트 하고 n 값은 32로 나눈 나머지를 사용한다.
  • 코드 라인 39~41에서 미리 계산해둔 테이블에서 n 인덱스에 해당하는 값을 val에 곱하고 32비트 우측 시프트하여 반환한다.

 

예) val=0x64, n=0~63일 때 산출되는 값들의 변화

  • ((val >> (n / 32)) * 테이블[n % 32]) >> 32

1 = (0x64 * 0xfa83b2da) >> 32 = 0x61
2 = (0x64 * 0xf5257d14) >> 32 = 0x5f

31 = (0x64 * 0x82cd8698) >> 32 = 0x33
32 = (0x32 * 0xffffffff) >> 32 = 0x31
33 = (0x32 * 0xfa83b2da) >> 32 = 0x30
34 = (0x32 * 0xf5257d14) >> 32 = 0x2f

63 = (0x32 * 0x82cd8698) >> 32 = 0x19

 

미리 만들어진 PELT용 decay factor

kernel/sched/fair.c

/*
 * We choose a half-life close to 1 scheduling period.
 * Note: The tables below are dependent on this value.
 */
#define LOAD_AVG_PERIOD 32
#define LOAD_AVG_MAX 47742 /* maximum possible load avg */
#define LOAD_AVG_MAX_N 345 /* number of full periods to produce LOAD_MAX_AVG */

/* Precomputed fixed inverse multiplies for multiplication by y^n */
static const u32 runnable_avg_yN_inv[] = {
        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,
};

runnable_avg_yN_inv[] 테이블은 다음 수식으로 만들어졌다.

수식: y^k x 2^32 단 y^32=0.5

 

/*
 * Precomputed \Sum y^k { 1<=k<=n }.  These are floor(true_value) to prevent
 * over-estimates when re-combining.
 */
static const u32 runnable_avg_yN_sum[] = {
            0, 1002, 1982, 2941, 3880, 4798, 5697, 6576, 7437, 8279, 9103,
         9909,10698,11470,12226,12966,13690,14398,15091,15769,16433,17082,
        17718,18340,18949,19545,20128,20698,21256,21802,22336,22859,23371,
};

runnable_avg_yN_sum[] 테이블은 다음 수식으로 만들어졌다. (예: n=30 (약 30ms))

수식: Sum(1024 * y^k) { 1<=k<=n }  y^32=0.5

  • y=약 0.978515625 (이를 us 단위로 표현하기 위해 1024를 곱하면 1002가 산출된다.)
  • sum(1024 * y^k) { 1<=k<=1 } =y^1=1002
  • sum(1024 * y^k) { 1<=k<=2 } =y^1 + y^2=1002 + 980=1,982
  • sum(1024 * y^k) { 1<=k<=3 } =y^1 + y^2 + y^3=1,002 + 980 + 959=2,941
  • sum(1024 * y^32)=y^1 + y^2 + y^3 + … + y^32=1,002 + 980 + 959 + … + 512=2,941

 

__compute_runnable_contrib()

kernel/sched/fair.c

/*
 * For updates fully spanning n periods, the contribution to runnable
 * average will be: \Sum 1024*y^n
 *
 * We can compute this reasonably efficiently by combining:
 *   y^PERIOD = 1/2 with precomputed \Sum 1024*y^n {for  n <PERIOD}
 */
static u32 __compute_runnable_contrib(u64 n)
{
        u32 contrib = 0;

        if (likely(n <= LOAD_AVG_PERIOD))
                return runnable_avg_yN_sum[n];
        else if (unlikely(n >= LOAD_AVG_MAX_N))
                return LOAD_AVG_MAX;

        /* Compute \Sum k^n combining precomputed values for k^i, \Sum k^j */
        do {
                contrib /= 2; /* y^LOAD_AVG_PERIOD = 1/2 */
                contrib += runnable_avg_yN_sum[LOAD_AVG_PERIOD];

                n -= LOAD_AVG_PERIOD;
        } while (n > LOAD_AVG_PERIOD);

        contrib = decay_load(contrib, n);
        return contrib + runnable_avg_yN_sum[n];
}

인수로 받은 1ms 단위 기간의 수 n 만큼 러너블 평균에 기여할 누적값을 산출하여 반환한다.

  • y^32=0.5일 때, 1024 * sum(y^n)에 대한 결과 값을 산출하되 미리 계산된 테이블을 이용한다.
  • 스케쥴링 기간 n은 ms 단위이며 결과는 us단위로 반환된다.
  • 343ms 이상은 최대 47742us 값을 반환한다.

 

  • 코드 라인 12~13에서 n이 32 이하인 경우 미리 계산된 테이블을 사용하여 곧바로 결과 값을 반환한다.
    • 예) n=2 -> 1982
  • 코드 라인 14~15에서 n이 LOAD_AVG_MAX_N(345) 이상인 경우 최대치인 47742를 반환한다.
  • 코드 라인 18~20에서 루프를 돌 때마다 contrib를 절반으로 감소시키며 contrib에 최대치인 테이블 최대치인 23371을 더한다.
  • 코드 라인 22~23에서 LOAD_AVG_PERIOD(32) 만큼씩 n을 줄이며 32를 초과하는 경우 계속 루프를 돈다.
  • 코드 라인 25~26에서 마지막으로 contrib를 가지고 n 만큼 decay한 후 n 번째 테이블 값을 더해 반환한다.

 

다음과 같이 다양한 조건에서 결과값을 알아본다.

  • n=0
    • =runnable_avg_yN_sum[0] =0
  • n=1
    • =runnable_avg_yN_sum[1] =1002
  • n=2
    • =runnable_avg_yN_sum[2] =1982
  • n=10
    • =runnable_avg_yN_sum[10] =9103
  • n=32
    • =runnable_avg_yN_sum[32] =23371
  • n=33
    • =decay_load(23371, 1) + runnable_avg_yN_sum[1] = 22870 + 1002 = 23872
  • n=100
    • = decay_load(23371 + 23371/2 + 23371/4, 4) + runnable_avg_yN_sum[4] = decay_load(40898, 4) +  3880 = 37503 + 3880 = 41383
  • n=343
    • =decay_load(23371 + 23371/2, 23371/4, 23371/8 + 23371/16 + 23371/32, + 23371/64 + 23371/128 + 23371/256 + 23371/512, 23) + runnable_avg_yN_sum[23] = decay_load(23371 + 11685 + 5842 + 2921 + 1460 + 730 + 365 + 182 + 91 + 45, 4) + 3880 = decay_load(46692, 23) + 18340 = 28371 + 18340 = 46711
  • n >= 344
    • =47742 (max)

 

스케줄링 엔티티 로드 평균 기여 갱신

__update_entity_load_avg_contrib()

kernel/sched/fair.c

/* Compute the current contribution to load_avg by se, return any delta */
static long __update_entity_load_avg_contrib(struct sched_entity *se)
{
        long old_contrib = se->avg.load_avg_contrib;

        if (entity_is_task(se)) {
                __update_task_entity_contrib(se);
        } else {
                __update_tg_runnable_avg(&se->avg, group_cfs_rq(se));
                __update_group_entity_contrib(se);
        }

        return se->avg.load_avg_contrib - old_contrib;
}

스케줄링 엔티티의 로드 평균 기여값을 갱신하고 그 변화값을 반환한다.

  • 코드 라인 4에서 스케줄링 엔티티의 로드 평균 기여 값을 old_contrib에 보관해둔다.
  • 코드 라인 6~7에서 태스크용 스케줄 엔티티인 경우 스케줄 엔티티의 로드 평균 기여값을 갱신한다.
  • 코드 라인 8~11에서 태스크 그룹용 스케줄 엔티티인 경우 스케줄 엔티티의 태스크 그룹용 로드 평균 기여값을 갱신한다.
  • 코드 라인 13에서 스케줄링 엔티티의 로드 평균 기여 값의 변화값을 반환한다.

 

__update_task_entity_contrib()

kernel/sched/fair.c

static inline void __update_task_entity_contrib(struct sched_entity *se)
{
        u32 contrib;

        /* avoid overflowing a 32-bit type w/ SCHED_LOAD_SCALE */
        contrib = se->avg.runnable_avg_sum * scale_load_down(se->load.weight);
        contrib /= (se->avg.runnable_avg_period + 1);
        se->avg.load_avg_contrib = scale_load(contrib);
}

태스크용 스케줄 엔티티의 로드 평균 기여값을 다음과 같이 산출한다.

  • avg.load_avg_contrib = load.weight * avg.runnable_avg_sum / (avg.runnable_avg_period + 1)

 

다음 그림은 위의 태스크용 스케줄 엔티티의 로드 평균 기여값 산출 과정을 보여준다.

 

__update_tg_runnable_avg()

kernel/sched/fair.c

/*
 * Aggregate cfs_rq runnable averages into an equivalent task_group
 * representation for computing load contributions.
 */
static inline void __update_tg_runnable_avg(struct sched_avg *sa,
                                                  struct cfs_rq *cfs_rq)
{
        struct task_group *tg = cfs_rq->tg;
        long contrib;

        /* The fraction of a cpu used by this cfs_rq */
        contrib = div_u64((u64)sa->runnable_avg_sum << NICE_0_SHIFT,
                          sa->runnable_avg_period + 1);
        contrib -= cfs_rq->tg_runnable_contrib;

        if (abs(contrib) > cfs_rq->tg_runnable_contrib / 64) {
                atomic_add(contrib, &tg->runnable_avg);
                cfs_rq->tg_runnable_contrib += contrib;
        }
}

태스크 그룹용 스케줄 엔티티의 러너블 평균 기여값을 다음과 같이 산출한다. 단 기존 기여도보다 산출된 값의 절대값이 64배를 초과하는 경우에만 갱신한다.

  • cont = sa->runnable_avg_sum * 1024 / (sa->runnable_avg_period + 1) – cfs_rq->tg_runnable_contrib
  • tg->runnable_avg = cont
  • cfs_rq->tg_runnable_contrib += cont

 

 

__update_group_entity_contrib()

kernel/sched/fair.c

static inline void __update_group_entity_contrib(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = group_cfs_rq(se);
        struct task_group *tg = cfs_rq->tg;
        int runnable_avg;

        u64 contrib;

        contrib = cfs_rq->tg_load_contrib * tg->shares;
        se->avg.load_avg_contrib = div_u64(contrib,
                                     atomic_long_read(&tg->load_avg) + 1);

        /*
         * For group entities we need to compute a correction term in the case
         * that they are consuming <1 cpu so that we would contribute the same
         * load as a task of equal weight.
         *
         * Explicitly co-ordinating this measurement would be expensive, but
         * fortunately the sum of each cpus contribution forms a usable
         * lower-bound on the true value.
         *
         * Consider the aggregate of 2 contributions.  Either they are disjoint
         * (and the sum represents true value) or they are disjoint and we are
         * understating by the aggregate of their overlap.
         *
         * Extending this to N cpus, for a given overlap, the maximum amount we
         * understand is then n_i(n_i+1)/2 * w_i where n_i is the number of
         * cpus that overlap for this interval and w_i is the interval width.
         *
         * On a small machine; the first term is well-bounded which bounds the
         * total error since w_i is a subset of the period.  Whereas on a
         * larger machine, while this first term can be larger, if w_i is the
         * of consequential size guaranteed to see n_i*w_i quickly converge to
         * our upper bound of 1-cpu.
         */
        runnable_avg = atomic_read(&tg->runnable_avg);
        if (runnable_avg < NICE_0_LOAD) {
                se->avg.load_avg_contrib *= runnable_avg;
                se->avg.load_avg_contrib >>= NICE_0_SHIFT;
        }
}

태스크 그룹용 스케줄 엔티티의 로드 평균 기여값을 갱신한다.

  • 코드 라인 9~11에서 태스크 그룹용 로드 기여값과 shares를 곱하고 태스크 그룹용 로드 평균+1로 나눈 값을 se->avg.load_avg_contrib에 대입한다.
  • 코드 라인 36~40에서 태스크 그룹의 러너블 평균이 nice-0 weight 값인 1024보다 작은 경우에 한해 이 값을 nice-0 weight에 대한 비율로 바꾼 후 위에서 산출한 값을 곱하여 갱신한다.
    • se->avg.load_avg_contrib *= runnable_avg / 1024

 

다음 그림은 태스크 그룹용 스케줄 엔티티의 로드 평균 기여값을 산출하는 수식이다.

 

update_cfs_rq_blocked_load()

kernel/sched/fair.c

/*
 * Decay the load contributed by all blocked children and account this so that
 * their contribution may appropriately discounted when they wake up.
 */
static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq, int force_update)
{                                             
        u64 now = cfs_rq_clock_task(cfs_rq) >> 20;
        u64 decays;

        decays = now - cfs_rq->last_decay;
        if (!decays && !force_update)
                return;

        if (atomic_long_read(&cfs_rq->removed_load)) {
                unsigned long removed_load;
                removed_load = atomic_long_xchg(&cfs_rq->removed_load, 0);
                subtract_blocked_load_contrib(cfs_rq, removed_load);
        }

        if (decays) {
                cfs_rq->blocked_load_avg = decay_load(cfs_rq->blocked_load_avg,
                                                      decays);
                atomic64_add(decays, &cfs_rq->decay_counter);
                cfs_rq->last_decay = now;
        }

        __update_cfs_rq_tg_load_contrib(cfs_rq, force_update);
}

blocked 로드 평균을 업데이트한다.

  • 코드 라인 7에서 현재 클럭 태스크의 시각을 ms 단위로 변환하여 now에 대입한다.
  • 코드 라인 10~12에서 now와 최종 decay 시각과의 차이를 decays에 대입한다. 만일 decays가 0이고 force_update 요청이 없는 경우 함수를 빠져나간다.
  • 코드 라인 14~18에서 removed_load가 있는 경우 0으로 대입하고 기존 값을 blocked 로드 평균에서 감소시킨다.
  • 코드 라인 20~25에서 decays 기간이 있는 경우 blocked_load_avg 값을 decays 만큼 decay 시킨 후 decay_counter에 decays를 추가하고 현재 갱신 시각 now를 last_decay에 저장한다.
  • 코드 라인 27에서 태스크 그룹용 로드 평균 기여를 갱신한다.

 

subtract_blocked_load_contrib()

kernel/sched/fair.c

static inline void subtract_blocked_load_contrib(struct cfs_rq *cfs_rq,
                                                 long load_contrib)
{
        if (likely(load_contrib < cfs_rq->blocked_load_avg))
                cfs_rq->blocked_load_avg -= load_contrib;
        else
                cfs_rq->blocked_load_avg = 0;
}

blocked 로드 평균에서 요청한 로드 기여값을 감소시킨다. 만일 0보다 작아지는 경우 0을 대입한다.

 

__update_cfs_rq_tg_load_contrib()

kernel/sched/fair.c

static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
                                                 int force_update)
{
        struct task_group *tg = cfs_rq->tg;
        long tg_contrib;

        tg_contrib = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg;
        tg_contrib -= cfs_rq->tg_load_contrib;

        if (!tg_contrib)
                return;

        if (force_update || abs(tg_contrib) > cfs_rq->tg_load_contrib / 8) {
                atomic_long_add(tg_contrib, &tg->load_avg);
                cfs_rq->tg_load_contrib += tg_contrib;
        }
}

태스크 그룹용 로드 평균 기여를 갱신한다.

  • tmp = cfs_rq->runnable_load_avg + cfs_rq->blocked_load_avg – cfs_rq->tg_load_contrib
    • cfs_rq->tg_load_contrib = tmp
    • tg->load_avg = tmp

 

다음 그림은 태스크 그룹용 스케줄 엔티티의 로드 평균과 로드 기여값을 갱신하는 모습을 보여준다.

 

구조체

sched_avg 구조체

include/linux/sched.h

struct sched_avg {
        /*
         * These sums represent an infinite geometric series and so are bound
         * above by 1024/(1-y).  Thus we only need a u32 to store them for all
         * choices of y < 1-2^(-32)*1024.
         */
        u32 runnable_avg_sum, runnable_avg_period;
        u64 last_runnable_update;
        s64 decay_count;
        unsigned long load_avg_contrib;
};
  • runnable_avg_sum
    • 러너블 로드라 불리며 러닝 타임 평균을 합하였다.
  • runnable_avg_period
    • Idle 타임을 포함한 전체 시간 평균을 합하였다.
  • last_runnable_update
    • 러너블 로드를 갱신한 마지막 시각
  • decay_count
    • 트래킹 migration에 사용하는 엔티티 decay 카운터
  • load_avg_contrib
    • 평균 로드 기여(weight * runnable_avg_sum / (runnable_avg_period+1))

 

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
        atomic_long_t load_avg;
        atomic_t runnable_avg;
#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;
};
  • css
    • cgroup 서브시스템 상태
    • rcu
    • list
    • *parent
      • 부모 태스크 그룹
    • siblings
      • 현재 태스크들
    • children
      • 자식 태스크 그룹
    • cfs_bandwidth
  • cfs 그룹 스케줄링 관련
    • **se
      • 태스크 그룹에 연결된 스케줄러블 엔티티들
    • **cfs_rq
      • 각 cpu에서 이 그룹이 소유하는 런큐
    • shares
    • load_avg
    • runnable_avg
  • rt 그룹 스케줄링 관련
    • **rt_se
    • **rt_rq
    • rt_bandwidth
  • autogroup 관련
    • *autogroup

 

참고

 

답글 남기기

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