Scheduler -5- (Core)

<kernel v5.4>

스케줄러 코어

스케줄러 코어와 각각의 스케줄러들은 다음과 같이 구성되어 있다.

 

스케줄러 Operations

스케줄러 코어는 여러 개의 스케줄러들과 연동되어 사용하는데, 직접 각 스케줄러의 함수를 호출하지 않고, 다음 sched_class 구조체를 통해 현재 5가지의 스케줄러와 인터페이스하여 사용하고 있다.

 

각 스케줄러의 operation을 담당하는 후크 함수들은 다음과 같이 구성되어 있다.

 

sched_class 구조체

kernel/sched/sched.h

struct sched_class {
        const struct sched_class *next;

#ifdef CONFIG_UCLAMP_TASK
        int uclamp_enabled;
#endif

        void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
        void (*yield_task)   (struct rq *rq);
        bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);

        void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

        /*
         * Both @prev and @rf are optional and may be NULL, in which case the
         * caller must already have invoked put_prev_task(rq, prev, rf).
         *
         * Otherwise it is the responsibility of the pick_next_task() to call
         * put_prev_task() on the @prev task or something equivalent, IFF it
         * returns a next task.
         *
         * In that case (@rf != NULL) it may return RETRY_TASK when it finds a
         * higher prio class has runnable tasks.
         */
        struct task_struct * (*pick_next_task)(struct rq *rq,
                                               struct task_struct *prev,
                                               struct rq_flags *rf);
        void (*put_prev_task)(struct rq *rq, struct task_struct *p);
        void (*set_next_task)(struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
        int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);
        int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
        void (*migrate_task_rq)(struct task_struct *p, int new_cpu);

        void (*task_woken)(struct rq *this_rq, struct task_struct *task);

        void (*set_cpus_allowed)(struct task_struct *p,
                                 const struct cpumask *newmask);

        void (*rq_online)(struct rq *rq);
        void (*rq_offline)(struct rq *rq);
#endif

        void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
        void (*task_fork)(struct task_struct *p);
        void (*task_dead)(struct task_struct *p);

        /*
         * The switched_from() call is allowed to drop rq->lock, therefore we
         * cannot assume the switched_from/switched_to pair is serliazed by
         * rq->lock. They are however serialized by p->pi_lock.
         */
        void (*switched_from)(struct rq *this_rq, struct task_struct *task);
        void (*switched_to)  (struct rq *this_rq, struct task_struct *task);
        void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
                              int oldprio);

        unsigned int (*get_rr_interval)(struct rq *rq,
                                        struct task_struct *task);

        void (*update_curr)(struct rq *rq);

#define TASK_SET_GROUP          0
#define TASK_MOVE_GROUP         1

#ifdef CONFIG_FAIR_GROUP_SCHED
        void (*task_change_group)(struct task_struct *p, int type);
#endif
};
  • (*next)
    • 현재 스케줄러에서 더 이상 진행할 수 없을 때, 다음으로 진행할 스케줄링 클래스를 지정한다.
      • 각각의 스케줄러들은 다음 순서대로 지정된다.
        • stop -> deadline -> rt -> cfs -> stop
  • uclamp_enabled
    • uclamp min, max 사용 여부를 지정한다.
  •  (*enqueue_task)
    • 태스크가 실행 가능한(러너블) 상태가 되어 스케줄러가 관리하는 런큐에 엔큐할 때 호출된다.
  • (*dequeue_task)
    • 태스크가 실행 가능하지 않은 상태가 되어 스케줄러가 관리하는 런큐로부터 디큐할 때 호출된다.
  • (*yield_task)
    • yield() 함수를 실행하여 현재 태스크를 스케줄 아웃하고, 다음 태스크에 양보할 때 호출된다.
  • (*yield_to_task)
    • 이 스케줄러의 지정한 태스크로 양보할 때 호출된다.
  • (*check_preempt_curr)
    • 이 스케줄러의 현재 동작 중인 태스크를 선점할 수 있는지 체크하여 선점 필요 시 리스케줄링 요청 표식을 한다.
  • (*pick_next_task)
    • 해당 스케줄러의 내부 자료 구조로부터 실행할 다음 태스크를 선택할 때 호출된다.
  • (*put_prev_task)
    • 실행중인 태스크를 다시 해당 스케줄러의 내부 자료 구조에 넣을 때 호출된다.
  • (*set_next_task)
    • 태스크의 스케줄링 클래스나 태스크 그룹을 바꿀때 호출된다.
  • (*balance)
    • 로드 밸런싱 필요 여부를 확인하기 위해 호출된다.
    • 현재 스케줄러를 포함하여 상위 스케줄러에서 동작 중인 태스크가 있는 경우 1을 반환한다.
  • (*select_task_rq)
    • 태스크가 실행될 cpu의 런큐를 선택할 때 호출된다.
  • (*migrate_task_rq)
    • 태스크를 마이그레이션 할 때 호출된다.
  • (*task_woken)
    • 태스크가 깨어날 때 사용할 cpu의 런큐를 지정할 때 호출된다.
  • (*set_cpus_allowed)
    • 태스크에 사용될 cpu 마스크를 지정할 때 호출된다.
  • (*rq_online)
    • 런큐를 온라인 상태로 변경할 때 호출된다.
  • (*rq_offline)
    • 런큐를 오프라인 상태로 변경할 떄 호출된다.
  • (*task_tick)
    • 스케줄 틱이 발생될 때 호출된다.
      • hrtick이 사용될 때 queued=1로 호출된다.
      • 일반 고정 스케줄틱이 사용될 때 queued=0으로 호출된다.
  • (*task_fork)
    • fork한 태스크를 스케줄러가 관리하는 런큐에 엔큐할 떄 호출된다.
  • (*task_dead)
    • 지정한 태스크를 dead 처리하기 위해 런큐에서 디큐할 때 호출된다.
  • (*switched_from)
    • 스케줄러 스위칭 전에 기존 실행 중인 스케줄러에서 동작했었던 태스크를 detach할 때 호출된다.
  • (*switched_to)
    • 스케줄러 스위칭 후에 새로 실행 할 스케줄러에 태스크를 attach할 때 호출된다.
  • (*prio_changed)
    • 태스크의 우선 순위를 변경할 때 호출된다.
  • (*get_rr_interval)
    • 라운드 로빈 인터벌 타임 값을 알아올 때 호출된다.
  • (*update_curr)
    • 현재 실행 중인 태스크의 런타임을 갱신할 때 호출된다.
  • (*task_change_group)
    • 태스크의 태스크 그룹(cgroup)을 변경할 때 호출된다.
      • type이 0일 때 태스크 그룹을 설정한다.
      • type이 1일 때 태스크 그룹을 이동한다.

 


우선 순위

우선 순위는 다음과 같은 값들을 사용하며, 숫자의 크기와 우선 순위가 각각 다름에 주의해야 한다.

  • NICE
    • -20(highest) ~ 19(lowest)까지 cfs 태스크에서 사용한다.
  • PRIORITY (유저 우선 순위)
    • 0(lowest) ~ 139(highest)까지 rt 및 cfs 태스크에서 사용한다.
  • RT PRIORITY (유저 rt 우선 순위)
    • 1(lowest) ~ 99(highest)까지 rt 태스크에서 사용한다.
    • 다음에서 사용한다.
      • p->rt_priority
  • 커널 우선 순위
    • 0(highest) ~ 139(lowest)까지 rt 및 cfs 태스크에서 사용한다.
    • 다음에서 사용한다.
      • p->static_prio
      • p->normal_prio
      • p->prio

 

 

다음 ps 툴에서 보여주는 값을 확인한다.

  • PRI
    • = 139 – p->prio
  • RTPRIO
    • = p->rt_priority
    • = 99 – p->normal_prio
$ ps -e -o cmd,ni, pri,rtprio
CMD                         NI  PRI RTPRIO
/sbin/init                   0   19      -
[kthreadd]                   0   19      -
[ksoftirqd/0]                0   19      -
[kworker/0:0H]             -20   39      -
[rcu_sched]                  0   19      -
[rcu_bh]                     0   19      -
[migration/0]                -  139     99   <- p->prio = 0(highest)
[watchdog/0]                 -  139     99
[cfinteractive]              -  139     99
[rpciod]                   -20   39      -
[kvm_arch_timer]           -20   39      -
[kvm-irqfd-clean]          -20   39      -
[kswapd0]                    0   19      -
[vmstat]                   -20   39      -
[irq/230-rockchi]            -   90     50
[vcodec]                   -20   39      -
[bioset]                   -20  39      -
[nvme]                     -20  39      -
[spi32766]                   0  19      -
[fusb302_wq]               -20  39      -
[irq/26-mmc1]                -  90     50
[mmcqd/1]                    -  41      1
/lib/systemd/systemd-udevd   0  19      -
-bash                        0  19      -
./load0                    -20  39      -   
./load100                  +19   0      -   <- p->prio = 139(lowest)

 

NICE 우선 순위 변경

다음과 같이 3가지 구성에 대해 nice 우선 순위를 변경할 수 있다.

  • 태스크(process)
  • 태스크 그룹(process group)
  • 유저

 

renice

다음은 renice 유틸리티의 사용방법이다.

$ renice

Usage:
 renice [-n] <priority> [-p|--pid] <pid>...
 renice [-n] <priority>  -g|--pgrp <pgid>...
 renice [-n] <priority>  -u|--user <user>...

Alter the priority of running processes.

Options:
 -n, --priority <num>   specify the nice increment value
 -p, --pid <id>         interpret argument as process ID (default)
 -g, --pgrp <id>        interpret argument as process group ID
 -u, --user <name>|<id> interpret argument as username or user ID

 -h, --help     display this help and exit
 -V, --version  output version information and exit

For more details see renice(1).

 

다음 그림은 NICE 우선 순위를 변경할 때의 함수 호출 관계를 보여준다.

 

우선 순위 관리

다음과 같이 태스크에는 우선 순위 관련하여 4개의 멤버 변수로 관리한다. RT 태스크의 경우 러닝 중에 PI(Priority Inversion) Problem을 회피하기 위해 PI 태스크의 우선 순위만큼 부스트하여 우선 순위가 상승하였다가 다시 돌아온다. 이렇게 운영 중에 우선 순위가 변할 수 있으므로 상속되는 태스크에 부스트된 우선 순위를 상속하지 않게 하기 위해 p->normal_prio를 사용하여 관리한다. 일반 cfs 태스크로만 운영하는 경우 아래의 p->static_prio, p->prio 및 p->normal_prio는 동일한 값을 유지한다.

 p->static_prio
  • 유저가 nice 값을 사용하여 cfs 태스크에 static하게 지정한 커널 우선 순위이다.
    • cfs 태스크: 100~139
  • 지정 전의 태스크들은 부모 태스크로부터 상속된다.
    • 참고로 kthread_create_worker() API를 사용하여 만드는 태스크들(dl, rt, cfs)은 디폴트 값으로 nice 0를 사용하는 cfs 스케줄러를 사용하는 kthreadd(pid=2)를 통해 만들어진다. 따라서 nice 0에 대응하는 priority 120 값을 상속받는다.
p->prio
  • 현재 운영되는 커널 우선 순위로 rt 및 cfs 태스크를 위해 0~139까지 사용된다.
  • rt 태스크의 경우 PI boost로 인해 러닝 중에 커널 우선 순위가 상승할 수도 있다.
  • fork 된 태스크는 부모 태스크로부터 우선 순위를 상속받지만, RT 태스크의 경우엔 부스트된 부모 태스크의 우선 순위를 상속 받지 않기 위해 부모 태스크의 normal_prio 값을 상속받는다.
p->normal_prio
  • 커널 우선 순위이다.
    • deadline 태스크의 경우 -1
    • rt 태스크의 경우 0~99
    • cfs 태스크의 경우 100~139
  • 처음 부모 태스크로부터 상속된다.
  • 부스트된 우선 순위가 아닌 원래 설정된 priority로 되돌아올 때 사용할 우선 순위로 시스템이 운영 중 스스로 값을 바꾸지 않는다.
  • rt -> cfs 스케줄러로 변경되는 경우 cfs 태스크에서 사용하는 p->static_prio 값을 가져와 사용한다. (디폴트: 120)
  • cfs -> rt 스케줄러로 변경하는 경우 아래 p->rt_priority 값도 전달받는다. 이 값을 변환(99 – p->rt_priority)하여 사용한다.
p->rt_priority
  • 유저가 rt 태스크에 static하게 지정한 rt 유저 우선 순위이다.
  • rt 유저 우선 순위 1~99 값은 커널 우선 순위와 다르게 숫자가 높을 수록 우선 순위가 높아지도록 사용된다.
  • 유저가 chrt 유틸리티 등으로 지정한 유저 rt 우선 순위 값은 sched_setscheduler() syscall 이후 커널의 sys_sched_setscheduler() 함수를 통해 p->rt_priority에 그 값 그대로 설정되고, p->normal_prio에는 98 ~ 0 값으로 변환되어 사용된다.

 

CFS 태스크의 우선 순위 변경

유저가 nice 및 renice 유틸리티 등으로 지정한 nice 값을 setpriority() syscall 이후 커널의 set_user_nice() 함수를 통해 cfs 태스크의 중간 우선 순위 값인 120을 더해 p->static_prio에 저장한다.

  • -20 ~ 19 범위의 nice 우선 순위는 커널 우선 순위 100 ~ 139로 변경하여 다음 멤버 변수에 저장한다.
    • p->static_prio
    • p->normal_prio
    • p->prio

 

다음은 태스크 하나의 우선 순위를 변경하는 예를 보여준다.

$ ps
  PID TTY          TIME CMD
11636 pts/1    00:00:00 bash
11675 pts/1    00:40:25 load100
11740 pts/1    00:00:00 ps
$ renice -n -2 -p 11675
11675 (process ID) old priority 0, new priority -2

 

다음은 유저에 해당하는 모든 태스크의 우선 순위를 변경하는 예를 보여준다.

$ who
root     ttyFIQ0      2020-08-24 14:39
linaro   tty7         2020-08-24 14:39 (:0)
jake     pts/0        2020-09-14 10:31 (172.17.1.111)

$ renice -n -3 -u jake
1000 (user ID) old priority 0, new priority -3

 

RT 태스크의 우선 순위 변경

rt 태스크의 경우 cfs 태스크 처럼 nice나 renice 툴로 간단히 우선 순위를 바꾸는 경로를 사용하지 않고, 스케줄러를 지정하는 sched_setscheduler() API를 통해 우선 순위도 바꿀 수 있다.

유저가 chrt 유틸리티로 지정한 rt 유저 우선 순위 값(1~99)을 sched_setscheduler() syscall 이후 커널의 sched_setscheduler() 함수를 통해 다음의 멤버 변수에 설정한다.

  • p->rt_priority
    • 전달 받은 값 그대로 설정한다.
  • p->normal_prio
    • 전달 받은 값을 변환(99 – p->rt_priority)하여 설정한다.
  • p->prio
    • 전달 받은 값을 변환(99 – p->rt_priority)하여 설정한다.

 

다음은 rt 태스크의 우선 순위를 변경하는 방법을 보여준다.

$ chrt
Show or change the real-time scheduling attributes of a process.

Set policy:
 chrt [options] <priority> <command> [<arg>...]
 chrt [options] --pid <priority> <pid>

Get policy:
 chrt [options] -p <pid>

Policy options:
 -b, --batch          set policy to SCHED_BATCH
 -d, --deadline       set policy to SCHED_DEADLINE
 -f, --fifo           set policy to SCHED_FIFO
 -i, --idle           set policy to SCHED_IDLE
 -o, --other          set policy to SCHED_OTHER
 -r, --rr             set policy to SCHED_RR (default)

Scheduling options:
 -R, --reset-on-fork       set SCHED_RESET_ON_FORK for FIFO or RR
 -T, --sched-runtime <ns>  runtime parameter for DEADLINE
 -P, --sched-period <ns>   period parameter for DEADLINE
 -D, --sched-deadline <ns> deadline parameter for DEADLINE

Other options:
 -a, --all-tasks      operate on all the tasks (threads) for a given pid
 -m, --max            show min and max valid priorities
 -p, --pid            operate on existing given pid
 -v, --verbose        display status information

 -h, --help     display this help and exit
 -V, --version  output version information and exit

For more details see chrt(1).

$ ps -e -o pid,cmd,nice,pri,rtprio | grep watchdog
   10 [watchdog/0]                  - 139     99
   11 [watchdog/1]                  - 139     99
   16 [watchdog/2]                  - 139     99
   21 [watchdog/3]                  - 139     99
   26 [watchdog/4]                  - 139     99
   31 [watchdog/5]                  - 139     99
  184 [dhd_watchdog_th]             0  19      -
 1799 grep watchdog                 0  19      -

$ chrt -f --pid 98 11            <- 유저 rt 우선 순위를 99에서 98로 1단계 내림

$ ps -e -o pid,cmd,nice,pri,rtprio | grep watchdog
   10 [watchdog/0]                  - 139     99
   11 [watchdog/1]                  - 138     98
   16 [watchdog/2]                  - 139     99
   21 [watchdog/3]                  - 139     99
   26 [watchdog/4]                  - 139     99
   31 [watchdog/5]                  - 139     99
  184 [dhd_watchdog_th]             0  19      -
 1803 grep watchdog                 0  19      -

 

다음 그림은 policy 및 rt 유저 우선 순위를 지정하여 스케줄러 속성을 지정하는 과정을 보여준다. 이 과정에서 rt 태스크의 우선 순위를 변경할 수 있다.

 

RT 스레드 생성 및 우선 순위 지정

다음 코드 예는 SCHED_FIFO policy와 유저 rt 우선 순위 99(highest)로 RT 스레드를 생성하는 예를 보여준다.

static struct kthread_worker *foo_kworker;

int foo_thread_init(void)
{
        int err;
        struct sched_param param = { .sched_priority = MAX_RT_PRIO - 1,};

        foo_kworker = kthread_create_worker(0, "foo");
        if (IS_ERR(foo_kworker)) {
                pr_err("Failed to create foo kworker\n");
                return PTR_ERR(foo_kworker);
        }
        sched_setscheduler(foo_kworker->task, SCHED_FIFO, &param);
}

 


UCLAMP

특정 프로세스의 유틸 로드 평균을 uclamp min ~ max 범위내에서만 산출되도록 제한한다. 즉 실제보다 더 크게 하거나 작게 제한할 수 있다.

 


스케줄 틱

다음과 같이 커널에서 사용하는 두 개의 틱의 호출 과정을 알아본다.

  • 정규 스케줄 틱
  • HR 틱

 

정규 스케줄 틱

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);
        calc_global_load_tick(rq);
        psi_task_tick(rq);

        rq_unlock(rq, &rf);

        perf_event_task_tick();

#ifdef CONFIG_SMP
        rq->idle_balance = idle_cpu(cpu);
        trigger_load_balance(rq);
#endif
}

스케줄 틱마다 런타임 처리 및 로드 평균 산출 등의 처리를 수행하고, 로드 밸런스 주기가 된 경우 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()
  • 코드 라인 14에서 글로벌 로드를 갱신한다.
  • 코드 라인 15에서 psi 요청 태스크가 등록된 psi 그룹의 stat 을 매 틱마다 갱신한다.
  • 코드 라인 17에서 런큐 락을 해제한다.
  • 코드 라인 22에서 현재 cpu의 런큐가 idle 상태인지 확인하여 rq->idle_balance에 대입한다.
  • 코드 라인 23에서 매 틱마다 로드 밸런스를 할 타이밍인지 체크하여 수행하게 한다.

 

hrtick 호출

hrtick()

kernel/sched/core.c

/*
 * High-resolution timer tick.
 * Runs from hardirq context with interrupts disabled.
 */
static enum hrtimer_restart hrtick(struct hrtimer *timer)
{
        struct rq *rq = container_of(timer, struct rq, hrtick_timer);

        WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());

        raw_spin_lock(&rq->lock);
        update_rq_clock(rq);
        rq->curr->sched_class->task_tick(rq, rq->curr, 1);
        raw_spin_unlock(&rq->lock);

        return HRTIMER_NORESTART;
}

런큐 클럭을 갱신하고 현재 태스크에 동작 중인 스케줄러의 (*task_tick) 후크 함수를 호출한다.

  • 각각의 스케줄러에서 사용되는 함수는 다음과 같다.
    • task_tick_rt()
    • task_tick_dl()
    • task_tick_fair()
    • task_tick_idle()
    • task_tick_stop()

 

hrtick 만료 시각 설정

hrtick_start()

kernel/sched/core.c

/*
 * Called to set the hrtick timer state.
 *              
 * called with rq->lock held and irqs disabled
 */
void hrtick_start(struct rq *rq, u64 delay)
{
        struct hrtimer *timer = &rq->hrtick_timer;
        ktime_t time;
        s64 delta;

        /*
         * Don't schedule slices shorter than 10000ns, that just
         * doesn't make sense and can cause timer DoS.
         */
        delta = max_t(s64, delay, 10000LL);
        time = ktime_add_ns(timer->base->get_time(), delta);

        hrtimer_set_expires(timer, time);

        if (rq == this_rq()) {
                __hrtick_restart(rq);
        } else if (!rq->hrtick_csd_pending) {
                smp_call_function_single_async(cpu_of(rq), &rq->hrtick_csd);
                rq->hrtick_csd_pending = 1;
        }
}

delta 만료 시간으로 런큐의 hrtick 타이머를 가동시킨다. 런큐가 현재 cpu인 경우 hrtimer를 곧바로 설정하고 그렇지 않은 경우 IPI call을 통해 hrtick에 대한 hrtimer를 설정한다.

  • 코드 라인 11~12에서 요청한 delta 값이 10000ns(10us) 보다 작지 않도록 교정하고 현재 시각에 더해 만료 시각 time을 산출한다.
  • 코드 라인 14에서 hrtimer에 만료 시각 time을 설정한다.
  • 코드 라인 16~17에서 요청 런큐가 현재 cpu에서 동작중인 경우 곧바로 hrtick에 대한 hrtimer를 가동시킨다.
    • 만료 시간이 되면 init_rq_hrtick()에서 초기화 설정해둔 hrtick() 함수가 호출된다.
  • 코드 라인 18~21에서 런큐에서 hrtick_csd_pending 상태가 아니면 hrtick에 대한 IPI 호출을 수행하고 런큐의 hrtick_csd_pending을 1로 설정한다.
    • init_rq_hrtick()에서 초기화 설정해둔 __hrtick_start() 함수가 IPI 호출 시 동작된다.

 

hrtick IPI 호출

__hrtick_start()

kernel/sched/core.c

/*
 * called from hardirq (IPI) context
 */
static void __hrtick_start(void *arg)
{
        struct rq *rq = arg;

        raw_spin_lock(&rq->lock);
        __hrtick_restart(rq);
        rq->hrtick_csd_pending = 0;
        raw_spin_unlock(&rq->lock);
}

다른 cpu로부터 IPI 호출을 받아 동작되는 이 함수에서는 런큐의 hrtick을 리프로그램한다.

  • 코드 라인 6에서 런큐의 hrtick을 리프로그램한다.
  • 코드 라인 7에서 런큐의 hrtick_csd_pending에 0을 대입하여 hrtick에 대한 call single data IPI 가 처리되었음을 알린다.

 


태스크 Fork

sched_fork()

kernel/sched/core.c

/*
 * fork()/clone()-time setup:
 */
int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
        unsigned long flags;

        __sched_fork(clone_flags, p);
        /*
         * We mark the process as NEW here. This guarantees that
         * nobody will actually run it, and a signal or other external
         * event cannot wake it up and insert it on the runqueue either.
         */
        p->state = TASK_NEW;

        /*
         * Make sure we do not leak PI boosting priority to the child.
         */
        p->prio = current->normal_prio;

        uclamp_fork(p);

        /*
         * Revert to default priority/policy on fork if requested.
         */
        if (unlikely(p->sched_reset_on_fork)) {
                if (task_has_dl_policy(p) || task_has_rt_policy(p)) {
                        p->policy = SCHED_NORMAL;
                        p->static_prio = NICE_TO_PRIO(0);
                        p->rt_priority = 0;
                } else if (PRIO_TO_NICE(p->static_prio) < 0)
                        p->static_prio = NICE_TO_PRIO(0);

                p->prio = p->normal_prio = __normal_prio(p);
                set_load_weight(p, false);

                /*
                 * We don't need the reset flag anymore after the fork. It has
                 * fulfilled its duty:
                 */
                p->sched_reset_on_fork = 0;
        }

        if (dl_prio(p->prio))
                return -EAGAIN;
        else if (rt_prio(p->prio))
                p->sched_class = &rt_sched_class;
        else
                p->sched_class = &fair_sched_class;

        init_entity_runnable_average(&p->se);

        /*
         * The child is not yet in the pid-hash so no cgroup attach races,
         * and the cgroup is pinned to this child due to cgroup_fork()
         * is ran before sched_fork().
         *
         * Silence PROVE_RCU.
         */
        raw_spin_lock_irqsave(&p->pi_lock, flags);
        /*
         * We're setting the CPU for the first time, we don't migrate,
         * so use __set_task_cpu().
         */
        __set_task_cpu(p, smp_processor_id());
        if (p->sched_class->task_fork)
                p->sched_class->task_fork(p);
        raw_spin_unlock_irqrestore(&p->pi_lock, flags);

#ifdef CONFIG_SCHED_INFO
        if (likely(sched_info_on()))
                memset(&p->sched_info, 0, sizeof(p->sched_info));
#endif
#if defined(CONFIG_SMP)
        p->on_cpu = 0;
#endif
        init_task_preempt_count(p);
#ifdef CONFIG_SMP
        plist_node_init(&p->pushable_tasks, MAX_PRIO);
        RB_CLEAR_NODE(&p->pushable_dl_tasks);
#endif
        return 0;
}
  • 코드 라인 5에서 fork된 태스크의 cfs, dl 및 rt 스케줄링 엔티티의 멤버 값들과 numa 밸런싱 관련 값들을 초기화한다.
  • 코드 라인 11에서 처음 태스크가 fork될 때 TASK_NEW 상태로 시작한다.
  • 코드 라인 16에서 PI(Priority Inversion) 문제를 회피하기 위해 부모 태스크가 boosting 상태의 우선 순위로 변경되어 운영하고 있는 경우가 있으므로, 부스팅 되기 직전에 원래 사용하던 우선 순위를 사용해야 한다.
  • 코드 라인 18에서 fork된 태스크의 uclamp 설정이 동작되지 않게 한다. 만일 fork된 태스크의 스케줄러 설정을 reset 요청한 경우 uclamp 값을 min=0, max=100으로 초기화한다. 단 rt 태스크의 경우 min 값을 100으로 설정하여 항상 부스팅한다.
  • 코드 라인 23~39에서 fork된 태스크의 스케줄러 설정을 reset 요청한 경우에 대해 부모의 priority/policy를 사용하지 않고, 디폴트 priority/policy 값을 사용하게 한다.
  • 코드 라인 41~42에서 dl 태스크의 경우 -EAGAIN 값을 반환한다.
  • 코드 라인 43~46에서 태스크가 사용할 스케줄러(rt, cfs)를 지정한다.
    • 태스크에 설정된 prio 값에 따라 rt 또는 cfs 스케줄러를 지정한다.
  • 코드 라인 48에서 엔티티의 로드 및 러너블 로드 평균을 설정된 가중치(scale_load_down(load.weight))값으로 초기화한다.
  • 코드 라인 57~65에서 태스크에 대해 spin 락을 획득한 채로 태스크가 사용할 cpu로 현재 cpu를 지정하고, 스케줄러의 (*task_fork) 후크 함수를 호출하여 런큐에 엔큐하도록 한다.
  • 코드 라인 68~69에서 태스크의 sched_info를 초기화한다.
  • 코드 라인 72에서 태스크가 러닝(running) 상태에 있음을 표시하는 on_cpu를 0으로 초기화한다.
  • 코드 라인 74에서 preempt 카운터를 초기화한다.
  • 코드 라인 76에서 rt 태스크의 마이그레이션에 사용할 pushabnle_tasks를 초기화한다.
  • 코드 라인 77에서 deadline 태스크의 마이그레이션에 사용할 pushable_dl_tasks를 초기화한다.
  • 코드 라인 79에서 정상 값 0을 반환한다.

 

__sched_fork()

kernel/sched/core.c

/*
 * Perform scheduler related setup for a newly forked process p.
 * p is forked by current.
 *
 * __sched_fork() is basic setup used by init_idle() too:
 */
static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
{
        p->on_rq                        = 0;

        p->se.on_rq                     = 0;
        p->se.exec_start                = 0;
        p->se.sum_exec_runtime          = 0;
        p->se.prev_sum_exec_runtime     = 0;
        p->se.nr_migrations             = 0;
        p->se.vruntime                  = 0;
        INIT_LIST_HEAD(&p->se.group_node);

#ifdef CONFIG_FAIR_GROUP_SCHED
        p->se.cfs_rq                    = NULL;
#endif

#ifdef CONFIG_SCHEDSTATS
        /* Even if schedstat is disabled, there should not be garbage */
        memset(&p->se.statistics, 0, sizeof(p->se.statistics));
#endif

        RB_CLEAR_NODE(&p->dl.rb_node);
        init_dl_task_timer(&p->dl);
        init_dl_inactive_task_timer(&p->dl);
        __dl_clear_params(p);

        INIT_LIST_HEAD(&p->rt.run_list);
        p->rt.timeout           = 0;
        p->rt.time_slice        = sched_rr_timeslice;
        p->rt.on_rq             = 0;
        p->rt.on_list           = 0;

#ifdef CONFIG_PREEMPT_NOTIFIERS
        INIT_HLIST_HEAD(&p->preempt_notifiers);
#endif

#ifdef CONFIG_COMPACTION
        p->capture_control = NULL;
#endif
        init_numa_balancing(clone_flags, p);
}

fork된 태스크의 cfs, dl 및 rt 스케줄링 엔티티의 멤버 값들과 numa 밸런싱 관련 값들을 초기화한다. 이 태스크는 현재 태스크에서 새롭게 fork되었으며 다음 두 곳 함수에서 호출되어 사용된다.

  • kernel/fork.c – copy_process() 함수 -> sched_fork() 함수
  • kernel/sched/core.c – init_idle() 함수

 

  • 코드 라인 3에서 on_rq를 0으로 초기화한다. 태스크가 아직 런큐에 엔큐되지 않았음을 의미한다.
  • 코드 라인 5에서 se.on_rq를 0으로 초기화한다. 엔티티가 아직 cfs 런큐에 엔큐되지 않았음을 의미한다.
  • 코드 라인 6~11에서 cfs 스케줄링 엔티티 값들을 초기화한다.
  • 코드 라인 14에서 그룹 스케줄링을 위해 엔티티가 소속된 cfs 런큐를 null로 초기화한다.
  • 코드 라인 19에서 엔티티 통계 값을 초기화한다.
  • 코드 라인 22에서 dl 스케줄링 엔티티의 rb_node를 클리어하여 dl 스케줄러의 RB 트리에 태스크가 하나도 대기하지 않음을 의미한다.
  • 코드 라인 23~24에서 dl 태스크 타이머와 inactive 태스크 타이머를 초기화한다.
  • 코드 라인 25에서 dl 엔티티용 파라미터들을 초기화한다.
  • 코드 라인 27에서 rt 엔티티용 run_list를 초기화한다.
  • 코드 라인 28~31에서 rt 엔티티용 파라미터들을 초기화한다.
  • 코드 라인 34에서 현재 태스크에서 preemption이 발생되면 preempt_notifiers에 등록된 함수들을 동작시키게 하기 위해 preempt_notifiers 리스트를 초기화한다.
  • 코드 라인 38에서 compaction에서 사용할 capture_control 구조체 포인터를 null로 초기화한다.
  • 코드 라인 40에서 numa 밸런싱에서 사용할 값들을 초기화한다.

 

init_dl_task_timer()

kernel/sched/deadline.c

void init_dl_task_timer(struct sched_dl_entity *dl_se)
{
        struct hrtimer *timer = &dl_se->dl_timer;

        hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
        timer->function = dl_task_timer;
}

dl 엔티티의 태스크 timer를 초기화하고 만료 시 호출될 함수를 지정한다.

 

init_dl_inactive_task_timer()

kernel/sched/deadline.c

void init_dl_inactive_task_timer(struct sched_dl_entity *dl_se)
{
        struct hrtimer *timer = &dl_se->inactive_timer;

        hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL_HARD);
        timer->function = inactive_task_timer;
}

dl 엔티티의 inactive 태스크 timer를 초기화하고 만료 시 호출될 함수를 지정한다.

 

__dl_clear_params()

kernel/sched/core.c

void __dl_clear_params(struct task_struct *p)
{
        struct sched_dl_entity *dl_se = &p->dl;

        dl_se->dl_runtime               = 0;
        dl_se->dl_deadline              = 0;
        dl_se->dl_period                = 0;
        dl_se->flags                    = 0;
        dl_se->dl_bw                    = 0;
        dl_se->dl_density               = 0;

        dl_se->dl_throttled             = 0;
        dl_se->dl_yielded               = 0;
        dl_se->dl_non_contending        = 0;
        dl_se->dl_overrun               = 0;
}

dl 엔티티용 파라메터들을 초기화한다.

 


태스크 깨우기

 

다음 그림은 wake_up_process() 함수 이후의 호출 관계를 보여준다.

 

wake_up_process()

kernel/sched/core.c

/**
 * wake_up_process - Wake up a specific process
 * @p: The process to be woken up.
 *
 * Attempt to wake up the nominated process and move it to the set of runnable
 * processes.
 *
 * Return: 1 if the process was woken up, 0 if it was already running.
 *
 * This function executes a full memory barrier before accessing the task state.
 */
int wake_up_process(struct task_struct *p)
{
        WARN_ON(task_is_stopped_or_traced(p));
        return try_to_wake_up(p, TASK_NORMAL, 0);
}
EXPORT_SYMBOL(wake_up_process);

요청한 태스크가 TASK_INTERRUPTIBLE 또는 TAKS_UNINTERRUPTIBLE 상태인 경우 깨운다. 깨운 경우 1을 반환하고, 이미 깨어나 동작 중인 경우 0을 반환한다.

  • #define TASK_NORMAL      (TASK_INTERRUPTIBLE | TAKS_UNINTERRUPTIBLE )

 

try_to_wake_up()

kernel/sched/core.c – 1/2

/**
 * try_to_wake_up - wake up a thread
 * @p: the thread to be awakened
 * @state: the mask of task states that can be woken
 * @wake_flags: wake modifier flags (WF_*)
 *
 * If (@state & @p->state) @p->state = TASK_RUNNING.
 *
 * If the task was not queued/runnable, also place it back on a runqueue.
 *
 * Atomic against schedule() which would dequeue a task, also see
 * set_current_state().
 *
 * This function executes a full memory barrier before accessing the task
 * state; see set_current_state().
 *
 * Return: %true if @p->state changes (an actual wakeup was done),
 *         %false otherwise.
 */
static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
        unsigned long flags;
        int cpu, success = 0;

        preempt_disable();
        if (p == current) {
                /*
                 * We're waking current, this means 'p->on_rq' and 'task_cpu(p)
                 * == smp_processor_id()'. Together this means we can special
                 * case the whole 'p->on_rq && ttwu_remote()' case below
                 * without taking any locks.
                 *
                 * In particular:
                 *  - we rely on Program-Order guarantees for all the ordering,
                 *  - we're serialized against set_special_state() by virtue of
                 *    it disabling IRQs (this allows not taking ->pi_lock).
                 */
                if (!(p->state & state))
                        goto out;

                success = 1;
                cpu = task_cpu(p);
                trace_sched_waking(p);
                p->state = TASK_RUNNING;
                trace_sched_wakeup(p);
                goto out;
        }

        /*
         * If we are going to wake up a thread waiting for CONDITION we
         * need to ensure that CONDITION=1 done by the caller can not be
         * reordered with p->state check below. This pairs with mb() in
         * set_current_state() the waiting thread does.
         */
        raw_spin_lock_irqsave(&p->pi_lock, flags);
        smp_mb__after_spinlock();
        if (!(p->state & state))
                goto unlock;

        trace_sched_waking(p);

        /* We're going to change ->state: */
        success = 1;
        cpu = task_cpu(p);

        /*
         * Ensure we load p->on_rq _after_ p->state, otherwise it would
         * be possible to, falsely, observe p->on_rq == 0 and get stuck
         * in smp_cond_load_acquire() below.
         *
         * sched_ttwu_pending()                 try_to_wake_up()
         *   STORE p->on_rq = 1                   LOAD p->state
         *   UNLOCK rq->lock
         *
         * __schedule() (switch to task 'p')
         *   LOCK rq->lock                        smp_rmb();
         *   smp_mb__after_spinlock();
         *   UNLOCK rq->lock
         *
         * [task p]
         *   STORE p->state = UNINTERRUPTIBLE     LOAD p->on_rq
         *
         * Pairs with the LOCK+smp_mb__after_spinlock() on rq->lock in
         * __schedule().  See the comment for smp_mb__after_spinlock().
         */
        smp_rmb();
        if (p->on_rq && ttwu_remote(p, wake_flags))
                goto unlock;

태스크의 상태가 요청한 state 마스크에 포함된 경우 태스크를 깨운다. 깨운 경우 1을 반환하고, 이미 깨어나 동작 중인 경우 0을 반환한다.

  • 코드 라인 8~29에서 요청한 태스크가 현재 동작 중인 태스크인 경우 다음과 같이 처리한다.
    • 러닝 상태가 아닌 경우 이미 꺠어 있는 상태이므로 먼저 러닝 상태로 변경하고 함수를 빠져나가기 위해 success=1로 변경하고 out 레이블로 이동한다.
    • 이미 러닝 상태인 경우엔 꺠울 필요 없으므로 그냥 함수를 빠져나가기 위해 out 레이블로 이동한다.
  • 코드 라인 37~40에서 스핀락을 획득하고, 다시 상태를 확인해보아 이미 러닝 상태인 경우 깨울 필요 없으므로 unlock 레이블로 이동한다.
  • 코드 라인 45에서 잠들어 있는 태스크를 깨울 예정이므로 미리 success=1로 변경해둔다.
  • 코드 라인 46에서 슬립전에 동작하던 cpu를 알아온다.
  • 코드 라인 68~70에서 태스크가 이미 런큐에 있는 경우 기존 태스크가  슬립해 있었던 cpu의 런큐에서 태스크를 깨우고 러닝 상태로 바꾼다음 out 레이블로 이동한다.

 

kernel/sched/core.c – 2/2

#ifdef CONFIG_SMP
        /*
         * Ensure we load p->on_cpu _after_ p->on_rq, otherwise it would be
         * possible to, falsely, observe p->on_cpu == 0.
         *
         * One must be running (->on_cpu == 1) in order to remove oneself
         * from the runqueue.
         *
         * __schedule() (switch to task 'p')    try_to_wake_up()
         *   STORE p->on_cpu = 1                  LOAD p->on_rq
         *   UNLOCK rq->lock
         *
         * __schedule() (put 'p' to sleep)
         *   LOCK rq->lock                        smp_rmb();
         *   smp_mb__after_spinlock();
         *   STORE p->on_rq = 0                   LOAD p->on_cpu
         *
         * Pairs with the LOCK+smp_mb__after_spinlock() on rq->lock in
         * __schedule().  See the comment for smp_mb__after_spinlock().
         */
        smp_rmb();

        /*
         * If the owning (remote) CPU is still in the middle of schedule() with
         * this task as prev, wait until its done referencing the task.
         *
         * Pairs with the smp_store_release() in finish_task().
         *
         * This ensures that tasks getting woken will be fully ordered against
         * their previous state and preserve Program Order.
         */
        smp_cond_load_acquire(&p->on_cpu, !VAL);

        p->sched_contributes_to_load = !!task_contributes_to_load(p);
        p->state = TASK_WAKING;

        if (p->in_iowait) {
                delayacct_blkio_end(p);
                atomic_dec(&task_rq(p)->nr_iowait);
        }

        cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);
        if (task_cpu(p) != cpu) {
                wake_flags |= WF_MIGRATED;
                psi_ttwu_dequeue(p);
                set_task_cpu(p, cpu);
        }

#else /* CONFIG_SMP */

        if (p->in_iowait) {
                delayacct_blkio_end(p);
                atomic_dec(&task_rq(p)->nr_iowait);
        }

#endif /* CONFIG_SMP */

        ttwu_queue(p, cpu, wake_flags);
unlock:
        raw_spin_unlock_irqrestore(&p->pi_lock, flags);
out:
        if (success)
                ttwu_stat(p, cpu, wake_flags);
        preempt_enable();

        return success;
}
  • 코드 라인 34에서 태스크가 로드에 기여를 하는지 여부를 알아온다.
    • frozen 태스크가 아니고 noload 없는 uniterruptible 상태의 태스크는 로드에 기여한다.
  • 코드 라인 35에서 태스크를 TASK_WAKING 상태로 바꾼다.
  • 코드 라인 37~40에서 태스크가 in_iowait 상태이면 io_wait 상태를 해제한다.
  • 코드 라인 42~47에서 태스크가 깨어날 cpu를 알아온다. 만일 태스크의 슬립전 cpu가 아닌 다른 cpu를 선택한 경우 WF_MIGRATED 플래그를 추가하고, psi 정보를 전달한 후 태스크에 선택한 cpu를 기록한다.
  • 코드 라인 58에서 태스크를 알아온 cpu의 런큐에서 깨운다.
  • 코드 라인 59~60에서 unlock 레이블이다. 스핀락을 복구한다.
  • 코드 라인 61~63에서 out 레이블이다. wakeup이 성공한 경우 관련 stat을 갱신한다.
  • 코드 라인 64~66에서 preemption을 다시 enable하고 success 상태를 반환한다.

 

런큐에 있는 태스크 깨우기

ttwu_remote()

kernel/sched/core.c

/*
 * Called in case the task @p isn't fully descheduled from its runqueue,
 * in this case we must do a remote wakeup. Its a 'light' wakeup though,
 * since all we need to do is flip p->state to TASK_RUNNING, since
 * the task is still ->on_rq.
 */
static int ttwu_remote(struct task_struct *p, int wake_flags)
{
        struct rq *rq;
        int ret = 0;

        rq = __task_rq_lock(p);
        if (task_on_rq_queued(p)) {
                /* check_preempt_curr() may use rq clock */
                update_rq_clock(rq);
                ttwu_do_wakeup(rq, p, wake_flags);
                ret = 1;
        }
        __task_rq_unlock(rq);

        return ret;
}

태스크가 이미 런큐에 있는 경우 태스크를 TASK_RUNNING 상태로 바꾸고 preemption 가능한지 체크한다. 런큐에 태스크가 있었으면 1을 반환한다.

 

ttwu_do_wakeup()

kernel/sched/core.c

/*
 * Mark the task runnable and perform wakeup-preemption.
 */
static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags,
                           struct rq_flags *rf)
{
        check_preempt_curr(rq, p, wake_flags);
        p->state = TASK_RUNNING;
        trace_sched_wakeup(p);

#ifdef CONFIG_SMP
        if (p->sched_class->task_woken) {
                /*
                 * Our task @p is fully woken up and running; so its safe to
                 * drop the rq->lock, hereafter rq is only used for statistics.
                 */
                rq_unpin_lock(rq, rf);
                p->sched_class->task_woken(rq, p);
                rq_repin_lock(rq, rf);
        }

        if (rq->idle_stamp) {
                u64 delta = rq_clock(rq) - rq->idle_stamp;
                u64 max = 2*rq->max_idle_balance_cost;

                update_avg(&rq->avg_idle, delta);

                if (rq->avg_idle > max)
                        rq->avg_idle = max;

                rq->idle_stamp = 0;
        }
#endif
}

태스크를 러너블(TASK_RUNNING) 상태로 변경하고 wake-up preemption을 수행한다.

  • 코드 라인 4에서 preemption이 필요하면 리스케줄 요청을 하도록 체크한다.
  • 코드 라인 5에서 태스크를 TASK_RUNNING 상태로 바꾼다.
  • 코드 라인 9~17에서 해당 태스크의 스케줄러에 해당하는 task_woken에 연결된 함수를 호출한다.
    • dl 및 rt 스케줄러만 관련 함수를 제공한다.
      • task_woken_dl()
        • 다른 dl 태스크가 동작 중이고 요청한 dl 태스크가 동작 중이 아닌 경우 밸런싱을 위해 필요 시 push 한다.
      • task_woken_rt()
        • 다른 rt 태스크가 동작 중이고 요청한 rt 태스크가 동작 중이 아닌 경우 밸런싱을 위해 필요 시 push 한다.
  • 코드 라인 19~29에서 idle 동안의 시간과 기존 avg_idle의 차이 기간의 1/8만 avg_idle에 추가한다. 단 max_idle_balance_cost의 2배를 초과하지 못하게 제한한다.

 

update_avg()

kernel/sched/core.c

static void update_avg(u64 *avg, u64 sample)
{
        s64 diff = sample - *avg;
        *avg += diff >> 3;
}

avg += (sample – avg) / 8 를 산출한다.

 

런큐에 없는 태스크를 깨우기

ttwu_queue()

kernel/sched/core.c

static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)
{
        struct rq *rq = cpu_rq(cpu);
        struct rq_flags rf;

#if defined(CONFIG_SMP)
        if (sched_feat(TTWU_QUEUE) && !cpus_share_cache(smp_processor_id(), cpu)) {
                sched_clock_cpu(cpu); /* Sync clocks across CPUs */
                ttwu_queue_remote(p, cpu, wake_flags);
                return;
        }
#endif

        rq_lock(rq, &rf);
        update_rq_clock(rq);
        ttwu_do_activate(rq, p, wake_flags, &rf);
        rq_unlock(rq, &rf);
}

태스크를 요청한 cpu의 런큐에서 깨운다.

  • 코드 라인 7~11에서 TTWU_QUEUE(디폴트=true) feature가 설정되었고 요청한 cpu와 현재 cpu가 같은 캐시를 공유하지 않으면 요청한 cpu의 런큐의 wake_list에 태스크를 추가하고 IPI를 통해 해당 cpu에 wakeup 요청을 한다.
  • 코드 라인 14~17에서 현재 cpu에서 직접 해당 cpu의 런큐 락을 획득한 후 태스크를 런큐에 엔큐한다. 그런 후 태스크를 러닝 상태로 변경한 후 wake-up preemption을 수행한다.

 

ttwu_queue_remote()

kernel/sched/core.c

static void ttwu_queue_remote(struct task_struct *p, int cpu, int wake_flags)
{
        struct rq *rq = cpu_rq(cpu);

        p->sched_remote_wakeup = !!(wake_flags & WF_MIGRATED);

        if (llist_add(&p->wake_entry, &cpu_rq(cpu)->wake_list)) {
                if (!set_nr_if_polling(rq->idle))
                        smp_send_reschedule(cpu);
                else
                        trace_sched_wake_idle_without_ipi(cpu);
        }
}

태스크를 리모트 cpu에서 깨운다.

  • 코드 라인 5에서 태스크에 remote wakeup 여부를 기록한다.
    • 태스크가 원래 슬립했었던 cpu가 아닌 다른 cpu에서 깨워졌는지 여부가 기록된다.
  • 코드 라인 7~12에서 태스크를 wake_list에 추가하고 IPI를 통해 해당 cpu에 리스케줄 요청한다.

 

ttwu_do_activate()

kernel/sched/core.c

static void
ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags,
                 struct rq_flags *rf)
{
        int en_flags = ENQUEUE_WAKEUP | ENQUEUE_NOCLOCK;

        lockdep_assert_held(&rq->lock);

#ifdef CONFIG_SMP
        if (p->sched_contributes_to_load)
                rq->nr_uninterruptible--;

        if (wake_flags & WF_MIGRATED)
                en_flags |= ENQUEUE_MIGRATED;
#endif

        activate_task(rq, p, en_flags);
        ttwu_do_wakeup(rq, p, wake_flags, rf);
}

태스크를 런큐에 엔큐하고 러너블 상태로 변경한 후 wake-up preemption을 수행한다.

  • 코드 라인 4에서 런큐 엔큐시 사용할 플래그를 지정한다.
  • 코드 라인 6에서 런큐 락을 획득한다.
  • 코드 라인 9~10에서 로드에 참여하는 uninterruptible 태스크인 경우 nr_uninterruptible을 1 감소시킨다.
  • 코드 라인 12~13에서 슬립 했었던 cpu가 아니라 다른 cpu에서 깨워지는 경우 ENQUEUE_MIGRATED 플래그를 추가한다.
  • 코드 라인 16에서 태스크를 런큐에 엔큐하여 동작시킨다.
  • 코드 라인 17에서 태스크를 러너블(TASK_RUNNING) 상태로 변경하고 wake-up preemption을 수행한다.

 


다음 스케줄할 태스크 선택

pick_next_task()

kernel/sched/core.c

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
        const struct sched_class *class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in the fair class we can
         * call that function directly, but only if the @prev task wasn't of a
         * higher scheduling class, because otherwise those loose the
         * opportunity to pull in more work from other CPUs.
         */
        if (likely((prev->sched_class == &idle_sched_class ||
                    prev->sched_class == &fair_sched_class) &&
                   rq->nr_running == rq->cfs.h_nr_running)) {

                p = fair_sched_class.pick_next_task(rq, prev, rf);
                if (unlikely(p == RETRY_TASK))
                        goto restart;

                /* Assumes fair_sched_class->next == idle_sched_class */
                if (unlikely(!p))
                        p = idle_sched_class.pick_next_task(rq, prev, rf);

                return p;
        }

restart:
#ifdef CONFIG_SMP
        /*
         * We must do the balancing pass before put_next_task(), such
         * that when we release the rq->lock the task is in the same
         * state as before we took rq->lock.
         *
         * We can terminate the balance pass as soon as we know there is
         * a runnable task of @class priority or higher.
         */
        for_class_range(class, prev->sched_class, &idle_sched_class) {
                if (class->balance(rq, prev, rf))
                        break;
        }
#endif

        put_prev_task(rq, prev);

        for_each_class(class) {
                p = class->pick_next_task(rq, NULL, NULL);
                if (p)
                        return p;
        }

        /* The idle class should always have a runnable task: */
        BUG();
}

다음 스케줄할 최우선 순위의 태스크를 알아온다. (stop -> dl -> rt -> fair -> idle 스케줄러 순)

  • 코드 라인 13~26에서 높은 확률로 idle 상태였거나 cfs 태스크만 동작하는 경우 cfs 스케줄러의 pick_next_task() 함수를 호출하여 다음 처리할 태스크를 반환한다.처리할 태스크가 없는 경우 idle 태스크를 반환한다. 만일 낮은 확률로 RETRY_TASK 결과를 가져온 경우 restart 레이블로 이동한다.
  • 코드 라인 27~40에서 stop 스케줄러부터 idle 스케줄 클래스까지 순서대로 돌며 (*balance) 루틴을 수행하여 true인 경우 다음 클래스는 무시하고 루프를 빠져나온다.
  • 코드 라인 52에서 기존 태스크를 런큐에 다시 엔큐한다.
  • 코드 라인 54~58에서 stop 스케줄러부터 idle 스케줄 클래스까지 순서대로 돌며 다음 태스크를 가져와서 반환한다.
  • 코드 라인 61에서 이 라인으로 내려오는 일이 없다.

 

다음 그림은 런큐에서 태스크가 수행될 때의 스케줄 순서를 보여준다.

  • 마지막 idle-task 스케줄러 이전까지 수행시킬 task가 없는 경우 부트 프로세스 중에 처음 사용했던 idle 태스크가 사용된다.

 


activate & deactivate 태스크

activate_task()

kernel/sched/core.c

void activate_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (task_contributes_to_load(p))
                rq->nr_uninterruptible--;

        enqueue_task(rq, p, flags);

        p->on_rq = TASK_ON_RQ_QUEUED;
}

태스크를 런큐에 추가한다.

  • 로드 기여중인 uninterruptible 태스크인 경우 런큐의 nr_uninterrtible 카운터를 감소시킨다.

 

task_contributes_to_load()

include/linux/sched.h

#define task_contributes_to_load(task)  ((task->state & TASK_UNINTERRUPTIBLE) != 0 && \
                                         (task->flags & PF_FROZEN) == 0 && \
                                         (task->state & TASK_NOLOAD) == 0)

uninterruptible 태스크 상태이면서 suspend 된 것은 아닌 경우 true를 반환한다.

  • 시스템 suspend 시 frozen 플래그가 설정된다.
  • uninterruptible 태스크가 forzen 플래그와 noload 상태가 없어야 로드 기여 상태가 된다.

 

enqueue_task()

kernel/sched/core.c

static void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (!(flags & ENQUEUE_NOCLOCK))
                update_rq_clock(rq);

        if (!(flags & ENQUEUE_RESTORE)) {
                sched_info_queued(rq, p);
                psi_enqueue(p, flags & ENQUEUE_WAKEUP);
        }

        uclamp_rq_inc(rq, p);
        p->sched_class->enqueue_task(rq, p, flags);
}

태스크를 런큐에 추가한다.

  • 런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*enqueue_task) 후크에 연결된 함수를 호출하여 런큐에 추가한다.
  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – enqueue_task_stop()
    • deadline 스케줄러 – enqueue_task_dl()
    • rt 스케줄러 – enqueue_task_rt()
    • cfs 스케줄러 – enqueue_task_fair()
    • idle 스케줄러 – enqueue_task_idle()

 

deactivate_task()

kernel/sched/core.c

void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
{
        p->on_rq = (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING;

        if (task_contributes_to_load(p))
                rq->nr_uninterruptible++;

        dequeue_task(rq, p, flags);
}

태스크를 런큐에서 제거한다.

  • 로드 기여중인 uninterruptible 태스크인 경우 런큐의 nr_uninterrtible 카운터를 증가시킨다.

 

dequeue_task()

kernel/sched/core.c

static void dequeue_task(struct rq *rq, struct task_struct *p, int flags)
{
        if (!(flags & DEQUEUE_NOCLOCK))
                update_rq_clock(rq);

        if (!(flags & DEQUEUE_SAVE)) {
                sched_info_dequeued(rq, p);
                psi_dequeue(p, flags & DEQUEUE_SLEEP);
        }

        uclamp_rq_dec(rq, p);
        p->sched_class->dequeue_task(rq, p, flags);
}

태스크를 런큐에서 제거한다.

  • 런큐 클럭을 갱신시키고 요청 태스크의 스케줄러에 있는 (*dequeue_task) 후크에 연결된 함수를 호출한다.
  • 각 스케줄러마다 다음의 함수를 호출한다.
    • stop 스케줄러 – dequeue_task_stop()
    • deadline 스케줄러 – dequeue_task_dl()
    • rt 스케줄러 – dequeue_task_rt()
    • cfs 스케줄러 – dequeue_task_fair()
    • idle 스케줄러 – dequeue_task_idle()

 


기타

스케줄링 클래스 변경

__sched_setscheduler() 에서 스케줄 클래스를 변경하거나 우선 순위를 변경할 때 check_class_changed() 함수를 호출한다.

check_class_changed()

  • (*switched_from)
  • (*switched_to)
  • (*prio_changed)

 

preemption 체크

check_preempt_curr()

  • (*check_preempt_curr)

 

실행 가능 cpu 설정

do_set_cpus_allowed()

  • (*set_cpus_allowed)

 

실행 cpu 변경

set_task_cpu()

  • (*migrate_task_rq)

 

새 태스크 실행

wake_up_new_task()

  • (*select_task_rq)
  • (*task_woken)

 

태스크 킬

finish_task_switch()

  • (*task_dead)

 

실행 도메인을 통해 선택한 cpu에서 태스크 실행(execve)

sched_exec()

  • (*select_task_rq)
  • migration_cpu_stop() -> 디큐 -> cpu 지정 -> 엔큐

 

태스크의 총 실행시간 조회

task_sched_runtime()

  • (*update_curr)
    • 현재 실행 중인 경우 정확한 산정을 위해 현재 까지 실행한 시간을 추가하기 위해 위의 후크를 통해 현재 태스크의 런타임 갱신을 요청한다.

 

다음 태스크에 양보

태스크는 러닝 상태를 유지하여 런큐에서 디큐되지 않은 채로 리스케줄한다. 현재 태스크가 cfs 태스크인 경우 리스케줄 시 현재 태스크는 가능한한 제외한다.

  • 현재 태스크가 cfs 태스크인 경우 skip 버디에 지정되어 pick_next_task()에서 리스케줄 시 선택되지 않게 한다.

sys_sched_yield()

  • (*yield_task)

 

지정된 태스크에 양보

태스크는 러닝 상태를 유지하여 런큐에서 디큐되지 않은 채로 지정한 태스크로 리스케줄한다. 현재 태스크가 cfs 태스크인 경우 리스케줄 시 현재 태스크는 가능한한 제외한다.

  • cfs 태스크인 경우 현재 태스크는 skip 버디에 지정되어 pick_next_task()에서 리스케줄 시 선택되지 않게 한다.
  • cfs 태스크인 경우 지정된 태스크는 next 버디에 지정되어 pick_next_task()에서 리스케줄 시 선택되도록 한다.

yield_to()

  • (*yield_to_task)

 

RR 인터벌 조회

round robin rt 태스크인 경우 rr 인터벌을 반환한다. (디폴트=100ms) cfs 태스크인 경우엔 해당 태스크의 time slice 값을 반환한다.

sched_rr_get_interval()

  • (*get_rr_interval)

 

Migrate 태스크

migrate_tasks()

  • (*put_prev_task)

 

태스크 그룹 변경

sched_change_group()

  • (*task_change_group)

 

런큐 선택

select_task_rq()

 


Wait for Blocked I/O

wait queue와 wait event에 대한 내용은 별도의 페이지에서 분석하기로 하고 관련된 문서는 다음을 먼저 참고한다.

 


스케줄러 Features

sched_feat() 매크로

kernel/sched/sched.h

/*
 * Each translation unit has its own copy of sysctl_sched_features to allow
 * constants propagation at compile time and compiler optimization based on
 * features default.
 */
#define SCHED_FEAT(name, enabled)       \
        (1UL << __SCHED_FEAT_##name) * enabled |
static const_debug __maybe_unused unsigned int sysctl_sched_features =
#include "features.h"
        0;
#undef SCHED_FEAT

#define sched_feat(x) !!(sysctl_sched_features & (1UL << __SCHED_FEAT_##x))

 

kernel/sched/features.h

/*
 * Only give sleepers 50% of their service deficit. This allows
 * them to run sooner, but does not allow tons of sleepers to
 * rip the spread apart.
 */
SCHED_FEAT(GENTLE_FAIR_SLEEPERS, true)

/*
 * Place new tasks ahead so that they do not starve already running
 * tasks
 */
SCHED_FEAT(START_DEBIT, true)

/*
 * Prefer to schedule the task we woke last (assuming it failed
 * wakeup-preemption), since its likely going to consume data we
 * touched, increases cache locality.
 */
SCHED_FEAT(NEXT_BUDDY, false)

/*
 * Prefer to schedule the task that ran last (when we did
 * wake-preempt) as that likely will touch the same data, increases
 * cache locality.
 */
SCHED_FEAT(LAST_BUDDY, true)

/*
 * Consider buddies to be cache hot, decreases the likelyness of a
 * cache buddy being migrated away, increases cache locality.
 */
SCHED_FEAT(CACHE_HOT_BUDDY, true)

/*
 * Allow wakeup-time preemption of the current task:
 */
SCHED_FEAT(WAKEUP_PREEMPTION, true)

SCHED_FEAT(HRTICK, false)
SCHED_FEAT(DOUBLE_TICK, false)

/*
 * Decrement CPU capacity based on time not spent running tasks
 */
SCHED_FEAT(NONTASK_CAPACITY, true)

/*
 * Queue remote wakeups on the target CPU and process them
 * using the scheduler IPI. Reduces rq->lock contention/bounces.
 */
SCHED_FEAT(TTWU_QUEUE, true)

/*
 * When doing wakeups, attempt to limit superfluous scans of the LLC domain.
 */
SCHED_FEAT(SIS_AVG_CPU, false)
SCHED_FEAT(SIS_PROP, true)

/*
 * Issue a WARN when we do multiple update_rq_clock() calls
 * in a single rq->lock section. Default disabled because the
 * annotations are not complete.
 */
SCHED_FEAT(WARN_DOUBLE_CLOCK, false)

#ifdef HAVE_RT_PUSH_IPI
/*
 * In order to avoid a thundering herd attack of CPUs that are
 * lowering their priorities at the same time, and there being
 * a single CPU that has an RT task that can migrate and is waiting
 * to run, where the other CPUs will try to take that CPUs
 * rq lock and possibly create a large contention, sending an
 * IPI to that CPU and let that CPU push the RT task to where
 * it should go may be a better scenario.
 */
SCHED_FEAT(RT_PUSH_IPI, true)
#endif

SCHED_FEAT(RT_RUNTIME_SHARE, true)
SCHED_FEAT(LB_MIN, false)
SCHED_FEAT(ATTACH_AGE_LOAD, true)

SCHED_FEAT(WA_IDLE, true)
SCHED_FEAT(WA_WEIGHT, true)
SCHED_FEAT(WA_BIAS, true)

/*
 * UtilEstimation. Use estimated CPU utilization.
 */
SCHED_FEAT(UTIL_EST, true)

다음과 같은 스케줄러 feature들이 있다. (디폴트: 주황색=true, 파란색=false)

  • GENTLE_FAIR_SLEEPERS
    • 슬립 후 깨어나는 태스크에 대해 스케줄 레이턴시의 절반 만큼 더 빨리 실행할 수 있도록 한다. (50% 보너스)
    • 이 기능을 disable하면 저가형(low-end) 디바이스에서 응답성이 좋아진다.
    • 참고: sched: Implement a gentler fair-sleepers feature (2009, v2.6.32-rc1)
  • START_DEBIT
    • 새(fork) 태스크에 대해 한 타임(스케줄 레이턴시) 뒤에서 실행하도록 한다.
    • 새 태스크가 이미 실행 중인 태스크를 방해하지 못하게 한다.
    • 참고: Improving scheduler latency (2010) | LWN.net
  • NEXT_BUDDY
    • 캐시 지역성을 높이기 위해 깨어난 태스크를 다음 스케줄 시 우선 처리한다.
  • LAST_BUDDY
    • 캐시 지역성을 향상시키기 위해 웨이크 업 preemption이 성공하면 preemption 직전에 실행된 작업 옆에 둔다.
  • CACHE_HOT_BUDDY
    • 캐시 지역성을 높이기 위해 마이그레이션 할 작업을 항상 캐시 hot 상태로 판단한다. (다른 cpu로의 마이그레이션 비율을 축소시킨다)
  • WAKEUP_PREEMPTION
    • 헤비 로드를 갖는 시스템에서 이 옵션을 disable하면 preemption을 하지 않도록 하여 성능을 높일 수 있다. 단 반응성이 떨어진다.
  • HRTICK
    • hrtick을 사용하면 태스크마다 주어지는 런타임을 hrtimer를 사용하여 틱을 만들어낸다.
  • DOUBLE_TICK
    • 정규 틱과 hrtick을 동시에 운영하게 한다.
  • NONTASK_CAPACITY
  • TTWU_QUEUE
    • 캐시 지역성을 높이기 위해서 태스크가 로컬 cpu가 아닌 다른 cpu에서 깨어나야 할 때 IPI를 사용하는 리모트 큐의 사용 여부를 결정한다.
    • 이 기능을 사용하면서 깨어날 태스크가 로컬 캐시를 공유하지 않는 cpu인 경우 IPI를 통해 원격 cpu 런큐에 태스크를 깨운다.
    • 이 기능을 사용하지 않거나 현재 cpu가 깨어나야 할 cpu가 서로 로컬 캐시를 공유하는 경우 다음과 같이 기존 wakeup 방법을 사용한다.
      • 로컬 cpu가 리모트 cpu의 런큐락을 획득하고 직접 enqueue한 후 preempt 요청한다.
  • SIS_AVG_CPU
  • SIS_PROP
  • WARN_DOUBLE_CLOCK
  • RT_PUSH_IPI
  • RT_RUNTIME_SHARE
    • SMP 시스템에서 RT 그룹 스케줄링을 사용할 때 런타임이 부족해진 경우 다른 cpu로 부터 빌려올 수 있게 한다.
    • 이 기능은 빌려오는 런타임때문에 cfs 태스크의 기아(starving) 현상이 발생할 수 있어 커널 v5.10-rc1에서 디폴트 값을 disable 하였다.
  • LB_MIN
  • ATTACH_AGE_LOAD
  • WA_IDLE
  • WA_WEIGHT
  • WA_BIAS
  • UTIL_EST

 

참고: Tweak Kernel’s Task Scheduler to Boost Performance on Android [Part 2] (2018) | DroidViews.com

 

다음은 qemu에서 동작중인 커널 v5.4의 스케줄러 feature들 예를 보여준다.

$ cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION 
NO_HRTICK NO_DOUBLE_TICK         NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU SIS_PROP NO_WARN_DOUBLE_CLOCK 
RT_PUSH_IPI                      RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD WA_IDLE WA_WEIGHT WA_BIAS 
UTIL_EST

 

다음은 rpi4 시스템에서 동작중인 커널 v4.19의 스케줄러 feature들 예를 보여준다.

$ cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION 
NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU SIS_PROP NO_WARN_DOUBLE_CLOCK 
RT_PUSH_IPI                      RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD WA_IDLE WA_WEIGHT WA_BIAS 
UTIL_EST

 

다음은 rock960 시스템에서 동작중인 커널 v4.4의 스케줄러 feature들 예를 보여준다.

$ cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION 
NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE
RT_PUSH_IPI NO_FORCE_SD_OVERLAP  RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD                 
ENERGY_AWARE

 

참고

 

 

Scheduler -2- (Global Cpu Load)

<kernel v5.4>

Scheduler -2- (Global Cpu Load)

cpu 로드 관련 소스의 위치는 다음과 같은 변화가 있어왔다.

 

추세 관련 사전 산술 지식

주식 시장에서 주가 흐름에 단순이동평균(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)
      • 최근 데이터에 더 높은 가중치를 주는 방법으로 전일 지수 이동 평균 값과 금일 값만 사용하여 간단히 계산한다.
      • 지수 평활 계수(Exponential Percentage) k를 사용하여 1-k를 전일 지수 이동 평균값에 곱하여 사용하고, 금일 값에 k를 곱해 사용한다.
        • 평활 계수는 다음과 같은 지수 함수 모델을 사용한다. (n=기간)
          • k = a * (b^n)
      • 지수 평활 계수(Exponential Percentage) k는 환경에 따라 다르다.
      • 주식 시장의 평활 계수 k는 지수 평균 기간에 의한 추정법을 사용하여 다음과 같이 결정된다.
        • (a=2, b=1/(n+1))
        • k= 2 * 1/(n+1) = 2/(n+1)
          • 예: n=2일, k=2/(n+1)=0.666666…
          • 예: n=3일, k=2/(n+1)=0.5
          • 예: n=10일, k=2/(n+1)=0.181818…
      • 매일 지수 이동 평균 값 * (1-k) + 금일 값 * (k)을 반영하여 산출한다.
        • 1일차: 1020 = 100% 반영
        • 2일차: 2일간 이동 평균 반영 = 1020 * 33% + 1030 * 66% = 1026
        • 3일차: 3일간 이동 평균 반영 = 1026 * 50% + 1000 * 50% = 1013
        • 4일차: 3일간 이동 평균 반영 = 1013 * 50% + 1010 * 50% = 1012
        • 5일차: 3일간 이동 평균 반영 = 1012 * 50% + 1020 * 50% = 1016
        • 6일차: 3일간 이동 평균 반영 = 1016 * 50% + 1060 * 50% = 1038
  • 가중 이동 평균과 지수 이동 평균에서 적용되는 가중치와 평활 계수가 적용 일자에 따라 변화되는 그래프 값은 다음 자료를 참고한다.

 

리눅스 커널에서의 지수 이동 평균

리눅스 커널에서는 cpu 로드 산출에 필요한 모든 raw 데이터를 저장하지 않는다. 따라서 가장 적합한 모델로 raw 데이터를 저장하지 않는 특성을 가진 지수 이동 평균(EMA)를 사용한다. 그리고 지수 평활법(ES: Exponential Smoothing) 중 하나인 지수 감소 평균(EDA)을 사용하여 지수 평활 계수 k값을 결정하는데 글로벌 cpu 로드와 PELT 산출에 사용하는 k 값이 다르며 각각의 주제에서 다루기로 한다.

  • 지수 감소 평균(EDA: Exponential Decaying Average, EDMA: Exponential Damped Moving Average)

글로벌 cpu 로드 산출식

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

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

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

 

cpu 로드의 이진화 정수 사용

cpu 로드 값은 32비트 시스템에서는 11비트를 사용한다. 실수 로드 값 1.0에 대응하는 2^11=2048 이진화 정수 값을 사용한다.

  • 1개의 cpu가 있는 시스템에서 태스크 2개가 동작 상태(runnable)인 경우 cpu 로드 값은 2.0이 된다.
  • cpu가 4개가 동작하는 시스템에서는 이 값을 cpu 수 4로 나누게 되므로 0.5의 cpu 로드 값이 된다.

 

글로벌 로드 평균 (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    <- e1 = n=12(1분)에서의 지수 평활 계수 k
  • avenrun[1] = avenrun[1]*e2 + nr_active*(1-e2) + 0.5    <- e2 = n=60(5분)에서의 지수 평활 계수 k
  • avenrun[2] = avenrun[2]*e3 + nr_active*(1-e3) + 0.5    <-e3 = n=180(15분)에서의 지수 평활 계수 k

 

커널의 글로벌 cpu 로드를 위한 지수 평활 계수는 다음과 같다.

  • 지수 함수 모델 k = a * (b^n)
    • a=1, b=e^(-1/n), n=반영할 기간
  • k=e^(-1/n)
  • 지수 평활 계수 k를 사용하여 cpu 로드 값은 다음과 같이 산출된다.
    • cpu 로드 값 = 기존 cpu 로드 값 * k + 새 cpu 로드 값 * (1 – k)
  • 예) 커널이 5초에 한번씩 측정된 과거 1분 동안의 누적 데이터를 사용하므로 기간 n=12가 된다.
    • k=e^(-1/12) = 0.920044 (약 92%)
      • Excel Spread Sheet 산출 예)
        • =@exp(-1/12)

 

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

cpu 로드 밸런스에 사용하였던 이 방법은  커널 v5.3-rc1에서 제거되었다.

 


글로벌 로드 평균

avenrun[] 산출 – (1, 5, 15분)

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

  • 고정 틱 핸들러
    • tick_handle_periodic() -> tick_periodic() -> do_timer() -> calc_global_load()
  • 틱 nohz 핸들러
    • tick_nohz_handler() -> tick_sched_do_timer() -> tick_do_update_jiffies64() -> do_timer() -> calc_global_load()
    • tick_nohz_update_jiffies() -> tick_do_update_jiffies64() -> do_timer() -> calc_global_load()
    • tick_nohz_restart_sched_tick() -> tick_do_update_jiffies64() -> do_timer() -> calc_global_load()
  • hrtimer 틱 핸들러
    • tick_sched_timer() -> tick_sched_do_timer() -> tick_do_update_jiffies64() -> do_timer() -> calc_global_load()

 

calc_global_load()

kernel/sched/loadavg.c

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

        sample_window = READ_ONCE(calc_load_update);
        if (time_before(jiffies, sample_window + 10))
                return;

        /*
         * Fold the 'old' NO_HZ-delta to include all NO_HZ CPUs.
         */
        delta = calc_load_nohz_fold();
        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);

        WRITE_ONCE(calc_load_update, sample_window + LOAD_FREQ);

        /*
         * In case we went to NO_HZ for multiple LOAD_FREQ intervals
         * catch up in bulk.
         */
        calc_global_nohz();
}

최근 1분, 5분, 15분 주기 지수 이동 평균을 사용한 글로벌 cpu 로드를 산출하여 avenrun[]에 대입한다. 이 함수가 매 틱마다 호출되지만 실제 산출은 5초 주기로 수행한다. 엄밀히 5초 주기 이후 lockless flip 인덱스 기법을 사용하기 위해 10틱이 지난 후에 수행한다.

  • 코드 라인 6~8에서 현재 시각(jiffies)이 cpu 로드 산출 주기(5초)+10틱 이전이면 함수를 빠져나간다.
  • 코드 라인 13~15에서 현재 cpu에 대해 active 태스크 수의 변화분 delta를 얻어와서 calc_load_tasks에 반영한다.
  • 코드 라인 17~18에서 active 태스크가 있는 경우 이를 11비트 정밀도를 갖는 이진화 정수로 변환시킨다.이 값을 전일 지수 이동 평균값에 적용할 예정이다.
    • 예) cpu 로드 값이 2이라면 2048(실수 1.0)을 곱한 값을 현재 로드 값으로 반영할 예정이다.
  • 코드 라인 20~22에서 기존 cpu 로드 값인 avenrun[]과 새로 추가 반영할 cpu 로드 값인 active 값으로 각각 1분, 5분, 15분에 해당하는 지수 평활 계수 EXP_n을 사용하여 avenrun[]에 반영한다.
  • 코드 라인 24에서 다음 cpu 로드 산출 주기를 위해 5초를 더한다.
  • 코드 라인 30에서 nohz idle로 인해 다음 cpu 로드 산출 주기를 이미 초과한 경우 miss된 cpu 로드 갱신 주기 수만큼 적용하여 cpu 로드를 산출하여 avenrun[]을 다시 갱신한다.
    • 예) 20여초 nohz idle로 인해 cpu 로드를 갱신하지 못한 경우 처음 5초에 해당하는 시간의 cpu 로드가 이미 갱신되었으므로 나머지 3번에 해당하는 cpu 로드를 산출하도록 한다.

 

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

11비트 정밀도를 가진 이진화 정수값을 산출하기 위한 각종 상수들이다.

include/linux/sched/loadavg.h

/*
 * 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/180)) * 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 로드를 산출하는 식을 보여준다. (커널 v4.7~)

 

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

  • 주의: 커널 v4.6 이하에서 반올림이 적용되어 산출한 값이다. 커널 v4.7 이상에서는 새 로드가 기존 로드보다 동등하거나 상승하는 경우 올림처리한다.

 

active 태스크 수 이론

cpu 로드를 산출하기 위해 active 태스크 수를 파악해야 한다. 리눅스에서의 active 태스크 수는 다음을 포함한다.

  • runnable 태스크 수
    • running 태스크(rq->curr 태스크)
    • 런큐에서 엔큐되어 대기중인 태스크들
  • uninterruptible 상태로 슬립한 태스크 수

 

리눅스 시스템에서의 글로벌 cpu 로드는 cpu 로드라기 보다는 시스템 로드에 더 가깝다. cpu 로드를 산출하기 위해 active 태스크 수를 파악해야 한다.

  • active 태스크 산출 요소
    • runnable 태스크의 수
      • running 태스크 (cfs_rq->curr 엔티티)
      • RB Tree enqueue 태스크들
      • 유닉스 및 리눅스에서 사용
    • Sleep 상태의 uninterruptible 태스크(주로 io 요청 대기 스레드) 수
      • 리눅스에서만 사용

 

유닉스 등과 다르게 리눅스에서는 uninterruptible 상태로 슬립 중인 태스크도 포함시키는 이유로 로드를 산출하는데 이 uninterruptible 태스크가 I/O 요청에 대한 대기 상태인 경우가 많고 이에 따라 I/O 요청에 대한 로드를 포함하는 것이 합리적인 판단이라서 포함시켰다.  확실히 이와 같은 형태의 글로벌 로드 산출 구현은 정확한 로드를 산출하는 것이 힘들다는 것을 알 수 있다. 그러므로 cpu 글로벌 로드 뿐만 아니라 여러 상태 지표를 동시에 사용하여야 시스템의 로드 상태를 파악할 수 있다. (결국 지금도 완전하지 않은 상태로 추후 바뀔 가능성도 있다)

 

다음 그림은 루트 태스크 그룹만을 가진 2개 cpu에서 동작하는 각 cfs 런큐의 태스크 상태들을 보여준다. 이들 중 로드에 포함될 active 태스크 수는 8이다.

  • 로드에 포함될 태스크들 (총 8개)
    • 4 개의 runnable 태스크들
      • 2 개의 running 태스크들
      • 2 개의 enqueue 태스크들
    • 4 개의 슬립 태스크들
      • 4 개의uninterruptible 태스크들

 

런큐에서의 active 태스크 수 산출 실전

active 태스크 수를 산출할 때 마다 각 cpu의 런큐를 뒤지지 않고 전역 변수 calc_load_tasks에 필요 시마다 전파하여 사용하는 방식을 사용하여 조금이라도 빠른 산출 방법을 적용하였다. nohz idle을 위해 중간 단계에 calc_load_nohz[2] 변수를 사용하여 active 태스크의 변동 분 delta를 저장하고 5초마다 로드가 산출될 때 calc_load_nohz[2] 배열에서 인덱스를 교대로 사용하여 읽어낸다. 배열의 사용법은 조금 복잡하니 calc_load_nohz_fold()에서 더 알아보자.

 

다음 그림은 nohz idle 상태로 진입할 때 active 태스크의 변동분을 저장하는 함수와 5초 주기로 글로벌 로드를 산출하는 함수의 흐름을 보여준다.

 

calc_load_nohz_fold()

kernel/sched/loadavg.c

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

        return delta;
}

현재 cpu의 런큐에서 다시 계산된 active 태스크 수의 변경된 값 delta를 얻어온다. (lockless를 위해 flip 인덱스로 접근하도록 설계되었다.)

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

 

calc_load_nohz[]

kernel/sched/loadavg.c

/*
 * 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 NO_HZ-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 NO_HZ-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 NO_HZ contribution in this window while
 *    accumlating the new one.
 *
 *  - When we wake up from NO_HZ 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 NO_HZ-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 NO_HZ 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_nohz[2];
static int calc_load_idx;

 

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

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

 

calc_load()

kernel/sched/loadavg.c

/*
 * a1 = a0 * e + a * (1 - e)
 */
static inline unsigned long
calc_load(unsigned long load, unsigned long exp, unsigned long active)
{
        unsigned long newload;

        newload = load * exp + active * (FIXED_1 - exp);
        if (active >= load)
                newload += FIXED_1-1;

        return newload / FIXED_1;
}

지수 이동 평균 기간이 적용된 지수 평활 계수 @exp를 사용하여 새 로드 값을 산출한다.

  • 코드 라인 5에서 기존 로드 값 @load에 이동 평균 기간이 적용된 지수 평활 계수 @exp를 곱해 감소시킨 후 현재 로드 값인 active 값을 반영한다.
    • @load 값은 기존 로드 값으로 11비트 정확도를 사용한 이진화 정수 값이다.
    • @active 값은 반영할 현재 로드 값으로 11비트 정확도를 사용한 이진화 정수 값이다.
  • 코드 라인 6~9에서 반영할 로드 값이 기존 로드 값보다 더 큰 경우 상승 추세이므로 소숫점이하 올림 처리하고, 그 외에는 버린다.

 

다음 그림은 글로벌 cpu 로드를 산출하는 예를 보여준다. (커널 v4.7~)

 

예) 기존 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) + 2047) / 2048 = 1270
    • avenrun[1]=(1024 * 2014 + 4096 * (2048-2014) + 2047) / 2048 = 1075
    • avenrun[2]=(1024 * 2037 + 4096 * (2048-2037) + 2047) / 2048 = 1041
  • 2nd 틱:
    • avenrun[0]=(1271 * 1884 + 4096 * (2048-1884) + 2047) / 2048 = 1497
    • avenrun[1]=(1076 * 2014 + 4096 * (2048-2014) + 2047) / 2048 = 1126
    • avenrun[2]=(1041 * 2037 + 4096 * (2048-2037) + 2047) / 2048 = 1058
  • 3rd 틱:
    • avenrun[0]=(1498 * 1884 + 4096 * (2048-1884) + 2047) / 2048 = 1706
    • avenrun[1]=(1127 * 2014 + 4096 * (2048-2014) + 2047) / 2048 = 1176
    • avenrun[2]=(1058 * 2037 + 4096 * (2048-2037) + 2047) / 2048 = 1075

 

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

  • 산출 전:
    • avenrun[0]=1024, active=0
    • avenrun[1]=1024, active=0
    • avenrun[2]=1024,active=0
  • 1st 틱:
    • avenrun[0]=(1024 * 1884 + 0 * (2048-1884) + 0) / 2048 = 942
    • avenrun[1]=(1024 * 2014 + 0 * (2048-2014) + 0) / 2048 = 1007
    • avenrun[2]=(1024 * 2037 + 0 * (2048-2037) + 0) / 2048 = 1018
  • 2nd 틱:
    • avenrun[0]=(1271 * 1884 + 0 * (2048-1884) + 0) / 2048 = 866
    • avenrun[1]=(1076 * 2014 + 0 * (2048-2014) + 0) / 2048 = 990
    • avenrun[2]=(1041 * 2037 + 0 * (2048-2037) + 0) / 2048 = 1012
  • 3rd 틱:
    • avenrun[0]=(1498 * 1884 + 0 * (2048-1884) + 0) / 2048 = 796
    • avenrun[1]=(1127 * 2014 + 0 * (2048-2014) + 0) / 2048 = 973
    • avenrun[2]=(1058 * 2037 + 0 * (2048-2037) + 0) / 2048 = 1006

 

cpu 로드 소숫점 처리

글로벌 cpu 로드를 처리하는데 장시간 idle 상태인데에도 각 주기별로 0.00, 0.01, 0.05 이하 값이 더 이상 하강하지 않는 버그가 있어 수정하였다.

  • 커널 v4.7이후 현재 코드와 동일하게 상승시 올림 처리하고, 하강시 내림 처리한다.
  • 커널 v4.7 이전 코드들은 상승/하강시 모두 반올림 처리하였다.
    • load *= exp;
    • load += active * (FIXED_1 – exp);
    • load += 1UL << (FSHIFT – 1);
    • return load >> FSHIFT;

 

다음 그림은 로드 값의 변화를 산출할때 반올림하여 처리하는 모습을 보여준다. (커널 v4.6 이하)

 

calc_global_nohz()

kernel/sched/loadavg.c

/*
 * NO_HZ can leave us missing all per-CPU ticks calling
 * calc_load_fold_active(), but since a NO_HZ CPU folds its delta into
 * calc_load_nohz per calc_load_nohz_start(), all we need to do is fold
 * in the pending NO_HZ delta if our NO_HZ 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)
{
        unsigned long sample_window;
        long delta, active, n;

        sample_window = READ_ONCE(calc_load_update);
        if (!time_before(jiffies, sample_window + 10)) {
                /*
                 * Catch-up, fold however many we are behind still
                 */
                delta = jiffies - sample_window - 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);

                WRITE_ONCE(calc_load_update, sample_window + n * LOAD_FREQ);
        }

        /*
         * Flip the NO_HZ 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[]에 대입한다.

  • 코드 라인 6~7에서 현재 시간(jiffies)이 갱신 주기+10틱보다 뒤에 있는 경우 즉, 갱신이 밀려 있는 경우
  • 코드 라인 11~12에서 몇 번 밀려 있는지 횟수를 산출한다.
    • 예) jiffies와ㅓ calc_load_update의 차이가 21초인 경우 21/5+1 = 정수 5가된다.
  • 코드 라인 14~15에서 현재 active 태스크 수를 읽어와서 그 값을 11비트 정밀도를 가진 이진화 정수로 바꾼다.
  • 코드 라인 17~21에서 avenrun[] 값을 갱신하고 갱신 주기도 update한다.
  • 코드 라인 32에서 calc_load_idx를 증가시켜 새로운 인덱스를 사용하도록 한다.

 

calc_load_n()

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

 

참고

 

 

PELT(Per-Entity Load Tracking) – v4.0

<kernel v4.0>

PELT: Per-Entity Load Tracking

커널 v5.4에 대한 최근 글은 다음을 참고한다.

 

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

  • enqueue_entity_load_avg()
    • cfs 런큐에 태스크가 엔큐될 때
  • dequeue_eneity_load_avg()
    • cfs 런큐에서 태스크가 디큐될 때
  • put_prev_entity()
    • 현재 동작 중인 태스크를 런큐의 대기로 돌려질 때
  • entity_tick()
    • 스케줄 틱마다 호출될 때

 

엔큐 시 엔티티 로드 평균 산출

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_count가 0을 초과한 경우 엔티티 decay를 동기화시킨다.
    • 스케줄 엔티티의 로드 평균 기여를 ‘cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count’ 만큼 decay 한다.
  • 코드 라인 38~41에서 decay_count가 0을 초과하였었고, 인수wakeup 요청이 있는 경우 migrate된 태스크들은 blocked 로드에서 기여 값을 감소시키고 엔티티 로드 평균을 구한다.
  • 코드 라인 43에서 스케줄 엔티티에 있는 로드 평균 기여를 cfs 런큐의 러너블 로드 평균에  추가한다
  • 코드 라인 45에서 블럭드 로드를 갱신하고 러너블 평균과 더해 cfs 런큐의 tg_load_contrib와 태스크 그룹의 load_avg 에 추가한다.

 

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

 

__synchronize_entity_decay()

kernel/sched/fair.c

/* Synchronize an entity's decay with its parenting cfs_rq.*/
static inline u64 __synchronize_entity_decay(struct sched_entity *se)
{
        struct cfs_rq *cfs_rq = cfs_rq_of(se);
        u64 decays = atomic64_read(&cfs_rq->decay_counter);

        decays -= se->avg.decay_count;
        se->avg.decay_count = 0;
        if (!decays)
                return 0;

        se->avg.load_avg_contrib = decay_load(se->avg.load_avg_contrib, decays);

        return decays;
}

스케줄 엔티티의 로드 평균 기여를 cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count 만큼 decay 한다.

  • 코드 라인 5~10에서 cfs 런큐의 decay_counter에서 스케줄 엔티티의 decay_count 값을 뺀다. 스케줄 엔티티의 decay_count 값은 0으로 리셋한다. 적용할 decays 값이 없으면 결과 값을 0으로 함수를 빠져나간다.
  • 코드 라인 12에서 스케줄 엔티티의 load_avg_contrib를 decays 만큼 decay한다.
  • 코드 라인 14에서 decays 값으로 함수를 빠져나간다.

 

다음 그림은 cfs 런큐에 소속된 하나의 스케줄 엔티티에 대해 decay할 기간을 적용시킨 모습을 보여준다.

 

디큐 시 엔티티 로드 평균 산출

dequeue_entity_load_avg()

kernel/sched/fair.c

/*
 * Remove se's load from this cfs_rq child load-average, if the entity is
 * transitioning to a blocked state we track its projected decay using
 * blocked_load_avg.
 */
static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
                                                  struct sched_entity *se,
                                                  int sleep)
{
        update_entity_load_avg(se, 1);
        /* we force update consideration on load-balancer moves */
        update_cfs_rq_blocked_load(cfs_rq, !sleep);

        cfs_rq->runnable_load_avg -= se->avg.load_avg_contrib;
        if (sleep) {
                cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
                se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
        } /* migrations, e.g. sleep=0 leave decay_count == 0 */
}

스케줄 엔티티가 디큐되면서 수행할 로드 평균을 갱신한다. cfs 런큐의 러너블 로드 평균에서 스케줄 엔팉티의 로드 평균 기여를 감소시키고 인수 sleep=1 요청된 경우 cfs 런큐의 블럭드 로드 평균에 추가한다.

  • 코드 라인 10~12에서 디큐 관련 산출을 하기 전에 먼저 스케줄 엔티티의 로드 평균을 산출하고 블럭드 로드 평균까지 갱신한다.
  • 코드 라인 14에서 cfs 런큐의 러너블 로드 평균을 스케줄 엔티티의 로드 평균 기여분만큼 감소시킨다.
  • 코드 라인 15~18에서 인수 sleep=1인 경우 감소 시킨 기여분을 cfs 런큐의 블럭드 로드 평균에 추가하고 cfs 런큐의 decay_counter를 스케줄 엔티티에 복사한다.

 

다음 그림은 dequeue_eneity_load_avg() 함수의 처리 과정을 보여준다.

 

Idle 관련 엔티티 로드 평균 산출

idle 상태로 진입하거나 빠져나올 때마다 러너블 평균을 산출한다.

idle_enter_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed running time before entering
 * idle. if the last scheduled task is not a CFS task, idle_enter will
 * be the only way to update the runnable statistic.
 */
void idle_enter_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 1);
}

idle 상태로 진입하기 전에  러너블 평균을 갱신한다.

 

idle_exit_fair()

kernel/sched/fair.c

/*
 * Update the rq's load with the elapsed idle time before a task is
 * scheduled. if the newly scheduled task is not a CFS task, idle_exit will
 * be the only way to update the runnable statistic.
 */
void idle_exit_fair(struct rq *this_rq)
{
        update_rq_runnable_avg(this_rq, 0);
}

idle 상태에서 빠져나오면 러너블 평균을 갱신하고 그 값을 태스크 그룹에도 반영한다.

 

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

스케줄 틱마다 호출되는 scheduler_tick() 함수와 hr 틱마다 호출되는 hrtick()  함수는 현재 curr에서 동작하는 태스크의 스케줄러의 (*task_tick) 후크 함수를 호출한다. 예를 들어 현재 런큐의 curr가 cfs 태스크인 경우 task_tick_fair() 함수가 호출되는데 태스크와 관련된 스케줄 엔티티부터 최상위 스케줄 엔티티까지 entity_tick() 함수를 호출하여 PELT와 관련된 함수들을 호출하고 스케줄 틱으로 호출된 경우 리스케줄 여부를 체크하고 hr 틱으로 호출되는 경우 무조건 리스케줄 요청한다.

  • 함수 호출 경로 예)
    • 스케줄 틱: scheduler_tick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=0으로 호출된다.
    • hr 틱: hrtick() -> task_tick_fair() -> entity_tick()
      • entity_tick() 함수를 호출할 때 인수 queued=1로 호출된다.

 

다음 그림은 entity_tick()에 대한 함수 흐름을 보여준다.

entity_tick()

kernel/sched/fair.c

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_entity_load_avg(curr, 1);
        update_cfs_rq_blocked_load(cfs_rq, 1);
        update_cfs_shares(cfs_rq);

#ifdef CONFIG_SCHED_HRTICK
        /*
         * queued ticks are scheduled to match the slice, so don't bother
         * validating it and just reschedule.
         */
        if (queued) {
                resched_curr(rq_of(cfs_rq));
                return;
        }
        /*
         * don't let the period tick interfere with the hrtick preemption
         */
        if (!sched_feat(DOUBLE_TICK) &&
                        hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
                return;
#endif

        if (cfs_rq->nr_running > 1)
                check_preempt_tick(cfs_rq, curr);
}

이 함수는 스케줄 틱 또는 hr 틱을 통해 호출되며 인수로 요청한 엔티티에 대한 로드(PELT) 갱신과 preemption 필요를 체크한다.

  • 코드 라인 7에서 PELT 관련 산출을 하기 전에 사전 준비를 위해 인수로 요청한 스케줄 엔티티의 런타임 통계들을 갱신한다.
  • 코드 라인 12에서 엔티티의 로드 평균 기여값을 갱신한다.
  • 코드 라인 13에서 스케줄 엔티티가 포함된 cfs 런큐의 러너블 로드와 블럭드 로드를 합하여 기여분을 cfs 런큐와 tg에 갱신한다.
  • 코드 라인 14에서 shares * 비율(tg에서 cfs 런큐의 로드 기여값이 차지하는 일정 비율)을 사용하여 스케줄 엔티티의 weight을 갱신하고 cfs 런큐의 로드 weight도 갱신한다.
  • 코드 라인 16~24에서 hrtick을 사용하는 커널에서 hrtick() 함수를 통해 호출된 경우 인수 queued=1로 진입한다. 이 때에는 무조건 리스케줄 요청을 하고 함수를 빠져나간다.
  • 코드 라인 28~30에서 DOUBLE_TICK feature를 사용하지 않는 경우 hrtick을 프로그래밍한다.
    • rpi2: DOUBLE_TICK 기능을 사용하지 않는다.
  • 코드 라인 33~34에서 이 루틴은 hrtick을 제외한 스케줄 틱을 사용할 때에만 진입되는데 러너블 태스크가 2개 이상인 경우 preemption 체크를 수행한다.

 

스케줄 엔티티의 러너블 로드 평균  갱신

 

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

스케줄 엔티티에 대한 러너블 로드 평균을 갱신한다. 인수로 cfs 런큐까지 갱신 요청하는 경우 기여도를 계산하여 cfs 런큐의 러너블 로드 평균도 갱신한다.

  • a) 스케줄 엔티티에 대한 러너블 로드 평균을 산출하기 위한 러너블 평균합(runnable_avg_sum) 및 러너블 평균 기간(runnable_avg_periods) 산출
    • 기존 러너블 평균합을 decay 시킨 값을 old라고 하고,
    • 산정할 기간을 decay한 값을 new라고 할 때
    • se->avg.runnable_avg_sum에는
      • 스케줄 엔티티에 대해 러너블 상태(러닝 포함)의 태스크에 대해서는  new + old 값을 반영하고, 러너블 상태가 아닌 태스크에 대해서는 old 값만 반영한다.
      • 추후 커널 소스에서는 러닝 상태를 별도로 관리한다.
    • se->avg.runnable_avg_periods에는
      • 스케줄 엔티티의 상태와 관계 없이 new + old 값을 반영한다.
  • b) cfs 런큐의 러너블 로드 평균 갱신
    • se->avg.load_avg_contrib

 

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

 

다음 그림은 __update_entity_load_avg() 함수가 스케줄 엔티티의 러너블 평균을 구하는 모습을 보여준다.

 

다음 그림은 스케줄 틱이 동작할 때 entity_tick() 함수에서 update_entity_load_avg() 함수를 호출할 때 동작하는 모습을 보여준다.

 

entity_is_task()

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를 수행하는 경우의 모습을 보여준다.

 

기존(old) 평균의 감소(decay)

기존 로드 값에 대해 ms 단위의 지나간 기간 만큼의 감쇠 비율(decay factor)로 곱한다. decay 요율은 ‘y^32 = 0.5’를 사용하는데 32ms 이전의 값은 0.5의 감쇠 비율(decay factor)을 사용한다. 이러한 경우 기존 로드 값이 512라고 할 때 4ms의 기간이 지나 감소된 로드 값은 y^4가 된다. 먼저 y에 대한 값을 계산해 보면 y=0.5^(1/32) = 0.978572… 가 산출된다. 이제 결정된 y 값을 사용하여 4ms 기간이 지난 감쇠 비율(decay factor)을 계산해 보면 ‘0.5^(1/32)^4 = 0.917004… ‘와 같이 산출된다.  결국 ‘512 * 0.91700404 = 469’라는 로드 값으로 줄어든다. 리눅스는 소수 표현을 사용하지 않으므로 빠른 연산을 하기 위해 ms 단위의 기간별로 미리 산출해둔 감쇠 비율을 32bit shift 값을 사용한 정수로 mult화 시켜 미리 테이블로 만들어 두고 활용한다. (0.91700404 << 32 = 0xeac0c6e6)

기존 로드 평균 값에 대해 ms 단위의 지나간 기간 만큼 감소(decay)한다.

  • 예) val=0x64, 기간 n=0~63(ms)일 때 산출되는 값들의 변화
    • 산출 식: ((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

 

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

로드 값 val을 n 기간(ms) 에 해당하는 감소 비율로 줄인다. n=0인 경우  1.0 요율이고, n=32인 경우 0.5 요율이다.

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

 

미리 만들어진 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,
};

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

  • n 번째 요율을 계산하는 수식(32bit shift 적용):
    • ‘y^n’은 실수 요율이고 커널에서 사용하기 위해 32비트 shift를 적용하여 정수로 바꾼다.
      • ‘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

 

새(new) 기간에 대한 기여 감소 합계(decay sum)

기존 값이 ms 단위의 지나간 기간 만큼 감쇠 비율(decay factor)을 사용하여 산출한 것에 반해 새 로드 값은 1 ms 단위의 각각의 지나간 기간에 대해 적용한 감쇠 비율을 곱한 값을 모두 더해 산출한다. 예를 들어 3ms의 기간이 흐른 로드 값은 ‘1024*y^3 + 1024*y^2 + 1024*y’ = ‘959 + 980 + 1002 = 2941’이다. (y 값은 ‘0.5^(1/32) = 0.97857206…;) 즉 1ms에 해당하는 1024us의 값이 3ms가 지나면 959us로 작아졌음을 알 수 있다. 리눅스는 빠른 산출을 위해 각 기간 별로 산출된 감쇠 비율에 대한 총합(deacy sum)을 테이블로 만들어 사용한다.

__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)

 

미리 만들어진 PELT용 decay factor sum

kernel/sched/fair.c

/*
 * 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[] 테이블은 다음 수식으로 만들어졌다.

  • ‘sum(y^k) { 1<=k<=n } y^32=0.5’은 실수 요율이고 커널에서 사용하기 위해 정수로 바꾸기 위해 산출된 값에 12bit shift를 적용한다.
    • 1024 * Sum(y^k) { 1<=k<=n }  y^32=0.5
  • y값을 먼저 구해보면
    • y=0.5^(1/32)=0.97852062…
  • 인덱스 값 n에 1부터 31까지 사용한 결과 값은?
    • sum(1024 * y^1) { 1<=k<=1 } = 1024 * (y^1) = 1002
    • sum(1024 * y^2) { 1<=k<=2 } =1024 * (y^1 + y^2) = 1002 + 980 = 1,982
    • sum(1024 * y^3) { 1<=k<=3 } =1024 * (y^1 + y^2 + y^3) = 1,002 + 980 + 959=2,941
    • sum(1024 * y^32)=1024 * (y^1 + y^2 + y^3 + … + y^32) = 1,002 + 980 + 959 + … + 512=23,371

 

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

스케줄링 엔티티의 러너블 로드 평균 값과 러너블 로드 기간의 decay 산출이 완료된 후 아래 함수가 호출된다. 여기에서는 엔티티가 태스크용인지 태스크 그룹용인지에 따라 처리하는 방법이 나뉜다.

  • 태스크용 스케줄 엔티티의 경우 se->avg.load_avg_contrib 값을 산출할 때 로드 weight과 러너블 기간 비율을 곱하여 산출한다.
    • = weight * 러너블 기간 비율(러너블 평균 합 / 러너블 기간 합)
    • = se->load.weight * se->avg.runnable_avg_sum / (se->avg.runnable_avg_period+1)
  • 태스크 그룹용 스케줄 엔티티의 경우 태스크 그룹에 기여하는 정도를 알아보기 위해 nice-0의 weight를 사용하여 러너블 기간 비율을 곱하여 산출한다.
    • = nice-0용 weight * 러너블 기간 비율(러너블 평균 합 / 러너블 기간 합)
    • = 1024 * se->avg.runnable_avg_sum / (se->avg.runnable_avg_period+1)

__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에서 스케줄링 엔티티의 로드 평균 기여 값의 변화값을 반환한다.

 

스케줄링 엔티티 로드 평균 기여 갱신 – a) for 태스크용 se

__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)

 

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

 

스케줄링 엔티티 로드 평균 기여 갱신 – b) for 태스크 그룹용 se

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

cfs 런큐와 태스크 그룹용 스케줄 엔티티의 러너블 평균 기여값을 산출한다. 단 변화분이 절대값이 기존 값의 1/64을 초과하는 경우에만 갱신한다. 태스크 그룹은 cpu별로 동작하는 cfs 런큐의 tg_runnable_contrib를 모두 합한 값이다. 이렇게 산출된 러너블 평균은 이어진 다음 함수에서 사용된다.

  • 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 로드 평균을 업데이트한다. blocked_load_avg에서 removed_load 만큼을 감소시킨 값을 ms 단위로 decay할 기간만큼 decay 한다.

  • 코드 라인 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에서 태스크 그룹용 로드 평균 기여를 갱신한다.

 

다음 그림은 blocked_load_avg – removed_load 값을 10ms decay 하는 모습을 보여준다.

 

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

 

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

 

CFS Shares 갱신으로 인한 로드 weight 재반영

kernel/sched/fair.c

update_cfs_shares()

static void update_cfs_shares(struct cfs_rq *cfs_rq)
{
        struct task_group *tg;
        struct sched_entity *se;
        long shares;

        tg = cfs_rq->tg;
        se = tg->se[cpu_of(rq_of(cfs_rq))];
        if (!se || throttled_hierarchy(cfs_rq))
                return;
#ifndef CONFIG_SMP
        if (likely(se->load.weight == tg->shares))
                return;
#endif
        shares = calc_cfs_shares(cfs_rq, tg);

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

태스크 그룹의 shares 값에 대한 cfs 런큐의 로드 비율을 적용하여 스케줄 엔티티, cfs 런큐 및 런큐등의 로드 weight을 갱신한다.

  • 코드 라인 7~8에서 cfs 런큐로 태스크 그룹 및 스케줄 엔티티를 알아온다.
  • 코드 라인 9~10에서 스케줄 엔티티가 없거나 cfs 런큐가 스로틀된 경우 함수를 빠져나간다.
  • 코드 라인 11~14에서 UP 시스템에서 태스크 그룹의 shares 값과 스케줄 엔티티의 로드 값이 동일하면 최대치를 사용하는 중이므로 함수를 빠져나간다.
  • 코드 라인 15에서 태스크 그룹의 cfs shares 값에 cfs 런큐 로드 비율이 반영된 로드 weight 값을 산출한다
  • 코드 라인 17에서 산출된 shares 값으로 스케줄 엔티티의 로드 weight 값을 재계산한다.

 

calc_cfs_shares()

kernel/sched/fair.c

static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
{
        long tg_weight, load, shares;

        tg_weight = calc_tg_weight(tg, cfs_rq);
        load = cfs_rq->load.weight;

        shares = (tg->shares * load);
        if (tg_weight)
                shares /= tg_weight; 

        if (shares < MIN_SHARES)
                shares = MIN_SHARES;
        if (shares > tg->shares) 
                shares = tg->shares;

        return shares;
}

태스크 그룹의 cfs shares 값에 대한 cfs 런큐  로드 비율이 반영된 로드 weight 값을 산출한다. (태스크 그룹의 shares * cfs 런큐 로드 weight / 태스크 그룹 weight)

  • 코드 라인 5에서 태스크 그룹의 weight 값을 tg_weight에 대입한다.
  • 코드 라인 6에서 cfs 런큐의 로드 weight 값을 load에 대입한다.
  • 코드 라인 8~10에서 태스크 그룹의 shares 값과 load를 곱한 후 태스크 그룹의 weight 값으로 나눈다.
    • tg->shares * cfs_rq->load.weight / tg_weight
  • 코드 라인 12~17에서 산출된 share 값이 최소 shares(2)보다 작지 않도록 제한하고 태스크 그룹의 shares 값보다 크지 않도록 제한하고 반환한다.
    • 2 <= 계산된 shaers <= tg->shares

 

다음 그림은 태스크 그룹의 shares 값에 대하여 태스크 그룹 대비 cfs 런큐의 로드기여 비율을 반영하여 산출한다.

  • UP 시스템에서는 태스크 그룹 대비 cfs 런큐의 로드 weight 비율을 반영하지 않는다. 따라서 태스크 그룹의 shares 값을 100% 반영한다.

 

calc_tg_weight()

kernel/sched/fair.c

static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
{
        long tg_weight;

        /*
         * Use this CPU's actual weight instead of the last load_contribution
         * to gain a more accurate current total weight. See
         * update_cfs_rq_load_contribution().
         */
        tg_weight = atomic_long_read(&tg->load_avg);
        tg_weight -= cfs_rq->tg_load_contrib;
        tg_weight += cfs_rq->load.weight;

        return tg_weight;
}

태스크 그룹의 로드 평균 값을 읽어와서 cfs 런큐의 태스크 그룹 로드 기여 값을 감소시키고 다시 cfs 런큐의 로드 weight 값을 더한 후 반환한다.

  • tg->load_avg – cfs_rq->tg_load_contrib + cfs_rq->load.weight

 

로드 weight 재설정

reweight_entity()

kernel/sched/fair.c

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

        update_load_set(&se->load, weight);

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

스케줄 엔티티의 로드 weight 값을 변경 시킨다. 스케줄 엔티티가 cfs 런큐에서 이미 동작중인 경우 cfs 런큐와 런큐의 로드 값을 다음 예와 같이 조정한다.

  • 예) se->load.weight 값이 5000 -> 6024로 변경되는 경우
    • cfs_rq->load -= 5000   -> cfs_rq->load += 6024
    • rq->load -= 5000 -> rq->load += 6024 (최상위 스케줄 엔티티인 경우)

 

  • 코드 라인 4~7에서 요청한 스케줄 엔티티가 런큐에 있고 cfs 런큐에서 지금 돌고 있는 중이면 현재 태스크의 런타임 통계를 갱신한다.
  • 코드 라인 8에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에서 감소시킨다. 또한 최상위 스케줄 엔티티인 경우 런큐의 로드 weight 값을 동일하게 감소시킨다.
  • 코드 라인 11에서 스케줄 엔티티의 로드 weight 값을 갱신한다.
  • 코드 라인 13~14에서 요청한 스케줄 엔티티가 런큐에 있는 경우 스케줄 엔티티의 로드 weight 값을 cfs 런큐에 추가한다. 또한 최상위 스케줄 엔티티인 경우 런큐의 로드 weight 값에 동일하게 추가한다.

 

로드 weight이 재산출되야 하는 상황들을 알아본다.

  • 태스크 그룹의 shares 값을 변경 시 sched_group_set_shares() -> 변경할 그룹부터 최상위 그룹까지 반복: update_cfs_shares() -> reweight_entity()에서 사용된다.
  • 요청 스케줄 엔티티가 엔큐될 때 enqueue_entity() -> update_cfs_shares() -> reweight_entity()
  • 요청 스케줄 엔티티가 디큐될 때 enqueue_entity() -> update_cfs_shares() -> reweight_entity()

 

다음 그림은 스케줄 엔티티의 로드 weight 값이 변경될 때 관련된 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으로 리셋한다.

 

Account Entity Enqueue & Dequeue

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);
        if (!parent_entity(se))
                update_load_add(&rq_of(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 런큐에 스케줄 엔티티의 로드를 추가한다. 부모 스케줄 엔티티가 없으면 cfs 런큐가 속한 런큐의 로드에도 추가한다.

  • 코드 라인 4에서 cfs 런큐에 스케줄 엔티티의 로드를 추가한다.
  • 코드 라인 5~6에서 부모 스케줄 엔티티가 없으면 cfs 런큐가 속한 런큐의 로드에도 추가한다.
  • 코드 라인 8~13에서 smp 시스템에서 태스크용 스케줄 엔티티인 경우 NUMA 시스템을 위해 런큐의 nr_numa_running 및 nr_preferred_running을 갱신한다. 그런 후 런큐의 cfs_tasks 리스트에 se->group_node를 추가한다.
  • 코드 라인 15에서 런큐의 nr_running 카운터를 1 증가시킨다.

스케줄 엔티티가 cfs 런큐에 엔큐되는 경우 관련 값들을 추가한다.

  • 코드 라인 4에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에 추가한다.
  • 코드 라인 5~6에서 최상위 스케줄 엔티티인 경우 런큐에도 추가한다.
  • 코드 라인 7~14에서 태스크 타입 스케줄 엔티티인 경우 누마 관련 값도 증가시키고 스케줄 엔티티를 런큐의 cfs_tasks 리스트에 추가한다.
  • 코드 라인 15에서 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 != -1);
        rq->nr_preferred_running += (p->numa_preferred_nid == task_node(p));
}

태스크가 엔큐되고 선호하는 누마 노드로 추가된 경우 다음의 값을 1씩 증가시킨다.

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

 

다음 그림은 스케줄 엔티티의 로드 weight 값을 런큐 및 cfs 런큐에 증감시키는 상황을 보여준다.

  • 태스크형 스케줄 엔티티의 경우 cfs_tasks 리스트에 추가/삭제되는 것도 알 수 있다.
  • 런큐의 load.weight 증감은 최상위 엔티티의 load.weight에 대해서만 해당한다.

 

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);
        if (!parent_entity(se))
                update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
        if (entity_is_task(se)) {
                account_numa_dequeue(rq_of(cfs_rq), task_of(se));
                list_del_init(&se->group_node);
        }
        cfs_rq->nr_running--;
}

스케줄 엔티티가 cfs 런큐에서 디큐되는 경우 관련 값들을 감소시킨다.

  • 코드 라인 4에서 스케줄 엔티티의 로드 weight 값을 cfs 런큐에서 감소시킨다.
  • 코드 라인 5~6에서 최상위 스케줄 엔티티인 경우 런큐에서도 감소시킨다.
  • 코드 라인 7~10에서 태스크 타입 스케줄 엔티티인 경우 누마 관련 값을 감소시키고, 런큐의 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 != -1);
        rq->nr_preferred_running -= (p->numa_preferred_nid == task_node(p));
}

태스크가 디큐되고 선호하는 누마 노드로 추가된 경우 다음의 값을 1씩 감소시킨다.

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

 

엔큐 & 디큐 시 엔티티 로드 평균 산출

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~16에서 낮은 확률로 스케줄 엔티티의 decay_count가 0이하인 경우 스케줄 엔티티의 avg.last_runnable_update를 현재 시각(clock_task)으로 갱신한다.
  • 코드 라인 17~31에서 decay_count가 음수인 경우 스케줄 엔티티의 avg.last_runnable_update(ns)를 decay_count(ms) 만큼 이전으로 감소시킨다. 그리고 update_entity_load_avg()를 호출하여 로드 평균을 갱신하고 decay_count는 0으로 초기화한다.
  • 코드 라인 33~35에서 스케줄 엔티티의 decay_count가 0을 초과한 경우 스케줄 엔티티의 로드 평균 기여를 ‘cfs 런큐의 decay_counter – 스케줄 엔티티의 avg.decay_count’ 만큼 decay 한다.
  • 코드 라인 38~41에서 decay_count가 0을 초과하였었고 인수 wakeup=1이 주어진 경우 블럭드로드 기여를 감소시키고 다시 update_entity_load_avg()를 호출하여 로드 평균을 갱신한다.
  • 코드 라인 43에서 스케줄 엔티티에 있는 로드 평균 기여를 cfs 런큐의 러너블 로드 평균에  추가한다.
  • 코드 라인 45에서 블럭드 로드를 갱신하고 러너블 평균과 더해 cfs 런큐의 tg_load_contrib와 태스크 그룹의 load_avg 에 추가한다.

 


구조체

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
    • 러너블 로드라 불리며 러너블(curr + rb 트리에서 대기) 타임 평균을 합하였다.
  • runnable_avg_period
    • Idle 타임을 포함한 전체 시간 평균을 합하였다.
  • last_runnable_update
    • 러너블 로드를 갱신한 마지막 시각
  • decay_count
    • 트래킹 migration에 사용하는 엔티티 decay 카운터로 슬립되어 엔티티가 cfs 런큐를 벗어난 시간을 decay하기 위해 사용된다.
  • load_avg_contrib
    • 평균 로드 기여(weight * runnable_avg_sum / (runnable_avg_period+1))
    • 태스크용 스케줄 엔티티에서는 엔티티의 load.weight이 러너블 평균 비율로 곱하여 산출된다.
    • 태스크 그룹용 스케줄 엔티티에서는 shares 값이 tg에 대한 cfs 비율 및 로드 비율 등이 적용되어 산출된다.

 

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
      • 각 cpu에서 이 그룹에 연결된 스케줄 엔티티(cpu 수 만큼)
    • **cfs_rq
      • 각 cpu에서 이 그룹에 연결된 cfs 런큐
    • shares
      • 그룹에 적용할 로드 weight 비율
    • load_avg
      • cfs 런큐의 로드 평균을 모두 합한 값으로 결국 스케줄 엔티티의 로드 평균 기여값을 모두 합한 값이다.
    • runnable_avg
      • cfs 런큐의 러너블 평균을 모두 합한 값으로 결국 스케줄 엔티티의 러너블 평균을 모두 합한 값이다.
  • rt 그룹 스케줄링 관련
    • **rt_se
      • 각 cpu에서 이 그룹에 연결된 rt 스케줄 엔티티(cpu 수 만큼)
    • **rt_rq
      • 각 cpu에서 이 그룹에 연결된 rt 런큐
    • rt_bandwidth
  • autogroup 관련
    • *autogroup

 

참고

런큐 로드 평균(cpu_load[]) – v4.0

<kernel v4.0>

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

cpu 로드 밸런스에 사용하였던 이 방법은  커널 v5.3-rc1에서 제거되었다.

 

런큐 로드 평균 (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

 


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 값으로 하여 반환한다.

 

참고

Persistent Memory & DAX

 

Persistent Memory

Persistent 메모리는 다음과 같은 속성이 있다.

  • Solid State 고성능 바이트 단위 주소 접근이 가능한 디바이스로 메모리 버스위에서 동작한다.
    • DRAM과 같이 직접 addressing이 가능한 물리 주소를 지원하여 시스템 메모리로도 사용할 수 있다.
  • 전원이 차단된 상태에서도 데이터가 보존되는 비휘발성 메모리이다.
    • Flash SSD 같은 종류들보다 훨씬 access 타임이 빠르다.
    • 주의: 기존 NVRAM의 주요 특성을 가지고 있으나 혼동하면 안된다.
  • NVDIMM 버스 사용
    • DRAM이 장착되는 DIMM 슬롯을 이용하여 DRAM과 같은 대역폭을 사용한다.
    • SSD 등이 사용하는 pci/pcie 및 usb 버스 등의 IO 채널을 사용하는 것보다 훨씬 빠르다.
  • DRAM 보다 더 저렴하여 같은 비용으로 DRAM 보다 더 큰 용량을 사용할 수 있다.
  • DRAM 처럼 캐시 사용이 가능한 상태로 동작할 수 있다. (보통 그렇게 사용한다)
  • Pmem으로 줄여 표현하기도 한다.

 

NVDIMM Pmem

현재 가장 많이 사용하고 있는 DIMM 버스를 이용하는 제품 두 종류를 소개한다.

  • NVDIMM-N 타입 persistent 메모리
    • 8/16/32G 제품이 먼저 출시되었고, DRAM + NAND 플래시 구성으로 만들어졌다.
    • 장점: 읽고 쓰기 성능이 3D XPoint보다 빠르다.
    • 단점: 정전시 DRAM 데이터를 NAND에 백업하기 위해 super capacitor가 필수로 사용된다.
  • 3D XPoint persistent 메모리
    • 장점: 자체적으로 비휘발성이 유지되므로 정전을 대비하기 위해 super capacitor를 필요로 하지 않는다.
    • 단점: 읽고 쓰기 성능이 DRAM+NAND 구성보다 느리다.
    • 인텔과 마이크론이 개발하였으며, 인텔은 Optane, 마이크론은 QuantX라는 브랜드명을 사한다. 현재 8~512G 제품이 출시되어 있다.

 

참고: HBM 버스

  • DIMM 보다 더 빠른 메모리 버스로 테라 단위의 대역폭을 요구하는 고속 GPU등에 사용되었다. 다만 고속을 위해 칩 외부의 슬롯 형태가 아닌 칩에 통합되어 제작해야 하는 단점이 있다.

 

다음 그림은 NVDIMM-N 타입 persistent 메모리이다. 배터리(super capacitor)가 외부에서 공급되는 것을 확인할 수 있다.

 

다음 그림은 NVDIMM-N 타입 persistent 메모리의 블럭 다이어그램이다.

 

다음 그림은 인텔 XEON CPU와 같이 사용해야 하는 Optane DC Persistent 메모리를 보여준다.

 

NVDIMM 표준화 및 규격

  • NVDIMM 규격에 사용되는 NV(Non-Volatile) 미디어는 NAND 플래시, 3D XPoint, 자기 메모리, 상변화 메모리, 저항 변화 메모리 등이 포함된다.
  • 다음 3개의 규격이 사용된다.
    • NVDIMM-N
      • DRAM(DDR3/DDR4) + NV 미디어(최소 DRAM과 1:1 용량)로 구성하고 메모리 성격을 가진다.
      • DRAM과 바이트 단위 주소 액세스를 할 수 있으나 NV 미디어와는 직접 액세스하지 않는다.
      • NV 미디어는 DRAM의 백업 역할을 한다. 전원 fail 시에는 DRAM의 백업을 위해 추가 배터리 연결이 필요하다.
      • 세 타입 중 가장 빠른 수십 나노초(ns)의 레이튼시를 갖는다.
    • NVDIMM-F
      • NV 미디어로만 구성하고, 스토리지 성격을 가진다.
      • 윈도 매커니즘을 통해 매핑이 가능하고, 블럭 단위의 액세스를 지향한다. (마운트하여 사용하는 형태 등)
      • 세 타입 중 가장 느린 수십 마이크로초(us)의 레이튼시를 갖는다.
    • NVDIMM-P
      • NVDIMM-N과 F를 섞은 형태로 DRAM+NV 미디어(DRAM보다 훨씬 큰 용량)로 구성된 하이브리드 성격을 가진다.
      • DDR(4 or 5) 프로토콜을 사용하는 DRAM 인터페이스를 사용하지만 non-volatile 성격을 갖는 DRAM을 사용하여 배터리 백업을 필요치 않는다.
      • 세 타입 중 중간인 수백 나노초(ns)의 레이튼시를 갖는다.
      • 2018년에 규격이 확정되었고, 아직 제품화되지는 않았다.

 

NVDIMM pmem 드라이버

커널에서의 persistent 메모리 지원은 커널 4.2 이후부터 nvdimm 드라이버가 소개되었고, 커널 v4.4에서 안정화되었다.

  • 디바이스 트리에서 nvdimm pmem 드라이버 지원
    • compatible = “pmem-region
    • volatile 속성 여부에 따라 두 가지 타입의 메모리를 지원한다.
      • volatile region
        • 속성이 있는 경우 시스템 메모리와 같이 물리 주소가 부여되어 시스템 메모리로 관리된다. (ZONE_DEVICE)
        • 두 개 이상의 pmem을 사용하는 경우 인터리브 구성을 한다.
          • 시스템 메모리에 매핑 시 pmem을 1:1로 리니어하게 매핑하지 않고, pmem 드라이버에서 인터리브하게 매핑한다.
      • pmem region
        • volatile 속성이 지정되지 않은 이 region은 DAX를 지원하는 파일 시스템에 마운트하여 사용한다.

 

pmem region으로 등록되어 사용하는 예)

        /*
         * This node specifies one 4KB region spanning from
         * 0x5000 to 0x5fff that is backed by non-volatile memory.
         */
        pmem@5000 {
                compatible = "pmem-region";
                reg = <0x00005000 0x00001000>;
        };

 

volatile region으로 등록되어 사용하는 예)

        /*
         * This node specifies two 4KB regions that are backed by
         * volatile (normal) memory.
         */
        pmem@6000 {
                compatible = "pmem-region";
                reg = < 0x00006000 0x00001000
                        0x00008000 0x00001000 >;
                volatile;
        };

 

다음 그림은 인텔에서 보여준 nvdimm pmem을 이용하는 여러 가지 방법을 보여준다.

 

NVDIMM 블럭 매핑

다음 그림은 커널 블럭디바이스에서의 로지컬 블럭과 실제 NVDIMM의 물리 블럭이 매핑되어 사용되는 모습을 보여준다.

  • 매번 같은 블럭에 기록하는 것처럼 행동하여도, NVDIMM 내부에서는 새로운 빈 블럭을 찾아 기록한다. (SSD와 동일)

 


DAX(Direct Access)

DAX를 사용하면 Persistent 메모리 또는 블럭 장치에 저장된 파일에 직접 액세스할 수 있다. 직접 액세스하므로 커널은 페이지 캐시를 사용하지 않는다. 그러나 파일 시스템에서 DAX 지원이 없으면 Standard File API를 통해 파일 읽기 및 쓰기를 버퍼링하는데 페이지 캐시를 사용하고 추가적인 복사 작업이 소요된다.

 

다음 그림에서 파란색은 파일 API를 사용한 접근 방법과, DAX를 지원하는 파일 시스템을 통해 직접 접근하는 방법을 보여준다.

 

위의 개념을 인텔 Optane DC Persistent Memory를 사용하는 경우 앞으로 다룰 namespace와 region 개념을 포함하여 보여주고 있다.

 

Persistent memory-aware File System

운영체제에 따라 다음 파일 시스템이 DAX를 지원한다.

  •  리눅스
    • ext2, ext4, xfs 파일시스템
  • 윈도우 서버
    • ntfs 파일 시스템

 

파일마운트 시 DAX enable

파일 시스템을 마운트 시 파일 시스템 종류별로 DAX를 enable 하는 방법이 약간 차이가 있다.

  • ext2
    • -o dax 옵션을 사용하면 마운트된 모든 파일에 적용된다. (/etc/fstab 에서는 dax 옵션을 사용한다.)
  • ext4 & xfs
    • 다음 옵션에 따라 개별 디렉토리 및 파일을 DAX 지원 상태로 변경할 수 있다.
      • -o dax=inode
        • persistent 속성(FS_XFLAG_DAX)을 사용하여 정규 파일 및 디렉토리에 적용/제거 할 수 있고, 이 옵션은 디폴트로 사용된다.
        • 예) xfs_io -c ‘chattr +x’ <dirname>
          • <dirname>부터 이후에 만들어지는 파일이나 하위 디렉토리는 dax가 enable 상태로 적용된다.
      • -o dax=never
        • 파일 및 디렉토리를 생성시 dax가 적용되지 않는다.
      • -o dax=always
        • 파일 및 디렉토리를 생성시 항상 dax가 적용된다.
      • -o dax
        • -o dax=always와 동일한 옵션으로 -o dax 만을 사용하는 경우는 제거될 예정이다.

 

DAX 파일 시스템의 블럭 사이즈

DAX를 지원하기 위한 블럭 디바이스는 파일 시스템의 블럭 사이즈를 커널의 PAGE_SIZE와 동일하게 사용해서 생성해야 한다.

# fdisk -l /dev/ndblk0.1s
Disk /dev/ndblk0.1s: 32 GiB, 34325135360 bytes, 8380160 sectors
Units: sectors of 1 * 4096 = 4096 bytes
Sector size (logical/physical): 4096 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

 

DAX(Direct Access) 커널 옵션

다음과 같은 커널 옵션들을 살펴본다.

  • DAX: direct access to differentiated memory”
    • CONFIG_DEV_DAX
    • mmap() 사용을 통해 저수준의 접근이 가능한 캐릭터 디바이스이다.
    • /dev/daxX.Y
  • PMEM DAX: direct access to persistent memory”
    • CONFIG_DEV_DAX_PMEM
    • 유저 스페이스 헬퍼 라이브러리인 libnvdimm 서브시스템을 통해 저수준의 접근이 가능하다.
      • ndctl 유틸리티
  • KMEM DAX: volatile-use of persistent memory”
    •  CONFIG_DEV_DAX_KMEM
    • DRAM과 같은 형태로 이용하므로 어떠한 applicaton의 수정 없이 사용할 수 있다.
    • ZONE_DEVICE 및 MEMORY_HOTPLUG를 사용한다.
    • 현재 pfn 메타데이터를 DRAM에 저장하므로 Persistent 메모리가 DRAM 용량보다 훨씬 큰 시스템 환경의 경우 현재 커널 버전에는 사용하지 않아야 한다.
      • PMEM DAX 처럼 pfn 메타데이터를 Persistent 메모리에 저장할 수 있는 옵션도 개발 완료된 상태였으나, 커널에 업스트림되지 않은 상태이다.
    • 참고: device-dax: “Hotplug” persistent memory for use like normal RAM (2019, v5.1-rc1)
  • HMEM DAX: direct access to ‘specific purpose’ memory”

 

 

KMEM DAX

시스템 물리 메모리로 구성하는 KMEM DAX는 DRAM이 사용하는 ZONE_NORMAL로 통합하지 않고, 약간 느린 메모리로 별도 분류하기 위해 ZONE_DEVICE를 사용한다. 한편 물리 메모리를 관리하기 위해 각 물리 메모리의 모든 페이지에 대응하는 pfn 메타데이터를 별도로 할당해서 가장 빠른 DRAM에 상주시켜 사용해야 한다. 따라서 persistent 메모리 용량이 매우 큰 경우에는 pfn 메타데이터 용량도 전체 메모리의 약 1.5% 만큼 소요되어 매우 커진다. 이렇게 만들어진 pfn 메타데이터는 성능을 위해 커널 메모리로 사용되는 pre-mapping된 ZONE_NORMAL(빠른 DRAM)에 할당해야 하므로 DRAM의 낭비마저 발생하는 단점이 있다. 그러므로 DRAM보다 약 8배 이상 큰 용량을 가진 persistent 메모리를 가진 시스템 구성의 경우에는 이 persistent 메모리를 물리 주소 번지를 갖는 ZONE_DEVICE로의 사용을 권장하지 않는다.

 

PMEM DAX

persistent 메모리의 할당 관리를 위한 pfn 메타데이터를 persistent storage에 만들어 관리를 하는 방법이 있다. 시스템 메모리에 비해 8배 이상 큰 용량의 persistent 메모리를 DAX를 지원하는 파일 시스템에 사용하여 마운트하여 사용하여 운용할 수 있다.

 

다음은 블럭 디바이스로 인식한 persistent 메모리의 파티션을 보여준다.

$ fdisk -l /dev/pmem0
Disk /dev/pmem0: 4 GiB, 4223664128 bytes, 8249344 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes
Disklabel type: gpt
Disk identifier: 10B97DA8-F537-6748-9E6F-ED66BBF7A047

Device       Start     End Sectors Size Type
/dev/pmem0p1  4096 8249310 8245215   4G Linux filesystem

 

다음은 블럭 디바이스로 인식한 persistent 메모리를 DAX를 지원하는 ext4 파일시스템으로 사용한 후 마운트한 예를 보여준다.

$ mkfs -t xfs /dev/pmem0
$ mount -o dax /dev/pmem0 /mnt/ext4-pmem0/

 

다음은 persistent 메모리들로 DAX를 지원하는 여러 파일시스템을 사용하여 마운트한 예를 보여준다.

$ lsblk
NAME                   MAJ:MIN RM   SIZE RO TYPE MOUNTPOINT
pmem0                  259:0    0    16G  0 disk
├─pmem0p1              259:6    0     4G  0 part /mnt/ext4-pmem0
└─pmem0p2              259:7    0  11.9G  0 part /mnt/btrfs-pmem0
pmem1                  259:1    0    16G  0 disk /mnt/xfs-pmem1

 

DAX Driver

 

Deprecated /sys/class/dax 지원

 

필요한 커널 설정

  • CONFIG_ZONE_DEVICE=y
  • CONFIG_TRANSPARENT_HUGEPAGE=y
  • CONFIG_ACPI_NFIT=m
  • CONFIG_LIBNVDIMM=m
  • CONFIG_BLK_DEV_PMEM=m
  • CONFIG_ND_BLK=m
  • CONFIG_BTT=y
  • CONFIG_NVDIMM_PFN=y
  • CONFIG_NVDIMM_DAX=y
  • CONFIG_DEV_DAX_KMEM=m
  • CONFIG_FS_DAX=y

 


NVDIMM Pmem 관리(libndctl)

 

Region

NVDIMM들을 각각의 region 또는 N-way 인터리브 세트로 묶어 하나의 region을 만들어낸다. 각 Region은 운영 가능한 타입이 있다.

 

다음 그림은 NVDIMM을 각각의 region으로 사용하거나 N-way 인터리브 세트로 구성하여 하나로 사용하는 방법을 보여준다.

  • 좌측: 각각의 NVDIMM을 각각의 region으로 구성
  • 우측: 두 개의 NVDIMM을 2-way 인터리브 세트로 구성하여 하나의 region으로 구성

(벤더의 하드웨어 설정 및 소프트웨어 툴 사용: 예) Xeon 서버의 UEFI 펌웨어 설정 + ipmctl 툴 사용)

 

Namespace

위에서 구성한 Region을 1개 이상의 Namespace로 나누어 사용할 수 있다.

  • 1개 이상의 pmem 장치가 “/dev/*”에 연결되어 사용되는 단위이다.
  • 1개 또는 여러 개의 pmem을 인터리브로 연결하여 하나의 /dev/*에 사용할 수 있는 입출력 단위이다.
  • 각 Namespace는 아래 타입과 모드를 지정하여 구성한다.
  • Namespace를 구성하는 툴은 ndctl이다.

 

다음 그림에서 두 개의 Region위에 각각 두 개의 Namespace를 만들어 총 4개의 Namespace를 구성한 모습을 볼 수 있다.

 

Type

Namespace의 액세스 타입이다. pmem은 물리적으로 아래 두 타입 중 하나만을 지원하기도 하고, 둘 다 지원하는 경우도 있다. 두 가지 타입을 모두 지원하는 경우엔 두 개 이상의 Namespace에 각각의 타입을 섞어 구성할 수도 있다.

  • PMEM
    • 휘발성 DRAM과 같은 형태이다.
    • 유저 모드 및 커널 모드에서 가상 주소를 통해 직접 액세스가 가능하다.
  • BLK
    • 슬라이딩 윈도우를 통해 수 페이지를 액세스할 수 있고, 블럭 윈도우를 이동(슬라이딩)하는 방법으로 컨트롤한다.
    • 유저 모드에서는 가상 주소를 통해 직접 액세스가 가능하지만 커널 모드에서는 직접 대응하지 않는다.

 

다음 그림은 SPA(System Physical Address)로 DPA(DIMM Physicall Address)로 향하는 모습을 보여준다.

  • PMEM 타입은 직접 액세스가 가능하지만 BLK 타입은 직접 액세스가 불가능하며 블럭 윈도우를 이동하는 방법으로 접근할 수 있다.

 

Mode

각 Namespace를 위해 다음 모드들 중 하나를 선택한다.

  • fsdax (aka. memory)
  • devdax (aka. dax)
  • raw
  • sector

 

다음 그림은 Namespace를 생성할 때 사이즈, 타입 및 모드를 지정하는 모습을 보여준다.

 

Map

PFN 메타 데이터(memmap, struct page 배열)의 저장 장소를 선택한다. (fsdax & devdax만 유효)

  • mem
    • DRAM에 저장한다.
  • dev
    • persistent storage에 저장한다.

 


각 모드별 특징과 구성 방법

fsdax (aka. memory)

  • 이 모드는 DAX를 지원하는 ext2, ext4 및 xfs 파일시스템을 사용한다.
  • ndctl create-namespace 명령을 사용할 때 옵션을 지정하지 않으면 지정되는 디폴트 모드이다.
  • mmap을 사용하여 가상 주소에 매핑할 수 있다.
  • 페이지 캐시를 제거한다.
  • /dev/pmemN[.M]
  • 블럭 디바이스 – 파일시스템
  • DAX
  • PFN 메타데이터 필요
  • Label 메타데이터

 

다음 그림은 두 개의 namespace를 fsdax 모드로 구성하는 모습을 보여준다. DAX 지원하는 파일 시스템에서 유저 application이 이 디바이스를 표준  파일 시스템을 통한 접근과 mmap()을 통한 직접 액세스  모두 사용할 수 있다.

 

devdax (aka. dax)

  • fsdax와 유사하게 이 디바이스를 mmap을 사용하여 가상 주소에 매핑할 수 있다.
  • 페이지 캐시를 제거한다.
  • /dev/daxN.M
  • 캐릭터 디바이스
  • DAX
  • PFN 메타데이터 필요
  • Label 메타데이터

 

다음 그림은 두 개의 namespace를 devdax 모드로 구성하는 모습을 보여준다. 파일 시스템이 없는 캐릭터 디바이스 형태로 유저 application이 이 디바이스를 mmap() 하여 직접 액세스할 수 있다.

 

sector

  • DAX를 지원하지 않는 모든 파일시스템에도 마운트하여 사용할 수 있다.
  • 섹터/블럭 단위를 atomic하게 수정한다.
  • /dev/pmemNs
  • 블럭 디바이스 – 파일시스템
  • no-DAX
  • no-PFN 메타데이터
  • Label 메타데이터

 

다음 그림은 두 개의 namespace를 sector 모드로 구성하는 모습을 보여준다. DAX를 지원하는 파일 시스템이라도 유저 application이 이 디바이스를 표준  파일 시스템을 통한 접근만을 허용한다.

 

다음 그림은 3개의 NVDIMM을 3-way 인터리브 세트로 구성하여 하나의 region으로 만들고, 그 위에 1 개의 namespace를 sector 모드로 구성하는 모습을 보여준다. 유저 application이 이 namespace에는 DAX를 지원하지 않는 파일 시스템을 통해 접근을 허용한다.

 

raw

  • 메모리 디스크처럼 동작한다.
  • /dev/pmemN
  • 블럭 디바이스 – 파일시스템
  • no-DAX
  • no-PFN 메타데이터
  • no Label 메타데이터

 

다음 그림은 복합 구성한 예를 보여준다.

  • 구성 정보는 Labels에 저장된다.
    • Legacy NVDIMM은 Label 저장을 지원하지 않는다.
  • 3개의 NVDIMM 유닛을 3-way 인터리브 세트로 묶어 전체 영역을 1개의 Region으로 사용한다.
  • 그리고 3 개의 Region 각각을 BLK 타입 – 섹터 모드로 구성하고, 1 개의 PMEM 타입 – fsdax 모드로 구성한다.

 

다음은 위의 그림과 동일한 설정으로 NVDIMM 컨트롤 유틸리티인 ndctl 툴로 구성을 하는 모습을 보여준다.

  • 섹터 사이즈는 운영할 리눅스 커널의 PAGE_SIZE와 동일해야 한다.
# ndctl disable-namespace all
disabled 7 namespaces

# ndctl destroy-namespace all
destroyed 7 namespaces

# ndctl create-namespace --type=blk --size=32g
{
  "dev":"namespace2.1",
  "mode":"sector",
  "uuid":"37c254cd-b123-4b13-b5b0-cd06c30e4efb",
  "sector_size":4096,
  "blockdev":"ndblk2.1s"
}

# ndctl create-namespace --type=blk --size=32g
{
  "dev":"namespace1.1",
  "mode":"sector",
  "uuid":"e1f5fa9f-4820-42f4-b8a3-be90fa00fe79",
  "sector_size":4096,
  "blockdev":"ndblk1.1s"
}

# ndctl create-namespace --type=blk --size=32g
{
  "dev":"namespace0.1",
  "mode":"sector",
  "uuid":"1f84a98c-8dac-4a29-966a-42a5ac78d78f",
  "sector_size":4096,
  "blockdev":"ndblk0.1s"
}

# ndctl create-namespace --type=pmem --mode=memory
{
  "dev":"namespace3.0",
  "mode":"memory",
  "size":99881058304,
  "uuid":"33311d73-487d-4d27-8f2a-9d682570e312",
  "blockdev":"pmem3"
}

 

다음은 fdisk를 사용하여 각 NVDIMM 디바이스들의 블럭 장치 구성 정보를 보여준다.

# fdisk -l /dev/pmem3 /dev/ndblk*
Disk /dev/pmem3: 93 GiB, 99881058304 bytes, 195080192 sectors
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

Disk /dev/ndblk0.1s: 32 GiB, 34325135360 bytes, 8380160 sectors
Units: sectors of 1 * 4096 = 4096 bytes
Sector size (logical/physical): 4096 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

Disk /dev/ndblk1.1s: 32 GiB, 34325135360 bytes, 8380160 sectors
Units: sectors of 1 * 4096 = 4096 bytes
Sector size (logical/physical): 4096 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

Disk /dev/ndblk2.1s: 32 GiB, 34325135360 bytes, 8380160 sectors
Units: sectors of 1 * 4096 = 4096 bytes
Sector size (logical/physical): 4096 bytes / 4096 bytes
I/O size (minimum/optimal): 4096 bytes / 4096 bytes

 

참고